
Лимит времени 3000/6000/6000/6000 мс. Лимит памяти 65000/65000/65000/65000 Кб. Автор: Дмитрий Шевченко, ВлГУ.
Currently you are working for a famous computer company
"Rivest C". The main computer has a very complicated
password to login. It is kept in the CEO's safe. The password
is very long and very strong from the mathematical point of
view. Unfortunately, the safe was not that strong, and someone
has stolen the password. Now you have to change it, but in order
to do so you have to enter the old password, and your CEO
does not remember it.
However, there is a way out. You can restore a password from
key that was used to generate it. The key consists of
the following parts:
It has N positive integer numbers A_{1},
A_{2},.. A_{N}, which make the
source row.
It has N pairs of positive integer numbers
(B_{1}, C_{1}),
(B_{2}, C_{2}),..
(B_{N}, C_{N}),
which make the transformation puzzle.
It has one positive integer number K which is the time
security key.
Now let's show, how this key is used to generate code. From the
original source row A we generate a new source row A'
according to the following system:
1. A_{j} is called correlated to A_{i}
if jB_{i} mod C_{i} = 0.
2. A'_{i} is calculated as the sum of all elements in original
source row that are correlated to A_{i}.
For example, suppose that N=5 and for A_{4}
we have pair (3,2). In that case elements A_{1},
A_{3}, A_{5} are
correlated to A_{4} and the new source row element
A'_{4} is calculated as sum (A_{1} +
A_{3} + A_{5}).
The code is generated like this. You calculate the new source row A'
and replace the old source row A with this one. You perform this
K times. After you are done with that, you write down the code
from final source row in the following way: the code is concatenation of
S_{1}, S_{2},.. S_{N}
where S_{i} are the first twenty five bits in binary
representation of A_{i}, starting from the
least significant bit. For example, suppose, that after K iterations
you have the following source row: {31,15,63}.
Then the code is this:
111110000000000000000000011110000000000000000000001111110000000000000000000.
Help your CEO and write a program that will generate
the code from the given key.
Input
In the first input row, numbers N and K are written separated
by a space (1 ≤ N ≤ 100, 1 ≤ K ≤ 10^{9}).
The next N rows contain three numbers each: (i+1)th row
contains numbers A_{i}, B_{i},
C_{i} (1 ≤ A_{i} ≤ 2^{30},
1 ≤ B_{i} ≤ N, 1 ≤ C_{i} ≤ N).
Output
Your output should contain a string representing the code. The
string should be 25*N characters long and should contain only
symbols '0' and '1'.
Input

Output

3 25
31 1 3
15 2 3
63 3 3

111110000000000000000000011110000000000000000000001111110000000000000000000

Input

Output

3 25
31 2 1
15 3 1
63 1 2

101100010010101111010001110110001001010111101000110111101111100111000100101

Для отправки решений необходимо выполнить вход.
