Description

给出一个排列，初始为$\left\{1, 2, 3, ...., n \right\}$。有两种操作：

a.将排列的最后一个数放在最前面。 b.将排列的第三个数字放在最前面。

接下来，我们用 $ka$ 或 $kb$ 来表示连续进行了 $k$ 次 $a$ 操作或者 $k$ 次 $b$ 操作。在 $m$ 次这样的操作之后，你需要输出最后的排列。

Format

Input

第一行两个正整数，含义见题面。 第二行输入 $m$ 个形如 $ka$ 或者 $kb$ 的字符串。其中 $k$ 是一个正整数，表示要进行的连续操作。

Output

输出一行 $n$ 个数，表示经过 $m$ 次操作之后的排列。

Samples

4 3
3a 2b 2a

2 1 3 4

Limitation

对于 $30\%$ 的数据，$1 \leq n, m \leq 100$, $\sum k \leq 100$。 对于 $100\%$ 的数据，$1 \leq n, m \leq 5 \times 10 ^5$, $1 \leq k \leq 10^{18}$。