1498D · Bananas in a Microwave

Problem: You have a malfunctioning microwave in which you want to put some bananas. You have $n$ time-steps before the microwave stops working completely. At each time-step, it displays a new operation.

Let $k$ be the number of bananas in the microwave currently. Initially, $k = 0$. In the $i$-th operation, you are given three parameters $t_i$, $x_i$, $y_i$ in the input. Based on the value of $t_i$, you must do one of the following:

Type 1: ($t_i=1$, $x_i$, $y_i$) — pick an $a_i$, such that $0 \le a_i \le y_i$, and perform the following update $a_i$ times: $k:=\lceil (k + x_i) \rceil$.

Type 2: ($t_i=2$, $x_i$, $y_i$) — pick an $a_i$, such that $0 \le a_i \le y_i$, and perform the following update $a_i$ times: $k:=\lceil (k \cdot x_i) \rceil$.

Note that $x_i$ can be a fractional value. See input format for more details. Also, $\lceil x \rceil$ is the smallest integer $\ge x$.

At the $i$-th time-step, you must apply the $i$-th operation exactly once.

For each $j$ such that $1 \le j \le m$, output the earliest time-step at which you can create exactly $j$ bananas. If you cannot create exactly $j$ bananas, output $-1$.

Input Format: The first line contains two space-separated integers $n$ $(1 \le n \le 200)$ and $m$ $(2 \le m \le 10^5)$.

Then, $n$ lines follow, where the $i$-th line denotes the operation for the $i$-th timestep. Each such line contains three space-separated integers $t_i$, $x'_i$ and $y_i$ ($1 \le t_i \le 2$, $1\le y_i\le m$).

Note that you are given $x'_i$, which is $10^5 \cdot x_i$. Thus, to obtain $x_i$, use the formula $x_i= \dfrac{x'_i} {10^5}$.

For type 1 operations, $1 \le x'_i \le 10^5 \cdot m$, and for type 2 operations, $10^5 < x'_i \le 10^5 \cdot m$.

Output Format: Print $m$ integers, where the $i$-th integer is the earliest time-step when you can obtain exactly $i$ bananas (or $-1$ if it is impossible).

Note: In the first sample input, let us see how to create $16$ number of bananas in three timesteps. Initially, $k=0$.

• In timestep 1, we choose $a_1=2$, so we apply the type 1 update — $k := \lceil(k+3)\rceil$ — two times. Hence, $k$ is now 6.
• In timestep 2, we choose $a_2=0$, hence value of $k$ remains unchanged.
• In timestep 3, we choose $a_3=1$, so we are applying the type 1 update $k:= \lceil(k+10)\rceil$ once. Hence, $k$ is now 16.

It can be shown that $k=16$ cannot be reached in fewer than three timesteps with the given operations.

In the second sample input, let us see how to create $17$ number of bananas in two timesteps. Initially, $k=0$.

• In timestep 1, we choose $a_1=1$, so we apply the type 1 update — $k := \lceil(k+3.99999)\rceil$ — once. Hence, $k$ is now 4.
• In timestep 2, we choose $a_2=1$, so we apply the type 2 update — $k := \lceil(k\cdot 4.12345)\rceil$ — once. Hence, $k$ is now 17.

It can be shown that $k=17$ cannot be reached in fewer than two timesteps with the given operations.