002 - ログインログアウト記録の解析

あなたは大学でコンピュータ演習を担当している．大学のコンピュータシステ ムでは1日分のすべてのPCのログイン/ログアウト記録が一つのファイルに保存 されている．一人の学生は複数のPCを同時に使うことができるが，誰かがログ インして，まだログアウトしていないPCにログインすることはできない．

あなたはこのファイルを利用して特定の学生が特定の時間帯(おそらくは演習時 間)に少なくとも1台のPCを利用している時間の長さを計算するプログラムを作成する ことを頼まれた．

例えば，次のようなログイン/ログアウト記録があったとする．

• 12:55にPC1で学生1がログイン
• 13:00にPC4で学生2がログイン
• 13:10にPC2で学生1がログイン
• 13:20にPC2で学生1がログアウト
• 13:30にPC3で学生1がログイン
• 13:40にPC1で学生1がログアウト
• 13:45にPC3で学生1がログアウト
• 14:20にPC1で学生1がログイン
• 14:30にPC4で学生2がログアウト
• 14:40にPC1で学生1がログアウト

ここで，「13:00から14:30までの時間帯の，学生1の利用時間は」という質問が 与えられたときは，下の図のように13:00から13:45までの45分と14:20から 14:30までの10分の計55分と答える必要がある．

入力はいくつかのデータセットの並びである. 入力の終わりは，一つの空白で区切られた二つのゼロからなる行で示される. データセット数が10を超えることはない.

各データセットは次のような形式をしている．

N M 
r 
利用記録₁
...
利用記録_r 
q 
質問₁
...
質問_q 

最初の行のN とM はそれぞれPC数，学生数を表す．また，r は利用記録数，q は質問数を表す．これらは次の条件を満たす整数である.

1 ≤ N  ≤ 1000, 1 ≤ M  ≤ 10000, 2 ≤ r  ≤ 1000, 1 ≤ q  ≤ 50

利用記録の各行は次のようなスペース一つで区切られた四つの整数からなる．

t  n  m  s 

s は0か1である． s が1の時は，「時刻t にPCn で学生m がログインしたこと」を表す． s が0の時は，「時刻t にPCn で学生m がログアウトしたこと」を表す． 時刻はその日の0:00からの経過を分単位で表す． t ，n , m は，次の条件を満たす．

540 ≤ t  ≤ 1260, 1 ≤ n  ≤ N , 1 ≤ m  ≤ M 

利用記録については以下を仮定してよい．

記録は時刻の昇順に並んでいる．

同じPCの同じ時刻の記録が二つ以上現れることはない．

最初の記録以前や最後の記録以降にログインしているPCはない．

同じPCについてのログインとログアウトの記録は交互に現れ，各ログイン/ログアウトの組は同じ学生のものである．

質問の各行は次のようなスペース一つで区切られた三つの整数からなる．

t_s  t_e  m 

これは，「時刻t_s から時刻t_e までの時間帯の，学生m の利用時間は」という質問を表している． t_s , t_e , m は，次 の条件を満たす．

540 ≤ t_s  < t_e  ≤ 1260, 1 ≤ m  ≤ M 

質問ごとに，利用時間を分単位で表す十進数一つを含む1行を出力すること．出 力行には他のいかなる文字も含んではならない．

4 2
10
775 1 1 1
780 4 2 1
790 2 1 1
800 2 1 0
810 3 1 1
820 1 1 0
825 3 1 0
860 1 1 1
870 4 2 0
880 1 1 0
1
780 870 1
13 15
12
540 12 13 1
600 12 13 0
650 13 15 1
660 12 15 1
665 11 13 1
670 13 15 0
675 11 13 0
680 12 15 0
1000 11 14 1
1060 12 14 1
1060 11 14 0
1080 12 14 0
3
540 700 13
600 1000 15
1000 1200 11
1 1
2
600 1 1 1
700 1 1 0
5
540 600 1
550 650 1
610 620 1
650 750 1
700 800 1
0 0

55
70
30
0
0
50
10
50
0