pupil discovered that for a decimal number, no matter how you rearrange its digits, it does not affect whether it is a multiple of 3. He wants to study whether a similar property exists for binary numbers. He generated a binary string of length $n$ and hopes that for a sub-interval of this binary string, you can calculate how many contiguous substrings with different positions can be rearranged (including leading zeros) to form a multiple of 3. Two sub-intervals are considered different if they have different starting positions or different ending positions. Since he wants to try as many cases as possible, he sometimes modifies a position in the string and performs multiple queries.

Input

The first line contains a positive integer $n$, representing the length of the binary string.

The next line contains $n$ space-separated integers, guaranteed to be either 0 or 1, representing the binary string.

The next line contains an integer $m$, representing the total number of queries and modifications.

Each of the following $m$ lines is either 1 i, indicating that pupil modified the $i$-th position of the string (0 becomes 1 or 1 becomes 0), or 2 l r, indicating that pupil is querying the sub-interval $[l, r]$.

The string is 1-indexed.

Output

For each query, output a single integer on a new line representing the result of the corresponding query.

Examples

Input 1

4
1 0 1 0
3
2 1 3
1 3
2 3 4

Output 1

2
3

Note

For the first query, in the interval $[2, 2]$, there is only the digit 0, which is a multiple of 3. The interval $[1, 3]$ can be rearranged into $011_{(2)} = 3_{(10)}$, which is a multiple of 3. Other intervals cannot be rearranged into a multiple of 3.

For the second query, all three intervals can be rearranged into a multiple of 3 (note that 00 is also valid).

Subtasks

For 20% of the data, $1 \le n, m \le 100$.

For 50% of the data, $1 \le n, m \le 5000$.

For 100% of the data, $1 \le n, m \le 100000$, $l \le r$.