Преподаватели одной летней школы по программированию решили устроить сюрприз для школьников, подобрав им имена в сеттинге фильма «Хоббит». Каждый школьник должен получить псевдоним, максимально схожий с его собственным именем, при этом являющийся именем какого-то из персонажей популярной саги, и сейчас преподаватели заняты сопоставлением псевдонимов именам школьников.
В смене участвуют n школьников. Преподаватели подобрали для них ровно n псевдонимов. Каждому школьнику нужно поставить в соответствие ровно один псевдоним. Определим уместность псевдонима b школьнику с именем a как длину наибольшего общего префикса a и b. Мы будем обозначать такую величину как 
. Тогда мы можем определить качество соответствия школьников псевдонимам как сумму уместностей всем псевдонимам соответствующих им школьников.
Найдите соответствие школьников псевдонимам с максимальным качеством.
В первой строке находится число n (1 ≤ n ≤ 100 000) — количество школьников в летней школе.
В последующих n строках находятся имена школьников. Каждое имя является непустым словом, состоящим из строчных английских букв. Среди имён могут быть повторяющиеся.
В последних n строках находятся предполагаемые псевдонимы. Каждый псевдоним является непустым словом, состоящим из строчных английских букв. Среди псевдонимов могут быть повторяющиеся.
Суммарная длина всех имён и псевдонимов не превосходит 800 000 символов.
В первой строке выведите максимальное возможное качество соответствия школьникам псевдонимов.
В последующих n строках опишите само оптимальное соответствие. Каждая строка должна иметь вид a b (1 ≤ a, b ≤ n), что означает, что школьник, шедший под номером a во входных данных, должно быть сопоставлен псевдониму, шедшему под номером b во входных данных.
Соответствие должно быть взаимно-однозначным, то есть каждый школьник и каждый псевдоним должен встретиться в вашем выводе ровно один раз. Если возможных оптимальных ответов несколько, выведите любой.
5
gennady
galya
boris
bill
toshik
bilbo
torin
gendalf
smaug
galadriel
11
4 1
2 5
1 3
5 2
3 4
В первом тесте из условия сопоставление выглядит следующим образом:
- bill → bilbo (lcp = 3)
- galya → galadriel (lcp = 3)
- gennady → gendalf (lcp = 3)
- toshik → torin (lcp = 2)
- boris → smaug (lcp = 0)
