Problem: 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 (eveni = a2i, 1 ≤ 2i ≤ n), odd is an array consisting of the numberals whose numbers are odd in а (oddi = a2i - 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 bi, such that l ≤ i ≤ r and u ≤ bi ≤ v. You should print the query results modulo mod.

Input

The first line contains three integers n, m, mod (1 ≤ n ≤ 1018, 1 ≤ m ≤ 105, 1 ≤ mod ≤ 109). Next m lines describe the queries. Each query is defined by four integers l, r, u, v (1 ≤ l ≤ r ≤ n, 1 ≤ u ≤ v ≤ 1018).

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.

Examples

Input

4 5 10000
2 3 4 5
2 4 1 3
1 2 2 4
2 3 3 5
1 3 3 4


Output

0
5
3
3
3


Input

2 5 10000
1 2 2 2
1 1 4 5
1 1 2 5
1 1 1 3
1 2 5 5


Output

2
0
0
1
0

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.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
long long int modulo;
long long int suma(long long int ini, long long int salto,
                   long long int cuantos) {
  long long int cuantosporcuantosmenos1partidopor2;
  if (cuantos % 2 == 0)
    cuantosporcuantosmenos1partidopor2 =
        cuantos / 2 % modulo * ((cuantos + modulo - 1) % modulo) % modulo;
  else
    cuantosporcuantosmenos1partidopor2 =
        (cuantos - 1) / 2 % modulo * (cuantos % modulo) % modulo;
  ini %= modulo;
  salto %= modulo;
  cuantos %= modulo;
  return (ini * cuantos + salto * cuantosporcuantosmenos1partidopor2) % modulo;
}
long long int suma(long long int ini, long long int salto,
                   long long int cuantos, long long int u, long long int v) {
  long long int inf, sup;
  if (u <= ini)
    inf = 1;
  else {
    inf = 1 + (u - ini) / salto;
    if ((u - ini) % salto != 0) inf++;
  }
  if (v >= ini + (cuantos - 1) * salto)
    sup = cuantos;
  else if (v < ini)
    sup = 0;
  else
    sup = 1 + (v - ini) / salto;
  if (inf > sup) return 0;
  return suma(ini + (inf - 1) * salto, salto, sup - inf + 1);
}
long long int sumale(long long int ini, long long int salto,
                     long long int cuantos, long long int le, long long int u,
                     long long int v) {
  if (le == 1) return suma(ini, salto, cuantos, u, v);
  long long int cuantosle = cuantos / 2;
  long long int cuantosri = cuantos / 2;
  if (cuantosle + cuantosri < cuantos) cuantosle++;
  if (le <= cuantosle)
    return (sumale(ini, 2 * salto, cuantosle, le, u, v) +
            suma(ini + salto, 2 * salto, cuantosri, u, v)) %
           modulo;
  return sumale(ini + salto, 2 * salto, cuantosri, le - cuantosle, u, v);
}
long long int sumari(long long int ini, long long int salto,
                     long long int cuantos, long long int ri, long long int u,
                     long long int v) {
  if (ri == cuantos) return suma(ini, salto, cuantos, u, v);
  long long int cuantosle = cuantos / 2;
  long long int cuantosri = cuantos / 2;
  if (cuantosle + cuantosri < cuantos) cuantosle++;
  if (ri > cuantosle)
    return (suma(ini, 2 * salto, cuantosle, u, v) +
            sumari(ini + salto, 2 * salto, cuantosri, ri - cuantosle, u, v)) %
           modulo;
  return sumari(ini, 2 * salto, cuantosle, ri, u, v);
}
long long int sumaleri(long long int ini, long long int salto,
                       long long int cuantos, long long int le,
                       long long int ri, long long int u, long long int v) {
  if (cuantos == 1) {
    if (ini >= u and ini <= v) return ini % modulo;
    return 0;
  }
  long long int cuantosle = cuantos / 2;
  long long int cuantosri = cuantos / 2;
  if (cuantosle + cuantosri < cuantos) cuantosle++;
  if (ri <= cuantosle) return sumaleri(ini, 2 * salto, cuantosle, le, ri, u, v);
  if (le > cuantosle)
    return sumaleri(ini + salto, 2 * salto, cuantosri, le - cuantosle,
                    ri - cuantosle, u, v);
  return (sumale(ini, 2 * salto, cuantosle, le, u, v) +
          sumari(ini + salto, 2 * salto, cuantosri, ri - cuantosle, u, v)) %
         modulo;
}
int main() {
  long long int n, m;
  cin >> n >> m >> modulo;
  for (int cas = 0; cas < m; cas++) {
    long long int le, ri, u, v;
    cin >> le >> ri >> u >> v;
    cout << sumaleri(1, 1, n, le, ri, u, v) << endl;
  }
}