In the event of technical difficulties with Szkopuł, please contact us via email at firstname.lastname@example.org.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (
#szkopul channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
Byteasar has recently started his PhD studies. He researches and teaches. The first semester is over. Students wrote their exam and now Byteasar has to grade it.
Each student produced one sheet of size millimetres. According to the advice by his elder colleagues Byteasar applied the standard university procedure. He grabbed all the sheets and threw them to the air. The sheets fell onto the ground. To his surprise, the sheets arranged themselves parallel to the walls of his rectangular office. The exam will be passed by the students whose sheets are on the top.
A sheet is on the top if none of its inner points is covered by another sheet. In particular, this means that sides of the sheet may be covered.
Write a program to check who passed the exam.
The first line of input contains three integers , and (, ) denoting respectively the number of sheets and the dimensions of each sheet in millimetres. Sheets are rectangles with sides parallel to the axes.
The following lines describe sheets in order of their fall to the floor. The description of one sheet is composed of three integers , , (, ). Point is the lower left corner of the sheet. If , then the sheet is a rectangle of height and width , but when , the height is and width .
The first line of the output should contain one integer equal to the number of sheets that are not covered (except for their sides) by other sheets. The second line should hold a sequence numbers of those sheets in increasing order. The sheets are numbered through as they appear in the input.
For the input data:
4 3 2 1 1 0 3 2 0 6 2 0 4 3 1
the correct result is:
2 1 4
Task author: Szymon Acedanski.