32992번 - 나는 애니메이션에 열정적인 사람이 아니야

문제

『블루로 똑떨한 내가 이세계에서는 레전더리 그랜드 마스터?』, 『내가 계산 기하를 사랑할 리가 없잖아』, 『러브레터를 128비트 이하로 보내는 방법』, 『너의 볼록껍질을 먹고 싶어』, 『이웃집 홍성현』

엘투는 은밀한 애니 취향을 가지고, 남들 몰래 여러 애니들을 시청하고 있었다.

그런 수상한 낌새를 눈치챈 친구들이 엘투의 요상한 취향에 대해 힐문하자, 엘투는 자신은 애니메이션에 열정적인 사람이 아니라면서 친구들로부터 받는 애니메이션에 열정적인 사람으로의 의심을 떨쳐 버리려고 하였다. 이를 위해 엘투는 다음과 같이 주장하였다.

"만약 우리 중에 $C$명 이상이 어떤 애니를 시청했다면, 그 애니는 웰노운(Well-known)이다."

엘투는 자신이 시청한 $M$개의 애니들이 모두 웰노운이었다는 사실을 증명함으로써 자신은 애니메이션에 열정적인 사람이 아님을 밝히고자 하였다. 이 주장을 강화하기 위해, 엘투는 애니 만화 사이트를 해킹하여, 자신의 친구들 $K$명의 시청 기록을 조사하였다. 그 결과, 엘투는 '어느 날에 어떤 친구가 $L$번째부터 $R$번째까지의 애니를 시청했다'라는 정보 목록을 모두 수집할 수 있었다.

어떤 애니메이션에 열정적인 친구들은 이미 시청했던 애니를 복습하기 위해서 다시 시청하기도 한다.

모든 상황을 고려했을 때, 1ドル$일차부터 $N$일차까지 모든 날에 대하여 웰노운 애니의 개수를 출력하는 프로그램을 작성하자. 이로써 엘투는 자신을 변호할 수 있을 것이다.

입력

첫 번째 줄에 다섯 개의 정수 $N,ドル $M,ドル $K,ドル $C,ドル $Q$가 공백으로 구분되어 주어진다. $N$은 엘투가 조사한 애니 시청 목록의 일수, $M$은 주어진 애니메이션의 수, $K$는 엘투의 친구들의 수, $C$는 웰노운 애니의 기준이 되는 시청자의 수, $Q$는 애니 시청 기록 정보의 개수이다.

그 다음 줄부터 $Q$개의 줄에 걸쳐서 애니 시청 기록에 대한 정보가 주어진다. 각 줄에는 네 정수 $D,ドル $P,ドル $L,ドル $R$이 공백으로 구분되어 주어진다. 이는 $D$번째 일차에 엘투의 $P$번째 친구가 $L, L+1, \cdots, R$번째 애니를 시청했다는 뜻이다.

출력

$N$개의 줄에 걸쳐서 주어진 문제의 답을 출력한다. 그중 $i$번째 줄에는 1ドル$일차부터 $i$일차까지 친구들의 시청 기록을 고려했을 때 웰노운 애니의 개수를 출력한다.

제한

• 1ドル \leq N, M, K, Q \leq 500,000円$
• 1ドル \leq D \leq N$
• 1ドル \leq L \leq R \leq M$
• 1ドル \leq C, P \leq K$

노트

실제로 엘투는 애니메이션에 열정적인 사람이다.