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 $\operatorname{lcp}(a, b)$. 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.


-----Input-----

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.


-----Output-----

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.


-----Examples-----
Input
5
gennady
galya
boris
bill
toshik
bilbo
torin
gendalf
smaug
galadriel

Output
11
4 1
2 5
1 3
5 2
3 4



-----Note-----

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)

Difficulty: interview

Starter code:

Solutions:
import sys

SIGMA = 26

nodes = []
pairs = []
res = 0

class Node:
    def __init__(self):
        self.ch = {}
        self.a = []
        self.b = []
        self.d = 0

    def add(self, s, i):
        t = self
        for c in s:
            v = ord(c) - ord('a')
            if not v in t.ch:
                t.ch[v] = Node()
                t.ch[v].d = t.d + 1
                nodes.append(t.ch[v])
            t = t.ch[v]
        t.a.append(i)

    def inc(self, s, i):
        t = self
        for c in s:
            v = ord(c) - ord('a')
            if not v in t.ch:
                break
            t = t.ch[v]
        t.b.append(i)

    def solve(self):
        nonlocal pairs
        nonlocal res
        for i in range(SIGMA):
            if i in self.ch:
                self.a.extend(self.ch[i].a)
                self.b.extend(self.ch[i].b)
        k = min(len(self.a), len(self.b))
        for i in range(k):
            pairs.append(str(self.a[-1]) + ' ' + str(self.b[-1]))
            self.a.pop()
            self.b.pop()
            res += self.d
        return res

sys.setrecursionlimit(2000000)
_input = sys.stdin.readlines()
_input = [s[:-1] for s in _input]
N = int(_input[0])
A = _input[1 : N + 1]
B = _input[N + 1 :]
T = Node()
nodes.append(T)
for i, s in enumerate(A):
    T.add(s, i + 1)
for i, s in enumerate(B):
    T.inc(s, i + 1)
for n in reversed(nodes):
    n.solve()
print(res)
print('\n'.join(pairs))


import sys

SIGMA = 26

nodes = []
pairs = []
res = 0

class Node:
    def __init__(self):
        self.ch = {}
        self.a = []
        self.b = []
        self.d = 0

    def add(self, s, i):
        t = self
        for c in s:
            v = ord(c) - ord('a')
            if not v in t.ch:
                t.ch[v] = Node()
                t.ch[v].d = t.d + 1
                nodes.append(t.ch[v])
            t = t.ch[v]
        t.a.append(i)

    def inc(self, s, i):
        t = self
        for c in s:
            v = ord(c) - ord('a')
            if not v in t.ch:
                break
            t = t.ch[v]
        t.b.append(i)

    def solve(self):
        nonlocal pairs
        nonlocal res
        for i in range(SIGMA):
            if i in self.ch:
                self.a.extend(self.ch[i].a)
                self.b.extend(self.ch[i].b)
        k = min(len(self.a), len(self.b))
        for i in range(k):
            pairs.append(str(self.a[-1]) + ' ' + str(self.b[-1]))
            self.a.pop()
            self.b.pop()
            res += self.d
        return res

_input = sys.stdin.readlines()
_input = [s[:-1] for s in _input]
N = int(_input[0])
A = _input[1 : N + 1]
B = _input[N + 1 :]
T = Node()
nodes.append(T)
for i, s in enumerate(A):
    T.add(s, i + 1)
for i, s in enumerate(B):
    T.inc(s, i + 1)
for n in reversed(nodes):
    n.solve()
print(res)
print('\n'.join(pairs))


import sys

class Node:
    def __init__(self, d):
        nonlocal nodes
        self.ch = {}
        self.a = [[], []]
        self.d = d
        nodes += [self]

nodes = []
pairs = []
res = 0

N = int(sys.stdin.readline())
_input = sys.stdin.readlines()
_input = [s[:-1] for s in _input]
A = [_input[:N], _input[N:]]
T = Node(0)

for i, l in enumerate(A):
    for j, s in enumerate(l):
        t = T
        for c in s:
            v = ord(c) - ord('a')
            if not v in t.ch:
                t.ch[v] = Node(t.d + 1)
            t = t.ch[v]
        t.a[i] += [j + 1]

for n in reversed(nodes):
    for i in n.ch:
        n.a[0] += n.ch[i].a[0]
        n.a[1] += n.ch[i].a[1]
    k = min(len(n.a[0]), len(n.a[1]))
    for i in range(k):
        pairs += [str(n.a[0][-1]) + ' ' + str(n.a[1][-1])]
        n.a[0].pop()
        n.a[1].pop()
        res += n.d

print(res)
print('\n'.join(pairs))


import sys

class Node:
    def __init__(self, d):
        nonlocal nodes
        self.ch = {}
        self.a = [[], []]
        self.d = d
        nodes += [self]

nodes = []
pairs = []
res = 0

N = int(sys.stdin.readline())
_input = sys.stdin.readlines()
_input = [s[:-1] for s in _input]
A = [_input[:N], _input[N:]]
T = Node(0)

for i, l in enumerate(A):
    for j, s in enumerate(l):
        t = T
        for c in s:
            v = ord(c) - ord('a')
            if not v in t.ch:
                t.ch[v] = Node(t.d + 1)
            t = t.ch[v]
        t.a[i] += [j + 1]

for n in reversed(nodes):
    for i in n.ch:
        n.a[0] += n.ch[i].a[0]
        n.a[1] += n.ch[i].a[1]
    k = min(len(n.a[0]), len(n.a[1]))
    for i in range(k):
        pairs += [str(n.a[0][-1]) + ' ' + str(n.a[1][-1])]
        n.a[0].pop()
        n.a[1].pop()
        res += n.d

print(res)
print('\n'.join(pairs))