## Educational Codeforces Round 129 – Problem A

Alice and Bob play a game. Alice has n cards, the i-th of them has the integer ai written on it. Bob has m cards, the j-th of them has the integer bj 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 4 cards with numbers [10,5,3,8], and Bob has 3 cards with numbers [6,11,6], the game may go as follows:

- Alice can choose any of her cards. She chooses the card with integer 5 and plays it.
- Bob can choose any of his cards with number greater than 5. He chooses a card with integer 6 and plays it.
- Alice can choose any of her cards with number greater than 6. She chooses the card with integer 10 and plays it.
- Bob can choose any of his cards with number greater than 10. He chooses a card with integer 11 and plays it.
- Alice can choose any of her cards with number greater than 11, 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 t (1≤t≤1000) — the number of test cases. Each test case consists of four lines.

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

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

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

The fourth line contains m integers b1,b2,…,bm (1≤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

```
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
```

## Example output

```
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 6, Bob has two cards with numbers [6,8].

If Alice is the first player, she has to play the card with number 6. Bob then has to play the card with number 8. 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

If Alice plays first and she has a higher (or equal) max number than Bob, she can throw that card and win. Same applies for Bob.

#include <iostream> #include <vector> #include <algorithm> using namespace std; int main(){ int t; cin >> t; while (t--) { int n,m; cin >> n; vector<int> a(n); for (int i=0;i<n;i++) cin >> a[i]; sort(a.begin(), a.end()); cin >> m; vector<int> b(m); for (int i=0;i<m;i++) cin >> b[i]; sort(b.begin(), b.end()); int ma = a[n-1]; int mb = b[m-1]; if (ma >= mb) cout << "Alice" << endl; else cout << "Bob" << endl; if (mb >= ma) cout << "Bob" << endl; else cout << "Alice" << endl; } return 0; }