The great human god clevertick, in order to process the data used by his test robots, created a processor named CTEX (CleverTick's Editing eXecutor).

The model of CTEX consists of several nodes and some transitions between nodes (which can be viewed as directed edges). The model has exactly one initial node and at least one terminal node. The initial node cannot be a terminal node.

Some nodes may have an output device, and the type of the output device is represented by an integer from $0$ to $S-1$. An output device of type $v$ can write a $v$ at the end of the paper tape when the pointer (the pointer of CTEX will be described later) reaches the node where the device is located.

Except for terminal nodes, every node has at least one transition originating from it, labeled with an integer from $0$ to $S-1$. The CTEX model guarantees that there are no two transitions originating from the same node that are labeled with the same value.

The text to be processed is recorded on a paper tape as a sequence of non-negative integers (all subsequent read and write operations are performed on this tape), and the range of integers in the sequence is $0$ to $S-1$. The processor has a pointer that starts at the initial node.

When CTEX starts, if there is an output device at the initial node, it writes a value representing the type of that output device at the end of the paper tape. After that, it repeats the following steps until it terminates:

The processor first checks whether the current node of the pointer is a terminal node. If it is a terminal node, it prints the current content of the paper tape, and the processor terminates normally. If it is not a terminal node, and if the current paper tape is empty (no values left), the processor terminates abnormally (outputs an error message and then terminates). If the paper tape is not empty, it performs the following operations:

Read a value from the beginning of the paper tape, let it be $v$, and remove this value from the paper tape. Then the processor checks whether there is a transition originating from the current node of the pointer labeled with $v$. If it exists, the pointer moves to the node reached by this transition; if there is no transition labeled with $v$, the position of the pointer does not change (i.e., it stays at the original node). After completing the node transition operation, if there is an output device at the node where the pointer is currently located, it writes a value representing the type of that output device at the end of the paper tape; if there is no output device, it writes nothing.

clevertick used CTEX to process a lot of text, which greatly facilitated his work in testing robots. Unfortunately, the anti-humanists eventually destroyed CTEX. One day, clevertick discovered that CTEX had been destroyed—only the nodes and transitions remained, while the values written on the transitions and the output devices on the nodes were all lost.

clevertick decided to use previously recorded information to restore CTEX. The information he previously recorded includes which texts he had processed using CTEX and their corresponding output results (paper tape content or abnormal termination information). In addition, he could also estimate the probability of each value being written on each transition and the probability of each type of output device existing on each node from previous records. To represent these probabilities, he assigned a cost value to each probability, where this value is inversely proportional to the logarithm of the corresponding probability. Regarding this cost value, we have a conjecture: for a CTEX restoration scheme, the smaller the sum of the cost values of the required information (the values written on transitions and the output device types), the greater the probability, and the greater the possibility that it is the original processor.

The problem is, clevertick no longer has enough time to restore CTEX, so he has handed this task to you, the master, and hopes you can help him complete it.

Input

This is an answer-submission problem. The input files ctex1.in~ctex10.in are already in the problem directory.

The first line of the input contains four integers $N, M, S, Z$, representing the number of nodes, the number of transitions, the range of elements in the sequence (integers), and the number of texts processed by CTEX, respectively.

The next line contains $N$ integers. The $i$-th integer represents the information of the node numbered $i-1$. If the value is $0$, it means it is neither an initial node nor a terminal node; if the value is $1$, it means it is an initial node; if the value is $2$, it means it is a terminal node.

The next $M$ lines each contain two integers $u$ and $v$ ($0 \le u, v < N$), where the $i$-th line indicates that there is a transition labeled $i-1$ from node $u$ to node $v$.

The next $N$ lines each contain $S+1$ non-negative integers. The $j$-th integer of the $i$-th line represents the cost value of an output device of type $j-1$ existing on node $i-1$. The $(S+1)$-th integer of the $i$-th line represents the cost value of no output device existing on node $i-1$.

The next $M$ lines each contain $S$ non-negative integers, where the $j$-th integer of the $i$-th line ($1 \le i \le M, 1 \le j \le S$) represents the cost value of the value $j-1$ being written on the transition numbered $i-1$.

The next $2Z$ lines consist of $Z$ parts. The first line of each part represents an input text processed by CTEX, and the second line represents the corresponding output or a string "-1 Error" (indicating the processor terminated abnormally, outputting an error message). If a line represents a sequence, the first integer $l$ in that line represents the length of the sequence, followed by $l$ integers representing this sequence.

Output

For the given 10 input files ctex1.in~ctex10.in, you need to submit your output files ctex1.out~ctex10.out respectively.

The output contains two lines, representing the CTEX construction you provide.

The first line contains $N$ space-separated integers, representing the output device types on nodes $0$ to $N-1$, using $-1$ to indicate that no output device exists.

The second line contains $M$ space-separated integers, representing the values written on transitions $0$ to $M-1$. These must be in the range $0$ to $S-1$, and it is not allowed for two transitions originating from the same node to have the same value.

Examples

Input 1

4 8 3 5
1 0 0 2
0 1
0 2
1 1
1 2
2 1
2 2
1 3
2 3
1 1 1 2
1 2 1 2
2 1 1 2
1 1 2 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
2 2 2
2 2 2
1 0
1 1
3 0 1 1
3 1 0 0
4 0 0 1 1
4 1 1 0 0
6 0 1 0 0 1 0
6 1 0 1 1 0 1
11 1 0 0 1 1 1 0 0 1 0 1
11 0 1 1 0 0 0 1 1 0 1 0

Output 1

2 0 1 -1
1 0 1 0 1 0 2 2

Note

One feasible scheme is to construct a processor that can invert the input text (0 becomes 1, 1 becomes 0) (as shown in the figure).

The sum of the cost values for this scheme is 14, which can be proven to be the minimum value satisfying the requirements.

Subtasks

For each set of data, if you do not submit the corresponding output file, the submitted output file has a format error, or after restoring the CTEX according to your output, its construction does not meet the problem requirements or the output results for any of the texts in the input file do not match the data (the processor execution time exceeds 20120526 units), you will receive 0 points.

Otherwise, for each set of data, we have 9 parameters (the parameters will not be given in the input data), denoted as $a_1, a_2, \dots, a_9$, where $a_1 > a_2 > \dots > a_9 > 0$. Let $total\_cost$ be the sum of the cost values in the scheme you provided for this set of data. Your score for this set of data is shown in the table below: