Boating to the shop

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Zenyk knows that "4/7" convenience stores, which offer discounts on sandwich ingredients, are located in villages along the Dniester River. He found a boat in the dormitory (you can find anything in there) and plans to sail on it for cheap ingredients. All he knows about this river is that initially \(w\) liters of water flow through it per hour, and also along the river there are \(n\) villages with streams flowing into the Dniester.

Zenyk will do everything to get food, so he decided that he needs to find out for each village how many liters of water per hour flow in the Dniester past that village. He knows the order of the villages along the river, as well as how many streams before the corresponding village flow into the Dniester and how many liters of water per hour flow through each of them. Help him determine the required information.

Input

The first line contains two integers \(n\) and \(w\) — the number of villages and the initial amount of water flowing per hour of time.

The next \(n\) lines contain information about the streams in the corresponding village in the following format: the first number in the line \(k\) corresponds to the number of streams in this village, followed by \(k\) integers \(v_i\) — how much water flows per hour in the corresponding stream.

The villages are given in the order along the river flow.

Output

Output \(n\) numbers, one per line: the number of liters of water per hour flowing in the Dniester past the corresponding village (in the order they are given).

Constraints

\(1 \le n, k \le 10^5\),

the sum over all \(k \le 10^5\),

\(15\) tests with constraints \(1 \le w, v_i \le 10^4\),

\(10\) tests with constraints \(1 \le w, v_i \le 10^9\).

Samples

Input (stdin) сopy	Output (stdout) сopy
3 4 3 1 1 5 2 4 7 2 7 11	11 22 40

Notes

Note that the streams increase the amount of water flowing in the Dniester per hour.