Cho dãy ~x~ gồm ~n~ số nguyên, bạn cần thực hiện ~q~ truy vấn có một trong hai dạng sau:

• ~1\ k\ u~: Cập nhật giá trị ở vị trí ~k~ thành ~u~ (~1 \le k \le n, 1 \le u \le 10^9~).
• ~2\ a\ b~: In tổng các giá trị trong đoạn ~[a, b]~ (~1 \le a \le b \le n~).

Input

• Dòng đầu tiên gồm hai số tự nhiên ~n~ và ~q~, lần lượt là số lượng phần tử và số lượng truy vấn (~1 \le n, q \le 2 \cdot 10^5~).
• Dòng thứ hai gồm ~n~ số nguyên ~x_1, x_2, \dots, x_n~ là các giá trị của dãy số (~1 \le x_i \le 10^9~).
• ~q~ dòng tiếp theo mỗi dòng gồm ba số nguyên thể hiện các truy vấn loại ~1~ hoặc ~2~.

Output

Với mỗi truy vấn loại ~2~ in ra kết quả tương ứng.

Sample Input 1

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

Sample Output 1

14
2
11

Cho dãy ~a~ có ~n~ phần tử, hãy thực hiện các truy vấn sau:

• ~1\ l\ r~: Đảo ngược đoạn phần tử ~[l, r]~ của dãy ~a~.
• ~2\ l\ r~: Tính tổng các giá trị của đoạn ~[l, r]~ của dãy ~a~.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~m~ ~(1 \le n \le 2 \cdot 10^5, 1 \le m \le 10^5)~— kích thước và số lượng truy vấn.
• Dòng tiếp theo chứa ~n~ số nguyên không âm ~a_1, a_2, a_3, \dots, a_n~ ~(0 \le a_i \le 10^9)~.
• ~m~ dòng tiếp theo chứa những truy vấn có dạng ~t~, ~l~ và ~r~ ~(1 \le t \le 2, 1 \le l \le r \le n)~.

Output

In ra đáp án cho mỗi truy vấn ~t=2~.

Sample Input 1

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

Sample Output 1

8
9

Notes

• Mảng ~a~ ban đầu là ~\{2, 1, 3, 4, 5, 3, 4, 4\}~.
• Truy vấn ~1~ hỏi tổng phần tử trong đoạn ~[2, 4]~ bằng ~8~.
• Mảng ~a~ sau khi thực hiện truy vấn ~2~ là ~\{2, 1, 3, 5, 4, 3, 4, 4\}~.
• Truy vấn ~3~ hỏi tổng phần tử trong đoạn ~[2, 4]~ bằng ~9~.

Cho một dãy số ~n~ phần tử ~a_{1}~, ~a_{2}~, ..., ~a_{n}~ và một số các truy vấn ~d~. Một truy vấn ~d~ là một cặp (~i~, ~j~) (~1~ ~\leq~ ~i~ ~\leq~ ~j~ ~\leq~ ~n~). Với mỗi truy vấn ~d~(i, ~j~), bạn cần trả về số phần tử phân biệt nằm trong dãy con ~a_{i}~, ~a_{i+1}~, ..., ~a_{j}~.

Input

• Dòng ~1~: ~n~ (~1~ ~\leq~ ~n~ ~\leq~ ~30000~).
• Dòng ~2~: ~n~ số ~a_{1}~, ~a_{2}~, ..., ~a_{n}~ (~1~ ~\leq~ ~a_{i}~ ~\leq~ ~10^{6}~).
• Dòng ~3~: ~q~ (~1~ ~\leq~ ~q~ ~\leq~ ~200000~), số lượng truy vấn- ~d~.
• Trong ~q~ dòng sau, mỗi dòng chứa ~2~ số ~i~, ~j~ biểu thị một truy vấn-d (~1~ ~\leq~ ~i~ ~\leq~ ~j~ ~\leq~ ~n~).

Output

• Với mỗi truy vấn ~d~(~i~, ~j~), in ra số phần tử phân biệt thuộc dãy con ~a_{i}~, ~a_{i+1}~, ..., ~a_{j}~ trên một dòng.

Sample Input

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

Sample Output

