该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

幻想乡一共有 $n$ 名工程师，其中第 $i$ 号工程师的技术水平可以用一个整数 $a_i$ 表示。

每名工程师还有一个在心中默默比较的对象，其中第 $i$ 号工程师的比较对象的编号可以记作 $p_i$。

在为“幻想乡补完计划”项目工作的过程中，这些工程师每天都会“见贤思齐”。即，每一天开始的时候，如果第 $p_i$ 号工程师的技术水平 $a_{p_i}$ 不小于第 $i$ 号工程师的技术水平 $a_i$，那么第 $i$ 号工程师就会加倍努力工作，使得他这一天结束的时候技术水平从 $a_i$ 增长到 $a_i + 1$。

幻想乡乡长历来对项目进展十分重视。在这个工程师们互相切磋的过程中，他会进行 $q$ 次的质询。每次质询，他会给出一个工程师的编号 $g$ 和一个天数 $d$，你的任务就是帮助幻想乡乡长预测在第 $d$ 天结束的时候编号为 $g$ 的工程师的技术水平。

输入格式

第一行：两个整数 $n,q$，表示工程师总数和质询总数。

第二行：$n$ 个整数 $a_1,\ldots,a_n$，表示每名工程师的技术水平。

第三行：$n$ 个整数 $p_1,\ldots,p_n$，表示每名工程师心中的比较对象编号。

接下来 $q$ 行：每行两个整数 $g,d$，表示一次质询。

输出格式

输出 $q$ 行：每行一个整数表示一个问题的答案。

4 12
4 9 5 8
2 3 4 2
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
4 1
4 2
4 3

5
6
7
9
9
9
6
7
8
9
10
10

大样例

大样例

数据规模与约定

对于全部数据：$1\leq n,q\leq 2\times 10^5,\ 1\leq a_i\leq 10^9,\ 1\leq g,p_i\leq n,\ 1\leq d\leq 2\times 10^5$。