Infinite Card Game
Contest: Educational Codeforces Round 157 (Rated for Div. 2)
Difficulty rating: 2300
Tags: binary search, brute force, data structures, dfs and similar, dp, dsu, games, graphs, greedy, sortings, two pointers

Monocarp and Bicarp are playing a card game. Each card has two parameters: an attack value and a defence value. A card $$$s$$$ beats another card $$$t$$$ if the attack of $$$s$$$ is strictly greater than the defence of $$$t$$$.

Monocarp has $$$n$$$ cards, the $$$i$$$-th of them has an attack value of $$$\mathit{ax}_i$$$ and a defence value of $$$\mathit{ay}_i$$$. Bicarp has $$$m$$$ cards, the $$$j$$$-th of them has an attack value of $$$\mathit{bx}_j$$$ and a defence value of $$$\mathit{by}_j$$$.

On the first move, Monocarp chooses one of his cards and plays it. Bicarp has to respond with his own card that beats that card. After that, Monocarp has to respond with a card that beats Bicarp's card. After that, it's Bicarp's turn, and so forth.

After a card is beaten, it returns to the hand of the player who played it. It implies that each player always has the same set of cards to play as at the start of the game. The game ends when the current player has no cards that beat the card which their opponent just played, and the current player loses.

If the game lasts for $$$100^{500}$$$ moves, it's declared a draw.

Both Monocarp and Bicarp play optimally. That is, if a player has a winning strategy regardless of his opponent's moves, he plays for a win. Otherwise, if he has a drawing strategy, he plays for a draw.

You are asked to calculate three values:

- the number of Monocarp's starting moves that result in a win for Monocarp;
- the number of Monocarp's starting moves that result in a draw;
- the number of Monocarp's starting moves that result in a win for Bicarp.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — the number of cards Monocarp has.

The second line contains $$$n$$$ integers $$$\mathit{ax}_1, \mathit{ax}_2, \dots, \mathit{ax}_n$$$ ($$$1 \le \mathit{ax}_i \le 10^6$$$) — the attack values of Monocarp's cards.

The third line contains $$$n$$$ integers $$$\mathit{ay}_1, \mathit{ay}_2, \dots, \mathit{ay}_n$$$ ($$$1 \le \mathit{ay}_i \le 10^6$$$) — the defence values of Monocarp's cards.

The fourth line contains a single integer $$$m$$$ ($$$1 \le m \le 3 \cdot 10^5$$$) — the number of cards Bicarp has.

The fifth line contains $$$m$$$ integers $$$\mathit{bx}_1, \mathit{bx}_2, \dots, \mathit{bx}_m$$$ ($$$1 \le \mathit{bx}_j \le 10^6$$$) — the attack values of Bicarp's cards.

The sixth line contains $$$m$$$ integers $$$\mathit{by}_1, \mathit{by}_2, \dots, \mathit{by}_m$$$ ($$$1 \le \mathit{by}_j \le 10^6$$$) — the defence values of Bicarp's cards.

Additional constraints on the input: the sum of $$$n$$$ over all test cases doesn't exceed $$$3 \cdot 10^5$$$, the sum of $$$m$$$ over all test cases doesn't exceed $$$3 \cdot 10^5$$$.

Output format:
For each test case, print three integers:

- the number of Monocarp's starting moves that result in a win for Monocarp;
- the number of Monocarp's starting moves that result in a draw;
- the number of Monocarp's starting moves that result in a win for Bicarp.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Example input:
3
3
8 7 4
7 1 10
2
8 4
5 10
9
8 8 5 5 5 4 4 1 4
2 7 5 2 8 9 7 1 9
10
9 8 7 6 5 5 4 3 2 1
7 1 6 7 5 8 8 4 9 6
1
10
5
1
10
5

Example output:
1 1 1
2 4 3
0 1 0

Editorial:
Let's restate the game in game theory terms. The state of the game can be just the card that is currently on top, since none of the previously played cards matter. A move is still a card beating another card, so these are the edges of the game graph.
Now we can solve this as a general game. Mark all trivial winning and losing states and determine the outcome for all other states with a DFS/BFS on a transposed game graph.
Unfortunately, there are $$$O(n^2)$$$ edges in the graph, so we can't quite do it as is. There are multiple ways to optimize that, I'll describe the smartest one, in my opinion.
Notice that, after a card beats another card, its attack doesn't matter at all. It's only health that's relevant. And the larger the health is, the fewer responses the opponent has. In particular, we use the fact that the sets of the responses can either coincide or be included one into another.
So, there is always the best response for each card (or multiple equally good ones). That is just the card with the largest health among the ones that beat the current one. To find this card, you can sort them by their attack value and find a prefix/suffix health maximum.
This massively reduces the number of edges. Now, each state has at most one outgoing edge. Zero edges mean that the card is winning, since there is no card to beat it. For these states, we can tell the winner. The rest of the states either reach these marked ones, thus, can be deduced, or form a closed loop among each other, making the outcome a draw (since there is always a response for each move).
Overall complexity: $$$O(n \log n)$$$ per testcase.