#dwango2015prelims5. [dwango2015_prelims_5]電波局

[dwango2015_prelims_5]電波局

问题说明

有一个星球上有一个以正三角形形状排列的城市,该城市中有 N×(N+1)/2N × (N + 1) / 2 个房屋。这个正三角形的特点是:其中一条边平行于东西方向,并且不构成该边的顶点位于最北边的房屋。

每个房屋都用两个整数进行编号。最北边的房屋编号为 (11,11),第 ii 行从西到东数第 jj 个(1jiN1 ≦ j ≦ i ≦ N)房屋的编号为 (ii,jj)。

以下是 N=5N = 5 的例子:

(1,

(2,

(2,

(3,

(3,

(3,

(4,

(4,

(4,

(4,

(5,

(5,

(5,

(5,

(5,

Dwango 公司拥有 MM 个无线电台(编号从 11MM),每个无线电台都向一个正三角形区域(每条边与城市外围的边平行)提供数字内容。

无线电台 i(1iM)i (1 ≦ i ≦ M)33 个整数 aia_ibib_icic_i ,并且向满足 1kjci1 ≦ k ≦ j ≦ c_i 的所有整数 jjkk 发送信号,将数字内容配送给房屋 (ai+j1a_i+j-1,bi+k1b_i+k-1)。

Dwango 公司计划新建一座电视台,以吸引更多的客户。

QQ 种设立电视台的方法。请编写一个程序,对于每种设立方法,计算能够获得的新客户数量。

输入

输入是标准输入,格式如下:

NN MM a1a_1 b1b_1 c1c_1 a2a_2 b2b_2 c2c_2aMa_M bMb_M cMc_M QQ d1d_1 e1e_1 f1f_1 d2d_2 e2e_2 f2f_2dQd_Q eQe_Q fQf_Q

  • 11 行包含两个整数 N(1N1,000,000,000)N (1 ≦ N ≦ 1,000,000,000)M(1M1,000)M (1 ≦ M ≦ 1,000),用空格分隔。
  • 22 行到第 MM 行提供了已经设立的无线电台的信息。其中第 ii 行提供了无线电台 ii 发出信号的范围,由 33 个整数 aia_ibi(1biaiN)b_i (1 ≦ b_i ≦ a_i ≦ N)ci(1ciNai+1)c_i (1 ≦ c_i ≦ N-a_i+1) 组成。这表示无线电台 ii 向满足 1kjci1 ≦ k ≦ j ≦ c_i 的所有整数 jjkk 发送信号,将数字内容配送给房屋 (ai+j1a_i+j-1,bi+k1b_i+k-1)。
  • M+2M+2 行包含一个整数 Q(1Q1,000)Q (1 ≦ Q ≦ 1,000)
  • M+3M+3 行到第 M+Q+2M+Q+2 行提供了关于新设立方法的信息。其中第 ii 行描述了第 ii 种设立方法中将要设立的无线电台发出信号的范围,由 33 个整数 did_iei(1eidiN)e_i (1 ≦ e_i ≦ d_i ≦ N)fi(1fiNdi+1)f_i (1 ≦ f_i ≦ N-d_i+1) 组成。这表示新设立的无线电台将向满足 1kjfi1 ≦ k ≦ j ≦ f_i 的所有整数 jjkk 发送信号,计划将数字内容传递给房屋 (di+j1d_i+j-1,ei+k1e_i+k-1)。

部分得分

本问题设有部分分。

  • 当满足 N200N ≦ 200M200M ≦ 200Q200Q ≦ 200 的数据集 11 的所有测试用例均正确时,可获得 1010 分。
  • 当满足 M200M ≦ 200Q200Q ≦ 200 的数据集 22 的所有测试用例均正确时,除上述分数外,还可额外获得 3030 分。
  • 当满足没有额外限制的数据集 33 的所有测试用例均正确时,除上述分数外,还可额外获得 6060 分。在所有数据集上均正确将获得总共 100100 分。

输出

输出包含 QQ 行。第 ii 行(1iQ1 ≦ i ≦ Q)为第 ii 种设立方法中所能覆盖的新房屋数量。

示例1


8 3
2 2 4
5 4 3
6 1 3
2
4 1 4
7 6 2

示例1输出


5
2

由已经建立的 33 个无线电台发送的信号覆盖的房屋范围如下图所示 (○表示被覆盖,×表示未被覆盖)。

×

×

×

×

×

×

×

×

×

×

×

×

×

×

×

第一种设立方法下,新增覆盖的房屋如下图中的+所示,共 55 个。

×

×

×

×

×

×

×

×

×

×

第二种设立方法下,新增覆盖的房屋如下图中的+所示,共 22 个。

×

×

×

×

×

×

×

×

×

×

×

×

×

示例2


3 2
1 1 2
3 2 1
3
2 1 2
2 2 1
1 1 3

示例2输出


1
0
2