Cake Sharing

Little R is a cute girl who wants to give everyone a hug and share a cake with them. The cake is a rectangular cuboid of size \(a\times b\times c\). Each unit cube in the cake is assigned a coordinate \((x,y,z)\) with \(1 \le x \le a\), \(1 \le y \le b\), \(1 \le z \le c\).

There are \(m\) cake-cutting operations. In each operation, one of the following three cuts is performed on the remaining cake:

1. Cut the part with \(x \le k\) and give it away.
2. Cut the part with \(y \le k\) and give it away.
3. Cut the part with \(z \le k\) and give it away.

After each operation, output the remaining volume of the cake that has not been given away.

Note: The cake is represented by its remaining axis-aligned rectangular region. For a cut of type 1, if the current remaining cake has its x-coordinate starting from \(L_x\), then after cutting with parameter \(k\), the new starting x-coordinate becomes \(\max(L_x, k+1)\), and similarly for types 2 and 3. The remaining volume is computed as:

\[ \text{Volume} = \max(0, a - L_x + 1) \times \max(0, b - L_y + 1) \times \max(0, c - L_z + 1) \]

inputFormat

The first line contains four integers \(a\), \(b\), \(c\) and \(m\) \( (1 \le a,b,c \le 10^9, 1 \le m \le 10^5)\), representing the dimensions of the cake and the number of operations.

Each of the next \(m\) lines contains two integers \(op\) and \(k\) \((op \in \{1,2,3\}, 1 \le k \le 10^9)\). \(op=1\) indicates a cut along the \(x\)-axis (i.e. remove all cubes with \(x\le k\)); \(op=2\) indicates a cut along the \(y\)-axis; and \(op=3\) indicates a cut along the \(z\)-axis.

outputFormat

Output \(m\) lines. The \(i\)-th line should contain one integer representing the remaining volume of the cake after the \(i\)-th cut operation.

sample

5 4 3 3
1 2
2 1
3 2

36
27
9