P3797 妖梦斩木棒

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

有一天，妖梦正在练习剑术。地面上摆放着一根非常长的木棒，妖梦把它切成了等长的 $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$。含义见题目描述。

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

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