时间限制：2000ms　内存限制：512MB

题目描述

古代的公文驿传制度里，公文从一个驿站传到下一个驿站，每站都要登记盖章。程老师给地方志办公室整理一份旧驿站的档案，档案里记录着某条驿路上 $n$ 个驿站的传送规则。驿站编号 $1$ 到 $n$，每个驿站 $i$ 都登记了一个固定的"下一站" $p_i$：公文在第 $i$ 个驿站处理完毕后，下一晚必定送往第 $p_i$ 个驿站，风雨无阻，从不更改。$p_i$ 可以是任何一个驿站，包括 $i$ 自己——有些驿站地处要冲，公文要在本站的几个机构之间周转，登记的就是留在本站。

每个驿站还有一项"戳数" $w_i$：公文每在第 $i$ 个驿站过一夜，当晚就盖上 $w_i$ 枚验讫戳。不同驿站经手的部门多少不同，戳数也参差不齐。一份公文从某个驿站起送，第一晚就在起送站盖戳，之后每晚按传送规则前往下一站并盖戳，一晚接一晚，戳数一晚晚累加。由于传送规则是固定的，同一份公文走过的路线完全确定：从哪个驿站出发，后面每一晚在哪个驿站、盖多少戳，都是档案里写得明明白白的事。

档案里还能看出这套驿路的脾气。公文从一个驿站出发，或快或慢，总要走进一段周而复始的循环：有些驿站彼此来回传送，公文进去之后就在这一小片打转，外头的驿站再也去不了；也有些驿站只是过路，公文经过一回就永远离开。传送规则几十年没有变过，所以哪份公文在哪几站之间打转，翻着档案都能提前知道。各站的戳数都是正数，没有白过夜不盖戳的驿站；公文中途也不清账，戳数从头到尾一路累加，不会在哪个驿站归零重算。

地方志办公室正在编一份"公文时效对照表"，编辑们关心的问题是：一份公文从第 $s$ 个驿站起送，至少要过多少晚，累计盖戳数才能不少于 $T$ 枚。这个问题在整理档案时反复出现——不同公文起送站不同，要求的戳数也不同，办公室把问题一批批汇总过来，共有 $q$ 个，每个问题给出 $s$ 和 $T$，都要逐一答复。因为每个驿站的戳数至少是 $1$，晚数只要够多，戳数总能攒够，所以每个问题都有确切答案。

办公室的工作节奏是这样的：上午收到一批问题，下午就要把对照表填出来送回。编辑先试着手算，拿一份公文逐晚推演，第一晚在哪站、盖几枚，第二晚又在哪站、盖几枚，一页页翻档案，翻到戳数攒够为止。要求戳数少的公文还好办，几十晚也就翻完了；遇到要求戳数特别多的，一份公文要推演的晚数多得数不清，几个编辑合力也算不完，只好把这类问题先压下。问题积压得多了，办公室才想到请程老师帮忙。

对照表的填法也有讲究：每个问题只填一个晚数，不填路线，也不填中途各站的戳数，编辑们另有底稿备查。各问题彼此独立，答哪一题都不影响其余的题目；同一个起送站、同一份要求被问了两遍，两遍的答案自然一模一样。

程老师决定把这项答复工作交给程序。给定驿站的传送规则和各站戳数，回答全部 $q$ 个问题。

输入格式

第一行两个整数 $n, q$，表示驿站数量和问题数量。

第二行 $n$ 个整数 $p_1, p_2, \ldots, p_n$，其中 $p_i$ 表示第 $i$ 个驿站登记的下一站。

第三行 $n$ 个整数 $w_1, w_2, \ldots, w_n$，其中 $w_i$ 表示第 $i$ 个驿站每晚的戳数。

接下来 $q$ 行，每行两个整数 $s, T$，表示一个问题的起送驿站和要求戳数。

输出格式

输出 $q$ 行，每行一个整数，依次回答每个问题：累计盖戳数不少于 $T$ 所需的最少晚数。

数据范围

• 特殊性质 A：$p_1 = 2, p_2 = 3, \ldots, p_{n-1} = n, p_n = 1$。
• 对于全部数据，$1 \le n, q \le 2 \times 10^5$，$1 \le p_i \le n$，$1 \le w_i \le 10^9$，$1 \le s \le n$，$1 \le T \le 10^{18}$。

样例

样例 1

输入：

5 3
2 3 4 5 1
1 2 3 4 5
1 1
1 6
4 15

输出：

1
3
5

解释：五个驿站首尾相接转圈。第一个问题从 $1$ 号起送，第一晚就盖 $1$ 枚，够了，只需 $1$ 晚。第二个问题从 $1$ 号起送：第 $1$ 晚盖 $1$ 枚，第 $2$ 晚在 $2$ 号盖 $2$ 枚，第 $3$ 晚在 $3$ 号盖 $3$ 枚，累计 $1 + 2 + 3 = 6$ 枚，恰好够，需 $3$ 晚。第三个问题从 $4$ 号起送：依次盖 $4, 5, 1, 2, 3$，第 $5$ 晚累计 $4 + 5 + 1 + 2 + 3 = 15$ 枚，需 $5$ 晚。

样例 2

输入：

4 2
2 3 4 2
5 1 1 1
1 7
2 9

输出：

3
9

解释：第一个问题从 $1$ 号起送：第 $1$ 晚在 $1$ 号盖 $5$ 枚，第 $2$ 晚在 $2$ 号盖 $1$ 枚，第 $3$ 晚在 $3$ 号盖 $1$ 枚，累计 $5 + 1 + 1 = 7$ 枚，需 $3$ 晚。第二个问题从 $2$ 号起送：$2$ 号送往 $3$ 号，$3$ 号送往 $4$ 号，$4$ 号又送回 $2$ 号，之后每晚都在这三个驿站轮转，每晚只盖 $1$ 枚，攒够 $9$ 枚恰需 $9$ 晚。

样例 3

输入：

3 2
2 3 1
10 20 30
1 100
3 45

输出：

6
3

解释：第一个问题从 $1$ 号起送，三站轮转，逐晚戳数为 $10, 20, 30, 10, 20, 30$：前 $5$ 晚累计 $90$ 枚还不够，第 $6$ 晚累计 $120$ 枚，需 $6$ 晚。第二个问题从 $3$ 号起送：第 $1$ 晚盖 $30$ 枚，第 $2$ 晚在 $1$ 号盖 $10$ 枚，第 $3$ 晚在 $2$ 号盖 $20$ 枚，累计 $60$ 枚，超过 $45$，需 $3$ 晚。