Есть две бочки — в первую помещается \(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\), посчитайте объем воды в первой бочке после применения всех действий.
Выходные данные
Для всех пар начальных объемов воды \((c, d)\) таких, что \(0 \le c \le a\) и \(0 \le d \le b\), посчитайте объем воды в первой бочке после применения всех действий.
Выведите \(a + 1\) строку, в каждой строке должно быть \(b + 1\) целых чисел. \(j\)-е значение в \(i\)-й строке должно быть ответом для \(c = i - 1\) и \(d = j - 1\).
Примечание
Рассмотрим \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
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
|
|
2
|
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
|