L. Lockout
time limit per test
0.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The long-awaited annual Lockout for Schools using Problems from Codeforces (LSPC) has commenced! For those who are new to Lockout, in each match, two players compete head-to-head in a thrilling test of speed and accuracy. Contestants are reminded to familiarize themselves with the revised rules this year:

  • In a match, two contestants (denoted as contestant $$$1$$$ and contestant $$$2$$$) solve tasks from a given problemset consisting of $$$16$$$ tasks arranged in a $$$4 \times 4$$$ grid. Each task is uniquely identified by a task ID.
  • Contestants are allowed to attempt the tasks in any order. The first contestant to solve a task claims that task. Once a task is claimed, contestants are not allowed to submit solutions to that task anymore.
  • The first contestant who claims $$$4$$$ tasks that form a line or any $$$9$$$ tasks wins. The match immediately ends when this condition is met. A line is defined to be any of the $$$4$$$ rows, $$$4$$$ columns, the leading diagonal and the trailing diagonal of the $$$4 \times 4$$$ grid.
  • Matches have a time limit. If the winning condition is not met before the end of the match, the invigilator shall declare the match a tie.

Here's a warmup task designed to consolidate your understanding of the rules: given the list of task IDs in an arbitrary order along with the list of accepted submissions (submissions that result in a task being claimed) of a match in chronological order, can you reconstruct the $$$4 \times 4$$$ grid during the match?

Input

The first line contains $$$16$$$ task IDs. A task ID consists of an integer between $$$1$$$ and $$$9999$$$ (inclusive) followed by an uppercase letter.

The second line contains an integer $$$N$$$ ($$$0 \leq N \leq 16$$$), representing the number of accepted submissions during the match.

The next $$$N$$$ lines each describes an accepted submission: it contains an integer (either $$$1$$$ or $$$2$$$) and a task ID, representing the contestant who made the submission and the task that they claimed respectively. These $$$N$$$ task IDs are distinct.

It is guaranteed that the input corresponds to the accepted submissions of a Lockout match in chronological order.

Output

Output any possible $$$4 \times 4$$$ grid of task IDs that could have been used in the match.

Example
Input
3P 1U 4I 1C 5H 9I 2N 6G 5X 3L 5A 8S 9A 7L 9L 3E
7
1 5H
2 3E
1 5X
2 5A
2 3L
2 1C
2 7L
Output
9I 8S 9L 1C
2N 3P 7L 5H
6G 3E 1U 3L
5A 9A 4I 5X
Note

In the Sample Output above, the winning condition was not met after the first $$$6$$$ accepted submissions. Once contestant $$$2$$$ claimed task 7L, they managed to formed a line (specifically along the trailing diagonal) so contestant $$$2$$$ wins and the match is over.

On the other hand, the output 

9I 8S 9L 1C
2N 3P 3L 5H
6G 3E 1U 7L
5A 9A 4I 5X

will result in a Wrong Answer verdict because once contestant $$$2$$$ claims task 1C, a line has been formed so the match should have ended then.