310829: CF1895E. Infinite Card Game

E. Infinite Card Gametime limit per test3 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

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

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

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.

ExampleInput

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

Output

1 1 1
2 4 3
0 1 0

题目大意：
单卡车和双卡车正在玩一个纸牌游戏。每张牌有两个参数：攻击值和防御值。如果一张牌s的攻击值严格大于另一张牌t的防御值，则牌s击败牌t。

单卡车有n张牌，第i张牌的攻击值为\( \mathit{ax}_i \)，防御值为\( \mathit{ay}_i \)。双卡车有m张牌，第j张牌的攻击值为\( \mathit{bx}_j \)，防御值为\( \mathit{by}_j \)。

在第一轮，单卡车选择一张他的牌并打出。双卡车必须用他的能击败那张牌的牌回应。之后，单卡车必须用能击败双卡车牌的牌回应。之后，轮到双卡车，如此往复。

一张牌被击败后，它会返回到打出它的玩家的手中。这意味着每个玩家始终拥有与游戏开始时相同的牌组。当当前玩家没有能击败对手刚打出的牌的牌时，游戏结束，当前玩家输掉游戏。

如果游戏进行了\( 100^{500} \)轮，则宣布平局。

单卡车和双卡车都进行最优游戏。也就是说，如果一名玩家无论对手如何行动都能获胜，他会争取胜利。否则，如果他有一个平局策略，他会争取平局。

你需要计算以下三个值：
- 单卡车起始行动导致单卡车获胜的数量；
- 单卡车起始行动导致平局的数量；
- 单卡车起始行动导致双卡车获胜的数量。

输入数据格式：
第一行包含一个整数\( t \)（\( 1 \le t \le 10^4 \)）——测试用例的数量。

每个测试用例的第一行包含一个整数\( n \)（\( 1 \le n \le 3 \cdot 10^5 \)）——单卡车拥有的牌数。

第二行包含\( n \)个整数\( \mathit{ax}_1, \mathit{ax}_2, \dots, \mathit{ax}_n \)（\( 1 \le \mathit{ax}_i \le 10^6 \)）——单卡车的牌的攻击值。

第三行包含\( n \)个整数\( \mathit{ay}_1, \mathit{ay}_2, \dots, \mathit{ay}_n \)（\( 1 \le \mathit{ay}_i \le 10^6 \)）——单卡车的牌的防御值。

第四行包含一个整数\( m \)（\( 1 \le m \le 3 \cdot 10^5 \)）——双卡车拥有的牌数。

第五行包含\( m \)个整数\( \mathit{bx}_1, \mathit{bx}_2, \dots, \mathit{bx}_m \)（\( 1 \le \mathit{bx}_j \le 10^6 \)）——双卡车的牌的攻击值。

第六行包含\( m \)个整数\( \mathit{by}_1, \mathit{by}_2, \dots, \mathit{by}_m \)（\( 1 \le \mathit{by}_j \le 10^6 \)）——双卡车的牌的防御值。

输入数据的附加限制：所有测试用例的\( n \)之和不超过\( 3 \cdot 10^5 \)，所有测试用例的\( m \)之和不超过\( 3 \cdot 10^5 \)。

输出数据格式：
对于每个测试用例，打印三个整数：
- 单卡车起始行动导致单卡车获胜的数量；
- 单卡车起始行动导致平局的数量；
- 单卡车起始行动导致双卡车获胜的数量。题目大意： 单卡车和双卡车正在玩一个纸牌游戏。每张牌有两个参数：攻击值和防御值。如果一张牌s的攻击值严格大于另一张牌t的防御值，则牌s击败牌t。 单卡车有n张牌，第i张牌的攻击值为\( \mathit{ax}_i \)，防御值为\( \mathit{ay}_i \)。双卡车有m张牌，第j张牌的攻击值为\( \mathit{bx}_j \)，防御值为\( \mathit{by}_j \)。 在第一轮，单卡车选择一张他的牌并打出。双卡车必须用他的能击败那张牌的牌回应。之后，单卡车必须用能击败双卡车牌的牌回应。之后，轮到双卡车，如此往复。 一张牌被击败后，它会返回到打出它的玩家的手中。这意味着每个玩家始终拥有与游戏开始时相同的牌组。当当前玩家没有能击败对手刚打出的牌的牌时，游戏结束，当前玩家输掉游戏。 如果游戏进行了\( 100^{500} \)轮，则宣布平局。 单卡车和双卡车都进行最优游戏。也就是说，如果一名玩家无论对手如何行动都能获胜，他会争取胜利。否则，如果他有一个平局策略，他会争取平局。 你需要计算以下三个值： - 单卡车起始行动导致单卡车获胜的数量； - 单卡车起始行动导致平局的数量； - 单卡车起始行动导致双卡车获胜的数量。 输入数据格式： 第一行包含一个整数\( t \)（\( 1 \le t \le 10^4 \)）——测试用例的数量。 每个测试用例的第一行包含一个整数\( n \)（\( 1 \le n \le 3 \cdot 10^5 \)）——单卡车拥有的牌数。 第二行包含\( n \)个整数\( \mathit{ax}_1, \mathit{ax}_2, \dots, \mathit{ax}_n \)（\( 1 \le \mathit{ax}_i \le 10^6 \)）——单卡车的牌的攻击值。 第三行包含\( n \)个整数\( \mathit{ay}_1, \mathit{ay}_2, \dots, \mathit{ay}_n \)（\( 1 \le \mathit{ay}_i \le 10^6 \)）——单卡车的牌的防御值。 第四行包含一个整数\( m \)（\( 1 \le m \le 3 \cdot 10^5 \)）——双卡车拥有的牌数。 第五行包含\( m \)个整数\( \mathit{bx}_1, \mathit{bx}_2, \dots, \mathit{bx}_m \)（\( 1 \le \mathit{bx}_j \le 10^6 \)）——双卡车的牌的攻击值。 第六行包含\( m \)个整数\( \mathit{by}_1, \mathit{by}_2, \dots, \mathit{by}_m \)（\( 1 \le \mathit{by}_j \le 10^6 \)）——双卡车的牌的防御值。 输入数据的附加限制：所有测试用例的\( n \)之和不超过\( 3 \cdot 10^5 \)，所有测试用例的\( m \)之和不超过\( 3 \cdot 10^5 \)。 输出数据格式： 对于每个测试用例，打印三个整数： - 单卡车起始行动导致单卡车获胜的数量； - 单卡车起始行动导致平局的数量； - 单卡车起始行动导致双卡车获胜的数量。