Voriukas

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

요약

양말 종류별 개수를 관리하면서 세탁할 때마다 잃어버린 수를 빼고, 각 세탁 후 K개로 이루어진 동일 종류 양말 세트가 몇 개인지 출력한다.

난이도: 보통10점 중 4점
유형: 해시맵, 배열, 시뮬레이션
정답자: 아직 제출이 없습니다

문제

$K$ -kojis voriukas visada dėvi $K$ vienodos rūšies kojinių. Kojines voriukas skalbia skalbimo mašinoje ir vienu skalbimu jis skalbia tik vienos rūšies kojines. Deja, po kiekvieno skalbimo, jis pameta dalį skalbtų kojinių.

Padėkite voriukui suskaičiuoti, kiek švarių kojinių komplektų (vieną komplektą sudaro $K$ tos pačios rūšies kojinių) jis turės po kiekvieno skalbimo.

입력

Pirmojoje eilutėje pateikti du sveikieji skaičiai: turimų kojinių skaičius $N$ ir voriuko kojų skaičius $K$ .

Antrojoje eilutėje pateikti $N$ tarpu atskirtų sveikųjų skaičių $t\_i$ , nusakančių kiekvienos kojinės rūšį. Skaičius $t\_i$ reiškia, kad atitinkama kojinė yra $t\_i$ rūšies.

Trečiojoje eilutėje pateikiamas sveikasis skaičius $Q$ – plovimų skaičius.

Likusiose $Q$ eilučių pateikiama po du tarpu atskirtus sveikuosius skaičius $a\_j$ ir $b\_j$ . Šie skaičiai nurodo, kad $j$ -ojo skalbimo metu, voriukas skalbė $a\_j$ rūšies kojines ir pametė $b\_j$ kojinių.

출력

Išveskite $Q$ eilučių. Kiekvienoje jų turi būti sveikasis skaičius $c\_k$ – kiek kojinių komplektų iš $K$ vienodos rūšies kojinių turi voriukas po $k$ -ojo skalbimo ( $1 ≤ k ≤ Q$ ).

제한

$1 ≤ N, K, Q ≤ 1\\,000\\,000$
$1 ≤ t\_i ≤ 10\\,000\\,000$ ( $1 ≤ i ≤ N$ )
$1 ≤ a\_j ≤ 10\\,000\\,000$ ( $1 ≤ j ≤ Q$ )
$1 ≤ b\_j ≤ 1\\,000\\,000$ ( $1 ≤ j ≤ Q$ )
Pateikiamos užklausos garantuoja, kad jokios rūšies kojinių skaičius niekada nebus neigiamas.

예제1

예제 1
입력
```
7 2
1 3 1 3 3 3 3
3
3 1
1 2
3 1
```
예상 출력
```
3
2
1
```