题目描述
小 R 是一个可爱的女孩子,她希望跟大家抱抱,顺便给大家分蛋糕吃。
蛋糕是一个大小为 a×b×c 的长方体,其中每个单位正方体都被赋予了一个坐标 (x,y,z)(1≤x≤a,1≤y≤b,1≤z≤c)。
共进行 m 次切蛋糕操作,每次按如下三种方式之一切分:
- 切出 x≤k 的部分分给大家。
- 切出 y≤k 的部分分给大家。
- 切出 z≤k 的部分分给大家。
由于她自己也想吃蛋糕,她希望知道在每次切蛋糕后,还剩下多少体积没有分给大家。
输入格式
第一行四个整数 a,b,c,m,表示蛋糕的大小和切蛋糕次数。
接下来 m 行,每行两个整数 op,k,表示进行【题目描述】中的第 op 种操作,参数为 k。
输出格式
m 行,每行一个整数,表示剩余部分体积。
提示
样例 1 解释
第一次切蛋糕,将所有 x≤2 的部分切掉,剩余的单位正方体有 (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) 共 9 个。
第二次切蛋糕,将所有 y≤1 的部分切掉,剩余的单位正方体有 (3,2,1),(3,2,2),(3,2,3),(3,3,1),(3,3,2),(3,3,3) 共 6 个。
样例 2 解释
第四次切蛋糕没有任何作用,因为第二次切蛋糕时 y≤654321 的部分已经被切掉,此时已经不存在 y≤111111 的单位正方体。
注意每次操作中的参数 k 是初始时决定的绝对坐标,不会随着操作的进行而改变。
数据范围
本题共 20 个测试点,每个测试点 5 分。
对于全部数据,保证 1≤a,b,c≤106,1≤m≤2×105,op∈{1,2,3},若 op=1 则 1≤k≤a,若 op=2 则 1≤k≤b,若 op=3 则 1≤k≤c。
- 对于测试点 1∼5:保证 a,b,c,m≤100。
- 对于测试点 6∼10:保证 b=c=1,op=1。
- 对于测试点 11∼15:保证 c=1,op∈{1,2}。
- 对于测试点 16∼20:无特殊限制。