Проникнув на базу группировки «Золотое кольцо», Эггси и его бывший наставник Гарри вскоре получили доступ к ноутбуку Поппи Адамс. Теперь им необходимо вычислить, отыскать, а впоследствии и арестовать всех участников «Золотого кольца». В процессе долгих поисков агенты наткнулись на нужный им документ — список логинов и паролей всех сотрудников, с помощью которых можно войти в их аккаунты во внутренней системе группировки и узнать имя и местоположение каждого преступника.
Но Поппи оказалась очень умна и поэтому перемешала все логины и пароли в списке так, что на первый взгляд он представлен в виде списка случайных строк. Однако ребята из «Кингсман» не менее сообразительны и быстро догадались, как сопоставить две строки из списка так, чтобы одна из них оказалась логином, а вторая — подходящим паролем.
Логин представляет из себя строку, состоящую из строчных латинских букв. Корректный пароль к нему представляет собой логин с приписанными к нему справа какими-либо маленькими латинскими буквами (возможно, количество приписанных букв нулевое). То есть логин является префиксом подходящего ему пароля.
Ваша задача — отыскать соответствующие друг другу логины и пароли. Каждая строка из списка может быть использована в качестве логина или пароля ровно один раз.
В первой строке входного файла находится натуральное число n — количество аккаунтов (1 ≤ n ≤ 105).
В следующих 2 × n строках дано по одной строке, состоящей из строчных латинских букв.
Суммарная длина строк не превышает 5 × 105.
В выходной файл выведите n строк, в каждой из которых два числа — первое из которых является индексом строки логина, а второе — индексом строки пароля.
Гарантируется, что ответ существует. Если ответов несколько, выведите любой.
2
abac
abacab
aba
abaa
3 4
1 2