의자 춤

deterministic 버전의 Musical Chairs1에서는 원형으로 놓인 $n$개의 의자가 있다. 의자는 시계 방향으로 1부터 $n$까지 번호가 매겨져 있다. 처음에 $i$번째 플레이어는 $i$번째 의자에 앉아 있다. 게임 중 게임 마스터는 모든 플레이어에게 동시에 명령을 내린다.

첫 번째 유형의 명령은 각 플레이어를 시계 방향으로 $x$칸 더 이동시킨다. 즉 플레이어는 의자 $i$에서 의자 $i+x$로 이동한다.

두 번째 유형의 명령은 각 플레이어를 의자 $i$에서 의자 $i\cdot x$로 이동시킨다. 두 계산 모두 $n$을 법으로 하며, 나머지가 0이면 의자 $n$에 해당한다.

두 명 이상의 플레이어가 같은 의자로 가려 하면, 시계 방향으로 가장 적게 이동해야 하는 플레이어가 그 자리를 차지한다. 그 의자를 노리던 나머지 플레이어는 게임에서 탈락한다. 그림 C.1은 명령 * 10의 경우를 보여 준다.

그림 C.1: 샘플 입력 1의 네 번째 명령 시점이다. 플레이어 4와 10이 모두 의자 2로 가려 한다. 시계 방향으로 덜 이동하는 플레이어 10이 그 자리를 차지한다.

1원래 게임을 알 필요는 없지만, 대회가 끝난 뒤에 직접 해 볼 수 있다.

첫 줄에 두 정수 $n$과 $q$ ($2\leq n,q\leq5\cdot10^5$)가 주어진다. 각각 의자의 수와 명령의 수이다.

이어지는 $q$개의 줄에는 다음 세 가지 명령 중 하나가 주어진다.

• + x: 의자 $i$에 있는 플레이어가 의자 $i+x$로 이동한다.
• * x: 의자 $i$에 있는 플레이어가 의자 $i\cdot x$로 이동한다.
• ? x: 의자 $x$에 있는 플레이어의 번호를 알려 준다.

모든 $x$는 $1 \leq x \leq n$을 만족한다.

? 명령마다 요청된 의자에 있는 플레이어의 번호를 출력한다. 의자가 비어 있으면 $-1$을 출력한다.