ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

USU Internal Contest March'2001

About     Problems     Submit solution     Judge status     Standings
Contest is over

H. Square Country 2

Time limit: 1.0 second
Memory limit: 64 MB
The Square Parliament of the Square country has decreed that the National Square Park be created. Of course, the Park should occupy a large square. Unfortunately, at the moment a lot of square citizens have invested (with the help of last championship's participants) their quadrics into land so that a part of the country is already occupied. Maybe, it is now impossible to find a land for the Park without affecting interests of the private owners. In this case some of the pieces of land must be expropriated.
To avoid social unrest the Parliament has to locate the Park so that the interests of as less important as possible citizens were affected. It is better to expropriate land from a thousand of simple citizens than from one member of the Parliament or from one bank-owner.
All pieces of land that are occupied by square citizens are marked with integers from 2 to 100 according to importance of the owner: the property of the Square President is marked with 100, the property of great businessmen are marked with 99, the property of members of the Parliament is marked with 98, and so on.
Besides, some pieces of land belong to the members of (not square) Jury which created this problem. This land is marked with number 255 and cannot be expropriated at all.


The first line contains integers L and A, which are the length of a side of the Square country, and the length of a side of the Park (1 ≤ AL ≤ 10000). The next line contains an integer M that is a number of occupied pieces of land (1 ≤ M ≤ 100). According to the Square Rules a piece of land is a square with integer coordinates of corners and its sides are parallel to the axes. The coordinates of the lower left corner of the Square country itself are (1, 1).
The next M lines contain information about occupied pieces of land: importance of the owner, length of the square's side and the coordinates of the lower left corner. The importance is an integer from 2 to 100 or integer 255. The side and the coordinates are integers from 1 to L. Each piece of land is contained in the country and may intersect another piece of land only along its boundary. All land which is not contained in the occupied pieces is free.


If it is possible to create the Park on free land, output an integer 1. Otherwise, output the least possible importance of owners whose land must be expropriated (an integer from 2 to 100). The number and area of expropriated pieces of land are not important. You should only take into account importance of the most important of the affected land-owners.
If it is impossible to create the Park not involving land of the Jury, output “IMPOSSIBLE”.


5 3
94 2 4 1
3 1 1 1
2 1 1 2
2 2 2 1
100 1 2 4
255 1 5 5
5 3
255 1 3 3


Problem illustration
The figure illustrates the first example. The Park can be created on the land marked with grey color. To do this the property of land-owners with importance 2 and 3 must be expropriated.
Problem Author: Stanislav Vasilyev
Problem Source: USU Open Collegiate Programming Contest March'2001 Senior Session
To submit the solution for this problem go to the Problem set: 1097. Square Country 2