Cho ~n~ quyển sách được đánh số từ ~1~ đến ~n~, quyển sách thứ ~i~ có trọng lượng ~w_i~ được sắp xếp thành một chồng với quyển thứ ~1~ ở trên cùng.

Năm 2025, Lucian đặt mục tiêu sẽ đọc sách liên tục trong ~q~ ngày. Ở ngày thứ ~i~, Lucian muốn đọc quyển sách có chỉ số ~p_i~. Và để lấy được quyển sách ra khỏi chồng sách, anh sẽ phải nhấc tất cả các quyển sách nằm trên quyển sách cần đọc lên, lấy quyển sách có chỉ số ~p_i~ ra rồi đặt lại quyển sách này lên trên cùng sau khi đọc xong. Lưu ý, sau quá trình này, các quyển sách vẫn giữ chỉ số ban đầu.

Yêu cầu: Ở mỗi ngày, hãy giúp Lucian tổng trọng lượng sách mà Lucian cần nhấc lên.

Input

Dòng đầu tiên chứa hai số nguyên ~n, q~ số lượng sách và số ngày mà Lucian đọc sách.

Dòng thứ hai chứa ~n~ số nguyên ~w_1, w_2, \dots, w_n~ (với ~1 \leq w_i \leq 10^9~) là trọng lượng của từng quyển sách.

Dòng thứ ba chứa ~q~ số nguyên ~p_1, p_2, \dots, p_q~ (với ~1 \leq p_j \leq n~) là chỉ số của quyển sách mà Lucian sẽ đọc trong từng ngày theo kế hoạch.

Output

In ra ~q~ dòng, mỗi dòng chứa một số nguyên duy nhất là tổng trọng lượng sách mà Lucian cần nhấc lên.

Scoring

• Subtask ~1~ (chiếm ~20\%~ số điểm): ~1 \leq n, q \leq 5000~.

• Subtask ~2~ (chiếm ~80\%~ số điểm): ~1 \leq n, q \leq 10^6~.

Sample Input 1

5 4
1 2 3 4 5
2 3 4 5

Sample Output 1

1
3
6
10

Cho mảng ~a~ gồm ~n~ phần tử được đánh số từ ~1~ đến ~n~ và ~q~ truy vấn thuộc một trong hai loại:

1. Cho hai số nguyên ~k, x~, gán ~a_k \leftarrow x~.

2. Cho hai số nguyên ~l, r~, tìm giá trị của phần tử nhỏ nhất trong đoạn con ~a_l, a_{l+1}, \dots, a_r~.

Yêu cầu: Với mỗi truy vấn loại ~2~, in ra giá trị phần tử nhỏ nhất cần tìm.

Input

Dòng đầu chứa hai số nguyên ~n, q~ là kích thước mảng ~a~ và số lượng truy vấn.

Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (với ~0 \leq a_i \leq 10^9~) mô tả mảng ~a~.

Trong ~q~ dòng tiếp theo, mỗi dòng chứa ba số nguyên mô tả các truy vấn:

• Đối với truy vấn loại 1, ba số nguyên này lần lượt là ~1 \space k \space x~ (với ~1 \leq k \leq n~ và ~0 \leq x \leq 10^9~).

• Đối với truy vấn loại 2, ba số nguyên này lần lượt là ~2 \space l \space r~ (với ~1 \leq l \leq r \leq n~).

Output

Với mỗi truy vấn loại 2, in ra đáp án trên một dòng.

Scoring

• Subtask ~1~ (chiếm ~20\%~ số điểm): ~1 \leq n, q \leq 5000~.

• Subtask ~2~ (chiếm ~40\%~ số điểm): ~1 \leq n, q \leq 4 \cdot 10^5~.

• Subtask ~3~ (chiếm ~40\%~ số điểm): ~1 \leq n, q \leq 10^6~.

Sample Input 1

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

Sample Output 1

2
4
5
6

Sample Input 2

6 6
8 3 5 9 9 3
2 2 5
2 3 6
1 3 8
2 1 6
1 5 5
2 6 6

Sample Output 2

3
3
3
3

Cho mảng ~a~ gồm ~n~ phần tử được đánh số từ ~1~ đến ~n~ và ~q~ thuộc một trong hai dạng:

