(М. Шагитов) В одном из конференц-залов города Н проводится научная конференция. Известно, какие места в зале уже забронированы для участников конференции из других городов и для участников конференции из города Н. Найдите ряд с наибольшим номером, в котором есть ровно сто свободных мест подряд между участниками из других городов, а также хотя бы пятьсот мест, занятых участниками из города Н. Гарантируется, что есть хотя бы один ряд, удовлетворяющий этому условию.
Входные данные представлены в файле 26-85.txt следующим образом. В первой строке входного файла записано натуральное число N -- общее количество занятых мест (1 ≤ N ≤ 600 000). В каждой из следующих N строках находятся по целых числа, не превышающих 25 000. Первые два числа -- это номер ряда и место в ряду, занятое участником конференции (натуральные числа). Если третье число равно 0, то место занято участником из города Н, а если оно равно 1, то участником из другого города.
Запишите в ответе два числа: максимальный номер подходящего ряда и количество мест, занятых в этом ряду участниками из других городов.
Пример входного файла:
15
1 1 0
1 3 1
1 5 0
1 7 1
1 8 0
2 3 1
2 8 1
2 9 0
2 10 0
3 1 0
3 2 1
3 6 1
3 7 0
3 8 0
3 9 0
В примере требуется найти ряд, в котором есть ровно три свободных места между участниками из других городов, а также хотя бы четыре занятых места, занятые участниками из города Н.
| |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
| 1 |
0 |
|
1 |
|
0 |
|
1 |
0 |
|
|
| 2 |
|
|
1 |
|
|
|
|
1 |
0 |
0 |
| 3 |
0 |
1 |
|
|
|
1 |
0 |
0 |
0 |
|
В 3-м ряду есть 3 свободных места подряд между участниками из других городов (выделены жёлтым) и 4 места заняты участниками из города Н. В этом ряду 2 места заняты участниками из других городов (выделены зеленым). Ответ: 3 2.