Timetable

You run a railway network connecting n cities numbered from 1 to n. Every train runs from its start station to its end station on a fixed timetable (always on time), without stopping anywhere in between. Each station publishes a departure timetable, and each timetable lists only direct connections.

A passenger who wants to travel from city p to city q is not restricted to direct connections — they may change trains. A change takes no time at all, but a passenger cannot switch to a train that departs before the train they are currently on arrives.

Passengers would like a timetable of all optimal connections. A connection that departs city p at time A and arrives in city q at time B is optimal if there is no other connection that departs p no earlier than A (at time ≥ A) and arrives in q no later than B (at time ≤ B). We only consider connections that can be completed within a single day.

Write a program that:

• reads n and the departure timetable of each of the n cities from standard input,
• builds the timetable of optimal connections from city 1 to city n,
• writes the answer to standard output.

The first line contains an integer n (2 ≤ n ≤ 100000). The timetables for cities 1, 2, …, n follow, in that order.

The first line of each timetable contains a single integer m. Each of the following m lines describes one timetable entry and contains a departure time A, an arrival time B (A < B), and a destination city number t (1 ≤ t ≤ n), separated by single spaces. Times A and B are given in the format hh:mm, where hh is a two-digit hour (00 ≤ hh ≤ 23) and mm is a two-digit minute (00 ≤ mm ≤ 59). Within a single timetable the entries are listed in non-decreasing order of departure time. The total number of entries across all timetables does not exceed 1000000.

The first line contains an integer r — the number of entries in the resulting timetable. Each of the following r lines contains a departure time A and an arrival time B separated by a single space. The time format must match the input, and the entries must be sorted in increasing order of departure time. If several optimal connections share the same departure and arrival time, output only one of them.