题目描述
Agar.io 是一款流行的游戏,每个玩家在二维平面上控制一个球。
我们对游戏进行下列简化:
- 现在有 n(1≤n≤100) 个玩家(包括 ZQC 自己),每个玩家有一个坐标 (x,y) 和活动半径 r(0≤x,y,r≤10000),当前质量 w(1≤w≤10000)。也就是每个玩家在一个圆里活动,包括边界。
形式化地,玩家的活动范围为 S={(a,b)∣(a−x)2+(b−y)2≤r2,a∈R,b∈R}。
- 还有 m(1≤m≤400) 个食物球,每个球有坐标 (xf,yf)(0≤xf,yf≤10000) 和质量 wf(1≤wf≤10000)。
- 每个玩家可以吃到自己活动范围内的食物球(不能吃其它玩家),并且可以只吃一部分,每个玩家吃每个食物球的量必须是非负整数,吃掉的部分会加在自身质量上。
形式化地,用一个 n×m 的矩阵 A 来表示吃的情况,其中 Aij 表示玩家 i 吃食物 j 的量,则:
- ∀i,j 有 Aij∈N
- ∀i,最终的质量 wni=wi+∑j=1mAij
- ∀j 有 ∑i=1nAij≤wfj
- 由于 ZQC 非常神,她可以钦点所有玩家的行动。
- ZQC 会将它活动范围内的所有食物球吃光。
- 对于每个食物球,如果它在至少一个玩家的活动范围内,则它一定要被吃光。形式化地,设这个食物球编号为 j,则有 ∑i=1nAij=wfj
问有没有一种钦点方案使得没有其它玩家的质量比 ZQC 的更大(∀i,wni≤wn1)?
一句话题意:问是否存在一种分配方案使得所有能被吃到的食物球都被吃光,并且满足 ZQC 是最♂大的玩家(之一)。
输入格式
第一行一个正整数 T(1≤T≤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