A8168 | 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.