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*<sub class="lower-index">*i*</sub> = *a*<sub class="lower-index">2*i*</sub>, 1 ≤ 2*i* ≤ *n*), *odd* is an array consisting of the numberals whose numbers are odd in *а* (*odd*<sub class="lower-index">*i*</sub> = *a*<sub class="lower-index">2*i* - 1</sub>, 1 ≤ 2*i* - 1 ≤ *n*). Then let's define the transformation of array *F*(*a*) in the following manner:
 -  if *n* &gt; 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*<sub class="lower-index">*i*</sub>, such that *l* ≤ *i* ≤ *r* and *u* ≤ *b*<sub class="lower-index">*i*</sub> ≤ *v*. You should print the query results modulo *mod*.
The first line contains three integers *n*, *m*, *mod* (1 ≤ *n* ≤ 10<sup class="upper-index">18</sup>, 1 ≤ *m* ≤ 10<sup class="upper-index">5</sup>, 1 ≤ *mod* ≤ 10<sup class="upper-index">9</sup>). 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<sup class="upper-index">18</sup>).

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

line = sys.stdin.readline().split(" ")
N = int(line[0])
queryc = int(line[1])
MOD = int(line[2])

def find (length, idx):
    if length == 1:
        return 0
    if idx < (length + 1) // 2:
        return 2 * find((length + 1) // 2, idx)
    else:
        return 2 * find(length // 2, idx - (length + 1) // 2) + 1

MAX_LG = 60

def n_suff (suff, lens, v):
    add = 0
    if suff <= v % (1 << lens):
        add = 1
    return (v >> lens) + add

def sum_n (n):
    return n * (n - 1) // 2

def sum_le (x, v):
    cnt = 0
    sums = 0

    if x <= v:
        sums += x
        cnt += 1

    for i in range(MAX_LG - 1, -1, -1):
        if x & 1 << i:
            suff = x % (1 << i)
            ns = n_suff(suff, i + 1, v)
            cnt += ns
            sums += ns * suff
            sums += sum_n(ns) << (i + 1)

    return sums + cnt

def query_up (r, v):
    if r < 0:
        return 0
    if v < 0:
        return 0
    return sum_le(find(N, r), min(v, N - 1))

def query (l, r, u, v):
    return query_up(r, v) - query_up(l - 1, v) - query_up(r, u - 1) + query_up(l - 1, u - 1)

for i in range(queryc):
    q = sys.stdin.readline().split(" ")
    sys.stdout.write(str(query(int(q[0]) - 1, int(q[1]) - 1, int(q[2]) - 1, int(q[3]) - 1)))
    sys.stdout.write('\n')
