Problem Description

You have $k$ machines. Each machine stores the $n$ numbers $1 \sim n$ in an unordered way. When you start a machine, it prints the frontmost number among the numbers stored in that machine, and then deletes it.

Fortunately, you know $m$ pairs $(a_i, b_i)$, meaning that in every machine’s storage, each stored $a_i$ is before $b_i$.

You also know the output produced by starting machines one by one. For each printed number, determine a plan that specifies which machine it came from, and make sure that the number of occurrences of each number $= k$.

There may be multiple feasible solutions; output any one to get accepted.

Input Format

The first line contains three integers $n, k, m\ (1 \leq n, k \leq 5 \times 10^5, 0 \leq m \leq 2.5 \times 10^5, 1 \leq n \times k \leq 5 \times 10^5)$.

Then follow $m$ lines, each containing two integers $a_i, b_i\ (1 \leq a_i, b_i \leq n)$, and it is guaranteed that there is no cycle.

Then one line contains $n \times k$ numbers, representing the sequence printed by the machines when they are started in order.

Output Format

Output one valid starting plan.

3 3 2
1 2
1 3
1 1 2 3 3 2 1 2 3

1 2 2 1 2 1 3 3 3

Hint

Translated by ChatGPT 5