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 ≤ a_i ≤ y_i, and perform the following update a_i times: k:=⌈ (k + x_i) ⌉.

Type 2: (t_i=2, x_i, y_i) — pick an a_i, such that 0 ≤ a_i ≤ y_i, and perform the following update a_i times: k:=⌈ (k ⋅ x_i) ⌉.

Note that x_i can be a fractional value. See input format for more details. Also, ⌈ x ⌉ is the smallest integer ≥ x.

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

For each j such that 1 ≤ j ≤ 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 ≤ n ≤ 200) and m (2 ≤ m ≤ 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 ≤ t_i ≤ 2, 1≤ y_i≤ m).

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

For type 1 operations, 1 ≤ x'_i ≤ 10^5 ⋅ m, and for type 2 operations, 10^5 < x'_i ≤ 10^5 ⋅ 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 := ⌈(k+3)⌉ — 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:= ⌈(k+10)⌉ 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 := ⌈(k+3.99999)⌉ — once. Hence, k is now 4. 
  * In timestep 2, we choose a_2=1, so we apply the type 2 update — k := ⌈(k⋅ 4.12345)⌉ — 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.

Solution (in JAVA):

Solution:
import java.util.*;
import java.io.*;

public class Main {
	public static long GCD(long a, long b) {
		if (b == 0)
			return a;
		if (a == 0)
			return b;
		return (a > b) ? GCD(a % b, b) : GCD(a, b % a);
	}

	public static void main(String[] args) throws Exception {

		int n = sc.nextInt();
		int m = sc.nextInt();
		int[] ans = new int[m + 1];
		Arrays.fill(ans, -1);
		ans[0] = 0;
		for (int i = 1; i <= n; i++) {
			int tt = sc.nextInt();

//			System.out.println(x);

			if (tt == 1) {
				long x = (sc.nextLong()) ;
				long y = sc.nextLong();
				int[] used = new int[m + 1];
				for (long j = 0; j <= m; j++) {
					long c =  j*100000 + x-(j*100000 + x)%100000+((j*100000 + x)%100000==0?0:100000);
					c/=100000;
//				pw.println(c+" "+j);
					if (c <= m && (used[(int) j] < y) && ans[(int) c] == -1 && ans[(int) j] != -1) {
						ans[(int) c] = i;
						used[(int) c] = used[(int) j] + 1;
					}
				}
			} else {
				long x = sc.nextLong();
				long y = sc.nextLong();
				int[] used = new int[m + 1];
				for (long j = 0; j <= m; j++) {
					long c =  j * x-(j* x)%100000+((j* x)%100000==0?0:100000);
					c/=100000;
						
						if (c <=m && (used[(int) j] < y && ans[(int) c] == -1) && ans[(int) j] != -1) {
							ans[(int) c] = i;
							used[(int) c] = used[(int) j] + 1;
						}
					
				}
			}
		}
		for (int i = 1; i <= m; i++) {
			pw.print(ans[i] + " ");
		}
		pw.println();

		pw.close();
	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

		public Scanner(FileReader r) {
			br = new BufferedReader(r);
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public double nextDouble() throws IOException {
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if (x.charAt(0) == '-') {
				neg = true;
				start++;
			}
			for (int i = start; i < x.length(); i++)
				if (x.charAt(i) == '.') {
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				} else {
					sb.append(x.charAt(i));
					if (dec)
						f *= 10;
				}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg ? -1 : 1);
		}

		public long[] nextlongArray(int n) throws IOException {
			long[] a = new long[n];
			for (int i = 0; i < n; i++)
				a[i] = nextLong();
			return a;
		}

		public Long[] nextLongArray(int n) throws IOException {
			Long[] a = new Long[n];
			for (int i = 0; i < n; i++)
				a[i] = nextLong();
			return a;
		}

		public int[] nextIntArray(int n) throws IOException {
			int[] a = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = nextInt();
			return a;
		}

		public Integer[] nextIntegerArray(int n) throws IOException {
			Integer[] a = new Integer[n];
			for (int i = 0; i < n; i++)
				a[i] = nextInt();
			return a;
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

	}

	static class pair implements Comparable<pair> {
		long x;
		long y;

		public pair(long x, long y) {
			this.x = x;
			this.y = y;
		}

		public String toString() {
			return x + " " + y;
		}

		public boolean equals(Object o) {
			if (o instanceof pair) {
				pair p = (pair) o;
				return p.x == x && p.y == y;
			}
			return false;
		}

		public int hashCode() {
			return new Long(x).hashCode() * 31 + new Long(y).hashCode();
		}

		public int compareTo(pair other) {
			if (this.x == other.x) {
				return Long.compare(this.y, other.y);
			}
			return Long.compare(this.x, other.x);
		}
	}

	static class tuble implements Comparable<tuble> {
		int x;
		int y;
		int z;

		public tuble(int x, int y, int z) {
			this.x = x;
			this.y = y;
			this.z = z;
		}

		public String toString() {
			return x + " " + y + " " + z;
		}

		public int compareTo(tuble other) {
			if (this.x == other.x) {
				if (this.y == other.y) {
					return this.z - other.z;
				}
				return this.y - other.y;
			} else {
				return this.x - other.x;
			}
		}
	}

	static long mod = 1000000007;
	static Random rn = new Random();
	static Scanner sc = new Scanner(System.in);
	static PrintWriter pw = new PrintWriter(System.out);
}