A settlement system moves money through n accounts, numbered 1 to n, in strict order: account i can only credit accounts j > i.

You are given the n x n integer matrix N, where N[j][i] is the multiplier applied to account i's start-of-tick balance and credited to account j during a tick (N[j][i] = 0 whenever j <= i). At each tick, every account's new balance is its old balance plus all credits received during the tick. You are also given the starting balances v_1, ..., v_n.

The system runs for k ticks. Output the exact final balance of every account.

Input

The first line contains n and k. The next n lines contain the matrix N, row j on line j. The last line contains v_1, ..., v_n.

Output

n integers: the final balances, in order.

Constraints

1 <= n <= 100

0 <= k <= 10^18

|N[j][i]| <= 10, |v_i| <= 10^6, all integers

Scoring

This is a standard problem: a submission scores full points if it produces the correct output for every test case, and zero otherwise.