N개의 구역이 원형으로 배열되어 있고, 각 구역은 활성 또는 비활성 상태를 가진다.

세 종류의 쿼리를 처리하라: 1 i는 i번 구역의 상태를 전환하고, 2 x는 현재 위치를 x만큼 시계 방향으로 이동시키며, 3은 현재 위치에서 시계 방향으로 가장 가까운 활성 구역까지의 이동 거리를 출력한다.

활성 구역이 없으면 -1을 출력한다.

입력

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

둘째 줄에 길이 \(N\)의 수열 \(A\)가 주어진다. \(A_i\)가 \(1\)이면 i번째 구역이 활성 상태이고, \(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