您正在玩棋盘游戏。在这个游戏中,玩家有两个特征,x和y——分别是白魔法技能和黑魔法技能。桌子上有n 张符卡,每张符卡都有四个特征:ai、bi、ci 和di。在一次移动中,玩家可以选择其中一张牌并施展写在上面的咒语,但前提是它的前两个特征满足 ai ≤ x 和 bi ≤ y 的要求,即如果玩家有足够的魔法技能来施展该咒语。然而,施放该法术后,玩家的特征会发生变化并变得等于 x = ci 和 y = di。
在游戏开始时,玩家的两个特征都为零。游戏的目标是施放第 n 个咒语。你的任务是用尽可能少的动作完成它。你可以以任意顺序和任意次数使用法术(例如,你可能根本不使用某些法术)。
输入
输入的第一行包含一个整数 n (1 ≤ n ≤ 100 000) — 桌子上的牌数。
接下来的 n 行每行包含四个整数 ai、bi、ci、di (0 ≤ ai、bi、ci、di ≤ 109) — 相应卡片的特征。
输出
在第一行中打印一个整数 k — 施放第 n 个咒语所需的最小移动次数,在第二行中打印 k 个数字 — 按照您应该施放它们的顺序排列的卡牌索引。如果有多种可能的解决方案,请打印其中任何一个。
如果无法施放第 n 个咒语,则打印 - 1。
示例
输入 #1
4 0 0 3 4 2 2 5 3 4 1 1 7 5 3 8 8
输出 #1
3 1 2 4
输入 #2
2 0 0 4 6 5 1 1000000000 1000000000
输出 #2
-1