题目描述

在最新一届世界杯之后，一些国家正在考虑退出 FIFA，并成立一项新运动：bootfall。在 bootfall 中，两支队伍各有 $N$ 名球员对抗。每名球员可以是后卫或前锋，且在每场比赛前，球队可以决定每名球员的角色。

你执教一支拥有 $N$ 名球员的球队，第 $i$ 名球员的进攻值为 $a_i$，防守值为 $d_i$。球队的进攻强度 $A$ 等于被指定为前锋的球员的所有 $a_i$ 之和，球队的防守强度 $D$ 等于被指定为后卫的球员的所有 $d_i$ 之和。若你的球队面对另一支进攻强度为 $A'$、防守强度为 $D'$ 的队伍，你的球队将打入 $\max(0, A - D')$ 球，而对手将打入 $\max(0, A' - D)$ 球。

你的球队将面对 $Q$ 支其他队伍，其中第 $i$ 支队伍的进攻强度为 $A_i$，防守强度为 $D_i$。你的任务是在每场比赛中决定哪些人防守、哪些人进攻，以获得尽可能好的结果（理想顺序为赢、平，尽量不要输）。

输入格式

第一行包含整数 $N$（$1 \le N \le 400$），表示你队伍的球员数量。

接下来的 $N$ 行中，每行包含两个整数 $a_i$ 和 $d_i$（$0 \le a_i, d_i \le 400$），分别为第 $i$ 名球员的进攻值与防守值。

下一行包含一个整数 $Q$（$1 \le Q \le 3 \cdot 10^5$），表示比赛场数。

随后 $Q$ 行中，每行包含两个整数 $A_i$ 和 $D_i$（$0 \le A_i, D_i \le 160000$），表示你的球队将面对一支进攻强度为 $A_i$、防守强度为 $D_i$ 的队伍。

输出格式

在一行中输出三个整数 $w, d, l$：分别为在每场比赛都最优选择进攻与防守分配时，你将赢、平、输的场次数。

4
2 3
1 1
0 2
5 1
5
5 5
6 5
7 10
10 0
12 0

2 2 1

提示

子任务

本题采用捆绑测试。 | 子任务编号 | 得分 | 限制 | |:-:|:-:|---| | $1$ | $11$ | 对所有 $1 \le i \le Q$，有 $A_i = 0$ | | $2$ | $16$ | $N \le 5,\ Q \le 1000$ | | $3$ | $20$ | 对所有 $1 \le i \le Q$，有 $D_i = 0$ | | $4$ | $24$ | $N, a_i, d_i \le 30,\ Q \le 1000$ | | $5$ | $29$ | 无额外限制。 |