影魔，奈文摩尔，据说有着一个诗人的灵魂。事实上，他吞噬的诗人灵魂早已成千上万。千百年来，他收集了各式各样的灵魂，包括诗人、牧师、帝王、乞丐、奴隶、罪人，当然，还有英雄。

每一个灵魂，都有着自己的战斗力，而影魔，靠这些战斗力提升自己的攻击。

奈文摩尔有 nnn 个灵魂，他们在影魔宽广的体内可以排成一排，从左至右标号 111 到 nnn。第 iii 个灵魂的战斗力为 kik_iki，灵魂们以点对的形式为影魔提供攻击力，对于灵魂对 i,j(i<j)i, j(i<j)i,j(i<j) 来说，若不存在 ks(i<s<j)k_s(i<s<j)ks(i<s<j)</s<j)k_s(i<s<j) 大于 kik_iki 或者 kjk_jkj，则会为影魔提供 p1p_1p1 的攻击力（可理解为：当 j=i+1j = i + 1j=i+1 时，因为不存在满足 i<s<ji <="" s="" ji<s<j</s 的 sss，从而 ksk_sks 不存在，这时提供 p1p_1p1 的攻击力；当 j>i+1j > i + 1j>i+1 时，若 max{ks∣i<s<j}≤min(ki,kj)\max\{k_s |="" i="" <="" s="" j\}\le="" \min(k_i,="" k_j)max{ks∣i<s<j}≤min(ki,kj)</s，则提供 p1p_1p1 的攻击力）；另一种情况，令 ccc 为 ki+1,ki+2,⋯,kj−1k_{i + 1}, k_{i + 2}, \cdots, k_{j -1}ki+1,ki+2,⋯,kj−1 的最大值，若 ccc 满足：ki<c<kjk_i <="" c="" k_jki<c<kj</c，或者 kj<c<kik_j <="" c="" k_ikj<c<ki</c，则会为影魔提供 p2p_2p2 的攻击力，当这样的 ccc 不存在时，自然不会提供这 p2p_2p2 的攻击力；其他情况的点对，均不会为影魔提供攻击力。

影魔的挚友噬魂鬼在一天造访影魔体内时被这些灵魂吸引住了，他想知道，对于任意一段区间 [a,b][a,b][a,b]，位于这些区间中的灵魂对会为影魔提供多少攻击力，即考虑所有满足 a≤i<j≤ba\le i<j\le="" ba≤i<j≤b 的灵魂对 i,ji, ji,j 提供的攻击力之和。

顺带一提，灵魂的战斗力组成一个 111 到 nnn 的排列：k1,k1,⋯,knk_1, k_1, \cdots, k_nk1,k1,⋯,kn。

第一行四个整数 n,m,p1,p2n,m,p_1,p_2n,m,p1,p2；
第二行 nnn 个整数数：k1,k2,⋯,knk_1, k_2,\cdots, k_nk1,k2,⋯,kn；
接下来 mmm 行,每行两个数 a,ba,ba,b，表示询问区间 [a,b][a,b][a,b] 中的灵魂对会为影魔提供多少攻击力。

共输出 mmm 行，每行一个答案，依次对应 mmm 个询问。

对于 30%30\%30% 的数据，1≤n,m≤5001\le n, m\le 5001≤n,m≤500；
另有 30%30\%30% 的数据，p1=2p2p_1 = 2p_2p1=2p2；
对于 100%100\%100% 的数据，1≤n,m≤200000,1≤p1,p2≤10001\le n,m\le 200000, 1\le p_1, p_2\le 10001≤n,m≤200000,1≤p1,p2≤1000。