30081번 - Voriukas 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 34 | 20 | 17 | 54.839% |
문제
$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
7 2 1 3 1 3 3 3 3 3 3 1 1 2 3 1
예제 출력 1
3 2 1
Voriukas turi $7$ kojines ir $2$ kojas.
- Po pirmojo skalbimo voriukui lieka $2$ pirmos rūšies ir $4$ trečios rūšies kojinės. Iš jų susidaro $3$ kojinių komplektai.
- Po antrojo skalbimo lieka $4$ trečios rūšies kojinės iš kurių susidaro $2$ komplektai.
- Po trečio skalbimo lieka tik $3$ trečios rūšies kojinės ir iš jų galima sudaryti tik $1$ komplektą.