TPU Task Scheduling

Your task is to assign each of N A+B problems to one of K TPUs in order to optimize the overall computation performance. Although each problem is an A+B computation, the twist is that there are dependencies among these problems. In particular, if problem i depends on problem j, then problem i can only start after problem j finishes computing and its result is transmitted to the TPU where problem i will be executed.

The computation time of problem i on TPU j is given by \(t_{ij}\). When problem j is computed on TPU \(p\) and problem i is computed on TPU \(q\), the transmission time for passing the result is \(r_{pq}\) (with \(r_{pp}=0\) for any TPU \(p\)). Data transmission occurs in parallel among different machines and does not interfere with computation, but data cannot be forwarded (i.e. transmission must be executed directly between the two TPUs).

The following additional conditions hold:

1. The dependency graph among the problems is acyclic.
2. At any moment, each TPU can only compute one problem, and once a problem starts computing, it is processed non-preemptively until it finishes.
3. If a TPU is idle and one or more problems are ready (i.e. all dependencies have been resolved and necessary data is available), the TPU will immediately select the problem with the smallest index to compute.
4. Each TPU is capable of performing multiple data transmissions concurrently and the transmissions do not affect the computation time.
5. No data forwarding is allowed.
6. \(r_{ii}=0\) for all \(i\).
7. If a task does not depend on any other task, then its required data is already present on its assigned TPU at time 0.

The objective is to decide on which TPU each problem should be computed so that either the sum of all TPUs' computing times (computation plus transmission) is minimized, or the overall finish time (from the start of the first computation to the end of the last computation) is minimized.

Note that, under the above conditions, the execution order on each TPU is completely determined by the rules. Your output should be a valid assignment of tasks to TPUs (each TPU is identified by an integer from 1 to \(K\)).

inputFormat

The input starts with a single line containing three integers \(N\), \(K\), and \(M\) representing the number of problems, the number of TPUs, and the number of dependency relations, respectively.

This is followed by \(N\) lines, each containing \(K\) integers. The i-th of these lines contains \(t_{i1}, t_{i2}, ..., t_{iK}\) where \(t_{ij}\) is the computation time of problem i on TPU j.

Then there are \(K\) lines, each with \(K\) integers. The p-th of these lines contains \(r_{p1}, r_{p2}, ..., r_{pK}\) where \(r_{pq}\) is the transmission time from TPU p to TPU q (note that \(r_{pp}=0\) for any p).

Finally, there are \(M\) lines, each containing two integers u and v (1-based indices), indicating that problem v depends on problem u (i.e. problem v cannot start until problem u has finished and its result has been transmitted to the TPU assigned to problem v).

outputFormat

Output a single line containing \(N\) integers. The i-th integer represents the TPU (an integer from 1 to \(K\)) to which problem i is assigned. Any valid assignment that meets the problem constraints is accepted. (Note that the execution order on each TPU is automatically determined by the rules.)

sample

3 2 2
1 2
2 1
3 4
0 1
2 0
1 2
2 3

1 1 1