Problem Description

On a certain planet, there is a town shaped like an equilateral triangle. This town has $N \times (N + 1) / 2$ houses arranged in an equilateral triangular pattern. The triangle is such that one of its sides is parallel to the east-west direction, and the vertex not on this side is the northernmost house.

Each house is numbered using two integers. The northernmost house is numbered ($ 1 $, $ 1 $), and the $ j $th house from the west in the $ i $th row from the north (where $1 \leq j \leq i \leq N$) is numbered ($ i $, $ j $).

Here is an example for $ N = 5 $:

(1,1)(2,1)(2,2)(3,1)(3,2)(3,3)(4,1)(4,2)(4,3)(4,4)(5,1)(5,2)(5,3)(5,4)(5,5)

dwango Inc. has $ M $ radio stations (numbered from $ 1 $ to $ M $), each broadcasting digital content to a certain range of houses in the shape of an equilateral triangle (with sides parallel to the edges of the town).

For each radio station $ i $ (where $1 \leq i \leq M$), three integers $ a_i $, $ b_i $, and $ c_i $ are defined. The radio station $ i $ broadcasts to all houses ($ a_i + j - 1 $, $ b_i + k - 1 $) for all integers $ j $ and $ k $ satisfying $1 \leq k \leq j \leq c_i$.

dwango Inc. plans to install one new radio station to attract new customers.

There are $ Q $ proposed methods for installing the new radio station. Write a program to determine the number of new customers that can be acquired for each installation method.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ a_1 $ $ b_1 $ $ c_1 $ $ a_2 $ $ b_2 $ $ c_2 $ : $ a_M $ $ b_M $ $ c_M $ $ Q $ $ d_1 $ $ e_1 $ $ f_1 $ $ d_2 $ $ e_2 $ $ f_2 $ : $ d_Q $ $ e_Q $ $ f_Q $

• The first line contains two integers $ N $ (where $1 \leq N \leq 1,000,000,000$) and $ M $ (where $1 \leq M \leq 1,000$), separated by a space.
• The next $ M $ lines contain information about the already installed radio stations. The $ i $th line (where $1 \leq i \leq M$) contains three integers $ a_i $, $ b_i $ (where $1 \leq b_i \leq a_i \leq N$), and $ c_i $ (where $1 \leq c_i \leq N - a_i + 1$), representing the range of houses covered by radio station $ i $.
• The line following the $ M $ lines contains an integer $ Q $ (where $1 \leq Q \leq 1,000$).
• The next $ Q $ lines contain information about the new installation methods. The $ i $th line (where $1 \leq i \leq Q$) contains three integers $ d_i $, $ e_i $ (where $1 \leq e_i \leq d_i \leq N$), and $ f_i $ (where $1 \leq f_i \leq N - d_i + 1$), representing the range of houses that the new radio station would cover.

Output Format

The output consists of $ Q $ lines. The $ i $th line (where $1 \leq i \leq Q$) should contain the number of new houses that would be covered by the $ i $th installation method.

Sample Input and Output

Sample Input #1

8 3
2 2 4
5 4 3
6 1 3
2
4 1 4
7 6 2

Sample Output #1

5
2

Sample Input #2

3 2
1 1 2
3 2 1
3
2 1 2
2 2 1
1 1 3

Sample Output #2

1
0
2

Notes/Hints

Partial Points

This problem has partial points.

• For a dataset where $N \leq 200$, $M \leq 200$, and $Q \leq 200$, you can get $ 10 $ points.
• For a dataset where $M \leq 200$ and $Q \leq 200$, you can get an additional $ 30 $ points.
• For a dataset without additional constraints, you can get an additional $ 60 $ points, totaling $ 100 $ points.

Sample Explanation 1

The ranges of houses covered by the already installed $ 3 $ radio stations are as shown in the figure below (○ indicates coverage, × indicates no coverage).

××○×○○×○○○×○○○○○××○○×○○×○○○×○○○×××××

For the first installation method, the new houses covered are indicated by + below:

××○×○○+○○○+○○○○○++○○×○○+○○○×○○○×××××

For the second installation method, the new houses covered are indicated by + below:

××○×○○×○○○×○○○○○××○○×○○×○○○×○○○××++×

见题面 Input 部分

见题面 Output 部分