CF1498D Bananas in a Microwave

你有一个故障的微波炉，你想在里面放一些香蕉。你有 $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$ 个操作一次。 对于每个 $j$，$1 \le j \le m$，输出你能恰好得到 $j$ 个香蕉的最早时间步。如果无法得到恰好 $j$ 个香蕉，输出 $-1$。

第一行包含两个用空格分隔的整数 $n$（$1 \le n \le 200$）和 $m$（$2 \le m \le 10^5$）。 接下来有 $n$ 行，每行描述第 $i$ 个时间步的操作。每行包含三个用空格分隔的整数 $t_i$、$x'_i$ 和 $y_i$（$1 \le t_i \le 2$，$1 \le y_i \le m$）。 注意，给定的是 $x'_i$，即 $x_i$ 的 $10^5$ 倍。因此，$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$，如果无法获得）。

在第一个样例输入中，来看如何在三步内得到 $16$ 个香蕉。初始时 $k=0$。 - 第一步，选择 $a_1=2$，应用类型 1 操作 $k := \lceil(k+3)\rceil$ 两次。此时 $k=6$。 - 第二步，选择 $a_2=0$，$k$ 保持不变。 - 第三步，选择 $a_3=1$，应用类型 1 操作 $k := \lceil(k+10)\rceil$ 一次。此时 $k=16$。 可以证明，无法在更早的时间步内得到 $k=16$。 在第二个样例输入中，来看如何在两步内得到 $17$ 个香蕉。初始时 $k=0$。 - 第一步，选择 $a_1=1$，应用类型 1 操作 $k := \lceil(k+3.99999)\rceil$ 一次。此时 $k=4$。 - 第二步，选择 $a_2=1$，应用类型 2 操作 $k := \lceil(k \cdot 4.12345)\rceil$ 一次。此时 $k=17$。 可以证明，无法在更早的时间步内得到 $k=17$。 由 ChatGPT 4.1 翻译