There are really rush days in the Institute of Parasitic and Symbiotic
Creatures (IPSC) this week. They have just discovered new species of
bacteria and want to collect as much information about
it as possible. Unfortunately the bacteria breed so quickly that one
is hardly able to monitor their expansion. So far the institute staff
knows only the following few facts about these bacteria:
-
The bacteria live in N separate colonies.
The colonies are numbered from 0 to N-1.
-
Every second the number of bacteria in each colony may change.
E.g. some of them may die, reproduce or even move to another colony.
These changes occur according to some already known rules.
There are M such rules and they are used repeatedly in the
order recorded by the scientists.
(If we number the rules from 0 to M-1, after S
seconds of the experiment the rule (S-1) modulo M is used.)
-
Whenever K bacteria meet in one colony, they merge together,
evolve into a higher organism and fly away. (Note: If e.g.
2K+5 bacteria meet in one colony, K of them create
an organism, another K of them create another organism and only
the remaining 5 bacteria will stay in the colony.)
Your task is to compute how many bacteria will live in each of the
colonies after T seconds, provided there is exactly one bacterium
in each of them at the beginning.
Input file specification
On the first line there are three integers N, M and
T separated by one space (1 ≤ N ≤ 100, 1 ≤ M ≤ 1000, 1 ≤ T ≤ 1016). The second line contains one
integer K (1 ≤ K ≤ 1070). M lines follow, each of them describes
one of the rules according to which the bacteria behave.
The description consists of one string and exactly two integers
separated by one space. Possible descriptions and their meanings follow.
die i 0
All bacteria in the i-th colony die.
reproduce i k
The number of bacteria in the i-th colony
increases k times. (1 <= k <= 100)
copy i j
Increases the number of bacteria in the i-th colony by
the number of bacteria in the j-th colony.
teleport i j
Moves all bacteria from the j-th colony to
the i-th colony. (i != j)
swap i j
Exchanges all bacteria between the i-th and the j-th colony.
(i != j)
merry-go-round 0 0
Rotates all bacteria to the next colony, i.e.
moves all bacteria from the i-th to the i+1-th colony
(0 <= i < N-1 ) and
moves all bacteria from N-1-st to the 0-th colony.
All the moves occur at the same time.
Output file specification
For each colony print one line with the number of bacteria that will
live in this colony after T seconds.
Example
Input file
8 6 11
7
reproduce 2 5
copy 4 2
die 1 0
merry-go-round 0 0
teleport 5 3
swap 0 2
Output file
1
0
0
0
0
4
4
1
Note
The colonies evolved as follows:
Second |
Change |
Colonies |
0th | 1st | 2nd | 3rd | 4th | 5th | 6th | 7th |
beginning | |
1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
1st | reproduce 2 5 |
1 | 1 | 5 | 1 | 1 | 1 | 1 | 1 |
2nd | copy 4 2 |
1 | 1 | 5 | 1 | 6 | 1 | 1 | 1 |
3rd | die 1 0 |
1 | 0 | 5 | 1 | 6 | 1 | 1 | 1 |
4th | merry-go-round 0 0 |
1 | 1 | 0 | 5 | 1 | 6 | 1 | 1 |
5th | teleport 5 3 |
1 | 1 | 0 | 0 | 1 | 4 | 1 | 1 |
6th | swap 0 2 |
0 | 1 | 1 | 0 | 1 | 4 | 1 | 1 |
7th | reproduce 2 5 |
0 | 1 | 5 | 0 | 1 | 4 | 1 | 1 |
8th | copy 4 2 |
0 | 1 | 5 | 0 | 6 | 4 | 1 | 1 |
9th | die 1 0 |
0 | 0 | 5 | 0 | 6 | 4 | 1 | 1 |
10th | merry-go-round 0 0 |
1 | 0 | 0 | 5 | 0 | 6 | 4 | 1 |
11th | teleport 5 3 |
1 | 0 | 0 | 0 | 0 | 4 | 4 | 1 |
|