Migrated from Lutece 2872 运动会

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

运动会上的一个经典保留节目就是方阵表演了。当然，因为太累，所以没有人愿意参加这个项目。

$\text{Fe}^{3+}$ 硬凑了 $n$ 个哲♂学家来进行这个项目的表演。他们的表演方式很奇怪，是 $k$ 个动作的一直重复。

他们这套动作，由 $\text{Fe}^{3+}$ 统一发号施令：

• + i：让第 $i$ 位哲学家举起一朵 Fa♂；
• E i：让第 $i$ 位哲学家乖♂乖放下手上的所有 Fa♂；
• S i j：让第 $i$ 位哲学家和第 $j$ 位哲学家交换他们所有的 Fa♂（保证 $i\neq j$）。

主席台的大佬们觉得这个表演太单调了，于是他们就想直接知道第 $i$ 个哲学家做了 $m_i$ 套动作后举起了几朵 Fa♂。

Input

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

接下来 $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$ 套动作后举起了几朵 Fa♂。

Output

输出一行 $n$ 个整数，第 $i$ 个输出的整数表示第 $i$ 位哲学家做了 $m_i$ 套动作后举起的 Fa♂ 的数量。两个整数之间用一个空格隔开。

Samples

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

0 0 0 1 0

Note

对于第一套动作的每一个动作后，每位哲学家举起的 Fa♂ 的数量如下：

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

之后一直循环这套动作，可以看成结束时第 $1$ 位哲学家始终让第 $4$ 位哲学家只举起 $1$ 朵 Fa♂，因此每套动作的最后只有第 $4$ 位哲学家举着 $1$ 朵 Fa♂。

Resources

The 20th UESTC Programming Contest Preliminary