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