Вы играете в настольную карточную игру. В этой игре у игрока есть две характеристики x и y — мастерство владения светлой и тёмной магией соответственно. На столе лежат n карт заклинаний, каждая из которых имеет четыре характеристики ai, bi, ci, di. За один ход игрок может сыграть одну из карт и прочитать написанное на ней заклинание, но только в том случае, если её две первых характеристики удовлетворяют соотношениям ai ≤ x и bi ≤ y, то есть если игрок обладает достаточным мастерством владения магией для прочтения этого заклинания. Сразу после прочтения заклинания i характеристики игрока меняются и становятся равными x = ci и y = di.
В начале игры обе характеристики игрока равны нулю. Цель игры состоит в том, чтобы прочитать n-е заклинание. Ваша задача — сделать это за как можно меньшее число ходов. Заклинания можно читать в произвольном порядке и произвольное число раз (в том числе и вовсе не использовать какие-то заклинания).
Выходные данные
В первой строке выведите единственное число k — минимальное количество ходов, необходимое для прочтения n-го заклинания, а во второй строке выведите k чисел — номера карт, в том порядке, в котором их надо разыгрывать. Если правильных ответов несколько, то разрешается вывести любой.
Если прочитать n-е заклинание невозможно, то выведите - 1.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
0 0 3 4
2 2 5 3
4 1 1 7
5 3 8 8
|
3
1 2 4
|
|
2
|
2
0 0 4 6
5 1 1000000000 1000000000
|
-1
|