Infinite War?

The two-player card game War has very simple rules. Our version of the game is played with \(n\) cards that have the numbers from \(1\) to \(n\) on them. The cards are split into two decks, with each player holding one of the decks. The game is played in turns. In each turn both players simultaneously reveal the top card of their deck. The player who revealed the bigger card wins the turn. The winner takes both revealed cards and places them on the bottom of their deck. The game ends when one player holds all the cards.

It should be obvious that when it comes to winning and losing, our version of War is basically a glorified screensaver: as all cards are distinct (which eliminates ties), the players have no way of influencing who eventually wins the game.

Danka is currently visiting her granny. Granny loves playing War. Danka… not so much. But that’s not something you can freely admit, and so every afternoon the two play a game of War. More precisely, granny is sipping her tea while Danka has to manipulate both decks: reveal granny’s card and her own card, and then add both to the bottom of the deck belonging to the winner of that turn. The game always takes ages, and by the end of it Danka is already bored out of her mind.

However, one day she had a revelation. While she cannot influence who eventually wins, she can influence how long the game will take. How? Remember that at the end of each turn the turn’s winner places the two cards at the bottom of their deck. Here the winner actually has some agency because they get to choose one of two options:

option 0: add the smaller card first (so the bigger of the two ends on the bottom of the new deck)
option 1: add the bigger card first

Task

You will be given multiple scenarios, each corresponding to the start of one game. In each scenario you will be given two lists of cards: one for granny’s initial deck, the other for Danka’s initial deck.

In each scenario your task is to help Danka end the game as quickly as you can. More precisely, for each scenario you should provide a strategy: a sequence \(a_1,\dots,a_k\) of zeros and ones such that if Danka chooses option \(a_i\) in turn \(i\), the game will end at the end of turn \(k\).

Your score for this problem will depend on the quality of the solutions you find.

Input format

There is a single input file. Its first line contains the number \(t\) of test cases. The specified number of test cases follows, one after another. Each test case consists of three lines:

The first line has the numbers \(g\) and \(d\): the number of cards in granny’s deck and the number of cards in Danka’s deck.
The second line has \(g\) numbers: the numbers on cards in granny’s deck, from top to bottom.
The third line has \(d\) numbers: Danka’s deck in the same format.

The value \(n\) is given implicitly as \(n = g+d\). It is guaranteed that each of the values from \(1\) to \(n\) appears exactly once in both decks combined.

All test cases in the scored input file will have the same \(n\).

Output format

For each test case output a single line with two numbers: the number \(k\) of turns your game will take, and a large base-16 integer whose base-2 digits (from the most to the least significant one) are \(a_1,\dots,a_k\). The output is not case-sensitive.

Note that in this round your output file size must not exceed 5 MB (i.e., \(5\times 2^{20}\) bytes). If your games take too long, your full output file will be bigger. If that happens to you, you can submit just the solutions to the first \(t' < t\) test cases for the biggest \(t'\) that still fits into the limit. Such output files will still get a partial score if they are correct.

Special rule

Resubmissions for this problem do not generate penalty minutes.

Subproblem I1 (100 points, private)

Input file: I1.in

Constraints: \(t=1000\) and each test case has \(n=1000\).

Your score is determined as follows:

If your output is empty, malformed, or for any test case your sequence of bits doesn’t win the game in exactly the declared number of turns, your score for the whole submission is of course zero.

Otherwise, your score is determined as follows:

Let \(x\) be the largest value \(k\) in your answers.
If \(t' < t\) (your output solves only a prefix of the given test cases), \(x := \max(x, 25\,000\,000/t' )\).
Your score is determined from \(x\) using the formula below and then rounded to two decimal places.

\[\text{score} \;=\; 100 \,\cdot\, \min\left(1,\ \max\left(0,\ \frac{\ln (X_0/x)}{\ln (X_0/X_1)}\right)\right), \quad X_0 = 175\,000,\quad X_1 = 7\,500 .\]

The formula is such that smaller \(x\) is better. Sample scores:

\(x\)	7 500	10 000	15 000	21 000	30 000	50 000	100 000	175 000
score	100.00	90.87	77.99	67.31	55.99	39.77	17.77	0.00

Examples

input

3
2 2
3 1
4 2
4 2
1 4 6 3
5 2
6 6
4 12 1 3 7 10
8 11 6 2 9 5

output

2 0
4 8
22 30f3e5

In game 1 granny starts with the deck \((3, 1)\) and Danka with \((4, 2)\). Both are given from top to bottom.

In the first round of the game granny reveals 3, Danka reveals 4, and thus Danka wins. In the second round of the game granny reveals 1, Danka reveals 2, and thus Danka wins again. Regardless of the choices Danka made in each turn, she now holds all four cards and the game ends.

In the example output we chose \(a_1=0\) and \(a_2=0\). For these choices Danka’s final deck is \((3, 4, 1, 2)\).

For game 2, the example output claims to end the game in 4 turns, with Danka’s choices being \(a=(1,0,0,0)\). Here’s the corresponding game:

turn	granny	Danka	winner	option	decks after
1	1	5	Danka	1	granny \(4,6,3\); Danka \(2,5,1\)
2	4	2	granny	0	granny \(6,3,2,4\); Danka \(5,1\)
3	6	5	granny	0	granny \(3,2,4,5,6\); Danka \(1\)
4	3	1	granny	0	granny \(2,4,5,6,1,3\); Danka —

If Danka instead chooses option 0 each time, the game would take 16 turns instead of 4.

The example answer shown for game 3 is correct but not optimal. The answer “22 30f3e5” encodes the following sequence of options: 11 0000 1111 0011 1110 0101.