UFO Cubes in Roswell

Time limit2sMemory limit1024 MB

Summary

Given a cube with mirrors at integer points, trace every downward light ray and report how many exit each face and how many deflections they took.

Level: Medium7 of 10
Topics: Simulation, Implementation, Hash map, Geometry
Solved: No attempts yet

Problem

Bob and Alice live in Roswell (New Mexico, USA) and have found a strange object left behind by an Unidentified Flying Object (UFO). It is a large cube of side length $s$ ( $1 \le s \le 2^{15}$ ) pierced with tiny holes, and it shines differently on every face. Some mechanism inside the cube reflects sunlight so that light emerges from some, but not all, of the holes on each face.

The cube contains $n$ ( $1 \le n \le 10^6$ ) double-sided mirrors at distinct integer coordinates. Each mirror is tiny (less than one unit across) and is set at $45^\circ$ in one of the six orientations below (labelled $0$ to $5$ ). Each orientation couples two axes and turns a ray by $90^\circ$ ; a ray travelling along the remaining, unpaired axis (that is, a ray whose direction lies in the mirror's plane) passes straight through without any interaction.

Orientation	Mirror plane	Reflection (rays along the third axis pass straight through)
0	x-y	+x ↔ −y, +y ↔ −x; ±z pass through
1	x-y	+x ↔ +y, −x ↔ −y; ±z pass through
2	y-z	+y ↔ −z, −y ↔ +z; ±x pass through
3	y-z	+y ↔ +z, −y ↔ −z; ±x pass through
4	z-x	+z ↔ −x, −z ↔ +x; ±y pass through
5	z-x	+z ↔ +x, −z ↔ −x; ±y pass through

The cube occupies $0 \le x, y, z \le s$ . The Sun is above the cube, so light enters travelling in the $+y$ direction (downward). One unit of light enters through every integer coordinate of the top face $y = 0$ : at each point $(x, 0, z)$ with $0 \le x \le s$ and $0 \le z \le s$ , moving in the $+y$ direction. There are therefore $(s+1)^2$ incoming rays. Each ray travels in a straight line until it meets a mirror that deflects it ( $90^\circ$ ), and once no further mirror lies ahead it leaves the cube through one of the six faces.

The six faces are numbered $0$ to $5$ as follows.

Face	Plane
0	z = s
1	z = 0
2	x = s
3	x = 0
4	y = s (bottom)
5	y = 0 (top, where the light enters)

For each face, report how many rays leave through it and the total number of deflections those rays underwent.

Input and Output

The first line contains the size $s$ of the cube.

The second line contains the number of mirrors $n$ .

Each of the next $n$ lines describes one mirror with four integers $x$ , $y$ , $z$ , $o$ : the coordinates $(x, y, z)$ of the mirror ( $0 \le x, y, z \le s$ ) and its orientation $o$ ( $0 \le o \le 5$ ). No two mirrors share the same coordinates.

The output consists of 12 integers, one per line. They form six groups of two, one group per face in the order $0, 1, 2, 3, 4, 5$ . In each group the first integer is the number of rays that leave through that face and the second is the total number of times those rays were deflected.

Examples3

Example 1

Input

Expected output

Example 2
Input
```
3
1
1 1 1 0
```
Expected output
```
0
0
0
0
0
0
1
1
15
0
0
0
```
Example 3
Input
```
4
1
2 2 2 3
```
Expected output
```
1
1
0
0
0
0
0
0
24
0
0
0
```