Великий маг планирует составить магическое заклинание. Заклинание состоит из рун, которые будем обозначать целыми числами. Заклинание, которое планирует составить маг, представляет собой перестановку $$$p$$$, состоящую из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$.
Для составления заклинания маг может использовать специальный волшебный справочник, содержащий $$$m$$$ страниц, пронумерованных от $$$1$$$ до $$$m$$$, на каждой из которых записана одна руна, целое число от $$$1$$$ до $$$n$$$. К сожалению, маг уже стар и не может сам переписывать руны из справочника; к счастью, у него есть $$$k$$$ учеников, которых он может в некотором порядке призвать к себе и попросить переписать фрагменты справочника на один общий длинный свиток. Если призвать $$$i$$$-го ученика, то он по порядку перепишет на свиток руны со страниц справочника от $$$l_i$$$-й до $$$r_i$$$-й, включительно. Учеников можно призывать в любом порядке, но каждого ученика можно призвать не более одного раза.
Например, пусть в справочнике $$$m=6$$$ рун записаны в следующем порядке: $$$[2, 1, 3, 1, 2, 4]$$$, у мага $$$k=3$$$ ученика с $$$l_1=5$$$, $$$r_1=6$$$; $$$l_2=2$$$, $$$r_2=6$$$ и $$$l_3=1$$$, $$$r_3=3$$$.
Если призвать сначала третьего, а затем первого ученика, они выпишут на свиток руны в следующем порядке: $$$[2, 1, 3, 2, 4]$$$.
А если призвать сначала второго, затем первого и затем третьего ученика, то на свитке получится последовательность рун $$$[1, 3, 1, 2, 4, 2, 4, 2, 1, 3]$$$.
После того, как на свиток будет переписано некоторое количество рун, маг может вырезать любой непрерывный отрезок свитка. Он хочет призвать минимальное количество учеников, чтобы в итоге он мог, вырезав непрерывный отрезок получившегося свитка, получить искомое магическое заклинание.
В примере выше, если заклинание представляет собой перестановку $$$[1, 3, 2, 4]$$$, то его можно получить, призвав сначала третьего, а затем первого ученика, и вырезав из получившегося свитка $$$[2, 1, 3, 2, 4]$$$ руны со 2-й по 5-ю.
Помогите магу определить, какое минимальное количество учеников он должен призвать и в каком порядке их нужно призывать, чтобы составить искомое заклинание, если это возможно.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^5$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$1 \le n \le 3 \cdot 10^5$$$, $$$1 \le m \le 3 \cdot 10^5$$$, $$$1 \le k \le 3 \cdot 10^5$$$) — длина перестановки $$$p$$$, количество страниц в книге и количество учеников.
Следующая строка содержит $$$n$$$ различных целых чисел $$$p_i$$$ ($$$1 \le p_i \le n$$$) — перестановку $$$p$$$. Гарантируется, что все $$$p_i$$$ попарно различны.
Следующая строка содержит $$$m$$$ целых чисел $$$a_i$$$ ($$$1 \le a_i \le n$$$) — руны, содержащиеся в книге.
Следующие $$$k$$$ строк содержат по два целых числа, $$$i$$$-я из них содержит числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \le r_i \le m$$$), задающие отрезок страниц, которые переписывает $$$i$$$-й ученик.
Гарантируется, что суммы $$$n$$$, $$$m$$$ и $$$k$$$ по всем наборам входных данных не превосходят $$$3 \cdot 10^5$$$ соответственно.
Для каждого набора входных данных, если нельзя призвать учеников в некотором порядке так, чтобы перестановка $$$p$$$ входила в выписанную на свиток последовательность рун как подотрезок, то выведите $$$-1$$$.
Иначе выведите число $$$c$$$ — минимальное количество призываемых учеников.
В следующей строке выведите $$$c$$$ чисел — номера учеников в порядке, в котором их следует призывать. Ученики нумеруются целыми числами от $$$1$$$ до $$$k$$$ в порядке перечисления во входных данных. Все номера учеников должны быть попарно различными.
Если существует несколько оптимальных ответов, выведите любой из них.
24 6 31 3 2 42 1 3 1 2 45 62 61 33 4 13 1 22 1 3 11 4
23 1-1