Potato is going to play a very common carnival game with Rar the Cat. This game starts off with three cups, with a ball hidden underneath the middle cup. The cup at the leftmost position will be labelled as Cup 1, the middle position as Cup 2, and the rightmost position as Cup 3. Thus, at the beginning, the ball will be underneath Cup 2. Rar the Cat then performs N random swaps between two different cups. For example, if he swaps Cup 1 and Cup 2, the ball that was originally under Cup 2 will be under Cup 1 after that swap.
As you probably would have realised by now, a potato has many eyes, so it is able to track all the swaps that Rar the Cat performs. However, the potato's computational ability is limited due to its lack of a brain. Thus, given all the swaps that Rar the Cat performs, help Potato find out which cup the ball is under after the final swap.
Your program should implement the following functions:
- void startGame(), which indicates the start of the game.
- void swap(int A, int B), which indicates a swap between Cup A and Cup B.
- int getAnswer(), which is called at the end of a game. Return the cup the ball is currently under.
Subtask 1 (23%): 1 <= N
<= 1 000
Subtask 2 (77%): 1 <= N
<= 1 000 000
Sample Input 1
Sample Output 1