Problem: You are given n integers. You need to choose a subset and put the chosen numbers in a beautiful rectangle (rectangular matrix). Each chosen number should occupy one of its rectangle cells, each cell must be filled with exactly one chosen number. Some of the n numbers may not be chosen.

A rectangle (rectangular matrix) is called beautiful if in each row and in each column all values are different.

What is the largest (by the total number of cells) beautiful rectangle you can construct? Print the rectangle itself.

Input

The first line contains n (1 ≤ n ≤ 4⋅10^5). The second line contains n integers (1 ≤ a_i ≤ 10^9).

Output

In the first line print x (1 ≤ x ≤ n) — the total number of cells of the required maximum beautiful rectangle. In the second line print p and q (p ⋅ q=x): its sizes. In the next p lines print the required rectangle itself. If there are several answers, print any.

Examples

Input


12
3 1 4 1 5 9 2 6 5 3 5 8


Output


12
3 4
1 2 3 5
3 1 5 4
5 6 8 9


Input


5
1 1 1 1 1


Output


1
1 1
1

Solution (in JAVA):

Solution:
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

public class C {
	static PrintWriter out = new PrintWriter(System.out);

	static int N;
	static Integer ar[];
	static ArrayList<Data> freqs;
	static SuperBIT bit;
	
	static int ord[][];
	
	public static void main(String[] args) {
		FS in = new FS();
		N = in.nextInt();
		ar = new Integer[N];
		for(int i = 0; i < N; i++) ar[i] = in.nextInt();
		Arrays.sort(ar);
		
		freqs = new ArrayList<Data>();
		int l = 0, r = 0;
		while(l < N) {
			while(r < N && (int)ar[r] == (int)ar[l]) r++;
			freqs.add(new Data(ar[l],r-l));
			l=r;
		}
		Collections.sort(freqs);
		bit = new SuperBIT(N+1);
		for(Data d : freqs) {
			bit.update(1, d.occ, 1);
		}
		
		// Only need to try up to SQRT N rows
		int R = 0, C = 0;
		for(int rows = 1; rows*rows <= N; rows++) {
			
			//binary search number of columns (this one is binary serachable)
			int lo = 1, hi = N/rows;
			int best = 0;
			while(lo <= hi) {
				int mid = (lo+hi)/2;
				if(canMake(rows, mid)) {
					best = max(best, mid);
					lo = mid+1;
				}
				else hi = mid-1;
			}
			
			if(rows * best > R*C) {
				R=rows;
				C=best;
			}
		}
		
		//make R the smaaller one
		if(R > C) {
			int tmp = R;
			R = C;
			C = tmp;
		}
		
		out.println(R*C);
		out.println(R+" "+C);
		int [][] rec = build(R,C);
		for(int i = 0; i < R; i++) {
			for(int j = 0; j < C; j++) {
				out.print(rec[i][j]+" ");
			}out.println();
		}
		out.close();
	}
	
	static int[][] build(int r, int c){
		int res[][] = new int[r][c];
		
		// add the pairs
		ord = new int[r][c];
		for(int rr = 0; rr < r; rr++) {
			int cc = rr;
			int val = rr+1;
			for(int i = 0; i < c; i++) {
				ord[rr][cc] = val;
				cc = (cc+1);
				if(cc >= c) cc = 0;
				val += r;
			}
		}
		
		ArrayList<Pair> ps = new ArrayList<Pair>();
		for(int i = 0; i < r; i++)
			for(int j = 0; j < c; j++)
				ps.add(new Pair(i,j));
		Collections.sort(ps);
		
		
		int idd = 0;
		for(int i = freqs.size()-1; i >= 0; i--) {
			if(idd >= ps.size()) break;
			Data d = freqs.get(i);
			for(int j = 0; j < min(r, d.occ); j++) {
				if(idd >= ps.size()) break;
				
				Pair p = ps.get(idd);
				res[p.r][p.c] = d.num;
				idd++;
			}
		}
		
		return res;
	}
	
	static boolean canMake(int r, int c) {
		int maxUniq = min(r,c);
		int totalVals = (int) bit.query(1, maxUniq);
		return totalVals >= r*c;
	}
	
	static class Pair implements Comparable<Pair>{
		int r,c;
		public Pair(int rr, int cc) {
			r=rr;
			c=cc;
		}
		@Override
		public int compareTo(Pair o) {
			return ord[r][c] - ord[o.r][o.c];
		}
	}
	
	static class Data implements Comparable<Data>{
		int num, occ;
		public Data(int nn, int oo) {
			num=nn;
			occ = oo;
		}
		@Override
		public int compareTo(Data o) {
			return occ-o.occ;
		}
		@Override
		public String toString() {
			return "[v="+num+" f="+occ+"]";
		}
	}
	
	static int min(int a, int b) { return a < b ? a : b;}
	static int max(int a, int b) { return a > b ? a : b;}
	
	static class SuperBIT {
		  long[] dataMul, dataAdd;
		  SuperBIT(int n) {
		    dataMul = new long[n];
		    dataAdd = new long[n];
		  }
		  void update(int left, int right, long val) {
		    internalUpdate(left, val, -val * (left-1));
		    internalUpdate(right, -val, val * right);
		  }
		  void internalUpdate(int at, long mul, long add) {
		    while (at < dataMul.length) {
		      dataMul[at] += mul;
		      dataAdd[at] += add;
		      at |= (at + 1);
		    }
		  }
		  long query(int at) {
		    long mul = 0;
		    long add = 0;
		    int start = at;
		    while(at >= 0) {
		      mul += dataMul[at];
		      add += dataAdd[at];
		      at = (at & (at + 1)) -1;
		    }
		    return mul * start + add;
		  }
		  long query(int left, int right) {
		    if (left > right) {
		      int temp = left;
		      left = right;
		      right = temp;
		    }
		    return query(right) - (left > 0 ? query(left-1) : 0);
		  }
		}
	
	static class FS{
		BufferedReader br;
		StringTokenizer st;
		public FS() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {st = new StringTokenizer(br.readLine());}
				catch(Exception e) { throw null;}
			}
			return st.nextToken();
		}
		int nextInt() { return Integer.parseInt(next());}
		double nextDouble() { return Double.parseDouble(next());}
		long nextLong() { return Long.parseLong(next());}
		int[] NIA(int n) {
			int r[] = new int[n];
			for(int i = 0; i < n; i++) r[i] = nextInt();
			return r;
		}
		long[] NLA(int n) {
			long r[] = new long[n];
			for(int i = 0; i < n; i++) r[i] = nextLong();
			return r;
		}
		char[][] grid(int r, int c){
			char res[][] = new char[r][c];
			for(int i = 0; i < r; i++) {
				char l[] = next().toCharArray();
				for(int j = 0; j < c; j++) {
					res[i][j] = l[j];
				}
			}
			return res;
		}
	}
	
}