#P14089. [ICPC 2023 Seoul R] K-Lottery

[ICPC 2023 Seoul R] K-Lottery

题目描述

KK-Lottery awards only one winner in each round. For each round, K!K! tickets are produced and each ticket contains KK different numbers from 11 to KK, and no two tickets are identical. Among the tickets produced each round, MM tickets are sold. The draw is conducted as follows each round. While randomly generating NN(NKN\ge K) distinct numbers one by one, if the relative order of the last KK 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 66 tickets are produced (K=3K = 3). The ticket sequences produced are (1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2)(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2), and (3,2,1)(3, 2, 1). Among them, let's say (1,2,3)(1, 2, 3) and (1,3,2)(1, 3, 2) are sold (M=2M = 2). Let's assume that the following 1010 random numbers (20,35,10,7,99,53,72,33,88,16)(20, 35, 10, 7, 99, 53, 72, 33, 88, 16) are scheduled to be generated (N=10N = 10). Then the relative order of (7,99,53)(7, 99, 53), say (1,3,2)(1, 3, 2) matches the sold ticket (1,3,2)(1, 3, 2), so that ticket wins.

In another scenario, let's consider a round where 2424 tickets are produced (K=4K = 4). The ticket sequences produced are (1,2,3,4),(1,2,4,3),(1,3,2,4),(1, 2, 3, 4), (1, 2, 4, 3), (1, 3, 2, 4) , \dots, and (4,3,2,1)(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)(4, 2, 3, 1) are sold (M=5M = 5). Let's assume that the following 1010 random numbers (19,31,9,1,89,48,63,30,78,12)(19, 31, 9, 1, 89, 48, 63, 30, 78, 12) are scheduled to be generated (N=10N = 10). Then the relative order of (89,48,63,30)(89, 48, 63, 30), say (4,2,3,1)(4, 2, 3, 1) matches the sold ticket (4,2,3,1)(4, 2, 3, 1), so that ticket wins.

Given information about a round of the KK-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,MK,M, and NN ($3 \le K \le 10,000 , 1 \le M\le \min (K!, 1,000) , K\le N\le 1,000,000 , 3\le KM \le 100,000$), where KK is the number of numbers in each ticket, MM is the number of tickets sold, and NN is the number of numbers in the randomly generated sequence of the round. In each of the following MM lines, KK integers of a ticket sold in the round are given. The final line contains NN different positive integers NiN_i (1Ni100,000,000,1iN1 \le N_i\le 100,000,000, 1 \le i\le 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.

3 2 10
1 2 3
1 3 2
20 35 10 7 99 53 72 33 88 16
1 3 2
4 5 10
1 2 3 4
1 2 4 3
3 4 1 2
4 1 2 3
4 2 3 1
19 31 9 1 89 48 63 30 78 12
4 2 3 1
3 3 7
1 3 2
2 3 1
2 1 3
11 22 33 44 55 66 77
0