Сплетня
(Время: 2 сек. Память: 64 Мб Сложность: 57%)
Опишем процесс распространения сплетни в коллективе из n человек. Зададим последовательность различных чисел p1, p2, …,pn – порядок, в котором люди узнают о сплетне. Человек с номером p1 является инициатором сплетни, а остальные узнают о ней от предыдущего, то есть pi узнаёт от pi−1 для 2 ≤ i.
Есть сплетня, которую нужно распространить особым образом. Дана последовательность различных номеров людей s1, s2, …, sm, где
2 ≤ m. Она означает следующее:
- человек s1 – инициатор сплетни;
- для каждого 2 ≤ i ≤ m человек si должен узнать о сплетне позже, чем si−1;
- человек sm должен узнать о сплетне последним среди всех n человек.
Для каждого человека определено целое число ai. Эти величины означают, что если человек i хочет рассказать сплетню человеку j, то на это уйдёт |ai − aj| минут.
Определите порядок pi, который удовлетворяет требованиям выше и при котором потратится наименьшее количество времени, чтобы о сплетне узнали все n человек.
Входные данные
Первая строка входного файла INPUT.TXT содержит целое число t – количество наборов входных данных (1 ≤ t ≤ 30
000).
Каждый набор состоит из трёх строк. В первой строке записаны два целых числа n и m (2 ≤ m ≤ n ≤ 300 000).
Вторая строка содержит n целых чисел a1, a2, …, an (1 ≤ ai ≤ 109).
В третьей строке содержатся m различных целых чисел s1, s2, …, sm (1 ≤ si ≤ n).
Гарантируется, что сумма n по всем наборам не превосходит 300 000.
Выходные данные
Для каждого тестового набора в выходной файл OUTPUT.TXT выведите n чисел в отдельной строке – оптимальный порядок распространения сплетни. Разрешается выводить любой подходящий вариант.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3
5 3
1 2 3 4 5
3 2 5
5 2
10 10 10 10 10
4 1
8 3
83 90 3 11 81 43 87 58
3 1 8 | 3 1 2 4 5
4 3 5 2 1
3 4 6 1 7 2 5 8 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
