Problem: To confuse the opponents, the Galactic Empire represents fractions in an unusual format. The fractions are represented as two sets of integers. The product of numbers from the first set gives the fraction numerator, the product of numbers from the second set gives the fraction denominator. However, it turned out that the programs that work with fractions in this representations aren't complete, they lack supporting the operation of reducing fractions. Implement this operation and the Empire won't forget you.

Input

The first input line contains two space-separated integers n, m (1 ≤ n, m ≤ 105) that show how many numbers the first set (the numerator) and the second set (the denominator) contain, correspondingly.

The second line contains n space-separated integers: a1, a2, ..., an (1 ≤ ai ≤ 107) — the numbers that are multiplied to produce the numerator.

The third line contains m space-separated integers: b1, b2, ..., bm (1 ≤ bi ≤ 107) — the numbers that are multiplied to produce the denominator.

Output

Print the answer to the problem in the form, similar to the form of the input data. The number of values in the sets you print nout, mout must satisfy the inequality 1 ≤ nout, mout ≤ 105, and the actual values in the sets aout, i and bout, i must satisfy the inequality 1 ≤ aout, i, bout, i ≤ 107. 

Separate the values in the lines by spaces. The printed fraction must be reduced, that is, there mustn't be such integer x (x > 1), that the numerator and the denominator of the printed fraction are divisible by x. If there are several matching answers, print any of them.

Examples

Input

3 2
100 5 2
50 10


Output

2 3
2 1
1 1 1


Input

4 3
2 5 10 20
100 1 3


Output

1 1
20
3

Note

In the first test sample the numerator equals 1000, the denominator equals 500. If we reduce fraction 1000/500 by the greatest common divisor of the numerator and the denominator (by 500), we obtain fraction 2/1.

In the second test sample the numerator equals 2000, the denominator equals 300. If we reduce fraction 2000/300 by the greatest common divisor of the numerator and the denominator (by 100), we obtain fraction 20/3.

Solution (in JAVA):

Solution:
import java.util.*;
import java.io.*;

public class Solution
{
       static class Reader {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;
 
        public Reader()
        {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }
 
        public Reader(String file_name) throws IOException
        {
            din = new DataInputStream(
                new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }
 
        public String readLine() throws IOException
        {
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1) {
                if (c == '\n') {
                    if (cnt != 0) {
                        break;
                    }
                    else {
                        continue;
                    }
                }
                buf[cnt++] = (byte)c;
            }
            return new String(buf, 0, cnt);
        }
 
        public int nextInt() throws IOException
        {
            int ret = 0;
            byte c = read();
            while (c <= ' ') {
                c = read();
            }
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
 
            if (neg)
                return -ret;
            return ret;
        }
 
        public long nextLong() throws IOException
        {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }
 
        public double nextDouble() throws IOException
        {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
 
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
 
            if (c == '.') {
                while ((c = read()) >= '0' && c <= '9') {
                    ret += (c - '0') / (div *= 10);
                }
            }
 
            if (neg)
                return -ret;
            return ret;
        }
 
        private void fillBuffer() throws IOException
        {
            bytesRead = din.read(buffer, bufferPointer = 0,
                                 BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }
 
        private byte read() throws IOException
        {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }
 
        public void close() throws IOException
        {
            if (din == null)
                return;
            din.close();
        }
    }
    static int parent(int x , int p[])
    {
           if(p[x] == x)
           return x;
           
           return (p[x] = parent(p[x],p));
    }
    
    static void union(int a , int b , int p[] , int size[])
    {
           a = parent(a,p);
           b = parent(b,p);
           
           if(size[a] < size[b])
           {
                  int temp = a;
                  a = b;
                  b = temp;
           }
           p[b] = a;
           size[a] += size[b];
    }
    
   static long getSum(int index , long BITree[])
    {
        int sum = 0; // Iniialize result
      
        // index in BITree[] is 1 more than
        // the index in arr[]
        index = index + 1;
      
        // Traverse ancestors of BITree[index]
        while(index>0)
        {
            // Add current element of BITree 
            // to sum
            sum += BITree[index];
      
            // Move index to parent node in 
            // getSum View
            index -= index & (-index);
        }
        return sum;
    }
  
