310738: CF1878D. Reverse Madness

D. Reverse Madnesstime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given a string $s$ of length $n$, containing lowercase Latin letters.

Next you will be given a positive integer $k$ and two arrays, $l$ and $r$ of length $k$.

It is guaranteed that the following conditions hold for these 2 arrays:

• $l_1 = 1$;
• $r_k = n$;
• $l_i \le r_i$, for each positive integer $i$ such that $1 \le i \le k$;
• $l_i = r_{i-1}+1$, for each positive integer $i$ such that $2 \le i \le k$;

Now you will be given a positive integer $q$ which represents the number of modifications you need to do on $s$.

Each modification is defined with one positive integer $x$:

• Find an index $i$ such that $l_i \le x \le r_i$ (notice that such $i$ is unique).
• Let $a=\min(x, r_i+l_i-x)$ and let $b=\max(x, r_i+l_i-x)$.
• Reverse the substring of $s$ from index $a$ to index $b$.

Reversing the substring $[a, b]$ of a string $s$ means to make $s$ equal to $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}, \dots, s_{n-1}, s_n$.

Print $s$ after the last modification is finished.

Input

Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains two integers $n$ and $k$ ($1 \le k \le n \le 2\cdot 10^5$) — the length of the string $s$, and the length of arrays $l$ and $r$.

The second line of each test case contains the string $s$ ($ |s| = n$) containing lowercase Latin letters — the initial string.

The third line of each test case contains $k$ positive integers $l_1, l_2, \dots, l_k$ ($1 \le l_i \le n$) — the array $l$.

The fourth line of each test case contains $k$ positive integers $r_1, r_2, \dots, r_k$ ($1 \le r_i \le n$) — the array $r$.

The fifth line of each test case contains a positive integer $q$ ($1 \le q \le 2 \cdot 10^5 $) — the number of modifications you need to do to $s$.

The sixth line of each test case contains $q$ positive integers $x_1, x_2, \dots, x_q$ ($1\le x_i \le n$) — the description of the modifications.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot10^5$.

It is guaranteed that the sum of $q$ over all test cases does not exceed $2\cdot10^5$.

It is guaranteed that the conditions in the statement hold for the arrays $l$ and $r$.

Output

For each test case, in a new line, output the string $s$ after the last modification is done.

ExampleInput

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

Output

badc
abedc
gaf
jihgedcdga
a

Note

In the first test case:

The initial string is "abcd". In the first modification, we have $x=1$. Since $l_1=1\leq x \leq r_1=2$, we find the index $i = 1$. We reverse the substring from index $x=1$ to $l_1+r_1-x=1+2-1=2$. After this modification, our string is "bacd".

In the second modification (and the last modification), we have $x=3$. Since $l_2=3\leq x \leq r_2=4$, we find the index $i = 2$. We reverse the substring from index $x=3$ to $l_2+r_2-x=3+4-3=4$. After this modification, our string is "badc".

In the second test case:

The initial string is "abcde". In the first modification, we have $x=1$. Since $l_1=1\leq x \leq r_1=1$, we find the index $i = 1$. We reverse the substring from index $x=1$ to $l_1+r_1-x=1+1-1=1$. After this modification, our string hasn't changed ("abcde").

In the second modification, we have $x=2$. Since $l_2=2\leq x \leq r_2=2$, we find the index $i = 2$. We reverse the substring from index $x=2$ to $l_2+r_2-x=2+2-2=2$. After this modification, our string hasn't changed ("abcde").

In the third modification (and the last modification), we have $x=3$. Since $l_3=3\leq x \leq r_3=5$, we find the index $i = 3$. We reverse the substring from index $x=3$ to $l_3+r_3-x=3+5-3=5$. After this modification, our string is "abedc".

