← 返回题目列表

Codeforces · 117/D

D. 转型不快

中文机器翻译题面 查看原题

设 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]