Description

博士:「名乃,名乃」
名乃:「怎麼了博士?」
博士:「名乃我改造你的身體了。」
名乃:「欸?」
博士:「我在名乃身上輸入了一個序列,我只要按按鈕名乃就會回答出答案喔。」
名乃:「怎麼會這樣 >A<」
博士:「>Ɐ<」

博士在名乃身上輸入了一個長度為 $N$ 的序列 $a_1\sim a_N$,並且還輸入了三個整數 $A,B,K$。
接下來博士會按 $Q$ 次按鈕,每次博士會按兩個正整數 $l,r$($1\leq l\leq r\leq N$),按完之後名乃會回答 $a_l\sim a_r$ 裡有幾對數字位元 xor 後再 xor $A$ 與 xor $B$ 的和 $\geq K$,
也就是 $\sum\limits_{i=l}^ r\sum\limits_{j=i+1}^ r [(a_i\oplus a_j\oplus A)+(a_i\oplus a_j\oplus B)\geq K]$。

因為博士程式寫到一半就跑去吃點心了,所以寫程式的重責大任就交給你了。

Input Format

第一行輸入兩個正整數 $N,Q$。
第二行輸入三個整數 $A,B,K$。
第三行輸入 $N$ 個整數 $a_1\sim a_N$。
接下來 $Q$ 行,每行輸入兩個正整數 $l,r$。

對於所有測試資料:

  • $1\leq N,Q\leq 10^ 5$
  • $0\leq A,B,a_i<2048$
  • $0\leq K<4096$
  • $1\leq l\leq r\leq N$

Output Format

對於每次輸入 $l,r$,輸出一個整數 $\sum\limits_{i=l}^ r\sum\limits_{j=i+1}^ r [(a_i\oplus a_j\oplus A)+(a_i\oplus a_j\oplus B)\geq K]$。

Sample Input 1

7 10
11 13 21
13 6 3 12 15 12 15
1 2
2 7
1 6
2 5
5 6
2 2
1 5
3 5
5 6
1 3

Sample Output 1

0
7
7
2
1
0
4
1
1
1

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~6 $N,Q\leq 500$ 9
3 0~12 $N\leq 3000$ 15
4 0, 13~20 $a_i<32$ 14
5 1, 21~26 $l=1$ 22
6 0~40 無其他限制 40

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 524288 65536 1 2 3 4 6
1 2000 524288 65536 2 3 5 6
2 2000 524288 65536 2 3 6
3 2000 524288 65536 2 3 6
4 2000 524288 65536 2 3 6
5 2000 524288 65536 2 3 6
6 2000 524288 65536 2 3 6
7 2000 524288 65536 3 6
8 2000 524288 65536 3 6
9 2000 524288 65536 3 6
10 2000 524288 65536 3 6
11 2000 524288 65536 3 6
12 2000 524288 65536 3 6
13 2000 524288 65536 4 6
14 2000 524288 65536 4 6
15 2000 524288 65536 4 6
16 2000 524288 65536 4 6
17 2000 524288 65536 4 6
18 2000 524288 65536 4 6
19 2000 524288 65536 4 6
20 2000 524288 65536 4 6
21 2000 524288 65536 5 6
22 2000 524288 65536 5 6
23 2000 524288 65536 5 6
24 2000 524288 65536 5 6
25 2000 524288 65536 5 6
26 2000 524288 65536 5 6
27 2000 524288 65536 6
28 2000 524288 65536 6
29 2000 524288 65536 6
30 2000 524288 65536 6
31 2000 524288 65536 6
32 2000 524288 65536 6
33 2000 524288 65536 6
34 2000 524288 65536 6
35 2000 524288 65536 6
36 2000 524288 65536 6
37 2000 524288 65536 6
38 2000 524288 65536 6
39 2000 524288 65536 6
40 2000 524288 65536 6