G. Game With Stones
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Porfiry and Rodion are playing with stones. They have a pile of $$$m$$$ stones, and $$$n$$$ boxes, arranged in a row. They consider different distributions of all stones to boxes. Each such distribution can be described with $$$n$$$ non-negative integers $$$a_1, a_2, \dots, a_n$$$ such that $$$a_1+a_2+\dots+a_n = m$$$.

Rodion loves to move stones from a pile to adjacent one. In one step, he can take exactly one stone from some non-empty box and put it to one of adjacent boxes. For two distributions $$$a=(a_i)$$$ and $$$b=(b_i)$$$, Porfiry defined value $$$W(a, b)$$$ as minimum number of Rodion's moves required to transform distribution $$$a$$$ to distribution $$$b$$$.

After some observation, Porfiry gave Rodion the following task: given $$$k$$$ distributions $$$(a^1_i), (a^2_i), \dots, (a_i^k)$$$, find distribution $$$b$$$, such that the total distance $$$W(a^1, b) + W(a^2, b) + \dots + W(a^k, b)$$$ is minimum possible.

Input

The first line of the input contains three space-separated integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$1 \leq n, k \leq 1000$$$, $$$1 \leq m \leq 10^9$$$).

The $$$j$$$-th of the following $$$k$$$ lines contains a description of the $$$j$$$-th distribution, represented by $$$n$$$ non-negative integers $$$a^j_1, a^j_2 \dots, a^j_n$$$ ($$$a^j_1 + a^j_2 + \dots + a^j_n = m$$$).

Output

Output optimal distribution $$$b$$$. If there is more than one optimal answer, print any of them.

Example
Input
4 10 3
1 2 3 4
4 2 1 3
1 3 4 2
Output
1 3 3 3