Snake

There is a DOS game called 'Dummy'. In the game, a snake crawls around a board. When the snake eats an apple, its length increases. If it hits a wall or its own body, the game ends.

The game is played on an N x N square board. Some cells contain apples, and the four edges of the board are walls. At the beginning, the snake is in the top-left cell, has length 1, and faces right.

Every second, the snake moves in the following order.

• First, it extends its body and moves its head into the next cell.
• If the head touches a wall or the snake's own body, the game ends.
• If the new cell contains an apple, the apple disappears and the tail does not move.
• If the new cell does not contain an apple, the tail cell becomes empty, so the snake's length stays the same.

Given the apple positions and the snake's direction changes, determine how many seconds after the game starts the game ends.

The first line contains the board size N. (2 <= N <= 100)

The second line contains the number of apples K. (0 <= K <= 100)

Each of the next K lines contains the position of an apple. The first integer is the row, and the second integer is the column. All apple positions are distinct, and there is no apple in the top-left cell (row 1, column 1).

The next line contains the number of direction changes L. (1 <= L <= 100)

Each of the next L lines contains one direction change, consisting of an integer X and a character C. After X seconds have elapsed since the game started, the snake turns 90 degrees left if C is 'L', or 90 degrees right if C is 'D'. X is a positive integer at most 10,000, and the direction changes are given in increasing order of X.

Print one line containing the number of seconds until the game ends.