Vova 玩一款名为《法师与怪物》的电脑游戏。 Vova的角色是一名法师。虽然他刚刚开始,但他的角色不懂咒语。
Vova的角色可以在游戏过程中学习新法术。每个法术都有两个值 xi 和 yi 来表征——分别是每秒伤害和每秒法力消耗。 Vova 不必在整数秒内使用咒语。更正式地说,如果他使用伤害为 x 且法力消耗为 y 的法术持续 z 秒,那么他将造成 x·z 伤害并消耗 y·z 法力(无舍入)。如果没有剩余法力(法力值在游戏开始时设定,并且在每次战斗开始时保持不变),那么角色将无法使用任何法术。禁止同时使用多个法术。
Vova也可以与怪物战斗。每个怪物都有两个值 tj 和 hj - 怪物在 tj 秒内杀死 Vova 的角色并拥有 hj 生命值。每次战斗后法力都会重新填充(或者沃娃的角色会以完整的法力储备复活),因此之前的战斗对以后的战斗没有影响。
Vova的角色杀死一个怪物,如果他使用他的法术在不超过tj秒内对它造成hj伤害(允许在一场战斗中使用多个法术)并且消耗的法力不超过他在战斗开始时的法力值。如果怪物的生命值恰好在 tj 秒内变为零(这意味着怪物和 Vova 的角色同时互相杀死),则 Vova 赢得战斗。
您必须编写一个可以回答两种类型查询的程序:
- 1 x y — Vova 的角色学习新法术,每秒造成 x 点伤害,每秒消耗 y 点法力。
- 第 2 小时 — Vova 与怪物战斗,怪物在 t 秒内杀死了他的角色并拥有 h 点生命值。
请注意,查询以不同的形式给出。还要记住,Vova 的角色在游戏开始时不知道任何咒语。
对于第二类的每个查询,您必须确定 Vova 是否能够赢得与相应怪物的战斗。
输入
第一行包含两个整数 q 和 m (2 ≤ q ≤ 105, 1 ≤ m ≤ 1012) — 每场战斗开始时的查询次数和法力值。
接下来的 q 行中的第 i 行包含三个数字 ki、ai 和 bi (1 ≤ ki ≤ 2, 1 ≤ ai, bi ≤ 106)。
使用它们,您可以通过以下方式恢复查询:令 j 为具有肯定答案的第二类型的最后一个查询的索引(如果没有这些查询,则 j = 0)。
- 如果 ki = 1,则角色通过 x = (ai + j) mod 106 + 1,y = (bi + j) mod 106 + 1 学习法术。
- 如果ki = 2,那么你必须确定Vova是否能够赢得与t = (ai + j) mod 106 + 1、h = (bi + j) mod 106 + 1的怪物的战斗。
输出
对于第二类型的每个查询,如果 Vova 能够赢得与相应怪物的战斗,则打印“是”,否则打印“否”。
示例
输入 #1
3 100 1 4 9 2 19 49 2 19 49
输出 #1
YES NO
注意
在第一个示例中,Vova 的角色首先学习每秒 5 点伤害和 10 点法力消耗的法术。下一个查询是与怪物的战斗,该怪物可以在 20 秒内杀死角色并拥有 50 点生命值。 Vova 在 10 秒内杀死它(花费 100 点法力)。下一个怪物有 52 点生命值,因此 Vova 无法仅用 100 点法力造成那么多伤害。