Движение по городу

Движение по городу

В городе Н-ске все улицы идут либо с севера на юг, либо с запада на восток. Расстояние между соседними улицами одинаковое, поэтому пересекаясь они образуют кварталы в виде квадратов.

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

Требуется определить минимальное время, которое необходимо затратить при движении с соблюдением знаков от перекрестка A до перекрестка B, если движение начнется в момент времени T.

Правила движения и ограничения задачи:

· движение по улицам двухстороннее;

· гарантируется, что на каждом перекрестке в каждый момент времени при подъезде с каждого направления есть хотя бы одно направление дальнейшего движения;

· возможными направлениями движения на перекрестке считаются (для перекрестка в центре города, при отсутствии запрещающих знаков): 1 - прямо, 2 - направо, 3 - в обратном направлении, 4 - налево;

· разрешается остановка перед перекрестком и ожидание времени окончания действия запрещающего знака;

· направление движения можно менять только на перекрестке;

· время движения между соседними перекрестками одинаково в пределах города и составляет величину Z;

· время движения по перекрестку принимать за 0;

· на одном и том же перекрестке при подъезде к нему с одного и того же направления не может быть более одного запрещающего знака для одного и того же направления дальнейшего движения;

· движение начинается из центра перекрестка A, поэтому знаки на этом перекрестке на первом шаге не имеют значения;

· к перекрестку B можно подъехать с любой стороны;

· перекрестки A и B не совпадают;

· гарантируется, что имеется хотя бы один путь от перекрестка A до перекрестка B.

Входной файл

Первая строка содержит два целых числа N и M, разделенных пробелом - количество улиц в городе, идущих с севера на юг и с запада на восток соответственно (2 ≤ N, M ≤ 11).

Вторая строка содержит целое число K - количество запрещающих знаков (0 ≤ K ≤ 16*N*M-14*(N+M)+8).

В каждой из K следующих строк содержится описание одного знака в формате X Y P1 P2 V1 V2, где:

· X и Y - целые числа; номера улиц, идущих с севера на юг и с запада на восток соответственно, на пересечении которых расположен перекресток, на котором установлен описываемый знак (X ≤ N; Y ≤ M);

· P1 - целое число; направление подъезда к перекрестку, на котором установлен знак; 1 - с севера, 2 - с востока, 3 - с юга, 4 - с запада;

· P2 - целое число; направление движения от перекрестка, которое запрещается знаком; 1 - прямо, 2 - направо, 3 - в обратном направлении, 4 - налево;

· V1 и V2 - время начала и окончания действия знака в формате чч:мм (00:00 ≤ V1 ≤ 23:59; 00:00 ≤ V2 ≤ 24:00; V1 ¹ V2). Например, если V1 = 06:00, а V2 = 08:00, то в 6:00 уже нельзя осуществлять движение, а в 8:00 - уже можно. Значение V2 = 24:00 используется только в диапазоне 00:00 - 24:00, означающем круглосуточный запрет движения.

Фрагменты формата разделяются пробелами.

Предпоследняя строка содержит два времени T и Z в формате чч:мм - время начала движения и время движения от перекрестка к перекрестку (00:00 ≤ T, Z ≤ 23:59).

Последняя строка содержит четыре целых числа AX, AY, BX, BY, разделенных пробелами - координаты перекрестков начала и окончания движения, где:

· A относится к перекрестку начала движения;

· B относится к перекрестку окончания движения;

· X относится к номеру улицы, идущей с севера на юг;

· Y относится к номеру улицы, идущей с запада на восток;

· 1 £ AX, BX ≤ N, 1 £ AY, BY ≤ M.

Выходной файл должен содержать два целых числа TH и TM, разделенных двоеточием (без пробелов) - минимальное время движения от перекрестка A к перекрестку B (TH ³ 0; 0 ≤ TM ≤ 59).

Пример 1:

Input. txt

4 3

4

2 2 4 1 06:00 10:30

2 2 3 2 00:00 24:00

3 1 4 2 08:00 18:30

3 3 4 4 08:30 23:00

08:00 00:30

1 2 3 2

Output. txt

2:0

Пример 2:

Input. txt

4 3

4

2 2 4 1 06:00 10:30

2 2 3 2 00:00 24:00

3 1 4 2 08:00 18:30

3 3 4 4 08:30 23:00

09:30 00:30

1 2 3 2

Output. txt

1:30