A student who won a programming competition received internship offers from two universities. While preparing their study plans, they learned the teaching quality rating for each subject at these universities.

The study program at the first university consists of a sequence of $n$ distinct subjects $a_1, a_2, \dots, a_n$ listed in chronological order, with ratings $x_1, x_2, \dots, x_n$ respectively. The study program at the second university consists of a sequence of $m$ distinct subjects $b_1, b_2, \dots, b_m$ listed in chronological order, with ratings $y_1, y_2, \dots, y_m$ respectively.

The student has the option to create a study plan at the first university to study subjects at positions from $l_a$ to $r_a$ inclusive ($1 \le l_a \le r_a \le n$), or to decline the internship at the first university. Similarly, they can create a study plan at the second university to study subjects at positions from $l_b$ to $r_b$ inclusive ($1 \le l_b \le r_b \le m$), or to decline the internship at the second university.

It makes no sense to study the same subject twice at different universities, so all subjects in the two chosen study plans must be distinct.

You are required to write a program that determines the student's study plans in such a way as to obtain the highest possible sum of ratings for the subjects studied.

Input

The first line of input contains two integers $n$ and $m$ — the number of subjects in the study programs of the first and second universities, respectively ($1 \le n, m \le 500\,000$).

The second line of input contains $n$ integers $a_i$ — the subjects included in the first university's program, listed in chronological order ($1 \le a_i \le n + m$).

The third line of input contains $n$ integers $x_i$ — the ratings of the subjects included in the first university's program, listed in the same order as the subjects $a_i$ ($1 \le x_i \le 10^9$).

The fourth line of input contains $m$ integers $b_i$ — the subjects included in the second university's program, listed in chronological order ($1 \le b_i \le n + m$).

The fifth line of input contains $m$ integers $y_i$ — the ratings of the subjects included in the second university's program, listed in the same order as the subjects $b_i$ ($1 \le y_i \le 10^9$).

Output

The first line of output must contain an integer $r$ — the highest possible sum of subject ratings.

The second line of output must contain the integers $l_a, r_a$ — the positions in the study program of the first and last subjects included in the study plan at the first university, or "0 0" if the student declined the internship at the first university.

The third line of output must contain the integers $l_b, r_b$ — the positions in the study program of the first and last subjects included in the study plan at the second university, or "0 0" if the student declined the internship at the second university.

If there are multiple possible correct answers, you may output any of them.

Examples

Input 1

7 5
3 1 4 8 6 9 2
2 7 4 10 1 5 3
9 2 11 3 8
3 5 3 4 12

Output 1

39
2 6
2 4

Input 2

2 3
1 2
1 4
2 3 1
17 2 15

Output 2

34
0 0
1 3

Input 3

3 3
4 2 1
10 1 2
5 4 2
1 2 9

Output 3

19
1 1
3 3

Note

In the first example, the provided study plans lead to a total rating of $(7 + 4 + 10 + 1 + 5) + (5 + 3 + 4) = 27 + 12 = 39$. If the student had chosen only the second and third subjects at the first university and the entire course at the second university, the total rating would have been $(7 + 4) + (3 + 5 + 3 + 4 + 12) = 11 + 27 = 38$.

In the second example, the first and third subjects at the second university have such a high rating compared to the corresponding subjects at the first university that the most profitable option is to complete the entire internship at the second university and decline the internship at the first university.