#描述#
水果忍者（Fruit Ninja）是iPhone和Andriod上的一个刺激好玩、容易上手却教人难以离手的动作游戏，玩家将会在游戏中扮演一个讨厌水果的忍者，用锋利的刀切开各种水果。只需将将手指扫过屏幕，就能像忍者战士般痛快地切开溅出美味果汁的水果。游戏玩法简单，你的手指就是忍者手中的刀，把空中的水果切到越多越好，分数也就越高。<br />
MatRush已经玩过在iTouch、Andriod、iPad以及PC上的各个版本的水果忍者，他发现对于这个游戏来说，是有如下的积分规则的：<br />
<p>规则①：每类水果都有他的价值，当你切到这个水果后，得分将按照总价值结合规则②来给定。<br /></p>
<p>规则②：在没有Combo的情况下（即每次一刀只切中1-2个水果）,每个水果就按对应价值给分，在有Combo的情况下（同时切中3个及以上数量的水果），无论Combo的数量是多少，都将按切中的水果价值的2倍来计分。<br /></p>
现在MatRush很阴险地使用了一个技巧，那就是在水果出现后按先截图然后暂停键，再把截图粘贴到画图中。通过这个技巧，MatRush对于同一个截图已经想好了许多不同的切法策略（1次1刀），他想问你的是，对于他的每个策略，能得到的分数是多少呢？<br />
<br />
<p align=center><img src="http://bbs.zjut.com/attachments/forumid_369/1108041122f2008fdd8638e26a.png"></p>
如图：在本题中我们将截图看成二维平面，每个水果看成一个圆心、半径都给定的近似圆，同时给出每个水果的类型以及每种类型的水果的价值。MatRush切的一刀可以认为是一条线段，他将告诉你线段的两个端点Ai和Bi，你可以认为MatRush是从Ai将手指移到Bi的。当且仅当需要横跨整个水果才算切中，切到水果的一半也不算切中。当然，对于擦边而过（与手指轨迹相切）的水果，MatRush是切不到的。所以在上图中，MatRush一共切到了3个水果，很Happy的得到了2倍分数。

#格式#
##输入格式##
输入有多组数据，每组数据的第一行包含两个整数N、M、Q，表示截图上目前有N(1&lt=N&lt=1000)个水果并且它们分别属于M(1&lt=M&lt=1000)种水果种类之一，MatRush想出了Q(1&lt=Q&lt=1000)种切的策略。第二行包含M个整数，表示第0种到第M-1种水果的价值Vi(1&lt=Vi&lt=100000)，第三行到接下来N行，每行包含4个整数xi，yi，ri，ti，xi和yi(-10000&lt=xi,yi&lt=10000)表示第i个水果的圆心坐标，ri(0&lt=ri&lt=1000)表示水果的近似圆的半径，ti(0&lt=ti&ltM)表示该水果所属的种类。注意：水果在游戏中是3D的，考虑成二维后有可能会重叠，即近似圆之间可能会相交。再紧接着Q行，每行包含4个整数Axi, Ayi, Bxi, Byi，范围都是[-10000,10000]，表示MatRush的Q种策略，即从Ai点切到Bi点，保证Ai点和Bi点不会恰好在某个圆内或者圆的边上。

##输出格式##
对于每组数据，输出有Q+1行，首先一行是 "Case #k:"，其中k表示当前数据组数，从1开始。接下来Q行表示MatRush采用的Q种策略所能得到的不同的分数。

#样例1#
##样例输入1##

4 2 1
500 1000
6 6 3 0
8 4 2 1
12 6 1 1
10 8 4 0
4 2 12 14

##样例输出1##

Case #1:
1000

#限制#
2000ms
32768KB

#提示#
为了普及计算几何题，此题所需模板可以在精弘论坛ACM板块中下载，所以果断AC吧！地址是：http://bbs.zjut.com/viewthread.php?tid=1479014

#来源#
LCS