题目内容

在神秘的遗迹中隐藏着 $n$ 块传送石碑，编号为 $1$ 到 $n$。每块石碑 $i$ 上刻有一个能量值 $w_i$，并且刻有一个固定的目的地 $d_i$（$1 \le d_i \le n$），表示从石碑 $i$ 只会传送到石碑 $d_i$。

探险者可以站在一块石碑上，选择是否进行传送。每次传送时，设当前石碑为 $i$，目标石碑为 $j = d_i$：

• 若 $w_j > w_i$，则探险者的能量增加 $X$；
• 若 $w_j \le w_i$，则探险者的能量增加 $Y$。

注意 $X$ 和 $Y$ 可以是负数，表示能量减少。初始能量为 $0$，探险者可以在任意时刻选择停止，并且不必走完所有可能的步数。

现在有 $q$ 次独立的询问，每次询问给定一个起始石碑 $u$ 和一个最大传送次数 $k$。你需要回答：从石碑 $u$ 出发，按照目的地序列连续传送，总步数不超过 $k$，所能获得的能量序列前缀和的最大值是多少（可以选择不走，此时收益为 $0$）。

输入保证 $n$ 和 $q$ 均不超过 $2 imes 10^5$，$X$ 与 $Y$ 的绝对值不超过 $10^6$，石碑能量值 $w_i$ 不超过 $10^6$，步数限制 $k$ 不超过 $10^9$。

输入描述

第一行输入四个整数 $n, q, X, Y$。 第二行输入 $n$ 个整数 $d_1, d_2, \dots, d_n$，表示每块石碑的目的地。 第三行输入 $n$ 个整数 $w_1, w_2, \dots, w_n$，表示每块石碑的能量值。 接下来 $q$ 行，每行输入两个整数 $u, k$，代表一次询问的起始石碑编号和最大传送次数。

输出描述

输出 $q$ 行，每行一个整数，表示对应询问的最大能量收益（至少为 $0$）。

样例1

输入

4 4 2 1
2 3 4 1
1 2 3 4
1 1
1 2
1 3
4 2

输出

2
4
6
4

说明

石碑能量依次为 $w = [1, 2, 3, 4]$，目的地构成环 $1 o 2 o 3 o 4 o 1$。由于始终满足 $w_{d_i} > w_i$，每一步收益均为 $X = 2$。

• 询问 1 1：走 1 步得到收益序列 $[0, 2]$，最大前缀和为 2。
• 询问 1 2：走 2 步得 $[0, 2, 4]$，最大值为 4。
• 询问 1 3：走 3 步得 $[0, 2, 4, 6]$，最大值为 6。
• 询问 4 2：从 4 出发经 $1$ 到 $2$，收益依次为 $2, 2$，序列 $[0, 2, 4]$，最大值 4。所有收益非负，走满 $k$ 步即最优。

样例2

输入

3 3 -5 3
2 3 1
10 5 8
1 2
1 3
2 1

输出

3
3
0

说明

$n=3$，能量 $w=[10,5,8]$，目的地 $d=[2,3,1]$。$X=-5$，$Y=3$。

• 询问 1 2：路径 $1 o 2$（$w_2=5 \le 10$，收益 $Y=3$）再 $2 o 3$（$w_3=8 > 5$，收益 $X=-5$）。累计能量序列 $[0, 3, -2]$，最大前缀和为 3。
• 询问 1 3：继续 $3 o 1$（$w_1=10 > 8$，收益 $-5$），序列 $[0,3,-2,-7]$，最大值仍为 3。
• 询问 2 1：从 2 走 1 步到 3，收益 $-5$，序列 $[0,-5]$，最大值取 $0$（可以不传送）。

样例3

输入

4 3 -2 3
2 3 4 1
1 10 5 20
1 4
1 3
2 1

输出

2
1
3

说明

$X=-2, Y=3$，$w=[1,10,5,20]$，$d=[2,3,4,1]$。

• 询问 1 4：走 4 步，依次 $1 o 2$（$10 > 1$，收益 $-2$），$2 o 3$（$5 \le 10$，收益 $+3$），$3 o 4$（$20 > 5$，收益 $-2$），$4 o 1$（$1 \le 20$，收益 $+3$）。累计序列 $[0,-2,1,-1,2]$，最大前缀为 2。
• 询问 1 3：仅走前 3 步，序列 $[0,-2,1,-1]$，最大值 1。
• 询问 2 1：从 2 走 1 步到 3，$5 \le 10$ 得 $+3$，最大前缀为 3。