Cho một cây vô hướng không trọng số gồm ~n~ đỉnh, đỉnh thứ ~i~ có trọng số là ~a_i~.

Với mỗi đỉnh ~u~, hãy xác định xem có bao nhiêu đỉnh ~v~ là tổ tiên của ~u~ thỏa mãn ~a_v~ > ~a_u~.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~.
• Dòng thứ hai gồm ~n~ số nguyên, số thứ ~i~ miêu tả giá trị ~a_i~.
• ~n-1~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~x,y~ miêu tả cạnh của cây.

Constraint

• ~1 \le n\le 10^5~
• ~1 \le a_i \le 10^9~

Subtask

• Subtask ~1~ ~(40\%)~: ~n \le 2000~.
• Subtaks ~2~ ~(60\%)~: Không có điều kiện gì thêm.

Output

• Gồm ~n~ số nguyên trên một dòng, số thứ ~i~ là kết quả của đỉnh thứ ~i~.

Sample Input 1:

5
3 1 4 2 3
1 2
1 3
3 4
3 5

Sample Output 1:

0 1 0 2 1

Sơ đồ quân đội của đế chế ~X~ được thiết lập ở dạng cây. Có ~n~ sĩ quan được đánh số từ ~1~ tới ~n~, mỗi người đều có một cấp trên trực tiếp, riêng sĩ quan ~1~ - là chỉ huy tối cao - thì không.

Sĩ quan ~x~ được coi là cấp dưới (trực tiếp hoặc gián tiếp) của sĩ quan ~y~ nếu một trong hai điều kiện sau đúng:

• Sĩ quan ~y~ là cấp trên trực tiếp của sĩ quan ~x~.
• Cấp trên trực tiếp của sĩ quan ~x~ là cấp dưới của sĩ quan ~y~.

Quân đội có cách truyền lệnh rất riêng, nó được miêu tả giống thuật toán ~DFS~.

Giả sử, ta có sơ đồ quan hệ sau:

• Nếu sĩ quan ~1~ truyền lệnh, các sĩ quan sẽ nhận được lệnh theo thứ tự: ~[1,2,3,5,6,8,7,9,4]~.
• Nếu sĩ quan ~3~ truyền lệnh, các sĩ quan sẽ nhận được lệnh theo thứ tự: ~[3,5,6,8,7,9]~.
• Nếu sĩ quan ~9~ truyền lệnh, các sĩ quan sẽ nhận được lệnh theo thứ tự: ~[9]~.

Có một lưu ý quan trọng, đó là nếu sĩ quan ~u~ có ~k~ cấp dưới trực tiếp: ~v_1,v_2,...,v_k~ thì sẽ truyền lệnh cho ~v_i~ theo thứ tự từ bé đến lớn.

Bạn cần giúp chỉ huy tối cao trả lời ~q~ truy vấn, truy vấn thứ ~i~ có dạng ~(u_i,k_i)~, hỏi rằng nếu sĩ quan ~u_i~ truyền tin, sĩ quan nhận tin thứ ~k_i~ là ai.

Input

• Dòng đầu chứa hai số nguyên ~n, q~ ~(n,q \le 2 \times 10^5)~.
• Dòng sau gồm ~n-1~ số, ~p_2,p_3,...,p_n~, ~p_i~ miêu tả cấp trên trực tiếp của nhân viên thứ ~i~.
• ~q~ dòng sau, dòng thứ ~i~ gồm hai số nguyên dương ~u_i,k_i~, miêu tả truy vấn thứ ~i~.

Output

• Gồm ~q~ dòng trả lời cho ~q~ truy vấn, in ra sĩ quan thứ ~k_i~ nhận tin nếu người truyền tin là sĩ quan ~u_i~, ngược lại nếu không đủ ~k_i~ người nhận được tin thì in ra ~-1~.

Sample Input 1

9 6
1 1 1 3 5 3 5 7
3 1
1 5
3 4
7 3
1 8
1 9

Sample Output 1

3
6
8
-1
9
4

Cho một cây có gốc bao gồm ~n~ nút. Các nút được đánh số ~1,2,... ,n~ và nút ~1~ là gốc của cây. Mỗi nút có một giá trị.

Nhiệm vụ của bạn là xử lý các loại truy vấn sau:

• ~1.~ thay đổi giá trị của nút ~s~ thành ~x~
• ~2.~ tính tổng các giá trị trong cây con gốc ~s~

Input