3
2
3

Trên một mặt phẳng có n điểm có tọa độ nguyên ~(x_i, y_i)~ trong khoảng từ ~0~ đến ~10^6~. Khoảng cách giữa hai điểm có số thứ tự ~a~ và ~b~ là ~dist(a, b)~ được xác định như sau: ~|x_a - x_b| + |y_a - y_b|~ (khoảng cách tính bằng công thức này được gọi là khoảng cách Manhattan).

Chúng ta gọi một đường đi Hamiltonian là một hoán vị ~p_i~ của các số từ ~1~ đến ~n~. Chiều dài của đường đi này được tính theo công thức sau: $$\sum_{i=1}^{n-1}(dist(p_i, p_{i+1})) + dist(p_n, p_1)$$

Hãy tìm một đường đi Hamiltonian sao cho chiều dài của nó không vượt quá ~25 \times 10^8~. Lưu ý rằng bạn không cần tối ưu hóa chiều dài của đường đi.

Input

Dòng đầu tiên chứa số nguyên n ~(1 \leq n \leq 10^6)~.

Dòng thứ ~i+1~ chứa tọa độ của điểm thứ ~i~: ~x_i~ và ~y_i~ ~(0 \leq x_i, y_i \leq 10^6)~.

Đảm bảo rằng không có hai điểm nào trùng nhau.

Output

In ra hoán vị của các số ~p_i~ từ 1 đến ~n~ — đường đi Hamiltonian cần tìm.

Nếu có nhiều đáp án đúng, in bất kỳ một trong số chúng.

Đảm bảo rằng có ít nhất một đường đi thỏa mãn yêu cầu.

Sample Input 1

5
0 7
8 10
3 4
5 0
9 12

Sample Output 1

5 2 1 3 4

Cho một cây gồm ~n~ đỉnh và ~Q~ truy vấn. Trên mỗi đỉnh ~u~ của cây được gán một giá trị là ~C_u~. Mỗi truy vấn sẽ thuộc ~1~ trong ~2~ dạng như sau:

• ~1~ ~u~ ~v~ ~(1 \le u,v \le n)~ : tìm số các số khác nhau trong đường đi từ ~u~ đến ~v~.
• ~2~ ~x~ ~val~ ~(1 \le x \le n;~ ~0 \le val \le 10^9)~: gán giá trị ~val~ vào ~C_x~.

Input

• Dòng đầu tiên bao gồm hai số ~n~ và ~Q~ lần lượt là số đỉnh của cây và số truy vấn của bài (~1 \le n, Q \le 10^5~).
• Dòng thứ hai chứa ~n~ số nguyên là các giá trị ~C_1, C_2, \dots, C_n~ (~0 \le C_i \le 10^9~).
• ~n - 1~ dòng tiếp theo chứa các cạnh của cây và trong đó mỗi dòng sẽ chứa ~2~ số ~u~ và ~v~ là hai đỉnh được nối với nhau bởi ~1~ cạnh (~1 \le u, v \le n~).
• ~Q~ dòng tiếp theo lần lượt là các truy vấn của bài toán.

Output

Ở mỗi truy vấn loại ~1~ sẽ in ra đáp án của truy vấn trên một dòng duy nhất.

Scoring

Sample Input 1

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

Sample Output 1

5
3
4
3
3

Cho dãy ~A~ gồm ~N~ phần tử nguyên dương. Có ~M~ thao tác được thực hiện trên dãy ~A~ có dạng như sau:

• ~X~ ~Y~: Gán ~A_X = Y~, rồi đếm số lượng cặp số nghịch thế tồn tại trong dãy ~A~.

Nhắc lại: Một cặp số nghịch thế trong dãy ~A~ được định nghĩa là một cặp số nguyên ~(i, j)~ sao cho ~1 \leq i < j \leq n~ và ~A_i > A_j~.

Input

• Dòng đầu chứa số nguyên dương ~N~ (~1 \leq N \leq 250000~).
• Dòng thứ ~2~ chứa ~N~ số nguyên dương ~A_i~ cách nhau bởi dấu cách (~A_i \leq 5 \times 10^4~).
• Dòng thứ ~3~ chứa số nguyên dương ~M~ (~M \leq 10^4~).
• ~M~ dòng tiếp theo, mỗi dòng chứa ~2~ số nguyên dương ~X, Y~ (~X \leq N~ và ~Y \leq 5 \times 10^4~).