    // Updates a node in Binary Index Tree (BITree)
    // at given index in BITree. The given value 
    // 'val' is added to BITree[i] and all of 
    // its ancestors in tree.
    public static void updateBIT(int n, int index, 
                                        long val , long BITree[])
    {
        // index in BITree[] is 1 more than 
        // the index in arr[]
        index = index + 1;
      
        // Traverse all ancestors and add 'val'
        while(index <= n)
        {
        // Add 'val' to current node of BIT Tree
        BITree[index] += val;
      
        // Update index to that of parent 
        // in update View
        index += index & (-index);
        }
    }
  
  
       public static void main(String []args) throws IOException
       {
             Reader sc = new Reader();
             int n = 10000000;
             int prime[] = new int[n + 1];
        for (int i = 0; i <= n; i++)
            prime[i] = i;
 
        for (int p = 2; p * p <= n; p++)
        {
            // If prime[p] is not changed, then it is a
            // prime
            if (prime[p] == p)
            {
                // Update all multiples of p
                for (int i = p * p; i <= n; i += p)
                    prime[i] = p;
            }
        }
 
             int nn = sc.nextInt();
             int mm = sc.nextInt();
             int a[] = new int[n+1];
             int b[] = new int[n+1];
             int arr1[] = new int[nn];
             int arr2[] = new int[mm];
             for(int i = 0 ; i < nn ; i++)
             {
                    int x = sc.nextInt();
                    arr1[i] = x;
                    while(x > 1)
                    {
                       int y = prime[x];
                       int tot = 0;
                       while(x%y == 0)
                       {
                              tot++;
                              x = x/y;
                       }
                       a[y] += tot;
                    }
             }
             
             
             for(int i = 0 ; i < mm ; i++)
             {
                    int x = sc.nextInt();
                    arr2[i] = x;
                    while(x > 1)
                    {
                       int y = prime[x];
                       int tot = 0;
                       while(x%y == 0)
                       {
                              tot++;
                              x = x/y;
                       }
                       b[y] += tot;
                    }
             }
             
             for(int i = 1 ; i <= n ; i++)
             {
                    a[i] = Math.min(a[i],b[i]);
                    b[i] = a[i];
             }
             System.out.println(nn + " " + mm);
             for(int i = 0 ; i < nn ; i++)
             {
                    int x = arr1[i];
                    while(x > 1)
                    {
                           int y = prime[x];
                           int tot = 0;
                           int xx = x;
                           while(x%y == 0)
                           {
                                  x = x/y;
                                  tot++;
                           }
                           if(a[y] > tot)
                           {
                                  a[y] -= tot;
                                  arr1[i] /= (int)Math.pow(y,tot);
                                  tot = 0;
                           }
                           
                           else
                           {
                                  arr1[i] /= (int)Math.pow(y,a[y]);
                                 
                                  tot -= a[y];
                                   a[y] = 0;
                           }
                           
                    }
             }
            //System.out.println(b[2]);
             for(int i = 0 ; i < mm ; i++)
             {
                    int x = arr2[i];
                    while(x > 1)
                    {
                           int y = prime[x];
                           int tot = 0;
                           int xx = x;
                           while(x%y == 0)
                           {
                                  x = x/y;
                                  tot++;
                           }
                           if(b[y] > tot)
                           {
                                  b[y] -= tot;
                                  arr2[i] /= (int)Math.pow(y,tot);
                                  tot = 0;
                           }
                           
                           else
                           {
                                  arr2[i] /= (int)Math.pow(y,b[y]);
                                 
                                  tot -= b[y];
                                   b[y] = 0;
                           }
                           
                    }
             }
             
             StringBuffer str = new StringBuffer("");
             for(int i = 0 ; i < nn ; i++)
             {
                    str.append(arr1[i] + " ");
             }
             str.append(System.lineSeparator());
             for(int i = 0 ; i < mm ; i++)
             {
                    str.append(arr2[i] + " ");
             }
             System.out.println(str);
       }
}

class pair
{
       int val,idx;
       public pair(int val , int idx)
       {
              this.val = val;
              this.idx = idx;
       }
}

class Compare implements Comparator<pair>
{
       public int comapre(pair a , pair b)
       {
              return b.val-a.val;
       }
}