Hongik Tourist

Dohyeon becomes a Hongik tourist and wants to tour Hongik University. Hongik University consists of $N$ zones arranged in a circle. From zone $1$ clockwise come zones $2$, ..., $N$, and going one more step clockwise from zone $N$ brings you to zone $1$.

Hongik University has landmarks. To make his tour worthwhile, Dohyeon wants to visit only landmarks. Dohyeon is standing at zone $1$.

Write a program that processes the following queries for Dohyeon.

• $1$ $i$ : if zone $i$ is not a landmark, it becomes one; if it is a landmark, its designation is removed. ($1 \leq i \leq N$)
• $2$ $x$ : Dohyeon moves $x$ steps clockwise. ($1 \leq x \leq 10^9$)
• $3$ : print the minimum number of steps Dohyeon must move clockwise to reach a landmark. If no landmark exists, print $-1$.

The first line gives the number of zones $N$ ($1 \leq N \leq 500\,000$) and the number of queries $Q$ ($1 \leq Q \leq 100\,000$) as integers.

The second line gives a sequence $A$ of length $N$. If zone $i$ is a landmark, $A_i$ is $1$; otherwise it is $0$.

From the third line, $Q$ lines give the queries described above. There is at least one query of type $3$.

For each query of type $3$, print its value.