ByteGuy owns a strong-box protected with a lock. This lock has $n$ knobs. Each knob can be situated in one of $p$ possible positions.

ByteGuy has not used his strong-box for a long time now, so he has forgotten the configuration of knobs which opens the strong-box. He went to the company producing locks, where he learned about construction of the lock. It consists of $n$ knobs and the same number of bolts. All of them (both bolts and knobs) can be in one of $p$ allowed positions numbered from $0$ to $p - 1$. The lock opens, when all of the bolts are set to the position $0$. Turning $i$-th knob by one position (from position $0$ to $1$, from $1$ to $2$, ..., from $p - 2$ to $p - 1$, from $p - 1$ to $0$) causes, that $j$-th bolt rotates by $c_{i,j}$ positions (from position $l$ to $(l + c_{i,j}) \bmod p$). The manufacturer of locks helped ByteGuy and gave him a modern 3D-scaner, which allowed to check the configuration of the bolts hidden inside a strong-box.

Locks manufactured for strong-boxes are of high quality and there is only one configuration of knobs which opens the lock.

Task

Write a program, which:

• reads the description of a lock in ByteGuys's strong-box,
• computes the configuration of knobs which opens the lock,
• writes the result to the standard output.

Input

The first line contains two integers $n$ - the number of knobs, $1 \le n \le 300$ and the prime number $p$ - the number of possible positions of knobs, $3 \le p \le 40\,000$. The following line contains $n$ integers in the range $0 \ldots p - 1$ - positions, in which successive knobs are located. The third line contains $n$ integers from the range $0 \ldots p - 1$ - positions of consecutive bolts of ByteGuy's strong-box. Following $n$ lines contain descriptions of consecutive knobs - $i$-th of these lines contains exactly $n$ integers - $c_{i,0}$, $c_{i,1}$, $\ldots$, $c_{i,n-1}$, $0 \le c_{i,j} < p$.

Output

The only line of output should contain $n$ integers from the range $0 \ldots p - 1$, separated with single spaces - the configuration of knobs which opens the lock.

Example

Input

2 3
1 1
2 2
1 0
0 1

Output

2 2