题目描述

在自由市场、极端资本主义的铁路票价体系中，最重要的只有一件事：激励机制。

铁路公司会因为高客流量、旅程顺利和乘客满意而获得奖励；相反，如果乘客延误 30 分钟或更久，铁路公司就必须向乘客退款。

作为一名同样精明的资本主义者，你决定利用这项慷慨的延误赔偿政策。

若满足以下条件，乘客就能获得退款：

在实际延误发生后，无论乘客如何选择列车，只要经过的车站路线与原计划相同，他都不可能在“原预订行程准点时的到达时刻之后不足 30 分钟”到达终点。

换言之，实际情况下能够达到的最早到达时刻，与原预订方案的计划到达时刻之差必须至少为 1800 秒。

现在，你已经获得了当天所有列车的原始时刻表和延误信息。请找出：最早可以预订几点从车站 1 出发的列车，才能确保获得延误赔偿？

输入格式

• 第一行包含两个整数 $N,M$：
  • $N$（$1\le N\le100$）表示车站数；
  • $M$（$1\le M\le10^5$）表示时刻表中的列车数。
• 接下来 $M$ 行，每行包含四个整数 $X,S,T,L$：
  • $X$（$1\le X\le N-1$）表示列车从车站 $X$ 开往车站 $X+1$；
  • $S,T$（$0\le S\le T<86400$）分别表示计划出发时刻和计划到达时刻，单位为秒；
  • $L$（$0\le L<86400$）表示该列车延误的秒数。

该列车实际的出发时刻为 $S+L$，实际的到达时刻为 $T+L$。

车站按照旅程方向依次编号为 $1,2,\ldots,N$。每趟列车只在两个相邻车站之间运行，即从 $X$ 到 $X+1$。

换乘列车不需要额外时间。

输出格式

输出一个整数，表示能够确保获得赔偿的最早预订旅程的首班列车计划出发时刻。

如果不存在这样的旅程，输出：

impossible

样例 1

输入

2 3
1 1800 9000 1800
1 2000 9200 1600
1 2200 9400 1400

输出

1800

样例 2

输入

2 2
1 1800 3600 1800
1 1900 3600 1600

输出

impossible

样例 3

输入

3 2
1 10 20 1
2 20 30 0

输出

10