There are two water tanks, the first one fits $$$a$$$ liters of water, the second one fits $$$b$$$ liters of water. The first tank has $$$c$$$ ($$$0 \le c \le a$$$) liters of water initially, the second tank has $$$d$$$ ($$$0 \le d \le b$$$) liters of water initially.

You want to perform $$$n$$$ operations on them. The $$$i$$$-th operation is specified by a single non-zero integer $$$v_i$$$. If $$$v_i \gt 0$$$, then you try to pour $$$v_i$$$ liters of water from the first tank into the second one. If $$$v_i \lt 0$$$, you try to pour $$$-v_i$$$ liters of water from the second tank to the first one.

When you try to pour $$$x$$$ liters of water from the tank that has $$$y$$$ liters currently available to the tank that can fit $$$z$$$ more liters of water, the operation only moves $$$\min(x, y, z)$$$ liters of water.

For all pairs of the initial volumes of water $$$(c, d)$$$ such that $$$0 \le c \le a$$$ and $$$0 \le d \le b$$$, calculate the volume of water in the first tank after all operations are performed.

Input

The first line contains three integers $$$n, a$$$ and $$$b$$$ ($$$1 \le n \le 10^4$$$; $$$1 \le a, b \le 1000$$$) — the number of operations and the capacities of the tanks, respectively.

The second line contains $$$n$$$ integers $$$v_1, v_2, \dots, v_n$$$ ($$$-1000 \le v_i \le 1000$$$; $$$v_i \neq 0$$$) — the volume of water you try to pour in each operation.

Output

For all pairs of the initial volumes of water $$$(c, d)$$$ such that $$$0 \le c \le a$$$ and $$$0 \le d \le b$$$, calculate the volume of water in the first tank after all operations are performed.

Print $$$a + 1$$$ lines, each line should contain $$$b + 1$$$ integers. The $$$j$$$-th value in the $$$i$$$-th line should be equal to the answer for $$$c = i - 1$$$ and $$$d = j - 1$$$.

Note

Consider $$$c = 3$$$ and $$$d = 2$$$ from the first example:

The first operation tries to move $$$2$$$ liters of water from the second tank to the first one, the second tank has $$$2$$$ liters available, the first tank can fit $$$1$$$ more liter. Thus, $$$\min(2, 2, 1) = 1$$$ liter is moved, the first tank now contains $$$4$$$ liters, the second tank now contains $$$1$$$ liter.
The second operation tries to move $$$1$$$ liter of water from the first tank to the second one. $$$\min(1, 4, 3) = 1$$$ liter is moved, the first tank now contains $$$3$$$ liters, the second tank now contains $$$2$$$ liter.
The third operation tries to move $$$2$$$ liter of water from the first tank to the second one. $$$\min(2, 3, 2) = 2$$$ liters are moved, the first tank now contains $$$1$$$ liter, the second tank now contains $$$4$$$ liters.

There's $$$1$$$ liter of water in the first tank at the end. Thus, the third value in the fourth row is $$$1$$$.

Idx	Name	Rating
A	Garland	800
B	Points on Plane	1000
C	Sum on Subarrays	1500
D	Binary String Sorting	1800
E	Two Tanks	2400
F	Traveling in Berland	2500
G	Prediction	2800

Educational Codeforces Round 145 (Rated for Div. 2)