하이퍼 주사위 굴리기

$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$도 회전시키는 것으로 정의한다.