wwx 的羊腿生产

题目描述

wwx 的羊腿工厂中有 $n$ 台机器可以生产羊腿，每台机器前面都有一个存储箱来存放生产好的羊腿。

而 wwx 编制了一份长度为 $k$ 的生产方案，方案中，每个单位时间执行下面三个操作之一：

• i：让第 $i$ 台机器生产一个羊腿，并放在它所属的存储箱中；

E i：清空第 $i$ 台机器所属的存储箱，把这些羊腿送到 wwx 家里；

S i j：将第 $i$ 台机器的存储箱中的羊腿和第 $j$ 台中的羊腿交换（保证 $i\neq j$）。

这 $n$ 台机器不断循环执行这份生产方案

现在 wwx 想知道第 $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$ 个整数表示 wwx 想知道第 $i$ 台机器在重复了 $m_i$ 轮生产方案后，它所属的存储箱中有多少个羊腿。

输出格式

输出一行包含 $n$ 个整数，表示每次询问的答案

数据范围

本题共 $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$。

样例输入

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

样例输出

0 0 0 1 0

样例说明

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

$[1,0,0,0,0]$

$[0,0,0,1,0]$

$[0,0,0,1,0]$

之后一直循环这个生产方案，可以发现结束时第 $1$ 台机器始终让第 $4$ 台机器只有一个羊腿，因此每次方案执行一轮，最后只有第 $4$ 台机器所属的存储箱有一个羊腿