Kulramen

Figure 1: Så här kunde Simons kulram (med $R=4$) se ut innan han började äta upp kulorna. Då var det lätt att översätta ställningen till ett decimaltal.

Lille Simon har fått en kulram i present. Kulramen har $R$ rader och i varje rad fanns från början 9 kulor, så att man kunde representera $R$-siffriga decimaltal – en siffra på varje rad. Om en rad hade $X$ kulor på vänstra sidan, sedan ett mellanrum och övriga kulor på höger sida representerade raden siffran X.

Tyvärr tyckte Simon att kulorna på ramen såg väldigt smaskiga ut, och åt helt enkelt upp några kulor. Det finns dock minst en kula kvar på varje rad.

Simon lärde sig snabbt att räkna på sin nya kulram. Han representerar talet där alla kulor är på högersidan som talet 0, och adderar sedan 1 precis som han hade gjort på en vanlig kulram, genom att flytta en kula från höger till vänster på den nedersta raden som har någon kula kvar på höger sida (låt oss kalla den flyttningsraden) samt flytta alla kulor på raderna nedanför flyttningsraden till höger sida (om inte flyttningsraden är den nedersta raden). Om 1 adderas när alla kulorna på alla rader redan är på vänster sida (så att det inte finns någon flyttningsrad) blir resultatet 0.

Figure 2: Några exempel på hur Simon adderar 1 på den kulram som återfinns i de två första exemplen. Dubbelpilen markerar “flyttningsraden” vid de olika additionerna.

Simon håller på att räkna sandkornen i sin sandlåda och skulle behöva hjälp att skriva ett program som, givet ett visst utgångsläge på kulramen, räknar ut hur kulramen ser ut när han $N$ gånger har adderat 1.

Indata

På första raden står antalet rader $R$. Därefter följer $R$ rader med vardera två heltal, antalet kulor till vänster respektive höger på varje rad (uppifrån och ned). Slutligen finns en rad med det positiva heltalet $N$.

Utdata

Programmet ska skriva ut $R$ rader med två tal på varje rad: antalet kulor till vänster respektive höger på varje rad efter additionerna.

Poängsättning

För testfall värda $20$ poäng gäller att $R=4$, $N\le 100$, och det finns 2 kulor på varje rad.
För testfall värda ytterligare $40$ poäng gäller att $R=4$ och $N\le 10,000$.
För testfall värda $40$ poäng gäller att $R\le 12$ och $N\le 10^{12}$.

4
0 4
0 2
1 2
0 1
6

0 4
1 1
0 3
0 1

4
2 2
2 0
2 1
1 0
85

1 3
1 1
1 2
0 1

4
1 1
0 2
2 0
1 1
37

2 0
1 1
2 0
2 0

10
4 5
7 2
8 0
6 3
3 5
4 4
1 8
0 9
7 1
2 6
9876543210

1 8
5 4
1 7
9 0
7 1
1 7
4 5
3 6
0 8
2 6