Output

Xuất ra ~M~ dòng, dòng thứ ~i~ chứa ~1~ số nguyên duy nhất là đáp án cho truy vấn thứ ~i~.

Sample Input

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

Sample Output

17
18
16
13
14
8
6

Trong một cuộc thí nghiệm tự hỏi tự trả lời do Lợi tổ chức, có ~n~ kẹo thủ được đánh thứ tự ~1~ đến ~n~ từ trái qua phải. Mỗi kẹo thủ đang có ~a_i~ kẹo. Một kẹo thủ được gọi là vua kẹo, nếu số kẹo của anh ta chính xác bằng tổng số kẹo của các kẹo thủ bên trái. Lợi quan tâm đến việc liệu có ít nhất một vua kẹo hay không.

Thí nghiệm như sau, Lợi thực hiện ~q~ thay đổi. Với mỗi thay đổi:

• Lợi chọn kẹo thủ ~p_i~ và thay đổi số kẹo của anh ta thành ~x_i~.

• Kiểm tra xem có ít nhất một vua kẹo hay không. Nếu có, Lợi muốn biết chỉ số của một vua kẹo bất kỳ.

Do Lợi hay bị lag, nên các bạn hãy giúp anh ấy nhé.

Input

Dòng đầu chứa ~n~ và ~q~ (~1 \le n, q \le 2 \times 10^5~).

Dòng tiếp theo chứa ~n~ số nguyên ~a_1, a_2, \cdots, a_n~ (~0 \le a_i \le 10^9~) - số kẹo của các kẹo thủ.

Cuối cùng là ~q~ dòng, dòng thứ ~i~ chứa ~p_i~ và ~x_i~ (~1 \le p_i \le n~, ~0 \le x_i \le 10^9~) - thay đổi thứ ~i~.

Output

In ra ~q~ dòng, dòng thứ ~i~ chứa ~-1~, nếu sau thay đổi thứ ~i~, không có vua kẹo nào. Ngược lại in ra ~j~ là chỉ số của vua kẹo.

Nếu có nhiều vua kẹo sau thay đổi, in ra chỉ số của vua kẹo bất kỳ.

Sample Input 1

2 1
1 3
1 2

Sample Output 1

-1

Sample Input 2

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

Sample Output 2

3
2
-1
3

Sample Input 3

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

Sample Output 3

1
-1
9
-1
4
-1
1

Notes

Ở ví dụ đầu tiên, số kẹo của các kẹo thủ sau thay đổi thứ nhất là (~2, 3~). Đáp án là ~-1~, vì tổng số kẹo của các kẹo thủ bên trái kẹo thủ thứ nhất là ~0~, bên trái kẹo thủ thứ hai là ~2~.

Ở ví dụ thứ hai:

• Sau thay đổi thứ nhất, số kẹo của các kẹo thủ là (~1, 2, 3~). Đáp án là ~3~, vì kẹo thủ thứ ba có ~3~ kẹo, tổng số kẹo của kẹo thủ thứ nhất và thứ hai cũng là ~1 + 2 = 3~.

• Sau thay đổi thứ hai, số kẹo là (~2, 2, 3~), đáp án là ~2~.

• Sau thay đổi thứ ba, số kẹo là (~2, 4, 3~), đáp án là ~-1~.

• Sau thay đổi thứ tư, số kẹo là (~2, 4, 6~), đáp án là ~3~.

Dế Mèn có mảng ~a~ gồm ~n~ số nguyên. Anh ấy cần trả lời ~q~ truy vấn sau:

• ~l\ r~: Tìm cặp ~(i, j)~ ~(l \le i < j \le r)~ sao cho ~|a_i - a_j|~ nhỏ nhất có thể, in ra giá trị đó.

Tất nhiên Dế Mèn biết bài này giải bằng chia căn cơ bản, nhưng Dế Mèn đang lười nên các bạn code giúp nhé!

Input

