#P10861. 球

    ID: 10003 传统题 5000ms 512MiB 尝试: 3 已通过: 1 难度: 6 上传者: 标签>组合数学CF1900数学前缀和模运算排序线段树模拟

球

球(qiu)

题目描述

小 P 初始在原点 (0,0)(0,0),面朝 yy 轴正方向。他依次放置 101010010^{10^{100}} 个球,第 ii 个球的重量为 imiim^i。

第 ii 步,先在当前位置放下第 ii 个球;如果右侧相邻整点尚未放球,就向右转,然后向前走一个单位。前 25 个球的编号分布如下,11 位于原点,上方为 yy 轴正方向:

21 22 23 24 25
20  7  8  9 10
19  6  1  2 11
18  5  4  3 12
17 16 15 14 13

回答 qq 次询问:求横坐标在 [x1,x2][x_1,x_2]、纵坐标在 [y1,y2][y_1,y_2] 的所有整点上,球的重量之和,对 2642^{64} 取模。

输入格式

第一行两个整数 m,qm,q。

接下来 qq 行,每行四个整数 x1,x2,y1,y2x_1,x_2,y_1,y_2。

输出格式

每个询问输出一行非负整数表示答案。

样例 1 输入

1 1
0 0 0 1

样例 1 输出

9

样例说明

所求的两个球编号为 1、8,m=1m=1 时重量和为 1+8=91+8=9。

数据范围

令 WW 为不小于所有询问坐标的最小正整数,保证所有坐标非负。

W≤1018W\le10^{18},x1≤x2x_1\le x_2,y1≤y2y_1\le y_2,0≤m<2640\le m<2^{64},q≤106q\le10^6。

子任务 分值 附加限制
1 W≤104W\le10^4
2 W≤107W\le10^7
3 W≤109W\le10^9
4 W≤1012W\le10^{12}
5 m=1m=1
6 q=1q=1
7 79 W≤1018W\le10^{18}