# Palindrome String

Time limit: 0.65s Memory limit: 64MB Input: Output:

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.

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);.
# Points Constraints
0 0 Examples
1 20 $1 \leq n, q \leq 10 \ 000$; The string and operations are random.
2 30 $1 \leq n, q \leq 200 \ 000$; The operations are only of type $2$.

## 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
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