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 (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
0th1st2nd3rd4th5th6th7th
beginning 11111111
1streproduce 2 5 11511111
2ndcopy 4 2 11516111
3rddie 1 0 10516111
4thmerry-go-round 0 0 11051611
5thteleport 5 3 11001411
6thswap 0 2 01101411
7threproduce 2 5 01501411
8thcopy 4 2 01506411
9thdie 1 0 00506411
10thmerry-go-round 0 0 10050641
11thteleport 5 3 10000441