Дана строка \(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\) после выполнения всех операций.
Примечание
В первом наборе входных данных:
Исходная строка — «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».
Примеры
| № | Входные данные | Выходные данные |
|
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
|
badc
abedc
gaf
jihgedcdga
a
|