IPSC 2003 Problem H – Hordes of Bacteria

IPSC 2003

Problem H – Hordes of Bacteria

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. The second line contains one integer K. 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

Note

The colonies evolved as follows: