SPOJ Brasil

Sortônia é a capital da província da Logônia do Norte. A cidade é definida com quase todas as suas ruas em uma grade quadrada alinhadas na direção Norte-Sul ou na direção Oeste-Leste. A única exceção é a Avenida Merge que vai na direção Sudoeste-Nordeste, dividindo os blocos da cidade ao longo de suas diagonais.

Sortônia é também uma das cidades mais verdes da Nlogônia. A universidade local desenvolveu uma tecnologia para aproveitar o campo magnético da Terra para geração de energia. Como consequência, todas as interseções da Avenida Merge possuem geradores de força instalados, abastecendo todas as casas e comércios da cidade.

A tecnologia foi elogiada pelos ambientalistas na época por ter eliminado a emissão de carbono da Sortônia, mas logo após sua introdução, milhares de abelhas e pássaros foram encontrados mortos na cidade. Confusa, a Rainha da Nlogônia ordenou os biofísicos do reino que investigassem o fenômeno.

Após muito meses de estudos, eles descobriram que os geradores usados pelos Sortonianos criaram anomalias no campo magnético local. Os pássaros e abelhas que usam o campo magnético da Terra para guiar seu voo foram confundidos por essas anomalias, começaram a voar em círulos e eventualmente morreram por exaustão.

De acordo com os modelos teóricos dos biofísicos, cada gerador cria uma anomalia que é representada por um valor inteiro. Cada anomalia propaga indefinidamente nas quatro direções cardeais. Pontos que não estão diretamente ao norte, sul, oeste ou leste do gerador não são afetados por ele. Por outro lado, se um ponto está alinhado com dois geradores então a anomalia naquele ponto é a soma das duas anomalias produzidas por esses geradores. Por exemplo, considere a figura abaixo que representa uma certa porção da Sortônia. A anomalia no ponto R é apenas aquela produzida pelo gerador naquele ponto enquanto a anomalia no ponto T é a soma das anomalia produzidas pelos geradores no ponto R e no ponto S.

Os biofísicos gostariam de medir as anomalias para algumas das interseções da cidade, mas essas medições requerem equipamentos caros e perícia técnica. Então eles planejam medir apenas um subconjunto das interseções da cidade e extrapolar os outros dados a partir deles. Prever uma anomalia a partir de um conjunto de medições pode requerer combinar várias delas de modos complicados. Então, a Rainha da Nlogônia ordenou que você escrevesse um programa que prevê as anomalias em certas interseções dadas as medidas préviamente feitas.

Entrada

Cada caso de teste é descrito usando várias linhas. A primeia linha contém cois inteiros M e Q representando respectivamente o número de medições e o número de consultas (1 ≤ M,Q ≤ 104). Cada uma das próximas M linhas descreve uma medição usando três inteiros X, Y e A, indicando que a anomalia medida no ponto (X, Y) é A (-107 ≤ X,Y ≤ 107 e -104 ≤ A ≤ 104). Após isso, cada uma das próximas Q linhas descreve uma consulta usando dois inteiros X' e Y', indicando que a anomalia no ponto (X',Y') deve ser prevista (-107 ≤ X',Y' ≤ 107). Todas as posições são medidas em blocos da cidade; o primeira coordenada aumenta de Oeste para Leste, enquanto a segunda coordenada aumenta de Sul para Norte. O ponto (0,0) está localizado na Avenida Merge. Você pode assumir que em cada caso de teste cada ponto não será medido mais de uma vez. Da mesma maneira, cada ponto não será consultado mais de uma vez. Você pode assumir que todas as medições são consistentes.

O último caso de teste é seguido por uma linha contendo dois zeros.

Saída

Para cada caso de teste imprima Q+1 linhas. Na i-ésima linha escreva a resposta para a i-ésima consulta. Se a informação dada pelas medições é suficiente para prever a anomalia no ponto consultado, então escreva um inteiro representando a anomalia no ponto consultado. Caso contrário escreva o caractere '*' (asterisco). Imprima uma linha contendo um único caractere '-' (hífen) após cada caso de teste.

Exemplo

Entrada

3 3 
30 -10 3 
30 20 15 
40 20 2 
-10 40 
40 -10 
-10 -10 
6 8 
0 1 11 
0 3 8 
1 0 11 
3 0 8 
4 4 0 
3 5 6 
1 5 
0 3 
3 0 
4 3 
0 2 
2 4 
4 4 
5 5 
0 0 

Saída

-10
-10
*
-
9
8
8
*
*
*
0
*
-