Activity Selection Problem

You are given a set of activities, each with a unique ID, a start time, and an end time. Your task is to select the maximum number of activities that do not overlap. Two activities are considered non-overlapping if the start time of one is not less than the end time of the previously selected activity.

You should output the number of chosen activities in the first line, and in the second line output the activity IDs separated by spaces in the order they are selected by the greedy algorithm.

Formally, given \(N\) activities represented as tuples \((ID_i, s_i, e_i)\), choose a subset \(S\) such that no two activities in \(S\) overlap and \(|S|\) is maximized.

inputFormat

The first line contains a single integer \(N\) representing the number of activities. Each of the next \(N\) lines contains three integers: \(ID\), start time, and end time of an activity.

outputFormat

The first line should contain an integer representing the maximum number of non-overlapping activities selected. The second line should list the IDs of the selected activities separated by spaces.

## sample

5
1 1 4
2 3 5
3 0 6
4 5 7
5 8 9

3
1 4 5

</p>