Аккаунты
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Проникнув на базу группировки «Золотое кольцо», Эггси и его бывший наставник Гарри вскоре получили доступ к ноутбуку Поппи Адамс. Теперь им необходимо вычислить, отыскать, а впоследствии и арестовать всех участников «Золотого кольца». В процессе долгих поисков агенты наткнулись на нужный им документ — список логинов и паролей всех сотрудников, с помощью которых можно войти в их аккаунты во внутренней системе группировки и узнать имя и местоположение каждого преступника.

Но Поппи оказалась очень умна и поэтому перемешала все логины и пароли в списке так, что на первый взгляд он представлен в виде списка случайных строк. Однако ребята из «Кингсман» не менее сообразительны и быстро догадались, как сопоставить две строки из списка так, чтобы одна из них оказалась логином, а вторая — подходящим паролем.

Логин представляет из себя строку, состоящую из строчных латинских букв. Корректный пароль к нему представляет собой логин с приписанными к нему справа какими-либо маленькими латинскими буквами (возможно, количество приписанных букв нулевое). То есть логин является префиксом подходящего ему пароля.

Ваша задача — отыскать соответствующие друг другу логины и пароли. Каждая строка из списка может быть использована в качестве логина или пароля ровно один раз.

Входные данные

В первой строке входного файла находится натуральное число n — количество аккаунтов (1 ≤ n ≤ 105).

В следующих 2 × n строках дано по одной строке, состоящей из строчных латинских букв.

Суммарная длина строк не превышает 5 × 105.

Выходные данные

В выходной файл выведите n строк, в каждой из которых два числа — первое из которых является индексом строки логина, а второе — индексом строки пароля.

Гарантируется, что ответ существует. Если ответов несколько, выведите любой.

Пример

Входные данные
2
abac
abacab
aba
abaa
Выходные данные
3 4
1 2