Problem: Professor GukiZ has two arrays of integers, a and b. Professor wants to make the sum of the elements in the array a sa as close as possible to the sum of the elements in the array b sb. So he wants to minimize the value v = |sa - sb|.

In one operation professor can swap some element from the array a and some element from the array b. For example if the array a is [5, 1, 3, 2, 4] and the array b is [3, 3, 2] professor can swap the element 5 from the array a and the element 2 from the array b and get the new array a [2, 1, 3, 2, 4] and the new array b [3, 3, 5].

Professor doesn't want to make more than two swaps. Find the minimal value v and some sequence of no more than two swaps that will lead to the such value v. Professor makes swaps one by one, each new swap he makes with the new arrays a and b.

Input

The first line contains integer n (1 ≤ n ≤ 2000) — the number of elements in the array a.

The second line contains n integers ai ( - 109 ≤ ai ≤ 109) — the elements of the array a.

The third line contains integer m (1 ≤ m ≤ 2000) — the number of elements in the array b.

The fourth line contains m integers bj ( - 109 ≤ bj ≤ 109) — the elements of the array b.

Output

In the first line print the minimal value v = |sa - sb| that can be got with no more than two swaps.

The second line should contain the number of swaps k (0 ≤ k ≤ 2).

Each of the next k lines should contain two integers xp, yp (1 ≤ xp ≤ n, 1 ≤ yp ≤ m) — the index of the element in the array a and the index of the element in the array b in the p-th swap.

If there are several optimal solutions print any of them. Print the swaps in order the professor did them.

Examples

Input

5
5 4 3 2 1
4
1 1 1 1


Output

1
2
1 1
4 2


Input

5
1 2 3 4 5
1
15


Output

0
0


Input

5
1 2 3 4 5
4
1 2 3 4


Output

1
1
3 1

Solution (in JAVA):

Solution:

import java.io.*;
import java.util.*;

public class D {
	InputStream is;

	int __t__ = 1;
	int __f__ = 0;
	int __FILE_DEBUG_FLAG__ = __f__;
	String __DEBUG_FILE_NAME__ = "src/D1";

	FastScanner in;
	PrintWriter out;

	final long INF = 10000000000000000L;
	class Pair {
		int x;
		int y;

		Pair(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	
	class State implements Comparable<State> {
		long sum;
		int a;
		int b;
		
		State (long sum, int a, int b) {
			this.sum = sum;
			this.a = a;
			this.b = b;
		}
		
		public int compareTo(State s) {
			return Long.compare(sum, s.sum);	
		}
		
		public String toString() {
			return sum + "";
		}
		public String dump(String symbol) {
			return symbol + " : " + sum + " " + a + " " + b;
		}
	}

	int lower_bound(State[] a, long key) {
		int lo = -1, hi = a.length - 1;
		while (hi - lo > 1) {
			int mid = (hi + lo) / 2;
			if (a[mid].sum < key)
				lo = mid;
			else
				hi = mid;
		}
		return hi;
	}
		
	public void solve() {
		int n = in.nextInt();
		int[] a = in.nextIntArray(n);
		int m = in.nextInt();
		int[] b = in.nextIntArray(m);
		
		long as = 0, bs = 0;
		for (int i = 0; i < n; i++) as += a[i];
		for (int i = 0; i < m; i++) bs += b[i];
		
		long v = Math.abs(as - bs);
		int k = 0;
		ArrayList<Pair> ps = new ArrayList<Pair>();
		// k = 1
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				long nas = as - a[i] + b[j], nbs = bs - b[j] + a[i];
				long diff = Math.abs(nas - nbs);
				if (diff < v) {
					v = diff;
					k = 1;
					ps.clear();
					ps.add(new Pair(i, j));
				}
			}
		}
		
