Minimizing House Transfers

During the South African World Cup, fans could rent rooms in a designated hotel called Avatar. Since the number of rooms does not exceed $26$, each room is denoted by a capital letter. When a booking request comes in – for example, from the evening of June 12 to the noon of June 19 – it might happen that no single room is available for the entire period. In that case the fan must switch rooms during the stay. For instance, Manager Liu might say: "I will accommodate you in room B for 3 days and then transfer you to room F for the rest of your trip."

Your task is to help minimize the number of times the guest has to switch rooms (i.e. move from one room to another) in order to cover the entire rental period. Note that in the hotel’s billing system each day is counted from the evening to the following noon. Therefore, if an interval covers [s, e] days it means the room is available from the evening of day $s$ until the noon of day $e$. The guest may check out earlier than the end of an available interval if desired, but the available intervals cannot be partially used to “skip” a gap. A transfer is counted only when the guest changes the room (the initial room selection is free).

inputFormat

The first line contains two integers $L$ and $R$ ($L < R$), representing the booking start day (evening) and the finish day (noon) respectively. The second line contains an integer $n$, the number of available intervals. Each of the following $n$ lines contains a capital letter (from A to Z) and two integers $s$ and $e$ ($s < e$) denoting that the corresponding room is available from the evening of day $s$ to the noon of day $e$. You may assume that if a solution exists, the intervals can be chosen so that the entire period $[L,R]$ is covered continuously.

outputFormat

Print a single integer representing the minimum number of times the guest has to transfer from one room to another to cover the entire rental period. If it is impossible to cover the period continuously with the available intervals, output -1.

sample

12 19
4
B 12 16
F 16 19
A 12 14
A 14 19

0