一条笔直的公路上有 $k$ 个标志，已知这条公路的长度 $n$，第 $i$ 个标志位于 $a_{i}$ 点，一辆大巴车从 $0$ 点出发，并在 $b_{i}$ 分钟经过第 $i$ 个标志。现给出 $q$ 个询问，求大巴车经过 $d$ 点的时间（向下取整）。

输入有 $t$ 组，对于每组数据的 $q$ 个询问，输出一行，用空格间隔。

对于 $100\%$ 的数据，$1\le t\le 10^4$，$k\le n\le 10^9$，$1\le k,q\le 10^5$，$1\le a_1<a_2<\ldots<a_k=n$，$1\le b_1<b_2<\ldots<b_k\le 10^9$。