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

Bạn đang chơi một trò chơi bao gồm ~n~ hành tinh. Mỗi hành tinh có một cổng dịch chuyển đến một hành tinh khác (hoặc chính hành tinh đó).

Nhiệm vụ của bạn là xử lý ~q~ truy vấn có dạng: khi bạn bắt đầu trên hành tinh ~x~ và di chuyển qua ~k~ cổng dịch chuyển, bạn sẽ đến hành tinh nào?

Input

• Dòng đầu vào đầu tiên có hai số nguyên ~n~ và ~q~: số lượng hành tinh và truy vấn. Các hành tinh được đánh số ~1,2,\ldots,n~.
• Dòng thứ hai có ~n~ số nguyên ~t_1,t_2,\ldots,t_n~: với mỗi hành tinh, điểm đến của của cổng dịch chuyển. Có thể là ~t_i=i~.
• 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~: bạn bắt đầu trên hành tinh ~x~ và di chuyển qua ~k~ cổng dịch chuyển.

Output

• In đáp án cho mỗi truy vấn.

Constraints

• ~1 \leq n, q \leq 2 \cdot 10^5~
• ~1 \leq t_i \leq n~
• ~1 \leq x \leq n~
• ~0 \leq k \leq 10^9~

Sample Input

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

Sample Output

1
2
4

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

Mạng lưới giao thông ở 1 nước bao gồm ~N~ thành phố (đánh số từ ~1~ đến ~N~) và ~N - 1~ đường nối các thành phố với nhau. Có một đường đi duy nhất giữa mỗi cặp thành phố. Mỗi con đường có một độ dài xác định.

Viết chương trình, với mỗi ~K~ cặp thành phố cho trước, tìm độ dài của con đường ngắn nhất và dài nhất trên đường đi giữa 2 thành phố này.

Input

• Dòng đầu tiên chứa số nguyên ~N~, ~2 \le N \le 100000~.
• Mỗi dòng trong ~N - 1~ dòng tiếp theo chứa 3 số nguyên ~A~, ~B~, ~C~ cho biết có một con đường độ dài ~C~ giữa thành phố ~A~ và thành phố ~B~. Độ dài của mỗi con đường là số nguyên không vượt quá ~100000~.
• Dòng tiếp theo chứa số nguyên ~K~, ~1 \le K \le 100000~.
• Mỗi dòng trong ~K~ dòng tiếp theo chứa 2 số nguyên ~D~ và ~E~ – chỉ số của 2 thành phố cần truy vấn (~D \ne E~).

Output

• Mỗi dòng trong ~K~ dòng chứa 2 số nguyên – độ dài của con đường ngắn nhất và dài nhất trên đường đi giữa 2 thành phố tương ứng.

Sample Input

5
2 3 100
3 4 200
1 5 150
1 3 50
3
2 4
5 3
1 2

Sample Output

100 200
50 150
50 100

Ghi chú

Vì có đúng ~N - 1~ con đường, nên đồ thị là một cây. Mỗi truy vấn yêu cầu tìm đường đi giữa hai đỉnh và xác định đoạn đường ngắn nhất và dài nhất trên đường đi đó (tức là đoạn có trọng số nhỏ nhất và lớn nhất trong chuỗi các cạnh nối hai đỉnh đó).

Cho một cây ~n~ nút và ta định nghĩa nút ~1~ là gốc của cây.

Bây giờ ta có ~q~ truy vấn, mỗi truy vấn có dạng: ~l_i,r_i~ ~(1 \le l_i \le r_i \le n)~.

Yêu cầu: Ứng với mỗi truy vấn, ta in ra LCA của tất cả các nút từ ~l_i~ đến ~r_i~.

Input

• Dòng đầu vào đầu tiên chứa số nguyên ~n~ - thể hiện số nút của cây.

• ~n-1~ dòng tiếp theo: mỗi dòng gồm ~2~ số nguyên ~x,y~ - thể hiện cạnh nối giữa hai đỉnh ~x~ và ~y~.

• Dòng tiếp theo, chứa số ~q~ thể hiện số lượng truy vấn.

• ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~l_i,r_i~ ~(1 \le l_i \le r_i\le n)~.

Constraints

• ~1 \le n \le 3*10^5~.

Subtask

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

Output

• Ứng với mỗi truy vấn, in ra đáp án cần tìm.

Sample Input 1:

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

Sample Output 1:

4
1

Cho một cây có ~n~ đỉnh và ~q~ truy vấn có dạng ~r, u, v~.

Yêu cầu: Với mỗi truy vấn, in ra LCA của ~u~ và ~v~ nếu ~r~ là gốc của cây.

Input

• Dòng đầu vào đầu tiên chứa số nguyên ~n~ (~1 \le n \le 2 \times 10^5~).

• ~n-1~ dòng tiếp theo: mỗi dòng gồm ~2~ số nguyên ~u,v~ - thể hiện cạnh nối giữa hai đỉnh ~u~ và ~v~.

