You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

妖梦是住在白玉楼的半人半灵，拥有使用剑术程度的能力。

题目描述

有一天，妖梦正在练习剑术。地面上摆放着一根非常长的木棒，妖梦把它切成了等长的 $n$ 段。 现在这根木棒可以看作由三种小段构成：中间的 $n - 2$ 段都是左右都被切断的断头，我们记作 X；最左边的一段和最右边的一段各有一个圆头，分别记作 ( 和 )。

幽幽子吃饱后闲来无事，决定戏弄一下妖梦。她拿来了许多这样的三种小段木棒，来替换掉妖梦切下来的 $n$ 段中的一部分，然后问妖梦一些问题。

这些操作可以这样描述：

• 1 x C 将第 $x$ 个小段的木棒替换成 $C$ 型，$C$ 只会是 X, (, ) 中的一种

• 2 l r 询问在区间 $[l, r]$ 中（包含两端），有多少个完整的木棒。

完整的木棒左右两端必须分别为 ( 和 )，并且中间要么什么都没有，要么只能有 X。

虽然妖梦能够数清楚这些问题，但幽幽子觉得她回答得太慢了，你能教给妖梦一个更快的办法吗？

输入格式

第一行包含两个整数 $n, m$，分别表示共有 $n$ 段木棒，以及有 $m$ 次操作。

木棒的初始形状为 (XXXX...XXXX)

接下来 $m$ 行，每行三个整数/字符，用空格隔开。

第一个整数为 $1$ 或 $2$，表示操作的类型，若类型为 $1$，则接下来一个整数 $x$，一个字符 $C$。若类型为 $2$，接下来两个整数 $l,r$。含义见题目描述。

输出格式

对于每一个操作二，输出一行一个整数，表示该询问的答案。

4 4
2 1 4
2 2 4
1 2 (
2 2 4

1
0
1

提示

对于 $30\%$ 的数据，$2 \leq n,m \leq 1 \times 10^3$。

对于 $100\%$ 的数据，$2 \leq n,m \leq 2 \times 10^5$。

by-orangebird。