K. Magic Spell
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

The great wizard plans to compose a magic spell. The spell consists of runes, which we will denote by integers. The spell that the wizard plans to create is a permutation $$$p$$$ consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$.

To compose the spell, the wizard can use a special magical reference book containing $$$m$$$ pages, numbered from $$$1$$$ to $$$m$$$, each of which contains one rune, an integer from $$$1$$$ to $$$n$$$. Unfortunately, the wizard is already old and cannot rewrite the runes from the reference book himself; fortunately, he has $$$k$$$ students whom he can summon in some order and ask to transcribe fragments of the reference book onto one common long scroll. If the $$$i$$$-th student is summoned, he will sequentially transcribe the runes from the reference book from the $$$l_i$$$-th to the $$$r_i$$$-th page, inclusive. Students can be summoned in any order, but each student can be summoned no more than once.

For example, suppose the reference book has $$$m=6$$$ runes written in the following order: $$$[2, 1, 3, 1, 2, 4]$$$, and the wizard has $$$k=3$$$ students with $$$l_1=5$$$, $$$r_1=6$$$; $$$l_2=2$$$, $$$r_2=6$$$; and $$$l_3=1$$$, $$$r_3=3$$$.

If the third student is summoned first and then the first student, they will write the runes onto the scroll in the following order: $$$[2, 1, 3, 2, 4]$$$.

However, if the second student is summoned first, then the first, and then the third student, the resulting sequence of runes on the scroll will be $$$[1, 3, 1, 2, 4, 2, 4, 2, 1, 3]$$$.

After the runes have been transcribed onto the scroll, the wizard can cut out any continuous segment of the scroll. He wants to summon the minimum number of students so that he can obtain the desired magic spell by cutting out a continuous segment from the resulting scroll.

In the example above, if the spell is the permutation $$$[1, 3, 2, 4]$$$, it can be obtained by summoning the third student first and then the first student, and cutting out from the resulting scroll $$$[2, 1, 3, 2, 4]$$$ the runes from the 2nd to the 5th.

Help the wizard determine the minimum number of students he must summon and in what order they should be summoned to create the desired spell, if possible.

Input

Each test consists of several sets of input data. The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of sets of input data. The following describes the sets of input data.

The first line of each set of input data contains three integers $$$n$$$, $$$m$$$, and $$$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$$$) — the length of the permutation $$$p$$$, the number of pages in the book, and the number of students.

The next line contains $$$n$$$ distinct integers $$$p_i$$$ ($$$1 \le p_i \le n$$$) — the permutation $$$p$$$. It is guaranteed that all $$$p_i$$$ are pairwise distinct.

The next line contains $$$m$$$ integers $$$a_i$$$ ($$$1 \le a_i \le n$$$) — the runes contained in the book.

The following $$$k$$$ lines each contain two integers; the $$$i$$$-th of them contains the numbers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le m$$$), defining the segment of pages that the $$$i$$$-th student transcribes.

It is guaranteed that the sums of $$$n$$$, $$$m$$$, and $$$k$$$ across all sets of input data do not exceed $$$3 \cdot 10^5$$$ respectively.

Output

For each set of input data, if it is impossible to summon students in some order such that the permutation $$$p$$$ is a subsegment of the sequence of runes written on the scroll, output $$$-1$$$.

Otherwise, output the number $$$c$$$ — the minimum number of summoned students.

In the next line, output $$$c$$$ numbers — the indices of the students in the order they should be summoned. The students are numbered with integers from $$$1$$$ to $$$k$$$ in the order they are listed in the input. All student indices must be distinct.

If there are multiple optimal answers, output any of them.

Example
Input
2
4 6 3
1 3 2 4
2 1 3 1 2 4
5 6
2 6
1 3
3 4 1
3 1 2
2 1 3 1
1 4
Output
2
3 1
-1