该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

还没集够的 Displace_ 不得不回班补 whk了。

在一天的数学周测中，Displace_ 喜提前面挂分挂完，但是最后的附加题爆切。

评卷时，全班带上老师竟然都是用 whk 的"看上去很对的贪心"来证明的，令人唏嘘。

Displace_ 选手进行一波 all in，他直接冲刺，上讲台把[数据删除]角度的证明过程写出来，但是喜提没人听懂。

Displace_ 很难过，于是他逃出班里，来机房出了这道题，请你给他带来喜悦。

题目描述

定义一对互不相同正整数是 kuhu 的，当且仅当这对整数加起来是 2 的非负整数次幂，比如 2+6 就是 kuhu 的，而 4+8 就不是。

现在给你一个限制 $l,r$，请你求出最多能选出来多少个数组成一个集合 ${a}$，满足以下条件：

1.$l\leq a_i\leq r$

2.任意一对整数都不是 kuhu 的。

Displace_ 是毒瘤的，于是他要求你完成 $m$ 组询问。

Displace_ 是无聊的，所以对于一些数据，你需要额外求出对于所有的 $1\leq l\leq r\leq n$，所有答案的和。

输入格式

第一行三个整数 $n,m,num$，表示 $r$ 的上界、询问的次数和额外输出的参数。

接下来 $m$ 行，每行两个整数 $l, r$。

输出格式

先输出 $m$ 行，每行一个整数表示这次询问的答案。

再输出一行一个整数表示所有答案的和与 $num$ 的乘积。

样例输入

20 3 1
1 20
10 20
1 10

样例输出

12
7
7
1106

数据范围与时空限制

1s，512MB

对于所有测试点，保证 $n, m\leq 3e5$，$num\in{0,1}$，$l\leq r\leq n$。

测试点编号	$n\leq$	$m\leq$	$num$	特殊性质
1	20	3	0	/
2
3	500
4
5			1
6
7	300000		0	A
8
9
10	2000			/
11			1
12	20000		0
13			1
14	100000		0
15
16			1
17
18	300000		0
19			1
20

特殊性质A：保证所有询问都有 $l=1$。