给你一个长度为 $$$n$$$ 的字符串 $$$s$$$,包含小写拉丁字母。
接下来,您将得到一个正整数 $$$k$$$ 和两个数组,$$$l$$$ 和 $$$r$$$,长度为 $$$k$$$。
这 2 个数组保证满足以下条件:
- $$$l_1 = 1$$$;
- $$$r_k = n$$$;
- $$$l_i \le r_i$$$,对于每个正整数 $$$i$$$ 使得 $$$1 \le i \le k$$$;
- $$$l_i = r_{i-1}+1$$$,对于每个正整数 $$$i$$$ 使得 $$$2 \le i \le k$$$;
现在您将得到一个正整数 $$$q$$$,它代表您需要对 $$$s$$$ 进行的修改次数。
每个修改都用一个正整数 $$$x$$$ 定义:
- 找到一个索引 $$$i$$$ 使得 $$$l_i \le x \le r_i$$$ (注意这样的 $$$i$$$ 是唯一的)。
- 让 $$$a=\min(x, r_i+l_i-x)$$$ 并让 $$$b=\max(x, r_i+l_i-x)$$$。
- 将 $$$s$$$ 的子字符串从索引 $$$a$$$ 反转到索引 $$$b$$$。
反转字符串 $$$s$$$ 的子串 $$$[a, b]$$$ 意味着使 $$$s$$$ 等于 $$$s_1, s_2, \dots, s_{a-1},\ s_b, s_{b-1}, \dots, s_{a+1}, s_a,\ s_{b+1}、s_{b+2}、\点、s_{n-1}、s_n$$$。
最后一次修改完成后打印$$$s$$$。
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le n \le 2\cdot 10^5$$$) - 字符串 $$$s$$$ 的长度,以及数组 $$$l$$$ 和 $$$r$$$ 的长度。
每个测试用例的第二行包含字符串 $$$s$$$ ($$$ |s| = n$$$),其中包含小写拉丁字母 - 初始字符串。
每个测试用例的第三行包含 $$$k$$$ 正整数 $$$l_1, l_2, \dots, l_k$$$ ($$$1 \le l_i \le n$$$) — 数组 $$$l$$$。
每个测试用例的第四行包含 $$$k$$$ 正整数 $$$r_1, r_2, \dots, r_k$$$ ($$$1 \le r_i \le n$$$) — 数组 $$$r$$$。
每个测试用例的第五行包含一个正整数 $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5 $$$) - 您需要对 $$$s$$$ 进行的修改数量。
每个测试用例的第六行包含 $$$q$$$ 正整数 $$$x_1, x_2, \dots, x_q$$$ ($$$1\le x_i \le n$$$) — 修改的描述。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot10^5$$$。
保证所有测试用例的 $$$q$$$ 总和不超过 $$$2\cdot10^5$$$。
保证语句中的条件对于数组 $$$l$$$ 和 $$$r$$$ 成立。
输出
对于每个测试用例,在新行中输出最后一次修改完成后的字符串 $$$s$$$。
示例
输入 #1
5 4 2 abcd 1 3 2 4 2 1 3 5 3 abcde 1 2 3 1 2 5 3 1 2 3 3 1 gaf 1 3 2 2 2 10 1 aghcdegdij 1 10 5 1 2 3 4 2 1 1 a 1 1 1 1
输出 #1
badc abedc gaf jihgedcdga a
注意
在第一个测试用例中:
初始字符串是“abcd”。在第一个修改中,我们有 $$$x=1$$$。由于$$$l_1=1\leq x \leq r_1=2$$$,我们找到索引$$$i = 1$$$。我们将子字符串从索引 $$$x=1$$$ 反转为 $$$l_1+r_1-x=1+2-1=2$$$。修改后,我们的字符串是“bacd”。
在第二次修改(也是最后一次修改)中,我们有 $$$x=3$$$。由于$$$l_2=3\leq x \leq r_2=4$$$,我们找到索引$$$i = 2$$$。我们将子字符串从索引 $$$x=3$$$ 反转为 $$$l_2+r_2-x=3+4-3=4$$$。修改后,我们的字符串是“badc”。
在第二个测试用例中:
初始字符串是“abcde”。在第一个修改中,我们有 $$$x=1$$$。由于$$$l_1=1\leq x \leq r_1=1$$$,我们找到索引$$$i = 1$$$。我们将子字符串从索引 $$$x=1$$$ 反转为 $$$l_1+r_1-x=1+1-1=1$$$。修改后,我们的字符串没有改变(“abcde”)。
在第二个修改中,我们有 $$$x=2$$$。由于 $$$l_2=2\leq x \leq r_2=2$$$,我们找到索引 $$$i = 2$$$。我们将子字符串从索引 $$$x=2$$$ 反转为 $$$l_2+r_2-x=2+2-2=2$$$。修改后,我们的字符串没有改变(“abcde”)。
在第三次修改(也是最后一次修改)中,我们有 $$$x=3$$$。由于 $$$l_3=3\leq x \leq r_3=5$$$,我们找到索引 $$$i = 3$$$。我们将子字符串从索引 $$$x=3$$$ 反转为 $$$l_3+r_3-x=3+5-3=5$$$。修改后,我们的字符串是“abedc”。