봄 맞이 축제에 N(1 \le N \le 2 \cdot 10^5 ) 마리의 곰들은 둥글게 서 있으면서 서로 순서를 바꾸는 새로운 춤을 만들었다.

구체적으로, N개의 자리가 원형으로 있으며 0번부터 N-1번까지 순서대로 번호 매겨져 있으며 N-1번 다음은 0번으로 이어지는 원형이다.

곰들 역시 번호가 매겨져 있으며 초기에는 i번째 자리에는 i번 곰이 서 있다.

여기에서 K개의 특정 자리(0=A_1 \lt A_2 \lt \ldots \lt A_K \lt N)는 "댄서 곰의 자리"로, 이 자리에 있는 곰은 다른 곳으로 움직인다. (1 \le K \le N)

신이 난 곰들은 춤을 추는 매 분마다 2가지 동작을 한다.

먼저, "댄서 곰의 자리"에 있는 곰이 회전 이동을 한다. 회전 이동의 과정은 다음과 같다.
A_1 자리에 있는 곰은 A_2 자리로 이동하고 A_2 자리에 있는 곰은 A_3 자리로 이동하는 식이며 최종적으로 A_K자리에 있는 곰은 A_1 자리로 이동한다.

(이러한 K번의 동작은 모두 동시에 발생하므로 회전 이동이 완료된 후에도 모든 "댄서 곰의 자리"에는 정확히 한 마리의 곰이 있다.)

다음 동작으로 "댄서 곰의 자리"를 변경한다. A_1은 A_1+1이 되고, A_2는 A_2+1이 된다. (A_i=N-1인 경우 A_i는 0이 된다.)

T분의 춤이 끝난 후 곰의 순서를 계산하라. (1 \le T \le 10^9)

댄서 곰 (Rotate and Shift) timer 4s memory 32MB

댄서 곰 (Rotate and Shift) 4s 32MB