{"problem":{"name":"A. Аккаунты","description":{"content":"Проникнув на базу группировки «Золотое кольцо», Эггси и его бывший наставник Гарри вскоре получили доступ к ноутбуку Поппи Адамс. Теперь им необходимо вычислить, отыскать, а впоследствии и арестовать ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10155A"},"statements":[{"statement_type":"Markdown","content":"Проникнув на базу группировки «Золотое кольцо», Эггси и его бывший наставник Гарри вскоре получили доступ к ноутбуку Поппи Адамс. Теперь им необходимо вычислить, отыскать, а впоследствии и арестовать всех участников «Золотого кольца». В процессе долгих поисков агенты наткнулись на нужный им документ — список логинов и паролей всех сотрудников, с помощью которых можно войти в их аккаунты во внутренней системе группировки и узнать имя и местоположение каждого преступника.\n\nНо Поппи оказалась очень умна и поэтому перемешала все логины и пароли в списке так, что на первый взгляд он представлен в виде списка случайных строк. Однако ребята из «Кингсман» не менее сообразительны и быстро догадались, как сопоставить две строки из списка так, чтобы одна из них оказалась логином, а вторая — подходящим паролем. \n\nЛогин представляет из себя строку, состоящую из строчных латинских букв. Корректный пароль к нему представляет собой логин с приписанными к нему справа какими-либо маленькими латинскими буквами (возможно, количество приписанных букв нулевое). То есть логин является префиксом подходящего ему пароля.\n\nВаша задача — отыскать соответствующие друг другу логины и пароли. Каждая строка из списка может быть использована в качестве логина или пароля ровно один раз.\n\nВ первой строке входного файла находится натуральное число n — количество аккаунтов (1 ≤ n ≤ 105).\n\nВ следующих 2 × n строках дано по одной строке, состоящей из строчных латинских букв. \n\nСуммарная длина строк не превышает 5 × 105.\n\nВ выходной файл выведите n строк, в каждой из которых два числа — первое из которых является индексом строки логина, а второе — индексом строки пароля.\n\nГарантируется, что ответ существует. Если ответов несколько, выведите любой.\n\n## Входные Данные\n\nВ первой строке входного файла находится натуральное число n — количество аккаунтов (1 ≤ n ≤ 105).В следующих 2 × n строках дано по одной строке, состоящей из строчных латинских букв. Суммарная длина строк не превышает 5 × 105.\n\n## Выходные Данные\n\nВ выходной файл выведите n строк, в каждой из которых два числа — первое из которых является индексом строки логина, а второе — индексом строки пароля.Гарантируется, что ответ существует. Если ответов несколько, выведите любой.\n\n## Пример\n\nВходные данные2abacabacababaabaaВыходные данные3 41 2\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of accounts.  \nLet $ S = (s_1, s_2, \\dots, s_{2n}) $ be a sequence of $ 2n $ strings over lowercase Latin letters.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^5 $  \n2. $ \\sum_{i=1}^{2n} |s_i| \\leq 5 \\times 10^5 $  \n3. Each string $ s_i $ consists only of lowercase Latin letters.  \n4. There exists a perfect matching between $ n $ login-password pairs such that for each pair $ (s_i, s_j) $, $ s_i $ is a prefix of $ s_j $, and each string is used exactly once.  \n\n**Objective**  \nFind a bijection $ M \\subseteq \\{1, \\dots, 2n\\} \\times \\{1, \\dots, 2n\\} $ such that:  \n- $ |M| = n $,  \n- For each $ (i, j) \\in M $, $ s_i $ is a prefix of $ s_j $,  \n- Each index appears in exactly one pair,  \n- Output the set $ M $ as $ n $ pairs $ (i, j) $, where $ i $ is the index of the login and $ j $ is the index of the password.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10155A","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}