凯伦刚从超市回到家,正准备睡觉。
洗完澡,换上睡衣,她看向架子,看到了一张相册。出于好奇,她打开它,看到了一张交易卡集。
她回忆起自己小时候经常玩这些卡片,尽管她现在已经长大了,但她仍然对其中的一些事情感到好奇。
每张卡牌都具有三个特性:力量、防御和速度。所有卡牌的所有特征值均为正整数。任何卡牌可以拥有的最大可能强度为 p,最大可能防御为 q,最大可能速度为 r。
她的收藏中有 n 张卡片。第 i 张卡牌的强度分别为 ai,防御力为 bi,速度为 ci。
如果一张牌的至少两个特征严格大于另一张牌的相应特征,则该牌击败另一张牌。
她现在想知道有多少张不同的牌可以击败她收藏中的所有牌。如果两张牌的至少一个特征具有不同的值,则两张牌被视为不同。
输入
输入的第一行包含四个整数,n、p、q 和 r(1 ≤ n、p、q、r ≤ 500000),分别表示集合中的卡牌数量、最大可能强度、最大可能防御和最大可能速度。
接下来的 n 行每行包含三个整数。特别地,第i行包含ai、bi和ci(1≤ai≤p,1≤bi≤q,1≤ci≤r),分别表示第i张收集卡的强度、防御和速度。
输出
在一行中单独输出一个整数,即可以击败她收集的所有纸牌的不同纸牌的数量。
示例
输入 #1
3 4 4 5 2 2 5 1 3 4 4 1 1
输出 #1
10
输入 #2
5 10 10 10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
输出 #2
972
注意
在第一个测试用例中,最大可能的强度为 4,最大可能的防御为 4,最大可能的速度为 5。凯伦有三张牌:
- 第一张牌的强度为 2,防御为 2,速度为 5。
- 第二张牌的强度为 1,防御为 3,速度为 4。
- 第三张牌的强度为 4,防御为 1,速度为 1。
有 10 张牌可以击败这里的所有牌:
1.力量3、防御3、速度5的卡牌。
2. 强度为3、防御为4、速度为2的卡牌。
3. 力量为3、防御为4、速度为3的卡牌。
4. 强度为3、防御为4、速度为4的卡牌。
5. 力量为3、防御为4、速度为5的卡牌。
6. 强度为4、防御为3、速度为5的卡牌。
7. 强度为4、防御为4、速度为2的卡牌。
8. 强度为 4、防御为 4、速度为 3 的卡牌。
9. 强度为4、防御为4、速度为4的卡牌。
10. 强度4、防御4、速度5的卡牌。
在第二个测试用例中,最大可能的强度为 10,最大可能的防御为 10,最大可能的速度为 10。凯伦有五张牌,全部强度为 1,防御为 1,速度为 1。
972张卡牌中至少有两个特征大于1的卡牌中的任何一张都可以击败她收藏的所有卡牌。