bus_driver_scheduling_sat.py

#!/usr/bin/env python3
# Copyright 2010-2021 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

FLAGS = flags.FLAGS

flags.DEFINE_string('output_proto', '',
                    'Output file to write the cp_model proto to.')
flags.DEFINE_string('params', 'num_search_workers:8,log_search_progress:true',
                    'Sat solver parameters.')
flags.DEFINE_integer('instance', 1, 'Instance to select (1, 2, 3).', 1, 3)

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

# pytype: disable=wrong-arg-types


def bus_driver_scheduling(minimize_drivers, max_num_drivers):
    """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 FLAGS.instance == 1:
        shifts = SAMPLE_SHIFTS_SMALL
    elif FLAGS.instance == 2:
        shifts = SAMPLE_SHIFTS_MEDIUM
    elif FLAGS.instance == 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.NewIntVar(min_start_time - setup_time, max_end_time,
                            'start_%i' % d))
        end_times.append(
            model.NewIntVar(min_start_time, max_end_time + cleanup_time,
                            'end_%i' % d))
        driving_times.append(
            model.NewIntVar(0, max_driving_time, 'driving_%i' % d))
        working_times.append(
            model.NewIntVar(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.NewIntVar(0, max_driving_time,
                                                  'dr_%i_%i' % (d, s))
            no_break_driving[d, s] = model.NewIntVar(
                0, max_driving_time_without_pauses, 'mdr_%i_%i' % (d, s))
            performed[d, s] = model.NewBoolVar('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.NewBoolVar('%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).OnlyEnforceIf(source_lit)
            model.Add(total_driving[d, s] == duration).OnlyEnforceIf(source_lit)
            model.Add(no_break_driving[d,
                                       s] == duration).OnlyEnforceIf(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.NewBoolVar('%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).OnlyEnforceIf(sink_lit)
            model.Add(
                driving_times[d] == total_driving[d, s]).OnlyEnforceIf(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).OnlyEnforceIf(performed[d,
                                                                     s].Not())
            model.Add(no_break_driving[d, s] == 0).OnlyEnforceIf(
                performed[d, s].Not())
            incoming_literals[s].append(performed[d, s].Not())
            outgoing_literals[s].append(performed[d, s].Not())
            # Not 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).OnlyEnforceIf(
                performed[d, s])
            model.Add(end_times[d] >= shift[4] + cleanup_time).OnlyEnforceIf(
                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.NewBoolVar('%i from %i to %i' % (d, s, o))

                # Increase driving time
                model.Add(total_driving[d, o] == total_driving[d, s] +
                          other[5]).OnlyEnforceIf(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]).OnlyEnforceIf(lit)
                else:
                    model.Add(no_break_driving[d, o] == no_break_driving[d, s] +
                              other[5]).OnlyEnforceIf(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.NewBoolVar('working_%i' % d)
            model.Add(start_times[d] == min_start_time).OnlyEnforceIf(
                working.Not())
            model.Add(end_times[d] == min_start_time).OnlyEnforceIf(
                working.Not())
            model.Add(driving_times[d] == 0).OnlyEnforceIf(working.Not())
            working_drivers.append(working)
            outgoing_source_literals.append(working.Not())
            incoming_sink_literals.append(working.Not())
            # Conditional working time constraints
            model.Add(
                working_times[d] >= min_working_time).OnlyEnforceIf(working)
            model.Add(working_times[d] == 0).OnlyEnforceIf(working.Not())
        else:
            # Working time constraints
            model.Add(working_times[d] >= min_working_time)

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

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

    # 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.AddImplication(working_drivers[d].Not(),
                                 working_drivers[d + 1].Not())

    # 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.ScalProd(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.ScalProd(delay_literals, delay_weights))

    if not minimize_drivers and FLAGS.output_proto:
        print('Writing proto to %s' % FLAGS.output_proto)
        with open(FLAGS.output_proto, 'w') as text_file:
            text_file.write(str(model))

    # Solve model.
    solver = cp_model.CpSolver()
    if FLAGS.params:
        text_format.Parse(FLAGS.params, 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.ObjectiveValue())
        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.BooleanValue(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.ObjectiveValue())


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)