#P18102. Fresh Cartridges
Fresh Cartridges
Fresh Cartridges
机器人位于一个 维循环竞技场中,每一维坐标都是模 的剩余类。
每盒弹药中装有一个指令:由 个模 的数构成的位移向量。使用一次弹药,就会使机器人按该向量移动,所有坐标均对 取模。
一个遥控器恰好能装入 盒弹药。如果只使用装入的弹药,且每盒可以使用任意多次,机器人就能从任意位置到达任意其他位置,我们称这个遥控器是通用的。
仓库中共有 盒弹药,第 盒的位移向量为 。
接下来有 份相互独立的检查报告。第 份报告中,只有下标位于 的弹药没有过期,可以免费取用;仓库中的其他弹药都已经过期,禁止使用。
对于每份报告,你还可以制造任意多盒新弹药。每盒花费1枚硬币,位移向量可以任意选择,也允许与已有向量相同。新制造的弹药不会保留到其他报告中。
对于每份报告,求组装两个通用遥控器最少需要花费多少枚硬币。**每盒弹药只能使用一次,并且只能装入其中一个遥控器。**不同的弹药即使向量相同,仍然是不同的盒子。
输入格式
第一行一个整数 (),表示测试组数。
每组数据第一行包含三个整数 ,满足
接下来 行,每行 个整数 ,表示第 盒弹药的位移向量,满足 。
接下来 行,每行两个整数 ,满足 。
保证所有测试组的 ,且 。
输出格式
按输入报告的顺序,对每份报告输出一行一个整数,表示最少花费。
样例 1
1
1 3 4
0
1
2
1 1
2 2
3 3
1 3
2
1
1
0
在一维情形下,一个非零向量就能组成一台通用遥控器。零向量没有作用;若只有一盒非零弹药,还需为另一台制造一盒。
样例 2
1
2 4 3
1 0
0 1
0 1
0 1
1 2
1 3
1 4
2
1
1
即使取到全部四盒,也只有一盒提供第一坐标方向,所以仍需至少制造一盒;不能把这盒已有弹药同时装进两台遥控器。