로스웰의 UFO 정육면체

밥(Bob)과 앨리스(Alice)는 미국 뉴멕시코주 로스웰에 산다. 두 사람은 미확인 비행 물체(UFO)가 남기고 간 이상한 물건을 주웠다. 이 물건은 아주 작은 구멍이 촘촘히 뚫린, 한 변의 길이가 $s$ ($1 \le s \le 2^{15}$)인 커다란 정육면체이며, 각 면마다 다르게 빛난다. 정육면체 내부의 어떤 장치가 햇빛을 반사하여, 각 면의 구멍 중 일부에서만 빛이 새어 나온다.

관찰 결과, 정육면체 안에는 서로 다른 정수 좌표에 놓인 양면 거울이 $n$ ($1 \le n \le 10^6$)개 들어 있다. 각 거울은 아주 작으며(지름이 1 단위 미만), $45^\circ$ 기울어져 아래 여섯 가지 방향($0$부터 $5$) 중 하나로 놓여 있다. 각 방향은 두 축을 짝지어 광선을 $90^\circ$ 꺾으며, 짝지어지지 않은 나머지 한 축 방향으로 진행하는 광선(즉 진행 방향이 거울 평면 안에 있는 광선)은 거울과 상호작용하지 않고 그대로 통과한다.

정육면체는 $0 \le x, y, z \le s$ 영역을 차지한다. 태양은 위쪽에 있으므로 빛은 $+y$ 방향(아래쪽)으로 들어온다. 윗면($y = 0$)의 모든 정수 좌표, 즉 $0 \le x \le s$이고 $0 \le z \le s$인 각 점 $(x, 0, z)$마다 빛 한 단위가 $+y$ 방향으로 정육면체에 들어온다. 따라서 들어오는 광선은 모두 $(s+1)^2$개이다. 각 광선은 직진하다가 상호작용하는 거울을 만나면 $90^\circ$ 꺾이고, 더 이상 거울을 만나지 않으면 여섯 면 중 하나를 통해 밖으로 나간다.

여섯 면의 번호 $0$부터 $5$는 다음과 같다.

각 면에 대해, 그 면으로 나가는 광선의 개수와, 그 광선들이 나가기까지 꺾인 횟수의 총합을 구하여라.

첫째 줄에 정육면체의 크기 $s$가 주어진다.

둘째 줄에 거울의 개수 $n$이 주어진다.

이어지는 $n$개의 줄에는 각 거울의 정보가 네 정수 $x$, $y$, $z$, $o$로 주어진다. $(x, y, z)$는 거울의 좌표($0 \le x, y, z \le s$)이고 $o$는 그 방향($0 \le o \le 5$)이다. 어떤 두 거울도 같은 좌표에 있지 않다.

출력은 12개의 정수이며 한 줄에 하나씩 출력한다. 이 정수들은 두 개씩 여섯 묶음을 이루고, 각 묶음은 면 번호 $0, 1, 2, 3, 4, 5$ 순서대로 각 면에 대응한다. 각 묶음에서 첫 번째 정수는 그 면으로 나간 광선의 개수이고, 두 번째 정수는 그 광선들이 꺾인 횟수의 총합이다.