CF117D.Not Quick Transformation

Let $a$ be an array consisting of $n$ numbers. The array's elements are numbered from $1$ to $n$ , $even$ is an array consisting of the numerals whose numbers are even in $a$ ( $even_{i}=a_{2i}$ , $1<=2i<=n$ ), $odd$ is an array consisting of the numberals whose numbers are odd in $а$ ( $odd_{i}=a_{2i-1}$ , $1<=2i-1<=n$ ). Then let's define the transformation of array $F(a)$ in the following manner:

• if n>1 , $F(a)=F(odd)+F(even)$ , where operation " $+$ " stands for the arrays' concatenation (joining together)
• if $n=1$ , $F(a)=a$

Let $a$ be an array consisting of $n$ numbers $1,2,3,...,n$ . Then $b$ is the result of applying the transformation to the array $a$ (so $b=F(a)$ ). You are given $m$ queries $(l,r,u,v)$ . Your task is to find for each query the sum of numbers $b_{i}$ , such that $l<=i<=r$ and $u<=b_{i}<=v$ . You should print the query results modulo $mod$ .

The first line contains three integers $n$ , $m$ , $mod$ ( $1<=n<=10^{18},1<=m<=10^{5},1<=mod<=10^{9}$ ). Next $m$ lines describe the queries. Each query is defined by four integers $l$ , $r$ , $u$ , $v$ ( $1<=l<=r<=n$ , $1<=u<=v<=10^{18}$ ).

Please do not use the %lld specificator to read or write 64-bit integers in C++. Use %I64d specificator.

Print $m$ lines each containing an integer — remainder modulo $mod$ of the query result.

Let's consider the first example. First let's construct an array $b=F(a)=F([1,2,3,4])$ .

• Step 1. $F([1,2,3,4])=F([1,3])+F([2,4])$
• Step 2. $F([1,3])=F([1])+F([3])=[1]+[3]=[1,3]$
• Step 3. $F([2,4])=F([2])+F([4])=[2]+[4]=[2,4]$
• Step 4. $b=F([1,2,3,4])=F([1,3])+F([2,4])=[1,3]+[2,4]=[1,3,2,4]$

Thus $b=[1,3,2,4]$ . Let's consider the first query $l=2,r=3,u=4,v=5$ . The second and third positions in the array $b$ do not have numbers in the range $[4,5]$ , so the sum obviously equals zero. Let's consider the second query $l=2,r=4,u=1,v=3$ . The second and third positions have two numbers that belong to the range $[1,3]$ , their sum equals 5.