Một phòng thí nghiệm lưu một chuỗi gen ~s~ gồm ~n~ ký tự. Trong quá trình thí nghiệm, một vài vị trí trong chuỗi gen có thể bị thay đổi.

Có ~q~ thao tác thuộc một trong hai loại:

• Loại ~1~: thay đổi ký tự tại một vị trí.
• Loại ~2~: với hai đoạn ~s[l_1..r_1]~ và ~s[l_2..r_2]~, cần tìm độ dài tiền tố chung dài nhất của hai đoạn này.

Yêu cầu

Với mỗi thao tác loại ~2~, in ra một số nguyên là độ dài tiền tố chung dài nhất của hai đoạn được hỏi.

Dữ liệu

Dữ liệu vào từ chuẩn gồm:

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~.
• Dòng thứ hai chứa xâu ~s~ có độ dài ~n~.
• Mỗi dòng trong ~q~ dòng tiếp theo có một trong hai dạng:
  • 1 p c: gán ~s_p := c~.
  • 2 l_1 r_1 l_2 r_2: hỏi độ dài tiền tố chung dài nhất của ~s[l_1..r_1]~ và ~s[l_2..r_2]~.

Các chỉ số được đánh số từ ~1~.

Kết quả

Với mỗi thao tác loại ~2~, ghi ra một dòng chứa đáp án tương ứng.

Ví dụ

Ví dụ 1

Input

10 6
abacabadab
2 1 4 5 8
2 1 3 7 9
1 3 d
2 1 4 5 8
1 7 c
2 1 5 5 9

Output

3
1
2
2

Giải thích

Ví dụ 1

Ban đầu ~s[1..4] = \text{abac}~ và ~s[5..8] = \text{abad}~, hai đoạn có tiền tố chung dài nhất là ~\text{aba}~.

Sau khi đổi ~s_3~ thành ~\text{d}~, đoạn ~s[1..4]~ trở thành ~\text{abdc}~ nên tiền tố chung với ~s[5..8]~ chỉ có độ dài ~2~.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le n, q \le 2 \cdot 10^5~.
• ~s~ và các ký tự cập nhật chỉ gồm chữ cái tiếng Anh thường từ ~\text{a}~ đến ~\text{z}~.
• Với thao tác loại ~1~: ~1 \le p \le n~.
• Với thao tác loại ~2~: ~1 \le l_1 \le r_1 \le n~ và ~1 \le l_2 \le r_2 \le n~.

Chấm điểm

• Subtask~1~ ~(20\%)~: ~n, q \le 2000~, không có thao tác cập nhật.
• Subtask~2~ ~(25\%)~: không có thao tác cập nhật.
• Subtask~3~ ~(25\%)~: ~n, q \le 5 \cdot 10^4~.
• Subtask~4~ ~(30\%)~: không có ràng buộc bổ sung.