|
Лимит времени 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 A1,
A2,.. AN, which make the
source row.
It has N pairs of positive integer numbers
(B1, C1),
(B2, C2),..
(BN, CN),
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. Aj is called correlated to Ai
if |j-Bi| mod Ci = 0.
2. A'i is calculated as the sum of all elements in original
source row that are correlated to Ai.
For example, suppose that N=5 and for A4
we have pair (3,2). In that case elements A1,
A3, A5 are
correlated to A4 and the new source row element
A'4 is calculated as sum (A1 +
A3 + A5).
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
S1, S2,.. SN
where Si are the first twenty five bits in binary
representation of Ai, 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 ≤ 109).
The next N rows contain three numbers each: (i+1)-th row
contains numbers Ai, Bi,
Ci (1 ≤ Ai ≤ 230,
1 ≤ Bi ≤ N, 1 ≤ Ci ≤ 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
|
Для отправки решений необходимо выполнить вход.
|