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 CPP):

Solution:
#include <bits/stdc++.h>
int n, m;
long long a[2001] = {
    0,
};
long long a_idx[2001] = {
    0,
};
long long a_idx_dummy[2001] = {
    0,
};
long long b[2001] = {
    0,
};
long long b_idx[2001] = {
    0,
};
long long pair_a[2000000] = {
    0,
};
long long pair_a_idx_x[2000000] = {
    0,
};
long long pair_a_idx_y[2000000] = {
    0,
};
int a_length = 0;
long long pair_b[2000000] = {
    0,
};
long long pair_b_idx_x[2000000] = {
    0,
};
long long pair_b_idx_y[2000000] = {
    0,
};
int b_length = 0;
long long sa = 0;
long long sb = 0;
long long prev_sa = 0;
long long prev_sb = 0;
long long prev_sub = 0;
long long cur_sa = 0;
long long cur_sb = 0;
int idx_a = 0;
int idx_b = 0;
int num_of_swap = 0;
void Swap(long long* A, long long* B) {
  long long Temp = *A;
  *A = *B;
  *B = Temp;
}
int Partition(long long Dataset[], long long data_idx_x[],
              long long data_idx_y[], int Left, int Right) {
  int First = Left;
  long long Pivot = Dataset[First];
  ++Left;
  while (Left <= Right) {
    while (Dataset[Left] <= Pivot && Left < Right) {
      ++Left;
    }
    while (Dataset[Right] > Pivot && Left <= Right) {
      --Right;
    }
    if (Left < Right) {
      Swap(&Dataset[Left], &Dataset[Right]);
      Swap(&data_idx_x[Left], &data_idx_x[Right]);
      Swap(&data_idx_y[Left], &data_idx_y[Right]);
    } else {
      break;
    }
  }
  Swap(&Dataset[First], &Dataset[Right]);
  Swap(&data_idx_x[First], &data_idx_x[Right]);
  Swap(&data_idx_y[First], &data_idx_y[Right]);
  return Right;
}
void QuickSort_Loop(long long Dataset[], long long data_idx_x[],
                    long long data_idx_y[], int Left, int Right) {
  int stack[100000][2] = {
      0,
  };
  int top = 0;
  int index;
  stack[top][0] = Left;
  stack[top][1] = Right;
  top++;
  while (top > 0) {
    Left = stack[--top][0];
    Right = stack[top][1];
    if (Left < Right) {
      index = Partition(Dataset, data_idx_x, data_idx_y, Left, Right);
      stack[top][0] = Left;
      stack[top++][1] = index - 1;
      stack[top][0] = index + 1;
      stack[top++][1] = Right;
    }
  }
}
long long get_abs(long long val) {
  if (val < 0) {
    val *= -1;
  }
  return val;
}
void make_pair_array() {
  int i, j;
  for (i = 0; i < n; i++) {
    for (j = i + 1; j < n; j++) {
      pair_a[a_length] = a[i] + a[j];
      pair_a_idx_x[a_length] = i;
      pair_a_idx_y[a_length] = j;
      a_length++;
    }
  }
  for (i = 0; i < m; i++) {
    for (j = i + 1; j < m; j++) {
      pair_b[b_length] = b[i] + b[j];
      pair_b_idx_x[b_length] = i;
      pair_b_idx_y[b_length] = j;
      b_length++;
    }
  }
}
void compare_swap(int num, long long a[], long long b[], int a_length,
                  int b_length) {
  long long diff = 0;
  long long cur_sub = 0;
  int window_a = 0;
  int window_b = 0;
  while (window_a < a_length && window_b < b_length) {
    diff = a[window_a] - b[window_b];
    cur_sa = sa - diff;
    cur_sb = sb + diff;
    cur_sub = get_abs(cur_sa - cur_sb);
    if (prev_sub > cur_sub) {
      prev_sub = cur_sub;
      idx_a = window_a;
      idx_b = window_b;
      num_of_swap = num;
    }
    if (cur_sa > cur_sb) {
      window_a += 1;
    } else if (cur_sa < cur_sb) {
      window_b += 1;
    } else {
      break;
    }
  }
}
int main(void) {
  int i;
  scanf("%d", &n);
  for (i = 0; i < n; i++) {
    scanf("%lld", &a[i]);
    a_idx[i] = i;
    sa += a[i];
  }
  scanf("%d", &m);
  for (i = 0; i < m; i++) {
    scanf("%lld", &b[i]);
    b_idx[i] = i;
    sb += b[i];
  }
  make_pair_array();
  QuickSort_Loop(a, a_idx, a_idx_dummy, 0, n - 1);
  QuickSort_Loop(b, b_idx, a_idx_dummy, 0, m - 1);
  QuickSort_Loop(pair_a, pair_a_idx_x, pair_a_idx_y, 0, a_length - 1);
  QuickSort_Loop(pair_b, pair_b_idx_x, pair_b_idx_y, 0, b_length - 1);
  prev_sa = sa;
  prev_sb = sb;
  prev_sub = get_abs(prev_sa - prev_sb);
  compare_swap(1, a, b, n, m);
  if (prev_sub != 0) {
    compare_swap(2, pair_a, pair_b, a_length, b_length);
  }
  printf("%lld\n", prev_sub);
  printf("%d\n", num_of_swap);
  if (num_of_swap == 1) {
    printf("%lld %lld\n", a_idx[idx_a] + 1, b_idx[idx_b] + 1);
  } else if (num_of_swap == 2) {
    printf("%lld %lld\n", pair_a_idx_x[idx_a] + 1, pair_b_idx_x[idx_b] + 1);
    printf("%lld %lld", pair_a_idx_y[idx_a] + 1, pair_b_idx_y[idx_b] + 1);
  }
  return 0;
}