VK Cup 2015 - Finals, online mirror |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

dfs and similar

strings

trees

*2300

No tag edit access

The problem statement has recently been changed. View the changes.

×
A. Matching Names

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputTeachers 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.

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)

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/21/2024 12:56:51 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|