Aizhan 准备教 Emil 做 Quyrdaq，这是一种由精肉和土豆制成的传统哈萨克菜肴。根据她的古老食谱，第一步是炸土豆。为了完成这一步，必须遵循一条重要规则——只有当土豆大小各不相同（即没有两个土豆大小相同）时，才能将它们放在同一个锅里炸。

食谱的一部分描述了一种分离土豆的特殊技术。首先，将手头所有的 $n$ 个土豆（大小分别为 $a_1, a_2, \dots, a_n$）排成一行。然后必须执行以下程序：

1. 如果当前行中没有两个大小相同的土豆，则该行中的所有土豆一起放入一个锅中炸，耗时 $x$ 秒。
2. 否则，必须将当前行的土豆分成两行。新行中的第一行将包含奇数位置的土豆（$a_1, a_3, \dots$），而另一行将包含偶数位置的土豆（$a_2, a_4, \dots$）。分离过程耗时 $y$ 秒。随后，该程序将依次应用于这两个新行。

Emil 很快意识到，使用全部 $n$ 个土豆可能太费时间了。因此，他决定只使用属于区间 $a_l, a_{l+1}, \dots, a_r$ 的土豆。现在，他只需要选择 $l$ 和 $r$ 的值，他为此想出了 $q$ 种不同的方案。

请帮助我们的朋友。对于 $q$ 种选择 $l$ 和 $r$ 的方案中的每一种，计算按照上述程序炸排成一行的土豆 $a_l, a_{l+1}, \dots, a_r$ 所需的时间。

你可以在“说明”部分找到额外的解释。

输入格式

第一行包含三个整数 $n, x, y$ ($1 \le n \le 2 \cdot 10^5, 0 \le x, y \le 10^9$)。 第二行包含 $n$ 个空格分隔的整数 $a_1, \dots, a_n$ ($1 \le a_i \le n$)。 第三行包含整数 $q$ ($1 \le q \le 2 \cdot 10^5$)。 接下来的 $q$ 行，每行包含两个数字 $l_i, r_i$ ($1 \le l_i \le r_i \le n$)，表示第 $i$ 种方案中 $l$ 和 $r$ 的值。

输出格式

对于 $q$ 种方案中的每一种，输出炸土豆 $a_{l_i}, a_{l_i+1}, \dots, a_{r_i}$ 所需的时间。

子任务

本题包含 8 个子任务，满足以下要求：

1. $n, q \le 1000$。分值 11 分。
2. $n \le 1000$。分值 12 分。
3. $a_i \le 1$。分值 7 分。
4. $a_i \le 2$。分值 15 分。
5. $n, q \le 10^4$。分值 16 分。
6. $n, q \le 5 \cdot 10^4$。分值 14 分。
7. $n, q \le 10^5$。分值 13 分。
8. 原始问题约束。分值 12 分。

样例

样例输入 1

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

样例输出 1

27
5

说明

例如，假设 $x = 5, y = 6$，土豆排成的大小为 $[5, 1, 2, 1, 3, 4, 1]$。对于 $l = 2, r = 5$，我们应该首先将 $[1, 2, 1, 3]$ 分成两行 $[1, 1]$ 和 $[2, 3]$，耗时 6 秒。炸第二行 $[2, 3]$ 将花费 5 秒。第一行 $[1, 1]$ 必须被分成 $[1]$ 和 $[1]$，额外耗时 6 秒。最后，两行都炸 5 秒。整个过程所需的时间为 $6 + 5 + 6 + 5 + 5 = 27$ 秒。

Emil 将独自烹饪，因此所有动作都是依次完成的。换句话说，在分离和油炸过程中的任何时刻，恰好只有一个动作正在进行（炸土豆或将一行分成两行）。