2567. [東方] 蓬莱山·辉夜 壹

【题目描述】

永恒与须臾的置换！

「那就让满月从此消失于地上好了。

如此一来，当能中断连接月球与地上之间的通道。

其实从地上看到的满月，正是唯一能打开那通道的钥匙。

所以，月之使者亦只有于满月才能到访。

要是破坏那钥匙的话……

地上，就成为一个巨大的密室了。」

完美的计划。

真正的满月消失了，地上的人类和妖怪们还是发现了一些蛛丝马迹，便要打破辉夜的幻术。

辉夜的幻术是永恒与须臾之力同时作用的结果。须臾是很短的时间，永恒则是很长的时间。在一个须臾内，幻术阵法可以完成一个变换，T个须臾之后，则会由量变达成质变，须臾化作永恒，幻术阵法便会不攻自破。

但是地上的人们和妖怪们发现，等到幻术阵法自破需要的时间太长了，有一种快速的破阵方法，那就是直接计算出阵法在T个须臾之后的格局。

阵法可以看作是由N个小魔法阵，从阵法基石开始，围成一圈构成，按逆时针位置编号为0, 1, 2...N-1(每个小魔法阵的编号取决于它所在的位置)。整个阵法建立之初，每个小魔法阵里面只有 1 点能量。每个须臾，这些魔法阵可以进行这样的变换的其中之一：

clear a 0 表示将第a个魔法阵的能量清零

derive a b 表示将第b个魔法阵里面的能量都转移到魔法阵a里面(注意b的能量转移到a里面这样b里面就没有能量了)

swap a b 表示将第a个魔法阵与第b个魔法阵交换位置

multiply a b 表示将第a个魔法阵的能量变为原来的b倍

rotate 0 0表示每个魔法阵都转移到它逆时针方向上下一个魔法阵的位置

T个须臾里面，整个幻术法阵循环往复地执行着M条变换规则。而且由于小魔法阵储存能量的能力有限，所以小魔法阵里面一旦有超过P点的能量值的话，每P点能量都会被压缩成一团而被排斥消失。

众人与众妖怪通过仔细观察记录，发现了幻术法阵变换的规律，也就是法阵重复执行的M条变换规则，并且计算出了小魔法阵的能量阈值P，而且通过查阅上古传说，知道了永恒的时间T。现在这些资料都将交给你，请你帮忙计算出T个须臾后法阵中，每个小魔法阵的能量值。

注意看提示里面的样例解释(

【输入格式】

第一行四个整数T, N, M, P。含义请仔细阅读题面

接下来M行，每行一条变换规则，格式为一个单词+2个参数，即一个字符串与两个参数。变换规则具体请仔细阅读题面。

【输出格式】

一行N个整数，依次为，从阵法基石(请仔细阅读题面)开始按逆时针位置，编号为0, 1, 2..N-1的小魔法阵中的魔法值。

【样例输入】

样例输入1:

5 4 3 233

rotate 0 0

derive 1 3

multiply 0 2

样例输入2:

100 12 11 1000000007

multiply 8 2

derive 11 3

swap 0 4

rotate 0 0

multiply 9 4

derive 5 10

multiply 7 2

swap 8 1

multiply 7 5

rotate 0 0

clear 7 0

【样例输出】

output1:

 0 3 2 0

  output2:

12800 2 0 1 0 0 12800 0 129600 0 57600 0

【提示】

/*
T 0        1        2        3        4        5 
 init    rotate  derive  multiply   rotate   derive
  1        1        1        1        2        2
1   1 -> 1   1 -> 0   2 -> 0   2 -> 1   2 -> 0   3
  1        1        1        2        0        0
  ↑
 箭头指向0位置，逆时针方向0,1,2,3
 最后T = 5时，按照顺时针方向从0开始，小魔法阵能量依次为0 3 2 0
*/

数据范围:

对于前40%的数据



1 <= T <= 10^6



对于全部的数据：



1 <= T <= 10^15



2 <= N <= 50



1 <= M <= 20



P在signed int范围内

【来源】

《算法艺术与信息学竞赛》第二章。 题面来自sxysxy。