시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB (추가 메모리 없음)151584744.762%

문제

도현이는 홍익 투어리스트가 되어 홍익대학교를 견학하려고 한다. 홍익대학교는 $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$번 쿼리가 주어질 때마다 해당 쿼리의 값을 출력한다.

예제 입력 1

5 7
0 1 0 0 1
3
1 2
3
2 9
3
1 5
3

예제 출력 1

1
4
0
-1

출처

University > 홍익대학교 > 2021 홍익대학교 프로그래밍 경진대회 G번