Electrical Pollution

Sortonia is the capital of the North Nlogonia province. The city is laid out with almost all of its streets in a square grid, aligned to either the North-South or the West-East direction. The only exception is Merge Avenue, which runs Southwest-Northeast, splitting city blocks along their diagonals.

Sortonia is also one of the greenest cities in Nlogonia. The local university developed technology to harness the magnetic field of Earth for energy generation. As a consequence, all intersections of Merge Avenue have power generators installed, supplying all the homes and businesses of the city.

This technology was praised by environmentalists at the time for eliminating Sortonia’s carbon footprint, but soon after its introduction, thousands of bees and birds were found dead in the city. Puzzled, the Queen of Nlogonia ordered the queendom’s biophysicists to investigate the phenomenon.

After many months of study, they discovered that the generators used by Sortonians created anomalies in the local magnetic field. The birds and bees that use the Earth’s magnetic field to guide their flight were confused by these anomalies, started flying in circles and eventually died of exhaustion.

According to the biophysicists’ theoretical models, each generator creates an anomaly that is represented as an integer value. Each anomaly propagates indefinitely in all four compass directions. Points that are not directly north, south, west or east of the generator are unaffected by it. On the other hand, if a point is aligned with two generators then the anomaly at that point is the sum of the two anomalies produced by those generators. As an example, consider the picture below that represents a certain portion of Sortonia. The anomaly at point R is just the one produced by the generator at that point, while the anomaly at point T is the sum of the anomalies produced by the generator at point R and the generator at point S.

The biophysicists would like to measure the anomalies for some city intersections, but these measurements require expensive equipment and technical expertise. So they plan to measure only a subset of the city’s intersections and extrapolate other data from them. Predicting an anomaly from a set of measurements might require combining several of them in complicated ways. Thus, the Queen ordered you to write a program that predicts the anomalies at certain intersections, given the measurements previously made.

Each test case is described using several lines. The first line contains two integers M and Q representing respectively the number of measurements and the number of queries (1 ≤ M,Q ≤ 104). Each of the next M lines describes a measurement using three integers X, Y and A, indicating that the measured anomaly at point (X, Y) is A (−107 ≤ X, Y ≤ 107 and −104 ≤ A ≤ 104). After that, each of the next Q lines describes a query using two integers X' and Y', indicating that the anomaly at point (X', Y') must be predicted (−107 ≤ X', Y' ≤ 107). All positions are measured in city blocks; the first coordinate increases from West to East, while the second coordinate increases from South to North. Point (0, 0) is located on Merge Avenue. You may assume that within each test case each point is not measured more than once. Likewise, each point is not queried more than once. You may also assume that all the measurements are consistent.

The last test case is followed by a line containing two zeros.

For each test case output Q + 1 lines. In the i-th line write the answer to the i-th query. If the information given by the measurements is enough to predict the anomaly at the queried point, then write an integer representing the predicted anomaly at the queried point. Otherwise write the character ‘*’ (asterisk). Print a line containing a single character ‘-’ (hyphen) after each test case.