Description

One day, Youmu was practicing swordsmanship. There was an extremely long wooden rod on the ground, and Youmu cut it into $n$ equal segments. Now this rod can be regarded as composed of three kinds of small segments: the middle $n - 2$ segments are stumps cut on both sides, denoted by X; the leftmost segment and the rightmost segment each have a rounded end, denoted by ( and ) respectively.

After eating her fill and feeling bored, Yuyuko decided to play a prank on Youmu. She brought many small wooden segments of these three types to replace part of the $n$ segments Youmu had cut, and then asked Youmu some questions.

These operations are described as follows:

• 1 x C Replace the $x$-th small segment with type $C$, where $C$ is one of X, (, ).
• 2 l r Query how many complete rods are in the interval $[l, r]$ (inclusive).

A complete rod must have ( on the left end and ) on the right end, and between them there may be zero or more X only.

Although Youmu can count the answers to these questions, Yuyuko thinks she answers too slowly. Can you teach Youmu a faster method?

Input Format

The first line contains two integers $n, m$, representing that there are $n$ segments and $m$ operations.

The initial shape of the rod is (XXXX...XXXX).

Then follow $m$ lines, each describing one operation in one of the following forms, separated by spaces:

• Type 1: 1 x C — an integer $x$ and a character $C$.
• Type 2: 2 l r — two integers $l, r$.

The meanings are as described above.

Output Format

For each type 2 operation, output one line with one integer, representing the answer to that query.

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

1
0
1

Hint

For 30% of the testdata, $2 \leq n, m \leq 1 \times 10^3$.

For 100% of the testdata, $2 \leq n, m \leq 2 \times 10^5$.

by-orangebird.

Translated by ChatGPT 5