У вас есть сломанная микроволновка, в которую вы хотите положить несколько бананов. У вас есть \(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\).
Выходные данные
Выведите \(m\) целых чисел, где \(i\)-е число равно самому раннему моменту времени, в который можно получить ровно \(i\) бананов (или \(-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\) нельзя получить быстрее, чем за два момента времени, используя данные операции.
Примеры
| № | Входные данные | Выходные данные |
|
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
|
|
2
|
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
|