보상금

철도 회사는 승객이 예매한 일정보다 30분($1800$초) 이상 늦게 목적지에 닿으면 보상금을 지급해야 한다. 당신은 그 보상금을 노린다.

여행은 $1, 2, \dots, N$번 역을 이 순서대로 지난다. 시간표에 실린 열차는 모두 한 구간만 운행해서, 어떤 역 $X$에서 $X + 1$번 역으로 간다. 열차마다 계획 출발 시각 $S$와 계획 도착 시각 $T$가 있고 여행 당일에는 $L$초 지연되므로, 실제로는 $S + L$에 출발해 $T + L$에 도착한다. 시간표와 지연 목록을 모두 손에 넣었으니 예매하기 전에 그날의 운행을 전부 안다.

예매는 $N - 1$개 구간마다 열차를 하나씩 고르는 것이다. 이웃한 두 구간에서 뒤 열차의 계획 출발 시각은 앞 열차의 계획 도착 시각보다 빨라서는 안 된다. 환승에는 시간이 걸리지 않는다. 예매의 출발 시각은 첫 열차의 계획 출발 시각이고, 약속 도착 시각은 마지막 열차의 계획 도착 시각이다.

여행 당일에는 예매한 출발 시각에 1번 역에 선다. 그 뒤로는 실제로 탈 수 있는 열차라면 무엇이든 타도 된다. 1번 역에서는 실제 출발 시각이 예매 출발 시각 이상인 열차를, 그다음 역부터는 실제 출발 시각이 그 역에 실제로 도착한 시각 이상인 열차를 탄다. 예매한 열차를 그대로 탈 필요는 없다.

출발 시각이 $s$이고 약속 도착 시각이 $A$인 예매는, 시각 $s$에 1번 역을 떠나는 모든 이동 방법이 $N$번 역에 아예 닿지 못하거나 실제 도착 시각이 $A + 1800$ 이상일 때 보상금을 받는다.

시각은 초 단위 숫자일 뿐이고 하루가 지나도 되돌아가지 않으므로, 지연 탓에 실제 도착 시각이 $86400$을 넘기도 한다.

보상금을 받는 예매 가운데 출발 시각이 가장 이른 것을 구하라.

첫째 줄에 역의 수 $N$과 시간표에 실린 열차의 수 $M$이 주어진다 ($2 \le N \le 100$, $1 \le M \le 10^5$).

다음 $M$개 줄에는 열차 하나를 나타내는 네 정수 $X$, $S$, $T$, $L$이 주어진다 ($1 \le X \le N - 1$, $0 \le S \le T < 86400$, $0 \le L < 86400$). 이 열차는 $X$번 역에서 $X + 1$번 역으로 가고, 계획 출발 시각은 $S$, 계획 도착 시각은 $T$이며 $L$초 지연된다.

보상금을 받는 예매 가운데 가장 이른 출발 시각을 한 줄에 출력한다. 그런 예매가 없으면 impossible을 출력한다.