CF792F.Mages and Monsters

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.

沃瓦正在玩一款名为《法师与怪物》的电脑游戏。沃瓦的角色是一名法师。但由于他刚刚开始游戏，他的角色目前尚未掌握任何法术。

沃瓦的角色可以在游戏中学习新的法术。每个法术由两个值 $x_i$ 和 $y_i$ 表征——分别表示每秒造成的伤害和每秒消耗的法力值。沃瓦无需以整数秒为单位使用法术。更准确地说，若他使用一个伤害为 $x$、法力消耗为 $y$ 的法术持续 $z$ 秒，则总共造成 $x \cdot z$ 点伤害，并消耗 $y \cdot z$ 点法力（不进行四舍五入）。若法力耗尽（初始法力值在游戏开始时设定，且每次战斗开始时均保持该固定值），则角色将无法再使用任何法术。禁止同时使用多个法术。

此外，沃瓦还可以与怪物战斗。每个怪物由两个值 $t_j$ 和 $h_j$ 表征——分别表示该怪物将在 $t_j$ 秒内击杀沃瓦的角色，以及其拥有 $h_j$ 点生命值。每次战斗结束后法力值都会完全恢复（或沃瓦的角色以满法力值复活），因此之前的战斗对后续战斗无任何影响。

沃瓦的角色成功击杀一只怪物，当且仅当他能在 不超过 $t_j$ 秒 内对该怪物造成 至少 $h_j$ 点伤害，且在此过程中 总法力消耗不超过战斗开始时的法力上限（允许在一场战斗中使用多个不同的法术）。若怪物的生命值恰好在第 $t_j$ 秒归零（即怪物与沃瓦的角色在同一时刻互相击杀），则沃瓦赢得该场战斗。

你需要编写一个程序，能够响应以下两类查询：

• 1 x y — 沃瓦的角色学会一个新法术，该法术每秒造成 $x$ 点伤害，每秒消耗 $y$ 点法力；
• 2 t h — 沃瓦与一只怪物战斗，该怪物将在 $t$ 秒内击杀沃瓦的角色，且拥有 $h$ 点生命值。

注意：查询以如上形式给出。另外请记住，游戏开始时沃瓦的角色尚未掌握任何法术。

对于每个类型为 2 的查询，你必须判断沃瓦是否能够战胜对应的怪物。

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.

第一行包含两个整数 $ q $ 和 $ m $（$ 2 \leq q \leq 10^5 $，$ 1 \leq m \leq 10^{12} $）—— 分别表示查询次数以及每次战斗开始时拥有的法力值。

接下来的 $ q $ 行中，第 $ i $ 行包含三个数 $ k_i $、$ a_i $ 和 $ b_i $（$ 1 \leq k_i \leq 2 $，$ 1 \leq a_i, b_i \leq 10^6 $）。

利用这些输入可按如下方式还原实际查询：令 $ j $ 表示上一个答案为正的第二类查询的索引（若不存在此类查询，则令 $ j = 0 $）。

• 若 $ k_i = 1 $，则角色习得一个法术，其参数为 $ x = (a_i + j) \bmod 10^6 + 1 $，$ y = (b_i + j) \bmod 10^6 + 1 $；
• 若 $ k_i = 2 $，则需判断 Vova 是否能战胜一个怪物，该怪物的参数为 $ t = (a_i + j) \bmod 10^6 + 1 $，$ h = (b_i + j) \bmod 10^6 + 1 $。

For every query of second type print YES if Vova is able to win the fight with corresponding monster and NO otherwise.

对于每个第二类查询，如果沃瓦能够击败对应的怪物，则输出 YES，否则输出 NO。

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.

在第一个例子中，沃瓦的角色首先学会了每秒造成 5 点伤害、消耗 10 点法力值的法术。接下来是一场与怪物的战斗，该怪物可在 20 秒内杀死角色，且拥有 50 点生命值。沃瓦在 10 秒内将其击杀（共消耗 100 点法力值）。下一个怪物拥有 52 点生命值，因此沃瓦仅凭 100 点法力值无法造成足够的伤害。