Max is preparing hard for the most important event in his life — the ACM ICPC finals. He knows that in the nearest future n programming competitions are going to be held, and that the i-th of them starts at the moment of time ai, ends at the moment of time bi and has usefulness ci. To prepare better, he wants to choose for participating such set of competitions that their total usefulness will be as large as possible, and in case of a tie — that their total duration will be as small as possible. Of course, Max cannot participate in several competitions simultaneously, and also never starts competition after its moment of start and never gives up a competition before its end.
The first line contains a single integer n (1 ≤ n ≤ 200000) — the number of competitions.
The next n lines contain three integers each ai, bi, ci separated by a space (0 ≤ ai < bi ≤ 109, 1 ≤ ci ≤ 109) — times of the start and the end of the i-th competition and its usefulness.
In the first line output three integers — the number of competitions k, in which Max should participate, and then their total usefulness and total duration.
In the second line output k integers separated by a space — the numbers of competitions Max should participate in. Competitions are numbered from one in the order they are listed in the input.
If there are several correct answers, output any of them.
## Input
The first line contains a single integer n (1 ≤ n ≤ 200000) — the number of competitions.The next n lines contain three integers each ai, bi, ci separated by a space (0 ≤ ai < bi ≤ 109, 1 ≤ ci ≤ 109) — times of the start and the end of the i-th competition and its usefulness.
## Output
In the first line output three integers — the number of competitions k, in which Max should participate, and then their total usefulness and total duration.In the second line output k integers separated by a space — the numbers of competitions Max should participate in. Competitions are numbered from one in the order they are listed in the input.If there are several correct answers, output any of them.
[samples]
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of competitions.
For each $ i \in \{1, \dots, n\} $, let $ (a_i, b_i, c_i) \in \mathbb{Z}^3 $ denote the start time, end time, and usefulness of competition $ i $, where $ 0 \leq a_i < b_i \leq 10^9 $ and $ 1 \leq c_i \leq 10^9 $.
Let $ S \subseteq \{1, \dots, n\} $ be a subset of competitions such that for any two distinct $ i, j \in S $, the intervals $ [a_i, b_i] $ and $ [a_j, b_j] $ are non-overlapping (i.e., $ b_i \leq a_j $ or $ b_j \leq a_i $).
**Constraints**
1. $ 1 \leq n \leq 200000 $
2. $ 0 \leq a_i < b_i \leq 10^9 $ for all $ i \in \{1, \dots, n\} $
3. $ 1 \leq c_i \leq 10^9 $ for all $ i \in \{1, \dots, n\} $
4. Competitions in $ S $ must be pairwise non-overlapping.
**Objective**
Find a subset $ S \subseteq \{1, \dots, n\} $ that:
- **Maximizes** total usefulness: $ \sum_{i \in S} c_i $
- **Minimizes** total duration: $ \sum_{i \in S} (b_i - a_i) $, in case of ties in total usefulness.
Output:
- $ |S| $, $ \sum_{i \in S} c_i $, $ \sum_{i \in S} (b_i - a_i) $
- The list of competition indices $ i \in S $ (1-indexed, in any order)