Một công ty có ~n~ nhân viên, tạo thành một hệ thống phân cấp dạng cây trong đó mỗi nhân viên, ngoại trừ tổng giám đốc đều có một sếp cao hơn trực tiếp.

Nhiệm vụ của bạn là xử lý ~q~ truy vấn dưới dạng: ai là người sếp cao hơn nhân viên ~x~ đúng ~k~ bậc trong hệ thống phân cấp?

Input

• Dòng đầu vào đầu tiên có hai số nguyên ~n~ và ~q:~ số lượng nhân viên và truy vấn. Các nhân viên được đánh số ~1,2,... ,n~ và người số ~1~ là tổng giám đốc.
• Dòng tiếp theo có ~n-1~ số nguyên ~e_{2},e_{3},... ,e_{n}:~ người chủ mỗi nhân viên ~2,3,\ldots ,n~.
• Cuối cùng, có ~q~ dòng mô tả các truy vấn. Mỗi dòng có hai số nguyên ~x~ và ~k~ ứng với câu hỏi: "Ai là người sếp cao hơn nhân viên ~x~ ~k~ bậc?"

Output

• In câu trả lời cho mỗi truy vấn. Nếu không tồn tại một ông chủ như vậy , hãy in -1.

Constraints

• ~1 \leq n,q \leq 2 \cdot 10^5~
• ~1 \leq e_{i} \leq i - 1~
• ~1 \leq x \leq n~
• ~1 \leq k \leq n~

Sample Input

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

Sample Output

3
1
-1

Một công ty có ~n~ nhân viên, tạo thành một hệ thống phân cấp dạng cây trong đó mỗi nhân viên, ngoại trừ tổng giám đốc đều có một sếp cao hơn trực tiếp.

Nhiệm vụ của bạn là xử lý ~q~ truy vấn có dạng: ai là người sếp chung có bậc thấp nhất của nhân viên ~a~ và ~b~ trong hệ thống phân cấp?

Input

• Dòng đầu vào đầu tiên có hai số nguyên ~n~ và ~q:~ số lượng nhân viên và truy vấn. Các nhân viên được đánh số ~1,2,... ,n~ và người số ~1~ là tổng giám đốc.
• Dòng tiếp theo có ~n-1~ số nguyên ~e_2,e_3,\dots,e_n:~ người chủ mỗi nhân viên ~2,3,...,n~.
• Cuối cùng, có ~q~ dòng mô tả các truy vấn. Mỗi dòng có hai số nguyên ~a~ và ~b~ ứng với câu hỏi: "Ai là chủ chung thấp nhất của nhân viên ~a~ và ~b~?"

Output

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

Constraints

• ~1 \leq n,q \leq 2 \cdot 10^5~
• ~1 \leq e_{i} \leq i - 1~
• ~1 \leq a,b \leq n~

Sample Input

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

Sample Output

3
1
1

Bạn được cho ~1~ cái cây gồm ~n~ đỉnh, với đỉnh ~1~ là nút gốc, và giá trị tương ứng của từng đỉnh.

Nhiệm vụ của bạn là cần phải thực hiện ~q~ truy vấn có dạng như sau:

• ~1~. Đổi giá trị của nút ~s~ thành ~x~.

• ~2~. Tính tổng giá trị của các nút nằm trong cây con gốc ~s~.

Input

• Dòng đầu gồm ~2~ số ~n~ và ~q~ (~1 \leq n, q \leq 2 \times 10^5~) tương ứng là số lượng nút trong cây và truy vấn.

• Dòng tiếp theo là dãy ~n~ số ~a_1, a_2, a_3, \cdots, a_n~ (~1 \leq a_i \leq 10^9~) là giá trị ban đầu của nút tương ứng trên cây.

• Tiếp theo là ~n - 1~ cặp số ~a~, ~b~ (~1 \leq a, b \leq n~) cho ta biết cạnh giữa ~2~ nút ~a - b~ trên cây.

• Trong ~q~ dòng cuối cùng là các truy vấn có ~1~ trong ~2~ dạng:

  — ~1~ ~s~ ~x~ (~1 \leq s \leq n~, ~1 \leq x \leq 10^9~).

  — ~2~ ~s~ (~1 \leq s \leq n~).

