题目描述

小 Z 手头有个长度为 $2n$ 字符串 $S$，他可以对字符串进行两种操作：

• $op=1:$ 将字符串的第 $i$ 号位置与第 $j$ 号位置互换；
• $op=2:$ 将字符串的前后半段互换，即若原来为 $S_1S_2S_3...S_nS_{n+1}S_{n+2}...S_{2n}$，操作后变为 $S_{n+1}S_{n+2}...S_{2n}S_1S_2S_3...S_n$；

小 Z 一共进行了 $q$ 次操作，求操作完毕之后的字符串 $S$。

输入格式

第一行，$2$ 个正整数 $n,q$，表示字符串 $S$ 的长度为 $2n$，共有 $q$ 次操作。

第二行，字符串 $S$（仅包含字母）。

接下来 $q$ 行，每一行表示一次操作：

• $1, i, j$：表示将第 $i,j$ 位互换；
• $2$：表示前后半段互换；

输出格式

操作完成之后的字符串。

输入输出样例

2 2
flip
2
1 1 4

lpfi

样例 $\tt \#1$说明

• 第一次操作后，字符串变为 ipfl。
• 第二次操作后，字符串变为 lpfi。

数据范围

• 对于 $30\%$ 的数据，$1 \leq n,q \leq 2000$​
• 对于 $60\%$ 的数据，保证操作 $2$ 的次数不超过 $2000$ 次
• 对于所有测评数据，$1 \leq n,q \leq 10^5$