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: bi, ei, yi denoting that the areas with the coordinates (bi, yi), (bi + 1, yi), (bi + 2, yi), ..., (ei - 1, yi), (ei, yi) are covered by fire.
1 ≤ T ≤ 10
1 ≤ N, M, K ≤ 109
0 ≤ P ≤ 106
1 ≤ bi ≤ ei ≤ N
1 ≤ yi ≤ 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:
Beetlejumpers have long been dreaming about having access to the numerous natural resources of the planet Stavromula Gamma. The local inhabitants do not even want to think about moving to less fertile territories. The military conflict seems to be inevitable, and supposing that the rumors are true, it will arise soon. The latest orders of the General Beattle, probably concerning the details of the attack, are of such a great importance that instead of being broadcast by a radio, they are delivered to the commanders personally.
The envelopes are marked with the sign ,,CONFIDENTIAL. Personal service", therefore their delivery may be carried out only by one of the three drivers accredited by the army. The army is in possession of super-fast vehicles – beetcars which were made available to the drivers. Due to the planned attack, such resources as fuel are priceless and must be used as efficiently as possible.
On the planet Stavromula Gamma, there are N cities marked with numbers from 1 to N and M two-way roads located between some of the cities. The network of the roads is so highly developed that for each city there is a certain set of the roads which allows for transportation to every other city.
The orders to the commanders of each of K units which are stationed on the planet Stavromula Gamma must be delivered with the use of three fast beetcars.
The drivers of the beetcars must deliver all envelopes and come back to the headquarters driving the shortest possible distance altogether (minimum distance in total). Moreover the habits present in the beetle army (always unconditionally observed by the army) require that the commanders become familiar with the wording of the orders in an appropriate order – the higher is their military rank, the sooner they should receive it.
The first line of the input includes two numbers: N and M, denoting the number of the cities and the number of the roads on the planet respectively. Each i-th line of the subsequent M lines consists of three numbers: ai, bi, di denoting that between the cities ai and bi there is a road measuring di. The next line consists of one number T which constitutes the number of test cases.
The following lines include the descriptions of these test cases. Each of them is composed of two lines. The first of the lines includes two integer numbers: H and K which stand for the identifier of the city in which the headquarters is located and the number of the units for which the orders should be delivered respectively. The second line of the description of the test case is composed of K numbers within the range from 1 to N. These are the identifiers of the cities where the units are stationed. They are listed exactly in the order according to which the orders are to be delivered.
1 ≤ N ≤ 104
1 ≤ M ≤ 106
1 ≤ ai, bi ≤ N
1 ≤ di ≤ 106
1 ≤ T ≤ 10
1 ≤ H ≤ N
1 ≤ K ≤ 1000
For each test case, one integer number should be given in a separate line. Each value denotes the minimum distance that all three beetcars must go in total to deliver all orders from the headquarters and to go back to the headquarters. The values should be given in the same order as provided in the input data.
7 10
1 7 24
7 6 26
3 1 4
1 4 2
3 4 100
2 1 4
2 3 5
1 5 10
4 5 6
2 3 8
2
1 7
4 5 3 6 4 4 2
2 3
1 2 3
129
13
1: 
2: 
3: 
1: 
2: 
1: 
2: 2
1: 
"This should definitely look much better..." – said the fire brigade captain Peetle-Son. He got used to it that his decisions concerning the management of the Compulsory Beetle Fire Brigade units have always been optimal. Unfortunately, the reports were exceptionally alarming – the fire was spreading fast. Soon it turned out that the cause of the fire was not the experiment conducted by professor Beetlestein, but a well-planned sabotage action carried out by the Fighters for Going Back to the Future.
Courageous firemen under the command of captain Peetle-Son are now threatened not only by a direct fight with the element. Additionally they must pay attention to the explosive charges placed by the saboteurs, which effectively enlarge the disaster area and directly threaten the life of the rescuers. Even the most cautious captain could not predict such a scenario. Hospitals (very rare in this part of the Universum) are bursting at the seams and are unable to take in the heroes fighting with the fire and explosions. The best doctors and professors of the beetle surgery do their best in order to save the life of each fireman.
In the hospital, there are specialized surgery tables used to carry out medical treatments. Each table is of a specific type defining the kinds of treatment which are to be performed on them. Each kind of a treatment may be carried out on various (known in advance) types of surgery tables. Each type of the table may be used for more than one kind of the treatment.
Example. The treatment of "leg amputation" may be carried out both on a table equipped with a "laser blade" (table of the first type) and a table equipped with (ouch!) "sword blade" (table of another type). Next: a table equipped with a "laser blade" may be for example used in the "leg amputation" (x type treatment), in "resection of dead tissues" (y type of treatment) and in "eyesight correction" (z type treatment).
N brave beetlejumpers should be provided with medical aid. Treatment of each of them is individually adjusted to the current patient's condition. The entire recovery process of an i-th beetlejumper is composed of mi kinds of treatments (
, where 
is the number of all kinds of treatment known to the beetle surgeons) which must be carried out in an ordered sequence. Each j-th treatment can be carried out by a qualified doctor in time tj on one out of the Rj table types. If the surgical table is not occupied at the moment, the treatment may begin immediately.
Example. If the patient is to undergo three treatments: (1) "general anesthesia administration", (2) "leg amputation" and (3) "permanent prosthesis attachment", each of the treatments may be performed when a particular operating table is unoccupied and when patient's previous treatments are finished. It means that (2) "leg amputation" can be performed only after finishing (1) "general anesthesia administration", and (3) "permanent prosthesis attachment" can be performed only after (2) "leg amputation".
Doctors must act quickly and decidedly – each minute may save a life of a beetlejumper! Fortunately, the hospital staff may use more than one table of each type, what enables parallel strenuous work of the doctors. However, the costs of drawing on the reserves of such equipment are significant...
Your task is to help the hospital staff to plan the treatment process of the beetlejumpers. Unusual threat in the fire area causes great losses among the fire brigades thus it is important to perform the surgeries as quickly as possible and to effectively use the surgical tables.
The first line of a test set includes one natural number M which is the number of the types of surgery tables. The second line includes M (separated by single whitespace characters) natural numbers Lk which are the numbers of surgery tables of each type actually available in the hospital.
Each surgery table has its own identifier (ID) which is a subsequent integer number. For example, if M = 2, L1 = 3 and L2 = 2, then the subsequent surgery tables are marked with identifiers ID={1, 2, 3, 4, 5}, where the tables with the ID={1, 2, 3} are the tables of the first type and the tables of the ID={4, 5} of the second type.
The third line of a test set consists of one natural number , which is the number of the kinds of treatments known to the beetle surgeons. Each j-th line from subsequent lines is composed of (2 + Rj) natural lines meaning respectively: identifier of j-th kind of a treatment, its time (tj) and identifiers of the types of surgery tables on which it may be performed.
The next line includes one natural number N which stands for the number of the injured beetlejumpers. Each i-th line of the subsequent N lines is composed of (1 + mi) natural numbers meaning respectively: identifier of a treated beetlejumper and identifier of the subsequent kinds of treatments necessary to be carried out in order to cure i-th patient.
1 ≤ N ≤ 103
1 ≤ M, Lk ≤ 5·103
1 ≤ Rj ≤ M
1 ≤ tj ≤ 104
Output data should in the first line consist of two natural numbers separated by a whitespace: S denoting the number of used surgery tables and T denoting the time necessary for curing all beetlejumpers (from the beginning of the first treatment till the end of the last one).
Each of the subsequent S lines describes one surgery table. For each surgery table, its ID and subsequent treatments carried out on it should be given. Each treatment performed on a given table is defined by a pair of natural numbers: identifier of a beetlejumper related to this treatment and a treatment sequential number from the patient's treatments list (starting from 1). Surgery tables should be described in an ascending order (in respect of their identifiers). The numbers within the lines should be separated by single whitespace characters.
If the following conditions are fulfilled:
, i.e. the number of all available tables, 
(rounded off to three decimal places), where the value T0 is the total time of all treatments of all beetlejumpers (irrespective of the availability of the tables) and Pbly is the sum of maximum P values achieved by last year's contestants for all test sets. Otherwise the score is 0.For the input data (this example is not from the official testset, it is just example):
4
1 1 1 2
4
1 5 1 2
2 10 1
3 15 1 2 3 4
4 3 3
3
1 1 2 3 4
2 3 1
3 1 2 1 1
A possible correct answer is:
4 35
1 1 1 1 2 3 2 3 3 3 4
2 3 1 2 2
3 2 1 1 4
5 1 3
, after rounding the P value equals to 0.018. 
Breeding of unusual kind of cattle has recently become a very lucrative undertaking. Megacows are an endemic species. Due to the biological factors, their occurrence and breeding possibilities are limited to only one, quite remote part of the Universum.
However, the work in this discipline is not easy at all. Megacows are extremely strong, thus a typical classic fence is not able to restrict them. Fortunately, the plots are equipped with numerous Force Points marked as (FP). These points connected with each other create an energy barrier – efficient fence for this new cattle species.
Prior to the commencement of typical activities at the rancho, every new farmer in this region must face other noxious limitation – the local law. It prohibits any private ownership of the land. The only way of conducting legal breeding is the lease of a plot of land and payment of high taxes to the benefit of the Beetlejumper Land Council. The amount of the tax due depends on the actual area of the territory limited by the energy barrier.
Help the farmers specify the minimum (to reduce the taxes) and the maximum (to specify the potential of the rancho to enlarge the herd) area which may be circled by the energy barrier on a given plot of land.
The task should be accomplished by indicating a proper order of joining the Force Points. Each point may be connected with only two other FPs and the lines connecting these points cannot cross. Additionally in order to make the energy barrier stable enough, you must choose at least (N–K) points from among N points available on a plot of land for the connection.
The first line of a test set includes one natural number T – the number of plots of land, the values of which the farmers would like to know. The subsequent lines include T descriptions of the plots of land.
The first line of the description of a plot of land consists of two integer numbers separated by a whitespace: N, indicating the number of Force Points available on a plot of land and K – the number of points which may be skipped in order to make the barrier stable enough. Each i-th from among the subsequent N lines includes three integer numbers: ci, xi, yi. The values xi and yi are the unique (within the area of a plot of land) coordinates of a given FP, whereas ci is an identifier (also unique within the area of a plot of land) (see Output).
1 ≤ T ≤ 5
3 ≤ N ≤ 1000
0 ≤ K ≤ 100
1 ≤ ci ≤ N
0 ≤ xi, yi ≤ 104
The output data should include characteristics and definitions indicated for particular plots of land in the order in which these plots appeared in the input file. Each separate description is composed of three lines discussed below.
The first line should consist of a definition of the possible biggest area limited by an energy barrier. This line should start with a natural number L which indicates the number of the used Force Points. Then, after a whitespace, you should place L numbers separated by a single whitespace, which constitute a sequence of ci identifiers – their connection in a given sequence should create a closed polygonal chain which defines a subjective area. Each identifier may appear only once (the last element is automatically connected with the first one).
The second line is a definition of the possible smallest area limited by the energy barrier. The elements of this definition are analogous to these from the first line.
The third line of a description should consist of the number S which is a product (rounded to the closest integer number) of the number 10 and a difference of the areas listed in the first and second line of a given description. This means: S = round(10·(amax - amin)), where amax is the area from the first line of the description of the solution for a given plot of land, and amin is the area from the second line of this description.
If the following conditions are satisfied:
then the score for a given set equals 
, where Ss is the sum of the S values for all plots of land in a given test set and Stly is the sum of maximum Ss values achieved by last year's contestants for all test sets. Otherwise the score is 0.
For the input data (this example is not from the official testset, it is just example):
3
8 0
1 2 2
2 2 3
3 1 3
4 1 1
7 1 4
6 3 1
8 1 2
5 3 4
8 2
6 3 3
1 2 1
2 2 2
3 2 3
4 4 1
8 2 4
7 3 2
5 4 4
4 0
2 4 3
1 2 2
3 2 3
4 4 2
A possible correct answer is:
8 7 5 6 4 8 1 2 3
8 7 5 2 1 6 4 8 3
10
6 1 2 3 8 5 4
6 1 2 3 6 7 4
35
4 3 2 4 1
4 3 2 4 1
0
Explanation:
