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

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

Cho một cây có trọng số gồm ~n~ đỉnh, được đánh số từ ~1~ đến ~n~, trọng số của đỉnh thứ ~i~ là ~a_i~. Gọi ~S(i)~ là dãy các trọng số của các đỉnh trên đường đi từ ~1~ tới ~i~.

Với mỗi ~i~, hãy tìm độ dài dãy con tăng dài nhất của ~S(i)~.

Input

• Dòng đầu chứa số nguyên ~n~ ~(n \le 2 \times 10^5)~.
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_1,a_2,...,a_n~ miêu tả trọng số của các đỉnh ~(1 \le a_i \le 10^9)~.
• ~n-1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u, v~ ~(1≤u,v≤n; u≠v)~ mô tả một cạnh của cây nối hai đỉnh ~u~ và ~v~.

Output

• In ra ~n~ số nguyên là độ dài của dãy con tăng dài nhất của ~S(i)~.

Subtask

• Subtask ~1~: ~a_i \le 100~. ~(30\%)~
• Subtask ~2~: Không có đỉnh nào có quá hai cạnh nối. ~(30\%)~
• Subtask ~3~: Không có ràng buộc gì thêm. ~(40\%)~

Sample Input 1

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

Sample Output 1

1
2
3
3
4
4
5
2
2
3

Ở 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

Tại nước Cộng hòa VOI, có ~N~ thành phố được đánh số từ ~1~ đến ~N~. Các thành phố được kết nối với ~N - 1~ đường hai chiều. Người dân ở Cộng hòa VOI đang đi lại giữa các thành phố bằng những con đường này. Họ có thể đi lại giữa hai thành phố bất kỳ bằng cách đi qua một hoặc một số con đường.

Ông Chau là ứng cử viên tổng thống của Cộng hòa VOI. Tất nhiên, để trở thành tổng thống, ông ta phải thực hiện chiến dịch tranh cử tổng thống. Thư ký của ông đã lên kế hoạch cho ~M~ chiến dịch tranh cử. Trong kế hoạch thứ ~i~, ông Chau sẽ đi từ thành phố ~A_i~ đến thành phố ~B_i~, sử dụng số con đường tối thiểu và phát biểu trước công chúng tại mỗi thành phố trên đường đi (bao gồm thành phố ~A_i~ và thành phố ~B_i~). Bởi vì thư ký của ông ấy rất giỏi, nên anh ta biết rằng ông Chau sẽ nhận được phiếu ~C_i~ nếu kế hoạch thứ ~i~ được thực hiện. Có thể thực hiện nhiều kế hoạch.

Tuy nhiên, những người ở Cộng hòa VOI rất thiếu kiên nhẫn. Nếu ông Chau phát biểu trước công chúng nhiều lần trong cùng một thành phố, ông sẽ mất sự ủng hộ từ người dân trong Cộng hòa VOI.

Bởi vì ông Chau muốn trở thành tổng thống, ông ấy muốn nhận được càng nhiều phiếu bầu càng tốt. Vì bạn là siêu lập trình viên ở Cộng hòa VOI, ông ấy đã yêu cầu bạn viết một chương trình tính toán số phiếu bầu tối đa mà ông Chau có thể nhận được trong cuộc bầu cử tổng thống với giả định rằng ông ấy sẽ không phát biểu trước công chúng nhiều lần trong cùng một thành phố.

Với ~N~ là số thành phố ở Cộng hòa VOI, thông tin về các con đường, ~M~ là số kế hoạch cho chiến dịch bầu cử và thông tin của từng kế hoạch, hãy viết một chương trình tính toán số phiếu bầu tối đa mà ông Chau có thể nhận được cuộc bầu cử tổng thống.

Input:

• Dòng đầu tiên chứa số nguyên ~N~ ~(2 \leq n \leq 10^5)~ là số thành phố tại nước cộng hoà VOI

• ~N - 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u, v~ ~(1 \leq u, v \leq N, u \neq v)~ thể hiện con đường nối giữa thành phố ~u~ và thành phố ~v~.

• Dòng tiếp theo chứa số nguyên ~M~ ~(1 \leq M \leq 10^5)~ là số kế hoạch tranh cử

• ~M~ dòng tiêp theo, dòng thứ ~i~ chứa ba số nguyên ~A_i, B_i, C_i~ ~(1 \leq A_i, B_i \leq N, A_i \neq B_i, 1 \leq C_i \leq 10^4)~ thể hiện kế hoạch thứ ~i~

Output:

• Gồm một dòng duy nhất là số phiếu tối đa ông Chau có thể nhận được

Scoring:

Bộ test của bài được chia làm các subtask như sau:

• Subtask 1 (10 điểm): ~M \leq 15~
• Subtask 2 (5 điểm): ~X_i = i,Y_i = i + 1, C_i = 1~
• Subtask 3 (5 điểm): ~X_i = i,Y_i = i + 1~
• Subtask 4 (30 điểm): ~C_i = 1~
• Subtask 5 (10 điểm): ~N \leq 1000, M \leq 1000~
• Subtask 6 (40 điểm): Không có ràng buộc gì thêm.

Điểm tối đa của bài là ~100~ điểm.

Example

Sample Input 1

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

Sample Output 1

8

Sample Explanation 1

    - Trong ví dụ ở trên, ông Chau thực hiện kế hoạch ~1~ và ~2~, do vậy số phiếu bầu nhận được là ~3 + 5 = 8~, đây là đáp án tối ưu.

