30856번 - K-Lottery 다국어

문제

$K$-Lottery awards only one winner in each round. For each round, $K!$ tickets are produced and each ticket contains $K$ different numbers from 1ドル$ to $K,ドル and no two tickets are identical. Among the tickets produced each round, $M$ tickets are sold. The draw is conducted as follows each round. While randomly generating $N$ ($N ≥ K$) distinct numbers one by one, if the relative order of the last $K$ consecutive numbers matches the numbers on any of the sold tickets, the draw ends immediately, and the corresponding ticket wins. Some rounds may not have any winning tickets.

For instance, let's consider a round where 6 tickets are produced ($K = 3$). The ticket sequences produced are $(1, 2, 3),ドル $(1, 3, 2),ドル $(2, 1, 3),ドル $(2, 3, 1),ドル $(3, 1, 2),ドル and $(3, 2, 1)$. Among them, let's say $(1, 2, 3)$ and $(1, 3, 2)$ are sold ($M = 2$). Let's assume that the following 10ドル$ random numbers $(20, 35, 10, 7, 99, 53, 72, 33, 88, 16)$ are scheduled to be generated ($N = 10$). Then the relative order of $(7, 99, 53),ドル say $(1, 3, 2)$ matches the sold ticket $(1, 3, 2),ドル so that ticket wins.

In another scenario, let's consider a round where 24ドル$ tickets are produced ($K = 4$). The ticket sequences produced are $(1, 2, 3, 4),ドル $(1, 2, 4, 3),ドル $(1, 3, 2, 4),ドル $\dots,ドル and $(4, 3, 2, 1)$. Among them, let's assume $(1, 2, 3, 4),ドル $(1, 2, 4, 3),ドル $(3, 4, 1, 2),ドル $(4, 1, 2, 3),ドル and $(4, 2, 3, 1)$ are sold ($M = 5$). Let's assume that the following 10ドル$ random numbers $(19, 31, 9, 1, 89, 48, 63, 30, 78, 12)$ are scheduled to be generated ($N = 10$). Then the relative order of $(89, 48, 63, 30),ドル say $(4, 2, 3, 1)$ matches the sold ticket $(4, 2, 3, 1),ドル so that ticket wins.

Given information about a round of the $K$-Lottery, including the number of produced tickets, the number sequences of the sold tickets, and the sequence scheduled to be randomly generated for the winning ticket, write a program to output the number sequence of the winning ticket.

입력

Your program is to read from standard input. The input starts with a line containing three integers, $K,ドル $M,ドル and $N$ (3ドル ≤ K ≤ 10,000円,ドル 1ドル ≤ M ≤ \min (K!, 1,000円),ドル $K ≤ N ≤ 1,000円,000円,ドル 3ドル ≤ KM ≤ 100,000円$), where $K$ is the number of numbers in each ticket, $M$ is the number of tickets sold, and $N$ is the number of numbers in the randomly generated sequence of the round. In each of the following $M$ lines, $K$ integers of a ticket sold in the round are given. The final line contains $N$ different positive integers $N_i$ (1ドル ≤ N_i ≤ 100,000円,000円,ドル 1ドル ≤ i ≤ N$) which is the number sequence for determining a winner.

출력

Your program is to write to standard output. Print exactly one line. The line should contain the number sequence of the winning ticket. If there is no winning ticket, print 0.

제한

힌트