B国在耗资百亿元之后终于研制出了新式武器——连环阵(Zenith Protected Linked Hybrid Zone),并声称这是一种无敌的自发性智能武器。但A国经侦察发现,连环阵其实是由M个独立武器组成的。这M个武器编号为1,2,…,M。每件武器有两种状态:无敌自卫状态和攻击状态。最初,1号武器处于攻击状态,其他武器都处在无敌自卫状态。以后,一旦第i(1 <= i<M)号武器被消灭,1秒钟以后第i+1号武器就自动从无敌自卫状态变成攻击状态。当第M号武器被消灭以后,这个造价昂贵的连环阵就被彻底摧毁了。
为了打败B国,A国军事部长打算用最廉价的武器——炸弹来消灭连环阵。经过长时间的精密探测,A国的军事家们掌握了连环阵中M个武器的平面坐标,然后依此选择了n个点,并在这些点上安放了特殊的定时炸弹。这n个炸弹编号为1,2,…,n。每个炸弹的作用半径均为k,且会持续爆炸5分钟。在这5分钟内,每枚炸弹都可以在瞬间消灭离它直线距离不超过k的、处在攻击状态的B国武器。和连环阵类似,最初a1号炸弹持续引爆5分钟时间,然后a2号炸弹持续引爆5分钟时间,接着a3号炸弹引爆……以此类推,直到连环阵被摧毁。在每个炸弹爆炸的时候,其它尚未引爆的炸弹都处于地下隐蔽处,不会被己方的炸弹摧毁。
显然,选好a1、a2、a3...十分重要。好的序列可以在仅使用较少炸弹的情况下就能将连环阵摧毁;坏的序列可能在使用完所有炸弹后仍无法将连环阵摧毁。现在,请你决定一个序列a1、a2、a3…使得在第ax号炸弹引爆的时间内连环阵被摧毁。这里的x应当尽量小。
第一行包含三个整数:M、n和k(1≤M, n≤100,1≤ k≤ 1000),分别表示B国连环阵由M个武器组成,A国有n个炸弹可以使用,炸弹攻击范围为k。以下M行,每行由一对整数xi,yi(0≤ xi,yi ≤ 10000)组成,表示第i(1≤ i≤ M)号武器的平面坐标。再接下来n行,每行由一对整数ui,vi(0 ≤ ui,vi≤ 10000)组成,表示第i(1≤ i≤ n)号炸弹的平面坐标。输入数据保证无误和有解。
测试数据中的xi、yi、ui、vi是随机生成的。
第一行包含一个整数x,表示实际使用的炸弹数。第二行包括x个整数,依次表示a1,a2,…,ax。