bus_driver_scheduling_sat.py

#!/usr/bin/env python3
# Copyright 2010-2024 Google LLC
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.

"""This model implements a bus driver scheduling problem.

Constraints:
- max driving time per driver <= 9h
- max working time per driver <= 12h
- min working time per driver >= 6.5h (soft)
- 30 min break after each 4h of driving time per driver
- 10 min preparation time before the first shift
- 15 min cleaning time after the last shift
- 2 min waiting time after each shift for passenger boarding and alighting
"""

import collections
import math

from absl import app
from absl import flags
from google.protobuf import text_format
from ortools.sat.python import cp_model

_OUTPUT_PROTO = flags.DEFINE_string(
    "output_proto", "", "Output file to write the cp_model proto to."
)
_PARAMS = flags.DEFINE_string(
    "params",
    "num_search_workers:16,log_search_progress:true,max_time_in_seconds:30",
    "Sat solver parameters.",
)
_INSTANCE = flags.DEFINE_integer(
    "instance", 0, "Instance to select (0, 1, 2, 3).", 0, 3
)

SAMPLE_SHIFTS_TINY = [
    #
    # column description:
    # - shift id
    # - shift start time as hh:mm string (for logging and readability purposes)
    # - shift end time as hh:mm string (for logging and readability purposes)
    # - shift start minute
    # - shift end minute
    # - shift duration in minutes
    #
    [1, "08:00", "09:05", 480, 545, 65],
    [2, "08:00", "08:35", 480, 515, 35],
    [3, "08:11", "09:41", 491, 581, 90],
    [4, "08:28", "08:50", 508, 530, 22],
    [5, "08:35", "08:45", 515, 525, 10],
    [6, "08:40", "08:50", 520, 530, 10],
    [7, "09:03", "10:28", 543, 628, 85],
    [8, "09:23", "09:49", 563, 589, 26],
    [9, "09:30", "09:40", 570, 580, 10],
    [10, "09:57", "10:20", 597, 620, 23],
    [11, "10:09", "11:03", 609, 663, 54],
    [12, "10:20", "10:30", 620, 630, 10],
    [13, "11:00", "11:10", 660, 670, 10],
    [14, "11:45", "12:24", 705, 744, 39],
    [15, "12:18", "13:00", 738, 780, 42],
    [16, "13:18", "14:44", 798, 884, 86],
    [17, "13:53", "14:49", 833, 889, 56],
    [18, "14:03", "14:50", 843, 890, 47],
    [19, "14:28", "15:15", 868, 915, 47],
    [20, "14:30", "15:41", 870, 941, 71],
    [21, "14:48", "15:35", 888, 935, 47],
    [22, "15:03", "15:50", 903, 950, 47],
    [23, "15:28", "16:54", 928, 1014, 86],
    [24, "15:38", "16:25", 938, 985, 47],
    [25, "15:40", "15:56", 940, 956, 16],
    [26, "15:58", "16:45", 958, 1005, 47],
    [27, "16:04", "17:30", 964, 1050, 86],
]  # yapf:disable

SAMPLE_SHIFTS_SMALL = [
    #
    # column description:
    # - shift id
    # - shift start time as hh:mm string (for logging and readability purposes)
    # - shift end time as hh:mm string (for logging and readability purposes)
    # - shift start minute
    # - shift end minute
    # - shift duration in minutes
    #
    [0, "05:18", "06:00", 318, 360, 42],
    [1, "05:26", "06:08", 326, 368, 42],
    [2, "05:40", "05:56", 340, 356, 16],
    [3, "06:06", "06:51", 366, 411, 45],
    [4, "06:40", "07:52", 400, 472, 72],
    [5, "06:42", "07:13", 402, 433, 31],
    [6, "06:48", "08:15", 408, 495, 87],
    [7, "06:59", "08:07", 419, 487, 68],
    [8, "07:20", "07:36", 440, 456, 16],
    [9, "07:35", "08:22", 455, 502, 47],
    [10, "07:50", "08:55", 470, 535, 65],
    [11, "08:00", "09:05", 480, 545, 65],
    [12, "08:00", "08:35", 480, 515, 35],
    [13, "08:11", "09:41", 491, 581, 90],
    [14, "08:28", "08:50", 508, 530, 22],
    [15, "08:35", "08:45", 515, 525, 10],
    [16, "08:40", "08:50", 520, 530, 10],
    [17, "09:03", "10:28", 543, 628, 85],
    [18, "09:23", "09:49", 563, 589, 26],
    [19, "09:30", "09:40", 570, 580, 10],
    [20, "09:57", "10:20", 597, 620, 23],
    [21, "10:09", "11:03", 609, 663, 54],
    [22, "10:20", "10:30", 620, 630, 10],
    [23, "11:00", "11:10", 660, 670, 10],
    [24, "11:45", "12:24", 705, 744, 39],
    [25, "12:18", "13:00", 738, 780, 42],
    [26, "13:18", "14:44", 798, 884, 86],
    [27, "13:53", "14:49", 833, 889, 56],
    [28, "14:03", "14:50", 843, 890, 47],
    [29, "14:28", "15:15", 868, 915, 47],
    [30, "14:30", "15:41", 870, 941, 71],
    [31, "14:48", "15:35", 888, 935, 47],
    [32, "15:03", "15:50", 903, 950, 47],
    [33, "15:28", "16:54", 928, 1014, 86],
    [34, "15:38", "16:25", 938, 985, 47],
    [35, "15:40", "15:56", 940, 956, 16],
    [36, "15:58", "16:45", 958, 1005, 47],
    [37, "16:04", "17:30", 964, 1050, 86],
    [38, "16:28", "17:15", 988, 1035, 47],
    [39, "16:36", "17:21", 996, 1041, 45],
    [40, "16:50", "17:00", 1010, 1020, 10],
    [41, "16:54", "18:20", 1014, 1100, 86],
    [42, "17:01", "17:13", 1021, 1033, 12],
    [43, "17:19", "18:31", 1039, 1111, 72],
    [44, "17:23", "18:10", 1043, 1090, 47],
    [45, "17:34", "18:15", 1054, 1095, 41],
    [46, "18:04", "19:29", 1084, 1169, 85],
    [47, "18:34", "19:58", 1114, 1198, 84],
    [48, "19:56", "20:34", 1196, 1234, 38],
    [49, "20:05", "20:48", 1205, 1248, 43],
]  # yapf:disable

SAMPLE_SHIFTS_MEDIUM = [
    [0, "04:30", "04:53", 270, 293, 23],
    [1, "04:46", "04:56", 286, 296, 10],
    [2, "04:52", "05:56", 292, 356, 64],
    [3, "04:53", "05:23", 293, 323, 30],
    [4, "05:07", "05:44", 307, 344, 37],
    [5, "05:10", "06:06", 310, 366, 56],
    [6, "05:18", "06:03", 318, 363, 45],
    [7, "05:30", "05:40", 330, 340, 10],
    [8, "05:30", "05:40", 330, 340, 10],
    [9, "05:33", "06:15", 333, 375, 42],
    [10, "05:40", "05:50", 340, 350, 10],
    [11, "05:43", "06:08", 343, 368, 25],
    [12, "05:54", "07:20", 354, 440, 86],
    [13, "06:04", "06:37", 364, 397, 33],
    [14, "06:13", "06:58", 373, 418, 45],
    [15, "06:14", "07:40", 374, 460, 86],
    [16, "06:15", "07:15", 375, 435, 60],
    [17, "06:16", "06:26", 376, 386, 10],
    [18, "06:17", "06:34", 377, 394, 17],
    [19, "06:20", "06:36", 380, 396, 16],
    [20, "06:22", "07:06", 382, 426, 44],
    [21, "06:24", "07:50", 384, 470, 86],
    [22, "06:27", "06:44", 387, 404, 17],
    [23, "06:30", "06:40", 390, 400, 10],
    [24, "06:31", "06:43", 391, 403, 12],
    [25, "06:33", "07:53", 393, 473, 80],
    [26, "06:34", "07:09", 394, 429, 35],
    [27, "06:40", "06:56", 400, 416, 16],
    [28, "06:44", "07:17", 404, 437, 33],
    [29, "06:46", "06:58", 406, 418, 12],
    [30, "06:49", "07:43", 409, 463, 54],
    [31, "06:50", "07:05", 410, 425, 15],
    [32, "06:52", "07:36", 412, 456, 44],
    [33, "06:54", "07:27", 414, 447, 33],
    [34, "06:56", "08:23", 416, 503, 87],
    [35, "07:04", "07:44", 424, 464, 40],
    [36, "07:11", "08:36", 431, 516, 85],
    [37, "07:17", "07:35", 437, 455, 18],
    [38, "07:22", "08:06", 442, 486, 44],
    [39, "07:27", "08:15", 447, 495, 48],
    [40, "07:35", "07:45", 455, 465, 10],
    [41, "07:43", "08:08", 463, 488, 25],
    [42, "07:50", "08:37", 470, 517, 47],
    [43, "07:58", "08:45", 478, 525, 47],
    [44, "08:00", "08:35", 480, 515, 35],
    [45, "08:06", "08:51", 486, 531, 45],
    [46, "08:10", "08:45", 490, 525, 35],
    [47, "08:15", "08:30", 495, 510, 15],
    [48, "08:16", "09:00", 496, 540, 44],
    [49, "08:18", "09:16", 498, 556, 58],
    [50, "08:20", "08:36", 500, 516, 16],
    [51, "08:27", "09:07", 507, 547, 40],
    [52, "08:30", "08:45", 510, 525, 15],
    [53, "08:35", "09:15", 515, 555, 40],
    [54, "08:46", "09:30", 526, 570, 44],
    [55, "08:51", "09:17", 531, 557, 26],
    [56, "08:55", "09:15", 535, 555, 20],
    [57, "08:58", "09:38", 538, 578, 40],
    [58, "09:00", "09:35", 540, 575, 35],
    [59, "09:00", "09:16", 540, 556, 16],
    [60, "09:20", "09:36", 560, 576, 16],
    [61, "09:31", "09:43", 571, 583, 12],
    [62, "09:33", "10:15", 573, 615, 42],
    [63, "09:54", "10:05", 594, 605, 11],
    [64, "10:11", "10:38", 611, 638, 27],
    [65, "10:18", "11:00", 618, 660, 42],
    [66, "10:21", "10:47", 621, 647, 26],
    [67, "10:25", "11:04", 625, 664, 39],
    [68, "10:26", "11:08", 626, 668, 42],
    [69, "10:44", "12:11", 644, 731, 87],
    [70, "11:00", "11:16", 660, 676, 16],
    [71, "11:15", "11:54", 675, 714, 39],
    [72, "11:16", "11:28", 676, 688, 12],
    [73, "11:20", "11:30", 680, 690, 10],
    [74, "11:21", "11:47", 681, 707, 26],
    [75, "11:25", "12:04", 685, 724, 39],
    [76, "11:34", "11:45", 694, 705, 11],
    [77, "11:35", "12:14", 695, 734, 39],
    [78, "11:41", "12:23", 701, 743, 42],
    [79, "11:44", "12:35", 704, 755, 51],
    [80, "11:46", "11:58", 706, 718, 12],
    [81, "12:00", "12:10", 720, 730, 10],
    [82, "12:04", "12:15", 724, 735, 11],
    [83, "12:04", "13:04", 724, 784, 60],
    [84, "12:11", "12:38", 731, 758, 27],
    [85, "12:15", "12:54", 735, 774, 39],
    [86, "12:25", "13:10", 745, 790, 45],
    [87, "12:30", "12:40", 750, 760, 10],
    [88, "12:34", "13:58", 754, 838, 84],
    [89, "12:38", "13:25", 758, 805, 47],
    [90, "12:48", "13:35", 768, 815, 47],
    [91, "13:00", "13:16", 780, 796, 16],
    [92, "13:05", "13:44", 785, 824, 39],
    [93, "13:08", "13:55", 788, 835, 47],
    [94, "13:14", "14:38", 794, 878, 84],
    [95, "13:23", "13:49", 803, 829, 26],
    [96, "13:25", "14:04", 805, 844, 39],
    [97, "13:28", "14:54", 808, 894, 86],
    [98, "13:31", "13:43", 811, 823, 12],
    [99, "13:34", "14:58", 814, 898, 84],
    [100, "13:38", "14:25", 818, 865, 47],
    [101, "13:38", "15:04", 818, 904, 86],
    [102, "13:39", "14:33", 819, 873, 54],
    [103, "13:40", "13:50", 820, 830, 10],
    [104, "13:43", "14:10", 823, 850, 27],
    [105, "13:48", "14:35", 828, 875, 47],
    [106, "13:48", "14:35", 828, 875, 47],
    [107, "13:53", "14:40", 833, 880, 47],
    [108, "13:58", "15:24", 838, 924, 86],
    [109, "13:58", "14:25", 838, 865, 27],
    [110, "14:00", "14:16", 840, 856, 16],
    [111, "14:13", "15:00", 853, 900, 47],
    [112, "14:20", "15:31", 860, 931, 71],
    [113, "14:25", "15:02", 865, 902, 37],
    [114, "14:34", "14:45", 874, 885, 11],
    [115, "14:40", "15:51", 880, 951, 71],
    [116, "14:40", "14:56", 880, 896, 16],
    [117, "14:46", "14:58", 886, 898, 12],
    [118, "14:49", "15:43", 889, 943, 54],
    [119, "14:52", "15:21", 892, 921, 29],
    [120, "14:58", "16:24", 898, 984, 86],
    [121, "14:59", "15:53", 899, 953, 54],
    [122, "15:00", "15:10", 900, 910, 10],
    [123, "15:00", "15:35", 900, 935, 35],
    [124, "15:08", "15:45", 908, 945, 37],
    [125, "15:12", "15:36", 912, 936, 24],
    [126, "15:18", "16:05", 918, 965, 47],
    [127, "15:24", "16:05", 924, 965, 41],
    [128, "15:31", "15:43", 931, 943, 12],
    [129, "15:35", "15:54", 935, 954, 19],
    [130, "15:36", "16:21", 936, 981, 45],
    [131, "15:39", "16:33", 939, 993, 54],
    [132, "15:48", "16:35", 948, 995, 47],
    [133, "15:50", "17:01", 950, 1021, 71],
    [134, "16:03", "16:50", 963, 1010, 47],
    [135, "16:18", "17:44", 978, 1064, 86],
    [136, "16:24", "17:05", 984, 1025, 41],
    [137, "16:28", "17:15", 988, 1035, 47],
    [138, "16:34", "17:15", 994, 1035, 41],
    [139, "16:38", "17:25", 998, 1045, 47],
    [140, "16:40", "16:56", 1000, 1016, 16],
    [141, "16:45", "17:04", 1005, 1024, 19],
    [142, "16:52", "17:36", 1012, 1056, 44],
    [143, "16:58", "17:45", 1018, 1065, 47],
    [144, "17:04", "18:30", 1024, 1110, 86],
    [145, "17:04", "17:45", 1024, 1065, 41],
    [146, "17:09", "18:03", 1029, 1083, 54],
    [147, "17:18", "18:44", 1038, 1124, 86],
    [148, "17:28", "18:15", 1048, 1095, 47],
    [149, "17:29", "18:41", 1049, 1121, 72],
    [150, "17:36", "18:21", 1056, 1101, 45],
    [151, "17:38", "18:25", 1058, 1105, 47],
    [152, "17:40", "17:56", 1060, 1076, 16],
    [153, "17:45", "18:04", 1065, 1084, 19],
    [154, "17:46", "17:58", 1066, 1078, 12],
    [155, "17:48", "18:35", 1068, 1115, 47],
    [156, "17:49", "18:43", 1069, 1123, 54],
    [157, "17:55", "18:14", 1075, 1094, 19],
    [158, "17:58", "18:45", 1078, 1125, 47],
    [159, "18:00", "19:11", 1080, 1151, 71],
    [160, "18:04", "18:45", 1084, 1125, 41],
    [161, "18:09", "19:03", 1089, 1143, 54],
    [162, "18:13", "19:00", 1093, 1140, 47],
    [163, "18:13", "18:40", 1093, 1120, 27],
    [164, "18:19", "19:13", 1099, 1153, 54],
    [165, "18:28", "19:25", 1108, 1165, 57],
    [166, "18:48", "19:28", 1128, 1168, 40],
    [167, "19:03", "19:45", 1143, 1185, 42],
    [168, "19:20", "19:36", 1160, 1176, 16],
    [169, "19:21", "19:31", 1161, 1171, 10],
    [170, "19:25", "20:04", 1165, 1204, 39],
    [171, "19:26", "20:08", 1166, 1208, 42],
    [172, "19:30", "19:40", 1170, 1180, 10],
    [173, "19:44", "20:33", 1184, 1233, 49],
    [174, "19:48", "21:09", 1188, 1269, 81],
    [175, "19:53", "21:02", 1193, 1262, 69],
    [176, "20:04", "20:29", 1204, 1229, 25],
    [177, "20:17", "21:03", 1217, 1263, 46],
    [178, "20:20", "20:57", 1220, 1257, 37],
    [179, "20:29", "21:18", 1229, 1278, 49],
    [180, "20:35", "21:54", 1235, 1314, 79],
    [181, "20:40", "20:50", 1240, 1250, 10],
    [182, "20:47", "21:42", 1247, 1302, 55],
    [183, "21:00", "21:10", 1260, 1270, 10],
    [184, "21:07", "21:44", 1267, 1304, 37],
    [185, "21:14", "22:03", 1274, 1323, 49],
    [186, "21:39", "21:55", 1299, 1315, 16],
    [187, "21:40", "22:17", 1300, 1337, 37],
    [188, "21:40", "21:50", 1300, 1310, 10],
    [189, "21:48", "22:03", 1308, 1323, 15],
    [190, "22:17", "23:03", 1337, 1383, 46],
    [191, "22:43", "23:08", 1363, 1388, 25],
    [192, "23:35", "01:05", 1415, 1505, 90],
    [193, "23:46", "00:01", 1426, 1441, 15],
    [194, "23:47", "00:33", 1427, 1473, 46],
    [195, "23:52", "00:24", 1432, 1464, 32],
    [196, "23:58", "00:38", 1438, 1478, 40],
    [197, "00:02", "00:12", 1442, 1452, 10],
    [198, "00:07", "00:39", 1447, 1479, 32],
    [199, "00:25", "01:12", 1465, 1512, 47],
]  # yapf:disable

