409868: GYM103811 L Lockout

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?

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 any possible $$$4 \times 4$$$ grid of task IDs that could have been used in the match.

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

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

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.