F. Маги и монстры
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вова играет в компьютерную игру Mages and Monsters. Персонаж Вовы — маг, но так как Вова только начал играть, персонаж ещё не знает ни одного заклинания.

В течение игры персонаж Вовы может учить новые заклинания. Каждое заклинание характеризуется двумя числами xi и yi — урон, наносимый заклинанием в секунду, и расходы маны в секунду соответственно, когда Вова использует это заклинание. Вова не обязательно должен использовать заклинание целое количество секунд, тогда урон и затраты маны изменятся пропорционально — более формально, если персонаж использует заклинание с уроном x и затратами маны y в течение z секунд, то он нанесёт x·z урона и потратит y·z маны (без округлений). Если запас маны исчерпан (его значение в начале каждого боя одинаково и известно с самого начала), персонаж не может использовать заклинания вообще; нельзя одновременно применять более одного заклинания.

Также Вова может сражаться с монстрами; каждый монстр характеризуется величинами tj и hj — монстр убивает персонажа Вовы за tj секунд и имеет hj здоровья. После каждого боя с монстром персонаж Вовы восстанавливает ману (или возрождается с полным запасом), так что результаты предыдущих боёв никак не влияют на последующие.

Считается, что Вова может уничтожить монстра, если он способен при помощи своих заклинаний (можно использовать несколько разных заклинаний в одном и том же бою) нанести ему hj урона не более чем за tj секунд, учитывая расходы маны. Если здоровье монстра становится равным нулю ровно через tj секунд после начала боя (то есть монстр и персонаж убивают друг друга одновременно), считается, что Вова может победить.

Необходимо написать программу, обрабатывающую два вида запросов:

  • 1 x y — Вова учит заклинание, наносящее x урона в секунду и тратящее y маны в секунду.
  • 2 t h — Вова сражается с монстром, который способен убить персонажа за t секунд и которому нужно нанести h урона для победы.

Обратите внимание, что запросы подаются в изменённом виде. Помните, что персонаж Вовы не знает ни одного заклинания в начале игры.

Для каждого запроса второго типа нужно определить, может ли Вова победить соответствующего монстра.

Входные данные

В первой строке записаны два целых числа 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, то необходимо определить, может ли Вова победить монстра с характеристиками, вычисляемыми таким же образом (t = (ai + j) mod 106 + 1, h = (bi + j) mod 106 + 1).
Выходные данные

На каждый запрос второго типа выведите по одной строке — YES, если Вова может победить соответствующего монстра, и NO в противном случае.

Пример
Входные данные
3 100
1 4 9
2 19 49
2 19 49
Выходные данные
YES
NO
Примечание

В первом тесте персонаж сначала учит заклинание, наносящее 5 урона за 10 маны в секунду. Следующим запросом он сражается с монстром, побеждающим его за 20 секунд и имеющим 50 здоровья, и убивает его за 10 секунд (тратя 100 маны). Следующий монстр уже имеет 52 здоровья, и Вова не может нанести такой урон, имея только 100 маны.