ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

MSU SE and Ural SU contest. Petrozavodsk training camp. Summer 2005

About     Problems     Submit solution     Judge status     Standings
Contest is over

G. Maze

Time limit: 0.5 second
Memory limit: 64 MB
One of the most popular games of all times is the "Maze". The game is played on a N × M table. The player can make the instructions: 'left', 'right', 'up', 'down'. For each cell of the table and each instruction the game-master has defined the destination cell that the player moves to; that is, the player is given the map of the maze. Once a game was interrupted, and the master has forgotten which cell the player was in. Fortunately, a full record of the gameplay has remained, which is the sequence of the instructions made by the player. You are to write a program determining the cells that the player can be currently in.


The first line of the input contains two numbers N and M (1 ≤ N,M ≤ 100). Four blocks of N lines each follow. Each line contains M pairs, being the new coordinates of the player after making k'th instruction standing in the cell (j, i), where i is the number of pair in the line, j is the number of line in the block, and k is the number of block. Following is the number S (1 ≤ S ≤ 4000) of the instructions made by the player. The last line contains the S numbers of the instructions made.


The first line of the output must contain the number L of the cells that player can be in after making the given sequence of instructions. Each of the next L lines must contain the coordinates of these cells, ordered first by the first coordinate, and then by the second.


2 3
1 2  1 3  1 3
2 2  2 3  2 3
2 1  2 2  2 3
2 1  2 2  2 3
1 1  1 1  1 2
2 1  2 1  2 2
1 1  1 2  1 3
1 1  1 2  1 3
1 2 3 4
1 1
1 2
Problem Author: Andrew Khalyavin
Problem Source: Petrozavodsk summer training camp, August 2005.
To submit the solution for this problem go to the Problem set: 1386. Maze