402932: GYM100952 I Mancala

Mancala is a traditional board game played in Africa, Middle East and Asia. It is played by two players. This game board consists of two rows of holes, one row for each player. Each row has N holes, and each hole has some non-negative number of stones.

The two players will, in turn, make a move. One move is described as follows:

• the player chooses one of the holes in his row and takes all the stones from it.
• he starts to put these stones one in each hole, starting from the next hole and moving in counter-clockwise order, until there are no more stones left in his hands.

player1's row: 2 2 3

player2's row: 1 8 2

if player2 starts a move and chooses the middle hole in his row(the one with 8 stones). The board after the move will be like:

player1's row: 3 3 5

player2's row: 2 1 4

you were playing a very important game with your best friend, when suddenly you had a phone call and moved your eyes of the game. Now you lost track of the game and you need to make sure if your friend made a valid move.

You are given the final board configuration and the place where the last stone landed, Your task is to check is your friend's move is invalid, and in case of a valid move, find the state of the board before that move.

You are player1 while your friend is player2.

The input consists of several test cases, each test case starts with three numbers n(1 ≤ n ≤ 10000) (the number of holes in each of the rows), r (1 ≤ r ≤ 2) and k (1 ≤ k ≤ n) (the row and hole number where the last stone was put, respectively). Then 2n numbers follow, a_i :1  ≤  i  ≤  n, and b_j :1  ≤  j  ≤  n, where a_i is the number of stones in the i-th hole in your row. b_j is the number of stones in the j-th hole in your friend's row. Initially given a_i and b_i satisfy that: (0 ≤ a_i, b_j ≤ 1000000000) while a_i and b_j are fit in 64 bits in the state of the board before the move (if there is a valid move).

The last test case is followed by three zeros.

For each test case display the case number followed by the word "INVALID" without the quotes if the move is invalid, or 2n numbers representing the original board configuration otherwise.

3 1 3
3 3 5
2 1 4
4 2 2
1 2 3 4
5 4 3 2
4 2 2
1 2 3 4
1 2 3 4
5 2 3
2 2 2 2 2
2 2 2 2 2
0 0 0

Case 1:
2 2 3
1 8 2
Case 2:
INVALID
Case 3:
0 1 2 3
9 0 2 3
Case 4:
0 0 0 0 0
0 0 20 0 0