您的微波炉出现故障,您想在其中放入一些香蕉。在微波炉完全停止工作之前,您有 $$$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$$$ )。
示例
输入 #1
3 20 1 300000 2 2 400000 2 1 1000000 3
输出 #1
-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
输出 #2
-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$$$ 无法在少于两个时间步内达到。