Cho một cây gồm ~n~ đỉnh với các trọng số trên cạnh.

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

• Nhân thử các cạnh nối với đỉnh ~u_i~ lên ~x_i~ lần, hỏi đường kính của cây mới có độ dài là bao nhiêu.
• Lưu ý là ta chỉ nhân thử, sau truy vấn này thì cây về nguyên bản.

Input

• Dòng đầu gồm số nguyên dương ~n~.
• ~n-1~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~u~, ~v~ và ~w~ miêu tả cạnh ~(u,v)~ có độ dài ~w~ của cây.
• Dòng tiếp theo gồm số nguyên dương ~q~.
• ~q~ dòng sau, mỗi dòng gồm hai số nguyên dương ~u_i,y_i~ miêu tả truy vấn.

Output

• Với mỗi truy vấn, in ra độ dài đường kính của cây mới trong giả định.

Constraints

• ~1 \le n \le 10^5~.
• ~1 \le q \le 10^5~

Subtask

• ~30\%~ số điểm thỏa mãn ~n \le 2000~.
• ~30\%~ số điểm thỏa mãn cây là đường thẳng.
• ~40\%~ số điểm thỏa mãn ~n \le 10^5~

Sample Input 1

8
2 5 3
1 4 2
5 1 2
3 4 1
4 7 2
6 1 6
4 8 2
3
3 2
4 3
1 3

Sample Output 1

11
18
27

Newton đang nghiên cứu về những bí mật của thiên nhiên thì bất ngờ ông nằm ngủ quên dưới một gốc táo lớn. Trong giấc mơ, ông bước vào một thế giới kỳ diệu được bao phủ bởi những cây táo đỏ lấp lánh. Một sinh vật kỳ lạ xuất hiện và nói với Newton rằng: "Nếu ông có thể tìm ra cặp táo phù hợp nhất trên cây táo tri thức này, ông sẽ khám phá ra bí mật của vạn vật."

Cây táo tri thức được biểu diễn dưới dạng một đồ thị dạng cây với mỗi đỉnh đại diện cho một quả táo. Cây gồm ~n~ đỉnh được đánh số từ ~1, 2, 3, ..., n~ và ~n - 1~ cạnh. Mỗi quả táo đều mang trong mình một chỉ số hạnh phúc, tương ứng là ~a_1, a_2, ..., a_n~ lần lượt từ đỉnh ~1~ đến ~n~.

Newton được biết rằng một số ~x~ được gọi là số siêu hạnh phúc bậc ~k~ nếu căn bậc ~k~ của ~x~ là một số tự nhiên. Nói cách khác, ~x~ có thể được viết dưới dạng ~y^k~ với ~y~ là một số tự nhiên.

Ví dụ:

• ~k = 2~ thì các số siêu hạnh phúc có thể là ~4~ (vì ~2^2 = 4~), ~81~ (vì ~9^2 = 81~).
• ~k = 3~ thì các số siêu hạnh phúc có thể là ~8~ (vì ~2^3 = 8~), ~8000~ (vì ~20^3 = 8000~).

Một cặp quả táo được gọi là phù hợp với nhau nếu tích của chỉ số hạnh phúc của hai quả táo đó là một số siêu hạnh phúc bậc ~k~.

Newton chỉ có thể quan sát các quả táo trên một đường đi đơn bất kỳ giữa hai đỉnh ~u~ và ~v~ trên cây. Ông đặt ra ~q~ câu hỏi như sau:

Với mỗi đường đi từ ~u~ đến ~v~, hãy cho biết có bao nhiêu cặp quả táo ~(a, b)~ sao cho:

• Cả ~a~ và ~b~ đều thuộc đường đi đó,
• ~a < b~,
• Và tích của chỉ số hạnh phúc của hai quả là một số siêu hạnh phúc bậc ~k~.

Newton rất cần bạn giúp ông trả lời các câu hỏi này để ông có thể hoàn thiện lý thuyết mà sau này có tên gọi "vạn vật hấp dẫn".

Input

• Dòng đầu chứa ba số nguyên: ~n, k, q~ (~1 \le n, q \le 10^5~, ~1 \le k \le 5~).
• Dòng tiếp theo là dãy số nguyên dương ~a_1, a_2, ..., a_n~ (~1 \le a_i \le 10^6~).
• ~n - 1~ dòng tiếp theo lần lượt là các cạnh của đồ thị (đảm bảo đồ thị đã cho là đồ thị dạng cây).
• Tiếp theo là ~q~ dòng chứa các câu hỏi của Newton, mỗi câu hỏi có dạng ~(u, v)~ với ~1 \le u, v \le n~.

Output

• Ghi ra ~q~ dòng, mỗi dòng chứa kết quả của truy vấn tương ứng.

Scoring

Sample Input 1

6 3 4
1 15 30 7 49 10
1 4
4 2
4 3
4 5
6 5
4 5
1 6
2 4
1 1

Sample Output 1

1
1
0
0

Explanation 1

Ở thắc mắc đầu tiên, các đỉnh thuộc đường đi từ ~4~ đến ~5~ là ~4, 5~ và chỉ số hạnh phúc tương ứng là ~7~ và ~49~, nên chỉ có ~1~ cặp duy nhất là ~(4, 5)~ và cặp này hợp nhau vì ~7 \times 49 = 343~ ~(343 = 7^3)~.