403784: GYM101300 A Wildfire

Professor Beetlestein had no reasons to be satisfied. The teleportation experiment was not successful at all, and what is more it caused a tremendous fire in a nearby forest. The entire complex of neighboring buildings was threatened with a disaster. The professor, instead of devoting his precious time to drawing conclusions and to conducting further experiments, is forced to supervise the firefighting action at the moment.

The entire area touched by the fire creates an N × M grid of square areas of the identical size and integer coordinates. Some of these areas are already devoured by fire. All firemen were delegated to put out the fire, together with the only available airplane of the local Compulsory Beetle Fire Brigade. The airplane, when flying from the west to the east (thus the first area coordinate increases), may drop a firefighting material on K subsequent stripes of the terrain which are 3 areas wide. For example, if K = 2 and the airplane begins the extinguishing of the fire over the area with the coordinates (4, 7), then it is possible to put out the fire within the areas (4, 6), (4, 7), (4, 8), (5, 6), (5, 7), (5, 8).

The potential of the firefighting airplane must be properly used in order to control the situation as fast as possible. In particular, the Beetle Firefighting Substance cannot be wasted, therefore the entire areas within the drop territory should be seized by fire. The professor ordered his assistants to elaborate an optimal action plan. First, he wants to know the number of the areas that may potentially be extinguished during the first flight of the firefighting airplane.

Help the assistants establish the number of various areas from the grid which may be potentially extinguished by the airplane during its first flight.

The first line of a test set includes one natural number T denoting the number of tests. The description of each test is composed of the map of the territory covered by the disaster.

The first line of the description contains three integer numbers: N, M and K the meaning of which was explained in the previous section. In the second line of the description, there is one integer number P. Each i-th of the subsequent P lines includes three integer numbers: b_i, e_i, y_i denoting that the areas with the coordinates (b_i, y_i), (b_i + 1, y_i), (b_i + 2, y_i), ..., (e_i - 1, y_i), (e_i, y_i) are covered by fire.

1 ≤ T ≤ 10

1 ≤ N, M, K ≤ 10⁹

0 ≤ P ≤ 10⁶

1 ≤ b_i ≤ e_i ≤ N

1 ≤ y_i ≤ M

The output data should contain T integer numbers, one in each line. Each corresponds to the number of various areas of the grid which may potentially be extinguished in a given test during the first flight. The values should be given in the same order as provided in the input data.

3
5 5 1
3
1 1 1
1 1 2
1 1 3
5 5 2
3
1 1 1
1 1 2
1 1 3
6 5 2
9
4 5 5
6 6 1
1 4 2
2 3 3
4 5 5
2 5 4
4 5 3
1 2 1
3 4 4

3
0
13

Explaining the example:

• The airplane may extinguish all burning areas beginning the extinguishing over the area (1, 2).
• It is impossible to carry out a drop so that all areas within its territory are covered by fire.
• The airplane may begin a drop over the areas: (2, 3), (3, 3), (4, 4).