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

엘투는 남들 몰래 여러 애니를 보고 있었다.

그런 낌새를 눈치챈 친구들이 엘투의 특이한 취향을 캐묻자, 엘투는 자신이 애니메이션에 열정적인 사람이 아니라고 주장하며 의심을 떨쳐 내려 하였다. 이를 위해 엘투는 다음과 같이 주장하였다.

"만약 우리 중에 $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$

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