Задача 46. Мы могли бы служить в разведке ≡

Условие

...

От Алтуфьево до Пражской

Лишь на первый взгляд далеко:

Мы везем московские тайны

По секретным веткам метро.

...

Илья Калинников, "Метро", 2000 г.

Видеоклип

Супер-шпион агент-007 прибыл в столицу России, чтобы собрать слухи о секретном перегоне на Серпуховско-Тимирязевской линии московского метро. Всего на этой ветке n станций (и, соответственно n − 1 перегон), которыми пользуются москвичи и гости столицы. Джеймс Бонд под видом простого туриста несколько раз проехал из конца в конец этой ветки и узнал продолжительность в минутах для каждого перегона — a_i. Подозрения подтвердились — отдельные отечественные чиновники высокого ранга тратили на перемещение из конца в конец линии существенно меньше времени — всего t минут. Завербованный агент Епифан сообщил дополнительные сведения: между двумя станциями вроде бы существует секретный перегон, перемещение по которому занимает всего k минут, но где он находится — государственная тайна, доступа к которой у него нет. Немного подумав, агент-007 определил все возможные места для секретного перегона.

Формат входных данных

Первая строка входного файла содержит три натуральных числа, записанных через пробел: n — количество станций, k — время поездки по тайному перегону и t — время поездки по всей ветке метро чиновников высокого ранга. Во второй строке через пробел расположены n − 1 натуральных чисел a_i — время поездок по обычным перегонам в порядке следования по линии метро.

Формат выходных данных

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

Ограничения

2 ≤ n ≤ 10⁵

1 ≤ a_i, k, t ≤ 10⁹

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при n = 2, получат не менее 10 баллов.

Решения, верно работающие при n = 3, получат не менее 20 баллов.

Пояснение к примерам:

В первом примере дано 11 станций. Время перемещения по секретному перегону — 3 минуты, воспользовавшись которым, чиновники высокого ранга затратят на общий путь всего 15 минут. Смотри рисунок:

Существует всего 5 подходящих мест, где может быть расположен такой секретный перегон.

Во втором примере входные данные таковы, что секретный путь невозможен.

Примеры тестов

11 3 15
1 2 1 3 4 1 2 5 3 1

5
1 6
2 7
3 8
6 10
7 11

2 5 10
10

0