• Dòng tiếp theo, chứa số ~q~ thể hiện số lượng truy vấn (~1 \le q \le 2 \times 10^5~).

• ~q~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~r, u, v~ ~(1 \le r, u, v \le n)~.

Sample Input:

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

Sample Output:

1
2

Tèo là một cậu bé rất thích vẽ và tô màu. Cậu có một dải băng giấy dài vô tận được đánh số từ 0 trở đi. Tèo có ~n~ chiếc bút màu, mỗi chiếc có một đặc tính riêng. Chiếc bút thứ ~i~ chỉ có thể tô được một đoạn liền mạch trên dải băng giấy, từ vị trí ~l~ đến vị trí ~r~.

Một ngày nọ, cô giáo giao cho Tèo ~m~ bài tập về nhà. Mỗi bài tập yêu cầu Tèo phải tô màu hoàn toàn một đoạn nhất định trên dải băng, từ vị trí ~x~ đến ~y~. Để hoàn thành một bài tập, Tèo phải chọn ra một vài chiếc bút trong bộ sưu tập của mình và dùng chúng tô màu. Sau khi tô xong, toàn bộ đoạn ~[x, y]~ phải được phủ kín màu, không chừa một kẽ hở nào (kể cả những điểm không phải số nguyên). Chú ý là Tèo có thể tô ra ngoài đoạn ~[x, y]~ cũng được, miễn là toàn bộ đoạn ~[x, y]~ phải được tô màu.

Vì muốn tiết kiệm mực, với mỗi bài tập, Tèo muốn biết số lượng bút ít nhất cậu cần dùng là bao nhiêu. Nếu một bài tập nào đó không thể hoàn thành (không có cách nào tô kín được đoạn ~[x, y]~ bằng những chiếc bút Tèo có), cậu sẽ báo cáo lại với cô giáo là "không thể làm được".

Bạn hãy giúp Tèo tìm ra câu trả lời cho từng bài tập nhé!

Input

Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ ~(1 \leq n, m \leq 2 \cdot 10^5)~ — lần lượt là số lượng bút màu Tèo có và số lượng bài tập.

~n~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~l_i~ và ~r_i~ ~(0 \leq l_i \lt r_i \leq 5 \cdot 10^5)~ — mô tả đoạn mà chiếc bút thứ ~i~ có thể tô.

~m~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~x_i~ và ~y_i~ ~(0 \leq x_i \lt y_i \leq 5 \cdot 10^5)~ — mô tả đoạn cần tô trong bài tập thứ ~i~.

Output

In ra ~m~ số nguyên, mỗi số trên một dòng. Số thứ ~i~ là câu trả lời cho bài tập thứ ~i~:

• Là số lượng bút ít nhất cần dùng để tô kín đoạn ~[x_i, y_i]~.
• Là ~-1~ nếu Tèo không thể hoàn thành bài tập đó.

Ví dụ

Sample Input 1

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

Sample Output 1

1
2
1

Sample Input 2

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

Sample Output 2

1
1
-1
-1

Giải thích ví dụ

Ví dụ đầu tiên: Tèo có 2 cây bút: một cây tô được đoạn ~[1, 3]~ và một cây tô được ~[2, 4]~.

1. Bài tập ~[1, 3]~: Tèo chỉ cần dùng 1 cây bút (cây ~[1, 3]~) là đủ.
2. Bài tập ~[1, 4]~: Tèo cần dùng cả 2 cây bút. Cây ~[1, 3]~ tô phần đầu, và cây ~[2, 4]~ tô phần cuối. Dùng một cây không thể tô hết được.
3. Bài tập ~[3, 4]~: Tèo chỉ cần dùng 1 cây bút (cây ~[2, 4]~). Việc cây bút này tô lem ra ngoài đoạn ~[3, 4]~ (tô cả từ 2 đến 3) không ảnh hưởng đến kết quả.

Ví dụ thứ hai: Tèo có 3 cây bút: hai cây tô được ~[1, 3]~ và một cây tô được ~[4, 5]~.

1. Bài tập ~[1, 2]~: Tèo chỉ cần dùng 1 cây bút ~[1, 3]~ là đủ.
2. Bài tập ~[1, 3]~: Tèo chỉ cần dùng 1 cây bút ~[1, 3]~.
3. Bài tập ~[1, 4]~: Tèo không thể hoàn thành. Cây bút ~[1, 3]~ chỉ tô đến 3, còn khoảng trống từ 3 đến 4 không có bút nào tô được.
4. Bài tập ~[1, 5]~: Tèo cũng không thể hoàn thành. Dù cậu dùng cả bút ~[1, 3]~ và bút ~[4, 5]~, sẽ có một kẽ hở không được tô màu giữa 3 và 4. Ví dụ, điểm 3.5 sẽ không có màu.

Zero Two có một mảng ~n~ số nguyên ~a_1, a_2, ... , a_n~.

