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 c1 \ l \ r \ c: all characters from the substring [l,r][l,r] become equal to cc.
  • 2 l r2 \ l \ r: print 1 if the substring [l,r][l,r] is a palindrome, otherwise print 0.

Task

Write a program that reads a string of length nn and qq operations and executes these operations.

Input data

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

Output data

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

Constraints and clarifications

  • The string is indexed from 11.
  • 1n,q200 0001 \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 1n,q10 0001 \leq n, q \leq 10 \ 000; The string and operations are random.
2 30 1n,q200 0001 \leq n, q \leq 200 \ 000; The operations are only of type 22.
3 50 No additional constraints

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

Log in or sign up to be able to send submissions!