Background

In the 2024 postgraduate recommendation process, TheBigFatDuck, having realized its dream, left hometown Hefei for the metropolis Beijing for the further study.

Description

After a tough course, TheBigFatDuck felt hungry and he'd like to find someting to eat.

The restaurants in Beijing form a tree structure, with a total of $n$ restaurants indexed from $1$ to $n$. Each restaurant has a flavor value $a_i$.

Now, TheBigFatDuck wants to know the index of the first restaurant with a flavor value greater than or equal to $c$ that he encounter on the path $x \to y$. It's important to note that during the process, some restaurants may update their dishes, resulting in modified flavor values.

Format

Input

The first line consists of two integers, $n$ and $m$ $(1 \le n,m \le 200,000)$, representing the number of nodes in a tree and the number of operations.

The next $n-1$ lines contain two integers each, $u_i$ and $v_i$, representing the $n-1$ edges of the tree $(u_i, v_i)$.

Following that, there is a single line with $n$ integers, $a_i$, indicating the initial taste values of each restaurant.

The next $m$ lines represent the $m$ operations. Each line starts with an integer $opt$, representing the type of operation.

• If $opt = 1$, the next three integers, $u, v, c$, denote that Mr. Big Duck wants to inquire the first restaurant $i$ on the path $u \to v$ satisfied $a_i \ge c$. If there is no such $i$, the result of the inquiry is $-1$.
• If $opt = 2$, the next two integers, $x, c$, indicate that the restaurant with the number $x$ has updated its dish, and the new taste value is $c$.($a_x := c$)

Output

For each operation with $opt = 1$, output the result of the inquiry.

Sample

8 5
1 2
1 3
2 4
2 5
3 6
3 7
7 8
3 4 5 6 7 8 9 10
1 3 7 9
1 1 5 4
2 4 0
1 4 3 5
1 4 8 10

7
2
3
8

Limitation

1s，128MB

In the end, TheBigFatDuck stopped in front of a LaoxiangJi.

"I still miss the familiar taste of Fei Xi Lao Mu Chicken Soup. Perhaps I'm longing for my college days."

"Now that I've finally achieved my dream, I've lost youthful sight of the past days. Was it worth it?"

Suddenly, TheBigFatDuck realized that he had nothing to commemorate or regret because TheHamster even did not exist. It was merely a figment of his imagination, even though it provided him encouragement and support, urging him to make changes.

"Perhaps I should say thank you to TheHamster, but regardless, it's time to wake up. This is the path I have chosen, and I must keep on going."