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.</p>

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) mod 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.

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.

The first line contains two integers n - the number of knobs, 1 ≤ n ≤ 300 and the prime number p - the number of possible positions of knobs, 3 ≤ p ≤ 40 000. The following line contains n integers in the range 0...p - 1 - positions, in which successive knobs are located. The third line contains n integers from the range 0...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, ..., c_i,n-1, 0 ≤ c_i,j < p.

출력 형식

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

예제 입력

2 3
1 1
2 2
1 0
0 1

예제 출력

2 2