Arkady 喜欢在他的厨房里走动。他迷宫般的厨房由几个与通道相连的重要场所组成。不幸的是,这些通道被牛奶淹没,无法通过。也就是说,只有在一定的时间间隔内才可以从任意方向通过每个通道。
所有通道的长度都是相等的,阿尔卡迪在一秒钟内穿过它们。出于安全考虑,阿尔卡迪永远不能停下来,也不能在通过通道时改变方向。换句话说,如果他开始在某个通道中行走,他应该到达该通道的尽头并立即离开该通道。
今天Arkady需要从地点1快速到达重要地点n。他计划在时刻0离开地点1,尽快到达地点n。请找出他在路上应该花费的最短时间。
输入
第一行包含两个整数 n 和 m (1 ≤ n ≤ 5·105, 0 ≤ m ≤ 5·105) – 分别是重要地点的数量和通道的数量。
之后是 m 行,每行描述一个段落。每行包含四个整数 a、b、l 和 r(1 ≤ a、b ≤ n、a ≠ b、0 ≤ l < r ≤ 109)——通道连接的位置以及可以使用该通道的时间段。
输出
打印一个整数 - Arkady 到达目的地所需的最短时间。如果他无法到达地点 n,则打印 -1。
示例
输入 #1
5 6 1 2 0 1 2 5 2 3 2 5 0 1 1 3 0 1 3 4 1 2 4 5 2 3
输出 #1
3
输入 #2
2 1 1 2 1 100
输出 #2
-1
注意
在第一个例子中,Arkady 应该经过重要的地方 1 → 3 → 4 → 5。
在第二个示例中,Arkady 无法开始行走,因为在时间点 0 不可能使用唯一的通道。