Being a true expert in rhetorics and NLP, Rudolph spends a lot of time on different forums and online discussions. Recently he has heard about some progress in artificial intelligence and decided to develop an algorithm to reply questions for him, keeping quality of the answers best possible.
Rudolph knows in advance that he will need to reply exactly $n$ questions, and that is why he prepares $n$ different strings — answers to the upcoming questions. Then, the algorithm takes $n$ questions as an input and matches them with the answers. Of course, in order for Rudolph's wit not to be doubted, each answer must be used exactly once.
It is a well known fact that Rudolph is a master of words and rhymes, and therefore artificial intelligence must be smart enough to give the most original and appropriate responses. To evaluate the quality of the algorithm, Rudolph came up with the following metric.
The value of the metric equals to the sum of rhyming values for each question-answer pair. The rhyming of one pair is evaluated as follows: all characters except lowercase Latin letters are removed from the question and answer, and the length of their largest common suffix is calculated. This length will be the rhyming value for this pair.
You need to develop such an algorithm to match the questions with answers and calculate the largest possible value of the metric. If there are several possible responses with optimal values of the metric, choose any.
The first line contains a single integer $n$ – the number of questions and answers ($1 <= n <= 800$). Each of the following $n$ lines has one string — a question. Then, each of the following $n$ lines has one string — an answer.
Each string consists of lowercase Latin letters, spaces and symbols "?" "!" and ")".
Total length of all strings does not exceed $200000$.
The first line of the output should contain the answer — optimal value of the metric (the sum of rhymings of all pairs question-answer). Then, in the following $2 n$ lines print the pairs question-answer: questions in the same order, as in the input, and each question having the corresponding answer on the next line.
Suppose that we want to calculate rhyming for the pair
"abc d ef!!!" and "lol k e k cd?)ef?"
To do this, we remove all the symbols, except for lowercase Latin letters: "abcdef", "lolkekcdef", and then we find the length of the longest common suffix, which is 4.
## Input
The first line contains a single integer $n$ – the number of questions and answers ($1 <= n <= 800$). Each of the following $n$ lines has one string — a question. Then, each of the following $n$ lines has one string — an answer.Each string consists of lowercase Latin letters, spaces and symbols "?" "!" and ")".Total length of all strings does not exceed $200000$.
## Output
The first line of the output should contain the answer — optimal value of the metric (the sum of rhymings of all pairs question-answer). Then, in the following $2 n$ lines print the pairs question-answer: questions in the same order, as in the input, and each question having the corresponding answer on the next line.
[samples]
## Note
Suppose that we want to calculate rhyming for the pair"abc d ef!!!" and "lol k e k cd?)ef?"To do this, we remove all the symbols, except for lowercase Latin letters: "abcdef", "lolkekcdef", and then we find the length of the longest common suffix, which is 4.
**Definitions**
Let $ n \in \mathbb{Z}^+ $, $ n \leq 800 $.
Let $ Q = (q_1, \dots, q_n) $ be the sequence of question strings.
Let $ A = (a_1, \dots, a_n) $ be the sequence of answer strings.
For any string $ s $, define $ \text{clean}(s) $ as the string obtained by removing all characters except lowercase Latin letters.
For two strings $ x, y $, define $ \text{rhyme}(x, y) = |\text{lcsuf}(\text{clean}(x), \text{clean}(y))| $, where $ \text{lcsuf}(u, v) $ is the longest common suffix of $ u $ and $ v $.
**Constraints**
1. Total length of all strings in $ Q \cup A $ is $ \leq 200000 $.
2. Each answer must be used exactly once; each question matched to exactly one answer.
**Objective**
Find a permutation $ \sigma \in S_n $ maximizing:
$$
\sum_{i=1}^{n} \text{rhyme}(q_i, a_{\sigma(i)})
$$
Output the maximum sum and a corresponding matching: for each $ i \in \{1, \dots, n\} $, output $ q_i $ followed by $ a_{\sigma(i)} $.