Рабочее место участника

Один из машинистов, работающих в метрополитене на некольцевой ветке, хочет встретиться со своими коллегами, работающими на той же ветке, и лично пригласить их к себе на юбилей. Чтобы не забыть о том, когда и с кем он может встретиться во время работы, он попросил вас составить ему расписание возможных встреч. Известно количество электропоездов на маршруте, время начала работы каждого поезда, время окончания его работы, количество станций метро на ветке, интервалы движения. Станции и электропоезда пронумерованы от единицы. Время начала и окончания работы лежат в пределах одних и тех же суток в диапазоне от 00.00 до 23.59. Движение поездов организовано так, что поезд после конечной станции встаёт в депо этой станции на отдых. Кроме того, на одной и той же станции в одно и то же время не может оказаться двух поездов, следующих в одном направлении. Начало движения каждого поезда по маршруту всегда начинается со станции номер 1.

Нужно для двух электропоездов определить, сколько раз и на каких станциях эти поезда будут встречаться в течение рабочего дня (возможно, что они никогда не встретятся). При этом встреча поездов в депо не считается встречей, поскольку в депо машинисты очень заняты и переговорить не могут.

В первой строке 3 целых числа (разделённые одним пробелом): количество электричек на маршруте `М` (`2\ ≤\ М\ <\ 100`); количество станций на маршруте `К` (`2\ ≤\ К\ ≤\ 50`); время отдыха электрички в депо на конечных станциях `В` (`1\ ≤\ В\ ≤\ 40`) минут. Во второй строке через пробел (`К-1`) число – время движения поезда между `i` и `i+1` станциями (`1\ ≤\ i\ ≤\ К-1`).

Далее в `М` строках задается для каждого электропоезда: `Т_{н}` – время выхода на маршрут и `Т_{к}` – время окончания работы (через пробел) в формате: чч.мм. Затем следует список из `L` строк-запросов (`1\ ≤\ L\ ≤\ 100`), каждая строка состоит из двух целых чисел: номеров электропоездов, движение которых на маршруте необходимо проанализировать. В последней строке списка стоят два нуля через пробел – признак конца файла.

Для каждой пары электропоездов, заданных во входном файле, выведите результаты анализа в том же порядке, как перечислены пары во входном файле.

В первой строке файла для каждой пары количество встреч `Р`, если они возможны, и 0, если не возможны. В случае ненулевого ответа далее `Р` строк, в каждой строке номер станции, на которой электрички встречаются, и время встречи в формате чч.мм. Встречи перечислить в порядке возрастания номеров станций, встречи на одной и той же станции вывести в порядке возрастания времени.

6 6 20
5 10 7 3 5
06.00 11.00
06.30 11.30
07.00 12.00
08.00 13.00
08.30 13.30
09.00 14.00
1 2
1 3
4 5
4 6
0 0

5
2 07.45
2 09.25
5 06.55
5 08.35
5 10.15
0
5
2 09.45
2 11.25
5 08.55
5 10.35
5 12.15
0