3958: 「LibreOJ β Round」ZQC 的游戏

*Agar.io* 是一款流行的游戏，每个玩家在二维平面上控制一个球。 我们对游戏进行下列简化： * 现在有 $ n(1 \leq n \leq 100) $ 个玩家（包括 ZQC 自己），每个玩家有一个坐标 $ (x,y) $ 和活动半径 $ r(0 \leq x, y, r \leq 10000) $，当前质量 $ w(1 \leq w \leq 10000) $。也就是每个玩家在一个圆里活动，**包括边界**。 形式化地，玩家的活动范围为 $S=\{(a,b)|(a-x)^2+(b-y)^2\leq r^2,a\in \mathbb{R},b\in \mathbb{R}\}$。 * 还有 $ m(1 \leq m \leq 400) $ 个食物球，每个球有坐标 $ (x_f, y_f)(0 \leq x_f, y_f \leq 10000) $ 和质量 $ w_f(1 \leq w_f \leq 10000) $。 * 每个玩家可以吃到自己活动范围内的食物球（不能吃其它玩家），并且**可以只吃一部分**，每个玩家吃每个食物球的量必须是**非负整数**，吃掉的部分会加在自身质量上。 形式化地，用一个 $n\times m$ 的矩阵 $A$ 来表示吃的情况，其中 $A_{ij}$ 表示玩家 $i$ 吃食物 $j$ 的量，则： * $\forall i,j$ 有 $A_{ij}\in \mathbb{N}$ * $\forall i$，最终的质量 $w_{\text{n}i}=w_i+\sum_{j=1}^m A_{ij}$ * $\forall j$ 有 $\sum_{i=1}^n A_{ij}\leq {w_f}_j$ * 由于 ZQC 非常神，她可以钦点所有玩家的行动。 * ZQC 会将它活动范围内的所有食物球吃光。 * 对于每个食物球，如果它在至少一个玩家的活动范围内，则它一定要被吃光。形式化地，设这个食物球编号为 $j$，则有 $\sum_{i=1}^n A_{ij}= {w_f}_j$ 问有没有一种钦点方案使得**没有其它玩家的质量比 ZQC 的更大**（$\forall i,w_{\text{n}i}\leq w_{\text{n}1}$）？ --- **一句话题意**：问是否存在一种分配方案使得所有能被吃到的食物球都被吃光，并且满足 ZQC 是最**♂**大的玩家（之一）。

第一行一个正整数 $T (1\le T \le 100) $，表示测试数据的组数。 对于每组测试数据，第一行两个正整数 $ n, m $。 接下来 $ n $ 行，每行四个整数 $ x, y, w, r $，其中第一个玩家是 ZQC。 接下来 $ m $ 行，每行三个整数 $ x, y, w $。

如果方案存在，输出一行 `ZQC! ZQC!`，否则输出一行 `qaq`。

2
3 2
0 0 1 10
10 0 1 10
20 0 1 10
5 0 2
15 0 4
3 2
0 0 1 10
10 0 1 10
20 0 1 10
5 0 2
15 0 5

ZQC! ZQC!
qaq