29262번 - 하이퍼 주사위 굴리기

문제

\(N\)차원 유클리드 공간에 \(N\)차원 데카르트 좌표계가 정의되어 있다. \(N\)차원 데카르트 좌표계에서는 원점을 지나는 좌표축 \(N\)개가 존재하는데, 이 문제에서는 \(i\)번째 좌표축을 \(x_i\)축, \(x_i\)값이 커지는 좌표축의 방향을 \(+x_i\)방향, \(x_i\)값이 작아지는 좌표축의 방향을 \(-x_i\)방향이라고 정의한다.

현재 이 공간에 \(x_1 \leq -\tfrac{1}{2}\)인 모든 공간이 채워져 있고, 편의상 \(x_1 < -\tfrac{1}{2}\)인 부분을 바닥, 그리고 \(x_1 = -\tfrac{1}{2}\)를 바닥면으로 정의한다. 또한, \(1 \times 1 \times \cdots \times 1\) 크기의 주사위가 원점을 중심으로 놓여 있다. 즉, 주사위가 현재 차지하고 있는 공간은 \( [-\tfrac{1}{2},\tfrac{1}{2}] \times [-\tfrac{1}{2},\tfrac{1}{2}] \times \cdots \times [-\tfrac{1}{2},\tfrac{1}{2}]\)가 된다. 이 주사위는 \(N-1\)차원 도형으로 정의되는 \(2N\)개의 면을 가지고 있으며, \(1 \leq i \leq N\)인 정수 \(i\)에 대하여 \(+x_i\)방향 면에는 \(2N+1-i\)가, \(-x_i\)방향 면에는 \(i\)가 적혀있다.

총 \(M\)개의 명령이 주어질 때, 모든 명령을 순서대로 수행한 후 원점과 주사위 중심 간 유클리드 거리의 제곱을 출력하시오. 각 명령은 \(1\) 이상 \(2N\) 이하의 정수 \(v\)로 주어지며, 다음의 행동을 해야 하는 것을 의미한다.

• 현재 \(v\)가 적혀있는 주사위의 면이 바닥면에 오도록 주사위를 굴린다. 주사위를 굴리기 전, \(v\)가 \(-x_1\)방향 혹은 \(+x_1\)방향 주사위의 면에 적혀있지 않음이 보장된다.

유클리드 거리 및 주사위를 굴린다는 행동 등의 엄밀한 정의는 아래의 노트를 참고한다.

입력

첫 번째 줄에 두 양의 정수 $N,ドル $M$이 주어진다. $N$은 주사위의 차원 수이며, $M$은 주사위를 굴리는 명령의 수이다. (3ドル \leq N \leq 10^9,ドル 1ドル \leq M \leq 500,000円$)

다음 줄에 $M$개의 양의 정수 $v_{1}, v_{2}, \cdots, v_{M}$이 주어진다. $v_{i}$는 $i$ 번째 명령에 해당하는 정수이다. (1ドル \leq v_{i} \leq 2N$)

출력

첫 번째 줄에 모든 명령을 순서대로 수행하고 나서 원점과 주사위 중심 간 유클리드 거리의 제곱을 정수로 출력한다.

제한

노트

\(N\)차원 유클리드 공간에 정의된 두 점 \((x_1,x_2,\cdots, x_N)\), \((y_1,y_2,\cdots,y_N)\) 간 유클리드 거리의 제곱은 다음과 같다.

\[(x_1-y_1)^2 + (x_2-y_2)^2 + \cdots + (x_N - y_N)^2\]

주사위를 굴린다는 행동의 엄밀한 정의는 다음과 같다. \(v\)가 적힌 주사위의 면을 \(V\), 바닥과 붙어있는 주사위의 면을 \(W\)라고 정의하자. 이때, \(V\)와 \(W\)의 교집합 \(Z\)는 \(N-2\)차원 도형으로 정의된다. \(V\)가 바닥면에 오도록 주사위를 굴린다는 것은, 주사위를 \(Z\)를 기준으로 시계방향 또는 반시계방향으로 \(90\)도 회전시킨다는 것을 의미한다. 이때 주사위를 회전시키는 방향은 주사위가 바닥으로 들어가지 않는 방향이어야 한다.

주사위를 \(N-2\)차원 도형 \(Z\)를 기준으로 \(\theta\)도 회전시킨다는 것은 다음을 의미한다. \(x\)를 주사위 내부의 임의의 점이라고 정의하자. 그리고 \(x\)를 지나면서 \(Z\)와 선형 독립인 공간을 \(A\)라고 정의하자. \(Z\)가 \(N-2\)차원 도형이기 때문에, \(A\)는 항상 \(2\)차원 무한평면으로 표현된다. \(A\)와 \(Z\)의 교집합을 \(y\)라고 정의하자. \(A\)와 \(Z\)가 선형독립이기 때문에, \(y\)는 단 한 개의 점으로 표현된다.

평면 \(A\)안에서 \(x\)를 \(y\) 기준으로 \(\theta\)도 회전시킨다. 이 행동을 모든 \(x\)에 대하여 수행하는 것을 주사위를 \(\theta\)도 회전시키는 것으로 정의한다.