题目描述

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

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

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

输入

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

接下来 $k$ 行，表示这套方案中的每一个操作，保证 $1\le i,j\le n,i\neq j$。

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

输出

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

样例

样例输入

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

样例输出

0 0 0 1 0

样例说明

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

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

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

数据范围

本题共 $20$ 组数据。

对于 $15\%$ 的数据，$n,k\le 100$。

对于另 $15\%$ 的数据，$k\le 10^5,m_i\le 100$。

对于另 $30\%$ 的数据，$n\le 10^5$。

对于全部数据，$1\le n,k\le 10^6,1\le m_i\le 10^9,1\le i,j\le n,i\neq j$。