310283: CF1809E. Two Tanks

E. Two Tankstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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 > 0$, then you try to pour $v_i$ liters of water from the first tank into the second one. If $v_i < 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$.

ExamplesInput

3 4 4
-2 1 2

Output

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 

Input

3 9 5
1 -2 2

Output

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 

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$.

题目大意：
有两个水罐，第一个容量为a升，第二个容量为b升。第一个罐最初有c升水（0≤c≤a），第二个罐最初有d升水（0≤d≤b）。需要进行n次操作，每次操作由一个非零整数vi表示。如果vi>0，则尝试从第一个罐向第二个罐倒vi升水；如果vi<0，则尝试从第二个罐向第一个罐倒-vi升水。尝试从一个装有y升水的罐向一个还能装z升水的罐倒x升水时，实际只移动min(x, y, z)升水。对于所有初始水量(c, d)对，计算所有操作完成后第一个罐中的水量。

输入数据格式：
第一行包含三个整数n, a和b（1≤n≤10^4；1≤a, b≤1000）——操作次数和罐的容量。
第二行包含n个整数v1, v2, …, vn（-1000≤vi≤1000；vi≠0）——每次操作的倒水量。

输出数据格式：
对于所有初始水量(c, d)对，计算所有操作完成后第一个罐中的水量。
打印a+1行，每行包含b+1个整数。第i行第j个值应为c=i-1和d=j-1时的答案。

请注意，由于您请求的是仅题目大意以及输入输出数据格式，因此未提供详细的LaTeX格式的数学公式。如果需要公式的LaTeX表示，请明确指出哪个公式需要转换。题目大意： 有两个水罐，第一个容量为a升，第二个容量为b升。第一个罐最初有c升水（0≤c≤a），第二个罐最初有d升水（0≤d≤b）。需要进行n次操作，每次操作由一个非零整数vi表示。如果vi>0，则尝试从第一个罐向第二个罐倒vi升水；如果vi<0，则尝试从第二个罐向第一个罐倒-vi升水。尝试从一个装有y升水的罐向一个还能装z升水的罐倒x升水时，实际只移动min(x, y, z)升水。对于所有初始水量(c, d)对，计算所有操作完成后第一个罐中的水量。 输入数据格式： 第一行包含三个整数n, a和b（1≤n≤10^4；1≤a, b≤1000）——操作次数和罐的容量。 第二行包含n个整数v1, v2, …, vn（-1000≤vi≤1000；vi≠0）——每次操作的倒水量。 输出数据格式： 对于所有初始水量(c, d)对，计算所有操作完成后第一个罐中的水量。 打印a+1行，每行包含b+1个整数。第i行第j个值应为c=i-1和d=j-1时的答案。 请注意，由于您请求的是仅题目大意以及输入输出数据格式，因此未提供详细的LaTeX格式的数学公式。如果需要公式的LaTeX表示，请明确指出哪个公式需要转换。