주판

시간 제한1초메모리 제한512 MB

요약

R개의 줄로 된 주판에서 1을 N번 더한 뒤의 상태를 구한다. 각 덧셈은 가장 아래쪽의 옮길 수 있는 줄에서 구슬 하나를 왼쪽으로 옮기고 그 아래 줄을 초기화한다.

난이도: 보통10점 중 4점
유형: 수학, 시뮬레이션, 구현, 정수론
정답자: 아직 제출이 없습니다

문제

그림 2. 사이먼이 구슬을 먹기 전의 주판(이 경우 $R=4$ )은 이렇게 생겼을 수 있다. 이때는 배열을 십진수로 옮기기 쉬웠다.

어린 사이먼은 선물로 주판을 받았다. 주판에는 $R$ 개의 줄이 있고, 각 줄에는 처음에 구슬이 9개씩 있어서 $R$ 자리 십진수를 나타낼 수 있었다. 각 줄에서 한 자리씩 담당한다. 어떤 줄의 왼쪽에 구슬이 $X$ 개 있고 그다음 빈틈이 있으며 나머지 구슬이 오른쪽에 있다면, 그 줄은 숫자 X를 나타낸다.

안타깝게도 사이먼은 주판의 구슬이 아주 맛있어 보여서 몇 개를 그냥 먹어 버렸다. 그래도 각 줄에는 구슬이 적어도 하나는 남아 있다.

사이먼은 새 주판으로 셈하는 법을 금방 익혔다. 그는 모든 구슬이 오른쪽에 있는 상태를 숫자 0으로 나타내고, 평범한 주판에서 하던 것처럼 1을 더한다. 오른쪽에 구슬이 남아 있는 가장 아래쪽 줄(이 줄을 이동 줄이라고 하자)에서 구슬 하나를 오른쪽에서 왼쪽으로 옮기고, 이동 줄보다 아래에 있는 모든 줄의 구슬을 오른쪽으로 옮긴다. 이동 줄이 맨 아래 줄이면 아무것도 옮기지 않는다. 모든 줄의 구슬이 이미 왼쪽에 있는 상태에서 1을 더하면, 즉 이동 줄이 없으면 결과는 0이 된다.

그림 3. 처음 두 예제에 나오는 주판에서 사이먼이 1을 더하는 몇 가지 예. 이중 화살표는 각 덧셈에서의 "이동 줄"을 나타낸다.

사이먼은 모래 상자의 모래알을 세고 있는데, 주판의 어떤 시작 상태가 주어졌을 때 1을 $N$ 번 더한 뒤 주판이 어떻게 되는지 계산하는 프로그램을 도와줄 사람이 필요하다.

입력

첫째 줄에 줄의 개수 $R$ 이 주어진다. 이어서 $R$ 개의 줄에 각각 두 정수가 주어지는데, 각 줄의 왼쪽과 오른쪽에 있는 구슬의 개수이다(위에서 아래 순서). 마지막 줄에 양의 정수 $N$ 이 주어진다.

출력

덧셈을 마친 뒤 각 줄의 왼쪽과 오른쪽에 있는 구슬의 개수를 $R$ 개의 줄에 두 수씩 출력한다.

제한

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

예제4

예제 1
입력
```
4
0 4
0 2
1 2
0 1
6
```
예상 출력
```
0 4
1 1
0 3
0 1
```
예제 2
입력
```
4
2 2
2 0
2 1
1 0
85
```
예상 출력
```
1 3
1 1
1 2
0 1
```
예제 3
입력
```
4
1 1
0 2
2 0
1 1
37
```
예상 출력
```
2 0
1 1
2 0
2 0
```

예제 4

입력

예상 출력