Educational Codeforces Round 6 |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

binary search

two pointers

*2200

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Professor GukiZ and Two Arrays

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputProfessor GukiZ has two arrays of integers, a and b. Professor wants to make the sum of the elements in the array a *s*_{a} as close as possible to the sum of the elements in the array b *s*_{b}. So he wants to minimize the value *v* = |*s*_{a} - *s*_{b}|.

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 *a*_{i} ( - 10^{9} ≤ *a*_{i} ≤ 10^{9}) — 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 *b*_{j} ( - 10^{9} ≤ *b*_{j} ≤ 10^{9}) — the elements of the array b.

Output

In the first line print the minimal value *v* = |*s*_{a} - *s*_{b}| 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 *x*_{p}, *y*_{p} (1 ≤ *x*_{p} ≤ *n*, 1 ≤ *y*_{p} ≤ *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

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/08/2024 17:31:32 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|