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