23326번 - 홍익 투어리스트

도현이는 홍익 투어리스트가 되어 홍익대학교를 견학하려고 한다. 홍익대학교는 $N$개의 구역이 원형으로 배치된 모습이다. $1$번 구역에서 시계 방향으로 각각 $2$번, ... , $N$번 구역이 존재하고, $N$번 구역에서 시계 방향으로 한 칸 더 갈 경우 $1$번 구역으로 도착한다. 

홍익대학교에는 명소가 존재한다. 도현이는 알찬 투어를 위해 명소만을 방문하려 한다. 도현이는 $1$번 구역에 서있다.

도현이를 위해 다음과 같은 쿼리를 수행하는 프로그램을 작성해보자.

• $1$ $i$ : $i$번 구역이 명소가 아니었다면 명소로 지정되고, 명소였다면 지정이 풀리게 된다. ($1 \leq i \leq N$)
• $2$ $x$ : 도현이가 시계방향으로 $x$만큼 이동한다. ($1 \leq x \leq 10^9$)
• $3$ : 도현이가 명소에 도달하기 위해 시계방향으로 최소 몇 칸 움직여야 하는 지 출력한다. 명소가 존재하지 않는 경우 $-1$을 출력한다.

첫째 줄에 구역의 개수 $N$ ($1 \leq N \leq 500\,000$)과 쿼리의 개수 $Q$ ($1 \leq Q \leq 100\,000$)가 정수로 주어진다.

둘째 줄에 길이 $N$의 수열 $A$가 주어진다. $i$번째 구역이 명소라면 $A_i$는 $1$, 그렇지 않다면 $0$이다.

셋째 줄부터 $Q$줄에 걸쳐 본문의 쿼리가 주어진다. $3$번 쿼리는 하나 이상 존재한다.

$3$번 쿼리가 주어질 때마다 해당 쿼리의 값을 출력한다.