There are n battlefields with weights w_1, ..., w_n. You have B troops to distribute among them as non-negative integers. You win a battlefield if you place strictly more troops on it than your opponent; ties go to the opponent. You win the war if the total weight of the battlefields you win is strictly more than half of the total weight.

You will face a panel of K opponents, each equally likely. Your intelligence reports each opponent's planned allocation o_k, but it is imperfect: on every battlefield f, opponent k actually fields max(o_{k,f} + e, 0) troops, where e is drawn uniformly from the integers -d_k, ..., d_k, independently across battlefields.

Choose one allocation to face the whole panel.

Input

The first line contains n, B and K. The second line contains the weights w_1, ..., w_n. The third line contains the noise half-widths d_1, ..., d_K. Each of the next K lines contains one opponent's planned allocation: n non-negative integers.

Output

n non-negative integers summing to at most B: your allocation.

Scoring

Your score is the average over the K opponents of the probability that your allocation wins the war against that opponent.

Constraints

5 <= n <= 40

n <= B <= 500

10 <= K <= 200

1 <= w_i <= 100

0 <= d_k <= B / 10

Every opponent's planned allocation sums to at most B.