D. Безумные развороты
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана строка $$$s$$$ длиной $$$n$$$, состоящая их строчных латинских букв.

Затем вам будут даны положительное целое число $$$k$$$ и два массива $$$l$$$ и $$$r$$$ длиной $$$k$$$.

Гарантируется, что для этих двух массивов выполняются следующие условия:

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

Переворачивание подстроки $$$[a, b]$$$ строки $$$s$$$ означает, что $$$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$$$.

Выведите $$$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$$$ после выполнения всех операций.

Пример
Входные данные
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
Выходные данные
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».