#1726. 药水生产

药水生产

题目描述

你的工厂中有 nn 台机器生产同一种药水,每台机器前面都有一个药水池来存放生产好的药水。你编制了一份长度为 kk 的药水生产方案,方案中,每个单位时间执行下面三个操作之一:

  • + i:让第 ii 台机器生产一单位药水,并放在它所属的药水池中;
  • E i:清空第 ii 台机器所属的药水池,把这些药水运输到灌装车间;
  • S i j:为了不使药水池因盛放过多药水而溢出,将第 ii 台机器的药水池中的药水和第 jj 台中的药水交换(保证 iji\neq j)。

nn 台机器不断重复这份生产方案,你想知道第 ii 台机器在重复了 mim_i 次生产方案后,它所属的药水池中有多少单位的药水。

输入

第一行两个正整数 n,k (1n,k106)n,k\ (1\le n,k\le 10^6)

接下来 kk 行,表示这套方案中的每一个操作,保证 1i,jn,ij1\le i,j\le n,i\neq j

接下来一行 nn 个整数 m1,m2,,mn (1mi109)m_1,m_2,\ldots,m_n\ (1\le m_i\le 10^9),第 ii 个整数表示你想知道第 ii 台机器在重复了 mim_i 次生产方案后,它所属的药水池中有多少单位的药水。

输出

输出一行 nn 个整数表示答案。两个整数之间用一个空格隔开。

样例

样例输入

5 3
+ 1
S 1 4
E 1
1 2 3 4 5

样例输出

0 0 0 1 0

样例说明

对于第一次进行该生产方案的每一个操作后,每台机器所属药水池中的药水体积如下:

  1. [1,0,0,0,0][1,0,0,0,0]
  2. [0,0,0,1,0][0,0,0,1,0]
  3. [0,0,0,1,0][0,0,0,1,0]

之后一直循环这个生产方案,可以看成结束时第 11 台机器始终让第 44 台机器只有一单位体积药水,因此每套动作的最后只有第 44 台机器所属的药水池有一单位体积药水。

数据范围

本题共 2020 组数据。

对于 15%15\% 的数据,n,k100n,k\le 100

对于另 15%15\% 的数据,k105,mi100k\le 10^5,m_i\le 100

对于另 30%30\% 的数据,n105n\le 10^5

对于全部数据,1n,k106,1mi109,1i,jn,ij1\le n,k\le 10^6,1\le m_i\le 10^9,1\le i,j\le n,i\neq j