Bệ phóng tên lửa

Trạm không gian Alpha đang chuẩn bị phóng hàng loạt tên lửa. Mỗi tên lửa ban đầu được bố trí tại một bệ phóng có độ cao nhất định.

Tuy nhiên, do ảnh hưởng từ từ trường, độ cao của một số bệ có thể thay đổi theo thời gian. Ngoài ra, để tối ưu hiệu suất phóng, trạm cần xác định xem có tồn tại tên lửa nào trong một khoảng vị trí nhất định có độ cao không vượt quá một ngưỡng cho trước hay không.

Bạn được giao nhiệm vụ mô phỏng các truy vấn sau:

• 1 u v: cập nhật độ cao của tên lửa tại vị trí \(u\) thành \(v\).
• 2 u v val: kiểm tra xem có tên lửa nào nằm trong đoạn \([u, v]\) có độ cao nhỏ hơn hoặc bằng \(val\). Nếu có, in ra vị trí nhỏ nhất thoả mãn. Nếu không, in \(-1\).

Input

• Dòng đầu tiên chứa hai số nguyên \(n\), \(q\) — số tên lửa và số truy vấn (\(1 \le n \le 10^5\), \(1 \le q \le 10^6\)).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) — độ cao ban đầu của các tên lửa (\(0 \le a_i \le 10^9\)).
• Mỗi dòng trong \(q\) dòng tiếp theo là một truy vấn, theo một trong hai dạng sau: - 1 u v (\(1 \le u \le n\), \(0 \le v \le 10^9\)) - 2 u v val (\(1 \le u \le v \le n\), \(0 \le val \le 10^9\))

Output

Với mỗi truy vấn loại 2, in ra một dòng:

• Nếu tồn tại tên lửa thoả mãn, in ra vị trí nhỏ nhất (bên trái nhất).
• Nếu không, in \(-1\).

Scoring

• Subtask 1 (30% số điểm): \(n, q \le 1000\)
• Subtask 2 (25% số điểm): \(q \le 10^5\)
• Subtask 3 (45% số điểm): \(q \le 10^6\)

Sample Input 1

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

Sample Output 1

2
3
-1
2