Jill 热爱大学生活，为了保持优异的成绩，她从不耽误任何家庭作业的截止日期。但更重要的是，她热爱观看系列剧并与她最好的朋友 Johnny 讨论剧情。不幸的是，今天她必须在这两项活动之间做出选择！

Jill 需要完成 $n$ 项家庭作业。第 $i$ 项任务需要 $a_i$ 分钟完成，并且必须在从现在起最多 $d_i$ 分钟内提交给老师。此外，还有 $m$ 集新出的系列剧，Johnny 和 Jill 想要讨论这些剧集。第 $j$ 集的时长为 $l_j$ 分钟。Jill 可以按任意顺序完成作业，但她必须按顺序观看剧集。无论是完成作业还是观看剧集，一旦开始都不能中断。

Johnny 和 Jill 需要商定一个时间 $t_k$ 进行通话讨论剧情。他们目前还不确定选择哪个时间。对于每一个可能的时间 $t_k$，请计算在保证能够按时完成所有 $n$ 项家庭作业的前提下，Jill 最多能观看多少集剧集。

注意：在本题中，我们假设与 Johnny 在 $t_k$ 时刻讨论剧情不会占用 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$) —— 通话时间的可能数量。

第二行包含 $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$ 下，Jill 最多能观看的剧集数量。

样例

样例输入 1

2
1 2 3
10
15
5 5
5 15 20
3 4 5
8 100 8
10 150 20
2 32 1 1
9 200 51 50 10

样例输出 1

1 1 2
1 4 2 2 1