Story

You have been hired as a project leader of F Corporation. Your job is to assign tasks to team members appropriately. The current project consists of a number of tasks. The expected number of days for a team member to complete a task depends on skill levels of the team member and required skill levels for the task. You are highly experienced and can accurately estimate the required skill levels for each task, but since you have just joined the team, you do not yet know the skill levels of each team member at all. Please assign tasks appropriately while gradually evaluating the skill levels of team members.

Problem Statement

You want to assign $N$ tasks to $M$ team members. You can assign each task to at most one team member, and once you assign a task to a team member, you cannot assign another task to him/her until he/she completes the task. There are $K$ types of skills. Each team member $j$ has a non-negative integer vector $\\bm{s_j} = (s_{j,1},\\cdots,s_{j,K})$ representing skill levels, and each task $i$ has a non-negative integer vector $\\bm{d_i} = (d_{i,1},\\cdots,d_{i,K})$ representing required skill levels. Among these, the skill levels $\\bm{s_1},\\cdots,\\bm{s_M}$ are not given as input.

We define $w_{i,j}:=\\sum_{k=1}^K \\max(0,d_{i,k}-s_{j,k})$. Then, it takes $t_{i,j}$ days for team member $j$ to complete task $i$, where $t_{i,j}$ is defined as follows.

1. If $w_{i,j}=0$, $t_{i,j}=1$.
2. If $w_{i,j}>0$, $t_{i,j}=\\max(1,w_{i,j}+r_i)$, where $r_i$ is a uniform random integer between $\-3$ and $3$, inclusive.

When a task taking $t$ days is started on day $d$, the task will be completed at the end of day $d+t-1$. There are dependencies between tasks, and before starting a task, all of its dependent tasks must have been completed by the end of the previous day. Please complete all tasks in as few days as possible.

Input and Output

For the range of each input value, see Input Generation.

At the start of the execution, the number of tasks $N$, the number of team members $M$, the number of skills $K$, the number of dependencies $R$, required skill levels for each task $\\bm{d_1},\\cdots,\\bm{d_N}$, and a list of pairs of dependent tasks $(u_1,v_1),\\cdots,(u_R,v_R)$ are given from Standard Input in the following format.

$N$ $M$ $K$ $R$ $d_{1,1}$ $\\cdots$ $d_{1,K}$ $\\vdots$ $d_{N,1}$ $\\cdots$ $d_{N,K}$ $u_1$ $v_1$ $\\vdots$ $u_R$ $v_R$

$(u_i,v_i)$ indicates that the task $v_i$ ($1\\leq v_i\\leq N$) depends on the task $u_i$ ($1\\leq u_i\\leq N$) and that $u_i$ must be completed before starting $v_i$. It satisfies $u_i<v_i$, and the same $(u_i,v_i)$ pair appears at most once in the input.

Then, starting from day 1, do the following two processes every day.

First, output to Standard Output a list of pairs $(a_1,b_1),\\cdots,(a_m,b_m)$ such that team member $a_i$ ($1\\leq a_i\\leq M$) starts task $b_i$ ($1\\leq b_i\\leq N$) on that day in one line in the following format.

$m$ $a_1$ $b_1$ $\\cdots$ $a_m$ $b_m$

After the output, you have to flush Standard Output. Otherwise, the submission might be judged as TLE