E. Две бочки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Есть две бочки — в первую помещается $$$a$$$ литров воды, во вторую помещается $$$b$$$ литров воды. В первой бочке изначально $$$c$$$ ($$$0 \le c \le a$$$) литров воды, во второй бочке изначально $$$d$$$ ($$$0 \le d \le b$$$) литров воды.

Вы хотите провести $$$n$$$ действий над ними. $$$i$$$-е действие задается одним ненулевым целым числом $$$v_i$$$. Если $$$v_i > 0$$$, то вы пытаетесь налить $$$v_i$$$ литров воды из первой бочки во вторую. Если $$$v_i < 0$$$, то вы пытаетесь налить $$$-v_i$$$ литров воды из второй бочки в первую.

Когда вы пытаетесь налить $$$x$$$ литров воды из бочки, в которой сейчас $$$y$$$ литров воды, в бочку, в которой может поместиться еще $$$z$$$ литров воды, то за действие вы перельете только $$$\min(x, y, z)$$$ литров воды.

Для всех пар начальных объемов воды $$$(c, d)$$$ таких, что $$$0 \le c \le a$$$ и $$$0 \le d \le b$$$, посчитайте объем воды в первой бочке после применения всех действий.

Входные данные

В первой строке записаны три целых числа $$$n, a$$$ и $$$b$$$ ($$$1 \le n \le 10^4$$$; $$$1 \le a, b \le 1000$$$) — количество действий и вместимости бочек, соответственно.

Во второй строке записаны $$$n$$$ целых чисел $$$v_1, v_2, \dots, v_n$$$ ($$$-1000 \le v_i \le 1000$$$; $$$v_i \neq 0$$$) — объем воды, который вы пытаетесь перелить в каждом действии.

Выходные данные

Для всех пар начальных объемов воды $$$(c, d)$$$ таких, что $$$0 \le c \le a$$$ и $$$0 \le d \le b$$$, посчитайте объем воды в первой бочке после применения всех действий.

Выведите $$$a + 1$$$ строку, в каждой строке должно быть $$$b + 1$$$ целых чисел. $$$j$$$-е значение в $$$i$$$-й строке должно быть ответом для $$$c = i - 1$$$ и $$$d = j - 1$$$.

Примеры
Входные данные
3 4 4
-2 1 2
Выходные данные
0 0 0 0 0 
0 0 0 0 1 
0 0 1 1 2 
0 1 1 2 3 
1 1 2 3 4
Входные данные
3 9 5
1 -2 2
Выходные данные
0 0 0 0 0 0 
0 0 0 0 0 1 
0 1 1 1 1 2 
1 2 2 2 2 3 
2 3 3 3 3 4 
3 4 4 4 4 5 
4 5 5 5 5 6 
5 6 6 6 6 7 
6 7 7 7 7 8 
7 7 7 7 8 9
Примечание

Рассмотрим $$$c = 3$$$ и $$$d = 2$$$ из первого примера:

  • В первом действии вы пытаетесь перелить $$$2$$$ литра воды из второй бочки в первую, во второй бочке есть $$$2$$$ литра воды, в первую поместится еще $$$1$$$ литр. Поэтому переливается $$$\min(2, 2, 1) = 1$$$ литр, в первой бочке теперь $$$4$$$ литра, во второй $$$1$$$ литр.
  • Во втором действии вы пытаетесь перелить $$$1$$$ литр воды из первой бочки во вторую. Переливается $$$\min(1, 4, 3) = 1$$$ литр, в первой бочке теперь $$$3$$$ литра, во второй $$$2$$$ литра.
  • В третьем действии вы пытаетесь перелить $$$2$$$ литра воды из первой бочки во вторую. Переливается $$$\min(2, 3, 2) = 2$$$ литра, в первой бочке теперь $$$1$$$ литр, во второй $$$4$$$ литра.

В конце в первой бочке $$$1$$$ литр воды. Поэтому третье значение в четвертой строке равно $$$1$$$.