Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Jewel is a promising magician. Recently, he has learned a technique to mesmerize his audience. Let's demystify his technique as follows:

Jewel keeps three glasses upside down. Let's denote these three glasses as G1, G2 and G3. Initially, G1 is kept at position 1, G2 is at position 2 and G3 is located at position 3. Underneath one of these three glasses, Jewel keeps a blue marble. Initially, the audience knows where the marble is. But after some trickery from Jewel, he picks out a glass from a position in which the marble was placed at the beginning. And to their utmost surprise, the audience find out that the marble is not where it should be! What actually happens is, Jewel holds two glasses and swaps the position of them in lightning speed. Imagine, if Jewel swaps two glasses G1 and G3 from its original position, G1 is now placed at position 3 and G3 is now placed at position 1. Please also note that, if the marble was positioned at 1 to begin with, its place has now been shifted to 3 along with its containing glass.

To understand the “magic” of Jewel, his competitor Shahin has placed a hidden camera at the top of the stage. With this camera, Shahin has figured about all the swaps that Jewel has made. Just like the stories of all the problem statements, Shahin has come to you for help with all the data that he has collected from his hidden camera.

Shahin knows at which position the marble was placed initially. He also knows the sequential swaps of the glasses that had taken place. You will have to answer the total number of times the marble was placed at each position after Jewel starts his swapping.

The first line of input will contain exactly three integers $A$, $B$ and $C$. Exactly one of these three integers will have the value of $1$, the rest of them will have the value of $0$. The meaning of these values are as follows:

If $A$ is equal to $1$, it means the blue marble is at position $1$ at the start of the show, otherwise the value of $A$ is $0$.

If $B$ is equal to $1$, it means the blue marble is at position $2$ at the start of the show, otherwise the value of B is 0.

If $C$ is equal to $1$, it means the blue marble is at position $3$ at the start of the show, otherwise the value of $C$ is $0$.

The next line will have an integer $S$ ( $0 <= S <= 1000000$ ), the total number of swaps that Jewel has performed.

Each of the next S lines will have two integers P1 and P2, indicating there was a swap between position $P1$ and $P2$ ($1<=P1,P2<=3$ and $P1!=P2$).

Subtask 1 ( 10 points ):

$S = 0$

Subtask 2 ( 20 points ):

$S = 1$

Subtask 3 ( 70 points):

$0 <= S <= 1000000$

Print three integers on a line, each indicating the number of times the blue marble has ended up in that position after a swap. Please note that the position in which the marble was placed before the start of the show will not be counted unless at least one swap is performed among any of the glasses.

Input | Output |
---|---|

1 0 0 1 1 2 | 0 1 0 |

67% Solution Ratio

anonyo.akandEarliest,

salman.exeFastest, 0.1s

serotoninLightest, 131 kB

anonyo.akandShortest, 166B

Login to submit

The main task of this problem is to perform swaps. The simplest way to swap two numbers A and B is a...