Candy Land

Candy Land is a board game popular among young children. The board is a row of squares, and each square is either a color square or a special square. Several players can play. On a turn, a player flips the top card of a face-down deck. A card shows one colored square, two squares of the same color, or one special square. With one colored square, the player advances from their current position to the next square of that color. With two squares of the same color, the player advances to the second square of that color past their current position. With a special square, the player moves directly to that special square, which can be ahead of or behind their current position. Each special square appears exactly once on the board. Several players can stand on the same square at the same time. Players start directly before the first square.

The last square is multicolored (all colors) and is where a player lands when no further square of the card's color exists. The first player to reach the last square wins. If a player draws a two-square card whose color appears only on the last square, that player wins.

After a player follows a card, the player places it face down at the bottom of the deck. The children do not shuffle the cards, so the game is fully deterministic.

The first line has two positive integers, n (2 ≤ n ≤ 200), the number of squares, and p (2 ≤ p ≤ 6), the number of players. The next n-1 lines each contain a string of uppercase letters, giving the contents of squares 1 through n-1 in order. The last square is not listed. Each string has at most 20 uppercase letters. Special squares start with SPECIAL followed by at least one uppercase letter. No color contains the substring SPECIAL.

The next line has c (c ≤ 500), the number of cards. Each of the next c lines describes one card, from the top of the deck down. A card is a number (1, 2, or 3), a space, and an uppercase string. Card type 1 is a single colored square, type 2 is two squares of that color, and type 3 is a special square. For types 1 and 2, the string is a color on the board. For type 3, the string is a special square on the board.

Print the 1-based number of the player who wins, on a line by itself. The input guarantees that the game ends in fewer than 10,000 turns, although some players may never finish if play continued forever.