Count Complete Wooden Sticks

One day, Youmu was practicing her swordsmanship. On the ground lay a very long wooden stick. She cut it into n equal pieces. The stick now can be seen as composed of three types of segments: the two end segments have a circular head and are denoted by ( for the left end and ) for the right end, while the middle n-2 segments are cut on both ends and are denoted by X.

After her meal, Youmu’s friend, Yuyuko, decided to play a prank on her. Yuyuko brought many small wooden stick segments of these three types and replaced some of the segments Youmu had cut. Then she asked Youmu some questions. The operations are described as follows:

1. 1 x C: Replace the segment at position x with character C. Here, C is one of X, (, or ).
2. 2 l r: Query, in the interval from segment l to segment r (inclusive), how many complete wooden sticks exist.

A complete wooden stick is defined as a contiguous subsequence whose left end is (, right end is ), and all intermediate segments (if any) are X. In other words, a valid complete stick matches the pattern $$(X^*) )$$

(Here, X^* denotes zero or more occurrences of X.)

Your task is to help Youmu answer Yuyuko's queries quickly.

inputFormat

The first line contains two integers n and q denoting the number of segments and the number of operations, respectively.

The second line contains a string of length n which represents the initial configuration. The string consists only of characters (, ), and X. The initial configuration is always a complete wooden stick: the first character is (, the last character is ), and every character in between is X.

Each of the next q lines represents an operation in one of the following formats:

• 1 x C — update the segment at position x to character C (which is guaranteed to be one of (, ), or X).
• 2 l r — query the number of complete wooden sticks in the interval from l to r (inclusive).

Note: The positions are 1-indexed.

outputFormat

For each query operation (of type 2), output a single integer, the number of complete wooden sticks in the specified interval.

sample

3 3
(X)
2 1 3
1 2 )
2 1 3

1
1