CF1498D.Bananas in a Microwave

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$.

你有一台故障的微波炉，想在里面放入一些香蕉。在微波炉彻底损坏前，你共有 $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$ 表示不小于 $x$ 的最小整数（即向上取整）。

在第 $i$ 个时间步，你必须且仅能执行第 $i$ 个操作一次。

对每个满足 $1 \le j \le m$ 的 $j$，输出能够恰好得到 $j$ 根香蕉的最早时间步；若无法恰好得到 $j$ 根香蕉，则输出 $-1$。

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 \lt x'_i \le 10^5 \cdot m$.

第一行包含两个以空格分隔的整数 $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= \dfrac{x'_i} {10^5}$ 计算出 $x_i$。

对于类型 1 的操作，满足 $1 \le x'_i \le 10^5 \cdot m$；对于类型 2 的操作，满足 $10^5 \lt x'_i \le 10^5 \cdot m$。

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).

输出 $m$ 个整数，其中第 $i$ 个整数表示能够恰好获得 $i$ 根香蕉的最早时间步（若无法实现，则为 $-1$）。

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.

在第一个样例输入中，我们来演示如何在三个时间步内生成 $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$。