#1094. 2-03G. JM的无情铁手

菜的一批的JM先生最近研发出了一种对数组的新操作，他称为无情铁手，形式化的定义如下：

1. 设数组$A$长为$n$，元素分别为$a1,a2,a3,...an$
2. 如果$n=1$，则操作结束之后$A$不变
3. 如果$n>1$，则首先将$A$按下标的奇偶拆分成两个数组，即数组$A1:a1,a3,a5,...$, 数组$A2：a2,a4,a6,....$。然后分别对$A1$和$A2$执行无情铁手操作，再把$A2$接在$A1$的后面就是操作完成后的A。

现在JM先生有一个初始时长为$n$的数组$A$，元素为$1,2,3,4,...,n$。

JM先生有$q$个询问，他想知道对于$l,r,u,v$，执行一次无情铁手操作后的数组$A$，下标在$[l,r]$区间、值在$[u,v]$区间内的值的总和是多少。

因为结果可能太大，需要对一个给定的整数$m$取模。所有询问相互独立。

如果你能AC这道题目，你就会受到JM先生无情铁手的祝福，++节操。

输入第一行有三个整数n,q,m，分别表示数组长度，询问个数，模数。

之后有q行，每行4个整数l,r,u,v，表示需要统计的下标区间与值域区间。

输出$q$行，每行一个整数，表示该次询问的统计答案对$m$取模后的结果。

输入样例

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

输出样例

2
0
0
1
0

$1≤n≤1e18，1≤q≤1e5，1≤m≤1e9$

$1≤l≤r≤n，1≤u≤v≤1e18$