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*_{2*i*}$, $1 ≤ 2*i* ≤ *n*$), $*odd*$ is an array consisting of the numberals whose numbers are odd in $*а*$ ($*odd*_{*i*} = *a*_{2*i* - 1}$, $1 ≤ 2*i* - 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*$.

Input

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.

Output

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

Note

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.