시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB51133.333%

문제

Недавно черепашки получили письмо от учителя Сплинтера. В нем было сказано, что они должны прийти в центр Нью-Йорка ровно в полночь (а до нее оставалось всего несколько часов). Леонардо заподозрил что-то неладное и предположил, что это ловушка, а учитель в беде и его необходимо срочно спасать. Донателло заметил набор точек, расположенных на одной прямой, который был нарисован в углу листка, и тут же вспомнил шифр, который они недавно придумали вместе с учителем Сплинтером.

Сам шифр заключался в следующем. Введем на прямой с точками такую систему координат, что крайние точки имеют координаты ноль и один. Координаты всех остальных точек будут рациональными числами, лежащими в интервале от нуля до единицы. Известно, что изначально на прямой были нарисованы только две крайние точки.

Также известно, что учитель ставил очередную точку только строго посередине между какими-то двумя уже поставленными. Например, третьей точкой он мог поставить точку с координатой $\frac{1}{2}$, четвертой --- точку с координатой $\frac{1}{4}$, а пятой --- точку с координатой $\frac{5}{8}=\frac{\frac{1}{4} + 1}{2}$. Таким образом учитель поставил $n-2$ точки.

Донателло хочет проверить, является ли набор точек, найденных на листе, описанным шифром.

입력

В первой строке входного файла записано целое число $n$ ($2 \le n \le 1500$) --- количество точек на рисунке в письме. В следующих $n$ строках записано по два целых числа $x_i$ и $y_i$ ($0 \le x_i \le y_i \le 10^9, y_i \neq 0$), означающие, что $i$-я точка имеет координату $\frac{x_i}{y_i}$.

Гарантируется, что в множестве есть точки с координатами ноль и один и что все точки различны. Также гарантируется, что все дроби, данные в условии, несократимые.

Необходимо определить, можно ли было поставить эти точки описанным образом.

출력

В выходной файл в первой строке выведите YES, если точки могли быть поставлены описанным образом, и NO в противном случае.

Если множество получить можно, в следующих $n - 2$ строках выведите по три числа --- номер точки, которую нужно добавить на очередном шаге, а также номера двух точек, которые уже были добавлены, таких, что новая точка лежит ровно посередине между ними. Считайте, что точки с координатами $0$ и $1$ уже добавлены.

Если же множество нельзя получить подобным образом, то во второй строке выведите номер любой точки, которую нельзя получить. Все точки нумеруются с $1$.

예제 입력 1

4
0 1
1 4
1 2
1 1

예제 출력 1

YES
3 1 4
2 1 3

예제 입력 2

4
0 1
1 4
3 4
1 1

예제 출력 2

NO
2

예제 입력 3

5
5 8
1 4
1 2
1 1
0 1

예제 출력 3

YES
3 5 4
2 3 5
1 2 4