CF566A.Matching Names

Teachers of one programming summer school decided to make a surprise for the students by giving them names in the style of the "Hobbit" movie. Each student must get a pseudonym maximally similar to his own name. The pseudonym must be a name of some character of the popular saga and now the teachers are busy matching pseudonyms to student names.

There are n students in a summer school. Teachers chose exactly n pseudonyms for them. Each student must get exactly one pseudonym corresponding to him. Let us determine the relevance of a pseudonym b to a student with name a as the length of the largest common prefix a and b. We will represent such value as . Then we can determine the quality of matching of the pseudonyms to students as a sum of relevances of all pseudonyms to the corresponding students.

Find the matching between students and pseudonyms with the maximum quality.

某编程暑期学校教师决定为学生们准备一个惊喜，给他们起《霍比特人》电影风格的化名。每位学生必须获得一个与其本名尽可能相似的化名。该化名必须是这部广受欢迎的传奇作品中某位角色的名字，而教师们目前正忙于将化名与学生姓名进行匹配。

暑期学校共有 $n$ 名学生。教师们恰好为他们选定了 $n$ 个化名。每位学生必须被分配且仅被分配一个对应的化名。我们定义化名 $b$ 对于姓名为 $a$ 的学生的相关性（relevance）为 $a$ 与 $b$ 的最长公共前缀的长度。我们将该值记作 。那么，化名与学生之间匹配的质量即为所有化名对其对应学生的相关性之和。

请找出使匹配质量最大的学生与化名之间的匹配方案。

The first line contains number n (1 ≤ n ≤ 100 000) — the number of students in the summer school.

Next n lines contain the name of the students. Each name is a non-empty word consisting of lowercase English letters. Some names can be repeating.

The last n lines contain the given pseudonyms. Each pseudonym is a non-empty word consisting of small English letters. Some pseudonyms can be repeating.

The total length of all the names and pseudonyms doesn't exceed 800 000 characters.

第一行包含一个整数 $n$（$1 \leq n \leq 100\,000$）—— 表示暑期学校中学生的数量。

接下来的 $n$ 行，每行包含一个学生的姓名。每个姓名均为一个非空单词，仅由小写英文字母组成。部分姓名可能重复。

最后的 $n$ 行，每行包含一个给定的化名。每个化名均为一个非空单词，仅由小写英文字母组成。部分化名可能重复。

所有姓名与化名的总长度不超过 $800\,000$ 个字符。

In the first line print the maximum possible quality of matching pseudonyms to students.

In the next n lines describe the optimal matching. Each line must have the form a b (1 ≤ a, b ≤ n), that means that the student who was number a in the input, must match to the pseudonym number b in the input.

The matching should be a one-to-one correspondence, that is, each student and each pseudonym should occur exactly once in your output. If there are several optimal answers, output any.

第一行输出匹配学生与化名所能达到的最大质量值。

接下来的 $n$ 行描述最优匹配方案。每行格式为 $a\ b$（其中 $1 \le a,\,b \le n$），表示输入中编号为 $a$ 的学生应匹配输入中编号为 $b$ 的化名。

该匹配必须是一一对应关系，即每个学生和每个化名在你的输出中均恰好出现一次。若存在多个最优解，输出任意一个即可。

The first test from the statement the match looks as follows:

• bill  →  bilbo (lcp = 3)
• galya  →  galadriel (lcp = 3)
• gennady  →  gendalf (lcp = 3)
• toshik  →  torin (lcp = 2)
• boris  →  smaug (lcp = 0)

题目描述中的第一个测试用例的匹配情况如下：

• bill  →  bilbo（最长公共前缀长度 lcp = 3）
• galya  →  galadriel（最长公共前缀长度 lcp = 3）
• gennady  →  gendalf（最长公共前缀长度 lcp = 3）
• toshik  →  torin（最长公共前缀长度 lcp = 2）
• boris  →  smaug（最长公共前缀长度 lcp = 0）