Snakes and Ladders

Time limit1sMemory limit128 MB

Summary
Simulate a Snakes and Ladders game with a players and a list of die rolls, applying snakes and ladders after each move, and print each token's final square.
Level

Easy3 of 10

Topics
Simulation, Implementation, Array
Solved
No attempts yet

Problem

Snakes and Ladders is a board game played on a 10 by 10 grid. The squares are numbered 1 to 100. Every player has one token, and at the start of the game every token is placed on square 1. Players take turns rolling a single die that yields a value from 1 to 6, and turns proceed in order: player 1, player 2, ..., player aa, then player 1 again, and so on. After a roll, the player advances their token forward by the number shown on the die. If this would move the token past square 100, the token stops on square 100 instead.

After the token has advanced, snakes and ladders take effect:

  • if the token lands on the bottom of a ladder, it must immediately move up to the square at the top of that ladder;
  • if the token lands on the mouth of a snake, it must immediately move down to the square at the tail of that snake.

No square holds more than one snake or ladder endpoint, and square 100 is never the bottom of a ladder or the mouth of a snake. A player wins the moment their token reaches square 100, and the game ends immediately at that point.

Given the layout of the snakes and ladders and a sequence of die rolls, report the final position of every token. The sequence of rolls need not end in a win, and it may run on after the game is over; once a win occurs, every remaining roll is ignored.

Input

The first line contains three positive integers: the number of players aa, the number of snakes and ladders bb, and the number of die rolls cc. There are at most 1000000 players and at most 1000000 die rolls.

Each of the next bb lines describes one snake or ladder with two integers. The first integer is the square holding the mouth of the snake or the bottom of the ladder; the second integer is the square holding the tail of the snake or the top of the ladder.

Each of the following cc lines contains one integer, the value of the next die roll. The rolls are handed out to the players in turn order.

Output

For each player, print one line of the form Position of player N is P., where N is the player's number and P is that player's final position. Print the players in order from player 1 to player aa.

Examples3

  1. Example 1

    Input
    3 1 3
4 20
3
4
5
    Expected output
    Position of player 1 is 20.
Position of player 2 is 5.
Position of player 3 is 6.

  2. Example 2

    Input
    1 1 3
4 100
3
5
6
    Expected output
    Position of player 1 is 100.

  3. Example 3

    Input
    1 1 2
10 3
6
3
    Expected output
    Position of player 1 is 3.