For his wedding, Mr. Nguyen ordered "a chocolate and vanilla cake" from the bakery, but whereas he expected to receive one chocolate cake and one vanilla cake, the bakery delivered him one massive wedding cake with mixed layers of chocolate and vanilla! Now, he wants to separate the layers of the wedding cake into two separate chocolate and vanilla cakes.
The cake sent by the bakery has $$$n$$$ cylindrical layers of decreasing radius from the bottom to the top, with interspersed chocolate and vanilla layers. In addition to the plate already occupied by the mixed-layer cake, denoted plate 1, Mr. Nguyen has two empty plates, denoted plates 2 and 3, on which he wants to construct the chocolate and vanilla cakes, respectively. In one second, Mr. Nguyen can transfer the top layer of a cake from one plate to a different plate. He does not want the cake to collapse, however, so he can only move layers onto layers of larger radius.
Mr. Nguyen needs your help to separate the chocolate and vanilla layers from the mixed-layer cake on plate 1 onto plates 2 and 3, respectively, in at most $$$2^n-1$$$ seconds.
The first line of input contains $$$n$$$ ($$$2 \le n \le 20$$$), the number of total layers in the wedding cake.
The second line contains a bitstring $$$l$$$ of length $$$n$$$, listing the layers from bottom to top, where $$$l_i$$$ is 0 if layer $$$i$$$ is chocolate or 1 if it is vanilla. There is guaranteed to be at least one chocolate and one vanilla layer.
The output should be at most $$$2^n-1$$$ lines consisting of a series of instructions in the form "$$$i$$$ $$$j$$$" ($$$1 \le i, j \le 3, i \ne j$$$), meaning a layer should be moved from plate $$$i$$$ to plate $$$j$$$. If the instructions are followed in order, plate 1 should be empty and plates 2 and 3 should contain the chocolate and vanilla cakes, respectively.
3010
1 2 1 3 2 3 1 2 3 2
The diagram below illustrates the construction of the chocolate and vanilla cakes. This is done in 5 seconds, which is within the limit of $$$2^n-1=7$$$ seconds.
