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ドル$번 쿼리가 주어질 때마다 해당 쿼리의 값을 출력한다.

제한

힌트