吉尔喜欢在大学取得好成绩,因此她从不错过家庭作业的最后期限。但更重要的是,她喜欢观看该剧并与她最好的朋友约翰尼讨论。不幸的是,今天她需要在这两项活动中做出选择!
Jill 需要完成 $$$n$$$ 家庭作业。第 $$$i$$$ 任务需要 $$$a_i$$$ 分钟才能完成,从现在起最多需要 $$$d_i$$$ 分钟提交给教师。此外,约翰尼和吉尔还想讨论该系列的 $$$m$$$ 新剧集。第 $$$j$$$ 集持续 $$$l_j$$$ 分钟。吉尔可以按任何顺序完成任务,但她需要按剧集出现的顺序观看剧集。完成作业或观看剧集开始后都不能中断。
约翰尼和吉尔需要就 $$$t_k$$$ 打电话讨论该系列剧的时间达成一致。他们还不确定选择哪个时间。对于每个可能的时间,计算吉尔在该时间之前可以观看的最大集数,同时仍然能够及时完成所有 $$$n$$$ 家庭作业任务。
请注意,出于解决此问题的目的,我们假设在 $$$t_k$$$ 时间与 Johnny 讨论该系列剧不会占用 Jill 的大量时间,并且 即使她正在完成任何家庭作业, 也可能发生.
输入
输入中有多个测试用例。输入以测试用例的数量 $$$T$$$ ($$$1 \le T \le 1\,000$$$) 开始。
每个测试用例都以一行三个整数开头 $$$n$$$ ($$$1 \le n \le 200\,000$$$) - 作业任务数,$$$m$$$ ($$$1 \le m \le 200\,000$$$) - 集数,以及 $$$q$$$ ($$$1 \le q \le 200\,000$$$) — 与 Jill 通话的可能次数。
第二行包含 $$$n$$$ 整数 $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$) — 完成任务所需的分钟数。下一行包含 $$$n$$$ 整数 $$$d_i$$$ ($$$1 \le d_i \le 10^{15}$$$) - 必须完成此任务的截止日期。下一行包含 $$$m$$$ 整数 $$$l_j$$$ ($$$1 \le l_j \le 10^9$$$) - 按需要观看的顺序排列的剧集长度。下一行包含 $$$q$$$ 整数 $$$t_k$$$ ($$$1 \le t_k \le 10^{15}$$$) - 与 Jill 通话的可能次数。
可以在各自的期限内完成所有任务。
输入中所有测试用例的 $$$n$$$、$$$m$$$、$$$q$$$ 的总和不超过 $$$200\,000$$$。
输出
对于每个测试用例,输出一行包含 $$$q$$$ 整数 - 对于每个可能的时间 $$$t_k$$$ ,吉尔可以观看的最大剧集数。
示例
输入复制
21 2 310155 55 15 203 4 58 100 810 150 202 32 1 19 200 51 50 10
输出复制
1 1 2 1 4 2 2 1