设 a 为由 n 个数字组成的数组。数组的元素编号为 1 到 n,even 是由 a 中的偶数数字组成的数组 (eveni = a2i, 1 ≤ 2i ≤ n),odd 是由 а 中的奇数数字组成的数组 (oddi = a2i - 1, 1 ≤ 2i - 1 ≤ n)。然后我们按以下方式定义数组 F(a) 的变换:
- 如果 n > 1,F(a) = F(odd) + F(even),其中操作“ + ”代表数组的串联(连接在一起)
- 如果 n = 1,F(a) = a
设 a 为由 n 个数字 1、2、3、...、n 组成的数组。那么 b 就是对数组 a 应用变换的结果(因此 b = F(a))。您将获得 m 个查询(l、r、u、v)。您的任务是为每个查询找到数字 bi 的总和,使得 l ≤ i ≤ r 且 u ≤ bi ≤ v。您应该打印对 mod 取模的查询结果。
输入
第一行包含三个整数 n, m, mod (1 ≤ n ≤ 1018, 1 ≤ m ≤ 105, 1 ≤ mod ≤ 109)。接下来的 m 行描述查询。每个查询由四个整数 l、r、u、v 定义(1 ≤ l ≤ r ≤ n,1 ≤ u ≤ v ≤ 1018)。
请不要使用 %lld 说明符在 C++ 中读取或写入 64 位整数。使用 %I64d 说明符。
输出
打印 m 行,每行包含一个整数 — 查询结果的余数模模。
示例
输入 #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
注意
让我们考虑第一个例子。首先我们构造一个数组 b = F(a) = F([1, 2, 3, 4])。
- 步骤 1. F([1, 2, 3, 4]) = F([1, 3]) + F([2, 4])
- 步骤 2. F([1, 3]) = F([1]) + F([3]) = [1] + [3] = [1, 3]
- 步骤 3. F([2, 4]) = F([2]) + F([4]) = [2] + [4] = [2, 4]
- 步骤 4。 b = F([1, 2, 3, 4]) = F([1, 3]) + F([2 , 4]) = [1, 3] + [2, 4] = [1, 3, 2, 4]