Output

Xuất ra từng dòng tương ứng đáp án của từng truy vấn loại ~2~.

Scoring

Sample Input 1

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

Sample Output 1

8
10

Sample Input 2

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

Sample Output 2

30
50
47
8
12
3
9

Notes

Trong test ví dụ đầu tiên, hình ảnh của cây ban đầu:

Truy vấn "~2~ ~3~" sẽ lấy tổng phần khoanh vùng:

cho ra đáp án là: ~8~.

Sau truy vấn "~1~ ~5~ ~3~", đổi giá trị ở nút ~5~ thành ~3~:

Cuối cùng, truy vấn "~2~ ~3~" sẽ lấy tổng phần khoanh vùng:

cho ra đáp án là: ~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~ ~(1 \le n, q \le 2 \cdot 10^5)~ là số lượng nút và truy vấn. Các nút được đánh số ~1, 2, ..., n~.

• Dòng tiếp theo chứa ~n~ số nguyên ~v_1, v_2, ..., v_n~ ~(1 \le v_i \le 10^9)~ lần lượt là 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~ ~(1 \le a, b \le n)~ : có một cạnh nối giữa hai nút ~a~ và ~b~.

• Cuối cùng, có ~q~ dòng mô tả các truy vấn. Mỗi truy vấn có dạng "1 ~s~ ~x~" hoặc "2 ~s~" ~(1 \le s \le n, 1 \le x \le 10^9~).

Output

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

Scoring

Sample Input 1

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

Sample Output 1

11
8

Cho một cây vô hướng gồm ~n~ đỉnh.

Hãy tìm đường đi dài nhất ở trên cây, biết rằng độ dài đường đi từ ~u~ tới ~v~ chính bằng số cạnh trên đường đi đơn từ ~u~ tới ~v~.

Input

• Dòng đầu chứa hai số nguyên ~n~ ~(1 \le n \le 10^5)~.
• ~n-1~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~u~, ~v~ miêu tả cạnh của cây.

Output

• Đưa ra khoảng cách xa nhất của hai đỉnh bất kì trên cây.

Sample Input 1

5
1 2
1 3
3 4
3 5

Sample Output 1

3

Ivan Tèo rất thích thịt vịt, một hôm cậu tới thăm đất nước DuckLand, gồm ~n~ thành phố được nối với nhau bằng ~n-1~ con đường hai chiều, đảm bảo rằng ~n~ thành phố thông thương với nhau. Con đường thứ ~i~ nối hai thành phố ~u_i,v_i~ với nhau và gồm ~c_i~ con vịt.

Giả sử Tèo xuất phát từ thành phố ~s~, cậu sẽ đi tới một thành phố khác sao cho không con đường nào được đi qua nhiều hơn ~1~ lần, và mua hết các con vịt trên đường đi đó.

Tèo muốn biết nếu cậu xuất phát từ thành phố ~s~ với ~s~ lần lượt tương ứng ~1,2,3,...,n~, cậu sẽ mua được tối đa bao nhiêu con vịt nếu đi tối ưu?

Input

• Dòng đầu là số nguyên ~n~ ~(1 \le n \le 10^5)~
• ~n-1~ dòng tiếp theo, dòng thứ ~i~ chứa ~3~ số nguyên dương ~u_i,v_i,c_i~ xác định một con đường hai chiều giữa thành phố ~u_i,v_i~ với độ dài ~c_i~. ~(u_i,v_i \le n, c_i \le 10^4)~

Subtask

• Subtask ~1~ ~(50\%)~ : ~K \le N \le 10^3~
• Subtask ~2~ ~(50\%)~ : Không ràng buộc gì thêm.

Output

• Gồm ~n~ số nguyên dương trên một dòng, số thứ ~i~ là số con vịt tối đa Tèo có thể mua nếu đi từ thành phố ~s = i~.

Sample Input 1

4
1 2 4
2 3 5
3 4 7

Sample Output 1

16 12 9 16