SAMPLE_SHIFTS_LARGE = [
    [0, "04:18", "05:00", 258, 300, 42],
    [1, "04:27", "05:08", 267, 308, 41],
    [2, "04:29", "05:26", 269, 326, 57],
    [3, "04:29", "04:55", 269, 295, 26],
    [4, "04:30", "04:53", 270, 293, 23],
    [5, "04:30", "04:51", 270, 291, 21],
    [6, "04:31", "04:53", 271, 293, 22],
    [7, "04:33", "05:15", 273, 315, 42],
    [8, "04:34", "04:44", 274, 284, 10],
    [9, "04:34", "05:03", 274, 303, 29],
    [10, "04:35", "04:50", 275, 290, 15],
    [11, "04:36", "04:46", 276, 286, 10],
    [12, "04:37", "05:18", 277, 318, 41],
    [13, "04:41", "05:13", 281, 313, 32],
    [14, "04:42", "05:23", 282, 323, 41],
    [15, "04:43", "04:53", 283, 293, 10],
    [16, "04:44", "05:45", 284, 345, 61],
    [17, "04:45", "05:11", 285, 311, 26],
    [18, "04:46", "05:01", 286, 301, 15],
    [19, "04:46", "04:56", 286, 296, 10],
    [20, "04:47", "05:14", 287, 314, 27],
    [21, "04:48", "05:30", 288, 330, 42],
    [22, "04:49", "05:41", 289, 341, 52],
    [23, "04:49", "05:18", 289, 318, 29],
    [24, "04:50", "05:33", 290, 333, 43],
    [25, "04:52", "05:56", 292, 356, 64],
    [26, "04:52", "05:07", 292, 307, 15],
    [27, "04:53", "05:19", 293, 319, 26],
    [28, "04:53", "05:23", 293, 323, 30],
    [29, "04:55", "05:27", 295, 327, 32],
    [30, "04:57", "05:38", 297, 338, 41],
    [31, "05:00", "06:00", 300, 360, 60],
    [32, "05:00", "05:54", 300, 354, 54],
    [33, "05:01", "05:33", 301, 333, 32],
    [34, "05:01", "05:26", 301, 326, 25],
    [35, "05:02", "05:29", 302, 329, 27],
    [36, "05:02", "05:12", 302, 312, 10],
    [37, "05:03", "05:45", 303, 345, 42],
    [38, "05:03", "05:18", 303, 318, 15],
    [39, "05:03", "06:28", 303, 388, 85],
    [40, "05:03", "05:13", 303, 313, 10],
    [41, "05:04", "06:24", 304, 384, 80],
    [42, "05:07", "05:44", 307, 344, 37],
    [43, "05:08", "05:48", 308, 348, 40],
    [44, "05:10", "06:06", 310, 366, 56],
    [45, "05:11", "05:37", 311, 337, 26],
    [46, "05:11", "05:53", 311, 353, 42],
    [47, "05:13", "06:15", 313, 375, 62],
    [48, "05:13", "05:38", 313, 338, 25],
    [49, "05:16", "05:44", 316, 344, 28],
    [50, "05:17", "05:27", 317, 327, 10],
    [51, "05:18", "06:40", 318, 400, 82],
    [52, "05:18", "06:03", 318, 363, 45],
    [53, "05:18", "06:11", 318, 371, 53],
    [54, "05:18", "06:00", 318, 360, 42],
    [55, "05:19", "06:34", 319, 394, 75],
    [56, "05:20", "06:17", 320, 377, 57],
    [57, "05:22", "05:59", 322, 359, 37],
    [58, "05:24", "05:48", 324, 348, 24],
    [59, "05:25", "05:40", 325, 340, 15],
    [60, "05:26", "06:08", 326, 368, 42],
    [61, "05:27", "06:30", 327, 390, 63],
    [62, "05:27", "05:54", 327, 354, 27],
    [63, "05:28", "05:53", 328, 353, 25],
    [64, "05:29", "05:44", 329, 344, 15],
    [65, "05:30", "05:40", 330, 340, 10],
    [66, "05:30", "05:40", 330, 340, 10],
    [67, "05:30", "05:40", 330, 340, 10],
    [68, "05:32", "06:53", 332, 413, 81],
    [69, "05:33", "07:00", 333, 420, 87],
    [70, "05:33", "06:15", 333, 375, 42],
    [71, "05:33", "05:47", 333, 347, 14],
    [72, "05:37", "06:13", 337, 373, 36],
    [73, "05:37", "06:05", 337, 365, 28],
    [74, "05:38", "06:33", 338, 393, 55],
    [75, "05:38", "06:04", 338, 364, 26],
    [76, "05:38", "06:18", 338, 378, 40],
    [77, "05:39", "05:54", 339, 354, 15],
    [78, "05:40", "05:56", 340, 356, 16],
    [79, "05:40", "06:41", 340, 401, 61],
    [80, "05:40", "05:50", 340, 350, 10],
    [81, "05:41", "06:23", 341, 383, 42],
    [82, "05:41", "06:01", 341, 361, 20],
    [83, "05:43", "06:08", 343, 368, 25],
    [84, "05:44", "07:10", 344, 430, 86],
    [85, "05:44", "05:55", 344, 355, 11],
    [86, "05:45", "06:44", 345, 404, 59],
    [87, "05:47", "06:17", 347, 377, 30],
    [88, "05:48", "07:08", 348, 428, 80],
    [89, "05:48", "06:30", 348, 390, 42],
    [90, "05:50", "06:50", 350, 410, 60],
    [91, "05:50", "06:00", 350, 360, 10],
    [92, "05:50", "06:00", 350, 360, 10],
    [93, "05:50", "06:51", 350, 411, 61],
    [94, "05:52", "06:33", 352, 393, 41],
    [95, "05:52", "06:36", 352, 396, 44],
    [96, "05:52", "06:23", 352, 383, 31],
    [97, "05:54", "06:14", 354, 374, 20],
    [98, "05:54", "07:20", 354, 440, 86],
    [99, "05:55", "06:40", 355, 400, 45],
    [100, "05:55", "06:27", 355, 387, 32],
    [101, "05:56", "06:35", 356, 395, 39],
    [102, "05:56", "06:06", 356, 366, 10],
    [103, "05:57", "06:21", 357, 381, 24],
    [104, "05:58", "07:23", 358, 443, 85],
    [105, "05:58", "06:23", 358, 383, 25],
    [106, "05:58", "06:08", 358, 368, 10],
    [107, "05:58", "06:43", 358, 403, 45],
    [108, "06:00", "06:10", 360, 370, 10],
    [109, "06:00", "06:16", 360, 376, 16],
    [110, "06:00", "07:01", 360, 421, 61],
    [111, "06:01", "07:00", 361, 420, 59],
    [112, "06:01", "06:13", 361, 373, 12],
    [113, "06:01", "06:45", 361, 405, 44],
    [114, "06:03", "06:50", 363, 410, 47],
    [115, "06:04", "06:37", 364, 397, 33],
    [116, "06:04", "07:30", 364, 450, 86],
    [117, "06:05", "06:24", 365, 384, 19],
    [118, "06:06", "06:51", 366, 411, 45],
    [119, "06:07", "06:43", 367, 403, 36],
    [120, "06:08", "07:30", 368, 450, 82],
    [121, "06:10", "06:20", 370, 380, 10],
    [122, "06:10", "07:17", 370, 437, 67],
    [123, "06:11", "06:54", 371, 414, 43],
    [124, "06:11", "06:21", 371, 381, 10],
    [125, "06:13", "06:38", 373, 398, 25],
    [126, "06:13", "06:58", 373, 418, 45],
    [127, "06:13", "06:53", 373, 413, 40],
    [128, "06:14", "07:03", 374, 423, 49],
    [129, "06:14", "06:47", 374, 407, 33],
    [130, "06:14", "07:40", 374, 460, 86],
    [131, "06:15", "07:15", 375, 435, 60],
    [132, "06:16", "06:28", 376, 388, 12],
    [133, "06:16", "06:26", 376, 386, 10],
    [134, "06:17", "06:34", 377, 394, 17],
    [135, "06:18", "07:06", 378, 426, 48],
    [136, "06:18", "07:38", 378, 458, 80],
    [137, "06:18", "07:02", 378, 422, 44],
    [138, "06:19", "06:53", 379, 413, 34],
    [139, "06:20", "07:25", 380, 445, 65],
    [140, "06:20", "06:36", 380, 396, 16],
    [141, "06:20", "06:30", 380, 390, 10],
    [142, "06:20", "06:30", 380, 390, 10],
    [143, "06:21", "06:49", 381, 409, 28],
    [144, "06:22", "07:06", 382, 426, 44],
    [145, "06:24", "07:50", 384, 470, 86],
    [146, "06:24", "06:57", 384, 417, 33],
    [147, "06:26", "07:45", 386, 465, 79],
    [148, "06:26", "07:10", 386, 430, 44],
    [149, "06:27", "06:44", 387, 404, 17],
    [150, "06:28", "06:53", 388, 413, 25],
    [151, "06:28", "07:14", 388, 434, 46],
    [152, "06:29", "07:03", 389, 423, 34],
    [153, "06:30", "06:40", 390, 400, 10],
    [154, "06:30", "07:37", 390, 457, 67],
    [155, "06:31", "06:43", 391, 403, 12],
    [156, "06:33", "07:14", 393, 434, 41],
    [157, "06:33", "07:53", 393, 473, 80],
    [158, "06:34", "08:16", 394, 496, 102],
    [159, "06:34", "07:09", 394, 429, 35],
    [160, "06:34", "07:07", 394, 427, 33],
    [161, "06:36", "07:21", 396, 441, 45],
    [162, "06:37", "07:22", 397, 442, 45],
    [163, "06:37", "06:54", 397, 414, 17],
    [164, "06:38", "07:30", 398, 450, 52],
    [165, "06:38", "07:18", 398, 438, 40],
    [166, "06:39", "07:33", 399, 453, 54],
    [167, "06:40", "07:52", 400, 472, 72],
    [168, "06:40", "06:50", 400, 410, 10],
    [169, "06:40", "07:22", 400, 442, 42],
    [170, "06:40", "06:56", 400, 416, 16],
    [171, "06:41", "08:00", 401, 480, 79],
    [172, "06:42", "07:26", 402, 446, 44],
    [173, "06:42", "07:13", 402, 433, 31],
    [174, "06:43", "07:08", 403, 428, 25],
    [175, "06:43", "07:30", 403, 450, 47],
    [176, "06:43", "07:23", 403, 443, 40],
    [177, "06:44", "07:17", 404, 437, 33],
    [178, "06:44", "08:13", 404, 493, 89],
    [179, "06:46", "07:01", 406, 421, 15],
    [180, "06:46", "06:58", 406, 418, 12],
    [181, "06:47", "07:04", 407, 424, 17],
    [182, "06:48", "08:15", 408, 495, 87],
    [183, "06:48", "07:34", 408, 454, 46],
    [184, "06:48", "07:37", 408, 457, 49],
    [185, "06:49", "07:43", 409, 463, 54],
    [186, "06:50", "08:00", 410, 480, 70],
    [187, "06:50", "07:00", 410, 420, 10],
    [188, "06:50", "07:05", 410, 425, 15],
    [189, "06:51", "07:18", 411, 438, 27],
    [190, "06:52", "07:36", 412, 456, 44],
    [191, "06:53", "07:37", 413, 457, 44],
    [192, "06:54", "08:20", 414, 500, 86],
    [193, "06:54", "07:27", 414, 447, 33],
    [194, "06:54", "07:20", 414, 440, 26],
    [195, "06:56", "08:23", 416, 503, 87],
    [196, "06:57", "07:12", 417, 432, 15],
    [197, "06:57", "07:58", 417, 478, 61],
    [198, "06:57", "07:45", 417, 465, 48],
    [199, "06:57", "07:40", 417, 460, 43],
    [200, "06:58", "07:23", 418, 443, 25],
    [201, "06:59", "07:53", 419, 473, 54],
    [202, "06:59", "08:07", 419, 487, 68],
    [203, "07:00", "07:10", 420, 430, 10],
    [204, "07:00", "07:16", 420, 436, 16],
    [205, "07:01", "08:30", 421, 510, 89],
    [206, "07:01", "07:13", 421, 433, 12],
    [207, "07:01", "07:43", 421, 463, 42],
    [208, "07:03", "08:30", 423, 510, 87],
    [209, "07:04", "07:37", 424, 457, 33],
    [210, "07:04", "07:44", 424, 464, 40],
    [211, "07:05", "07:52", 425, 472, 47],
    [212, "07:05", "08:05", 425, 485, 60],
    [213, "07:05", "07:46", 425, 466, 41],
    [214, "07:06", "07:51", 426, 471, 45],
    [215, "07:07", "08:08", 427, 488, 61],
    [216, "07:07", "07:52", 427, 472, 45],
    [217, "07:07", "08:16", 427, 496, 69],
    [218, "07:07", "07:27", 427, 447, 20],
    [219, "07:09", "07:50", 429, 470, 41],
    [220, "07:09", "08:40", 429, 520, 91],
    [221, "07:09", "08:03", 429, 483, 54],
    [222, "07:10", "07:20", 430, 440, 10],
    [223, "07:11", "08:36", 431, 516, 85],
    [224, "07:12", "08:00", 432, 480, 48],
    [225, "07:12", "07:47", 432, 467, 35],
    [226, "07:13", "07:54", 433, 474, 41],
    [227, "07:13", "07:38", 433, 458, 25],
    [228, "07:14", "07:59", 434, 479, 45],
    [229, "07:16", "08:50", 436, 530, 94],
    [230, "07:16", "07:28", 436, 448, 12],
    [231, "07:17", "07:35", 437, 455, 18],
    [232, "07:17", "07:58", 437, 478, 41],
    [233, "07:18", "08:06", 438, 486, 48],
    [234, "07:18", "08:44", 438, 524, 86],
    [235, "07:19", "08:13", 439, 493, 54],
    [236, "07:20", "08:02", 440, 482, 42],
    [237, "07:20", "08:07", 440, 487, 47],
    [238, "07:20", "07:30", 440, 450, 10],
    [239, "07:20", "07:57", 440, 477, 37],
    [240, "07:20", "07:36", 440, 456, 16],
    [241, "07:21", "07:48", 441, 468, 27],
    [242, "07:22", "08:06", 442, 486, 44],
    [243, "07:22", "08:25", 442, 505, 63],
    [244, "07:24", "08:27", 444, 507, 63],
    [245, "07:24", "08:05", 444, 485, 41],
    [246, "07:26", "08:23", 446, 503, 57],
    [247, "07:26", "08:52", 446, 532, 86],
    [248, "07:27", "08:07", 447, 487, 40],
    [249, "07:27", "07:42", 447, 462, 15],
    [250, "07:27", "08:15", 447, 495, 48],
    [251, "07:28", "07:53", 448, 473, 25],
    [252, "07:28", "08:09", 448, 489, 41],
    [253, "07:28", "07:38", 448, 458, 10],
    [254, "07:30", "08:35", 450, 515, 65],
    [255, "07:31", "07:43", 451, 463, 12],
    [256, "07:32", "08:13", 452, 493, 41],
    [257, "07:34", "09:00", 454, 540, 86],
    [258, "07:34", "08:33", 454, 513, 59],
    [259, "07:34", "09:04", 454, 544, 90],
    [260, "07:35", "08:22", 455, 502, 47],
    [261, "07:35", "07:45", 455, 465, 10],
    [262, "07:35", "08:16", 455, 496, 41],
    [263, "07:36", "08:17", 456, 497, 41],
    [264, "07:36", "08:36", 456, 516, 60],
    [265, "07:37", "07:50", 457, 470, 13],
    [266, "07:40", "07:56", 460, 476, 16],
    [267, "07:40", "08:20", 460, 500, 40],
    [268, "07:40", "08:45", 460, 525, 65],
    [269, "07:41", "08:39", 461, 519, 58],
    [270, "07:41", "07:51", 461, 471, 10],
    [271, "07:42", "08:30", 462, 510, 48],
    [272, "07:42", "08:21", 462, 501, 39],
    [273, "07:43", "08:08", 463, 488, 25],
    [274, "07:43", "08:24", 463, 504, 41],
    [275, "07:44", "09:10", 464, 550, 86],
    [276, "07:44", "08:43", 464, 523, 59],
    [277, "07:46", "08:28", 466, 508, 42],
    [278, "07:46", "07:58", 466, 478, 12],
    [279, "07:47", "08:00", 467, 480, 13],
    [280, "07:48", "09:14", 468, 554, 86],
    [281, "07:49", "08:32", 469, 512, 43],
    [282, "07:50", "08:55", 470, 535, 65],
    [283, "07:50", "08:00", 470, 480, 10],
    [284, "07:50", "08:37", 470, 517, 47],
    [285, "07:50", "08:26", 470, 506, 36],
    [286, "07:51", "08:18", 471, 498, 27],
    [287, "07:52", "08:21", 472, 501, 29],
    [288, "07:53", "08:35", 473, 515, 42],
    [289, "07:54", "09:19", 474, 559, 85],
    [290, "07:55", "08:53", 475, 533, 58],
    [291, "07:56", "08:54", 476, 534, 58],
    [292, "07:57", "08:39", 477, 519, 42],
    [293, "07:57", "08:10", 477, 490, 13],
    [294, "07:58", "08:45", 478, 525, 47],
    [295, "07:58", "08:23", 478, 503, 25],
    [296, "08:00", "08:10", 480, 490, 10],
    [297, "08:00", "09:05", 480, 545, 65],
    [298, "08:00", "08:16", 480, 496, 16],
    [299, "08:00", "08:35", 480, 515, 35],
    [300, "08:01", "08:13", 481, 493, 12],
    [301, "08:01", "08:43", 481, 523, 42],
    [302, "08:03", "09:26", 483, 566, 83],
    [303, "08:04", "09:29", 484, 569, 85],
    [304, "08:05", "08:21", 485, 501, 16],
    [305, "08:05", "08:47", 485, 527, 42],
    [306, "08:06", "08:51", 486, 531, 45],
    [307, "08:06", "09:03", 486, 543, 57],
    [308, "08:07", "08:20", 487, 500, 13],
    [309, "08:08", "08:55", 488, 535, 47],
    [310, "08:08", "08:50", 488, 530, 42],
    [311, "08:10", "08:45", 490, 525, 35],
    [312, "08:10", "09:15", 490, 555, 65],
    [313, "08:10", "08:20", 490, 500, 10],
    [314, "08:11", "09:41", 491, 581, 90],
    [315, "08:12", "08:55", 492, 535, 43],
    [316, "08:13", "08:38", 493, 518, 25],
    [317, "08:14", "09:38", 494, 578, 84],
    [318, "08:15", "08:30", 495, 510, 15],
    [319, "08:16", "08:30", 496, 510, 14],
    [320, "08:16", "08:28", 496, 508, 12],
    [321, "08:16", "09:00", 496, 540, 44],
    [322, "08:17", "09:13", 497, 553, 56],
    [323, "08:18", "09:16", 498, 556, 58],
    [324, "08:18", "09:05", 498, 545, 47],
    [325, "08:20", "08:36", 500, 516, 16],
    [326, "08:20", "08:55", 500, 535, 35],
    [327, "08:20", "09:05", 500, 545, 45],
    [328, "08:20", "08:30", 500, 510, 10],
    [329, "08:20", "09:25", 500, 565, 65],
    [330, "08:21", "08:38", 501, 518, 17],
    [331, "08:21", "08:47", 501, 527, 26],
    [332, "08:22", "08:45", 502, 525, 23],
    [333, "08:23", "09:10", 503, 550, 47],
    [334, "08:24", "09:48", 504, 588, 84],
    [335, "08:26", "08:46", 506, 526, 20],
    [336, "08:27", "09:07", 507, 547, 40],
    [337, "08:28", "08:50", 508, 530, 22],
    [338, "08:28", "09:56", 508, 596, 88],
    [339, "08:28", "09:23", 508, 563, 55],
    [340, "08:29", "09:20", 509, 560, 51],
    [341, "08:30", "09:05", 510, 545, 35],
    [342, "08:30", "08:45", 510, 525, 15],
    [343, "08:30", "08:40", 510, 520, 10],
    [344, "08:30", "09:35", 510, 575, 65],
    [345, "08:31", "08:43", 511, 523, 12],
    [346, "08:31", "09:13", 511, 553, 42],
    [347, "08:34", "09:58", 514, 598, 84],
    [348, "08:35", "08:55", 515, 535, 20],
    [349, "08:35", "09:15", 515, 555, 40],
    [350, "08:35", "08:45", 515, 525, 10],
    [351, "08:36", "08:46", 516, 526, 10],
    [352, "08:36", "09:00", 516, 540, 24],
    [353, "08:38", "09:20", 518, 560, 42],
    [354, "08:38", "09:35", 518, 575, 57],
    [355, "08:38", "09:14", 518, 554, 36],
    [356, "08:39", "09:33", 519, 573, 54],
    [357, "08:40", "09:45", 520, 585, 65],
    [358, "08:40", "08:50", 520, 530, 10],
    [359, "08:40", "08:56", 520, 536, 16],
    [360, "08:42", "09:25", 522, 565, 43],
    [361, "08:43", "09:08", 523, 548, 25],
    [362, "08:44", "09:35", 524, 575, 51],
    [363, "08:45", "09:00", 525, 540, 15],
    [364, "08:45", "09:05", 525, 545, 20],
    [365, "08:46", "09:24", 526, 564, 38],
    [366, "08:46", "08:58", 526, 538, 12],
    [367, "08:46", "09:30", 526, 570, 44],
    [368, "08:48", "10:11", 528, 611, 83],
    [369, "08:48", "10:13", 528, 613, 85],
    [370, "08:49", "09:43", 529, 583, 54],
    [371, "08:50", "09:30", 530, 570, 40],
    [372, "08:50", "10:00", 530, 600, 70],
    [373, "08:50", "09:00", 530, 540, 10],
    [374, "08:51", "09:17", 531, 557, 26],
    [375, "08:53", "09:20", 533, 560, 27],
    [376, "08:53", "09:35", 533, 575, 42],
    [377, "08:55", "09:34", 535, 574, 39],
    [378, "08:55", "09:15", 535, 555, 20],
    [379, "08:58", "09:38", 538, 578, 40],
    [380, "08:58", "10:26", 538, 626, 88],
    [381, "08:59", "09:53", 539, 593, 54],
    [382, "08:59", "09:50", 539, 590, 51],
    [383, "09:00", "09:35", 540, 575, 35],
    [384, "09:00", "09:16", 540, 556, 16],
    [385, "09:00", "09:10", 540, 550, 10],
    [386, "09:00", "09:16", 540, 556, 16],
    [387, "09:01", "09:13", 541, 553, 12],
    [388, "09:03", "09:45", 543, 585, 42],
    [389, "09:03", "10:28", 543, 628, 85],
    [390, "09:05", "09:44", 545, 584, 39],
    [391, "09:05", "09:25", 545, 565, 20],
    [392, "09:08", "09:53", 548, 593, 45],
    [393, "09:08", "10:04", 548, 604, 56],
    [394, "09:09", "10:03", 549, 603, 54],
    [395, "09:10", "10:15", 550, 615, 65],
    [396, "09:10", "09:20", 550, 560, 10],
    [397, "09:11", "09:38", 551, 578, 27],
    [398, "09:13", "10:00", 553, 600, 47],
    [399, "09:14", "09:39", 554, 579, 25],
    [400, "09:14", "10:05", 554, 605, 51],
    [401, "09:15", "09:54", 555, 594, 39],
    [402, "09:16", "09:28", 556, 568, 12],
    [403, "09:18", "10:43", 558, 643, 85],
    [404, "09:18", "10:41", 558, 641, 83],
    [405, "09:18", "09:58", 558, 598, 40],
    [406, "09:19", "10:13", 559, 613, 54],
    [407, "09:20", "09:30", 560, 570, 10],
    [408, "09:20", "09:36", 560, 576, 16],
    [409, "09:21", "09:47", 561, 587, 26],
    [410, "09:23", "10:30", 563, 630, 67],
    [411, "09:23", "10:05", 563, 605, 42],
    [412, "09:23", "09:49", 563, 589, 26],
    [413, "09:24", "09:35", 564, 575, 11],
    [414, "09:25", "09:35", 565, 575, 10],
    [415, "09:25", "10:04", 565, 604, 39],
    [416, "09:28", "10:08", 568, 608, 40],
    [417, "09:29", "09:45", 569, 585, 16],
    [418, "09:29", "10:20", 569, 620, 51],
    [419, "09:29", "10:56", 569, 656, 87],
    [420, "09:29", "10:23", 569, 623, 54],
    [421, "09:30", "09:40", 570, 580, 10],
    [422, "09:31", "09:43", 571, 583, 12],
    [423, "09:33", "10:58", 573, 658, 85],
    [424, "09:33", "10:15", 573, 615, 42],
    [425, "09:34", "09:45", 574, 585, 11],
    [426, "09:35", "10:14", 575, 614, 39],
    [427, "09:38", "10:45", 578, 645, 67],
    [428, "09:39", "10:33", 579, 633, 54],
    [429, "09:40", "09:56", 580, 596, 16],
    [430, "09:40", "09:50", 580, 590, 10],
    [431, "09:41", "10:08", 581, 608, 27],
    [432, "09:41", "10:23", 581, 623, 42],
    [433, "09:44", "10:35", 584, 635, 51],
    [434, "09:44", "11:11", 584, 671, 87],
    [435, "09:44", "09:55", 584, 595, 11],
    [436, "09:45", "10:24", 585, 624, 39],
    [437, "09:46", "09:58", 586, 598, 12],
    [438, "09:48", "10:30", 588, 630, 42],
    [439, "09:48", "11:13", 588, 673, 85],
    [440, "09:48", "10:04", 588, 604, 16],
    [441, "09:49", "10:43", 589, 643, 54],
    [442, "09:50", "10:00", 590, 600, 10],
    [443, "09:51", "10:17", 591, 617, 26],
    [444, "09:53", "10:49", 593, 649, 56],
    [445, "09:53", "11:00", 593, 660, 67],
    [446, "09:54", "10:05", 594, 605, 11],
    [447, "09:55", "10:34", 595, 634, 39],
    [448, "09:56", "10:38", 596, 638, 42],
    [449, "09:57", "10:20", 597, 620, 23],
    [450, "09:59", "11:26", 599, 686, 87],
    [451, "09:59", "10:50", 599, 650, 51],
    [452, "09:59", "10:53", 599, 653, 54],
    [453, "10:00", "10:16", 600, 616, 16],
    [454, "10:00", "10:10", 600, 610, 10],
    [455, "10:01", "10:13", 601, 613, 12],
    [456, "10:03", "11:28", 603, 688, 85],
    [457, "10:03", "10:45", 603, 645, 42],
    [458, "10:04", "10:15", 604, 615, 11],
    [459, "10:05", "10:44", 605, 644, 39],
    [460, "10:08", "11:15", 608, 675, 67],
    [461, "10:09", "11:03", 609, 663, 54],
    [462, "10:10", "10:20", 610, 620, 10],
    [463, "10:11", "10:38", 611, 638, 27],
    [464, "10:11", "10:53", 611, 653, 42],
    [465, "10:14", "11:05", 614, 665, 51],
    [466, "10:14", "11:41", 614, 701, 87],
    [467, "10:14", "10:25", 614, 625, 11],
    [468, "10:15", "10:54", 615, 654, 39],
    [469, "10:16", "10:28", 616, 628, 12],
    [470, "10:18", "11:43", 618, 703, 85],
    [471, "10:18", "11:00", 618, 660, 42],
    [472, "10:19", "11:13", 619, 673, 54],
    [473, "10:20", "10:30", 620, 630, 10],
    [474, "10:20", "10:36", 620, 636, 16],
    [475, "10:21", "10:47", 621, 647, 26],
    [476, "10:23", "11:30", 623, 690, 67],
    [477, "10:23", "10:45", 623, 645, 22],
    [478, "10:24", "10:35", 624, 635, 11],
    [479, "10:25", "11:04", 625, 664, 39],
    [480, "10:26", "11:08", 626, 668, 42],
    [481, "10:29", "11:20", 629, 680, 51],
    [482, "10:29", "11:23", 629, 683, 54],
    [483, "10:29", "11:56", 629, 716, 87],
    [484, "10:30", "10:40", 630, 640, 10],
    [485, "10:31", "10:43", 631, 643, 12],
    [486, "10:33", "11:15", 633, 675, 42],
    [487, "10:33", "11:58", 633, 718, 85],
    [488, "10:34", "10:45", 634, 645, 11],
    [489, "10:35", "11:14", 635, 674, 39],
    [490, "10:38", "11:45", 638, 705, 67],
    [491, "10:39", "11:33", 639, 693, 54],
    [492, "10:40", "10:50", 640, 650, 10],
    [493, "10:40", "10:56", 640, 656, 16],
    [494, "10:41", "11:23", 641, 683, 42],
    [495, "10:41", "11:08", 641, 668, 27],
    [496, "10:44", "12:11", 644, 731, 87],
    [497, "10:44", "11:35", 644, 695, 51],
    [498, "10:44", "10:55", 644, 655, 11],
    [499, "10:45", "11:24", 645, 684, 39],
    [500, "10:46", "10:58", 646, 658, 12],
    [501, "10:48", "12:13", 648, 733, 85],
    [502, "10:48", "11:30", 648, 690, 42],
    [503, "10:49", "11:43", 649, 703, 54],
    [504, "10:50", "11:00", 650, 660, 10],
    [505, "10:51", "11:17", 651, 677, 26],
    [506, "10:53", "12:00", 653, 720, 67],
    [507, "10:53", "11:20", 653, 680, 27],
    [508, "10:54", "11:05", 654, 665, 11],
    [509, "10:55", "11:34", 655, 694, 39],
    [510, "10:56", "11:38", 656, 698, 42],
    [511, "10:59", "11:14", 659, 674, 15],
    [512, "10:59", "12:26", 659, 746, 87],
    [513, "10:59", "11:53", 659, 713, 54],
    [514, "10:59", "11:50", 659, 710, 51],
    [515, "11:00", "11:16", 660, 676, 16],
    [516, "11:00", "11:10", 660, 670, 10],
    [517, "11:01", "11:13", 661, 673, 12],
    [518, "11:03", "11:45", 663, 705, 42],
    [519, "11:03", "12:28", 663, 748, 85],
    [520, "11:04", "11:15", 664, 675, 11],
    [521, "11:05", "11:44", 665, 704, 39],
    [522, "11:08", "12:15", 668, 735, 67],
    [523, "11:09", "12:03", 669, 723, 54],
    [524, "11:10", "11:20", 670, 680, 10],
    [525, "11:11", "11:38", 671, 698, 27],
    [526, "11:11", "11:53", 671, 713, 42],
    [527, "11:14", "11:25", 674, 685, 11],
    [528, "11:14", "12:05", 674, 725, 51],
    [529, "11:14", "12:38", 674, 758, 84],
    [530, "11:14", "12:41", 674, 761, 87],
    [531, "11:15", "11:54", 675, 714, 39],
    [532, "11:16", "11:28", 676, 688, 12],
    [533, "11:18", "12:00", 678, 720, 42],
    [534, "11:19", "12:13", 679, 733, 54],
    [535, "11:20", "11:30", 680, 690, 10],
    [536, "11:20", "11:36", 680, 696, 16],
    [537, "11:21", "11:47", 681, 707, 26],
    [538, "11:23", "12:30", 683, 750, 67],
    [539, "11:23", "11:49", 683, 709, 26],
    [540, "11:24", "12:48", 684, 768, 84],
    [541, "11:24", "11:35", 684, 695, 11],
    [542, "11:25", "12:04", 685, 724, 39],
    [543, "11:26", "12:08", 686, 728, 42],
    [544, "11:29", "11:44", 689, 704, 15],
    [545, "11:29", "12:23", 689, 743, 54],
    [546, "11:29", "12:20", 689, 740, 51],
    [547, "11:29", "12:54", 689, 774, 85],
    [548, "11:30", "11:40", 690, 700, 10],
    [549, "11:31", "11:43", 691, 703, 12],
    [550, "11:33", "12:15", 693, 735, 42],
    [551, "11:34", "12:58", 694, 778, 84],
    [552, "11:34", "11:45", 694, 705, 11],
    [553, "11:35", "12:14", 695, 734, 39],
    [554, "11:38", "12:45", 698, 765, 67],
    [555, "11:39", "12:33", 699, 753, 54],
    [556, "11:40", "11:56", 700, 716, 16],
    [557, "11:40", "11:50", 700, 710, 10],
    [558, "11:41", "12:08", 701, 728, 27],
    [559, "11:41", "12:23", 701, 743, 42],
    [560, "11:44", "11:55", 704, 715, 11],
    [561, "11:44", "13:14", 704, 794, 90],
    [562, "11:44", "13:08", 704, 788, 84],
    [563, "11:44", "12:35", 704, 755, 51],
    [564, "11:45", "12:24", 705, 744, 39],
    [565, "11:46", "11:58", 706, 718, 12],
    [566, "11:48", "12:30", 708, 750, 42],
    [567, "11:49", "12:43", 709, 763, 54],
    [568, "11:50", "12:00", 710, 720, 10],
    [569, "11:51", "12:17", 711, 737, 26],
    [570, "11:53", "12:49", 713, 769, 56],
    [571, "11:53", "13:00", 713, 780, 67],
    [572, "11:54", "13:18", 714, 798, 84],
    [573, "11:54", "12:05", 714, 725, 11],
    [574, "11:55", "12:40", 715, 760, 45],
    [575, "11:55", "12:34", 715, 754, 39],
    [576, "11:56", "12:35", 716, 755, 39],
    [577, "11:57", "12:20", 717, 740, 23],
    [578, "11:58", "12:29", 718, 749, 31],
    [579, "11:59", "12:50", 719, 770, 51],
    [580, "11:59", "12:53", 719, 773, 54],
    [581, "11:59", "13:24", 719, 804, 85],
    [582, "11:59", "12:14", 719, 734, 15],
    [583, "12:00", "12:16", 720, 736, 16],
    [584, "12:00", "12:10", 720, 730, 10],
    [585, "12:01", "12:45", 721, 765, 44],
    [586, "12:01", "12:13", 721, 733, 12],
    [587, "12:03", "12:50", 723, 770, 47],
    [588, "12:04", "12:15", 724, 735, 11],
    [589, "12:04", "13:04", 724, 784, 60],
    [590, "12:04", "13:28", 724, 808, 84],
    [591, "12:05", "12:44", 725, 764, 39],
    [592, "12:08", "13:11", 728, 791, 63],
    [593, "12:08", "12:39", 728, 759, 31],
    [594, "12:09", "13:03", 729, 783, 54],
    [595, "12:10", "12:20", 730, 740, 10],
    [596, "12:11", "12:55", 731, 775, 44],
    [597, "12:11", "12:38", 731, 758, 27],
    [598, "12:14", "13:05", 734, 785, 51],
    [599, "12:14", "12:25", 734, 745, 11],
    [600, "12:14", "13:44", 734, 824, 90],
    [601, "12:14", "13:38", 734, 818, 84],
    [602, "12:15", "12:54", 735, 774, 39],
    [603, "12:16", "12:28", 736, 748, 12],
    [604, "12:18", "13:00", 738, 780, 42],
    [605, "12:19", "13:13", 739, 793, 54],
    [606, "12:20", "12:30", 740, 750, 10],
    [607, "12:20", "13:31", 740, 811, 71],
    [608, "12:20", "12:30", 740, 750, 10],
    [609, "12:20", "12:36", 740, 756, 16],
    [610, "12:21", "12:47", 741, 767, 26],
    [611, "12:23", "12:45", 743, 765, 22],
    [612, "12:24", "12:35", 744, 755, 11],
    [613, "12:24", "13:48", 744, 828, 84],
    [614, "12:25", "13:10", 745, 790, 45],
    [615, "12:25", "13:04", 745, 784, 39],
    [616, "12:26", "13:05", 746, 785, 39],
    [617, "12:28", "13:54", 748, 834, 86],
    [618, "12:28", "12:38", 748, 758, 10],
    [619, "12:28", "13:15", 748, 795, 47],
    [620, "12:29", "13:23", 749, 803, 54],
    [621, "12:30", "13:41", 750, 821, 71],
    [622, "12:30", "12:40", 750, 760, 10],
    [623, "12:31", "13:15", 751, 795, 44],
    [624, "12:31", "12:43", 751, 763, 12],
    [625, "12:33", "12:48", 753, 768, 15],
    [626, "12:33", "13:20", 753, 800, 47],
    [627, "12:34", "13:58", 754, 838, 84],
    [628, "12:34", "13:34", 754, 814, 60],
    [629, "12:34", "12:45", 754, 765, 11],
    [630, "12:35", "13:14", 755, 794, 39],
    [631, "12:38", "13:25", 758, 805, 47],
    [632, "12:38", "13:25", 758, 805, 47],
    [633, "12:38", "14:04", 758, 844, 86],
    [634, "12:39", "13:33", 759, 813, 54],
    [635, "12:40", "13:51", 760, 831, 71],
    [636, "12:40", "12:50", 760, 770, 10],
    [637, "12:40", "12:56", 760, 776, 16],
    [638, "12:41", "13:08", 761, 788, 27],
    [639, "12:43", "13:30", 763, 810, 47],
    [640, "12:44", "12:55", 764, 775, 11],
    [641, "12:44", "14:08", 764, 848, 84],
    [642, "12:45", "13:24", 765, 804, 39],
    [643, "12:46", "12:58", 766, 778, 12],
    [644, "12:46", "13:21", 766, 801, 35],
    [645, "12:48", "14:14", 768, 854, 86],
    [646, "12:48", "13:35", 768, 815, 47],
    [647, "12:48", "12:58", 768, 778, 10],
    [648, "12:48", "13:35", 768, 815, 47],
    [649, "12:49", "13:43", 769, 823, 54],
    [650, "12:50", "14:01", 770, 841, 71],
    [651, "12:50", "13:00", 770, 780, 10],
    [652, "12:50", "13:00", 770, 780, 10],
    [653, "12:51", "13:17", 771, 797, 26],
    [654, "12:53", "13:20", 773, 800, 27],
    [655, "12:53", "13:24", 773, 804, 31],
    [656, "12:53", "13:40", 773, 820, 47],
    [657, "12:54", "14:18", 774, 858, 84],
    [658, "12:54", "13:05", 774, 785, 11],
    [659, "12:55", "13:34", 775, 814, 39],
    [660, "12:58", "14:24", 778, 864, 86],
    [661, "12:58", "13:25", 778, 805, 27],
    [662, "12:58", "13:45", 778, 825, 47],
    [663, "12:58", "13:45", 778, 825, 47],
    [664, "12:59", "13:53", 779, 833, 54],
    [665, "13:00", "13:10", 780, 790, 10],
    [666, "13:00", "13:16", 780, 796, 16],
    [667, "13:00", "14:11", 780, 851, 71],
    [668, "13:01", "13:13", 781, 793, 12],
    [669, "13:03", "13:34", 783, 814, 31],
    [670, "13:03", "13:50", 783, 830, 47],
    [671, "13:04", "13:15", 784, 795, 11],
    [672, "13:04", "14:28", 784, 868, 84],
    [673, "13:05", "13:44", 785, 824, 39],
    [674, "13:08", "13:55", 788, 835, 47],
    [675, "13:08", "14:34", 788, 874, 86],
    [676, "13:08", "13:55", 788, 835, 47],
    [677, "13:09", "14:03", 789, 843, 54],
    [678, "13:10", "13:20", 790, 800, 10],
    [679, "13:10", "14:21", 790, 861, 71],
    [680, "13:13", "14:00", 793, 840, 47],
    [681, "13:13", "13:40", 793, 820, 27],
    [682, "13:14", "14:38", 794, 878, 84],
    [683, "13:14", "13:25", 794, 805, 11],
    [684, "13:15", "13:54", 795, 834, 39],
    [685, "13:16", "13:28", 796, 808, 12],
    [686, "13:18", "14:05", 798, 845, 47],
    [687, "13:18", "14:44", 798, 884, 86],
    [688, "13:18", "14:05", 798, 845, 47],
    [689, "13:19", "14:13", 799, 853, 54],
    [690, "13:20", "13:36", 800, 816, 16],
    [691, "13:20", "14:31", 800, 871, 71],
    [692, "13:20", "13:30", 800, 810, 10],
    [693, "13:21", "13:47", 801, 827, 26],
    [694, "13:23", "14:10", 803, 850, 47],
    [695, "13:23", "13:49", 803, 829, 26],
    [696, "13:24", "14:48", 804, 888, 84],
    [697, "13:24", "13:35", 804, 815, 11],
    [698, "13:25", "14:04", 805, 844, 39],
    [699, "13:28", "14:15", 808, 855, 47],
    [700, "13:28", "14:54", 808, 894, 86],
    [701, "13:28", "13:55", 808, 835, 27],
    [702, "13:28", "14:15", 808, 855, 47],
    [703, "13:29", "14:23", 809, 863, 54],
    [704, "13:30", "13:40", 810, 820, 10],
    [705, "13:30", "14:41", 810, 881, 71],
    [706, "13:31", "13:43", 811, 823, 12],
    [707, "13:33", "14:20", 813, 860, 47],
    [708, "13:34", "14:58", 814, 898, 84],
    [709, "13:34", "13:45", 814, 825, 11],
    [710, "13:35", "14:14", 815, 854, 39],
    [711, "13:38", "14:25", 818, 865, 47],
    [712, "13:38", "14:25", 818, 865, 47],
    [713, "13:38", "15:04", 818, 904, 86],
    [714, "13:39", "14:33", 819, 873, 54],
    [715, "13:40", "13:50", 820, 830, 10],
    [716, "13:40", "13:56", 820, 836, 16],
    [717, "13:40", "14:51", 820, 891, 71],
    [718, "13:43", "14:30", 823, 870, 47],
    [719, "13:43", "14:10", 823, 850, 27],
    [720, "13:44", "15:09", 824, 909, 85],
    [721, "13:44", "13:55", 824, 835, 11],
    [722, "13:45", "14:24", 825, 864, 39],
    [723, "13:46", "13:58", 826, 838, 12],
    [724, "13:48", "14:35", 828, 875, 47],
    [725, "13:48", "15:14", 828, 914, 86],
    [726, "13:48", "14:35", 828, 875, 47],
    [727, "13:49", "14:43", 829, 883, 54],
    [728, "13:50", "14:00", 830, 840, 10],
    [729, "13:50", "15:01", 830, 901, 71],
    [730, "13:51", "14:17", 831, 857, 26],
    [731, "13:53", "14:40", 833, 880, 47],
    [732, "13:53", "14:49", 833, 889, 56],
    [733, "13:54", "14:05", 834, 845, 11],
    [734, "13:54", "15:19", 834, 919, 85],
    [735, "13:55", "14:34", 835, 874, 39],
    [736, "13:57", "14:20", 837, 860, 23],
    [737, "13:58", "15:24", 838, 924, 86],
    [738, "13:58", "14:45", 838, 885, 47],
    [739, "13:58", "14:45", 838, 885, 47],
    [740, "13:58", "14:25", 838, 865, 27],
    [741, "13:59", "14:53", 839, 893, 54],
    [742, "14:00", "14:16", 840, 856, 16],
    [743, "14:00", "14:10", 840, 850, 10],
    [744, "14:00", "15:11", 840, 911, 71],
    [745, "14:01", "14:13", 841, 853, 12],
    [746, "14:03", "14:50", 843, 890, 47],
    [747, "14:04", "14:15", 844, 855, 11],
    [748, "14:04", "15:29", 844, 929, 85],
    [749, "14:05", "14:44", 845, 884, 39],
    [750, "14:08", "14:55", 848, 895, 47],
    [751, "14:08", "14:55", 848, 895, 47],
    [752, "14:08", "15:34", 848, 934, 86],
    [753, "14:09", "15:03", 849, 903, 54],
    [754, "14:10", "15:21", 850, 921, 71],
    [755, "14:10", "14:20", 850, 860, 10],
    [756, "14:13", "15:00", 853, 900, 47],
    [757, "14:13", "14:40", 853, 880, 27],
    [758, "14:14", "15:40", 854, 940, 86],
    [759, "14:14", "14:25", 854, 865, 11],
    [760, "14:15", "14:54", 855, 894, 39],
    [761, "14:16", "14:28", 856, 868, 12],
    [762, "14:18", "15:05", 858, 905, 47],
    [763, "14:18", "15:44", 858, 944, 86],
    [764, "14:18", "15:05", 858, 905, 47],
    [765, "14:19", "15:13", 859, 913, 54],
    [766, "14:20", "15:31", 860, 931, 71],
    [767, "14:20", "14:30", 860, 870, 10],
    [768, "14:20", "14:36", 860, 876, 16],
    [769, "14:21", "14:47", 861, 887, 26],
    [770, "14:23", "15:10", 863, 910, 47],
    [771, "14:23", "14:45", 863, 885, 22],
    [772, "14:24", "15:50", 864, 950, 86],
    [773, "14:24", "14:35", 864, 875, 11],
    [774, "14:25", "15:02", 865, 902, 37],
    [775, "14:26", "14:52", 866, 892, 26],
    [776, "14:28", "15:15", 868, 915, 47],
    [777, "14:28", "14:55", 868, 895, 27],
    [778, "14:28", "15:54", 868, 954, 86],
    [779, "14:28", "15:15", 868, 915, 47],
    [780, "14:29", "15:23", 869, 923, 54],
    [781, "14:30", "15:41", 870, 941, 71],
    [782, "14:30", "14:40", 870, 880, 10],
    [783, "14:31", "14:43", 871, 883, 12],
    [784, "14:33", "15:20", 873, 920, 47],
    [785, "14:34", "16:00", 874, 960, 86],
    [786, "14:34", "14:45", 874, 885, 11],
    [787, "14:35", "15:11", 875, 911, 36],
    [788, "14:38", "15:25", 878, 925, 47],
    [789, "14:38", "15:25", 878, 925, 47],
    [790, "14:38", "16:04", 878, 964, 86],
    [791, "14:39", "15:33", 879, 933, 54],
    [792, "14:40", "14:50", 880, 890, 10],
    [793, "14:40", "15:51", 880, 951, 71],
    [794, "14:40", "14:56", 880, 896, 16],
    [795, "14:43", "15:30", 883, 930, 47],
    [796, "14:43", "15:10", 883, 910, 27],
    [797, "14:44", "15:00", 884, 900, 16],
    [798, "14:44", "16:10", 884, 970, 86],
    [799, "14:45", "15:19", 885, 919, 34],
    [800, "14:46", "14:58", 886, 898, 12],
    [801, "14:48", "15:35", 888, 935, 47],
    [802, "14:48", "15:35", 888, 935, 47],
    [803, "14:48", "17:04", 888, 1024, 136],
    [804, "14:49", "15:43", 889, 943, 54],
    [805, "14:50", "16:01", 890, 961, 71],
    [806, "14:50", "15:00", 890, 900, 10],
    [807, "14:51", "15:17", 891, 917, 26],
    [808, "14:52", "15:27", 892, 927, 35],
    [809, "14:52", "15:21", 892, 921, 29],
    [810, "14:53", "15:40", 893, 940, 47],
    [811, "14:54", "15:08", 894, 908, 14],
    [812, "14:54", "16:20", 894, 980, 86],
    [813, "14:58", "16:24", 898, 984, 86],
    [814, "14:58", "15:45", 898, 945, 47],
    [815, "14:58", "15:25", 898, 925, 27],
    [816, "14:58", "15:45", 898, 945, 47],
    [817, "14:59", "15:53", 899, 953, 54],
    [818, "15:00", "15:10", 900, 910, 10],
    [819, "15:00", "15:35", 900, 935, 35],
    [820, "15:00", "16:11", 900, 971, 71],
    [821, "15:00", "15:16", 900, 916, 16],
    [822, "15:01", "15:13", 901, 913, 12],
    [823, "15:02", "15:16", 902, 916, 14],
    [824, "15:03", "15:50", 903, 950, 47],
    [825, "15:04", "16:30", 904, 990, 86],
    [826, "15:08", "16:34", 908, 994, 86],
    [827, "15:08", "15:55", 908, 955, 47],
    [828, "15:08", "15:55", 908, 955, 47],
    [829, "15:08", "15:45", 908, 945, 37],
    [830, "15:09", "16:14", 909, 974, 65],
    [831, "15:09", "16:03", 909, 963, 54],
    [832, "15:10", "16:21", 910, 981, 71],
    [833, "15:10", "15:20", 910, 920, 10],
    [834, "15:11", "15:24", 911, 924, 13],
    [835, "15:12", "15:36", 912, 936, 24],
    [836, "15:13", "16:00", 913, 960, 47],
    [837, "15:13", "15:40", 913, 940, 27],
    [838, "15:14", "16:40", 914, 1000, 86],
    [839, "15:16", "15:28", 916, 928, 12],
    [840, "15:16", "15:55", 916, 955, 39],
    [841, "15:18", "16:05", 918, 965, 47],
    [842, "15:18", "16:44", 918, 1004, 86],
    [843, "15:18", "16:05", 918, 965, 47],
    [844, "15:19", "16:13", 919, 973, 54],
    [845, "15:19", "15:34", 919, 934, 15],
    [846, "15:20", "15:30", 920, 930, 10],
    [847, "15:20", "16:31", 920, 991, 71],
    [848, "15:20", "15:36", 920, 936, 16],
    [849, "15:21", "15:47", 921, 947, 26],
    [850, "15:21", "16:06", 921, 966, 45],
    [851, "15:23", "16:10", 923, 970, 47],
    [852, "15:24", "16:50", 924, 1010, 86],
    [853, "15:24", "16:05", 924, 965, 41],
    [854, "15:27", "15:51", 927, 951, 24],
    [855, "15:27", "15:44", 927, 944, 17],
    [856, "15:28", "16:15", 928, 975, 47],
    [857, "15:28", "16:54", 928, 1014, 86],
    [858, "15:28", "16:15", 928, 975, 47],
    [859, "15:28", "15:55", 928, 955, 27],
    [860, "15:29", "16:23", 929, 983, 54],
    [861, "15:30", "16:41", 930, 1001, 71],
    [862, "15:30", "15:40", 930, 940, 10],
    [863, "15:31", "15:43", 931, 943, 12],
    [864, "15:33", "16:20", 933, 980, 47],
    [865, "15:34", "17:00", 934, 1020, 86],
    [866, "15:34", "16:15", 934, 975, 41],
    [867, "15:35", "15:54", 935, 954, 19],
    [868, "15:36", "16:21", 936, 981, 45],
    [869, "15:38", "16:25", 938, 985, 47],
    [870, "15:38", "16:25", 938, 985, 47],
    [871, "15:38", "16:39", 938, 999, 61],
    [872, "15:39", "16:33", 939, 993, 54],
    [873, "15:40", "15:50", 940, 950, 10],
    [874, "15:40", "16:51", 940, 1011, 71],
    [875, "15:40", "15:56", 940, 956, 16],
    [876, "15:43", "16:10", 943, 970, 27],
    [877, "15:43", "16:30", 943, 990, 47],
    [878, "15:44", "17:10", 944, 1030, 86],
    [879, "15:44", "16:25", 944, 985, 41],
    [880, "15:45", "16:04", 945, 964, 19],
    [881, "15:46", "15:58", 946, 958, 12],
    [882, "15:48", "16:35", 948, 995, 47],
    [883, "15:48", "16:35", 948, 995, 47],
    [884, "15:48", "17:14", 948, 1034, 86],
    [885, "15:49", "16:43", 949, 1003, 54],
    [886, "15:50", "16:00", 950, 960, 10],
    [887, "15:50", "17:01", 950, 1021, 71],
    [888, "15:51", "16:18", 951, 978, 27],
    [889, "15:52", "16:36", 952, 996, 44],
    [890, "15:53", "16:40", 953, 1000, 47],
    [891, "15:54", "17:20", 954, 1040, 86],
    [892, "15:54", "16:35", 954, 995, 41],
    [893, "15:55", "16:14", 955, 974, 19],
    [894, "15:58", "16:25", 958, 985, 27],
    [895, "15:58", "16:45", 958, 1005, 47],
    [896, "15:58", "16:45", 958, 1005, 47],
    [897, "15:58", "17:24", 958, 1044, 86],
    [898, "15:59", "17:11", 959, 1031, 72],
    [899, "15:59", "16:53", 959, 1013, 54],
    [900, "16:00", "16:10", 960, 970, 10],
    [901, "16:00", "16:16", 960, 976, 16],
    [902, "16:01", "16:13", 961, 973, 12],
    [903, "16:03", "16:50", 963, 1010, 47],
    [904, "16:04", "17:30", 964, 1050, 86],
    [905, "16:04", "16:45", 964, 1005, 41],
    [906, "16:05", "16:24", 965, 984, 19],
    [907, "16:06", "16:51", 966, 1011, 45],
    [908, "16:08", "16:55", 968, 1015, 47],
    [909, "16:08", "17:34", 968, 1054, 86],
    [910, "16:08", "16:55", 968, 1015, 47],
    [911, "16:09", "17:03", 969, 1023, 54],
    [912, "16:09", "17:21", 969, 1041, 72],
    [913, "16:10", "16:20", 970, 980, 10],
    [914, "16:13", "16:40", 973, 1000, 27],
    [915, "16:13", "17:00", 973, 1020, 47],
    [916, "16:14", "16:55", 974, 1015, 41],
    [917, "16:14", "17:40", 974, 1060, 86],
    [918, "16:15", "16:34", 975, 994, 19],
    [919, "16:16", "16:28", 976, 988, 12],
    [920, "16:18", "17:05", 978, 1025, 47],
    [921, "16:18", "17:05", 978, 1025, 47],
    [922, "16:18", "17:44", 978, 1064, 86],
    [923, "16:19", "17:31", 979, 1051, 72],
    [924, "16:19", "17:13", 979, 1033, 54],
    [925, "16:20", "16:30", 980, 990, 10],
    [926, "16:20", "16:36", 980, 996, 16],
    [927, "16:21", "16:48", 981, 1008, 27],
    [928, "16:22", "17:06", 982, 1026, 44],
    [929, "16:23", "17:10", 983, 1030, 47],
    [930, "16:24", "17:05", 984, 1025, 41],
    [931, "16:24", "17:50", 984, 1070, 86],
    [932, "16:25", "16:44", 985, 1004, 19],
    [933, "16:28", "17:15", 988, 1035, 47],
    [934, "16:28", "17:15", 988, 1035, 47],
    [935, "16:28", "16:55", 988, 1015, 27],
    [936, "16:28", "17:54", 988, 1074, 86],
    [937, "16:29", "17:23", 989, 1043, 54],
    [938, "16:29", "17:41", 989, 1061, 72],
    [939, "16:30", "16:40", 990, 1000, 10],
    [940, "16:31", "16:43", 991, 1003, 12],
    [941, "16:33", "17:20", 993, 1040, 47],
    [942, "16:34", "17:15", 994, 1035, 41],
    [943, "16:34", "18:00", 994, 1080, 86],
    [944, "16:35", "16:54", 995, 1014, 19],
    [945, "16:36", "17:21", 996, 1041, 45],
    [946, "16:38", "17:25", 998, 1045, 47],
    [947, "16:38", "17:25", 998, 1045, 47],
    [948, "16:38", "18:04", 998, 1084, 86],
    [949, "16:39", "17:33", 999, 1053, 54],
    [950, "16:39", "17:51", 999, 1071, 72],
    [951, "16:40", "16:56", 1000, 1016, 16],
    [952, "16:40", "16:50", 1000, 1010, 10],
    [953, "16:43", "17:10", 1003, 1030, 27],
    [954, "16:43", "17:30", 1003, 1050, 47],
    [955, "16:44", "17:25", 1004, 1045, 41],
    [956, "16:44", "18:10", 1004, 1090, 86],
    [957, "16:45", "17:04", 1005, 1024, 19],
    [958, "16:46", "16:58", 1006, 1018, 12],
    [959, "16:48", "18:14", 1008, 1094, 86],
    [960, "16:48", "17:35", 1008, 1055, 47],
    [961, "16:48", "17:35", 1008, 1055, 47],
    [962, "16:49", "18:01", 1009, 1081, 72],
    [963, "16:49", "17:43", 1009, 1063, 54],
    [964, "16:50", "17:00", 1010, 1020, 10],
    [965, "16:51", "17:18", 1011, 1038, 27],
    [966, "16:52", "17:36", 1012, 1056, 44],
    [967, "16:53", "17:40", 1013, 1060, 47],
    [968, "16:54", "18:20", 1014, 1100, 86],
    [969, "16:54", "17:35", 1014, 1055, 41],
    [970, "16:55", "17:14", 1015, 1034, 19],
    [971, "16:58", "17:25", 1018, 1045, 27],
    [972, "16:58", "17:45", 1018, 1065, 47],
    [973, "16:58", "17:45", 1018, 1065, 47],
    [974, "16:58", "18:24", 1018, 1104, 86],
    [975, "16:59", "18:11", 1019, 1091, 72],
    [976, "16:59", "17:53", 1019, 1073, 54],
    [977, "17:00", "17:16", 1020, 1036, 16],
    [978, "17:00", "17:10", 1020, 1030, 10],
    [979, "17:01", "17:13", 1021, 1033, 12],
    [980, "17:03", "17:50", 1023, 1070, 47],
    [981, "17:04", "18:30", 1024, 1110, 86],
    [982, "17:04", "17:45", 1024, 1065, 41],
    [983, "17:05", "17:24", 1025, 1044, 19],
    [984, "17:06", "17:51", 1026, 1071, 45],
    [985, "17:08", "17:55", 1028, 1075, 47],
    [986, "17:08", "17:55", 1028, 1075, 47],
    [987, "17:08", "18:34", 1028, 1114, 86],
    [988, "17:09", "18:03", 1029, 1083, 54],
    [989, "17:09", "18:21", 1029, 1101, 72],
    [990, "17:10", "17:20", 1030, 1040, 10],
    [991, "17:13", "17:40", 1033, 1060, 27],
    [992, "17:13", "18:00", 1033, 1080, 47],
    [993, "17:14", "17:55", 1034, 1075, 41],
    [994, "17:14", "18:40", 1034, 1120, 86],
    [995, "17:15", "17:34", 1035, 1054, 19],
    [996, "17:16", "17:28", 1036, 1048, 12],
    [997, "17:18", "18:05", 1038, 1085, 47],
    [998, "17:18", "18:05", 1038, 1085, 47],
    [999, "17:18", "18:44", 1038, 1124, 86],
    [1000, "17:19", "18:31", 1039, 1111, 72],
    [1001, "17:19", "18:13", 1039, 1093, 54],
    [1002, "17:20", "17:36", 1040, 1056, 16],
    [1003, "17:20", "17:30", 1040, 1050, 10],
    [1004, "17:21", "17:47", 1041, 1067, 26],
    [1005, "17:22", "18:06", 1042, 1086, 44],
    [1006, "17:23", "18:10", 1043, 1090, 47],
    [1007, "17:24", "18:50", 1044, 1130, 86],
    [1008, "17:24", "18:05", 1044, 1085, 41],
    [1009, "17:25", "17:44", 1045, 1064, 19],
    [1010, "17:28", "17:55", 1048, 1075, 27],
    [1011, "17:28", "18:15", 1048, 1095, 47],
    [1012, "17:28", "18:15", 1048, 1095, 47],
    [1013, "17:28", "18:54", 1048, 1134, 86],
    [1014, "17:29", "18:41", 1049, 1121, 72],
    [1015, "17:29", "18:23", 1049, 1103, 54],
    [1016, "17:30", "17:40", 1050, 1060, 10],
    [1017, "17:31", "17:43", 1051, 1063, 12],
    [1018, "17:33", "18:20", 1053, 1100, 47],
    [1019, "17:34", "18:15", 1054, 1095, 41],
    [1020, "17:34", "19:00", 1054, 1140, 86],
    [1021, "17:35", "17:54", 1055, 1074, 19],
    [1022, "17:36", "18:21", 1056, 1101, 45],
    [1023, "17:38", "18:25", 1058, 1105, 47],
    [1024, "17:38", "19:04", 1058, 1144, 86],
    [1025, "17:38", "18:25", 1058, 1105, 47],
    [1026, "17:39", "18:51", 1059, 1131, 72],
    [1027, "17:39", "18:33", 1059, 1113, 54],
    [1028, "17:40", "17:56", 1060, 1076, 16],
    [1029, "17:40", "17:50", 1060, 1070, 10],
    [1030, "17:43", "18:10", 1063, 1090, 27],
    [1031, "17:43", "18:30", 1063, 1110, 47],
    [1032, "17:44", "18:25", 1064, 1105, 41],
    [1033, "17:44", "19:14", 1064, 1154, 90],
    [1034, "17:45", "18:04", 1065, 1084, 19],
    [1035, "17:46", "17:58", 1066, 1078, 12],
    [1036, "17:48", "18:35", 1068, 1115, 47],
    [1037, "17:48", "18:35", 1068, 1115, 47],
    [1038, "17:48", "19:14", 1068, 1154, 86],
    [1039, "17:49", "19:01", 1069, 1141, 72],
    [1040, "17:49", "18:43", 1069, 1123, 54],
    [1041, "17:50", "18:00", 1070, 1080, 10],
    [1042, "17:51", "18:17", 1071, 1097, 26],
    [1043, "17:52", "18:36", 1072, 1116, 44],
    [1044, "17:53", "18:40", 1073, 1120, 47],
    [1045, "17:54", "18:35", 1074, 1115, 41],
    [1046, "17:54", "18:57", 1074, 1137, 63],
    [1047, "17:55", "18:14", 1075, 1094, 19],
    [1048, "17:58", "18:45", 1078, 1125, 47],
    [1049, "17:58", "18:45", 1078, 1125, 47],
    [1050, "17:58", "18:25", 1078, 1105, 27],
    [1051, "17:58", "19:26", 1078, 1166, 88],
    [1052, "17:59", "18:53", 1079, 1133, 54],
    [1053, "18:00", "19:11", 1080, 1151, 71],
    [1054, "18:00", "18:10", 1080, 1090, 10],
    [1055, "18:00", "18:16", 1080, 1096, 16],
    [1056, "18:01", "18:13", 1081, 1093, 12],
    [1057, "18:03", "18:50", 1083, 1130, 47],
    [1058, "18:04", "18:45", 1084, 1125, 41],
    [1059, "18:04", "19:29", 1084, 1169, 85],
    [1060, "18:05", "18:24", 1085, 1104, 19],
    [1061, "18:06", "18:51", 1086, 1131, 45],
    [1062, "18:08", "18:55", 1088, 1135, 47],
    [1063, "18:08", "19:06", 1088, 1146, 58],
    [1064, "18:08", "18:55", 1088, 1135, 47],
    [1065, "18:09", "19:03", 1089, 1143, 54],
    [1066, "18:10", "18:20", 1090, 1100, 10],
    [1067, "18:10", "19:21", 1090, 1161, 71],
    [1068, "18:13", "19:00", 1093, 1140, 47],
    [1069, "18:13", "18:40", 1093, 1120, 27],
    [1070, "18:14", "19:43", 1094, 1183, 89],
    [1071, "18:14", "18:55", 1094, 1135, 41],
    [1072, "18:15", "18:34", 1095, 1114, 19],
    [1073, "18:16", "18:28", 1096, 1108, 12],
    [1074, "18:17", "18:27", 1097, 1107, 10],
    [1075, "18:18", "19:41", 1098, 1181, 83],
    [1076, "18:18", "18:58", 1098, 1138, 40],
    [1077, "18:18", "19:05", 1098, 1145, 47],
    [1078, "18:19", "19:13", 1099, 1153, 54],
    [1079, "18:20", "19:31", 1100, 1171, 71],
    [1080, "18:20", "18:36", 1100, 1116, 16],
    [1081, "18:20", "18:30", 1100, 1110, 10],
    [1082, "18:22", "19:05", 1102, 1145, 43],
    [1083, "18:23", "19:05", 1103, 1145, 42],
    [1084, "18:24", "19:27", 1104, 1167, 63],
    [1085, "18:24", "19:05", 1104, 1145, 41],
    [1086, "18:25", "18:44", 1105, 1124, 19],
    [1087, "18:28", "19:25", 1108, 1165, 57],
    [1088, "18:28", "18:55", 1108, 1135, 27],
    [1089, "18:28", "19:08", 1108, 1148, 40],
    [1090, "18:28", "19:15", 1108, 1155, 47],
    [1091, "18:29", "19:23", 1109, 1163, 54],
    [1092, "18:30", "19:05", 1110, 1145, 35],
    [1093, "18:30", "18:40", 1110, 1120, 10],
    [1094, "18:31", "18:43", 1111, 1123, 12],
    [1095, "18:33", "19:15", 1113, 1155, 42],
    [1096, "18:34", "19:58", 1114, 1198, 84],
    [1097, "18:34", "19:14", 1114, 1154, 40],
    [1098, "18:35", "18:55", 1115, 1135, 20],
    [1099, "18:36", "19:20", 1116, 1160, 44],
    [1100, "18:38", "19:25", 1118, 1165, 47],
    [1101, "18:38", "19:23", 1118, 1163, 45],
    [1102, "18:38", "19:56", 1118, 1196, 78],
    [1103, "18:39", "19:33", 1119, 1173, 54],
    [1104, "18:40", "18:50", 1120, 1130, 10],
    [1105, "18:40", "19:45", 1120, 1185, 65],
    [1106, "18:40", "18:56", 1120, 1136, 16],
    [1107, "18:43", "19:10", 1123, 1150, 27],
    [1108, "18:43", "19:30", 1123, 1170, 47],
    [1109, "18:44", "19:24", 1124, 1164, 40],
    [1110, "18:45", "19:05", 1125, 1145, 20],
    [1111, "18:46", "18:58", 1126, 1138, 12],
    [1112, "18:48", "19:35", 1128, 1175, 47],
    [1113, "18:48", "20:12", 1128, 1212, 84],
    [1114, "18:48", "20:11", 1128, 1211, 83],
    [1115, "18:48", "19:28", 1128, 1168, 40],
    [1116, "18:49", "19:43", 1129, 1183, 54],
    [1117, "18:50", "19:00", 1130, 1140, 10],
    [1118, "18:51", "19:01", 1131, 1141, 10],
    [1119, "18:53", "19:35", 1133, 1175, 42],
    [1120, "18:53", "19:15", 1133, 1155, 22],
    [1121, "18:53", "20:00", 1133, 1200, 67],
    [1122, "18:55", "19:15", 1135, 1155, 20],
    [1123, "18:55", "19:34", 1135, 1174, 39],
    [1124, "18:58", "19:38", 1138, 1178, 40],
    [1125, "18:59", "19:53", 1139, 1193, 54],
    [1126, "18:59", "19:50", 1139, 1190, 51],
    [1127, "18:59", "19:53", 1139, 1193, 54],
    [1128, "19:00", "19:16", 1140, 1156, 16],
    [1129, "19:00", "19:10", 1140, 1150, 10],
    [1130, "19:00", "19:16", 1140, 1156, 16],
    [1131, "19:01", "19:13", 1141, 1153, 12],
    [1132, "19:03", "20:26", 1143, 1226, 83],
    [1133, "19:03", "19:45", 1143, 1185, 42],
    [1134, "19:05", "19:44", 1145, 1184, 39],
    [1135, "19:05", "19:25", 1145, 1165, 20],
    [1136, "19:08", "20:15", 1148, 1215, 67],
    [1137, "19:08", "19:35", 1148, 1175, 27],
    [1138, "19:09", "19:49", 1149, 1189, 40],
    [1139, "19:09", "20:03", 1149, 1203, 54],
    [1140, "19:10", "19:20", 1150, 1160, 10],
    [1141, "19:10", "19:20", 1150, 1160, 10],
    [1142, "19:11", "19:53", 1151, 1193, 42],
    [1143, "19:14", "20:26", 1154, 1226, 72],
    [1144, "19:14", "19:35", 1154, 1175, 21],
    [1145, "19:14", "19:24", 1154, 1164, 10],
    [1146, "19:14", "20:05", 1154, 1205, 51],
    [1147, "19:15", "19:30", 1155, 1170, 15],
    [1148, "19:15", "19:54", 1155, 1194, 39],
    [1149, "19:18", "20:39", 1158, 1239, 81],
    [1150, "19:18", "20:00", 1158, 1200, 42],
    [1151, "19:19", "20:14", 1159, 1214, 55],
    [1152, "19:20", "19:30", 1160, 1170, 10],
    [1153, "19:20", "19:36", 1160, 1176, 16],
    [1154, "19:21", "19:31", 1161, 1171, 10],
    [1155, "19:23", "20:30", 1163, 1230, 67],
    [1156, "19:23", "19:35", 1163, 1175, 12],
    [1157, "19:24", "19:45", 1164, 1185, 21],
    [1158, "19:24", "19:45", 1164, 1185, 21],
    [1159, "19:25", "20:04", 1165, 1204, 39],
    [1160, "19:26", "20:08", 1166, 1208, 42],
    [1161, "19:29", "20:02", 1169, 1202, 33],
    [1162, "19:29", "20:18", 1169, 1218, 49],
    [1163, "19:29", "20:41", 1169, 1241, 72],
    [1164, "19:30", "19:40", 1170, 1180, 10],
    [1165, "19:33", "20:54", 1173, 1254, 81],
    [1166, "19:33", "20:17", 1173, 1217, 44],
    [1167, "19:34", "19:55", 1174, 1195, 21],
    [1168, "19:35", "20:14", 1175, 1214, 39],
    [1169, "19:38", "20:05", 1178, 1205, 27],
    [1170, "19:38", "20:45", 1178, 1245, 67],
    [1171, "19:39", "20:12", 1179, 1212, 33],
    [1172, "19:40", "19:50", 1180, 1190, 10],
    [1173, "19:40", "19:56", 1180, 1196, 16],
    [1174, "19:41", "20:27", 1181, 1227, 46],
    [1175, "19:43", "19:55", 1183, 1195, 12],
    [1176, "19:44", "20:05", 1184, 1205, 21],
    [1177, "19:44", "20:33", 1184, 1233, 49],
    [1178, "19:44", "21:00", 1184, 1260, 76],
    [1179, "19:45", "20:24", 1185, 1224, 39],
    [1180, "19:48", "20:37", 1188, 1237, 49],
    [1181, "19:48", "21:09", 1188, 1269, 81],
    [1182, "19:50", "20:00", 1190, 1200, 10],
    [1183, "19:52", "20:29", 1192, 1229, 37],
    [1184, "19:53", "20:08", 1193, 1208, 15],
    [1185, "19:53", "21:02", 1193, 1262, 69],
    [1186, "19:53", "20:20", 1193, 1220, 27],
    [1187, "19:54", "20:19", 1194, 1219, 25],
    [1188, "19:55", "20:34", 1195, 1234, 39],
    [1189, "19:56", "20:34", 1196, 1234, 38],
    [1190, "19:59", "20:48", 1199, 1248, 49],
    [1191, "19:59", "21:20", 1199, 1280, 81],
    [1192, "20:00", "20:16", 1200, 1216, 16],
    [1193, "20:00", "20:10", 1200, 1210, 10],
    [1194, "20:03", "20:42", 1203, 1242, 39],
    [1195, "20:03", "21:24", 1203, 1284, 81],
    [1196, "20:04", "20:29", 1204, 1229, 25],
    [1197, "20:05", "20:48", 1205, 1248, 43],
    [1198, "20:07", "20:44", 1207, 1244, 37],
    [1199, "20:08", "20:40", 1208, 1240, 32],
    [1200, "20:08", "20:35", 1208, 1235, 27],
    [1201, "20:10", "20:20", 1210, 1220, 10],
    [1202, "20:10", "20:22", 1210, 1222, 12],
    [1203, "20:11", "20:47", 1211, 1247, 36],
    [1204, "20:14", "21:04", 1214, 1264, 50],
    [1205, "20:14", "21:03", 1214, 1263, 49],
    [1206, "20:17", "21:03", 1217, 1263, 46],
    [1207, "20:18", "21:39", 1218, 1299, 81],
    [1208, "20:20", "20:30", 1220, 1230, 10],
    [1209, "20:20", "20:57", 1220, 1257, 37],
    [1210, "20:20", "20:36", 1220, 1236, 16],
    [1211, "20:22", "20:59", 1222, 1259, 37],
    [1212, "20:22", "20:42", 1222, 1242, 20],
    [1213, "20:24", "20:49", 1224, 1249, 25],
    [1214, "20:27", "21:22", 1227, 1282, 55],
    [1215, "20:29", "21:18", 1229, 1278, 49],
    [1216, "20:30", "21:07", 1230, 1267, 37],
    [1217, "20:30", "20:40", 1230, 1240, 10],
    [1218, "20:30", "20:40", 1230, 1240, 10],
    [1219, "20:30", "21:40", 1230, 1300, 70],
    [1220, "20:32", "21:18", 1232, 1278, 46],
    [1221, "20:35", "21:54", 1235, 1314, 79],
    [1222, "20:37", "21:14", 1237, 1274, 37],
    [1223, "20:38", "21:08", 1238, 1268, 30],
    [1224, "20:40", "20:50", 1240, 1250, 10],
    [1225, "20:40", "21:17", 1240, 1277, 37],
    [1226, "20:40", "20:56", 1240, 1256, 16],
    [1227, "20:44", "21:33", 1244, 1293, 49],
    [1228, "20:47", "21:33", 1247, 1293, 46],
    [1229, "20:47", "21:42", 1247, 1302, 55],
    [1230, "20:50", "21:00", 1250, 1260, 10],
    [1231, "20:50", "22:00", 1250, 1320, 70],
    [1232, "20:50", "22:09", 1250, 1329, 79],
    [1233, "20:50", "21:27", 1250, 1287, 37],
    [1234, "20:52", "21:29", 1252, 1289, 37],
    [1235, "20:53", "21:20", 1253, 1280, 27],
    [1236, "20:56", "21:11", 1256, 1271, 15],
    [1237, "20:59", "21:48", 1259, 1308, 49],
    [1238, "21:00", "21:10", 1260, 1270, 10],
    [1239, "21:00", "21:37", 1260, 1297, 37],
    [1240, "21:02", "21:48", 1262, 1308, 46],
    [1241, "21:05", "22:24", 1265, 1344, 79],
    [1242, "21:07", "21:44", 1267, 1304, 37],
    [1243, "21:07", "22:02", 1267, 1322, 55],
    [1244, "21:08", "21:38", 1268, 1298, 30],
    [1245, "21:10", "22:25", 1270, 1345, 75],
    [1246, "21:10", "21:20", 1270, 1280, 10],
    [1247, "21:10", "21:47", 1270, 1307, 37],
    [1248, "21:14", "22:03", 1274, 1323, 49],
    [1249, "21:17", "22:03", 1277, 1323, 46],
    [1250, "21:20", "22:18", 1280, 1338, 58],
    [1251, "21:20", "21:57", 1280, 1317, 37],
    [1252, "21:20", "21:30", 1280, 1290, 10],
    [1253, "21:22", "21:59", 1282, 1319, 37],
    [1254, "21:24", "21:49", 1284, 1309, 25],
    [1255, "21:27", "22:21", 1287, 1341, 54],
    [1256, "21:30", "22:07", 1290, 1327, 37],
    [1257, "21:30", "22:20", 1290, 1340, 50],
    [1258, "21:30", "21:40", 1290, 1300, 10],
    [1259, "21:32", "22:18", 1292, 1338, 46],
    [1260, "21:32", "22:01", 1292, 1321, 29],
    [1261, "21:35", "22:54", 1295, 1374, 79],
    [1262, "21:37", "22:14", 1297, 1334, 37],
    [1263, "21:39", "21:55", 1299, 1315, 16],
    [1264, "21:40", "22:17", 1300, 1337, 37],
    [1265, "21:40", "21:50", 1300, 1310, 10],
    [1266, "21:41", "22:08", 1301, 1328, 27],
    [1267, "21:47", "22:16", 1307, 1336, 29],
    [1268, "21:47", "22:51", 1307, 1371, 64],
    [1269, "21:47", "22:33", 1307, 1353, 46],
    [1270, "21:48", "22:03", 1308, 1323, 15],
    [1271, "21:50", "22:55", 1310, 1375, 65],
    [1272, "21:50", "22:27", 1310, 1347, 37],
    [1273, "21:50", "22:00", 1310, 1320, 10],
    [1274, "21:52", "22:29", 1312, 1349, 37],
    [1275, "21:53", "22:19", 1313, 1339, 26],
    [1276, "22:00", "22:38", 1320, 1358, 38],
    [1277, "22:00", "22:10", 1320, 1330, 10],
    [1278, "22:02", "22:12", 1322, 1332, 10],
    [1279, "22:02", "22:48", 1322, 1368, 46],
    [1280, "22:04", "22:31", 1324, 1351, 27],
    [1281, "22:05", "23:24", 1325, 1404, 79],
    [1282, "22:07", "22:44", 1327, 1364, 37],
    [1283, "22:07", "22:39", 1327, 1359, 32],
    [1284, "22:09", "22:25", 1329, 1345, 16],
    [1285, "22:10", "23:25", 1330, 1405, 75],
    [1286, "22:13", "22:38", 1333, 1358, 25],
    [1287, "22:13", "22:53", 1333, 1373, 40],
    [1288, "22:17", "22:27", 1337, 1347, 10],
    [1289, "22:17", "23:03", 1337, 1383, 46],
    [1290, "22:19", "22:46", 1339, 1366, 27],
    [1291, "22:22", "22:59", 1342, 1379, 37],
    [1292, "22:24", "22:48", 1344, 1368, 24],
    [1293, "22:27", "22:52", 1347, 1372, 25],
    [1294, "22:27", "23:21", 1347, 1401, 54],
    [1295, "22:28", "23:08", 1348, 1388, 40],
    [1296, "22:30", "23:17", 1350, 1397, 47],
    [1297, "22:32", "22:42", 1352, 1362, 10],
    [1298, "22:32", "23:11", 1352, 1391, 39],
    [1299, "22:34", "23:01", 1354, 1381, 27],
    [1300, "22:35", "23:54", 1355, 1434, 79],
    [1301, "22:37", "23:14", 1357, 1394, 37],
    [1302, "22:43", "23:23", 1363, 1403, 40],
    [1303, "22:43", "23:08", 1363, 1388, 25],
    [1304, "22:47", "23:33", 1367, 1413, 46],
    [1305, "22:47", "22:57", 1367, 1377, 10],
    [1306, "22:49", "23:16", 1369, 1396, 27],
    [1307, "22:52", "23:29", 1372, 1409, 37],
    [1308, "22:53", "23:15", 1373, 1395, 22],
    [1309, "22:55", "23:55", 1375, 1435, 60],
    [1310, "22:57", "23:51", 1377, 1431, 54],
    [1311, "22:58", "23:38", 1378, 1418, 40],
    [1312, "23:02", "23:41", 1382, 1421, 39],
    [1313, "23:02", "23:12", 1382, 1392, 10],
    [1314, "23:04", "23:31", 1384, 1411, 27],
    [1315, "23:05", "00:24", 1385, 1464, 79],
    [1316, "23:07", "23:44", 1387, 1424, 37],
    [1317, "23:13", "23:53", 1393, 1433, 40],
    [1318, "23:13", "23:38", 1393, 1418, 25],
    [1319, "23:17", "00:03", 1397, 1443, 46],
    [1320, "23:17", "23:27", 1397, 1407, 10],
    [1321, "23:19", "23:46", 1399, 1426, 27],
    [1322, "23:22", "23:59", 1402, 1439, 37],
    [1323, "23:25", "00:25", 1405, 1465, 60],
    [1324, "23:27", "00:21", 1407, 1461, 54],
    [1325, "23:28", "00:08", 1408, 1448, 40],
    [1326, "23:32", "23:42", 1412, 1422, 10],
    [1327, "23:34", "00:01", 1414, 1441, 27],
    [1328, "23:35", "01:05", 1415, 1505, 90],
    [1329, "23:37", "00:09", 1417, 1449, 32],
    [1330, "23:43", "00:23", 1423, 1463, 40],
    [1331, "23:43", "00:08", 1423, 1448, 25],
    [1332, "23:46", "00:01", 1426, 1441, 15],
    [1333, "23:47", "23:57", 1427, 1437, 10],
    [1334, "23:47", "00:33", 1427, 1473, 46],
    [1335, "23:52", "00:24", 1432, 1464, 32],
    [1336, "23:55", "00:49", 1435, 1489, 54],
    [1337, "23:57", "00:57", 1437, 1497, 60],
    [1338, "23:58", "00:38", 1438, 1478, 40],
    [1339, "00:02", "00:12", 1442, 1452, 10],
    [1340, "00:07", "00:39", 1447, 1479, 32],
    [1341, "00:13", "00:38", 1453, 1478, 25],
    [1342, "00:13", "00:51", 1453, 1491, 38],
    [1343, "00:15", "01:14", 1455, 1514, 59],
    [1344, "00:17", "01:23", 1457, 1523, 66],
    [1345, "00:23", "00:33", 1463, 1473, 10],
    [1346, "00:24", "00:40", 1464, 1480, 16],
    [1347, "00:25", "01:12", 1465, 1512, 47],
    [1348, "00:28", "01:07", 1468, 1507, 39],
    [1349, "00:33", "01:05", 1473, 1505, 32],
    [1350, "00:43", "01:21", 1483, 1521, 38],
    [1351, "00:44", "00:54", 1484, 1494, 10],
    [1352, "00:47", "01:09", 1487, 1509, 22],
    [1353, "00:47", "01:26", 1487, 1526, 39],
    [1354, "00:54", "01:04", 1494, 1504, 10],
    [1355, "00:57", "01:07", 1497, 1507, 10],
]  # yapf:disable


