Problem1244--LOJ505 -「LibreOJ β Round」ZQC 的游戏

1244: LOJ505 -「LibreOJ β Round」ZQC 的游戏

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

Description

Agar.io 是一款流行的游戏,每个玩家在二维平面上控制一个球。
我们对游戏进行下列简化:
  • 现在有 $n\ (1 \leq n \leq 100)$ 个玩家(包括 ZQC 自己),每个玩家有一个坐标 $(x,\ y)$ 和活动半径 $r\ (0 \leq x,\ y,\ r \leq 10,000)$,当前质量 $w(1 \leq w \leq 10,000)$。也就是每个玩家在一个圆里活动,包括边界。
    形式化地,玩家的活动范围为 $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 10,000)$ 和质量 $w_f\ (1 \leq w_f \leq 10,000)$。
  • 每个玩家可以吃到自己活动范围内的食物球(不能吃其它玩家),并且可以只吃一部分,每个玩家吃每个食物球的量必须是非负整数,吃掉的部分会加在自身质量上。
    形式化地,用一个 $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$
    • $\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 是最♂大的玩家(之一)。

Input

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

Output

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

Sample 1 Input

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

Sample 1 Output

ZQC! ZQC!
qaq

HINT

LOJ505.

Source/Category