Practice on Toph

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

Jewel the Magician

By TarifEzaz · Limits 1s, 512 MB

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 AA, BB and CC. Exactly one of these three integers will have the value of 11, the rest of them will have the value of 00. The meaning of these values are as follows:

If AA is equal to 11, it means the blue marble is at position 11 at the start of the show, otherwise the value of AA is 00.

If BB is equal to 11, it means the blue marble is at position 22 at the start of the show, otherwise the value of B is 0.

If CC is equal to 11, it means the blue marble is at position 33 at the start of the show, otherwise the value of CC is 00.

The next line will have an integer SS ( 0<=S<=10000000 <= 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 P1P1 and P2P2 (1<=P1,P2<=31<=P1,P2<=3 and P1!=P2P1!=P2).

Subtask 1 ( 10 points ):

S=0 S = 0

Subtask 2 ( 20 points ):

S=1 S = 1

Subtask 3 ( 70 points):

0<=S<=1000000 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.


1 0 0
1 2
0 1 0



    67% Solution Ratio

    anonyo.akandEarliest, 1M ago

    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...