Open Data About Train Timetable

The National Railway Company of Landia decided to publish the whole train timetable information as open data. Being very enthusiastic, the web developer Andrew creates a website to include these open data. Bad surprise: the published information is just ordinary fake. Andrew analyzes very carefully the open data and discovers a lot of inconsistencies. The published information includes some fictitious trains, some trains are missing, the information about running restrictions are erroneous, etc.

Your task is to find all mismatches in a given timetable.

Input Specification

The input contains the following information:

• the first line contains the number of stations (≤ 40 000) and the number of trains (≤ 160 000);
• for each station: code (31-bit positive integer) and name (≤ 27 characters, including spaces);
• for each train: code, restriction (0: runs every day, 1: runs with restrictions), departure station code, departure time, arrival station code, arrival time (you don't need to use the train code, the departure time, and the arrival time).

Output Specification

You have to print the list of all mismatches (regarding the number of trains and restrictions). Mismatches must be lexicographically ordered by the name of the departure and arrival stations. Follow the format of the sample output.

Sample Input

1. 4 9
2. 15 Paris Est
3. 11 Roma Ovest
4. 12 Bucuresti Nord
5. 13 Budapest Keleti
6. 101 0 15 7:00 11 18:00
7. 102 0 11 8:00 15 20:00
8. 103 1 15 9:00 11 21:00
9. 201 0 12 6:00 13 23:00
10. 202 1 13 5:00 12 22:00
11. 301 0 11 6:00 13 23:30
12. 302 0 13 5:00 11 22:30
13. 203 0 12 12:00 13 10:00
14. 204 0 13 15:00 12 12:00

download as text file

Output for Sample Input

1. 12 Bucuresti Nord - 13 Budapest Keleti, restrictions
2. 15 Paris Est - 11 Roma Ovest, number of trains

download as text file

Explanation

There are two trains from Bucuresti to Budapest and two trains from Budapest to Bucuresti, but there is a mismatch regarding the restrictions.

There are two trains from Paris to Roma and one train from Roma to Paris, therefore there is a mismatch regarding the number of trains. In this case, the other type of mismatch (regarding the restrictions) is not signaled.

Note that each route with mismatches must be considered only once. For example, signal only Paris - Roma, don't signal Roma - Paris.