매직볼은 N * N 크기의 2차원 평면의 나라 플레인 왕국이

왕국의 방어를 위하여 제작중인 특별한 물질이다.

플레인 왕국의 과학자 커미가 매직볼을 시험하고 있다.

매직볼은 커미의 명령에 따라 분할, 이동, 합쳐짐을 반복한다.

커미는 M개의 매직볼을 지정한 위치에 떨어뜨릴 예정이다.

i번 매직볼이 떨어진 위치는 (ri, ci), 질량은 mi, 방향은 di, 속력은 si이다.

위치 (r, c)는 r행 c열을 의미한다.

플래인 왕국은 행과 열로 나뉘어진 grid(격자) 형태로 1 ~ N번까지 번호가 매겨져 있다.

또한 시작쪽의 모서리와 끝쪽 모서리는 서로 연결되어 있다.

다시 말해서 1번 행은 N번 행과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다는 의미이다.

커미의 명령이 내려지면 매직볼은 아래 그림과 같이

인접한 8개의 방향 중에 일부 방향으로 si 속력으로 이동한다.

커미가 모든 매직볼에게 이동을 명령하면 다음과 같은 일이 일어난다.

1. 모든 매직볼이 자신의 방향 di로 속력 si칸 만큼 이동한다.

* 이동하는 중에는 같은 칸에 여러 개의 매직볼이 있을 수도 있지만 목적지가

아니라면 충돌하거나 멈추지 않고 지나쳐 간다.

2. 이동이 모두 끝난 뒤, 2개 이상의 매직볼이 있는 칸에서는 다음과 같은 일이 일어난다.

1) 같은 칸에 있는 매직볼은 모두 하나로 합쳐진다.

2) 매직볼은 4개의 매직볼로 나누어진다.

3) 각기 나누어진 매직볼의 질량, 속력, 방향은 다음과 같이 바뀐다.

(1) 질량은 ⌊(합쳐진 매직볼 질량의 합)/5⌋이다.

(2) 속력은 ⌊(합쳐진 매직볼 속력의 합)/(합쳐진 매직볼의 개수)⌋이다.

(3) 합쳐지는 매직볼의 방향이 모두 홀수이거나 모두 짝수이면,

방향은 0, 2, 4, 6이 되고, 그렇지 않으면 1, 3, 5, 7이 된다.

4) 질량이 0인 매직볼은 소멸되어 없어진다.

커미가 이동을 K번 명령한 후, 남아있는 매직볼 질량의 합을 구해보자.

커미의 매직볼 timer 1s memory 256MB

커미의 매직볼 1s 256MB