P14089 [ICPC 2023 Seoul R] K-Lottery

$K$-Lottery 每轮只产生一名获胜者。在每一轮中，会生成 $K!$ 张彩票，每张彩票包含从 $1$ 到 $K$ 的 $K$ 个不同数字，且没有两张彩票完全相同。在这些生成的彩票中，有 $M$ 张被售出。每一轮的开奖流程如下：在依次随机生成 $N$（$N \ge K$）个不同数字的过程中，如果最近连续的 $K$ 个数字的相对次序恰好与某一张已售出的彩票完全相同，则开奖过程立即结束，这张彩票获胜。某些轮次可能不会产生获胜的彩票。 例如，考虑一轮比赛，共生成 $6$ 张彩票（$K = 3$）。生成的彩票排列分别为 $(1,2,3)$、$(1,3,2)$、$(2,1,3)$、$(2,3,1)$、$(3,1,2)$ 和 $(3,2,1)$。其中，$(1,2,3)$ 和 $(1,3,2)$ 被售出（$M = 2$）。假设即将生成的 $10$ 个随机数字为 $(20, 35, 10, 7, 99, 53, 72, 33, 88, 16)$（$N = 10$）。那么 $(7, 99, 53)$ 这连续三个数字的相对次序为 $(1, 3, 2)$，恰好与已售出的彩票 $(1, 3, 2)$ 相同，因此该彩票获胜。 再比如，考虑一轮比赛，共生成 $24$ 张彩票（$K = 4$）。生成的彩票排列为 $(1,2,3,4)$、$(1,2,4,3)$、$(1,3,2,4)$、$\dots$、$(4,3,2,1)$。其中，$(1,2,3,4)$、$(1,2,4,3)$、$(3,4,1,2)$、$(4,1,2,3)$ 和 $(4,2,3,1)$ 被售出（$M=5$）。假设即将生成的 $10$ 个随机数字为 $(19, 31, 9, 1, 89, 48, 63, 30, 78, 12)$（$N = 10$）。那么 $(89, 48, 63, 30)$ 这四个连续数字的相对次序为 $(4,2,3,1)$，恰好与已售出的彩票 $(4,2,3,1)$ 相同，因此该彩票获胜。 现在给定一轮 $K$-Lottery 的信息，包括生成的彩票数量、已售出的彩票的数字序列，以及用来决定获胜的彩票的随机序列。请编写程序输出获胜的彩票的数字序列。

你的程序需要从标准输入读取数据。输入的第一行为三个整数 $K$、$M$ 和 $N$ （$3 \le K \le 10\,000$，$1 \le M \le \min (K!, 1\,000)$，$K \le N \le 1\,000\,000$，$3 \le K M \le 100\,000$），其中 $K$ 表示每张彩票的数字数量，$M$ 表示售出的彩票数，$N$ 表示本轮随机生成的数字数量。接下来的 $M$ 行，每行包含 $K$ 个整数，表示一张已售出的彩票。最后一行包含 $N$ 个不同的正整数 $N_i$（$1 \leq N_i \leq 100\,000\,000, 1 \leq i \leq N$），表示用来决定中奖的彩票的随机数字序列。

你的程序需要向标准输出输出一行。该行输出获胜的彩票的数字序列。如果没有彩票获胜，输出 `0`。

由 ChatGPT 5 翻译