1. Cho hai số nguyên ~k, x~, gán ~a_k \leftarrow x~.

2. Cho ba số nguyên ~l, r, y~, đếm số phần tử trong đoạn con ~a_l, a_{l+1}, \dots, a_r~ có giá trị là ~y~. Nói cách khác, đếm số giá trị ~j~ sao cho ~l \leq j \leq r~ và ~a_j = y~.

Yêu cầu: Với mỗi truy vấn loại 2, in ra giá trị cần tìm.

Input

Dòng đầu tiên chứa hai số nguyên ~n, q~ là kích thước mảng ~a~ và số lượng truy vấn.

Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (với ~1 \leq a_i \leq 10^9~) mô tả mảng ~a~.

Trong ~q~ dòng tiếp theo, mỗi dòng mô tả một truy vấn:

• Đối với truy vấn loại 1, dòng này chứa ba số nguyên ~1 \space k \space x~ (với ~1 \leq k \leq n~ và ~1 \leq x \leq 10^9~).

• Đối với truy vấn loại 2, dòng này chứa bốn số nguyên ~2 \space l \space r \space y~ (với ~1 \leq l \leq r \leq n~ và ~1 \leq y \leq 10^9~).

Output

Với mỗi truy vấn loại 2, in ra đáp án trên một dòng.

Scoring

• Subtask ~1~ (chiếm ~20\%~ số điểm): ~1 \leq n, q \leq 5000~.

• Subtask ~2~ (chiếm ~30\%~ số điểm): ~1 \leq n, q \leq 10^5~; ~1 \leq y \leq 10~.

• Subtask ~3~ (chiếm ~50\%~ số điểm): ~1 \leq n, q \leq 10^5~.

Sample Input 1

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

Sample Output 1

2
3

Cho dãy ~a~ gồm ~n~ phần tử được đánh số từ ~1~ đến ~n~, số nguyên ~m~ và ~q~ truy vấn thuộc một hai loại:

1. Cho hai số nguyên ~k, x~, gán ~a_k \leftarrow a_k + x~. Test đảm bảo ~a_k~ không bao giờ âm.

2. Cho ba số nguyên ~l, r, y~, tính tổng các phần tử trong đoạn con ~a_l, a_{l+1}, \dots, a_r~ đồng dư ~y~ modulo ~m~. Nói cách khác, hãy tính:

   $$\sum_{l \leq i \leq r, \space a_i \equiv y \pmod m} a_i$$

Yêu cầu: Với mỗi truy vấn loại 2, in ra tổng cần tìm.

Input

Dòng đầu tiên chứa ba số nguyên ~n, m, q~ là kích thước mảng ~a~, hằng số cho trước và số lượng truy vấn.

Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (với ~0 \leq a_i \leq 10^9~) mô tả mảng ~a~.

Trong ~q~ dòng tiếp theo, mỗi dòng mô tả một truy vấn:

• Đối với truy vấn loại 1, dòng này chứa ba số nguyên ~1 \space k \space x~ (với ~1 \leq k \leq n~ và ~-10^9 \leq x \leq 10^9~).

• Đối với truy vấn loại 2, dòng này chứa bốn số nguyên ~2 \space l \space r \space y~ (với ~1 \leq l \leq r \leq n~ và ~0 \leq y < m~).

Output

Với mỗi truy vấn loại 2, in ra đáp án trên một dòng.

Scoring

• Subtask ~1~ (chiếm ~20\%~ số điểm): ~1 \leq n, q \leq 5000~; ~1 \leq m \leq 10^9~.

• Subtask ~2~ (chiếm ~10\%~ số điểm): ~1 \leq n, q \leq 10^4~; ~m = 1~.

• Subtask ~3~ (chiếm ~70\%~ số điểm): ~1 \leq n, q \leq 10^4~; ~1 \leq m \leq 10~.

Sample Input 1

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

Sample Output 1

5
12

Cho bản đồ kho báu có dạng bảng chữ nhật ~n \times m~, các dòng được đánh số từ ~1~ đến ~n~ và các cột được đánh số từ ~1~ đến ~m~. Ô ở dòng thứ ~i~, cột thứ ~j~ của bản đồ chứa một kho báu có giá trị ~a_{i, j}~. Cho ~q~ truy vấn thuộc một trong hai loại:

1. Cho ~x, y, z~, gán ~a_{x, y} \leftarrow z~.

2. Cho ~i, j, d~, tính tổng giá trị tất cả các kho báu có khoảng cách Manhattan~^\dagger~ với ô ~(i, j)~ không quá ~d~.

Yêu cầu: Với mỗi truy vấn loại 2, in ra tổng giá trị cần tìm.

~\dagger~ Khoảng cách Manhattan giữa hai số ~(i, j)~ và ~(x, y)~ là ~|i - x| + |j - y|~.

Input

Dòng đầu tiên chứa ba số nguyên ~n, m, q~ là kích thước bản đồ và số truy vấn.

Trong ~n~ dòng tiếp theo, dòng thứ ~i~ chứa ~m~ số nguyên ~a_{i, 1}, a_{i, 2}, \dots, a_{i, m}~ (với ~0 \leq a_{i, j} \leq 10^9~) là giá trị của các ô kho báu trên dòng thứ ~i~.

Trong ~q~ dòng tiếp theo, mỗi dòng chứa bốn số nguyên mô tả một truy vấn:

• Với truy vấn loại 1, bốn số nguyên đó là ~1 \space x \space y \space z~ (với ~1 \leq x \leq n~, ~1 \leq y \leq m~ và ~0 \leq z \leq 10^9~).

• Với truy vấn loại 2, bốn số nguyên đó là ~2 \space i \space j \space d~ (với ~1 \leq i \leq n~, ~1 \leq j \leq m~ và ~0 \leq d \leq n + m - 2~).

Output

Với mỗi truy vấn loại 2, in ra đáp án trên một dòng.

Scoring

• Subtask ~1~ (chiếm ~20\%~) số điểm: ~1 \leq n, m \leq 100~; ~1 \leq q \leq 1000~.

• Subtask ~2~ (chiếm ~80\%~) số điểm: ~1 \leq n, m \leq 500~; ~1 \leq q \leq 10^5~.

Sample Input 1

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

Sample Output 1

28
32

Cho mảng ~a~ gồm ~n~ phần tử được đánh số từ ~1~ đến ~n~, ta định nghĩa ~f(l, r)~ là số cặp nghịch thế trong đoạn con ~a_l, a_{l+1}, \dots, a_r~. Nói cách khác, ~f(l, r)~ là hàm đếm số cặp ~(i, j)~ sao cho ~l \leq i < j \leq r~ và ~a_i > a_j~.

Yêu cầu: Tính tổng ~f(l, r)~ cho mọi đoạn con của mảng ~a~, tức là tính

$$\sum_{1 \leq l \leq r \leq n} f(l, r)$$

Input

Dòng đầu tiên chứa số nguyên ~n~ là kích thước mảng.

Dòng thứ hai chứa ~n~ số nguyên ~a_1~, ~a_2~, ~\dots~, ~a_n~ (với ~1 \leq a_i \leq 10^9~) mô tả mảng ~a~.

Output

In ra đáp án modulo ~10^9 + 22213~, trên một dòng duy nhất.

Scoring

• Subtask ~1~ (chiếm ~20\%~ số điểm): ~1 \leq n \leq 100~.

• Subtask ~2~ (chiếm ~40\%~ số điểm): ~1 \leq n \leq 2000~.

• Subtask ~3~ (chiếm ~40\%~ số điểm): ~1 \leq n \leq 2 \cdot 10^5~.

Sample Input 1

5
5 3 4 1 2

Sample Output 1

25

Sample Input 2

6
1 2 3 4 6 5

Sample Output 2

5

Cho mảng ~a~ gồm ~n~ phần tử được đánh số từ ~1~ đến ~n~ và ~q~ thuộc một trong ba dạng:

1. Cho số nguyên ~x~, thêm một phần tử có giá trị ~x~ vào mảng ~a~.

2. Cho số nguyên ~y~, xóa một phần tử có giá trị ~y~ khỏi mảng ~a~ (nếu mảng ~a~ không có phần tử nào có giá trị ~y~, bỏ qua thao tác này).