Với một đoạn ~[l,r]~ cho trước, cô muốn bạn tìm hai đoạn con không giao nhau nằm trong đoạn ~[l,r]~ sao cho tổng của cả hai đoạn đều bằng ~0~.

Tuy nhiên, do cảm thấy yêu cầu còn quá dễ nên cô đã nâng cấp bài toán. Bạn cần tìm số lượng nhiều nhất các đoạn con không giao nhau nằm trong đoạn ~[l,r]~ và có tổng bằng ~0~.

Bạn cần trả lời ~q~ câu hỏi của Zero Two để làm cô ấy vui!

Input

• Dòng đầu tiên gồm số nguyên dương ~n~ (~n \le 4 \times 10^5~).
• Dòng thứ hai chứa ~n~ số dương ~a_i~ (~-10^9 \le a_i \le 10^9~).
• Dòng thứ ba gồm số nguyên dương ~q~ (~q \le 4 \times 10^5~).
• ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~l,r~ (~1 \le l \le r \le n~).

Output

• In ra trên ~q~ dòng là đáp án cho câu hỏi của Zero Two.

Scoring

• Subtask 1 ~(20\%)~: ~1 \le n,q \le 5000~.
• Subtask 2 ~(30\%)~: ~2 \le n,q \le 10^5~.
• Subtask 3 ~(50\%)~: Không có giới hạn gì thêm.

Sample Input

10
1 2 -3 0 1 -4 3 2 -1 1
3
1 10
1 5
2 9

Sample Output

4
2
2

Tuyến Metro dự định đưa vào khai thác bao gồm các ga được nối với nhau bằng các đường hầm hai chiều. Giữa hai nhà ga bất kì, luôn tồn tại đúng một đường đi sao cho mỗi đường hầm chỉ được đi qua nhiều nhất một lần. Nói cách khác, cấu trúc của tuyến Metro mới là một cây.

Tuyến Metro có hệ thống tính phí như sau: Mỗi ga có một trọng số ~x~ (~x = 1~ hoặc ~x = -1~). Nếu nhà ga có trọng số là ~-1~ thì mỗi lần bạn thăm nhà ga đó bạn sẽ mất phí ~1~ đồng, ngược lại thì bạn được thưởng ~1~ đồng.

Ban đầu, tuyến Metro chỉ có một ga với số thứ tự ~1~ và trọng số ~x = 1~. Có hai loại sự kiện như sau:

• + v x: Một ga mới với trọng số ~x~ được xây dựng. Ga này sẽ có một hầm hai chiều nối với ga được đánh số ~v~. Nó được gắn số thứ tự bằng một số lớn hơn một đơn vị so với số lượng nhà ga hiện có.
• ? u v k: Lâm, một người thường xuyên di chuyển bằng Metro, thắc mắc rằng có thể chọn một đường đi con của đường đi từ ga ~u~ đến ga ~v~, sao cho nếu đi theo con đường này thì sẽ được thưởng chính xác ~k~ đồng (~k < 0~ thì có nghĩa là phải trả phí). Chú ý: đường đi con này phải đi qua ít nhất hai ga.

Dữ liệu vào

• Dòng thứ nhất chứa số nguyên dương ~Q~ (~Q \le 2 \times 10^5~) mô tả số sự kiện sẽ xảy ra;
• ~Q~ dòng tiếp theo mô tả các sự kiện, mỗi dòng có một trong hai dạng: 1) Dạng thứ nhất: + v x mô tả thêm một ga mới nối với ga ~v~ (~x = 1~ hoặc ~x = -1~ và ga ~v~ có tồn tại); 2) Dạng thứ hai: ? u v k mô tả truy vấn có tồn tại đường đi con của đoạn đường đi từ ~u~ đến ~v~ với phần thưởng là ~k~ hay không? (ga ~u~ và ~v~ tồn tại và ~k \le Q~).

Kết quả

• Với mỗi truy vấn, nếu tồn tại đường đi con thỏa mãn in ra YES, nếu không in ra NO.

Giới hạn

• Subtask 1 (30%): ~Q \le 10^4~;
• Subtask 2 (30%): ~v = 1~ trong các truy vấn +;
• Subtask 3 (30%): Cấu trúc cây của ga là một đường thẳng;
• Subtask 4 (10%): Không có ràng buộc gì thêm.

Sample Input 1

5
+ 1 1
+ 2 -1
? 1 3 -1
+ 3 1
? 1 3 1

Sample Output 1

YES
YES

Notes

• Thêm ga thứ 2, nối với ga thứ 1, trọng số 1.
• Thêm ga thứ 3, nối với ga thứ 2, trọng số -1.
• Truy vấn có đường từ ga thứ 1 đến ga thứ 3 với tổng thưởng -1 không? $\rightarrow$ YES.
• Thêm ga thứ 4, nối với ga thứ 1, trọng số 1.
• Truy vấn có đường từ ga thứ 1 đến ga thứ 3 với tổng thưởng 1 không? $\rightarrow$ NO.