No, we don't luv stamina; we luv jumptrills!

After being tortured by three hours of handstream practice, the desperate XW is begging you to write a program that converts a given stream chart into a purely jumptrills chart.

Let's describe your task in formal terms. Note that some definitions in this problem may differ from those used in real 4-key rhythm games.

A chart is an $$$n \times 4$$$ binary matrix. Let $$$c_{i,j}$$$ denote the element in the $$$i$$$-th row and $$$j$$$-th column. Here, $$$c_{i,j} = 1$$$ means there is a note at that position, and $$$c_{i,j} = 0$$$ means it is empty. The given chart is guaranteed to satisfy that no column has two consecutive notes, i.e. for all $$$1 \lt i \leq n$$$ and $$$1 \leq j \leq 4$$$, we have $$$c_{i-1,j} \times c_{i,j} = 0$$$.

While playing the chart, you hit notes in columns 1 and 2 with your left hand, and notes in columns 3 and 4 with your right hand. To make the chart more playable, XW wants to ensure that no hand is required to hit notes in two consecutive rows. To achieve this, he needs you to perform the following operation:

• Check all rows in reverse order: from row $$$n-1$$$ down to row $$$1$$$.
• For the current row $$$i$$$:
  • If row $$$i+1$$$ has a note in column 1 or 2, and row $$$i$$$ also has a note in column 1 or 2, then move the note in row $$$i$$$ down by one row. (It can be proven that in this case, there is only one such note and the position below it is empty.)
  • Similarly, if row $$$i+1$$$ has a note in column 3 or 4, and row $$$i$$$ also has a note in column 3 or 4, move that note in row $$$i$$$ down by one row.

After applying the above transformation, the chart will be converted from a terrifying dense handstream chart into a friendly jumptrills chart. But XW doesn't know how to implement it. Can you help him?

Reading the sample might help you better understand the task.