inspiratie

Orașul Pitești este reprezentat în plan unde punctul $(0, 0)$ este restaurantul Ottoman (informație relevantă doar în scop turistic). Comisia științifică de la ONI 2026 este formată din $N$ membri, iar pentru fiecare membru $k$ primim un triplet de forma $(x_k, y_k, v_k)$, reprezentând faptul că membrul $k$ se află la punctul de coordonate $(x_k, y_k)$ și are o valoare $v_k$ (valoare cu care te naști).

Membrii comisiei sunt lipsiți de ocupație și vor să inspire orice concurent care se află în proximitatea lor. Orice concurent care se află la distanță Manhattan $D$ de membrul $k$ din comisie (cu $D < v_k$) este inspirat de către acesta, primind astfel $v_k - D$ unități de talent. Dacă un concurent se află în aria de inspirație a mai multor membri din comisie, acesta o să acumuleze toate unitățile de talent de la fiecare astfel de membru prin adunarea acestora.

La ONI 2026 participă $Q$ concurenți, iar pentru fiecare concurent se știe coordonata $(x, y)$ în care acesta a decis să se plaseze.

Cerință

Pentru fiecare concurent, să se afle cantitatea totală de talent pe care a primit-o de la toți membrii comisiei.

Date de intrare

Fișierul de intrare inspiratie.in conține pe prima linie numerele $N$, $Q$, separate prin câte un spațiu. Pe următoarele $N$ linii se vor afla câte trei numere: $x_i$, $y_i$ și $v_i$, reprezentând coordonatele la care se afla membrul din comisie $i$ și valoarea lui $v_i$. Pe următoarele $Q$ linii se vor afla câte două numere: $x_i$ și $y_i$, reprezentând coordonatele la care se plasează concurentul $i$.

Date de ieșire

Fișierul de ieșire inspiratie.out va conține pe o singură linie $Q$ numere naturale, separate prin câte un spațiu. Al $i$-lea număr reprezintă cantitatea de talent pe care concurentul $i$ o primește.

Restricții și precizări

• $1 \leq N, Q \leq 100 \ 000$;
• $1 \leq x_i, y_i \leq 10^8$;
• $1 \leq v_i \leq 10^8$;
• Distanța Manhattan dintre două puncte $(x_1, y_1)$ și $(x_2, y_2)$ este $|x_1 - x_2| + |y_1 - y_2|$.

Exemplu

inspiratie.in

2 2
3 3 3
5 4 2
3 4
4 4

inspiratie.out

2 2

Explicație

Avem $N = 2$ membri de comisie și $Q = 2$ concurenți. Primul membru de comisie se află la punctul de coordonate $(3, 3)$ cu valoarea $3$, iar al doilea la punctul de coordonate $(5, 4)$ cu valoarea $2$.

• Primul concurent este la punctul $(3, 4)$. Distanța față de primul membru de comisie: $|3 - 3| + |4 - 3| = 1 < 3 \Rightarrow$ talent $3 - 1 = 2$. Distanța față de al doilea membru de comisie: $|3 - 5| + |4 - 4| = 2 \not< 2 \Rightarrow$ talent $0$. Talent total: $2$.
• Al doilea concurent este la $(4, 4)$. Distanța față de primul membru de comisie: $|4 - 3| + |4 - 3| = 2 < 3 \Rightarrow$ talent $3 - 2 = 1$. Distanța față de al doilea membru de comisie: $|4 - 5| + |4 - 4| = 1 < 2 \Rightarrow$ talent $2 - 1 = 1$. Talent total: $1 + 1 = 2$.