뱀과 사다리

뱀과 사다리는 10×10 격자에서 진행하는 보드 게임이다. 칸에는 1부터 100까지 번호가 매겨져 있다. 각 플레이어는 말 하나를 가지며, 게임이 시작될 때 모든 말은 1번 칸에 놓인다. 플레이어들은 순서대로 돌아가며 주사위 하나를 던지고, 주사위는 1 이상 6 이하의 값을 낸다. 차례는 플레이어 1, 플레이어 2, ..., 플레이어 $a$, 다시 플레이어 1의 순서로 반복된다. 주사위를 던진 플레이어는 나온 수만큼 말을 앞으로 옮긴다. 이렇게 옮기면 100번 칸을 지나치게 되는 경우, 말은 100번 칸에 멈춘다.

말을 옮긴 뒤에는 뱀과 사다리가 적용된다.

• 말이 사다리의 아래쪽 칸에 도착하면, 즉시 그 사다리의 위쪽 칸으로 올라간다.
• 말이 뱀의 머리 칸에 도착하면, 즉시 그 뱀의 꼬리 칸으로 내려간다.

한 칸에는 뱀이나 사다리의 끝점이 두 개 이상 놓이지 않으며, 100번 칸은 사다리의 아래쪽이나 뱀의 머리가 되지 않는다. 어떤 플레이어의 말이 100번 칸에 도달하는 순간 그 플레이어가 이기고, 게임은 즉시 끝난다.

뱀과 사다리의 배치와 주사위 눈의 수열이 주어질 때, 모든 말의 최종 위치를 구하여라. 주사위 수열이 반드시 누군가의 승리로 끝나는 것은 아니며, 게임이 끝난 뒤에도 이어질 수 있다. 승부가 나면 그 이후의 주사위 눈은 모두 무시한다.

첫째 줄에 세 양의 정수, 곧 플레이어 수 $a$, 뱀과 사다리의 수 $b$, 주사위를 던진 횟수 $c$가 주어진다. 플레이어는 최대 1000000명, 주사위를 던진 횟수는 최대 1000000번이다.

다음 $b$개의 줄에는 각각 뱀 또는 사다리 하나가 두 정수로 주어진다. 첫 번째 정수는 뱀의 머리 또는 사다리의 아래쪽이 있는 칸이고, 두 번째 정수는 뱀의 꼬리 또는 사다리의 위쪽이 있는 칸이다.

이어지는 $c$개의 줄에는 각각 주사위 눈 하나가 정수로 주어진다. 주사위 눈은 차례 순서대로 플레이어에게 배정된다.

각 플레이어마다 Position of player N is P. 형식의 줄을 하나씩 출력한다. 여기서 N은 플레이어 번호, P는 그 플레이어의 최종 위치이다. 플레이어 1번부터 $a$번까지 순서대로 출력한다.