灯塔（beac）

题目描述

海岸线上从西向东依次分布着 $n$ 座灯塔，编号为 $1$ 到 $n$。第 $i$ 座灯塔的高度为 $h_i$，从这座灯塔转发一次信号需要消耗 $c_i$ 单位能量。为了避免信号在相近高度的塔之间反复转发，每座灯塔都预先规定了唯一的后继：从灯塔 $i$ 发出的信号，只会传递给它东侧第一座高度严格大于 $h_i$ 的灯塔。如果东侧不存在这样的灯塔，信号就在灯塔 $i$ 停止。

Y 同学需要处理 $q$ 次相互独立的应急测试。每次测试给出起始灯塔 $s$ 和初始能量 $e$。信号最初位于灯塔 $s$。只要当前灯塔存在后继，并且剩余能量不少于当前灯塔的转发消耗，信号就会继续向后继传递，同时扣除对应能量；否则测试立即结束。

对于每次测试，请输出信号最终停留的灯塔编号，以及测试结束时剩余的能量。

输入格式

第一行包含两个整数 $n,q$，分别表示灯塔数量和测试次数。

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

第三行包含 $n$ 个整数 $c_1,c_2,\ldots,c_n$，表示单次转发消耗。

接下来 $q$ 行，每行包含两个整数 $s,e$，描述一次测试。

输出格式

对于每次测试，输出一行两个整数，依次表示最终停留的灯塔编号和剩余能量。

样例

6 4
4 2 7 3 6 9
5 1 4 3 2 8
1 8
2 10
4 5
3 3

3 3
6 5
6 0
3 3

数据范围与约定

对于所有数据，$1\le n,q\le 2\times10^5$，$1\le h_i,c_i\le 10^9$，$0\le e\le 10^14$。

性质 A：保证 $h_1<h_2<\cdots<h_n$。

性质 B：保证 $h_1>h_2>\cdots>h_n$。