题目内容

​ 小塔正在一张有向但定连通的图上玩游戏。这张图包含$n$个点，第$i$个点的权值为$a$，当小美从$i$移动到 $Next_i$时，游戏规则如下:

• 如果$aNeat_i>ai$，小美的金币将增加$x$;

• 如果$aNext_i≤ai$，小美的金币将增加$y$。

  小塔会提出$q$次询问，每个询问从某个点$u$出发，移动不超过$k$步，最多能获得多少金币。

输入描述

​ 第一行输入四个整数$n,q,x,y(1≤n,q≤2×10^5,-10^6≤x,y ≤10^6)$代表图上点的数量、询问的次数、规则中金币的增加量。 ​ 第二行输入$n$个整数$Next_1,Next_z,...,Next_n(1≤ Next_i≤n)$表示第$i$个节点下一步的位置。 ​ 第三行输入$n$个整数$a_1,a_2,...,a_n(1≤a_i≤10^6)$,表示第$i$个节点的权值。 ​ 此后$q$行，每行输入两个整数$u,k(1≤u≤n,1≤k≤10^9)$ 代表一次询问的起始点和步数限制。

输出描述

对于每一次询问，在一行上输出一个整数，代表最多能获得的金币数量。

样例1

输入

4 5 -2 3
2 3 4 1
5 10 3 2
1 1
1 2
1 4
2 4
2 7

输出

0
1
4
6
8

说明

该样例如下图所示：

●对于第一次询问，走一步会扣除$2$金币，但是可以选择站在原地不走; ●对于第二次询问，走一步时金币数量减至$-2$，走两步金币数量变更为$-2+3=1$。

​

样例2

输入

4 4 2 -1
2 3 1 4
1 2 3 1000000
1 3
3 3
2 2
4 1000000

输出

4
3