• Dòng đầu vào đầu tiên chứa hai số nguyên ~n~ và ~q:~ số lượng nút và truy vấn. Các nút được đánh số ~1,2,... ,n.~
• Dòng tiếp theo có ~n~ số nguyên ~v_1,v_2,... ,v_n:~ giá trị của mỗi nút.
• Sau đó, có ~n-1~ dòng mô tả các cạnh. Mỗi dòng chứa hai số nguyên ~a~ và ~b:~ có một cạnh nối hai nút ~a~ và ~b~.
• Cuối cùng, có ~q~ các dòng mô tả các truy vấn. Mỗi truy vấn có dạng "~1~ ~s~ ~x~" hoặc "~2~ ~s~".

Output

• In câu trả lời cho mỗi truy vấn loại ~2~.

Constraints

• ~1 ≤ n, q ≤ 2⋅10^5~
• ~1 ≤ a, b, s ≤ n~
• ~1 ≤ v_i, x ≤ 10^9~

Example

Sample Input

5 3
4 2 5 2 1
1 2
1 3
3 4
3 5
2 3
1 5 3
2 3

Sample Output

8
10

Cho một cây có gốc bao gồm ~n~ nút. Các nút được đánh số ~1,2,... ,n~ và nút ~1~ là gốc của cây. Mỗi nút có một giá trị.

Nhiệm vụ của bạn là xử lý các loại truy vấn sau:

• ~1.~ thay đổi giá trị của nút ~s~ thành ~x~
• ~2.~ tính tổng giá trị trên đường đi từ gốc cây tới nút ~s~

Input

• Dòng đầu vào đầu tiên chứa hai số nguyên ~n~ và ~q:~ số lượng nút và truy vấn. Các nút được đánh số ~1,2,... ,n.~
• Dòng tiếp theo có ~n~ số nguyên ~v_1,v_2,... ,v_n:~ giá trị của mỗi nút.
• Sau đó, có ~n-1~ dòng mô tả các cạnh. Mỗi dòng chứa hai số nguyên ~a~ và ~b:~ có một cạnh nối hai nút ~a~ và ~b~.
• Cuối cùng, có ~q~ các dòng mô tả các truy vấn. Mỗi truy vấn có dạng "~1~ ~s~ ~x~" hoặc "~2~ ~s~".

Output

• In câu trả lời cho mỗi truy vấn loại ~2~.

Constraints

• ~1 ≤ n, q ≤ 2⋅10^5~
• ~1 ≤ a, b, s ≤ n~
• ~1 ≤ v_i, x ≤ 10^9~

Example

Sample Input

5 3
4 2 5 2 1
1 2
1 3
3 4
3 5
2 4
1 3 2
2 4

Sample Output

11
8

Cho một cây có gốc bao gồm ~n~ nút. Các nút được đánh số ~1,2,... ,n~ và nút ~1~ là gốc của cây. Nút thứ ~i~ trên cây có giá trị là ~c_i~, được biết ~(1 \le c_i \le n)~.

Bạn có ~q~ truy vấn có dạng như sau:

• ~a,b,c~: Hỏi trên đường đi từ đỉnh ~a~ tới đỉnh ~b~, liệu có tồn tại đỉnh nào có màu bằng ~c~ hay không.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n,q~ ~(1 \le n,q \le 10^5)~
• Dòng thứ hai chứa ~n~ số nguyên ~c_1,c_2,...,c_n~ miêu tả màu của các đỉnh.
• ~n-1~ dòng sau, mỗi dòng chứa hai số nguyên ~u,v~ ~(1 \le u,v \le n)~ miêu tả cạnh ~(u,v)~.
• ~q~ dòng sau, dòng thứ ~i~ chứa ba số nguyên ~a,b,c~ miêu tả truy vấn.

Output

• In ra xâu nhị phân có độ dài ~M~. Kí tự thứ ~i~ của xâu là ~1~ nếu truy vấn thứ ~i~ tồn tại đỉnh có màu là ~c~ tương ứng, ngược lại là ~0~.

Example

Sample Input

5 5
1 1 2 1 2
1 2
2 3
2 4
1 5
1 4 1
1 4 2
1 3 2
1 3 1
5 5 1

Sample Output

10110

Ở một đất nước nọ, có ~n~ thành phố được kết nối với nhau bằng ~n-1~ con đường 2 chiều, đảm bảo rằng từ một thành phố bất kì có thể tới được tất cả các thành phố khác.

Thành phố thứ ~i~ có một giá trị ~a_i~, là độ "đẹp của thành phố đó. Các giá trị a_i này có thể giống nhau, tức là các thành phố có thể có độ đẹp ngang nhau.

