В Двумерном королевстве наступили тяжелые времена... Сегодня утром Трехмерное королевство объявило войну Двумерному и в ходе этого (возможно, вооруженного) конфликта решится, кому же все-таки принадлежит прямая.
В Двумерном королевстве есть постоянная армия, состоящая из n человек. Каждый боец прошел специальную регистрацию и указал желаемый размер бронежилета: i-ый боец указал размер ai. Известно, что бойцы люди неприхотливые, поэтому штаб считает, что им комфортно носить любые бронежилеты с размерами от ai - x до ai + y включительно (числа x, y ≥ 0 заданы).
В распоряжении армии Двумерного королевства есть m бронежилетов, размер j-го бронежилета равен bj. Помогите мобилизовать армию Двумерного королевства — оденьте наибольшее возможное количество бойцов армии в бронежилеты. Каждый бронежилет разрешается использовать только один раз. i-ый боец может надеть j-ый бронежилет, если ai - x ≤ bj ≤ ai + y.
Выходные данные
В первой строке выведите единственное целое число k — максимальное количество одетых в бронежилеты бойцов.
В следующих k строках выведите k пар, по одной паре в строке в формате «ui vi» (без кавычек). Пара (ui, vi) означает, что боец с номером ui должен быть одет в бронежилет номер vi. Бойцы и бронежилеты нумеруются, начиная с единицы, в том порядке, в котором они заданы во входных данных. Все номера бойцов в парах должны быть попарно различны, все номера бронежилетов в парах также должны быть попарно различны. Пары можно выводить в любом порядке.
Если существует несколько оптимальных ответов, разрешается вывести любой.
Примечание
В первом примере требуется точное совпадение размеров бронежилетов: первый боец получает первый бронежилет (размер 1), а третий — второй бронежилет (размер 3). В этом примере возможен другой ответ, в котором второй бронежилет достается не третьему, а четвертому бойцу.
Во втором примере размер бронежилета должен отличаться от пожеланий бойца не больше чем на 2 размера, и одеть можно всех бойцов.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 3 0 0
1 2 3 3 4
1 3 5
|
2
1 1
3 2
|
|
2
|
3 3 2 2
1 5 9
3 5 7
|
3
1 1
2 2
3 3
|