Cho một cây vô hướng gồm ~n~ đỉnh ~(1 \le n \le 1e5)~ và ~m~ đỉnh đặc biệt ~(1 \le m \le n)~, kèm một số ~k~ nguyên dương bất kì ~(1 \le k \le n)~. Một đỉnh ~u~ được gọi là tốt nếu như với mọi đỉnh ~v~ thuộc tập ~m~ đỉnh đặc biệt, ta luôn có ~dist(u,v) \le k~. Ở đây, ~dist(u,v)~ là khoảng cách của đỉnh ~u~ và ~v~ trên cây, hay bằng số cạnh trên đường đi ngắn nhất từ đỉnh ~u~ tới đỉnh ~v~. Hãy đếm xem có bao nhiêu đỉnh được coi là "tốt".

Input:

• Dòng đầu gồm 3 số ~n,m,k. (1 \le m \le n \le 10^5, 1 \le k \le 10^5).~
• ~n-1~ dòng sau mỗi dòng gồm 2 số ~u,v (1 \le u,v \le n)~ là cạnh nối từ đỉnh ~u~ tới ~v~.
• Dòng cuối gồm ~m~ số miêu tả các đỉnh đặc biệt.

Output:

• Số đỉnh tốt.

Sample Test

Input:

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

Output:

3

Giải thích:

• 3 đỉnh tốt là đỉnh 3,4,5.

Ràng buộc

• Subtask 1: ~n <= 500.~ (50%)
• Subtask 2: Với mỗi thành phố, chỉ có tối đa 2 con đường nối tới các thành phố khác.
• Subtask 3: Không giới hạn gì thêm. (20%).

Cho một cây vô hướng gồm ~n~ đỉnh. Đỉnh thứ ~i~ ~(1 \le i \le n)~ có trọng số là ~a_i~, cạnh thứ ~i~ ~(1 \le i \le n-1)~ có trọng số là ~w_i~.

Định nghĩa hàm ~dist(u,v)~ là tổng trọng số của các cạnh trên đường đi đơn từ đỉnh ~u~ tới đỉnh ~v~.

Hãy tìm ~max(dist(u,v) \times gcd(a_u,a_v)) \forall u,v \in [1,n]~.

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~ là ~a_i~ miêu tả trọng số của đỉnh thứ ~i~.
• ~n-1~ dòng tiếp theo, dòng thứ ~i~ gồm ba số nguyên dương ~u_i,v_i,w_i~ miêu tả cạnh thứ ~i~ của cây.

Constraint

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

Subtask

• Subtask ~1~ ~(30\%)~: ~n \le 2000~.
• Subtask ~2~ ~(20\%)~: ~a_i = 1; \forall i \in [1,n]~
• Subtask ~3~ ~(30\%)~: ~n,a_i \le 4 \times 10^4~
• Subtask ~4~ ~(20\%)~: Không có ràng buộc gì thêm.

Output

• In ra kết quả của bài toán.

Sample Input 1:

2
10 10
1 2 10

Sample Output 1:

100

Be careful ... with recursion!

Đất nước HNAms gồm ~n~ thành phố được đánh số từ ~1~ tới ~n~. Đất nước HNAms rất thích bóng đá, ở thành phố thứ ~i~ có số sân vận động là ~a_i~. Do một vài chính sách đặc biệt của Bộ Thể Thao mà số sân vận động của các thành phố là không quá ~m~. Các thành phố của HNAms cũng có ~n-1~ con đường hai chiều để kết nối các thành phố lại. Con đường thứ ~i~ sẽ nối hai thành phố ~u_i~ và ~v_i~, đảm bảo rằng mọi cặp thành phố đều có lộ trình di chuyển tới nhau. Nói cách khác, như bao đất nước trong thế giới OI, HNAms có thể ví như một đồ thị dạng cây.

Bộ Xây Dựng đã tạo ra một phương pháp để đánh giá độ hiệu quả trong giao thông của một tổ hợp các thành phố:

• Giả sử ta có một tập thành phố ~u_1,u_2,...,u_k~, độ hiệu quả trong giao thông của tập hợp thành phố này chính bằng đường đi ngắn nhất nếu có thể xuất phát tại một thành phố tùy ý và đi qua hết các thành phố trong tập. Đường đi ở HNAms được tính theo số con đường mà lộ trình này đi qua.

Để hiểu rõ hơn về cách tính độ hiệu quả, hãy nhìn vào hình vẽ trên:

