Compensation

Train companies must pay compensation whenever a passenger reaches the destination at least 30 minutes ($1800$ seconds) later than the booked itinerary promised. You want that money.

Your trip visits stations $1, 2, \dots, N$ in that order. Every scheduled train runs one leg, from some station $X$ to station $X + 1$. A train has a planned departure time $S$ and a planned arrival time $T$, and it is delayed by $L$ seconds on the day of travel, so it really departs at $S + L$ and really arrives at $T + L$. You hold the timetable and the full list of delays, so you know how the day will go before you book anything.

A booking is one train for each of the $N - 1$ legs, chosen so that for every pair of consecutive legs the planned departure time of the later train is at least the planned arrival time of the earlier one. Changing trains takes no time. The start time of a booking is the planned departure time of its first train, and its promised arrival time is the planned arrival time of its last train.

On the day of travel you reach station 1 at the start time of your booking. From then on you may board any train you can physically catch: at station 1 a train whose real departure time is at least your start time, and at any later station a train whose real departure time is at least the real time you arrived there. You are not tied to the trains you booked.

A booking with start time $s$ and promised arrival time $A$ earns compensation when every travel plan that leaves station 1 at time $s$ either fails to reach station $N$ at all, or reaches it at a real time of at least $A + 1800$.

Times are plain second counts and never wrap around, so a delay can push a real arrival past $86400$.

Find the smallest start time among the bookings that earn compensation.

The first line contains two integers $N$ and $M$ ($2 \le N \le 100$, $1 \le M \le 10^5$), the number of stations and the number of scheduled trains.

Each of the next $M$ lines describes one train with four integers $X$, $S$, $T$ and $L$ ($1 \le X \le N - 1$, $0 \le S \le T < 86400$, $0 \le L < 86400$): the train runs from station $X$ to station $X + 1$, its planned departure time is $S$, its planned arrival time is $T$, and it is delayed by $L$ seconds.

Print one line holding the start time of the earliest booking that earns compensation. If no booking earns it, print impossible instead.