The concert band is playing spooky songs for Halloween!

A song can be represented as an array ~A~ of ~N~ elements. A sample of ~A~ is a subarray with bounds ~[l, r], \ 1 \le l \le r \le N~ of ~A~.

A spooky pair is a pair in a sample ~(i, j), \ l \le i < j \le r~ such that ~|A_i - A_j|~ is a multiple of four.

Aaron happens to be one of the best band players, but is deathly afraid of spooky pairs. To overcome this fear, he will practice ~Q~ samples.

For each sample, he wants you to determine the number of spooky pairs in order to not get jumpscared while playing. Can you help him?

Constraints

~1 \le N, Q \le 10^6~

~1 \le A_i \le 10^9~

Subtask 1 [15%]

~A_i~ is a multiple of four.

Subtask 2 [85%]

No additional constraints.

Input Specification

The first line of input will contain integers ~N~ and ~Q~.

The next line will contain ~N~ integers ~A_i~.

The next ~Q~ lines will contain ~2~ integers ~l~ and ~r~, the bounds for the sample.

Fast IO is recommended as input can get quite large. Python users should submit in PyPy.

Output Specification

For each of the ~Q~ samples output the number of spooky pairs in the sample on a new line.

Sample Input 1

4 2
4 8 4 12
2 4
2 2

Sample Output 1

3
0

Explanation for Sample Output 1

~(2, 3)~, ~(2, 4)~, and ~(3, 4)~ are spooky pairs in the first sample.

There are no spooky pairs in the second sample.

This sample input conforms to subtask ~1~.

Sample Input 2

5 3
1 3 5 7 7
1 5
4 5
1 3

Sample Output 2

4
1
1