English · Original
Chinese · Translation
Formal · Original
Karen just got home from the supermarket, and is getting ready to go to sleep.
<center></center>After taking a shower and changing into her pajamas, she looked at her shelf and saw an album. Curious, she opened it and saw a trading card collection.
She recalled that she used to play with those cards as a child, and, although she is now grown-up, she still wonders a few things about it.
Each card has three characteristics: _strength_, _defense_ and _speed_. The values of all characteristics of all cards are positive integers. The maximum possible strength any card can have is _p_, the maximum possible defense is _q_ and the maximum possible speed is _r_.
There are _n_ cards in her collection. The _i_\-th card has a strength _a__i_, defense _b__i_ and speed _c__i_, respectively.
A card _beats_ another card if at least two of its characteristics are _strictly greater_ than the corresponding characteristics of the other card.
She now wonders how many different cards can beat all the cards in her collection. Two cards are considered different if at least one of their characteristics have different values.
## Input
The first line of input contains four integers, _n_, _p_, _q_ and _r_ (1 ≤ _n_, _p_, _q_, _r_ ≤ 500000), the number of cards in the collection, the maximum possible strength, the maximum possible defense, and the maximum possible speed, respectively.
The next _n_ lines each contain three integers. In particular, the _i_\-th line contains _a__i_, _b__i_ and _c__i_ (1 ≤ _a__i_ ≤ _p_, 1 ≤ _b__i_ ≤ _q_, 1 ≤ _c__i_ ≤ _r_), the strength, defense and speed of the _i_\-th collection card, respectively.
## Output
Output a single integer on a line by itself, the number of different cards that can beat all the cards in her collection.
[samples]
## Note
In the first test case, the maximum possible strength is 4, the maximum possible defense is 4 and the maximum possible speed is 5. Karen has three cards:
* The first card has strength 2, defense 2 and speed 5.
* The second card has strength 1, defense 3 and speed 4.
* The third card has strength 4, defense 1 and speed 1.
There are 10 cards that beat all the cards here:
1. The card with strength 3, defense 3 and speed 5.
2. The card with strength 3, defense 4 and speed 2.
3. The card with strength 3, defense 4 and speed 3.
4. The card with strength 3, defense 4 and speed 4.
5. The card with strength 3, defense 4 and speed 5.
6. The card with strength 4, defense 3 and speed 5.
7. The card with strength 4, defense 4 and speed 2.
8. The card with strength 4, defense 4 and speed 3.
9. The card with strength 4, defense 4 and speed 4.
10. The card with strength 4, defense 4 and speed 5.
In the second test case, the maximum possible strength is 10, the maximum possible defense is 10 and the maximum possible speed is 10. Karen has five cards, all with strength 1, defense 1 and speed 1.
Any of the 972 cards which have at least two characteristics greater than 1 can beat all of the cards in her collection.
Karen 刚从超市回家，准备去睡觉。
洗完澡并换上睡衣后，她看向书架，发现了一本相册。出于好奇，她打开一看，里面是一套集换式卡片。
她回忆起小时候曾玩过这些卡片，尽管现在长大了，她仍对一些事情感到好奇。
每张卡片有三个属性：_力量_、_防御_和_速度_。所有卡片的所有属性值均为正整数。任意卡片可能的最大力量为 #cf_span[p]，最大防御为 #cf_span[q]，最大速度为 #cf_span[r]。
她的收藏中有 #cf_span[n] 张卡片。第 #cf_span[i] 张卡片的力量为 #cf_span[ai]，防御为 #cf_span[bi]，速度为 #cf_span[ci]。
一张卡片 _击败_ 另一张卡片，当且仅当它的至少两个属性 _严格大于_ 对应属性的另一张卡片。
她现在想知道，有多少张不同的卡片能击败她收藏中的所有卡片。两张卡片被认为是不同的，当且仅当至少有一个属性的值不同。
输入的第一行包含四个整数：#cf_span[n], #cf_span[p], #cf_span[q] 和 #cf_span[r]（#cf_span[1 ≤ n, p, q, r ≤ 500000]），分别表示收藏中的卡片数量、可能的最大力量、最大防御和最大速度。
接下来的 #cf_span[n] 行，每行包含三个整数。具体而言，第 #cf_span[i] 行包含 #cf_span[ai], #cf_span[bi] 和 #cf_span[ci]（#cf_span[1 ≤ ai ≤ p], #cf_span[1 ≤ bi ≤ q], #cf_span[1 ≤ ci ≤ r]），分别表示第 #cf_span[i] 张收藏卡片的力量、防御和速度。
请输出一个整数，表示能击败她收藏中所有卡片的不同卡片的数量。
## Input
输入的第一行包含四个整数：#cf_span[n], #cf_span[p], #cf_span[q] 和 #cf_span[r]（#cf_span[1 ≤ n, p, q, r ≤ 500000]），分别表示收藏中的卡片数量、可能的最大力量、最大防御和最大速度。接下来的 #cf_span[n] 行，每行包含三个整数。具体而言，第 #cf_span[i] 行包含 #cf_span[ai], #cf_span[bi] 和 #cf_span[ci]（#cf_span[1 ≤ ai ≤ p], #cf_span[1 ≤ bi ≤ q], #cf_span[1 ≤ ci ≤ r]），分别表示第 #cf_span[i] 张收藏卡片的力量、防御和速度。
## Output
请输出一个整数，表示能击败她收藏中所有卡片的不同卡片的数量。
[samples]
## Note
在第一个测试用例中，最大可能力量为 #cf_span[4]，最大可能防御为 #cf_span[4]，最大可能速度为 #cf_span[5]。Karen 有三张卡片：
第一张卡片的力量为 #cf_span[2]，防御为 #cf_span[2]，速度为 #cf_span[5]。
第二张卡片的力量为 #cf_span[1]，防御为 #cf_span[3]，速度为 #cf_span[4]。
第三张卡片的力量为 #cf_span[4]，防御为 #cf_span[1]，速度为 #cf_span[1]。
共有 #cf_span[10] 张卡片能击败所有这些卡片：
力量为 #cf_span[3]、防御为 #cf_span[3]、速度为 #cf_span[5] 的卡片。
力量为 #cf_span[3]、防御为 #cf_span[4]、速度为 #cf_span[2] 的卡片。
力量为 #cf_span[3]、防御为 #cf_span[4]、速度为 #cf_span[3] 的卡片。
力量为 #cf_span[3]、防御为 #cf_span[4]、速度为 #cf_span[4] 的卡片。
力量为 #cf_span[3]、防御为 #cf_span[4]、速度为 #cf_span[5] 的卡片。
力量为 #cf_span[4]、防御为 #cf_span[3]、速度为 #cf_span[5] 的卡片。
力量为 #cf_span[4]、防御为 #cf_span[4]、速度为 #cf_span[2] 的卡片。
力量为 #cf_span[4]、防御为 #cf_span[4]、速度为 #cf_span[3] 的卡片。
力量为 #cf_span[4]、防御为 #cf_span[4]、速度为 #cf_span[4] 的卡片。
力量为 #cf_span[4]、防御为 #cf_span[4]、速度为 #cf_span[5] 的卡片。
在第二个测试用例中，最大可能力量为 #cf_span[10]，最大可能防御为 #cf_span[10]，最大可能速度为 #cf_span[10]。Karen 有五张卡片，所有卡片的力量、防御和速度均为 #cf_span[1]。
任何具有至少两个属性大于 #cf_span[1] 的 #cf_span[972] 张卡片都能击败她收藏中的所有卡片。
**Definitions**
Let $ n, p, q, r \in \mathbb{Z}^+ $.
Let $ C = \{(a_i, b_i, c_i) \mid i \in \{1, \dots, n\}\} $ be the set of collection cards, where $ a_i \in [1, p] $, $ b_i \in [1, q] $, $ c_i \in [1, r] $.
Let $ \mathcal{U} = [1, p] \times [1, q] \times [1, r] $ be the universe of all possible cards.
**Constraint**
For any card $ x = (x_1, x_2, x_3) \in \mathcal{U} $, it **beats** a card $ y = (y_1, y_2, y_3) $ if at least two of the following hold:
$ x_1 > y_1 $, $ x_2 > y_2 $, $ x_3 > y_3 $.
**Objective**
Count the number of cards $ x \in \mathcal{U} $ such that for all $ (a_i, b_i, c_i) \in C $, $ x $ beats $ (a_i, b_i, c_i) $.
API Response (JSON)
{
"problem": {
"name": "D. Karen and Cards",
"description": {
"content": "Karen just got home from the supermarket, and is getting ready to go to sleep. <center></center>After taking a sh",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 524288
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF815D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Karen just got home from the supermarket, and is getting ready to go to sleep.\n\n<center></center>After taking a sh...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Karen 刚从超市回家，准备去睡觉。\n\n洗完澡并换上睡衣后，她看向书架，发现了一本相册。出于好奇，她打开一看，里面是一套集换式卡片。\n\n她回忆起小时候曾玩过这些卡片，尽管现在长大了，她仍对一些事情感到好奇。\n\n每张卡片有三个属性：_力量_、_防御_和_速度_。所有卡片的所有属性值均为正整数。任意卡片可能的最大力量为 #cf_span[p]，最大防御为 #cf_span[q]，最大速度为 #cf_...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, p, q, r \\in \\mathbb{Z}^+ $. \nLet $ C = \\{(a_i, b_i, c_i) \\mid i \\in \\{1, \\dots, n\\}\\} $ be the set of collection cards, where $ a_i \\in [1, p] $, $ b_i \\in [1, q] $, $ c_i ...",
"is_translate": false,
"language": "Formal"
}
]
}