Một xâu được gọi là xâu đối xứng nếu đọc từ trái sang phải cũng giống như đọc từ phải sang trái. Ví dụ, A, ABA, ACCA là xâu đối xứng, còn AB thì không.

Cho một xâu ~s~ chỉ gồm các ký tự in thường, thực hiện hai loại truy vấn sau:

• ~1~ ~i~ ~c~: cập nhật ký tự ~s_i~ thành ~c~.
• ~2~ ~l~ ~r~: Tìm một xâu con liên tiếp bất kỳ trong đoạn ~[l, r]~ của ~s~ thỏa mãn xâu đó là xâu đối xứng. Nói cách khác, tìm hai chỉ số ~u, v~ (~l \le u \le v \le r~) thỏa mãn ~s[u...v]~ là xâu đối xứng.

INPUT

Dòng đầu tiên gồm số nguyên dương ~n~ và ~q~ (~1 \le n, q \le 3 \times 10^5~) - độ dài xâu ~s~ và số truy vấn.

Dòng thứ hai gồm xâu ~s~ chỉ gồm các ký tự in thường. Lưu ý, các ký tự trong xâu được đánh số từ ~1~.

~q~ dòng tiếp theo, mỗi dòng thể hiện một truy vấn:

• ~1~ ~i~ ~c~ mô tả truy vấn loại 1 (~1 \le i \le n~, ~c~ là ký tự in thường).
• ~2~ ~l~ ~r~ mô tả truy vấn loại 2 (~1 \le l \le r \le n~).

OUTPUT

Với mỗi truy vấn loại ~2~, in ra hai chỉ số ~u, v~ (~l \le u \le v \le r~) thỏa mãn đề bài. Nếu không có chỉ số nào thỏa mãn, in ra ~-1~.

SAMPLE INPUT

5 4
abcdd
2 1 5
1 5 e
1 3 a
2 1 4

SAMPLE OUTPUT

4 5
1 3