G. Generic Spy Movies
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

While fooling around at work today your boss, the head producer at Accelerated Creator of Movies (ACM), gives you a large list:

James Bold: Fingers

Missionary Possible: Callout

John Licks 3: Caramellum

Tom Clancy's Jack of Ryan

Fasting and Furious: Hobos with Shows

... (many more movies)

Your boss then tells you: "Slick, high-octane, spy thriller movie franchises are popular nowadays! Make $$$n$$$ movies like that!" and immediately leaves. With your jobs on the line, your hardworking team of writer-producers create the generic genre perfect spy movie scenario for you:

  • Since more movies = more money, you plan to create $$$n$$$ movies.
  • What's a spy film without a spy team? A cast of $$$g$$$ people seems to be the sweet spot: no more, no less.
  • To keep things interesting, one of the members needs to go into hiding/leave/die at the end of each movie. Preferably with a teary goodbye and matching melodramatic soundtrack.
  • To keep the cast the same number ($$$g$$$ members), someone must join the team at the start of every sequel. People love new faces. Maybe they're secretly someone who left a few movies before for a nice twist.
  • People will think you're redoing the plot of a previous movie if you got the exact same cast as before. The casting for each movie should not repeat across the entire franchise.

Seems good, right? You have just called all the agents your connections could afford, and not only they give you a list of $$$a$$$ actors to cast, but also that they have already booked the actors for the first episode! The only thing left is to decide the casting for the $$$n-1$$$ movie episodes left - but you remember that you can only change 1 slot in the cast after every movie ($$$1$$$ leaving the slot, $$$1$$$ arriving at that slot the next).

Given a list of actors $$$a$$$ and the initial lineup of $$$g$$$ cast members, list the cast changes needed to reach $$$n$$$ movies.

Input

The first line of input contains $$$t$$$, the number of testcases.

Each test case consists of three lines:

  1. The irst line contains three space-separated positive integers: $$$g$$$ (number of guests per episode), $$$n$$$ (the number of movies to produce), and $$$a$$$ (number of actors available for casting).
  2. Second line contains $$$a$$$ space-separated lowercase strings, the $$$i$$$th of which $$$a_i$$$ denotes the name of the $$$i$$$th castable actor.
  3. The third line contains $$$g$$$ space-separated lowercase strings, containing the names of the actors casted for the first episode.

Constraints

  • $$$1 \le t \le 50$$$
  • $$$1 \le g \le a$$$
  • $$$2 \le a \le 10^3$$$
  • $$$2 \le n \le 10^4$$$
  • Each $$$a_i$$$ has a length of at least $$$1$$$ and at most $$$4$$$.
  • You can always complete the casting for all $$$n$$$ episodes, i.e., a solution always exists.
Output

For each test case, output $$$n - 1$$$ lines, each containing two space-separated lowercase strings $$$a_\text{out}$$$ (actor being replaced) and $$$a_\text{in}$$$ (actor coming in).

Output a single blank line before the output of every test case except the first one.

There may be multiple valid answers; any one will be accepted.

Example
Input
2
2 4 4
ali bob carl dude
ali bob
2 4 5
ali bob carl dude earl
carl dude
Output
bob carl
carl dude
ali bob

dude earl
carl dude
dude ali
Note

Cast list for the first test case (bold text means a cast change occured):

  1. ali bob (first episode, no changes yet)
  2. ali carl (bob $$$\rightarrow$$$ carl)
  3. ali dude (carl $$$\rightarrow$$$ dude)
  4. bob dude (ali $$$\rightarrow$$$ bob)