Description

Zlin 是一名经验丰富且技艺高超的赛车手,正在参加一场激烈的 GT3 系列赛.这场比赛的舞台设在世界著名的 比利时 Spa-Francorchamps 赛道上,这里以其充满挑战的弯道和长达七公里的赛道长度而闻名.

比赛已经进入最后阶段,Zlin 目前距离胜利仅剩下 $m$ 圈,但在他前方依然有 $n$ 名实力强大的对手.

通过现场遥控检测和数据分析,车队可以知道这 $n$ 位的车手接下来的平均圈速 $a$ 和这些车手当前领先 Zlin 的时间 $b$.

为了赢下比赛,Zlin 想尽可能的全力冲刺,但是车辆的机械结构和轮胎是有寿命的,车辆磨损越严重,接下来的速度损失也会越严重.

所以实际情况是车辆在不同工况下零部件的磨损情况是不同的,也就意味着对于不同的初始圈速,接下来每圈的圈速增加量是不同的.

对此,比赛策略组在赛前就制订了 $x$ 套策略.

每种比赛策略由以下参数决定: \begin{itemize} \item 初始圈速：$t_i$,表示第一圈的时间.

\item 圈速增加值：$d_i$,表示由于轮胎磨损，每跑一圈圈速增加的时间. \end{itemize} 对于第 $i$ 种策略,第 $k$ 圈的圈速为：$t_i + (k - 1) * d_i$.

但是车队的人都是数学白痴,他们并不清楚当前情况使用哪种策略最佳.

对此,请聪明的你帮车队计算一下对于这 $x$ 种策略,每种策略 Zlin 能取得的最好名次.

Format

Input

第一行有三个整数 $n, m, x\ (1 \leq n \leq 2 \cdot 10^5, 1 \leq m \leq 2 \cdot 10^5, 1 \leq x \leq 2 \cdot 10^5)$，分别表示选手数量，比赛圈数，比赛策略数量。

第二行有 $n$ 个整数 $a_1, a_2, \cdots, a_n\ (1 \leq a_i \leq 2 \times 10^5)$，表示每名选手的平均圈速。

第三行有 $n$ 个整数 $b_1, b_2, \cdots, b_n\ (1 \leq b_i \leq 2 \times 10^5)$，表示每名选手领先Zlin的时间。

接下来 $x$ 行,每行有两个整数 $t_i, d_i\ (1 \leq t_i \leq 2 \cdot 10^5, 1 \leq d_i \leq 2 \cdot 10^5)$,分别表示第 $i$ 种策略的初始圈速和圈速增加值。

Output

输出 $x$ 行.

第 $i$ 行输出一个整数表示第 $i$ 种策略下 Zlin 能取得的最好名次.

Samples

123 500

623

Note

初始排名越高,圈速不一定越快.

对于 $x$ 种策略,不保证 $t$ 越大, $d$ 越小,有可能速度快的同时车辆磨损还小.

默认超车不损失任何时间.

Limitation

1s, 1024KiB for each test case.