English · Original
Chinese · Translation
Formal · Original
Vova plays a computer game known as Mages and Monsters. Vova's character is a mage. Though as he has just started, his character knows no spells.
Vova's character can learn new spells during the game. Every spell is characterized by two values _x__i_ and _y__i_ — damage per second and mana cost per second, respectively. Vova doesn't have to use a spell for an integer amount of seconds. More formally, if he uses a spell with damage _x_ and mana cost _y_ for _z_ seconds, then he will deal _x_·_z_ damage and spend _y_·_z_ mana (no rounding). If there is no mana left (mana amount is set in the start of the game and it remains the same at the beginning of every fight), then character won't be able to use any spells. It is prohibited to use multiple spells simultaneously.
Also Vova can fight monsters. Every monster is characterized by two values _t__j_ and _h__j_ — monster kills Vova's character in _t__j_ seconds and has _h__j_ health points. Mana refills after every fight (or Vova's character revives with full mana reserve), so previous fights have no influence on further ones.
Vova's character kills a monster, if he deals _h__j_ damage to it in no more than _t__j_ seconds using his spells (it is allowed to use more than one spell in a fight) and spending no more mana than he had at the beginning of the fight. **If monster's health becomes zero exactly in _t__j_ seconds (it means that the monster and Vova's character kill each other at the same time), then Vova wins the fight**.
You have to write a program which can answer two types of queries:
* 1 _x_ _y_ — Vova's character learns new spell which deals _x_ damage per second and costs _y_ mana per second.
* 2 _t_ _h_ — Vova fights the monster which kills his character in _t_ seconds and has _h_ health points.
**Note that queries are given in a different form. Also remember that Vova's character knows no spells at the beginning of the game.**
For every query of second type you have to determine if Vova is able to win the fight with corresponding monster.
## Input
The first line contains two integer numbers _q_ and _m_ (2 ≤ _q_ ≤ 105, 1 ≤ _m_ ≤ 1012) — the number of queries and the amount of mana at the beginning of every fight.
_i_\-th of each next _q_ lines contains three numbers _k__i_, _a__i_ and _b__i_ (1 ≤ _k__i_ ≤ 2, 1 ≤ _a__i_, _b__i_ ≤ 106).
Using them you can restore queries this way: let _j_ be the index of the last query of second type with positive answer (_j_ = 0 if there were none of these).
* If _k__i_ = 1, then character learns spell with _x_ = (_a__i_ + _j_) _mod_ 106 + 1, _y_ = (_b__i_ + _j_) _mod_ 106 + 1.
* If _k__i_ = 2, then you have to determine if Vova is able to win the fight against monster with _t_ = (_a__i_ + _j_) _mod_ 106 + 1, _h_ = (_b__i_ + _j_) _mod_ 106 + 1.
## Output
For every query of second type print _YES_ if Vova is able to win the fight with corresponding monster and _NO_ otherwise.
[samples]
## Note
In first example Vova's character at first learns the spell with 5 damage and 10 mana cost per second. Next query is a fight with monster which can kill character in 20 seconds and has 50 health points. Vova kills it in 10 seconds (spending 100 mana). Next monster has 52 health, so Vova can't deal that much damage with only 100 mana.
Vova 玩一款名为《法师与怪物》的电脑游戏。Vova 的角色是一名法师。但由于他刚刚开始游戏，他的角色尚未掌握任何法术。
Vova 的角色可以在游戏中学习新的法术。每个法术由两个值 #cf_span[xi] 和 #cf_span[yi] 描述——每秒伤害和每秒法力消耗。Vova 不必以整数秒为单位使用法术。更正式地说，如果他使用一个每秒伤害为 #cf_span[x]、每秒法力消耗为 #cf_span[y] 的法术持续 #cf_span[z] 秒，则他会造成 #cf_span[x·z] 点伤害并消耗 #cf_span[y·z] 点法力（无需四舍五入）。如果法力耗尽（法力总量在游戏开始时设定，并在每次战斗开始时重置为相同值），则角色将无法使用任何法术。禁止同时使用多个法术。
此外，Vova 可以与怪物战斗。每个怪物由两个值 #cf_span[tj] 和 #cf_span[hj] 描述——怪物在 #cf_span[tj] 秒内杀死 Vova 的角色，且拥有 #cf_span[hj] 点生命值。每次战斗后法力会恢复（或 Vova 的角色复活并拥有满额法力），因此之前的战斗不会影响后续战斗。
Vova 的角色击败怪物，当且仅当他在不超过 #cf_span[tj] 秒的时间内，使用法术对怪物造成至少 #cf_span[hj] 点伤害，并且消耗的法力不超过战斗开始时拥有的法力总量。*如果怪物的生命值恰好在 #cf_span[tj] 秒时变为零（即怪物与 Vova 的角色同时死亡），则 Vova 赢得这场战斗*。
你需要编写一个程序来处理两种类型的查询：
*注意：查询以不同形式给出。同时请记住，Vova 的角色在游戏开始时不会任何法术。*
对于每个第二类查询，你需要判断 Vova 是否能赢得与对应怪物的战斗。
第一行包含两个整数 #cf_span[q] 和 #cf_span[m] #cf_span[(2 ≤ q ≤ 105, 1 ≤ m ≤ 1012)] —— 查询数量和每次战斗开始时的法力总量。
接下来的 #cf_span[q] 行中，第 #cf_span[i] 行包含三个数 #cf_span[ki], #cf_span[ai] 和 #cf_span[bi] #cf_span[(1 ≤ ki ≤ 2, 1 ≤ ai, bi ≤ 106)]。
根据这些数值，你可以还原出查询：设 #cf_span[j] 为上一个回答为“是”的第二类查询的索引（若无此类查询，则 #cf_span[j = 0]）。
对于每个第二类查询，若 Vova 能赢得与对应怪物的战斗，则输出 _YES_，否则输出 _NO_。
在第一个例子中，Vova 的角色首先学习了一个每秒伤害为 #cf_span[5]、每秒法力消耗为 #cf_span[10] 的法术。下一个查询是与一个在 #cf_span[20] 秒内杀死角色、拥有 #cf_span[50] 点生命值的怪物战斗。Vova 在 #cf_span[10] 秒内击败了它（消耗了 #cf_span[100] 点法力）。下一个怪物有 #cf_span[52] 点生命值，因此仅凭 #cf_span[100] 点法力，Vova 无法造成足够的伤害。
## Input
第一行包含两个整数 #cf_span[q] 和 #cf_span[m] #cf_span[(2 ≤ q ≤ 105, 1 ≤ m ≤ 1012)] —— 查询数量和每次战斗开始时的法力总量。第 #cf_span[i] 行包含三个数 #cf_span[ki], #cf_span[ai] 和 #cf_span[bi] #cf_span[(1 ≤ ki ≤ 2, 1 ≤ ai, bi ≤ 106)]。根据这些数值，你可以还原出查询：设 #cf_span[j] 为上一个回答为“是”的第二类查询的索引（若无此类查询，则 #cf_span[j = 0]）。若 #cf_span[ki = 1]，则角色学习一个每秒伤害为 #cf_span[(ai + j)] #cf_span[mod] #cf_span[106 + 1]、每秒法力消耗为 #cf_span[(bi + j)] #cf_span[mod] #cf_span[106 + 1] 的法术。若 #cf_span[ki = 2]，则你需要判断 Vova 是否能赢得与一个在 #cf_span[(ai + j)] #cf_span[mod] #cf_span[106 + 1] 秒内杀死角色、拥有 #cf_span[(bi + j)] #cf_span[mod] #cf_span[106 + 1] 点生命值的怪物的战斗。
## Output
对于每个第二类查询，若 Vova 能赢得与对应怪物的战斗，则输出 _YES_，否则输出 _NO_。
[samples]
## Note
在第一个例子中，Vova 的角色首先学习了一个每秒伤害为 #cf_span[5]、每秒法力消耗为 #cf_span[10] 的法术。下一个查询是与一个在 #cf_span[20] 秒内杀死角色、拥有 #cf_span[50] 点生命值的怪物战斗。Vova 在 #cf_span[10] 秒内击败了它（消耗了 #cf_span[100] 点法力）。下一个怪物有 #cf_span[52] 点生命值，因此仅凭 #cf_span[100] 点法力，Vova 无法造成足够的伤害。
**Definitions**
Let $ q \in \mathbb{Z}^+ $ be the number of queries, $ m \in \mathbb{Z}^+ $ be the initial mana per fight.
Let $ \mathcal{S} = \emptyset $ be the set of available spells, initially empty.
Each spell is a pair $ (x, y) \in \mathbb{R}^+ \times \mathbb{R}^+ $, denoting damage-per-second and mana-cost-per-second.
For each query $ i \in \{1, \dots, q\} $, given $ (k_i, a_i, b_i) $:
- If $ k_i = 1 $: add spell $ (a_i, b_i) $ to $ \mathcal{S} $.
- If $ k_i = 2 $: let $ t = a_i $, $ h = b_i $. Define monster $ M_i = (t, h) $.
Let $ j \in \mathbb{Z}_{\geq 0} $ be the index of the last query of type 2 with a "YES" answer (0 if none).
**Constraints**
1. $ 2 \leq q \leq 10^5 $, $ 1 \leq m \leq 10^{12} $
2. For all $ i $, $ 1 \leq a_i, b_i \leq 10^6 $
3. Spell usage: non-negative real durations allowed; no simultaneous casting.
4. For a fight with monster $ (t, h) $, total mana spent $ \leq m $, total damage $ \geq h $, and total time $ \leq t $.
**Objective**
For each query $ i $ with $ k_i = 2 $, determine whether there exists a finite set of spells $ \{(x_1, y_1), \dots, (x_n, y_n)\} \subseteq \mathcal{S} $ and non-negative real durations $ z_1, \dots, z_n \geq 0 $ such that:
$$
\sum_{l=1}^n x_l z_l \geq h, \quad \sum_{l=1}^n y_l z_l \leq m, \quad \sum_{l=1}^n z_l \leq t
$$
Output "YES" if such durations exist, "NO" otherwise.
API Response (JSON)
{
"problem": {
"name": "F. Mages and Monsters",
"description": {
"content": "Vova plays a computer game known as Mages and Monsters. Vova's character is a mage. Though as he has just started, his character knows no spells. Vova's character can learn new spells during the game",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF792F"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Vova plays a computer game known as Mages and Monsters. Vova's character is a mage. Though as he has just started, his character knows no spells.\n\nVova's character can learn new spells during the game...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Vova 玩一款名为《法师与怪物》的电脑游戏。Vova 的角色是一名法师。但由于他刚刚开始游戏，他的角色尚未掌握任何法术。\n\nVova 的角色可以在游戏中学习新的法术。每个法术由两个值 #cf_span[xi] 和 #cf_span[yi] 描述——每秒伤害和每秒法力消耗。Vova 不必以整数秒为单位使用法术。更正式地说，如果他使用一个每秒伤害为 #cf_span[x]、每秒法力消耗为 #cf_s...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ q \\in \\mathbb{Z}^+ $ be the number of queries, $ m \\in \\mathbb{Z}^+ $ be the initial mana per fight. \nLet $ \\mathcal{S} = \\emptyset $ be the set of available spells, initially...",
"is_translate": false,
"language": "Formal"
}
]
}