dwangoプログラミングコンテスト

E - 電波局


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題文

ある星には正三角形の形状をした街があり、この街は N × (N + 1) / 2 個の家が正三角形状に並んでいます。この正三角形は、ある辺が東西方向に平行で、その辺を構成しない頂点が最も北にある家となるような形状をしています。

各家は 2 つの整数を用いて番号が付けられています。最も北にある家を (1,1) とし、北の端から i 行目の西から j (1 ≦ j ≦ i ≦ N) 番目の家には (i,j) という番号が付けられています。

以下に N = 5 の例を示します。

(1,1)
(2,1)(2,2)
(3,1)(3,2)(3,3)
(4,1)(4,2)(4,3)(4,4)
(5,1)(5,2)(5,3)(5,4)(5,5)

dwango 社は M 個の電波局 (1 から M まで番号が付けられているとします) を持っており、それぞれの電波局はある正三角形状の範囲 (各辺は街の外周部の辺と平行である) にデジタルコンテンツを配信しています。

電波局 i (1 ≦ i ≦ M) には 3 つの整数 a_i,b_i,c_i が定められており、1 ≦ k ≦ j ≦ c_i を満たすすべての整数 j,k に対して、家 (a_i+j-1,b_i+k-1) に配信しています。

dwango 社は新たに 1 つ電波局を設置して、新たな顧客を呼び込もうと考えています。

電波局の設置の方法は Q 通り発案されています。各設置方法に対して新たに獲得できる顧客の人数を求めるプログラムを作成してください。


入力

入力は以下の形式で標準入力から与えられる。

N M
a_1 b_1 c_1
a_2 b_2 c_2
:
a_M b_M c_M
Q
d_1 e_1 f_1
d_2 e_2 f_2
:
d_Q e_Q f_Q
  • 1 行目には、2 つの整数 N (1 ≦ N ≦ 1,000,000,000),M (1 ≦ M ≦ 1,000) が空白区切りで与えられる。
  • 2 行目から M 行には、既に設置されている電波局に関する情報が与えられる。M 行のうち i (1 ≦ i ≦ M) 行目には電波局 i が配信する範囲を表す 3 つの整数 a_i,b_i (1 ≦ b_i ≦ a_i ≦ N),c_i (1 ≦ c_i ≦ N-a_i+1) が与えられる。これは電波局 i が、1 ≦ k ≦ j ≦ c_i を満たすすべての整数 j,k に対して、家 (a_i+j-1,b_i+k-1) に配信していることを表す。
  • M + 2 行目には、整数 Q (1 ≦ Q ≦ 1,000) が与えられる。
  • M + 3 行目から Q 行には、新たな設置方法に関する情報が与えられる。Q 行のうち i (1 ≦ i ≦ Q) 行目には、i 番目の設置方法において新たに設置する電波局が配信する範囲を表す 3 つの整数 d_i,e_i (1 ≦ e_i ≦ d_i ≦ N),f_i (1 ≦ f_i ≦ N-d_i+1) が与えられる。これは新たに設置する電波局が、1 ≦ k ≦ j ≦ f_i を満たすすべての整数 j,k に対して、家 (d_i+j-1,e_i+k-1) に配信予定であることを表す。

部分点

この問題には部分点が設定されています。

  • N ≦ 200 および M ≦ 200 および Q ≦ 200 を満たすデータセット 1 にすべて正解すると、10 点が得られます。
  • M ≦ 200 および Q ≦ 200 を満たすデータセット 2 にすべて正解すると、上記に加えてさらに 30 点が得られます。
  • 追加制約のないデータセット 3 にすべて正解すると、上記に 2 つに加えてさらに 60 点が得られ、全体で 100 点が得られます。

出力

出力は Q 行からなる。Q 行のうち i (1 ≦ i ≦ Q) 行目には、i 番目の設置方法において新たに配信される家の個数を出力せよ。


入力例1

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

出力例1

5
2

既に設置されている 3 つの電波局によって配信されている家の範囲は、下図のようになっています (○は配信されていることを、×は配信されいないことを表します)。

×
×
×
×
×
×××
××
×××××

1 つ目の設置方法の場合、新たに配信される家は下図の+で示す 5 個です。

×
×
×
+
+
++×
+×
×××××

2 つ目の設置方法の場合、新たに配信される家は下図の+で示す 2 個です。

×
×
×
×
×
×××
××
××++×

入力例2

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

出力例2

1
0
2

Submit提出する