You want to arrange $k$ people at a table. The table has $n$ rows and $m$ columns. Some of the cells are free and some of them are blocked.

The score of the arrangement is based on two factors:

• Friendship is always important, even with respect to disease. The $i^{th}$ person has a friendship value $f_i$. A connected component of people with the sum of friendship value equal to $s$ adds $s^2$ to score. A connected component is a set of people adjacent to each other. Two people are adjacent if they share a side.
• You need to take care of the health of people. The $i^{th}$ person has a danger value $d_i$. Two adjacent people $i$ and $j$ reduce the score by $d_i \times d_j$.

Your task is to print an arrangement with as high a score as possible. Note that you can drop a person and do not give him a seat at the table.

Input format

• The first line contains $k, n, m$.
• The second line contains array $f$.
• The third line contains array $d$.
• The last $n$ lines contain the table.

Output format

Print $k$ lines. In each line, print the row and column of the $i^{th}$ person in the arrangement. Otherwise, print "0 0" if you do not want to include this person in the arrangement.

Constraints

$n = m = 100$

$1 \le k \le n \times m$

$1 \le d_i, f_i \le 1000$