Codeforces Round 731 (Div. 3) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

greedy

two pointers

*1100

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. Pair Programming

time limit per test

2 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputMonocarp and Polycarp are learning new programming techniques. Now they decided to try pair programming.

It's known that they have worked together on the same file for $$$n + m$$$ minutes. Every minute exactly one of them made one change to the file. Before they started, there were already $$$k$$$ lines written in the file.

Every minute exactly one of them does one of two actions: adds a new line to the end of the file or changes one of its lines.

Monocarp worked in total for $$$n$$$ minutes and performed the sequence of actions $$$[a_1, a_2, \dots, a_n]$$$. If $$$a_i = 0$$$, then he adds a new line to the end of the file. If $$$a_i > 0$$$, then he changes the line with the number $$$a_i$$$. Monocarp performed actions strictly in this order: $$$a_1$$$, then $$$a_2$$$, ..., $$$a_n$$$.

Polycarp worked in total for $$$m$$$ minutes and performed the sequence of actions $$$[b_1, b_2, \dots, b_m]$$$. If $$$b_j = 0$$$, then he adds a new line to the end of the file. If $$$b_j > 0$$$, then he changes the line with the number $$$b_j$$$. Polycarp performed actions strictly in this order: $$$b_1$$$, then $$$b_2$$$, ..., $$$b_m$$$.

Restore their common sequence of actions of length $$$n + m$$$ such that all actions would be correct — there should be no changes to lines that do not yet exist. Keep in mind that in the common sequence Monocarp's actions should form the subsequence $$$[a_1, a_2, \dots, a_n]$$$ and Polycarp's — subsequence $$$[b_1, b_2, \dots, b_m]$$$. They can replace each other at the computer any number of times.

Let's look at an example. Suppose $$$k = 3$$$. Monocarp first changed the line with the number $$$2$$$ and then added a new line (thus, $$$n = 2, \: a = [2, 0]$$$). Polycarp first added a new line and then changed the line with the number $$$5$$$ (thus, $$$m = 2, \: b = [0, 5]$$$).

Since the initial length of the file was $$$3$$$, in order for Polycarp to change line number $$$5$$$ two new lines must be added beforehand. Examples of correct sequences of changes, in this case, would be $$$[0, 2, 0, 5]$$$ and $$$[2, 0, 0, 5]$$$. Changes $$$[0, 0, 5, 2]$$$ (wrong order of actions) and $$$[0, 5, 2, 0]$$$ (line $$$5$$$ cannot be edited yet) are not correct.

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 1000$$$). Then $$$t$$$ test cases follow. Before each test case, there is an empty line.

Each test case contains three lines. The first line contains three integers $$$k$$$, $$$n$$$, $$$m$$$ ($$$0 \le k \le 100$$$, $$$1 \le n, m \le 100$$$) — the initial number of lines in file and lengths of Monocarp's and Polycarp's sequences of changes respectively.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 300$$$).

The third line contains $$$m$$$ integers $$$b_1, b_2, \dots, b_m$$$ ($$$0 \le b_j \le 300$$$).

Output

For each test case print any correct common sequence of Monocarp's and Polycarp's actions of length $$$n + m$$$ or -1 if such sequence doesn't exist.

Example

Input

5 3 2 2 2 0 0 5 4 3 2 2 0 5 0 6 0 2 2 1 0 2 3 5 4 4 6 0 8 0 0 7 0 9 5 4 1 8 7 8 0 0

Output

2 0 0 5 0 2 0 6 5 -1 0 6 0 7 0 8 0 9 -1

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/12/2024 03:22:48 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|