3. Cho số nguyên ~k~, in ra phần tử nhỏ thứ ~k~ của mảng. Nói cách khác, gọi mảng ~b~ là mảng ~a~ sau khi sắp xếp theo thứ tự không giảm, tìm ~b_k~.

Yêu cầu: Với mỗi truy vấn loại 3, in ra giá trị cần tìm.

Input

Dòng đầu tiên chứa hai số nguyên ~n, q~ là kích thước mảng ~a~ và số lượng truy vấn.

Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (với ~1 \leq a_i \leq 10^9~) mô tả mảng ~a~.

Trong ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên mô tả một truy vấn:

• Đối với truy vấn loại 1, hai số nguyên đó là ~1 \space x~ (với ~1 \leq x \leq 10^9~).

• Đối với truy vấn loại 2, hai số nguyên đó là ~2 \space y~ (với ~1 \leq y \leq 10^9~).

• Đối với truy vấn loại 3, hai số nguyên đó là ~3 \space k~ (với ~1 \leq k \leq |a|~ và ~|a|~ là kích thước của mảng ~a~ tại thời điểm truy vấn).

Output

Với mỗi truy vấn loại 3, in ra đáp án trên một dòng.

Scoring

• Subtask ~1~ (chiếm ~20\%~ số điểm): ~1 \leq n, q \leq 2000~.

• Subtask ~2~ (chiếm ~10\%~ số điểm): ~1 \leq n, q \leq 5000~.

• Subtask ~3~ (chiếm ~70\%~ số điểm): ~1 \leq n, q \leq 3 \cdot 10^5~.

Sample Input 1

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

Sample Output 1

3
2

Cho mảng ~a~ gồm ~n~ phần tử được đánh số từ ~1~ đến ~n~ và ~q~ truy vấn online thuộc một trong hai loại:

1. Cho ~k, x~, gán ~a_k \leftarrow x~.

2. Cho ~l, r, p~, tính tổng XOR~^\dagger~ đoạn con ~a_l, a_{l+1}, \dots, a_r~ ngay sau truy vấn thứ ~p~.

Yêu cầu: Với mỗi truy vấn loại 2, in ra kết quả cần tìm.

~\dagger~ Tổng XOR của một dãy số ~b_1, b_2, \dots b_m~ là ~b_1 \oplus b_2 \oplus \dots \oplus b_m~ với ~\oplus~ là phép bitwise XOR.

Input

Dòng đầu tiên chứa hai số nguyên ~n, q, t~ là kích thước mảng ~a~, số lượng truy vấn và hằng số để mã hóa các truy vấn online.

Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (với ~0 \leq a_i \leq 10^9~) mô tả mảng ~a~.

Trong ~q~ dòng tiếp theo, mỗi dòng mô tả một truy vấn:

• Đối với truy vấn loại 1, dòng đó chứa ba số nguyên ~1 \space k' \space x'~. Khi đó, hai giá trị ~k, x~ có thể được khôi phục bằng công thức:

  $$\begin{align} k &= k' \oplus (t \cdot ans^2) \\ x &= x' \oplus (t \cdot ans^2) \end{align}$$

  với ~0 \leq k', x' < 2^{63}~, ~1 \leq k \leq n~ và ~0 \leq x \leq 10^9~.

• Đối với truy vấn loại 2, dòng đó chứa bốn số nguyên ~2 \space l' \space r' \space p'~. Khi đó ba giá trị ~l, r, p~ có thể được khôi phục bằng công thức:

  $$\begin{align} l &= l' \oplus (t \cdot ans^2) \\ r &= r' \oplus (t \cdot ans^2) \\ p &= p' \oplus (t \cdot ans^2) \\ \end{align}$$

  với ~0 \leq l', r', p' < 2^{63}~, ~1 \leq l \leq r \leq n~, ~p < i~ và ~i~ là thứ tự của truy vấn hiện tại.

Ở đây, ~\oplus~ là kí hiệu của phép bitwise XOR, ~ans~ là kết quả của truy vấn loại 2 gần nhất, ban đầu, ~ans = 0~.

