Rezolvare PBinfo #3394

În grădina lui Cosmin se află un măr cu număr nelimitat de mere. Cei N prieteni ai lui Cosmin, numerotați de la 1 la N, vor culege mere timp de T zile, după următoarea regulă:
În dimineața zilei Ti, prietenii lui Cosmin vor forma o coadă la intrarea în grădina, începând cu prietenul Xi. Așadar, coada va arăta sub forma Xi, Xi+1, …, XN, X1, …, Xi-1. În acea zi se vor culege Yi mere. Fiecare prieten Xi va intra în grădină, va culege un măr și se va întoarce în coadă.
În ziua T + 1, Cosmin alege aleatoriu K prieteni (Q1, …, Qk) și dorește să afle câte mere a cules fiecare.

Cerința

Scrieţi un program care să găsească numărul de mere culese de fiecare dintre cei K prieteni selectați de Cosmin.

Date de intrare

Fișierul de intrare mere.in conține:
- Pe prima linie, N T K, trei numere întregi reprezentând numărul de prieteni, numărul de zile în care se vor culege mere și numărul de întrebări ale lui Cosmin.
- Pe următoarele T linii, câte două numere întregi, separate printr-un spațiu, Xi și Yi, reprezentând indicele prietenul ce va intra primul în grădina, respectiv numărul de mere ce vor fi culese în ziua Ti.
- Pe ultima linie, K numere întregi, Qi, reprezentând indicii prietenilor lui Cosmin, pentru care se dorește aflarea numărului de mere culese.

Date de ieșire

Fișierul de ieșire mere.out va conţine K numere întregi, pe o singură linie, separate printr-un spațiu, reprezentând răspunsurile la cele K întrebări.

Restricții și precizări

• 1 ≤ Xi ≤ N ≤ 10.000.000
• 1 ≤ T ≤ 200.000
• 1 ≤ K ≤ 100.000
• 1 ≤ Yi ≤ 1.000.000
• Pentru teste în valoare de 30 puncte: 1 ≤ Xi ≤ N ≤ 100, 1 ≤ T ≤ 100, 1 ≤ K ≤ 100, 1 ≤ Yi ≤ 1.000
• Pentru teste în valoare de 50 puncte: 1 ≤ Xi ≤ N ≤ 200.000, 1 ≤ T ≤ 10.000, 1 ≤ K ≤ 10.000
• Pentru teste în valoare de 70 puncte: 1 ≤ Xi ≤ N ≤ 1.000.000, 1 ≤ T ≤ 100.000

Exemplu:

mere.in

5 3 4
1 2
3 5
2 7
2 4 1 2

mere.out

4 2 3 4

Explicație

5 persoane vor culege mere timp de 3 zile, astfel:
În prima zi, vor culege 2 mere persoanele cu indicii 1 și 2
În a doua zi, vor culege 5 mere persoanele cu indicii 3, 4, 5, 1 și 2
În a treia zi, vor culege 7 mere persoanele cu indicii 2, 3, 4, 5, 1, 2, 3.
Așadar, numărul de mere culese de fiecare persoană de la 1 la N este: 1 -> 3, 2 -> 4, 3 -> 3, 4 -> 2, 5 -> 2.