Description

pupil found that for a decimal number, no matter how its digits are rearranged, it does not affect whether it is a multiple of $3$. He wants to study whether there is a similar property for binary.

So he generated a binary string of length $n$, and hopes that for a subinterval of this binary string, you can find how many position-distinct contiguous substrings satisfy that after rearrangement (leading zeros are allowed), the result is a multiple of $3$.

Two position-distinct subintervals are defined as having different starting positions or different ending positions.

Since he wants to try as many cases as possible, he will sometimes modify one position in the string and will make multiple queries.

Input Format

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

The second line contains $n$ space-separated integers, each being $0$ or $1$, representing the binary string.

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

Each of the following $m$ lines is either 1 i, meaning pupil toggles the $i$-th position of the string ($0$ becomes $1$ or $1$ becomes $0$), or 2 l r, meaning pupil queries the subinterval $[l,r]$.

The string is $1$-indexed.

Output Format

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

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

2
3

Hint

Sample Explanation:

• For the first query, the interval $[2,2]$ contains 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$. All other intervals cannot be rearranged into a multiple of $3$.
• For the second query, all three intervals can be rearranged into multiples of $3$ (note that $00$ is also valid).

Constraints:

• For $20\%$ of the testdata, $1 \leq n,m \leq 100$.
• For $50\%$ of the testdata, $1 \leq n,m \leq 5000$.
• For $100\%$ of the testdata, $1 \leq n,m \leq 100000$, $l \leq r$.

Translated by ChatGPT 5