CF1878D.Reverse Madness

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.

给你一个长度为 $n$ 的字符串 $s$，其中仅包含小写拉丁字母。

接下来，你会得到一个正整数 $k$ 和两个长度均为 $k$ 的数组 $l$ 和 $r$。

保证这两个数组满足以下条件：

• $l_1 = 1$；
• $r_k = n$；
• 对每个满足 $1 \le i \le k$ 的正整数 $i$，有 $l_i \le r_i$；
• 对每个满足 $2 \le i \le k$ 的正整数 $i$，有 $l_i = r_{i-1}+1$；

随后，你将得到一个正整数 $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}, \dots, s_{n-1}, s_n$。

请输出在完成所有 $q$ 次修改后最终的字符串 $s$。

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$.

每个测试包含多个测试用例。第一行包含一个整数 $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$ 均成立。

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

对于每个测试用例，在新的一行中输出完成最后一次修改后的字符串 $s$。

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".

在第一个测试用例中：

初始字符串为 "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"。