爱丽丝啊。

总有一天，我会回来牵起你温暖的手，将你从那里救出来。

然后，再一次成为恋人吧。

在柴郡猫的帮助下，归雨和爱丽丝终于可以在箱庭迷宫中交流并行动。迷宫由编号 到 的 个箱庭组成，每个箱庭 有一条单向通道通往另一个箱庭 。特别地，若 ，则表示该箱庭是出口，一旦到达即可离开迷宫。

柴郡猫赋予了他们穿越箱庭的能力。他们可以无限次进行以下两种操作，每次操作花费一定的代价：

1. 选择一个人（归雨或爱丽丝）和一个非负整数 ，该人可以连续穿越  个箱庭，即沿着通道移动 步。该操作的代价为 。
2. 选择一个非负整数  ，让两人同时穿越  个箱庭（此时他们必须处于同一箱庭），两人一起沿着通道移动 步，最终仍处于同一箱庭。该操作的代价为 。

注意：每次操作移动 步，需沿着箱庭间的唯一路径前进，且实际步数不得超过路径长度。

由于蠕动潜行者无时无刻不在追寻归雨，归雨必须尽快带着爱丽丝逃离迷宫。归雨希望在总代价最小的前提下逃离。注意，两人必须都到达出口才算成功逃离。

现在给定迷宫的布局，你需要回答多组询问，每组询问给出归雨和爱丽丝的初始位置，输出对应的最小总代价。

第一行四个整数 （，，），表示箱庭的数量、询问的次数以及两种操作的代价。

第二行  个整数 ，其中  表示从箱庭  出发到达的下一个箱庭编号。若 ，则箱庭  为出口。

接下来  行，每行两个整数 （），分别表示归雨和爱丽丝的初始所在箱庭编号。

保证迷宫是连通的，且从任意箱庭出发沿着通道前进最终都会到达唯一的出口（即  的箱庭）。

对于每组询问，输出一行一个整数，表示在最优操作下的最小总代价。

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

2
32
31

50 11 30 1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 0 16 17 18 19 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 25 2 6 19 28 30 31 24 39 36 42 13 29
45 39
9 14
3 23
3 6
39 50
33 8
1 13
16 35
41 15
29 27
42 22

63
61
62
62
63
31
62
30
60
60
64

17 5 30 8
0 1 2 3 4 5 6 7 8 9 10 11 7 13 14 15 16
12 17
2 3
5 8
1 12
17 17

76
38
68
90
24