Cho xâu ~S~ có độ dài ~n (n \leq 10^5)~ chỉ gồm các chữ cái tiếng Anh in thường. Ký tự thứ ~i~ trong xâu được ký hiệu là ~S_i \ (i \leq n)~. Có 2 loại truy vấn trên xâu ~S~ như sau:

• ~1\ p\ c~: Thực hiện phép gán ~S_p = c~.
• ~2\ x\ y\ u\ v~: So sánh thứ tự từ điển của 2 xâu con ~S[x...y]~ và ~S[u...v]~.

Định nghĩa về thứ tự từ điển của 2 xâu:

• ~A=B~ khi: ~|A|=|B|~ (trong đó ~|T|~ là độ dài của xâu ~|T|~) và ~A_i = B_i (\forall i: 1 \leq i \leq |A|)~.
• ~A<B~ (hay ~B>A~) khi ~A~ là xâu con tiền tố của ~B~ hoặc ~A_k < B_k~ (với ~k~ là vị trí đầu tiên mà ~A_k \neq B_k~).

Yêu cầu

Cho ~q~ truy vấn thuộc 1 trong 2 dạng trên. Với truy vấn loại 2, in ra:

• -1 nếu ~S[x...y]<S[u...v]~</li>
• 0 nếu ~S[x...y]=S[u...v]~
• 1 nếu ~S[x...y]>S[u...v]~

Dữ liệu

• Dòng đầu chứa ~2~ số nguyên dương ~n,q (n,q \leq 10^5)~.
• Dòng tiếp theo chứa ~n~ chữ cái tiếng Anh in thường biểu diễn xâu ~S~.
• ~q~ dòng tiếp theo, mỗi dòng chứa một truy vấn thuộc 1 trong 2 dạng:
  • ~1\ p\ c\ (1 \leq p \leq n;\ c\ \in ['a'...'z']).~
  • ~2\ x\ y\ u\ v\ (1 \leq x,y,u,v \leq n;\ x\leq y;\ u\leq v ).~

Kết quả

Với mỗi truy vấn loại 2, in cách dòng 1 số nguyên duy nhất là đáp án cho truy vấn tương ứng theo yêu cầu đề bài.

Ví dụ

Sample Input

6 5
ababac
2 1 3 3 5
2 1 2 3 5
1 5 d
2 1 3 3 5
2 4 6 2 3

Sample Output

0
-1
-1
1

Giải thích

• Truy vấn 1: "aba" = "aba"
• Truy vấn 2: "ab" < "aba"
• Truy vấn 3: S = "ababdc"
• Truy vấn 4: "aba" < "abd"
• Truy vấn 5: "bdc" > "ba"