Một vị khách du lịch khi tới đất nước này chơi trong ~k (1 \le k \le 10^{18})~ ngày. Hiện tại, vị khách ấy đang ở thành phố 1. Cách di chuyển của vị khách này rất đặc biệt, ví dụ ở ngày thứ i và vị khách đang ở thành phố ~u~ (ở ngày đầu thì anh ta ở thành phố 1), anh sẽ đi tới thành phố ~v~ khác ~u~, sao cho ~a_v - dist(u,v)~ là lớn nhất (~dist(u,v)~ là đường đi ngắn nhất từ thành phố ~u~ tới ~v~). Nếu có nhiều thành phố thỏa mãn điều kiện trên, anh ta sẽ đi tới thành phố có chỉ số nhỏ nhất.

Là một người yêu thích tin học, vị khách đưa ra một yêu cầu trước khi tham quan, đó là hãy tính xem, sau ~k~ ngày, anh ta sẽ ở thành phố nào. Hãy lập trình và giải bài toán này giúp anh ấy.

Input

• Dòng đầu gồm 2 số ~n~ và ~k~, lần lượt là số thành phố và số ngày vị khách ở ~(1 \le n \le 3 \times 10^5, 1 \le k \le 10^{18})~.
• Dòng sau gồm ~n~ số miêu tả dãy ~a~. ~(0 \le a_i \le 10^9 \; \forall \; 1 \le i \le n).~
• ~n-1~ dòng sau, mỗi dòng gồm 2 số ~u,v (1 \le u,v \le n)~ miêu tả con đường 2 chiều nối ~u~ và ~v~.

Output

In ra thành phố mà anh ta sẽ đến sau ~k~ ngày.

Ràng buộc

• Subtask 1: ~n \le 1000, k \le 10^5~ (20%)
• Subtask 2: ~n \le 1000, k \le 10^{18}~ (15%)
• Subtask 3: ~n \le 300000, k \le 10^5~ (50%)
• Subtask 4: ~n \le 300000, k \le 10^{18}~ (15%)

Sample Test

Input:

5 4
1 1 3 2 4
1 2
1 3
2 4
2 5

Output:

5

Giải thích:

• Vị khách sẽ đi theo thứ tự 1 --> 3 --> 5 --> 2 --> 5

Marisa sống trong khu rừng ma thuật. Một trong những việc cô thường làm là hái nấm.

Khu rừng có thể được biểu diễn bằng một cây có ~n~ nút, ở nút thứ ~i~ là loại nấm có màu ~c_i~. Do đây là khu rừng ma thuật nên các cây nấm có khả năng đổi màu.

Cho ~q~ ngày, mỗi ngày một trong hai sự kiện sau sẽ diễn ra:

• Cây nấm ở nút ~i~ đổi màu thành ~c~.
• Marisa đi hái nấm những cây nấm màu ~c~ từ nút ~u~ đến nút ~v~ theo đường đi ngắn nhất.

Với mỗi ngày Marisa đi hái nấm, hãy cho cô biết sẽ hái được bao nhiêu nấm nhé!

Input:

• Dòng đầu tiên là 2 số nguyên dương ~n, q~.
• Dòng tiếp theo gồm ~n~ số nguyên dương ~c_i \le n~ là màu của cây nấm ở đỉnh ~i~.
• ~n - 1~ dòng tiếp theo mỗi dòng là 2 số nguyên dương ~u, v \le n~ thể hiện có đường đi trực tiếp giữa nút ~u~ và ~v~.
• ~q~ dòng tiếp theo là một trong 2 loại:
  • 1 i c, đổi màu cây nấm ở nút ~i~ thành ~c~.
  • 2 u v c, Marisa hái nấm những cây nấm màu ~c~ từ nút ~u~ đến nút ~v~ theo đường đi ngắn nhất.

Output:

• Với mỗi ngày Marisa đi hái nấm, hãy in ra số lượng cây nấm cô hái được, cây nấm cô hái ngày hôm sau sẽ tự mọc lại và cùng màu với cây nấm cũ.

Sample Test:

Input:

5 3
1 4 2 2 3
1 2
1 3
3 4
3 5
2 2 4 2
1 5 1
2 1 5 1

Output:

2
2

Giới hạn:

• Subtask 1 (40% số điểm): ~n, q \le 1000~.
• Subtask 2 (30% số điểm): ~n, q \le 10^5~.
• Subtask 3 (30% số điểm): ~n, q \le 5 \times 10^5~.