Nhà hàng sushi băng chuyền JOI vận chuyển các đĩa sushi trên một băng chuyền hình vòng tròn quay ngược chiều kim đồng hồ. Hiện có \(N\) khách, được đánh số từ \(1\) đến \(N\), ngồi quanh băng chuyền theo thứ tự số tăng dần ngược chiều kim đồng hồ. Khách \(N\) ngồi cạnh khách \(1\).

Mỗi khách đang giữ đúng một chiếc đĩa. Mỗi đĩa có một giá trị gọi là giá tiền. Khi rời nhà hàng, mỗi khách phải trả số tiền bằng giá của chiếc đĩa mình đang giữ.

Nhà hàng JOI tổ chức một đợt khuyến mãi đặc biệt. Đầu bếp lần lượt đưa đĩa lên băng chuyền trong \(Q\) lượt. Lượt thứ \(i\) được mô tả bởi ba số nguyên \((S_i,T_i,P_i)\), với \(1 \le i \le Q\).

Ngay trước khi đợt khuyến mãi bắt đầu, đầu bếp thu hết các đĩa đang có trên băng chuyền. Sau đó, với \(i=1,2,\ldots,Q\), lần lượt thực hiện ba bước sau:

1. Đầu bếp đặt một đĩa có giá \(P_i\) lên băng chuyền tại vị trí trước mặt khách \(S_i\).
2. Đĩa di chuyển trên băng chuyền từ khách \(S_i\) đến khách \(T_i\). Mỗi khách trên đường đi, kể cả hai khách ở đầu và cuối, xem chiếc đĩa đi qua trước mặt mình. Nếu giá đĩa trên băng chuyền nhỏ hơn giá đĩa đang giữ, khách đổi đĩa của mình với đĩa trên băng chuyền. Nếu giá đĩa trên băng chuyền lớn hơn hoặc bằng giá đĩa đang giữ, khách không đổi đĩa.
3. Sau khi đĩa đi qua trước mặt khách \(T_i\), đầu bếp thu lại chiếc đĩa đó.

Bạn là người học việc của đầu bếp và được giao nhiệm vụ rửa đĩa. Cách rửa đĩa ở nhà hàng JOI phụ thuộc vào giá của đĩa. Để chuẩn bị, bạn muốn biết trước giá của chiếc đĩa mà đầu bếp thu lại trong từng lượt của \(Q\) lượt khuyến mãi.

Bổ sung sau khi kỳ thi kết thúc: Khi \(S_i=T_i\), chỉ khách \(S_i\) thực hiện thao tác ở bước 2.

Yêu cầu

Cho giá của đĩa mà mỗi khách đang giữ ngay trước đợt khuyến mãi và thông tin của các lượt đưa đĩa lên băng chuyền. Hãy tính giá của chiếc đĩa mà đầu bếp thu lại trong mỗi lượt.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa hai số nguyên \(N,Q\), cách nhau bởi dấu cách, lần lượt là số khách và số lượt đưa đĩa lên băng chuyền.
• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa số nguyên \(X_i\), là giá của đĩa mà khách \(i\) giữ ngay trước đợt khuyến mãi, với \(1 \le i \le N\).
• Trong \(Q\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(S_i,T_i,P_i\), cách nhau bởi dấu cách, mô tả lượt thứ \(i\), với \(1 \le i \le Q\).

Dữ liệu ra

Ghi ra đầu ra chuẩn \(Q\) dòng. Dòng thứ \(i\) chứa một số nguyên là giá của chiếc đĩa mà đầu bếp thu lại trong lượt thứ \(i\), với \(1 \le i \le Q\).

Ràng buộc

• \(1 \le N \le 400\,000\).
• \(1 \le Q \le 25\,000\).
• \(1 \le X_i \le 1\,000\,000\,000\) với mọi \(1 \le i \le N\).
• \(1 \le S_i \le N\) với mọi \(1 \le i \le Q\).
• \(1 \le T_i \le N\) với mọi \(1 \le i \le Q\).
• \(1 \le P_i \le 1\,000\,000\,000\) với mọi \(1 \le i \le Q\).

Các bài toán con

1. 5 điểm: \(N \le 2\,000\), \(Q \le 2\,000\).
2. 15 điểm: \(S_i=1\) và \(T_i=N\) với mọi \(1 \le i \le Q\).
3. 80 điểm: Không có ràng buộc bổ sung.

Ví dụ

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

7
9
8
7
8
6
5

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

7
5

10 10
19
5
8
17
14
3
9
10
7
6
1 8 4
7 3 2
5 9 10
4 8 3
10 3 6
8 7 4
6 6 3
2 9 12
6 3 7
9 6 3

19
10
14
17
8
10
3
12
7
9