Problem Description

Little R is a cute girl. She wants to hug everyone, and also share some cake with them.

The cake is a cuboid of size $a\times b\times c$. Each unit cube is given a coordinate $(x,y,z)$, where $1\le x\le a,1\le y\le b,1\le z\le c$.

There are $m$ cake-cutting operations in total. Each operation cuts in one of the following three ways:

1. Cut out the part with $x\le k$ and give it to everyone.
2. Cut out the part with $y\le k$ and give it to everyone.
3. Cut out the part with $z\le k$ and give it to everyone.

Since she also wants to eat cake herself, she wants to know how much volume remains (not given away) after each cut.

Input Format

The first line contains four integers $a,b,c,m$, representing the cake size and the number of cutting operations.

The next $m$ lines each contain two integers $op,k$, meaning the $op$-th type of operation described in the Description, with parameter $k$.

Output Format

Output $m$ lines. Each line contains one integer, representing the volume of the remaining part.

3 3 3 2
1 2
2 1

9
6

1000000 1000000 1000000 6
1 123456
2 654321
3 233333
2 111111
1 333333
3 1000000

876544000000000000
303002853376000000
232302288589217792
232302288589217792
176680542935560631
0

Hint

Explanation for Sample $1$.

After the first cut, all parts with $x\le 2$ are cut off. The remaining unit cubes are $(3,1,1),(3,1,2),(3,1,3),(3,2,1),(3,2,2),(3,2,3),(3,3,1),(3,3,2),(3,3,3)$, a total of $9$ cubes.

After the second cut, all parts with $y\le 1$ are cut off. The remaining unit cubes are $(3,2,1),(3,2,2),(3,2,3),(3,3,1),(3,3,2),(3,3,3)$, a total of $6$ cubes.

Explanation for Sample $2$.

The fourth cut has no effect, because in the second cut, the part with $y\le 654321$ had already been removed. At that time, there were no unit cubes with $y\le 111111$ left.

Note that the parameter $k$ in each operation is an absolute coordinate decided at the beginning, and it does not change as operations proceed.

Constraints.

There are $20$ test points in total, $5$ points each.

For all testdata, it is guaranteed that $1\le a,b,c\le 10^6$, $1\le m\le 2\times 10^5$, $op\in\{1,2,3\}$. If $op=1$, then $1\le k\le a$; if $op=2$, then $1\le k\le b$; if $op=3$, then $1\le k\le c$.

• For test points $1\sim 5$, it is guaranteed that $a,b,c,m\le 100$.
• For test points $6\sim 10$, it is guaranteed that $b=c=1$ and $op=1$.
• For test points $11\sim 15$, it is guaranteed that $c=1$ and $op\in\{1,2\}$.
• For test points $16\sim 20$, there are no special constraints.

Translated by ChatGPT 5