该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

橱窗折影

题目描述

有一排 $n$ 个抽屉，编号为 $1$ 到 $n$。保证 $n$ 为偶数。

第 $i$ 个抽屉里有一个整数 $a_i$。

抽屉前面盖着一张透明编号膜。编号膜上有 $n$ 个窗口，窗口也从左到右编号为 $1$ 到 $n$。

初始时，第 $i$ 个窗口正对第 $i$ 个抽屉。

之后会进行 $q$ 次操作，操作分为以下五种：

• F：把透明膜左右翻转。

  翻转后，第 $i$ 个窗口会看到原来第 $n+1-i$ 个窗口看到的抽屉。

• C：捏一下透明膜。

  捏膜后，每一对相邻窗口交换看到的抽屉，即窗口 $(1,2),(3,4),\ldots,(n-1,n)$ 分别交换看到的抽屉。

• S x y：交换当前第 $x$ 个窗口和第 $y$ 个窗口看到的两个抽屉里的数。

• A x v：给当前第 $x$ 个窗口看到的抽屉里的数加上 $v$。

• Q x：输出当前第 $x$ 个窗口看到的抽屉里的数。

需要注意的是，F 和 C 只会改变“窗口看到哪个抽屉”，不会移动抽屉本身。

输入格式

第一行包含两个整数 $n$ 和 $q$（$2 \le n \le 2 \times 10^5$，$1 \le q \le 2 \times 10^5$，且 $n$ 为偶数），表示抽屉数量和操作次数。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$|a_i| \le 10^9$），表示每个抽屉中的初始整数。

接下来 $q$ 行，每行表示一次操作。操作格式为以下五种之一：

• F
• C
• S x y（$1 \le x,y \le n$）
• A x v（$1 \le x \le n$，$|v| \le 10^9$）
• Q x（$1 \le x \le n$）

保证所有操作过程中出现的数值都在 64 位有符号整数范围内。

输出格式

对于每个 Q 操作，输出一行一个整数，表示当前第 $x$ 个窗口看到的抽屉里的数。

输入输出样例 #1

输入 #1

6 9
10 20 30 40 50 60
Q 1
C
Q 1
S 1 6
F
Q 1
A 2 7
F
Q 5

输出 #1

10
20
20
67

说明/提示

初始时，窗口看到的抽屉顺序为：

1 2 3 4 5 6

第一次询问 Q 1，第 $1$ 个窗口看到第 $1$ 个抽屉，答案为 $10$。

执行 C 后，窗口看到的抽屉顺序变为：

2 1 4 3 6 5

所以第二次询问 Q 1，第 $1$ 个窗口看到第 $2$ 个抽屉，答案为 $20$。

接着执行 S 1 6，当前第 $1$ 个窗口看到第 $2$ 个抽屉，第 $6$ 个窗口看到第 $5$ 个抽屉，因此交换的是第 $2$ 个和第 $5$ 个抽屉里的数。

执行 F 后再询问 Q 1，此时第 $1$ 个窗口看到第 $5$ 个抽屉，该抽屉中的值为 $20$。

之后执行 A 2 7，当前第 $2$ 个窗口看到第 $6$ 个抽屉，因此第 $6$ 个抽屉中的数从 $60$ 变为 $67$。

最后再次执行 F，询问 Q 5，此时第 $5$ 个窗口看到第 $6$ 个抽屉，答案为 $67$。