The ACM-ICPC world final hosting

There are n major cities in the world. These cities are labeled from 0 to n, which in order to form a convex polygon on a single plane (see the figure below). Each year, the ACM-ICPC Committee has to select one city from these cities to host the ACM-ICPC world final. The selection process is described as follows:

• At the first phase, they create a shortlist. In order to do so, with a starting city s and a selection step d, they put all the cities with label s + i * d into the shortlist for all i such that 0i and s + i * d < n.

• At the second phase, one city will be selected from the shortlist to organize the ACM-ICPC world final. At that year, they might choose the city which is the most to the North (maximal y coordinate), to the South (minimum y coordinate), to the East (maximum x coordinate) or to the West X (minimum x coordinate). It is assumed that there are no two cities having the same x, or y coordinate.

There is a cost associated with each city to organize the ACM-ICPC world final. It is assumed that this cost does not change over years. Your task is to compute the total cost the ACM-ICPC Committee has to pay to organize the ACM-ICPC world finals for a given number of years.

Input 

The input consists of several data sets. The first line of the input file contains the number of data sets which is a positive integer and is not bigger than 20. The following lines describe the data sets.

For each data set, the first line contains the integer number n (1n100000). Each line of the next n lines describes one city, which contains three integer numbers x, y, and c separated by space. The pair (x, y) is a 2-D coordinate specifying the location of the city (- 200000x, y200000). c is the associated cost to organize the ACM-ICPC world final in that city (1c1000). The next line contains an integer number m, which is the number of years the ACM-ICPC Committee want to compute the cost to organize the ACM-ICPC world finals (1m10000). Each line of the next m lines contains three integer numbers s, d (0s < n;1d ), and p separated by space. The value of p can be 0, 1, 2 or 3 for selecting the city most to the North, the South, the East or the West respectively.

Output 

For each data set, write in one line the total cost for the ACM-ICPC Committee to organize the ACMICPC world finals.

Sample Input 

2 
4 
-1 1 2 
0 4 3 
5 3 2 
1 -1 2 
2 
0 1 0 
0 2 1 
3 
0 0 2 
1 1 3 
2 10 2 
2 
1 1 1 
0 2 0

Sample Output 

5 
5