Little E was playing the Somzig game and couldn't handle it because there wasn't enough time for operations, which led to this problem.

Little E has $n$ types of balls, where there are $a_i$ balls of the $i$-th type. There are two types of tools: the first type can turn a ball of a specified color into a ball of any color; the second type can turn a ball of a specified color into two balls of that same color. A ball that has already been transformed can also be transformed again using tools. There are $b_i$ tools of the first type for the $i$-th color and $c_i$ tools of the second type for the $i$-th color. Little E wants to know, assuming each tool can be used at most once, what is the maximum number of balls of the $i$-th color he can have for each $i$, and what is the maximum total number of balls he can have in the end.

Input

The input is read from standard input.

The first line contains a positive integer $n$.

The second line contains $n$ integers, where the $i$-th integer represents $a_i$.

The third line contains $n$ integers, where the $i$-th integer represents $b_i$.

The fourth line contains $n$ integers, where the $i$-th integer represents $c_i$.

Output

The output is written to standard output.

The first line contains $n$ integers, where the $i$-th integer represents the maximum number of balls of the $i$-th color Little E can have, assuming each tool is used at most once.

The second line contains an integer representing the maximum total number of balls Little E can have, assuming each tool is used at most once.

Examples

Input 1

2
1 2
1 2
1 0

Output 1

4 3
4

Subtasks

It is guaranteed that $1\le n \le 351493$.

It is guaranteed that $0\le a_i,b_i,c_i\le 10^9$.