A string is given and is composed of lowercase letters only. The following operations can be performed on the string:

• $1 \ l \ r \ c$: all characters from the substring $[l,r]$ become equal to $c$.
• $2 \ l \ r$: print 1 if the substring $[l,r]$ is a palindrome, otherwise print 0.

Task

Write a program that reads a string of length $n$ and $q$ operations and executes these operations.

Input data

The first line contains $n$ and $q$, the length of the string and the number of operations. The next line contains the string. On each of the following $q$ lines there is an operation.

Output data

For the operations of type $2$, print the answer, without any additional spaces.

Constraints and clarifications

• The string is indexed from $1$.
• $1 \leq n, q \leq 200 \ 000$
• It is recommended to use the following line of code at the beginning of the main function, it will decrease the input reading time: cin.tie(0)->sync_with_stdio(0);.

Example 1

stdin

7 4
abbaaaa
2 1 4
2 1 3
1 5 6 b
2 1 7

stdout

101

Explanation

For the first operation, the substring abba is a palindrome.
For the second operation, the substring abb is not a palindrome.
In this moment, we need to modify the string, it becomes abbabba.
For the third operation, the substring abbabba is a palindrome.

Example 2

stdin

15 12
ajhsajdjadnggsk
2 5 9
2 6 8
1 6 11 r
2 5 9
1 13 15 a
2 11 13
1 1 3 a
2 1 15
1 4 5 g
2 1 15
1 5 5 r
2 1 15

stdout

1100001