Heavy Burger

Kipa quit his demanding job and opened a hamburger restaurant to try something new. He had baked buns several times while making cakes, but hamburgers were new to him, so he decided to bake buns with a distinct top and bottom and sell the heavy burger, a carbohydrate bomb made by putting a hamburger patty between them.

An example of a heavy burger.

The exact definition of a heavy burger is as follows.

• Placing a bun Y with its inside facing down on top of a bun X with its inside facing up makes a heavy burger. Here X is called the corresponding pair of Y, and Y the corresponding pair of X.
• Placing a heavy burger on top of a bun X with its inside facing up and then placing a bun Y with its inside facing down on top of that makes a heavy burger. Likewise, X is called the corresponding pair of Y, and Y the corresponding pair of X.
• Placing a heavy burger on top of another heavy burger makes a heavy burger.
• Anything that cannot be made by the three rules above is not a heavy burger.

Kipa has N bun-baking machines lined up in a row and operates them at the same time. Each machine bakes exactly one bun. Number them 1 from the leftmost machine to the rightmost. While Kipa runs the shop, one of the following two situations can occur Q times.

• The buns in machines a through b are about to burn, so each of them must be flipped over.
• A customer wants the buns from machines a through b stacked one on top of another. That is, no bun may be flipped while stacking, and the bun from machine a must be at the bottom, the bun from machine (a+1) on top of it, and so on, with the bun from machine b at the top, in that order. Kipa thinks a machine with no bun looks like it has run out of ingredients, so after an order is finished he restores the buns to the up/down orientations they had before that order was taken.

However, when a customer stacks the buns to make a hamburger, some bun may have no corresponding pair and the stack may fail to qualify as a heavy burger. After stacking the buns as each customer ordered, Kipa wants to insert the fewest possible pre-baked buns while keeping the order of the stacked buns, so that the stack becomes a heavy burger. Kipa cares about his customers' health, so for each order he wants to know the height of the heavy burger, that is, the number of buns in it. Write a program that computes this and help Kipa.

The first line gives a positive integer N.

The second line gives a string of length N consisting only of ( and ). For every 1 ≤ i ≤ N, the i-th character being ( means machine i holds a bun with its inside facing up, and ) means it holds a bun with its inside facing down.

The third line gives a positive integer Q.

From the fourth line, Q lines each give three positive integers t, a, b describing a situation. t is at most 2, and 1 ≤ a ≤ b ≤ N.

t = 1 means the buns in machines a through b must be flipped over.

t = 2 means an order has come in to take out the buns from machines a through b and make them into a heavy burger.

For each order (t = 2), print the height of the heavy burger on its own line.

• 1 ≤ N ≤ 1,000,000
• 1 ≤ Q ≤ 300,000