Аккаунты

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

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

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

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

В первой строке входного файла находится натуральное число $n$ --- количество аккаунтов ($1 \le n \le 10^5$).

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

Суммарная длина строк не превышает $5 \times 10^5$.

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

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