中继

时间限制：$2.0\text{ s}$

空间限制：$128\text{ MiB}$

题目描述

一条狭长山谷中，从西向东依次建有 $n$ 座信号塔。第 $i$ 座塔的高度为 $h_i$。由于山谷的定向天线只能向东扫描，信号不会向编号更小的塔返回。

为了避免信号被较近的低塔遮挡，每座塔收到消息后，只会将它转发给东侧第一座高度严格大于自己的信号塔。高度相等的塔不符合条件。若东侧不存在这样的塔，则该塔没有后继，消息会停留在此处。

第 $i$ 座塔完成一次转发需要消耗 $c_i$ 单位的独立应急电量。消息被接收时不产生计入本题的消耗；电量只在实际完成一次转发时扣除。

现在要进行 $q$ 次独立的应急演练。每次给出起始塔 $s$ 和可用总电量 $x$。消息先位于第 $s$ 座塔，然后按上述唯一的后继规则不断向东转发。若当前塔没有后继，或剩余电量小于它的转发费用，消息就立即停止。当剩余电量恰好等于 $c_i$ 时，该次转发可以进行。

对每次演练，求消息最后停留的信号塔编号，以及实际完成的转发次数。演练之间不共享电量或消息状态。

输入格式

第一行两个正整数 $n,q$。

第二行 $n$ 个正整数 $h_1,h_2,\ldots,h_n$，表示各塔高度。

第三行 $n$ 个正整数 $c_1,c_2,\ldots,c_n$，表示各塔的转发费用。

接下来 $q$ 行，每行两个整数 $s,x$，表示一次测试的起始塔和可用电量。

输出格式

对每次测试输出一行两个整数，依次表示消息最后停留的塔编号和转发次数。

输入样例 1

6 4
3 1 4 4 2 6
5 2 7 1 3 9
1 4
1 5
2 9
4 100

输出样例 1

1 0
3 1
6 2
6 1

输入样例 2

7 5
2 2 5 1 4 5 8
3 8 2 6 1 4 7
1 3
2 8
3 2
4 7
6 100

输出样例 2

3 1
3 1
7 1
6 2
7 1

输入样例 3

见附件 sample/relay3.in

输出样例 3

见附件 sample/relay3.out

数据范围

对于所有测试点，保证 $1\le n,q\le 2\times 10^5$，$1\le h_i,c_i\le 10^9$，$1\le s\le n$，$0\le x\le 10^{18}$。

每个测试点单独计分。