Problem: You are given a string t and n strings s_1, s_2, ..., s_n. All strings consist of lowercase Latin letters.

Let f(t, s) be the number of occurences of string s in string t. For example, f('aaabacaa', 'aa') = 3, and f('ababa', 'aba') = 2.

Calculate the value of ∑_{i=1}^{n} ∑_{j=1}^{n} f(t, s_i + s_j), where s + t is the concatenation of strings s and t. Note that if there are two pairs i_1, j_1 and i_2, j_2 such that s_{i_1} + s_{j_1} = s_{i_2} + s_{j_2}, you should include both f(t, s_{i_1} + s_{j_1}) and f(t, s_{i_2} + s_{j_2}) in answer.

Input

The first line contains string t (1 ≤ |t| ≤ 2 ⋅ 10^5).

The second line contains integer n (1 ≤ n ≤ 2 ⋅ 10^5).

Each of next n lines contains string s_i (1 ≤ |s_i| ≤ 2 ⋅ 10^5).

It is guaranteed that ∑_{i=1}^{n} |s_i| ≤ 2 ⋅ 10^5. All strings consist of lowercase English letters.

Output

Print one integer — the value of ∑_{i=1}^{n} ∑_{j=1}^{n} f(t, s_i + s_j).

Examples

Input


aaabacaa
2
a
aa


Output


5


Input


aaabacaa
4
a
a
a
b


Output


33

Solution (in JAVA):

Solution:
// Main Code at the Bottom
import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.BigInteger; 
public class Main {
	//Fast IO class
    static class FastReader {
        BufferedReader br; 
        StringTokenizer st; 
        public FastReader() {
        	boolean env=System.getProperty("ONLINE_JUDGE") != null;
        	if(!env) {
        		try {
					br=new BufferedReader(new FileReader("src\\input.txt"));
				} catch (FileNotFoundException e) {
					e.printStackTrace();
				}
        	}
        	else br = new BufferedReader(new InputStreamReader(System.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()); 
        } 
        String nextLine() {
            String str = ""; 
            try {
                str = br.readLine(); 
            } 
            catch (IOException e) {
                e.printStackTrace(); 
            } 
            return str; 
        } 
    }     
    static long MOD=1000000000+7;
    //debug
    static void debug(Object... o) {
        System.out.println(Arrays.deepToString(o));
    }
    // Pair
    static class pair{
    	long x,y;
    	pair(long a,long b){
    		this.x=a;
    		this.y=b;
    	}
    	public boolean equals(Object obj) {
    		if(obj == null || obj.getClass()!= this.getClass()) return false;
            pair p = (pair) obj;
            return (this.x==p.x && this.y==p.y);
        }
    	public int hashCode() {
            return Objects.hash(x,y);
        }
    }
    static FastReader sc=new FastReader();
    static PrintWriter out=new PrintWriter(System.out);  
    //Global variables and functions
    static int n,c[],p[];
    static char s[];
    static void count_sort() {
    	int cnt[]=new int[n],pos[]=new int[n],p_new[]=new int[n];
    	for(int x: c) cnt[x]++;
    	pos[0]=0;
    	for(int i=1;i<n;i++) pos[i]=pos[i-1]+cnt[i-1];
    	for(int x: p) {
    		int i=c[x];
    		p_new[pos[i]]=x;
    		pos[i]++;
    	}
    	p=p_new;
    }
    static void buildSA() {
    	p=new int[n];c=new int[n];
    	//k=0
		int k=0;
		pair a[]=new pair[n];
		for(int i=0;i<n;i++) a[i]=new pair(s[i]-'a',i);
		Arrays.parallelSort(a,(p1,p2)->(int)(p1.x-p2.x));
		for(int i=0;i<n;i++) p[i]=(int)a[i].y;
		c[p[0]]=0;
		for(int i=1;i<n;i++) c[p[i]]=c[p[i-1]]+(s[p[i]]==s[p[i-1]]?0:1);
		//k>0
		while((1<<k)<n) {
			for(int i=0;i<n;i++) p[i]=(p[i]-(1<<k)+n)%n;
			count_sort();
			int c_new[]=new int[n];
			c_new[p[0]]=0;
			for(int i=1;i<n;i++) {
				int prev1=c[p[i-1]],prev2=c[(p[i-1]+(1<<k))%n];
				int cur1=c[p[i]],cur2=c[(p[i]+(1<<k))%n];
				if(prev1==cur1 && prev2==cur2) c_new[p[i]]=c_new[p[i-1]];
				else c_new[p[i]]=c_new[p[i-1]]+1;
			}
			c=c_new;
			k++;
		}
    }
    static int find(char tmp[],int f) {
    	int m=tmp.length;
    	if(m>=n) return -1;
    	int l=1,r=n-1,idx=-1;
		while(l<=r) {
			int mid=l+(r-l)/2;
			int cur=0;
			while(p[mid]+cur<n && cur<m && tmp[cur]==s[p[mid]+cur]) cur++;
			if(cur==m) {
				idx=mid;
				if(f==0) r=mid-1;
				else l=mid+1;
			}
			else if(tmp[cur]<s[p[mid]+cur]) r=mid-1;
			else l=mid+1;
		}
		return idx;
    }
    //Main function(The main code starts from here)
    public static void main (String[] args) throws java.lang.Exception {
    	int test=1;
    	//test=sc.nextInt();
    	while(test-->0){
    		String str=sc.nextLine();
    		s=(str+'$').toCharArray();
    		n=s.length;
    		buildSA();
    		int m=sc.nextInt();
    		String t[]=new String[m];
    		int obj[]=new int[n+5],pre[]=new int[n],suf[]=new int[n];
    		for(int i=0;i<m;i++) t[i]=sc.nextLine();
    		for(int i=0;i<m;i++) {
    			char tmp[]=t[i].toCharArray();
    			int l=find(tmp,0),r=find(tmp,1);
    			if(l==-1) continue;
    			obj[l]++;
    			obj[r+1]--;
    		}
    		for(int i=1;i<n;i++) obj[i]+=obj[i-1];
    		for(int i=0;i<n;i++) suf[p[i]]=obj[i];
    		StringBuilder sb=new StringBuilder(str);
    		sb.reverse();
    		s=(sb+"$").toCharArray();
    		buildSA();
    		Arrays.fill(obj, 0);
    		for(int i=0;i<m;i++) {
    			StringBuilder x=new StringBuilder(t[i]);
    			x.reverse();
    			char tmp[]=(x+"").toCharArray();
    			int l=find(tmp,0),r=find(tmp,1);
    			if(l==-1) continue;
    			obj[l]++;
    			obj[r+1]--;
    		}
    		for(int i=1;i<n;i++) obj[i]+=obj[i-1];
    		for(int i=0;i<n;i++) pre[p[i]]=obj[i];
    		for(int i=0;i<n/2;i++) {
    			int tmp=pre[i];
    			pre[i]=pre[n-i-1];
    			pre[n-i-1]=tmp;
    		}
    		for(int i=0;i<n-1;i++) pre[i]=pre[i+1];
    		pre[n-1]=0;
    		long ans=0;
    		for(int i=0;i<n-1;i++) ans+=(long)pre[i]*(long)suf[i+1];
    		out.println(ans);
    	}	
        out.flush();
        out.close();
    }
}