Monocarp 和 Bicarp 正在玩纸牌游戏。每张卡都有两个参数:攻击值和防御值。如果$$$s$$$ 的攻击严格大于$$$t$$$ 的防御,则一张牌$$$s$$$ 会击败另一张牌$$$t$$$。
Monocarp 有 $$$n$$$ 卡,其中第 $$$i$$$ 的攻击值为 $$$\mathit{ax}_i$$$,防御值为 $$$\mathit{ay}_i$$$。 Bicarp 有 $$$m$$$ 卡,其中第 $$$j$$$ 的攻击值为 $$$\mathit{bx}_j$$$,防御值为 $$$\mathit{by}_j$$$。
在第一步中,Monocarp 选择他的一张牌并打出它。比卡普必须用他自己的牌来回应,打败那张牌。之后,Monocarp 必须用一张击败 Bicarp 的牌来回应。之后,轮到比卡普了,依此类推。
一张牌被击败后,它会回到打出它的玩家的手上。这意味着每个玩家始终拥有与游戏开始时相同的牌组。当当前玩家没有牌可以击败对手刚刚打出的牌时,游戏结束,当前玩家输。
如果游戏持续 $$$100^{500}$$$ 步,则宣布平局。
Monocarp 和 Bicarp 都能发挥最佳效果。也就是说,如果一名玩家无论对手如何行动都有获胜策略,那么他就是为了胜利而下棋。否则,如果他有平局策略,他就会为平局而打。
您需要计算三个值:
- Monocarp 获胜的起始动作数量;
- Monocarp 的起始动作导致平局的次数;
- Monocarp 导致 Bicarp 获胜的起始动作数量。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — Monocarp 拥有的卡片数量。
第二行包含 $$$n$$$ 整数 $$$\mathit{ax}_1, \mathit{ax}_2, \dots, \mathit{ax}_n$$$ ($$$1 \le \mathit{ax}_i \le 10^6$$$) — Monocarp 卡牌的攻击值。
第三行包含 $$$n$$$ 整数 $$$\mathit{ay}_1, \mathit{ay}_2, \dots, \mathit{ay}_n$$$ ($$$1 \le \mathit{ay}_i \le 10^6$$$) — Monocarp 卡牌的防御值。
第四行包含一个整数 $$$m$$$ ($$$1 \le m \le 3 \cdot 10^5$$$) — Bicarp 拥有的牌数。
第五行包含 $$$m$$$ 整数 $$$\mathit{bx}_1, \mathit{bx}_2, \dots, \mathit{bx}_m$$$ ($$$1 \le \mathit{bx}_j \le 10^6$$$) — Bicarp 卡牌的攻击值。
第六行包含 $$$m$$$ 整数 $$$\mathit{by}_1, \mathit{by}_2, \dots, \mathit{by}_m$$$ ($$$1 \le \mathit{by}_j \le 10^6$$$) – Bicarp 牌的防御值。
输入的附加约束:所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$,所有测试用例的 $$$m$$$ 总和不超过 $$$3 \cdot 10^5$$$。
输出
对于每个测试用例,打印三个整数:
- Monocarp 获胜的起始动作数量;
- Monocarp 的起始动作导致平局的次数;
- Monocarp 导致 Bicarp 获胜的起始动作数量。
示例
输入 #1
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
输出 #1
1 1 1 2 4 3 0 1 0