编程历史与哲学系（PHP）系主任 E.D. Pryanik 教授坚信，只有彻底研读过他那部基础著作《程序设计科学》中全部 $n$ 卷内容的同学，才能在他的指导下撰写学年论文。学生必须研读所有书籍，之后 E.D. Pryanik 才会对他进行面试。如果教授对结果满意，他会为该学生分配一个学年论文题目。

教授希望你帮忙追踪他办公室书架上书籍的顺序。书架上包含 $n$ 本书，编号为 $1$ 到 $n$ 的整数。保证 $n$ 是一个偶数。书架可以表示为 $1$ 到 $n$ 的一个整数排列——即书架上书籍的顺序。

书架上会发生两种操作：

• 教授交换书架上的两本书。
• 一名新学生来到办公室阅读全部 $n$ 本书。 他按 $1$ 到 $n$ 的顺序阅读书籍：
  • 学生 $n$ 次取走下一本书。书的位置上留下一个空位。
  • 如果空位左侧的书籍数量少于空位右侧的书籍数量，他将空位左侧的所有书籍向右移动一个位置。否则，他将空位右侧的所有书籍向左移动一个位置。结果，空位会移动到最左侧或最右侧。
  • 学生将书放回空位。

给定书架上书籍的初始顺序和一系列操作，请在执行完所有操作后告诉教授书架上书籍的最终顺序。

输入格式

第一行包含两个整数 $n, q$ ($2 \le n, q \le 3 \cdot 10^5$)。保证 $n$ 是一个偶数。 第二行包含一个 $1$ 到 $n$ 的排列——书架上书籍的初始顺序。 接下来的 $q$ 行，每行包含一个操作的描述。每行以符号 “E” 或 “R” 开头，描述操作类型。

• 如果符号为 “E”，该行包含两个整数 $i, j$ ($1 \le i, j \le n, i \neq j$) —— 需要交换的书籍的编号（指书籍的编号，而非排列中的位置）。
• 如果符号为 “R”，则表示学生来到办公室阅读所有书籍。

输出格式

输出 $n$ 个数字——书架上书籍的最终顺序。

样例

输入 1

8 4
7 2 6 1 8 3 5 4
R
E 2 3
R
E 1 6

输出 1

7 1 3 6 2 4 5 8