Voriukas

$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.