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 JAVA):

Solution:
import java.io.InputStreamReader;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.math.BigInteger;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author AlexFetisov
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskD solver = new TaskD();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskD {
    long mod;

    public void solve(int testNumber, InputReader in, PrintWriter out) {
        long n = in.nextLong();
        int countQueries = in.nextInt();
        mod = in.nextLong();
        for (int q = 0; q < countQueries; ++q) {
            long left = in.nextLong() - 1;
            long right = in.nextLong() - 1;
            long down = in.nextLong();
            long up = in.nextLong();
            out.println(ask(0, n - 1, left, right, down, up, 1, n, 1));
        }
    }

    public long ask(long start, long finish, long step, long down, long up) {
        if (up < start || down > finish) return 0;
        if (down <= start) {
            down = start;
        } else {
            long left = (down - start + step - 1) / step;
            down = left * step + start;
        }

        if (up >= finish) {
            up = finish;
        } else {
            long left = (up - start) / step;
            up = left * step + start;
            if (up >= finish) up = finish;
        }

        long am = (up - down) / step;
        ++am;
        if (am % 2 == 0) {
            am /= 2;
            am %= mod;
            long res = (up + down) % mod;
            res *= am;
            return res % mod;
        } else {
            am %= mod;
            long res = ((up + down) / 2) % mod;
            res *= am;
            return res % mod;
        }
//        am %= mod;
//        long res = (up + down) % mod;
//        res *= am;
//        res %= mod;
        //BigInteger bi = BigInteger.valueOf(am).multiply(BigInteger.valueOf(up + down)).divide(BigInteger.valueOf(2));
//        return bi.mod(BigInteger.valueOf(mod)).intValue();
    }

    long ask(long rangeLeft, long rangeRight, long left, long right, long down, long up, long start, long finish, long step) {
        if (rangeLeft == left && rangeRight == right) {
            return ask(start, finish, step, down, up);
        }
        long middle = (rangeLeft + rangeRight) / 2;
        long res = 0;
        if (left <= middle) {
            long newStep = step * 2;
            long am = (finish - start) / step + 1;
            long newFinish = finish;
            if (am % 2 == 0) {
                newFinish = finish - step;
            }
            res += ask(rangeLeft, middle, left, Math.min(right, middle), down, up, start, newFinish, newStep);
        }
        if (right > middle) {
            long newStep = step * 2;
            long am = (finish - start) / step + 1;
            long newFinish = finish;
            if (am % 2 == 1) {
                newFinish = finish - step;
            }
            res += ask(middle + 1, rangeRight, Math.max(middle + 1, left), right, down, up,  start + step, newFinish, newStep);
        }
        return res % mod;
    }
}

class InputReader {
    private BufferedReader reader;
    private StringTokenizer stt;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream));
    }

    public String nextLine() {
        try {
            return reader.readLine().trim();
        } catch (IOException e) {
            return null;
        }
    }

    public String nextString() {
        while (stt == null || !stt.hasMoreTokens()) {
            stt = new StringTokenizer(nextLine());
        }
        return stt.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(nextString());
    }

    public long nextLong() {
        return Long.parseLong(nextString());
    }

}