Quần đảo Nhật Bản trải dài theo hướng đông tây. Các đường ranh giới theo hướng bắc nam chia quần đảo thành \(N\) khu vực, được đánh số từ \(1\) đến \(N\) theo thứ tự từ tây sang đông. Hiện tại, khu vực \(i\) (\(1 \le i \le N\)) có độ cao \(A_i\) mét.

Bão thường xuyên xảy ra tại quần đảo. Khi có bão, sóng biển gây xói mòn và làm giảm độ cao của các khu vực theo quy tắc sau.

Trong một cơn bão có gió tây với cường độ \(x\), xét \(x\) khu vực đầu tiên tính từ phía tây. Mọi khu vực trong số đó mà không có khu vực nào cao hơn nó ở phía tây đều bị giảm độ cao đi \(1\) mét. Cụ thể, gọi \(a_i\) là độ cao của khu vực \(i\) trước cơn bão. Độ cao của khu vực \(i\) giảm đi \(1\) mét nếu \(i \le x\) và \(a_k \le a_i\) với mọi \(k\) thỏa mãn \(1 \le k < i\); trong các trường hợp khác, độ cao không thay đổi.

Trong một cơn bão có gió đông với cường độ \(x\), xét \(x\) khu vực đầu tiên tính từ phía đông. Mọi khu vực trong số đó mà không có khu vực nào cao hơn nó ở phía đông đều bị giảm độ cao đi \(1\) mét. Cụ thể, gọi \(a_i\) là độ cao của khu vực \(i\) trước cơn bão. Độ cao của khu vực \(i\) giảm đi \(1\) mét nếu \(i \ge N - x + 1\) và \(a_k \le a_i\) với mọi \(k\) thỏa mãn \(i < k \le N\); trong các trường hợp khác, độ cao không thay đổi.

Bạn cần mô phỏng các sự kiện trong \(Q\) ngày tiếp theo. Vào ngày thứ \(j\) (\(1 \le j \le Q\)), sự kiện xảy ra được xác định như sau:

• Nếu \(T_j = 1\), có một cơn bão gió tây với cường độ \(X_j\).
• Nếu \(T_j = 2\), có một cơn bão gió đông với cường độ \(X_j\).
• Nếu \(T_j = 3\), cần báo cáo độ cao hiện tại của khu vực \(X_j\).

Các ràng buộc bảo đảm độ cao của mọi khu vực luôn không âm.

Cho độ cao hiện tại của các khu vực và các sự kiện trong \(Q\) ngày tiếp theo. Với mỗi ngày có \(T_j = 3\), hãy tìm độ cao của khu vực được chỉ định.

Dữ liệu vào

Dữ liệu vào có dạng:

N Q
A_1 A_2 ... A_N
T_1 X_1
T_2 X_2
...
T_Q X_Q

Dữ liệu ra

Với mỗi \(j\) (\(1 \le j \le Q\)) có \(T_j = 3\), in trên một dòng số nguyên biểu diễn độ cao, tính bằng mét, của khu vực \(X_j\) tại ngày thứ \(j\). In các kết quả theo thứ tự các ngày.

Ràng buộc

• \(1 \le N \le 300\,000\).
• \(1 \le Q \le 300\,000\).
• \(Q \le A_i \le 10^9\) (\(1 \le i \le N\)).
• \(1 \le T_j \le 3\) (\(1 \le j \le Q\)).
• \(1 \le X_j \le N\) (\(1 \le j \le Q\)).
• Tất cả các giá trị trong dữ liệu vào đều là số nguyên.

Chấm điểm

1. \(5\) điểm: \(N \le 2000\), \(Q \le 2000\).
2. \(27\) điểm: Nếu \(T_j \ne 3\) thì \(X_j = N\), với mọi \(1 \le j \le Q\).
3. \(28\) điểm: \(A_1 = A_2 = \cdots = A_N = Q\).
4. \(20\) điểm: \(T_j \ne 2\) với mọi \(1 \le j \le Q\).
5. \(20\) điểm: Không có ràng buộc bổ sung.

Ví dụ

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

5
6
6

5 7
10 13 14 7 12
1 5
2 5
3 3
3 4
2 5
3 1
3 2

12
7
9
11

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

7
9
6
6

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

5
7
6

Nguồn

Bản dịch tiếng Việt từ đề gốc tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.