		// k = 2
		State[] sums = new State[(n*(n-1))/2+2];
		int cur = 0;
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				long nas = as - 2 * a[i] - 2 * a[j];
				sums[cur++] = new State(nas, i, j);
			}
		}
		sums[cur++] = new State(-INF, -1, -1);
		sums[cur++] = new State(INF, -1, -1);
		
		Arrays.sort(sums);
		int[] prev = new int[n*(n-1)/2+2];
		
		for (int i = 0; i < prev.length; i++) {
			int c = 0;
			prev[i] = ++c;
			while (i < prev.length - 1 && sums[i].sum == sums[i+1].sum)
				prev[++i] = ++c;
		}
		for (int i = 0; i < m; i++) {
			for (int j = i + 1; j < m; j++) {
				long nbs = bs - 2 * b[i] - 2 * b[j];
				
				int hi = lower_bound(sums, nbs);
				int lo = hi - prev[hi];
				if (lo >= 0) {
					State ceil = sums[lo];
					long diff = Math.abs(ceil.sum - nbs);
					if (diff < v) {
						v = diff;
						k = 2;
						ps.clear();
						ps.add(new Pair(ceil.a, i));
						ps.add(new Pair(ceil.b, j));
					}
				}
				
				if (hi < sums.length) {
					State floor = sums[hi];
					long diff = Math.abs(floor.sum - nbs);
					if (diff < v) {
						v = diff;
						k = 2;
						ps.clear();
						ps.add(new Pair(floor.a, i));
						ps.add(new Pair(floor.b, j));
					}
				}
			}
		}
		out.println(v);
		out.println(k);
		for (Pair p : ps) 
			out.println((p.x+1) + " " + (p.y+1));
		out.close();
	}

	public void run() {
		if (__FILE_DEBUG_FLAG__ == __t__) {
			try {
				is = new FileInputStream(__DEBUG_FILE_NAME__);
			} catch (FileNotFoundException e) {
				// TODO 自動生成された catch ブロック
				e.printStackTrace();
			}
			System.out.println("FILE_INPUT!");
		} else {
			is = System.in;
		}
		in = new FastScanner(is);
		out = new PrintWriter(System.out);

		solve();
	}

	public static void main(String[] args) {
		new D().run();
	}

	public void mapDebug(int[][] a) {
		System.out.println("--------map display---------");

		for (int i = 0; i < a.length; i++) {
			for (int j = 0; j < a[i].length; j++) {
				System.out.printf("%3d ", a[i][j]);
			}
			System.out.println();
		}

		System.out.println("----------------------------");
		System.out.println();
	}

	public void debug(Object... obj) {
		System.out.println(Arrays.deepToString(obj));
	}

	class FastScanner {
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

		public FastScanner(InputStream stream) {
			this.stream = stream;
			//stream = new FileInputStream(new File("dec.in"));

		}

		int read() {
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		boolean isEndline(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		int[] nextIntArray(int n) {
			int[] array = new int[n];
			for (int i = 0; i < n; i++)
				array[i] = nextInt();

			return array;
		}

		int[][] nextIntMap(int n, int m) {
			int[][] map = new int[n][m];
			for (int i = 0; i < n; i++) {
				map[i] = in.nextIntArray(m);
			}
			return map;
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		long[] nextLongArray(int n) {
			long[] array = new long[n];
			for (int i = 0; i < n; i++)
				array[i] = nextLong();

			return array;
		}

		long[][] nextLongMap(int n, int m) {
			long[][] map = new long[n][m];
			for (int i = 0; i < n; i++) {
				map[i] = in.nextLongArray(m);
			}
			return map;
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		double[] nextDoubleArray(int n) {
			double[] array = new double[n];
			for (int i = 0; i < n; i++)
				array[i] = nextDouble();

			return array;
		}

		double[][] nextDoubleMap(int n, int m) {
			double[][] map = new double[n][m];
			for (int i = 0; i < n; i++) {
				map[i] = in.nextDoubleArray(m);
			}
			return map;
		}

		String next() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		String[] nextStringArray(int n) {
			String[] array = new String[n];
			for (int i = 0; i < n; i++)
				array[i] = next();

			return array;
		}

		String nextLine() {
			int c = read();
			while (isEndline(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndline(c));
			return res.toString();
		}
	}
}