Output

Với mỗi truy vấn loại 2, in ra kết quả trên một dòng.

Scoring

• Subtask ~1~ (chiếm ~20\%~): ~1 \leq n, q \leq 2000~; ~0 \leq t \leq 1~.

• Subtask ~2~ (chiếm ~20\%~): ~1 \leq n, q \leq 2 \cdot 10^5~; ~t = 0~.

• Subtask ~3~ (chiếm ~60\%~): ~1 \leq n, q \leq 2 \cdot 10^5~; ~t = 1~.

Sample Input 1

10 7 0
16 3 9 4 11 0 12 2 10 13
1 3 8
1 2 19
2 5 5 1
2 1 8 1
2 3 5 3
1 1 7
2 4 9 1

Sample Output 1

11
26
7
11

Cho xâu ~s~ độ dài ~n~, các kí tự của xâu được đánh số từ ~1~ đến ~n~. Cho ~q~ truy vấn thuộc một trong hai dạng:

1. Cho số nguyên ~i~ và chữ cái ~c~, gán ~s_i \leftarrow c~.

2. Cho ba số nguyên ~i, j, k~. Xét hai xâu con bắt đầu từ ~i~ và ~j~, có độ dài ~k~, so sánh thứ tự từ điển~^\dagger~ của hai xâu này. Nói cách khác, hãy xét thứ tự từ điển của hai xâu con ~s_i s_{i+1} \dots s_{i+k-1}~ và xâu con ~s_j s_{j+1} \dots s_{j+k-1}~

Yêu cầu: Với mỗi truy vấn loại 2, in ra một trong ba giá trị tương ứng kết quả so sánh thứ tự từ điển tìm được:

• Nếu hai xâu con giống nhau hoàn toàn, in ra =.

• Nếu xâu con ~s_i s_{i+1} \dots s_{i+k-1}~ có thứ tự từ điển bé hơn xâu ~s_j s_{j+1} \dots s_{j+k-1}~, in ra <.

• Ngược lại, in ra >.

~\dagger~ Xâu ~a_1 a_2 \dots a_m~ có thứ tự từ điển bé hơn xâu ~b_1 b_2 \dots b_m~ khi tồn tại một vị trí ~k~ (với ~0 \leq k \leq m~) sao cho tiền tố độ dài ~k~ của hai xâu ~a, b~ là giống nhau và ~a_{k+1} < b_{k+1}~. Việc so sánh hai chữ cái được thực hiện dựa trên thứ tự bảng chữ cái alphabet.

Input

Dòng đầu chứa hai số nguyên ~n, q~ là độ dài xâu ~s~ và số lượng truy vấn.

Dòng thứ hai chứa xâu độ dài ~n~ là xâu ~s~ gồm các chữ cái thường trong bảng chữ cái tiếng Anh.

Trong ~q~ dòng tiếp theo, mỗi dòng chứa mô tả của một truy vấn:

• Đối với truy vấn loại 1, dòng này chứa ba số nguyên ~1 \space i \space c~ (với ~1 \leq i \leq n~ và ~c~ là chữ cái thường trong bảng chữ cái tiếng Anh).

• Đối với truy vấn loại 2, dòng này chứa bốn số nguyên ~2 \space i \space j \space k~ (với ~1 \leq i, j \leq n~ và ~1 \leq k \leq n - \max(i, j) + 1~).

Output

In ra một xâu gồm các kí tự =, < và > biểu diễn đáp án của các truy vấn loại 2 tương ứng.

Scoring

• Subtask ~1~ (chiếm ~20\%~ số điểm): ~1 \leq n, q \leq 5000~.

• Subtask ~2~ (chiếm ~30\%~ số điểm): ~1 \leq n, q \leq 2 \cdot 10^5~; các kí tự trong xâu ~s~ tại mỗi thời điểm là ~\texttt{a}~ hoặc ~\texttt{b}~.

• Subtask ~3~ (chiếm ~50\%~ số điểm): ~1 \leq n, q \leq 2 \cdot 10^5~.

Sample Input 1

6 4
abcabc
2 1 4 2
1 6 d
2 1 4 3
2 2 4 3

Sample Output 1

=
<
>