题目大意：
给定一个长度为n的由小写拉丁字母组成的字符串s。接下来给定一个正整数k和两个长度为k的数组l和r。保证以下条件对于这两个数组成立：
- l1 = 1;
- rk = n;
- 对于每个正整数i（1 ≤ i ≤ k）, li ≤ ri;
- 对于每个正整数i（2 ≤ i ≤ k）, li = ri-1 + 1。
然后给定一个正整数q，表示需要对s进行的修改次数。每次修改由一个正整数x定义：
- 找到一个索引i，使得li ≤ x ≤ ri（注意这样的i是唯一的）。
- 令a = min(x, ri + li - x) 和 b = max(x, ri + li - x)。
- 反转从索引a到索引b的s的子字符串。
反转字符串s中从索引a到索引b的子字符串意味着使s等于s1, s2, …, sa-1, sb, sb-1, …, sa+1, sa, sb+1, sb+2, …, sn-1, sn。
在完成最后修改后打印s。

输入输出数据格式：
每个测试包含多个测试案例。第一行包含一个整数t（1 ≤ t ≤ 10^4）——测试案例的数量。接下来是t个测试案例的描述。
每个测试案例的第一行包含两个整数n和k（1 ≤ k ≤ n ≤ 2·10^5）——字符串s的长度和数组l和r的长度。
每个测试案例的第二行包含一个长度为n的字符串s，只包含小写拉丁字母——初始字符串。
每个测试案例的第三行包含k个正整数l1, l2, …, lk（1 ≤ li ≤ n）——数组l。
每个测试案例的第四行包含k个正整数r1, r2, …, rk（1 ≤ ri ≤ n）——数组r。
每个测试案例的第五行包含一个正整数q（1 ≤ q ≤ 2·10^5）——需要对s进行的修改次数。
每个测试案例的第六行包含q个正整数x1, x2, …, xq（1 ≤ xi ≤ n）——修改的描述。
保证所有测试案例的n之和不超过2·10^5。
保证所有测试案例的q之和不超过2·10^5。
保证数组l和r的条件在题目描述中成立。

对于每个测试案例，输出在完成最后修改后字符串s的结果。题目大意： 给定一个长度为n的由小写拉丁字母组成的字符串s。接下来给定一个正整数k和两个长度为k的数组l和r。保证以下条件对于这两个数组成立： - l1 = 1; - rk = n; - 对于每个正整数i（1 ≤ i ≤ k）, li ≤ ri; - 对于每个正整数i（2 ≤ i ≤ k）, li = ri-1 + 1。 然后给定一个正整数q，表示需要对s进行的修改次数。每次修改由一个正整数x定义： - 找到一个索引i，使得li ≤ x ≤ ri（注意这样的i是唯一的）。 - 令a = min(x, ri + li - x) 和 b = max(x, ri + li - x)。 - 反转从索引a到索引b的s的子字符串。 反转字符串s中从索引a到索引b的子字符串意味着使s等于s1, s2, …, sa-1, sb, sb-1, …, sa+1, sa, sb+1, sb+2, …, sn-1, sn。 在完成最后修改后打印s。 输入输出数据格式： 每个测试包含多个测试案例。第一行包含一个整数t（1 ≤ t ≤ 10^4）——测试案例的数量。接下来是t个测试案例的描述。 每个测试案例的第一行包含两个整数n和k（1 ≤ k ≤ n ≤ 2·10^5）——字符串s的长度和数组l和r的长度。 每个测试案例的第二行包含一个长度为n的字符串s，只包含小写拉丁字母——初始字符串。 每个测试案例的第三行包含k个正整数l1, l2, …, lk（1 ≤ li ≤ n）——数组l。 每个测试案例的第四行包含k个正整数r1, r2, …, rk（1 ≤ ri ≤ n）——数组r。 每个测试案例的第五行包含一个正整数q（1 ≤ q ≤ 2·10^5）——需要对s进行的修改次数。 每个测试案例的第六行包含q个正整数x1, x2, …, xq（1 ≤ xi ≤ n）——修改的描述。 保证所有测试案例的n之和不超过2·10^5。 保证所有测试案例的q之和不超过2·10^5。 保证数组l和r的条件在题目描述中成立。 对于每个测试案例，输出在完成最后修改后字符串s的结果。