题目内容

一条报文写成字符串 $w$，一共 $m$ 个字符。每个字符要么是开符 [，要么是合符 ]。

调度一共做 $t$ 次动作，只有下面两类。

第一类给出两端 $a,b$，把第 $a$ 个到第 $b$ 个字符全部换成对面：[ 换成 ]，] 换成 [。

第二类给出两端 $a,b$，问当前这一段是否配平。

配平的含义：从左往右扫描这一段，遇到 [ 就让计数加 $1$，遇到 ] 就让计数减 $1$。扫描途中计数始终不能小于 $0$，扫到末尾时计数必须回到 $0$。

例如 []、[[]]、[][] 都配平；][、[[]、][][ 都不配平。

输入描述

首行一个正整数 $m$。

第二行一个正整数 $t$。满足 $1\le m,t\le 2\times 10^{5}$。

第三行给出报文 $w$，长度恰好为 $m$，只含 [ 与 ]。

随后 $t$ 行，每行三个整数 $op,a,b$。

• $op=1$：把第 $a$ 个到第 $b$ 个字符换成对面。
• $op=2$：询问第 $a$ 个到第 $b$ 个字符现在是否配平。

位置从 $1$ 数起，且 $1\le a\le b\le m$。

输出描述

每个 $op=2$ 单独占一行：配平写出 $1$，否则写出 $0$。

$op=1$ 没有任何输出。

样例1

输入

6
4
[[][]]
2 1 6
1 1 2
2 1 6
2 4 5

输出

1
0
1

说明

• 整段 [[][]] 的计数依次是 $1,2,1,2,1,0$，配平，输出 $1$。
• 把前两个开符换成合符后，报文变成 ]]][]]，一开头计数就是 $-1$，输出 $0$。
• 第 $4$ 到第 $5$ 个仍是 []，输出 $1$。

样例2

输入

8
5
][[]][][
2 2 7
1 1 1
2 1 8
1 8 8
2 1 8

输出

1
0
1

说明

• 第 $2$ 到第 $7$ 个是 [[]][]，计数依次是 $1,2,1,0,1,0$，配平，输出 $1$。
• 只把开头的合符换成开符后，整段是 [[[]][][，扫完计数为 $2$，输出 $0$。
• 再把末尾的开符换成合符，整段变成 [[[]][]]，计数依次是 $1,2,3,2,1,2,1,0$，配平，输出 $1$。