This is an answer-submission problem.

Description

Our protagonist this time is Xiao He. As everyone knows, Xiao He is very wealthy and has purchased $K$ TPUs to solve $A+B$ problems. Xiao He now has $N$ $A+B$ problems, where the $i$-th $A+B$ problem requires $t_{ij}$ time to be computed on the $j$-th TPU. Unlike traditional $A+B$ problems, there are $M$ dependency relationships among these $N$ problems. If problem $i$ depends on problem $j$, then problem $i$ must wait for problem $j$ to finish its computation and for the result to be transmitted to the TPU where problem $j$ is located before problem $i$ can begin its computation. If problem $i$ is computed on the $p$-th TPU and problem $j$ is computed on the $q$-th machine, the time required for the result of problem $i$ to be transmitted to problem $j$ is $r_{pq}$. Data transmission is parallel; that is, multiple machines sending data to one machine, or one machine sending data to multiple machines, does not affect the speed of data transmission. However, we stipulate that data transmission cannot be forwarded; if data must be transmitted from machine $i$ to machine $j$, it cannot be transmitted to machine $k$ first and then to machine $j$.

Although Xiao He is very wealthy, he does not have much time because he still has to spend time with his girlfriend. Therefore, Xiao He wants you to help him decide which machine to assign each $A+B$ problem to, such that the total computation time of all TPUs is minimized, or the completion time of all tasks is minimized. The computation time of a TPU is defined as the sum of the time the TPU spends computing problems plus the time spent on all data transmissions. The completion time of all tasks is defined as the time from the start of the first computation to the end of the last computation.

Although Xiao He is very wealthy and knows that you do not have much time to work on this problem, he has simplified the task with the following rules:

1. There are no cycles in the dependency relationships of the problems.
2. At any moment, a TPU can only compute one problem, and once the computation of a problem begins, it will not be interrupted until the problem is finished.
3. If a TPU is not currently computing any problem and there are one or more problems ready to be computed (with data prepared), the TPU will choose the problem with the smallest index to start computing.
4. A TPU can perform multiple data transmissions simultaneously, and they do not affect each other's speed. Computation and data transmission can occur simultaneously without affecting each other's speed.
5. Data cannot be forwarded and can only be transmitted directly between the corresponding machines.
6. It is guaranteed that $r_{ii} = 0$.
7. If a task does not depend on any other tasks, the data required for that task is already prepared on the corresponding machine and does not need to be transmitted.

Under these conditions, Xiao He believes this problem is simple enough, so he happily went to play with his girlfriend and left this problem to you.

Input

This is an answer-submission problem with 10 input data files, named placement1.in ~ placement10.in.

The first line contains four integers $N, M, K, op$. If $op = 1$, you need to minimize the total computation time of the TPUs; otherwise, you need to minimize the completion time of the last task.

The next $M$ lines each contain two integers $i, j$, representing that problem $j$ depends on problem $i$.

The next $N$ lines each contain $K$ integers, representing $t_{ij}$.

The next $K$ lines each contain $K$ integers, representing $r_{ij}$.

Output

For each input file, you need to submit the corresponding output file placement1.out ~ placement10.out.

Each output file should contain one line with $N$ integers, representing the machine assigned to each task.

Examples

Input 1

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

Output 1

1 3 2

Subtasks

Each test case for this problem has ten scoring criteria. If your answer is less than or equal to $k$ of these criteria, you will receive $k$ points for that test case.

These criteria are saved in placement.ans* in the contestant's directory.

Note

To help you test your answers, Xiao He dumped his girlfriend and wrote a simulator for you. You can find an executable file named simulator in your directory. Its usage is to execute ./simulator <input_file> <output_file> in the terminal, where <input_file> is the input file and <output_file> is your answer. It will tell you the total computation time and the completion time of all tasks for your assignment scheme.

Note: Due to the fact that spending time with his girlfriend has reduced Xiao He's programming skills, he cannot guarantee that this simulator will provide correct results for input files not provided by him.

Each answer file must not exceed 10kB (in fact, the size of a valid solution will definitely be less than this limit).