18362번 - Desert 스페셜 저지다국어

The route from Bythad do Bytara leads among the sands of the Great Byteotian Desert. Making the trip is trying, especially since there are only s wells along the route. Knowing that his country’s prosperity depends on communications routes, the ruler of Byteotia has decided to have new wells dug along this particular route. The distance from Bythad to Bytara is n+1 bytemiles, and at each integer multiple of a bytemile from Bythad, there already is a well or a new one can be dug. However, the lower the water level is, the harder and costlier it is to dig a well.

Thus, the rules has commissioned the royal geologist Byteasar with surveying the options. Byteasar has m measurements obtained through the satellite network. Unfortunately, the information gathered by the satellites does not provide direct information about the water levels. Each measurement is for a contiguous fragment of the route and tells only that in certain points of this fragment, the water level is lower than in the remaining points. Moreover, it is known that the water level in every point is between 1 and 10⁹ bytemeters below surface. Help Byteasar by determining what the water level might be in every point along the route. It could turn out that the satellite data are contradictory.

The first line of the standard input contains three integers, n, s, and m (1 ≤ s ≤ n ≤ 100 000, 1 ≤ m ≤ 200 000), separated by single spaces, which specify the number of wells along the route and the number of satellite measurements.

The s lines that follow describe the wells: the i-th one contains two integers, p_i and d_i (1 ≤ p_i ≤ n, 1 ≤ d_i ≤ 1 000 000 000), which indicate that the i-th well is located p_i bytemiles from Bythad and is d_i bytometers deep (i.e., that the water level in the well is di bytometers below ground surface). The wells are given in an increasing order of p_i.

The next m lines describe the satellite measurements: the i-th one contains three integers l_i, r_i, and k_i (1 ≤ l_i < r_i ≤ n, 1 ≤ k_i ≤ r_i − l_i), followed by a sequence of k_i integers, x₁, x₂, . . . , x_ki (l_i ≤ x₁ < x₂ < . . . < x_ki ≤ r_i). These specify that a measurement was taken on the segment from l_i to r_i (including these endpoints), and it indicated that the water level in each of the points x1, . . . , x_ki is strictly lower than the water level in each of the remaining (integer) points of the interval, i.e. {l_i, . . . , r_i} \ {x₁, . . . , x_ki}. The sum of all the k_i’s does not exceed 200 000.

In tests worth 60% of the total score, the additional conditions n, m ≤ 1000 hold. In tests worth 30% of the total score, the sum of all k_i ’s does not exceed 1000.

If the measurements are contradictory, the first line of the standard output should contain a single word NIE (Polish for no). Otherwise, the first line of the output should contain the word TAK (Polish for yes), whereas the second line should contain a sequence of n integers, each in the range from 1 to 1 000 000 000, specifying the depths below the surface of the water levels at successive points along the route from Bythad. If there are multiple solutions, your program should pick one arbitrarily.