Description

There is a permutation of length $n$, initially in ascending order from $1$ to $n$, i.e. permutation $\{1,2,\ldots, n\}$. Now, $m$ consecutive shift operations will be performed on this permutation. There are two types of operations:

• $\texttt{a}$: Move the last number in the permutation to the front.
• $\texttt{b}$: Move the third number in the permutation to the front.

The consecutive operations are represented in the form of $k\texttt{a}$ or $k\texttt{b}$, where $k$ is the number of times the operation is repeated. Given the sequence of $m$ consecutive operations, please output the resulting permutation after performing the operations.

Input

The first line contains two integers $n,m\ (3\le n\le 10^5,1\le m\le 10^5)$, indicating the length of permutation and the number of operations.

The second line contains $m$ operations, each operation is a string formed in $k\texttt{a}$ or $k\texttt{b}$ ($1\le k\le 10^9$).

Output

Output $n$ integers in one line, indicating the resulting permutation.

Samples

4 3
3a 2b 2a

2 1 3 4

Note

1. After operation $3\texttt{a}$, the permutation becomes $\{2,3,4,1\}$.
2. After operation $2\texttt{b}$, the permutation becomes $\{3,4,2,1\}$.
3. After operation $2\texttt{a}$, the permutation becomes $\{2,1,3,4\}$.

Resources

电子科技大学第十四届 ACM 趣味程序设计竞赛