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 anoma- lies 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 repre- sented 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 mea- surements 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. Input 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
9 8 8 *
3/3