Once upon a time, there was a secret group of boys. People used to call them 'Dushtu Cheler Dol' (Gang of Naughty boys) or DCD in short. Members of DCD were very good at making fool of people.

Suppose, you are a member of DCD and you want to borrow money from N people (you are definitely not going to return the money because that will go against the values of DCD). Some of  the N people will not lend you money as they know about DCD. But at first you don't know how many of them know about it. Then there are M members of DCD who want to borrow money from you. As you know none of the M people will return your money, you will try to escape from them when they will ask you for money, but you are not sure of being able to escape. Failure of escaping means, you must give them the money they want. So, before starting you wanted to determined how much money you will have after the whole process. As many solutions are possible, you will determine an interval, which contains the maximum number of possible solutions. The difference between the starting point and ending point will be of definite size (given in the input).

Input

Test cases start with two integers N and M. Next, there will be N integers in the same or different lines where [0 <= N_i <= 10¹⁵] is the amount of money you will borrow from the i^th person. Then there will be M integers in the same or different lines, where [0 <= M_i <= 10¹⁵] is the amount of money i^th DCD member will ask for. (N + M) <= 17. Then you will be given an integer D [1 <= D <= 10¹⁵], the difference between the starting point and ending point of the desired interval.

There will be at most 200 test cases.

Output

For each test case, you have to print three integers S, T and E. S and T are the endpoints of an interval of difference D, (S <= T). E is the number of solutions between S and T (inclusive).

If there are several solutions, print the interval where S itself is a possible solution. If still there are several solutions, print the interval having minimum value of S.

Note:

1. Same money values achieved by different ways are considered different.
2. If you can't escape, you will have to pay money even if you have zero or less money left. Then your amount will be considered negative.
3. If the starting value of the interval is X, the ending value will be X + D - 1.

Example

Input:
2 0
1 2
1
4 1
5 6 9 9
2
5

Output:
0 0 1
11 15 9