R. Bingo
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

To celebrate the airing of Tonikawa Season 2, the Yuzaki couple has decided to host a giant game of bingo at the bathhouse. There are $$$N$$$ people, conveniently numbered with an ID from $$$1$$$ to $$$N$$$, each with a $$$5$$$ by $$$5$$$ bingo board where each number is in the range $$$[1, k]$$$. Nasa will then call out the numbers from $$$1$$$ to $$$k$$$ in a certain order. The first person to have a full row or column of numbers that have been called already on their board wins (for simplicity diagonals are ignored in this problem). In the case of a tie, the person with the lowest ID wins. Nasa is going to ask you many different orders, and for each order he wants you to find the person who will win.

Input

The first line contains two integers $$$N$$$ and $$$k$$$, the number of people and the maximum number on any board $$$(1 \leq N \leq 10^5, 1 \leq k \leq 25)$$$.

Following this will be $$$N$$$ $$$5 \times 5$$$ boards $$$B_i$$$, denoting the bingo board of the $$$i$$$'th contestant. It is guaranteed that all numbers present on the board will be in the range $$$[1, k]$$$ but not all numbers are guaranteed to be distinct.

The next line will contain $$$1$$$ integer $$$q$$$, denoting the number of queries Nasa will ask you $$$(1 \leq q \leq 5 \cdot 10^4)$$$.

The following $$$q$$$ lines will each contain $$$k$$$ integers $$$O_i$$$ denoting the order the numbers are called in the $$$i$$$'th query. It is guaranteed that $$$O_i$$$ is a permutation of the numbers $$$1$$$ to $$$k$$$.

 —

Testcases in subtasks are numbered from $$$1 - 20$$$ with samples skipped.

Testcases $$$1-4$$$ satisfy $$$N = 1$$$.

For testcases $$$5 - 8$$$, $$$k = 16$$$.

For testcases $$$9 - 12$$$, $$$16 \leq k \leq 20$$$.

For testcases $$$13 - 16$$$, $$$1 \leq q \leq 1 \cdot 10^4$$$.

Due to easy test data (a mistake on my part), many unintended solutions can ac. So as a bonus problem, try to solve $$$k = 27$$$ for the inteded solution.

The remaining testcases do not satisfy any additional constraints.

Output

For each query output a line with two integers, $$$w$$$ and $$$l$$$, the ID of the winner and the last number that was called before he won. In the case of multiple winners, output the winner with the lowest ID. Under the constraints of the problem, at least one person will win every round.

Example
Input
1 25
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
4
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
1 6 11 16 2 7 12 17 3 8 13 18 4 9 14 19 25 21 22 23 24 5 10 15 20
1 2 3 4 6 7 8 10 11 12 14 15 16 18 19 20 22 23 24 25 5 9 13 17 21
16 14 13 22 3 21 15 23 20 9 11 24 4 8 1 12 7 17 19 5 2 10 6 25 18
Output
1 5
1 21
1 5
1 12
Note

In the first query, the first row of $$$[1, 2, 3, 4, 5]$$$ was completed with $$$5$$$ being the last number called.

In the second query, the first column of $$$[1, 6, 11, 16, 21]$$$ was completed with $$$21$$$ being the last number called.

In the third query, the first row and last column, $$$[1, 2, 3, 4, 5]$$$ and $$$[5, 10, 15, 20, 25]$$$ respectively, were completed after $$$5$$$ was called.

As a reminder, diagonals are not counted in this problem as a winning condition as opposed to regular bingo.

You can do it! Tsukasa smiles down on you!

 —

Idea: 3366

Preparation: 3366

Occurrences: Advanced 12