Problem C
Cumbersome Comments

Example of code with two lines commented out.

You are developing a code editor with a feature that keeps track of how many active lines of code you have in file you are currently viewing. Your editor has just added 3 new functionalities that may affect the number of lines of code that are active. The operations are as follows:

• Commenting out one level of a range of selected lines.

• Uncommenting one level of a range of selected lines.

• Deleting a range of selected lines.

Commenting out a range of lines means adding an extra ’//’ at the beginning of each line. This may result in lines having multiple ’//’ at the beginning, meaning they would need to be uncommented multiple times as well before it will be counted as an active line. It is also given that no line of code will ever be commented out more than 15 times at once, and no uncommented line will be attempted to be further uncommented.

With these new features you must be able to quickly deduce how many lines of code are currently active.

Input

The first line contains the integer $N$, which is the number of lines of code initially present in the editor. After that follows a lines with $N$ integers, where the $i$-th integer is the number of times the $i$-th line of code has been commented out. After that follows an integer $T$, the number of operations to be performed. Each of the next $T$ lines contains a single operation, which is one of the following:

• c a b: Comment out one level the lines from $a$ to $b$ (inclusive).

• u a b: Uncomment one level the lines from $a$ to $b$ (inclusive).

• d a b: Delete the lines from $a$ to $b$ (inclusive).

The lines are numbered from $1$ to $N$, and the operations are guaranteed to be valid, $a$ and $b$ are always integers. The range indices are based on the lines currently present in the editor. Deleted lines are of course always inactive, and lines not commented out at all are considered active.

Output

For each completed operation, output the amount of active lines of code.

Limits

• $1 \leq T \leq 250000$

• $1 \leq N \leq 250000$

• Maximum comment level is $15$.

5
0 0 1 1 0
3
c 2 5
d 2 4
u 2 2

1
1
2