Game with Cards solution codeforces

Game with Cards solution codeforces

Alice and Bob play a game. Alice has nn cards, the ii-th of them has the integer aiai written on it. Bob has mm cards, the jj-th of them has the integer bjbj written on it.

On the first turn of the game, the first player chooses one of his/her cards and puts it on the table (plays it). On the second turn, the second player chooses one of his/her cards such that the integer on it is greater than the integer on the card played on the first turn, and plays it. On the third turn, the first player chooses one of his/her cards such that the integer on it is greater than the integer on the card played on the second turn, and plays it, and so on — the players take turns, and each player has to choose one of his/her cards with greater integer than the card played by the other player on the last turn.

If some player cannot make a turn, he/she loses.

For example, if Alice has 44 cards with numbers [10,5,3,8][10,5,3,8], and Bob has 33 cards with numbers [6,11,6][6,11,6], the game may go as follows:

  • Alice can choose any of her cards. She chooses the card with integer 55 and plays it.
  • Bob can choose any of his cards with number greater than 55. He chooses a card with integer 66 and plays it.
  • Alice can choose any of her cards with number greater than 66. She chooses the card with integer 1010 and plays it.
  • Bob can choose any of his cards with number greater than 1010. He chooses a card with integer 1111 and plays it.
  • Alice can choose any of her cards with number greater than 1111, but she has no such cards, so she loses.

Both Alice and Bob play optimally (if a player is able to win the game no matter how the other player plays, the former player will definitely win the game).

You have to answer two questions:

  • who wins if Alice is the first player?
  • who wins if Bob is the first player?
Input

The first line contains one integer tt (1t10001≤t≤1000) — the number of test cases. Each test case consists of four lines.

The first line of a test case contains one integer nn (1n501≤n≤50) — the number of cards Alice has.

The second line contains nn integers a1,a2,,ana1,a2,…,an (1ai501≤ai≤50) — the numbers written on the cards that Alice has.

The third line contains one integer mm (1m501≤m≤50) — the number of Bob’s cards.

The fourth line contains mm integers b1,b2,,bmb1,b2,…,bm (1bi501≤bi≤50) — the numbers on Bob’s cards.

Output

For each test case, print two lines. The first line should be Alice if Alice wins when she is the first player; otherwise, the first line should be Bob. The second line should contain the name of the winner if Bob is the first player, in the same format.

Example
input

Copy
4
1
6
2
6 8
4
1 3 3 7
2
4 2
1
50
2
25 50
10
1 2 3 4 5 6 7 8 9 10
2
5 15
output

Copy
Bob
Bob
Alice
Alice
Alice
Bob
Bob
Bob
Note

Let’s consider the first test case of the example.

Alice has one card with integer 66, Bob has two cards with numbers [6,8][6,8].

If Alice is the first player, she has to play the card with number 66. Bob then has to play the card with number 88. Alice has no cards left, so she loses.

If Bob is the first player, then no matter which of his cards he chooses on the first turn, Alice won’t be able to play her card on the second turn, so she will lose.

SOLUTION

Click here

Leave a Comment

Your email address will not be published.