Not Quick Transformation

题意翻译

对一个数列 $s$ 定义 $odd_s$ 是将 $s$ 的奇数位取出，即 $odd_s=\{s_{2i}\mid1\le 2i\le |S|\}$；$even_s$ 是将其偶数位取出，同理。 定义一个数列 $s$ 的变换 $F(s)$： $$ F(s)=\begin{cases} F(odd_s)+F(even_s)&|s|>1\\ s&|s|=1 \end{cases} $$ (上面的 $+$ 表示将两个数列首尾相接) 给定正整数 $n$，数列 $a=\{1,2,\dots,n\}$。通过变换得到 $b=F(a)$。 然后进行 $m$ 次询问，每次给出正整数 $l,r,u,v$，求 $$ \sum_{l\le i\le r}[u\le b_i\le v]b_i $$ 即求 $b$ 的 $[l,r]$ 区间内，权值在 $u,v$ 之间的数的权值和，答案对一开始输入的正整数 $mod$ 取模。 数据规模：$1\le n\le10^{18}$，$1\le m\le10^5$，$1\le mod\le10^9$；$1\le l\le r\le n$，$1\le u\le v\le 10^{18}$。

题目描述

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

输入输出样例

输入样例 #1

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

输出样例 #1

0
5
3
3
3

输入样例 #2

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

输出样例 #2

2
0
0
1
0

说明

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.