Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

D. Бананы в микроволновке
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть сломанная микроволновка, в которую вы хотите положить несколько бананов. У вас есть $$$n$$$ моментов времени, пока микроволновка не сломается окончательно. В каждый момент времени она показывает новую операцию.

Пусть $$$k$$$ будет равно текущему количеству бананов в микроволновке. Изначально $$$k = 0$$$. В $$$i$$$-й операции на вход подаются три параметра $$$t_i$$$, $$$x_i$$$, $$$y_i$$$. В зависимости от значения $$$t_i$$$ необходимо сделать одно из следующий действий:

Тип 1: ($$$t_i=1$$$, $$$x_i$$$, $$$y_i$$$) — выберите $$$a_i$$$ такое, что $$$0 \le a_i \le y_i$$$, и произведите следующую замену $$$a_i$$$ раз: $$$k:=\lceil (k + x_i) \rceil$$$.

Тип 2: ($$$t_i=2$$$, $$$x_i$$$, $$$y_i$$$) — выберите $$$a_i$$$ такое, что $$$0 \le a_i \le y_i$$$, и произведите следующую замену $$$a_i$$$ раз: $$$k:=\lceil (k \cdot x_i) \rceil$$$.

Обратите внимание, что $$$x_i$$$ может быть дробным значением. Смотрите формат входных данных для пояснения. Также $$$\lceil x \rceil$$$ — это наименьшее целое число $$$\ge x$$$.

В $$$i$$$-й момент времени необходимо произвести $$$i$$$-ю операцию ровно один раз.

Для каждого $$$j$$$ такого, что $$$1 \le j \le m$$$, выведите самый ранний момент времени такой, что вы можете получить ровно $$$j$$$ бананов. Если нельзя получить ровно $$$j$$$ бананов, то выведите $$$-1$$$.

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

В первой строке записаны два целых числа $$$n$$$ $$$(1 \le n \le 200)$$$ и $$$m$$$ $$$(2 \le m \le 10^5)$$$.

Затем следуют $$$n$$$ строк, где $$$i$$$-я строка описывает операцию в $$$i$$$-й момент времени. Каждая строка содержит три целых числа $$$t_i$$$, $$$x'_i$$$ и $$$y_i$$$ ($$$1 \le t_i \le 2$$$, $$$1\le y_i\le m$$$).

Обратите внимание, что задается $$$x'_i$$$, которое равно $$$10^5 \cdot x_i$$$. Чтобы получить $$$x_i$$$, используйте формулу $$$x_i= \dfrac{x'_i} {10^5}$$$.

Для операций типа 1 $$$1 \le x'_i \le 10^5 \cdot m$$$, а для операций типа 2 $$$10^5 < x'_i \le 10^5 \cdot m$$$.

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

Выведите $$$m$$$ целых чисел, где $$$i$$$-е число равно самому раннему моменту времени, в который можно получить ровно $$$i$$$ бананов (или $$$-1$$$, если это невозможно).

Примеры
Входные данные
3 20
1 300000 2
2 400000 2
1 1000000 3
Выходные данные
-1 -1 1 -1 -1 1 -1 -1 -1 3 -1 2 3 -1 -1 3 -1 -1 -1 3
Входные данные
3 20
1 399999 2
2 412345 2
1 1000001 3
Выходные данные
-1 -1 -1 1 -1 -1 -1 1 -1 -1 3 -1 -1 -1 3 -1 2 -1 3 -1
Примечание

В первом примере мы хотим показать, как получить $$$16$$$ бананов за три момента времени. Изначально $$$k=0$$$.

  • В момент времени 1 мы выбираем $$$a_1=2$$$, поэтому мы применяем обновление типа 1 — $$$k := \lceil(k+3)\rceil$$$ — два раза. Поэтому $$$k$$$ теперь 6.
  • В момент времени 2 мы выбираем $$$a_2=0$$$, поэтому $$$k$$$ не изменяется.
  • В момент времени 3 мы выбираем $$$a_3=1$$$, поэтому мы применяем обновление типа 1 $$$k:= \lceil(k+10)\rceil$$$ один раз. Поэтому $$$k$$$ теперь 16.

Можно показать, что $$$k=16$$$ нельзя получить быстрее, чем за три момента времени, используя данные операции.

Во втором примере мы хотим показать, как получить $$$17$$$ бананов за два момента времени. Изначально $$$k=0$$$.

  • В момент времени 1 мы выбираем $$$a_1=1$$$, поэтому мы применяем обновление типа 1 — $$$k := \lceil(k+3.99999)\rceil$$$ — один раз. Поэтому $$$k$$$ теперь 4.
  • В момент времени 2 мы выбираем $$$a_2=1$$$, поэтому мы применяем обновление типа 2 — $$$k := \lceil(k\cdot 4.12345)\rceil$$$ — один раз. Поэтому $$$k$$$ теперь 17.

Можно показать, что $$$k=17$$$ нельзя получить быстрее, чем за два момента времени, используя данные операции.