34816번 - 짝수 길이의 짝수 합

문제

길이가 $N$이고 0ドル$과 1ドル$로만 이루어진 문자열이 입력으로 주어진다. 이때, 다음과 같은 쿼리를 수행해 보자.

• 1ドル ,円 i$: $i$번째 문자를 반전한다. 즉, $i$번째 문자가 0ドル$이면 1ドル$로 바꾸고, 그렇지 않으면 0ドル$으로 바꾼다. (1ドル \le i \le N$)
• 2ドル ,円 x ,円 y$: 다음 조건을 모두 만족하는 정수 $l, r$이 있다면 YES, 그렇지 않으면 NO를 출력한다. (1ドル \le x \le y \le N$)
  • $x \le l \le r \le y$
  • $l$번째 문자부터 $r$번째 문자까지의 부분 문자열의 길이, 즉 $r-l+1$은 짝수이다.
  • $l$번째 문자부터 $r$번째 문자까지의 부분 문자열에 있는 $r-l+1$개의 숫자의 합, 즉 숫자 1ドル$의 개수는 짝수이다. 단, 0ドル$도 짝수로 간주한다.

쿼리가 누적해서 수행됨에 유의하여라.

입력

첫째 줄에 정수 $N$과 $Q$가 공백으로 구분되어 주어진다. $(1 \le N, Q \le 300,円 000)$

둘째 줄에 0ドル$과 1ドル$로만 이루어져 있는, 길이가 $N$인 문자열이 주어진다.

셋째 줄부터 $Q$개의 줄에 걸쳐 쿼리가 주어진다.

1ドル$번 쿼리의 경우, 1ドル ,円 i$의 형식으로 주어진다. $(1 \le i \le N)$

2ドル$번 쿼리의 경우, 2ドル ,円 x ,円 y$의 형식으로 주어진다. $(1 \le x \le y \le N)$

2ドル$번 쿼리가 한 개 이상 주어짐이 보장된다.

쿼리에서 입력으로 주어지는 모든 수는 정수이다.

출력

2ドル$번 쿼리가 주어질 때마다, 쿼리의 답을 한 줄에 하나씩 순서대로 출력한다.

제한

노트

어떤 문자열의 부분 문자열은 그 문자열의 비어 있지 않은 연속된 부분으로 정의한다.