Abacus

Time limit1sMemory limit512 MB

Summary

Given an abacus with R rows of beads, compute the state after adding 1 exactly N times, where each increment moves one bead and resets rows below.

Level: Medium4 of 10
Topics: Math, Simulation, Implementation, Number theory
Solved: No attempts yet

Problem

Figure 2. This is what Simon's abacus (with $R=4$ ) could look like before he started eating the beads. Back then it was easy to translate the position into a decimal number.

Little Simon got an abacus as a present. The abacus has $R$ rows, and each row originally held 9 beads, so that one could represent $R$ -digit decimal numbers: one digit per row. If a row had $X$ beads on the left side, then a gap, and the remaining beads on the right side, the row represented the digit X.

Unfortunately Simon thought the beads on the frame looked very tasty and simply ate some of them. Still, at least one bead remains on every row.

Simon quickly learned to count on his new abacus. He represents the number where all beads are on the right side as the number 0, and then adds 1 just as he would on an ordinary abacus, by moving one bead from right to left on the lowest row that still has any bead on the right side (let us call it the moving row) and moving all beads on the rows below the moving row to the right side (unless the moving row is the bottom row). If 1 is added when all beads on all rows are already on the left side (so that there is no moving row), the result is 0.

Figure 3. Some examples of how Simon adds 1 on the abacus shown in the first two examples. The double arrow marks the "moving row" for each addition.

Simon is counting the grains of sand in his sandbox and would need help writing a program that, given a starting position on the abacus, computes what the abacus looks like after he has added 1 $N$ times.

Input

The first line contains the number of rows $R$ . Then follow $R$ lines with two integers each, the number of beads on the left and on the right of each row (from top to bottom). Finally there is a line with the positive integer $N$ .

Output

The program shall print $R$ lines with two numbers on each line: the number of beads on the left and on the right of each row after the additions.

Constraints

$R\le 12$
$N\le 10^{12}$

Examples4

Example 1
Input
```
4
0 4
0 2
1 2
0 1
6
```
Expected output
```
0 4
1 1
0 3
0 1
```
Example 2
Input
```
4
2 2
2 0
2 1
1 0
85
```
Expected output
```
1 3
1 1
1 2
0 1
```
Example 3
Input
```
4
1 1
0 2
2 0
1 1
37
```
Expected output
```
2 0
1 1
2 0
2 0
```

Example 4

Input

Expected output