Codah ClubVježbaj. Pošalji. Napreduj.
Prijavi se
Hrvatski
#000271

Ograda

Mirko built a wooden fence next to his house. He built his fence by slamming rectangular wooden boards into the ground. For each board we know its height, width and distance of its left edge from Mirko's house. Mirko was really enjoying building his fence, so much that he stopped paying attention as to how he was building it – now that he is done, some of the boards are overlapping, and there are holes in the fence, total chaos! Mirko is now looking at his fence and is shocked – he could have built a fence the same fence (when looked from up front) using fewer boards. If we connect the top sides of all boards as in the image below, we get the skyline of the fence.

Image: dsadsa

\emph{The second example input. The skyline is depicted by a bold line.}

Mirko decided to remove some of the boards from the fence so that the skyline remains the same and that as few boards as possible remain in the fence. Write a program that determines which boards should remain in the fence.



InputThe first line contains an integer N (1 ≤ N ≤ 100 000), the number of boards initially in Mirko's fence. Each of the following N lines describes one board with three integers X, W and H; these are the distance of the left edge of the board from Mirko's house, width and height of the board, respectively. No two boards will share the same (X, W, H) triplet. All these numbers will be at most a billion (10^{9}). Boards are numbered 1 to N.


OutputOn the first line output B, the smallest number of boards that need to remain for the skyline to stay the same. On the second line output B integers separated by spaces, the numbers of boards that should remain in the fence. This part of the output is not necessarily unique.


Input:
5
10 11 30
19 1 20
15 9 10
7 7 20
3 12 40
Output:
3
1 3 5

Input:
6
15 8 4
10 8 3
25 3 7
3 9 5
1 5 3
7 2 2
Output:
5
1 2 3 4 5

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.