404987: GYM101726 J The Sverdlovsk incident

During the years of the Soviet Union, the name of the city of Yekaterinburg was Sverdlovsk, in honor to the Bolshevik Iakov Sverdlov, son of a Jewish artisan, that was an excellent orator and was one of the main protagonists beside Lenin in the revolution in October 1905. He was considered honest, energetic and hard-working, and was respected by all groups of the party. He died at 34. The city got back its original name in 1991 by the initiative of Boris Yeltsin, the first Russian president, born in that city.

In April 2nd, 1979, while the city was still called Sverdlovsk, there was an anthrax leaking from a military factory in the city. This incident is often called "Biological Chernobyl", and caused approximately 100 deaths, despite the exact number of victims and contaminated are still unknown. The Soviet Union denied for years the real causes of the incident and every victim record disappeared, since they could uncover serious violations of the Biological Weapons Convention.

The Soviet authorities had to use highly sophisticated decontamination procedures, specially in rural areas. Each rectangular area of dimensions N by M was divided in N × M square sectors of one squared meter. These sectors were identified by the coordinates of their centers, numbered from west to ease and from south to north from (1, 1).

Each sector was considered decontaminated if it was covered by at least K health agents. Each agent was capable of covering a circular area. The radius of this area depended on the equipment used and the experience of the agent. Your task is to determine how many of those sectors are considered decontaminated, that is, covered by at least K agents. A sector is considered to be covered if its center is in an area covered by some agent.

On the first line, a single integer T, the number of test cases.

The first line of each test case contains two integers, N and M, the dimension of the rectangular area mentioned in the statement. The second line contains the number of agents, C, and the number K.

The c-th of the next C lines contains the description of the c-th agent, that is, three integers X_c, Y_c and R_c, meaning (X_c, Y_c) is the center of the circular area covered by that agent, and the radius is R_c.

Limits

• 1 ≤ T ≤ 10
• 1 ≤ N ≤ 10³
• 1 ≤ M ≤ 10⁵
• 1 ≤ K ≤ C ≤ 10³
• 1 ≤ X_c ≤ N
• 1 ≤ Y_c ≤ M
• 0 ≤ R_c ≤ 10⁸

For each test case, print the number of decontaminated sectors.

2
10 10
2 1
3 3 2
8 8 2
15 15
6 2
4 4 2
5 5 1
6 6 3
7 7 2
10 10 0
11 10 1

26
20

More precisely, a sector with center (x_s, y_s) is covered by an agent positioned at (x_a, y_a) capable of decontaminating an area with radius r if