25961번 - 스코어보드 보기 귀찮아

2022년 올해도 어김없이 APC가 열렸다. $N$명이 참가하였고 그중 상위 $S$명에게만 상을 준다. 이번 APC에 참가한 지수는 $1$등까진 욕심이 없지만 수상만큼은 꼭 하고 싶어 한다.

꽤나 진지하게 참가한 지수는 중간중간 스코어보드를 보는 시간조차 아깝게 느껴진다. 지수는 그저 자신의 현재 순위와 수상권에 들기 위해서는 몇 문제만 더 풀면 되는지만 알면 된다.

실시간으로 대회 참가자들이 문제를 풀 때마다 참가자 정보가 들어온다고 할 때 지수의 현재 순위와 몇 문제만 더 풀면 수상권에 들 수 있는지 출력해 주자.

순위 기준은 다음과 같다.

1. 푼 문제 수가 더 많은 참가자
2. 푼 문제 수가 같은 경우에는 마지막으로 문제를 푼 시각이 더 빠른 참가자

한 문제도 풀지 않은 참가자는 모두 순위가 $N$등이다.

첫 번째 줄에 $N$과 $S$가 공백으로 구분되어 주어진다. ($1 \le N \le 500\,000$, $1 \le S \le N$)

두 번째 줄에 정보의 개수 $Q$가 주어진다. ($1 \le Q \le 500\,000$)

세 번째 줄부터 $Q$개의 줄에 걸쳐 새로 문제를 푼 참가자의 번호가 주어진다. 각 참가자의 번호는 $1$ 이상 $N$ 이하이고, 지수는 $1$번이다.

$Q$개의 줄에 걸쳐 각 정보가 주어질 때마다 현재 순위와 몇 문제를 풀어야 수상권에 드는지에 대한 정보를 공백으로 구분하여 출력하시오.