Лёша любит программирование и олимпиады и поэтому достаточно часто пишет раунды на сайте Codeforces. Однако за многие годы он так и не получил красный цвет. Тому есть целый ряд причин: иногда происходит перерасчёт рейтинга, иногда Лёша поздно приходит на работу и уже не успевает вернуться домой к раунду, а иногда он просто уклоняется от раундов китайских авторов, поскольку считает, что они плохого качества.
Но сегодня не такой день, сегодня всё складывается очень хорошо: раунд не китайский, Лёша пришёл на работу вовремя, и, главное, он каким-то образом узнал темы задач и разбалловку!
В раунде будет n задач. Изначально i-я задача оценивается в ai баллов, однако каждую минуту её стоимость уменьшается на bi баллов. Таким образом, если i-я задача была решена на минуте mi от начала соревнований, участнику будет начислено за нее costi = ai - bi·mi баллов. Леша решает все задачи подряд, и не тратит время на отдых. Он уверен, что независимо от того, какой порядок он выберет, на момент решения i-й задачи ее стоимость будет положительна.
Также для каждой задачи Лёша знает время ti, в течение которого он напишет её решение: время решения задачи Лёшей зависит исключительно от того, на какую тему эта задача, а темы, как мы помним, он выяснил.
Конечно, Лёша хочет набрать максимально возможное количество баллов. Он догадывается, что количество набранных баллов зависит от порядка решения задач. Но сейчас он на работе и не хочет опоздать на раунд, так что вопрос определения порядка задач, обеспечивающего максимально возможное количество баллов, перекладывается на вас.
В первой строке содержится целое число n (1 ≤ n ≤ 105) — количество задач в раунде.
В каждой из следующих n строк содержится по три целых числа ai, bi, ti (1 ≤ ai ≤ 1014, 1 ≤ bi, ti ≤ 103) — описание очередной задачи.
В первой строке выведите n чисел — номера задач в том порядке, который обеспечивает максимально возможное количество баллов.
Если существует несколько ответов, выведите любой.
## Входные Данные
В первой строке содержится целое число n (1 ≤ n ≤ 105) — количество задач в раунде. В каждой из следующих n строк содержится по три целых числа ai, bi, ti (1 ≤ ai ≤ 1014, 1 ≤ bi, ti ≤ 103) — описание очередной задачи.
## Выходные Данные
В первой строке выведите n чисел — номера задач в том порядке, который обеспечивает максимально возможное количество баллов. Если существует несколько ответов, выведите любой.
## Примеры
Входные данные5500 2 101000 4 121500 6 372000 8 422500 10 23Выходные данные5 2 1 4 3
[samples]
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of problems.
For each problem $ i \in \{1, \dots, n\} $:
- $ a_i \in \mathbb{Z}^+ $: initial score.
- $ b_i \in \mathbb{Z}^+ $: penalty rate per minute.
- $ t_i \in \mathbb{Z}^+ $: time required to solve the problem.
Let $ \pi \in S_n $ be a permutation representing the order of solving problems.
Let $ m_i = \sum_{j=1}^{k} t_{\pi(j)} $ be the completion time of problem $ i = \pi(k) $.
**Constraints**
1. $ 1 \le n \le 10^5 $
2. $ 1 \le a_i \le 10^{14} $, $ 1 \le b_i, t_i \le 10^3 $ for all $ i $
3. $ a_i - b_i \cdot m_i > 0 $ for all $ i $ (guaranteed)
**Objective**
Maximize total score:
$$
\sum_{i=1}^{n} \left( a_{\pi(i)} - b_{\pi(i)} \cdot \sum_{j=1}^{i} t_{\pi(j)} \right)
$$
**Output**
Any permutation $ \pi $ that maximizes the total score.