Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Bananas in a Microwave

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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

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

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

Examples

Input

3 20 1 300000 2 2 400000 2 1 1000000 3

Output

-1 -1 1 -1 -1 1 -1 -1 -1 3 -1 2 3 -1 -1 3 -1 -1 -1 3

Input

3 20 1 399999 2 2 412345 2 1 1000001 3

Output

-1 -1 -1 1 -1 -1 -1 1 -1 -1 3 -1 -1 -1 3 -1 2 -1 3 -1

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.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/01/2021 19:54:28 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|