У Поликарпа есть хобби — он разрабатывает необычную социальную сеть. Работа почти закончена, осталось только реализовать модуль, определяющий друзей. Да-да, в этой социальной сети не придется добавлять друзей вручную! Определение пар друзей осуществляется следующим образом. Пусть пользователь A написал сообщение пользователю B в момент t1, а пользователь B написал сообщение пользователю A в момент t2. Если 0 < t2 - t1 ≤ d, тогда сообщение пользователя B было ответом на сообщение пользователя A. Пользователи A и B считаются друзьями, если A ответил хотя бы на одно сообщение B или B ответил хотя бы на одно сообщение A.
Вам дан журнал переписки в хронологическом порядке и число d. Найдите все пары пользователей, которые будут считаться друзьями.
Выходные данные
В первую строку выведите целое число k — количество пар друзей. В следующих k строках выведите пары друзей в виде «Ai Bi» (без кавычек). Как пользователей в парах, так и сами пары можно выводить в любом порядке. Каждая пара должна быть выведена ровно один раз.
Примечание
В первом примере Вася и Петя — друзья, потому что времена отправки их сообщений отличаются на единицу, а Аня и Иван — нет, потому что времена отправки их сообщений отличаются больше чем на единицу.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 1
vasya petya 1
petya vasya 2
anya ivan 2
ivan anya 4
|
1
petya vasya
|
|
2
|
1 1000
a b 0
|
0
|