Cho dãy số ~a_1, a_2, ..., a_n~. Có ~q~ truy vấn, bao gồm ~2~ loại sau:

• Loại ~1~: ~1~ ~u~ ~v~, gán ~a_u = v~.
• Loại ~2~: ~2~ ~l~ ~r~, hãy in ra hai số ~i~ ~j~ bất kỳ sao cho ~l \le i \le j \le r~ và ~a_i \ne a_j~.

Nhiệm vụ của bạn hãy in ra các dòng là câu trả lời của từng truy vấn loại ~2~.

INPUT

• Dòng đầu tiên chứa hai số nguyên dương ~n,~ ~q~ (~1 \le n, q ≤ 3 \times 10^5~).
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ (~0 \le |a_i| \le 10^9~).
• ~q~ dòng tiếp theo, mỗi dòng là một trong hai loại truy vấn:
  • ~1~ ~u~ ~v~ (~1 \le u \le n~, ~0 \le |v| \le 10^9~).
  • ~2~ ~l~ ~r~ (~1 \le l \le r \le n~).

OUTPUT

In ra nhiều dòng, mỗi dòng gồm hai số ~i~ và ~j~ là đáp số của từng truy vấn loại ~2~.

Nếu không có kết quả hợp lệ cho truy vấn loại ~2~, in ra ~-1 -1~.

SAMPLE INPUT

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

SAMPLE OUTPUT

3 4
-1 -1
2 4
-1 -1

SUBTASKS