보리우카스

면접 대비

시간 제한2초메모리 제한1024 MB

요약

양말 종류와 세탁할 때마다 잃어버리는 양말 수가 주어질 때, 매번 같은 종류로 K짝을 이룬 세트가 몇 개 남는지 구합니다.

문제

다리가 $K$ 개인 거미 보리우카스는 항상 같은 종류의 양말 $K$ 개를 신습니다. 그는 세탁기로 양말을 빨며, 한 번의 세탁에는 한 종류의 양말만 넣습니다. 안타깝게도 세탁할 때마다 빤 양말 중 일부를 잃어버립니다.

각 세탁 후에 보리우카스가 가진 깨끗한 양말 세트의 수를 구하세요. 한 세트는 같은 종류의 양말 $K$ 개로 이루어집니다.

첫째 줄에 보리우카스가 가진 양말의 수 $N$ 과 거미의 다리 수 $K$ 가 주어집니다.

둘째 줄에 양말의 종류 $t_i$ $N$ 개가 공백으로 구분되어 주어집니다. $t_i$ 는 $i$ 번째 양말의 종류입니다.

셋째 줄에 세탁 횟수 $Q$ 가 주어집니다.

다음 $Q$ 개 줄에는 두 정수 $a_j$ 와 $b_j$ 가 주어집니다. 이는 $j$ 번째 세탁에서 거미가 종류 $a_j$ 의 양말을 빨았고, 양말 $b_j$ 개를 잃어버렸다는 뜻입니다.

$Q$ 개의 줄을 출력합니다. $k$ 번째 줄에는 $k$ 번째 세탁 후 보리우카스가 가진 같은 종류의 양말 $K$ 개 세트의 수 $c_k$ 를 출력합니다 ( $1 \le k \le Q$ ).