Mages and Monsters

题意翻译

你正在玩游戏，并且在扮演一个法师，你一开始不会任何法术。 你可能会在游戏中学到新的法术，某种法术的每秒能造成的伤害为 $x$，每用一秒要消耗 $y$ 的法力值。注意你使用法术的时间可以不为整数，即用法术 $z$ 秒会造成 $x*z$ 的伤害，消耗 $y*z$ 的法力值。 你也可能会遇到一些怪物。对于一个怪物，它会在 $t$ 秒后杀死你，并且拥有 $h$ 的血量。在战斗开始之前你会有 $m$ 点法力值，然后你可以在战斗过程中任意使用以前学会的法术去打怪，只要能在 $t$ 秒及以内，消耗不超过 $m$ 的法力值造成至少 $h$ 点伤害就可以获得胜利。 你已知游戏中会有 $q$ 个事件发生： - $1\ x\ y$ 表示你学习了一个每秒伤害为 $x$,每秒消耗法力值为 $y$ 的法术。 - $2\ t\ h$ 表示你接下来要打一个怪，战斗时间限制为 $t$，血量为 $h$。 你想要知道对于每一次战斗你能否获胜，如果是就输出`YES`，否则为`NO`。 注意每个事件中后两个数等于读进来的数 $+j$ 后模 $10^6$ 再 $+1$ 的结果，其中 $j$ 为上一个输出`YES`的事件编号（初始情况下 $j=0$）。

题目描述

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.

输入输出格式

输入格式

The first line contains two integer numbers $ q $ and $ m $ $ (2<=q<=10^{5},1<=m<=10^{12}) $ — 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}<=10^{6}) $ . 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 $ $ 10^{6}+1 $ , $ y=(b_{i}+j) $ $ mod $ $ 10^{6}+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 $ $ 10^{6}+1 $ , $ h=(b_{i}+j) $ $ mod $ $ 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.

输入输出样例

输入样例 #1

3 100
1 4 9
2 19 49
2 19 49

输出样例 #1

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.