주판

Simon이 구슬을 먹기 시작하기 전에는 Simon의 주판($R=4$)이 이렇게 생겼을 수 있다. 당시에는 이 상태를 십진수로 변환하기가 쉬웠다.

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

안타깝게도 Simon은 주판의 구슬이 매우 맛있어 보인다고 생각해 구슬 몇 개를 그냥 먹어 버렸다. 하지만 각 줄에는 적어도 하나의 구슬이 남아 있다.

Simon은 새 주판으로 계산하는 법을 금세 배웠다. 그는 모든 구슬이 오른쪽에 있는 상태를 수 0으로 나타내고, 일반 주판에서 했던 것처럼 1을 더한다. 오른쪽에 구슬이 남아 있는 줄 중 가장 아래쪽 줄(이를 이동 줄이라고 하자)에서 구슬 하나를 오른쪽에서 왼쪽으로 옮기고, 이동 줄 아래에 있는 모든 줄의 구슬을 오른쪽으로 옮긴다(이동 줄이 맨 아래쪽 줄이 아닌 경우). 모든 줄의 구슬이 이미 왼쪽에 있을 때(따라서 이동 줄이 없을 때) 1을 더하면 결과는 0이 된다.

앞의 두 예제에 나오는 주판에서 Simon이 1을 더하는 방법의 몇 가지 예이다. 양방향 화살표는 각 덧셈에서의 ``이동 줄''을 표시한다.

Simon은 모래상자에 있는 모래알을 세고 있으며, 주판의 특정한 초기 상태가 주어졌을 때 1을 $N$번 더한 후 주판이 어떻게 보이는지 계산하는 프로그램을 작성하는 데 도움이 필요하다.

채점

$20$점에 해당하는 테스트 케이스에서는 $R=4$, $N\le 100$이고, 각 줄에는 2개의 구슬이 있다.

추가로 $40$점에 해당하는 테스트 케이스에서는 $R=4$이고 $N\le 10,000$이다.

$40$점에 해당하는 테스트 케이스에서는 $R\le 12$이고 $N\le 10^{12}$이다.

첫째 줄에는 줄의 수 $R$가 주어진다. 이어서 위에서 아래 순서로 각 줄마다 왼쪽과 오른쪽에 있는 구슬의 수를 각각 나타내는 두 정수가 적힌 $R$개의 줄이 주어진다. 마지막으로 양의 정수 $N$가 적힌 줄이 주어진다.

프로그램은 덧셈을 마친 후 각 줄의 왼쪽과 오른쪽에 있는 구슬의 수를 각각 나타내는 두 수가 적힌 $R$개의 줄을 출력해야 한다.