로그인/로그아웃 기록 분석

어느 대학의 컴퓨터 실습 강좌에서는 하루 동안 모든 PC의 로그인/로그아웃 기록을 파일에 저장한다. 한 학생이 동시에 두 대 이상의 PC를 사용할 수도 있지만, 아직 로그아웃하지 않은 사람이 로그인해 둔 PC에는 다른 사람이 로그인할 수 없다.

주어진 시간 구간(예: 실습 수업 시간) 동안, 한 학생이 적어도 한 대 이상의 PC를 사용하고 있던 총 시간을 기록으로부터 계산하는 프로그램을 작성하여라.

다음은 로그인/로그아웃 기록의 한 예시이다.

• 학생 1이 12:55에 PC 1에 로그인
• 학생 2가 13:00에 PC 4에 로그인
• 학생 1이 13:10에 PC 2에 로그인
• 학생 1이 13:20에 PC 2에서 로그아웃
• 학생 1이 13:30에 PC 3에 로그인
• 학생 1이 13:40에 PC 1에서 로그아웃
• 학생 1이 13:45에 PC 3에서 로그아웃
• 학생 1이 14:20에 PC 1에 로그인
• 학생 2가 14:30에 PC 4에서 로그아웃
• 학생 1이 14:40에 PC 1에서 로그아웃

"13:00부터 14:30 사이에 학생 1이 사용한 시간을 구하라"라는 질의에 대해서는 "55분"을 출력해야 한다. 이는 13:00부터 13:45까지의 45분과 14:20부터 14:30까지의 10분을 더한 값이다.

입력은 여러 개의 데이터셋으로 이루어진다. 입력의 끝은 공백으로 구분된 두 개의 0(0 0)만 있는 줄로 나타낸다. 데이터셋의 개수는 10을 넘지 않는다.

각 데이터셋의 형식은 다음과 같다.

N M
r
record1
...
recordr
q
query1
...
queryq

첫 줄의 $N$과 $M$은 각각 PC의 수와 학생의 수이다. $r$은 기록의 수, $q$는 질의의 수이다. 이 네 정수는 다음을 만족한다.

• $1 \le N \le 1000$, $1 \le M \le 10000$, $2 \le r \le 1000$, $1 \le q \le 50$

각 기록은 공백으로 구분된 네 정수 $t\ n\ m\ s$ 로 이루어진다.

$s$는 0 또는 1이다. $s$가 1이면 학생 $m$이 시각 $t$에 PC $n$에 로그인했음을, $s$가 0이면 학생 $m$이 시각 $t$에 PC $n$에서 로그아웃했음을 뜻한다. 시각은 그날 0시 0분부터 경과한 분(minute)으로 표현된다. $t$, $n$, $m$은 다음을 만족한다.

• $540 \le t \le 1260$, $1 \le n \le N$, $1 \le m \le M$

기록에 대해 다음을 가정할 수 있다.

• 기록은 시각 $t$의 오름차순으로 저장되어 있다.
• 같은 PC에 대해 시각 $t$가 같은 기록은 존재하지 않는다.
• 파일의 첫 기록 이전이나 마지막 기록 이후에는 로그인 상태인 PC가 없다.
• 한 PC에 대한 로그인과 로그아웃 기록은 번갈아 나타나며, 각 로그인-로그아웃 쌍은 같은 학생에 대한 것이다.

각 질의는 공백으로 구분된 세 정수 $t_s\ t_e\ m$ 으로 이루어진다.

이는 "$t_s$부터 $t_e$ 사이에 학생 $m$이 사용한 시간"을 뜻한다. $t_s$, $t_e$, $m$은 다음을 만족한다.

• $540 \le t_s < t_e \le 1260$, $1 \le m \le M$

각 질의에 대해, 사용 시간(분)을 나타내는 10진 정수 하나를 한 줄에 출력한다. 출력 줄에는 이 숫자 외의 다른 문자가 있어서는 안 된다.