Problem: 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 <image>. 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) 

Solution (in JAVA):

Solution:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.NoSuchElementException;
import java.util.StringTokenizer;

public class CodeforceSol11a {
	static FastScanner in;
	static PrintWriter out;
	
	public static class FastScanner{
		BufferedReader br;
		StringTokenizer st;
		
		public FastScanner(InputStream in){
			br = new BufferedReader(new InputStreamReader(in));
		}
		
		String next(){
			while (st == null || !st.hasMoreElements()){
				try{
					st = new StringTokenizer(br.readLine());
				} catch (IOException e){
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		
		int nextInt(){
			return Integer.parseInt(next());
		}
		
		long nextLong(){
			return Long.parseLong(next());
		}
		
		double nextDouble(){
			return Double.parseDouble(next());
		}
	}
	

	
	
	
	/*
	public static class Trie{
		
		private class Node{
		    public char value;
		    public HashMap<Character,Node> children;
		    public boolean bIsEnd;
			
		    public Node(char ch){
		        value = ch;
		        children = new HashMap<Character,Node>();
		        bIsEnd = false;
		    }
		}
		
		private Node root;
		
		public Trie(){
			root = new Node((char) 0);
		}
		
		public void addWord(String word){
	        int length = word.length();
	        Node cur = root;
	 
	        for(int level = 0; level < length; level++) {
	            HashMap<Character,Node> child = cur.children;
	            char ch = word.charAt(level);
	 
	            if(child.containsKey(ch))
	                cur = child.get(ch);
	            else
	            {
	                child.put(ch, new Node(ch) );
	                cur = child.get(ch);
	            }
	        }
	        
	        cur.bIsEnd = true;
		}
		
		
		public String getMatchPrefix(String input)  {
	        String result = "";
	        int length = input.length();     

	        Node cur = root;   
	 
	        int level, prevMatch = 0;
	        for( level = 0 ; level < length; level++ ){
	            char ch = input.charAt(level);    
	 
	            HashMap<Character,Node> child = cur.children;                        
	 
	            if(child.containsKey(ch)){
	               result += ch;          
	               cur = child.get(ch);
	               prevMatch++;
	               if(cur.bIsEnd)
	                    prevMatch = level + 1;
	            }
	            else  break;
	        }
	 
	        if( !cur.bIsEnd )
	                return result.substring(0, prevMatch);        
	 
	        else return result;
	    }
	}*/
		
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		in = new FastScanner(System.in);
		out = new PrintWriter(System.out);
		
		Task work = new Task();
		work.solve(0, in, out);
/*		
		Trie tree = new Trie();
		ArrayList<String> students = new ArrayList<String>();
		ArrayList<String> pseudo = new ArrayList<String>();
		
		
		int num_students = in.nextInt();
		for(int no = 0; no < num_students; no++){
			String name = in.next();
			students.add(name);
		}
		
		
		String[] pseudoIndx = new String[num_students];
		for(int no2 = 0; no2 < num_students; no2++){
			String word = in.next();
			pseudo.add(word);
			pseudoIndx[no2] = word;
			tree.addWord(word);
		}
		
		HashMap<Integer, Integer> result = new HashMap<Integer, Integer>();
		
		ArrayList<String> nameprefix = new ArrayList<String>();
		
		int score = 0;
		for(int st = 0; st < num_students; st++){
			String prefix = tree.getMatchPrefix(students.get(st));
			nameprefix.add(prefix);
		}
		
		boolean[] used = new boolean[num_students];
		boolean[] usedV = new boolean[num_students];
		
		ArrayList<Integer> left = new ArrayList<Integer>();
		
		while(result.size() != num_students){
			int maxidx = 0;
			int maxval = -1;
			for(int potidx = 0; potidx < num_students; potidx++){
				if(nameprefix.get(potidx).length() > maxval && used[potidx] == false){
					maxval = nameprefix.get(potidx).length();
					maxidx = potidx;
				}
			}
			
			boolean found = false;
			
			int idx = 0;
			for(int i = 0; i < num_students; i++){
				if(pseudo.get(i).startsWith(nameprefix.get(maxidx)) && usedV[i] == false){
					score += maxval;
					idx = i;
					found = true;
					usedV[i] = true;
					break;
				}
				if(usedV[i] == false){
					idx = i;
				}
			}
			if(found){
				used[maxidx] = true;
				result.put(maxidx, idx);
			}
			else{
				used[maxidx] = true;
				left.add(maxidx);
				result.put(maxidx, idx);
			}
		}
		for(int idx1 : left){
			for(int idx2 = 0; idx2 < num_students; idx2++){
				if(!usedV[idx2]){
					result.put(idx1, idx2);
					used[idx1] = true;
					usedV[idx2] = true;
					break;
				}
			}
		}
		
		
		System.out.println(score);
		int s = 0;
		for(int v: result.keySet()){
			System.out.println(Integer.toString(v+1) + " " + Integer.toString(result.get(v)+1));
			s++;
		}
		*/
		out.close();
	}
	
	
	
    static class Task {
        int sz = 1;
        final int maxSz = 800_100;
        int[][] links = new int[maxSz][26];
        IntArrayList[] name = new IntArrayList[maxSz];
        IntArrayList[] hob = new IntArrayList[maxSz];
        int[] depth = new int[maxSz];
        IntArrayList order = new IntArrayList();
        long ans = 0;
        StringBuilder answer = new StringBuilder();

        {
            ArrayUtils.fill(links, -1);
        }

        public void add(CharSequence word, boolean isName, int id) {
            int current = 0;
            int length = word.length();
            for (int i = 0; i < length; i++) {
                int letter = word.charAt(i) - 'a';
                if (links[current][letter] == -1)
                    links[current][letter] = sz++;
                current = links[current][letter];
                depth[current] = i + 1;
            }

            if (name[current] == null) name[current] = new IntArrayList(1);
            if (hob[current] == null) hob[current] = new IntArrayList(1);
            if (isName)
                name[current].add(id);
            else
                hob[current].add(id);
        }

        void dfs(int v) {
            for (int ch = 0; ch < 26; ++ch) {
                int link = links[v][ch];
                if (link == -1) continue;
                dfs(link);
            }
            order.add(v);

        }

        private void upd(int v) {
            for (int ch = 0; ch < 26; ++ch) {
                int link = links[v][ch];
                if (link == -1) continue;
                name[v] = f(name[v], name[link]);
                hob[v] = f(hob[v], hob[link]);
            }

            while (0 < hob[v].size() && 0 < name[v].size()) {
                answer.append(name[v].popBack()).append(" ").append(hob[v].popBack()).append("\n");
                ans += depth[v];
            }
        }

        private IntArrayList f(IntArrayList a, IntArrayList b) {
            if (a == null) return b;
            if (b == null) return a;
            if (a.size() < b.size())
                return f(b, a);
            for (int i = 0; i < b.size(); i++) {
                a.add(b.get(i));
            }
            return a;
        }

        public void solve(int testNumber, FastScanner in, PrintWriter out) {

            int n = in.nextInt();
            for (int i = 0; i < n; i++) {
                add(in.next(), true, i + 1);
            }
            for (int i = 0; i < n; i++) {
                add(in.next(), false, i + 1);
            }

            dfs(0);
            for (int i = 0; i < order.size(); ++i)
                upd(order.get(i));

            out.println(ans);
            out.println(answer);
            out.flush();
        }


        static abstract class IntList extends IntCollection implements Comparable<IntList> {
            public abstract int get(int index);


            public IntIterator iterator() {
                return new IntIterator() {
                    private int size = size();
                    private int index = 0;

                    public int value() throws NoSuchElementException {
                        if (!isValid())
                            throw new NoSuchElementException();
                        return get(index);
                    }

                    public void advance() throws NoSuchElementException {
                        if (!isValid())
                            throw new NoSuchElementException();
                        index++;
                    }

                    public boolean isValid() {
                        return index < size;
                    }
                };
            }

            public int hashCode() {
                int hashCode = 1;
                for (IntIterator i = iterator(); i.isValid(); i.advance())
                    hashCode = 31 * hashCode + i.value();
                return hashCode;
            }


            public boolean equals(Object obj) {
                if (!(obj instanceof IntList))
                    return false;
                IntList list = (IntList) obj;
                if (list.size() != size())
                    return false;
                IntIterator i = iterator();
                IntIterator j = list.iterator();
                while (i.isValid()) {
                    if (i.value() != j.value())
                        return false;
                    i.advance();
                    j.advance();
                }
                return true;
            }

            public int compareTo(IntList o) {
                IntIterator i = iterator();
                IntIterator j = o.iterator();
                while (true) {
                    if (i.isValid()) {
                        if (j.isValid()) {
                            if (i.value() != j.value()) {
                                if (i.value() < j.value())
                                    return -1;
                                else
                                    return 1;
                            }
                        } else
                            return 1;
                    } else {
                        if (j.isValid())
                            return -1;
                        else
                            return 0;
                    }
                    i.advance();
                    j.advance();
                }
            }

        }

        static abstract class IntCollection {
            public abstract IntIterator iterator();

            public abstract int size();

            public abstract void add(int value);

            public void addAll(IntCollection values) {
                for (IntIterator it = values.iterator(); it.isValid(); it.advance()) {
                    add(it.value());
                }
            }

        }

        static class ArrayUtils {
            public static void fill(int[][] array, int value) {
                for (int[] row : array)
                    Arrays.fill(row, value);
            }

        }

        static class IntArrayList extends IntList {
            private int[] array;
            private int size;

            public IntArrayList() {
                this(10);
            }

            public IntArrayList(int capacity) {
                array = new int[capacity];
            }

            public IntArrayList(IntList list) {
                this(list.size());
                addAll(list);
            }


            public int get(int index) {
                if (index >= size)
                    throw new IndexOutOfBoundsException();
                return array[index];
            }


            public int size() {
                return size;
            }


            public void add(int value) {
                ensureCapacity(size + 1);
                array[size++] = value;
            }

            public void ensureCapacity(int newCapacity) {
                if (newCapacity > array.length) {
                    int[] newArray = new int[Math.max(newCapacity, array.length << 1)];
                    System.arraycopy(array, 0, newArray, 0, size);
                    array = newArray;
                }
            }


            public int popBack() {
                return array[--size];
            }

        }

        static interface IntIterator {
            public int value();

            public void advance();

            public boolean isValid();

        }
    }
	
}