Dice (APCS 2020-07 Intermediate)

There are \(n\) identical-looking dice in a row. Their positions are numbered from \(1\) to \(n\) from left to right.

Every die starts in the same orientation:

• the top face is \(1\) and the bottom face is \(6\);
• the front face is \(4\) and the back face is \(3\);
• the right face is \(2\) and the left face is \(5\).

The following figure illustrates the initial row with three dice. Each die has \(1\) on top, \(4\) at the front, and \(2\) on the right. Red pips are used only to make the movement of the initial top and front faces easier to follow; the number on a face is always determined by its number of pips.

The next figure is the net of the same die. The central red one-pip face is the top, the adjacent red four-pip face is the front, and the two-pip face is on the right. The net also shows the three pairs of opposite faces: \(1\) and \(6\), \(4\) and \(3\), and \(2\) and \(5\).

You must perform \(m\) operations in order. Each operation contains two integers \(a,b\):

1. If \(b>0\), swap the two dice currently at positions \(a\) and \(b\). Their entire orientations move with them.

2. If \(b=-1\), roll the die currently at position \(a\) forward once. After the roll:

   • the new top is the old back;
   • the new front is the old top;
   • the new bottom is the old front;
   • the new back is the old bottom.

   In the following figure, the left die is in the initial orientation and the right die shows the orientation after one forward roll. The old back face \(3\) moves to the top, the old top face \(1\) moves to the front, and the right face \(2\) stays in place.

   

3. If \(b=-2\), roll the die currently at position \(a\) to the right once. After the roll:

   • the new top is the old left;
   • the new right is the old top;
   • the new bottom is the old right;
   • the new left is the old bottom.

   In the following figure, the left die is in the initial orientation and the right die shows the orientation after one right roll. The old left face \(5\) moves to the top, the old top face \(1\) moves to the right, and the front face \(4\) stays in place.

   

Positions always refer to the current order. For example, after swapping positions \(1\) and \(3\), the next operation on position \(1\) affects the die that was just moved there from position \(3\).

Output the number on the top face at every position after all operations.

Input Format

The first line contains two positive integers \(n,m\): the number of dice and the number of operations.

Each of the next \(m\) lines contains two integers \(a,b\) describing one operation. It is guaranteed that:

• \(1\le a\le n\);
• \(b\) is \(-1\), \(-2\), or a positive integer satisfying \(1\le b\le n\).

Constraints

• \(1\le n\le20\)
• \(1\le m\le100\)
• All input values are integers.

Output Format

Output one line containing \(n\) integers. The \(i\)-th integer is the number on the top face of the die at position \(i\) after all operations. Separate adjacent integers with one space.

Scoring

The two sample cases are judged but worth zero points. There are exactly \(20\) scored test groups, each worth \(5\) points. Every scored group uses the full constraints.

Sample Input 1

1 2
1 -2
1 -1

Sample Output 1

3

Sample Explanation 1

After the die rolls to the right, its top, bottom, front, back, right, and left faces are \(5,2,4,3,1,6\), respectively. It then rolls forward, so its old back face becomes the new top. The final top face is therefore \(3\).

Sample Input 2

3 3
2 -1
3 -2
3 1

Sample Output 2

5 3 1

Sample Explanation 2

The die at position \(2\) has top face \(3\) after rolling forward. The die at position \(3\) has top face \(5\) after rolling to the right. Finally, the dice at positions \(3\) and \(1\) are swapped, so the top faces are \(5,3,1\) from left to right.

Source

APCS July 2020, Implementation Problem 2. The rules are based on ZeroJudge f580, Dice and Yi-Zhe Wang's solution notes. The statement and figure were rewritten and redrawn for AACPOJ.