K. Painting the Tree
time limit per test
5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Although Ororon is from the Master of the Night Wind, his weaving skills leave much to be desired. His creations resemble patterned towels more than proper woven scrolls. When the tribe's master artisans abandon hope of improving his craftsmanship, Ororon turns to sketching designs with pen and paper.

His grandmother Citlali, the renowned Granny Itztli, devises a challenge. She provides a tree with $$$n$$$ vertices and $$$m$$$ colored path operations. The operations are divided into two types:

For the operation of the first type, Ororon is given a vertex pair $$$(u,v)$$$ and a color $$$c$$$. He must paint all vertices along the unique simple path between $$$u$$$ and $$$v$$$ with color $$$c$$$. Each painting operation completely overwrites previous colors on those vertices.

For the operation of the second type, Ororon is also given a vertex pair $$$(u,v)$$$ and a color $$$c$$$. He must paint all vertices of the subtree$$$^{\text{∗}}$$$ of $$$u$$$ with $$$c$$$, assuming $$$v$$$ is the root of the tree. Note that $$$v$$$ is assumed as the root only in the current operation.

Being an expert shaman, Citlali already knows all final colors — her goal is to verify Ororon's work. Of course, Ororon also hates tedious painting, so help him determine the final color of every vertex after processing all $$$m$$$ operations in order.

$$$^{\text{∗}}$$$The subtree of a vertex $$$u$$$ is the set of all vertices that pass through $$$u$$$ on a simple path to the root.

Input

Each test has multiple test cases. The first line contains one integer $$$t$$$ ($$$1\le t\le 10^4$$$) — the number of test cases. The description of each test case follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1\le n\le 4\cdot 10^5$$$, $$$1\le m\le 2\cdot 10^5$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\cdots,a_n$$$ ($$$1\le a_i\le 10^6$$$) — the initial color of each vertex.

The $$$i$$$-th line of the following $$$n-1$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1\le x_i, y_i\le n$$$), describing an edge between vertex $$$x_i$$$ and $$$y_i$$$. It is guaranteed that these edges form a tree.

The $$$i$$$-th line of the following $$$m$$$ lines contains four integers $$$op_i$$$, $$$u_i$$$, $$$v_i$$$ and $$$c_i$$$ ($$$1\le op_i\le 2$$$, $$$1\le u_i,v_i \le n$$$, $$$1\le c_i\le 10^6$$$) — the type of the $$$i$$$-th operation and its parameters.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$4\cdot 10^5$$$, and the sum of $$$m$$$ over all test cases doesn't exceed $$$2\cdot10^5$$$.

Output

For each test case, output $$$n$$$ integers — the final color of each vertex.

Example
Input
2
1 2
1
1 1 1 4
2 1 1 5
8 4
1 2 3 4 5 6 7 8
8 1
6 7
4 6
7 5
3 2
5 2
5 1
2 4 4 5
1 3 4 6
1 1 7 2
2 5 6 1
Output
5
1 1 1 6 1 6 2 1