def bus_driver_scheduling(minimize_drivers: bool, max_num_drivers: int) -> int:
    """Optimize the bus driver scheduling problem.

    This model has two modes.

    If minimize_drivers == True, the objective will be to find the minimal
    number of drivers, independently of the working times of each drivers.

    Otherwise, will will create max_num_drivers non optional drivers, and
    minimize the sum of working times of these drivers.

    Args:
      minimize_drivers: A Boolean parameter specifying the objective of the
        problem. If True, it tries to minimize the number of used drivers. If
        false, it minimizes the sum of working times per workers.
      max_num_drivers: This number specifies the exact number of non optional
        drivers to use. This is only used if 'minimize_drivers' is False.

    Returns:
        The objective value of the model.
    """
    shifts = None
    if _INSTANCE.value == 0:
        shifts = SAMPLE_SHIFTS_TINY
    elif _INSTANCE.value == 1:
        shifts = SAMPLE_SHIFTS_SMALL
    elif _INSTANCE.value == 2:
        shifts = SAMPLE_SHIFTS_MEDIUM
    elif _INSTANCE.value == 3:
        shifts = SAMPLE_SHIFTS_LARGE

    num_shifts = len(shifts)

    # All durations are in minutes.
    max_driving_time = 540  # 8 hours.
    max_driving_time_without_pauses = 240  # 4 hours
    min_pause_after_4h = 30
    min_delay_between_shifts = 2
    max_working_time = 720
    min_working_time = 390  # 6.5 hours
    setup_time = 10
    cleanup_time = 15

    # Computed data.
    total_driving_time = sum(shift[5] for shift in shifts)
    min_num_drivers = int(math.ceil(total_driving_time * 1.0 / max_driving_time))
    num_drivers = 2 * min_num_drivers if minimize_drivers else max_num_drivers
    min_start_time = min(shift[3] for shift in shifts)
    max_end_time = max(shift[4] for shift in shifts)

    print("Bus driver scheduling")
    print("  num shifts =", num_shifts)
    print("  total driving time =", total_driving_time, "minutes")
    print("  min num drivers =", min_num_drivers)
    print("  num drivers =", num_drivers)
    print("  min start time =", min_start_time)
    print("  max end time =", max_end_time)

    model = cp_model.CpModel()

    # For each driver and each shift, we store:
    #   - the total driving time including this shift
    #   - the acrued driving time since the last 30 minute break
    # Special arcs have the following effect:
    #   - 'from source to shift' sets the starting time and accumulate the first
    #      shift
    #   - 'from shift to end' sets the ending time, and fill the driving_times
    #      variable
    # Arcs between two shifts have the following impact
    #   - add the duration of the shift to the total driving time
    #   - reset the accumulated driving time if the distance between the two
    #     shifts is more than 30 minutes, add the duration of the shift to the
    #     accumulated driving time since the last break otherwise

    # Per (driver, node) info (driving time, performed,
    # driving time since break)
    total_driving = {}
    no_break_driving = {}
    performed = {}
    starting_shifts = {}

    # Per driver info (start, end, driving times, is working)
    start_times = []
    end_times = []
    driving_times = []
    working_drivers = []
    working_times = []

    # Weighted objective
    delay_literals = []
    delay_weights = []

    # Used to propagate more between drivers
    shared_incoming_literals = collections.defaultdict(list)
    shared_outgoing_literals = collections.defaultdict(list)

    for d in range(num_drivers):
        start_times.append(
            model.new_int_var(min_start_time - setup_time, max_end_time, "start_%i" % d)
        )
        end_times.append(
            model.new_int_var(min_start_time, max_end_time + cleanup_time, "end_%i" % d)
        )
        driving_times.append(model.new_int_var(0, max_driving_time, "driving_%i" % d))
        working_times.append(
            model.new_int_var(0, max_working_time, "working_times_%i" % d)
        )

        incoming_literals = collections.defaultdict(list)
        outgoing_literals = collections.defaultdict(list)
        outgoing_source_literals = []
        incoming_sink_literals = []

        # Create all the shift variables before iterating on the transitions
        # between these shifts.
        for s in range(num_shifts):
            total_driving[d, s] = model.new_int_var(
                0, max_driving_time, "dr_%i_%i" % (d, s)
            )
            no_break_driving[d, s] = model.new_int_var(
                0, max_driving_time_without_pauses, "mdr_%i_%i" % (d, s)
            )
            performed[d, s] = model.new_bool_var("performed_%i_%i" % (d, s))

        for s in range(num_shifts):
            shift = shifts[s]
            duration = shift[5]

            # Arc from source to shift.
            #    - set the start time of the driver
            #    - increase driving time and driving time since break
            source_lit = model.new_bool_var("%i from source to %i" % (d, s))
            outgoing_source_literals.append(source_lit)
            incoming_literals[s].append(source_lit)
            shared_incoming_literals[s].append(source_lit)
            model.add(start_times[d] == shift[3] - setup_time).only_enforce_if(
                source_lit
            )
            model.add(total_driving[d, s] == duration).only_enforce_if(source_lit)
            model.add(no_break_driving[d, s] == duration).only_enforce_if(source_lit)
            starting_shifts[d, s] = source_lit

            # Arc from shift to sink
            #    - set the end time of the driver
            #    - set the driving times of the driver
            sink_lit = model.new_bool_var("%i from %i to sink" % (d, s))
            outgoing_literals[s].append(sink_lit)
            shared_outgoing_literals[s].append(sink_lit)
            incoming_sink_literals.append(sink_lit)
            model.add(end_times[d] == shift[4] + cleanup_time).only_enforce_if(sink_lit)
            model.add(driving_times[d] == total_driving[d, s]).only_enforce_if(sink_lit)

            # Node not performed
            #    - set both driving times to 0
            #    - add a looping arc on the node
            model.add(total_driving[d, s] == 0).only_enforce_if(~performed[d, s])
            model.add(no_break_driving[d, s] == 0).only_enforce_if(~performed[d, s])
            incoming_literals[s].append(~performed[d, s])
            outgoing_literals[s].append(~performed[d, s])
            # negated adding to the shared lists, because, globally, each node will
            # have one incoming literal, and one outgoing literal.

            # Node performed:
            #    - add upper bound on start_time
            #    - add lower bound on end_times
            model.add(start_times[d] <= shift[3] - setup_time).only_enforce_if(
                performed[d, s]
            )
            model.add(end_times[d] >= shift[4] + cleanup_time).only_enforce_if(
                performed[d, s]
            )

            for o in range(num_shifts):
                other = shifts[o]
                delay = other[3] - shift[4]
                if delay < min_delay_between_shifts:
                    continue
                lit = model.new_bool_var("%i from %i to %i" % (d, s, o))

                # Increase driving time
                model.add(
                    total_driving[d, o] == total_driving[d, s] + other[5]
                ).only_enforce_if(lit)

                # Increase no_break_driving or reset it to 0 depending on the delay
                if delay >= min_pause_after_4h:
                    model.add(no_break_driving[d, o] == other[5]).only_enforce_if(lit)
                else:
                    model.add(
                        no_break_driving[d, o] == no_break_driving[d, s] + other[5]
                    ).only_enforce_if(lit)

                # add arc
                outgoing_literals[s].append(lit)
                shared_outgoing_literals[s].append(lit)
                incoming_literals[o].append(lit)
                shared_incoming_literals[o].append(lit)

                # Cost part
                delay_literals.append(lit)
                delay_weights.append(delay)

        model.add(working_times[d] == end_times[d] - start_times[d])

        if minimize_drivers:
            # Driver is not working.
            working = model.new_bool_var("working_%i" % d)
            model.add(start_times[d] == min_start_time).only_enforce_if(~working)
            model.add(end_times[d] == min_start_time).only_enforce_if(~working)
            model.add(driving_times[d] == 0).only_enforce_if(~working)
            working_drivers.append(working)
            outgoing_source_literals.append(~working)
            incoming_sink_literals.append(~working)
            # Conditional working time constraints
            model.add(working_times[d] >= min_working_time).only_enforce_if(working)
            model.add(working_times[d] == 0).only_enforce_if(~working)
        else:
            # Working time constraints
            model.add(working_times[d] >= min_working_time)

        # Create circuit constraint.
        model.add_exactly_one(outgoing_source_literals)
        for s in range(num_shifts):
            model.add_exactly_one(outgoing_literals[s])
            model.add_exactly_one(incoming_literals[s])
        model.add_exactly_one(incoming_sink_literals)

    # Each shift is covered.
    for s in range(num_shifts):
        model.add_exactly_one(performed[d, s] for d in range(num_drivers))
        # Globally, each node has one incoming and one outgoing literal
        model.add_exactly_one(shared_incoming_literals[s])
        model.add_exactly_one(shared_outgoing_literals[s])

    # Symmetry breaking

    # The first 3 shifts must be performed by 3 different drivers.
    # Let's assign them to the first 3 drivers in sequence
    model.add(starting_shifts[0, 0] == 1)
    model.add(starting_shifts[1, 1] == 1)
    model.add(starting_shifts[2, 2] == 1)

    if minimize_drivers:
        # Push non working drivers to the end
        for d in range(num_drivers - 1):
            model.add_implication(~working_drivers[d], ~working_drivers[d + 1])

    # Redundant constraints: sum of driving times = sum of shift driving times
    model.add(cp_model.LinearExpr.sum(driving_times) == total_driving_time)
    if not minimize_drivers:
        model.add(
            cp_model.LinearExpr.sum(working_times)
            == total_driving_time
            + num_drivers * (setup_time + cleanup_time)
            + cp_model.LinearExpr.weighted_sum(delay_literals, delay_weights)
        )

    if minimize_drivers:
        # minimize the number of working drivers
        model.minimize(cp_model.LinearExpr.sum(working_drivers))
    else:
        # minimize the sum of delays between tasks, which in turns minimize the
        # sum of working times as the total driving time is fixed
        model.minimize(cp_model.LinearExpr.weighted_sum(delay_literals, delay_weights))

    if not minimize_drivers and _OUTPUT_PROTO.value:
        print("Writing proto to %s" % _OUTPUT_PROTO.value)
        with open(_OUTPUT_PROTO.value, "w") as text_file:
            text_file.write(str(model))

    # Solve model.
    solver = cp_model.CpSolver()
    if _PARAMS.value:
        text_format.Parse(_PARAMS.value, solver.parameters)

    status = solver.solve(model)

    if status != cp_model.OPTIMAL and status != cp_model.FEASIBLE:
        return -1

    # Display solution
    if minimize_drivers:
        max_num_drivers = int(solver.objective_value)
        print("minimal number of drivers =", max_num_drivers)
        return max_num_drivers

    for d in range(num_drivers):
        print("Driver %i: " % (d + 1))
        print("  total driving time =", solver.value(driving_times[d]))
        print(
            "  working time =",
            solver.value(working_times[d]) + setup_time + cleanup_time,
        )

        first = True
        for s in range(num_shifts):
            shift = shifts[s]

            if not solver.boolean_value(performed[d, s]):
                continue

            # Hack to detect if the waiting time between the last shift and
            # this one exceeds 30 minutes. For this, we look at the
            # no_break_driving which was reinitialized in that case.
            if solver.value(no_break_driving[d, s]) == shift[5] and not first:
                print("    **break**")
            print("    shift ", shift[0], ":", shift[1], "-", shift[2])
            first = False

    return int(solver.objective_value)


def main(_):
    """Optimize the bus driver allocation in two passes."""
    print("----------- first pass: minimize the number of drivers")
    num_drivers = bus_driver_scheduling(True, -1)
    if num_drivers == -1:
        print("no solution found, skipping the final step")
    else:
        print("----------- second pass: minimize the sum of working times")
        bus_driver_scheduling(False, num_drivers)


if __name__ == "__main__":
    app.run(main)