• Giả sử tập thành phố là ~[3,4,5]~, độ hiệu quả của tổ hợp này là ~5~, bởi ta sẽ đi theo lộ trình: ~3 \rightarrow 2 \rightarrow 1 \rightarrow 4 \rightarrow 1 \rightarrow 5~. Dễ thấy không có lộ trình nào có thể ngắn hơn.
• Giả sử tập thành phố là ~[2,5]~, độ hiệu quả của tổ hợp này là ~2~ với lộ trình: ~2 \rightarrow 1 \rightarrow 5~.
• Đối với tập thành phố rỗng hoặc có số thành phố bằng ~1~, độ hiệu quả được đánh giá là bằng ~0~.

Vì là một người đam mê bóng đá, chủ tịch HuySalad quyết định ăn mừng ~120~ năm sinh nhật của FIFA bằng việc tổ chức một mùa giải bóng đá bất tận, trải dài từ ngày ~1~ tới ngày ~m~ (hãy cố chấp nhận rằng thực sự có nhiều ngày như vậy). Vào ngày thứ ~x~ ~(1 \le x \le m)~, các trận đấu bóng đá sẽ được tổ chức tại các thành phố có số sân vận động chia hết cho ~x~.

Như vậy, lưu lượng khách di chuyển sẽ là rất lớn, Chính Phủ giao cho bạn - Bộ Công Nghệ - đối với mỗi ngày, hãy đánh giá độ hiệu quả của tổ hợp thành phố được tổ chức bóng đá. Nói cách khác, đối với mỗi ngày thứ ~x~ ~(1 \le x \le m)~, bạn sẽ phải đánh giá độ hiệu quả của tập thành phố ~[u_1,u_2,...,u_k]~ thỏa mãn ~x \mid a[u_i] ~ ~(\forall 1 \le i \le k)~.

Input:

• Dòng thứ nhất chứa hai số nguyên dương ~n,m~ ~(1 \le n \le 2 \times 10^5, 1 \le m \le 10^5)~
• Dòng thứ hai chứa ~n~ số nguyên dương, số thứ ~i~ là ~a_i~, miêu tả số sân vận động ở thành phố ~i~ ~(1 \le a_i \le m)~.
• ~n-1~ dòng tiếp theo, dòng thứ ~i~ gồm hai số nguyên dương ~u_i~ và ~v_i~ miêu tả con đường hai chiều nối từ thành phố ~u_i~ tới thành phố ~v_i~.

Output:

• In ra ~m~ dòng, dòng thứ ~i~ là độ hiệu quả của tổ hợp thành phố được sử dụng trong ngày thứ ~i~.

Subtask:

• Subtask ~1~ (~15\%~ số điểm): Tất cả các con đường thứ ~i~ trong khoảng ~[1,n-1]~ có dạng ~u_i = i, v_i = i+1~.
• Subtask ~2~ (~10\%~ số điểm): ~n \le 10, m = 1~.
• Subtask ~3~ (~15\%~ số điểm): ~m = 1~
• Subtask ~4~ (~10\%~ số điểm): ~m = 2~
• Subtask ~5~ (~30\%~ số điểm): ~n \le 5 \times 10^4, m \le 10^4~
• Subtask ~6~ (~20\%~ số điểm): Không có giới hạn gì thêm.

Sample Input 1

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

Sample Output 1

5

Explanation 1

Do ~m=1~ nên chỉ có ngày đầu tiên được tổ chức bóng đá, do tất cả các thành phố đều có số sân vận động chia hết cho ~1~, nên ta có tập ~[1,2,3,4,5]~.

Độ hiệu quả của tập này là ~5~, với lộ trình ~5 \rightarrow 3 \rightarrow 2 \rightarrow 3 \rightarrow 1 \rightarrow 4~

Sample Input 2

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

Sample Output 2

7
4
2
0
0

Explanation 2

Ta có các tập thành phố sau:

• Ngày ~1~: ~[1,2,3,4,5,6]~.
• Ngày ~2~: ~[1,2,4]~
• Ngày ~3~: ~[3,5]~
• Ngày ~4~: ~[4]~
• Ngày ~5~: ~[]~
• Do ngày ~4~ chỉ có một và ngày ~5~ không có thành phố nào trong tập, độ hiệu quả của chúng đều bằng ~0~.