• Dòng đầu gồm số nguyên dương ~n~ là độ dài mảng ~a~ ~(2 \le n \le 10^5)~.
• Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(0 \le a_i \le 10^9)~.
• Dòng thứ ba gồm số nguyên dương ~q~ là số truy vấn cần trả lời (~1 \le q \le 3 \cdot 10^5~).
• ~q~ dòng tiếp theo, mỗi dòng gồm ~2~ số nguyên dương ~l, r~ tương ứng với một truy vấn ~(1 \le l < r \le n)~.

Output

In ra ~q~ dòng tương ứng câu trả lời cho ~q~ truy vấn.

Sample Input 1

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

Sample Output 1

0
1
1
3

Sắp đến mùa đông, nhân viên Bedao kéo nhau đi du lịch. Việc nghỉ đông này vốn không có gì to tát, nhưng nếu quá nhiều nhân viên nghỉ làm cùng lúc, một số lãnh đạo sẽ cảm thấy... bực bội.

Công ty Bedao có ~n~ nhân viên, và mỗi nhân viên ~i~ (trừ chủ tịch, người có số hiệu ~1~) sẽ có một cấp trên trực tiếp ~p_i~. Nói cách khác, cấu trúc của công ty Bedao có dạng cây. Nhân viên ~u~ là cấp dưới của nhân viên ~v~, nếu ~v~ là cấp trên trực tiếp của ~u~, hoặc cấp trên trực tiếp của ~u~ là cấp dưới của ~v~.

Gọi ~s_i~ là số nhân viên cấp dưới của nhân viên ~i~ (ví dụ, ~s_1 = n - 1~ vì tất cả các nhân viên đều là cấp dưới của chủ tịch). Mỗi nhân viên ~i~ cũng có sức chịu đựng ~t_i~: nếu tại một thời điểm nào đó, có nhiều hơn ~t_i~ cấp dưới của ~i~ nghỉ làm mà nhân viên ~i~ vẫn phải đi làm, ~i~ sẽ trở nên bực bội (và hạ lương của toàn bộ cấp dưới!)

Trong ~m~ ngày liên tục được ghi nhận ở công ty Bedao, mỗi ngày sẽ có ~1~ trong ~2~ sự kiện xảy ra: hoặc có một nhân viên nghỉ làm để đi du lịch, hoặc có một nhân viên trở về sau kì nghỉ. Ban đầu, không có nhân viên nào ở Bedao đang nghỉ làm. Hãy cho biết, vào ngày thứ ~i~, có bao nhiêu nhân viên trở nên bực bội vì quá nhiều cấp dưới nghỉ việc?

Input

Dòng đầu tiên chứa hai số nguyên dương ~n, m~ (~1 \le n, m \le 10^5~) — lần lượt là số nhân viên ở công ty Bedao, và số ngày được ghi nhận ở công ty.

Dòng thứ hai chứa ~n - 1~ số nguyên dương ~p_2, p_3, \ldots, p_n~ (~1 \le p_i \le n~) — số hiệu của cấp trên trực tiếp của nhân viên ~i~.

Dòng thứ ba chứa ~n~ số nguyên ~t_1, t_2, \ldots, t_n~ (~0 \le t_i \le s_i~) — sức chịu đựng của nhân viên thứ ~i~.

Dòng thứ tư chứa ~m~ số nguyên ~q_1, q_2, \ldots, q_m~ (~1 \le |q_i| \le n, q_i \neq 0~) — thể hiện sự kiện xảy ra trong ngày thứ ~i~. Nếu ~q_i > 0~, nhân viên ~q_i~ bắt đầu nghỉ làm để đi du lịch; nếu ~q_i < 0~, nhân viên ~-q_i~ trở về sau kì nghỉ của mình. Dữ liệu đảm bảo, một nhân viên chỉ có thể nghỉ làm khi đang đi làm ở công ty, và ngược lại.

Output

In ra ~m~ số nguyên ~c_1, c_2, \ldots, c_m~, với ~c_i~ là số nhân viên cảm thấy bực bội vào ngày thứ ~i~.

Scoring

Sample Input 1

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

Sample Output 1

1
1
1
2
2
2
1
0