CS 202 Chutes and Ladders

Problem description

Chutes and Ladders is a board game played on a 10x10 grid. The squares of the grid are numbered 1 to 100. Each player is represented by a game piece token, which is placed on the square numbered 1 at the beginning of the game. Each player takes turns rolling a single die to move the token by the number of squares indicated by the die roll. If this would put the token past the square numbered 100, the token is advanced to 100. If, on completion of a move, a player's token lands on the bottom end of a ladder, the token is moved to the top of the ladder. If the player lands on the top of a chute, the token is moved to the bottom of the chute. No square contains more than one end of any chute or ladder. The square numbered 100 does not contain the top of a chute or the bottom of a ladder. The player who is first to bring their token to the square numbered 100 is the winner. At that point, the game ends.

Given the configuration of the chutes and ladders on a game board and a sequence of die rolls, determine the positions of all the tokens on the game board. The sequence of die rolls need not lead to any player winning. The sequence of die rolls may also continue after the game is over; in this case, the die rolls after the end of the game should be ignored.

Input

The first line is the number of test cases to follow. The test cases follow, one after another. The format of each test case is the following:

The first line contains three positive integers: the number a of players, the number b of chutes or ladders, and the number c of die rolls. There will be no more than 1,000,000 players and no more than 1,000,000 die rolls. Each of the next b lines contains two integers specifying a chute or ladder. The first integer indicates the square containing the top of the chute or the bottom of the ladder. The second integer indicates the square containing the bottom of the chute or the top of the ladder. The following c lines each contain one integer giving the number rolled on the die.

Output

For each player, output a single line containing a string of the form 'Player N is on square P.' where N is replaced with the number of the player and P is replaced with the final position of the player.

Sample Input

1
3 1 3
4 20
3
4
5

Sample Output

Player 1 is on square 20.
Player 2 is on square 5.
Player 3 is on square 6.