Reporting Documents

Each citizen of the ICPC Kingdom must always carry the $N$ documents issued by the kingdom, numbered from $1$ to $N$. Guards often ask random citizens for their documents during patrols.

Adrian is a citizen of the ICPC Kingdom and also carries these documents. Through negligence, some of them may be missing. The status of his documents is given by a string $B$ of length $N$, where $B_i = 1$ if document $i$ is on his hand and $B_i = 0$ if it is missing.

Each of the next $Q$ days, exactly one of the following happens.

• $1$ $x$: Adrian finds his missing document $x$, so $B_x$ becomes $1$. It is guaranteed that $B_x = 0$ right before this event.
• $2$ $x$: Adrian loses document $x$, so $B_x$ becomes $0$. It is guaranteed that $B_x = 1$ right before this event.
• $3$ $x$ $k$: A guard asks Adrian for documents $x + k \cdot i$ for every integer $i \ge 0$ such that $1 \le x + k \cdot i \le N$, where $x \le k$. Adrian pays a fine of 1 coin for each requested document he cannot provide at that moment.

For each event of type $3$, count the total fine Adrian must pay.

The first line contains an integer $N$ ($1 \le N \le 200000$), the number of documents. The second line contains a string $B$ of length $N$, where the $i$-th character is $B_i$ ($B_i \in \{0, 1\}$), the initial status of document $i$.

The third line contains an integer $Q$ ($1 \le Q \le 200000$), the number of days. Each of the next $Q$ lines describes one event and begins with an integer $t$ ($t \in \{1, 2, 3\}$). If $t = 1$ or $t = 2$, the line contains one more integer $x$ ($1 \le x \le N$). If $t = 3$, the line contains two more integers $x$ and $k$ ($1 \le x \le k \le N$). There is at least one event of type $3$.

For each event of type $3$, print the number of coins Adrian must pay on its own line.