Crazy Dice Rolling Game

In this problem, you are given a special die and asked to simulate a dropping game. The die has unusual rolling behavior. When dropped from a fixed position, the die lands on a cell in an infinite grid (the playing plane). Initially, every cell has a "stack height" of 0. When a die is dropped on a cell, it lands on top of the current stack in that cell (its new level is h+1 if the cell’s current height is h). Each die has an orientation. The initial orientation for every dropped die is:

• Top = 6
• Bottom = 1
• North (front) = 4
• South (back) = 3
• East = 2
• West = 5

After landing, the top die on a cell may be unstable. A die is unstable if it is "overhanging" its support. More precisely, let the current cell have height L (i.e. the die is at level L) and let an adjacent cell in one of the four cardinal directions (North, East, South, West) have height h (if no die has ever been dropped in that cell, consider h = 0). The die on the current cell will roll toward a neighbor if both:

1. The die would actually fall. That is, the condition \[ L > h+1 \] holds.
2. The die is allowed to roll in that direction. This special die can only roll in a direction whose lateral face has one of the numbers \(4, 5, 6\). Note that a die has four lateral faces. (For example, using the initial orientation the lateral faces are: North=4, East=2, South=3, West=5.)

If there are several allowed directions in which a roll would cause a fall, the die always rolls in the direction corresponding to the largest lateral face number (breaking ties arbitrarily).

The rolling process works as follows. When the die rolls, it rotates exactly \(90^\circ\) about the corresponding edge and falls into the adjacent cell. Its orientation changes accordingly. The update formulas for a roll are as follows (assume the current orientation is given by the six faces):

• Roll North: \[ \begin{aligned} {\rm top}' &= {\rm north},\\ {\rm bottom}' &= {\rm south},\\ {\rm north}' &= {\rm bottom},\\ {\rm south}' &= {\rm top},\\ {\rm east}' &= {\rm east},\\ {\rm west}' &= {\rm west} \end{aligned} \]
• Roll East: \[ \begin{aligned} {\rm top}' &= {\rm east},\\ {\rm bottom}' &= {\rm west},\\ {\rm east}' &= {\rm bottom},\\ {\rm west}' &= {\rm top},\\ {\rm north}' &= {\rm north},\\ {\rm south}' &= {\rm south} \end{aligned} \]
• Roll South: \[ \begin{aligned} {\rm top}' &= {\rm south},\\ {\rm bottom}' &= {\rm north},\\ {\rm south}' &= {\rm bottom},\\ {\rm north}' &= {\rm top},\\ {\rm east}' &= {\rm east},\\ {\rm west}' &= {\rm west} \end{aligned} \]
• Roll West: \[ \begin{aligned} {\rm top}' &= {\rm west},\\ {\rm bottom}' &= {\rm east},\\ {\rm west}' &= {\rm bottom},\\ {\rm east}' &= {\rm top},\\ {\rm north}' &= {\rm north},\\ {\rm south}' &= {\rm south} \end{aligned} \]

The die continues rolling until no allowed move exists (i.e. for every adjacent cell \(v\) in a direction \(d\) for which the current lateral face value \(x\) is in \(\{4,5,6\}\), the condition \(L > h+1\) fails). At that point the die stays in its cell and becomes part of the stack there.

Initially the board is empty. Then \(n\) dice are dropped one by one. Each new die is dropped at cell \((0,0)\) (and its initial orientation is reset as given above) and goes through the process described. After all \(n\) dice have been processed, from a bird’s–eye view only the top die in each cell is visible. Your task is to count, for each face value from 1 to 6, how many times it appears as the top face.

Input format: A single integer \(n\) representing the number of dice dropped.

Output format: Output 6 integers separated by spaces: the counts for faces 1, 2, 3, 4, 5, and 6, respectively.

Note: You may assume that \(n\) is small enough so that a simulation approach (processing dice one by one) will run in time.

inputFormat

The input consists of a single integer \(n\) (e.g. \(1 \le n \le 1000\)).

Example:
4

outputFormat

Output 6 space-separated integers in one line. They represent the number of times the faces 1, 2, 3, 4, 5, 6 appear as the top face in the final configuration.

Example:
For the sample input below, the output is:

0 1 0 1 0 1

(Explanation: For \(n = 4\), after simulating the dropping process, suppose the final top faces on the occupied cells are 6 at (0,0), 2 at (-1,0) and 4 at (0,1); hence, the counts of faces 1 to 6 are: 0, 1, 0, 1, 0, 1.)

sample

1

0 0 0 0 0 1