#2043. 「QFOI R1」抱抱

「QFOI R1」抱抱

题目描述

小 R 是一个可爱的女孩子,她希望跟大家抱抱,顺便给大家分蛋糕吃。

蛋糕是一个大小为 a×b×ca\times b\times c 的长方体,其中每个单位正方体都被赋予了一个坐标 (x,y,z)(x,y,z)(1≤x≤a,1≤y≤b,1≤z≤c1\le x\le a,1\le y\le b,1\le z\le c)。

共进行 mm 次切蛋糕操作,每次按如下三种方式之一切分:

  1. 切出 x≤kx\le k 的部分分给大家。
  2. 切出 y≤ky\le k 的部分分给大家。
  3. 切出 z≤kz\le k 的部分分给大家。

由于她自己也想吃蛋糕,她希望知道在每次切蛋糕后,还剩下多少体积没有分给大家。

输入格式

第一行四个整数 a,b,c,ma,b,c,m,表示蛋糕的大小和切蛋糕次数。

接下来 mm 行,每行两个整数 op,kop,k,表示进行【题目描述】中的第 opop 种操作,参数为 kk。

输出格式

mm 行,每行一个整数,表示剩余部分体积。

样例

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

题目来源:洛谷 P9713