Statement

While studying for his entrance exam to the National University for Aerospace Magic, Harry Coandă became interested in magical paper airplanes. Unfortunately, Harry Coandă doesn't have any magic paper at hand so he needs your help with some experiments. Harry designed T experiments to study the flight path of his airplane. An experiment takes place in a room of width N and height H that can be represented as an N × H grid. The rows and columns are indexed starting from 0. In the room there are W wall-like obstacles. Wall i is placed at distance X_i from the left side of the room (that is, in column X_i) and has a hole starting at height S_i and going up to height E_i, inclusive. The airplane starts on the far left end of the room at height \lfloor H/2 \rfloor and needs to reach the far right end of the room without crashing into walls, the floor, or the ceiling. The following figure displays a room of size 19 × 10, where S denotes the starting position of the plane...