Jewel the Magician

TarifEzaz Replay of National High S...
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.

Input

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 1, the rest of them will have the value of 0. The meaning of these values are as follows:

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

If BB 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 CC is equal to 1, it means the blue marble is at position 3 at the start of the show, otherwise the value of CC is 0.

The next line will have an integer SS (0S10000000 \le S \le 1000000), the total number of swaps that Jewel has performed.

Each of the next S lines will have two integers P1P1 and P2P2, indicating there was a swap between position P1P1 and P2P2 (1P1,P231\le P1,P2 \le 3 and P1P2P1 \ne P2).

Output

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.

Sample

InputOutput
1 0 0
1
1 2
0 1 0

Submit

Login to submit.

Statistics

65% Solution Ratio
anonyo.akandEarliest, Jun '21
RaidingShamanFastest, 0.0s
serotoninLightest, 131 kB
Nusab19Shortest, 141B
Toph uses cookies. By continuing you agree to our Cookie Policy.