After his leave from DMOJ, Wesley is very angry and demands you to construct an array ~x~ of length ~N~ consisting of positive integers such that each element ~x_i~ satisfies the following requirements:

• There are ~a_i~ elements before index ~i~ that are strictly smaller than ~x_i~
• There are ~b_i~ elements after index ~i~ that are strictly smaller than ~x_i~
• There are ~c_i~ elements before index ~i~ that are strictly greater than ~x_i~
• There are ~d_i~ elements after index ~i~ that are strictly greater than ~x_i~

Luckily, Wesley is a kind person and will allow for your array to violate at most ~1~ of the requirements above. In particular, you can pick an index ~i~ and modify exactly one of ~a_i~, ~b_i~, ~c_i~ and ~d_i~. In exchange however, he requests that your array is the lexicographically least one (it must be the lexicographically least array that violates at most ~1~ requirement).

Note: We say that array ~x~ is lexicographically less than array ~y~ if ~x \ne y~ and at the smallest index ~i~ where ~x_i~ and ~y_i~ differ, ~x_i < y_i~.

Constraints

~2 \le N \le 2 \times 10^5~

~0 \le a_i,b_i,c_i,d_i~

~a_i+c_i < i~

~b_i+d_i \le N-i~

Subtask 1 [12%]

~N \le 7~

Subtask 2 [23%]

~b_i, c_i = 0~

Subtask 3 [43%]

~N \le 5 \times 10^3~

Subtask 4 [22%]

No additional constraints.

Input Specification

The first line contains a single integer ~N~.

The next line contains ~N~ integers ~a_1, \ldots, a_N~.

The next line contains ~N~ integers ~b_1, \ldots, b_N~.

The next line contains ~N~ integers ~c_1, \ldots, c_N~.

The next line contains ~N~ integers ~d_1, \ldots, d_N~.

Output Specification

If no such array exists, output -1.

Otherwise, output the elements of the lexicographically least array on a single line.

Sample Input

5
0 0 2 2 1
1 0 2 1 0
0 1 0 1 2
2 1 0 0 0

Sample Output

2 1 4 3 2

Explanation for Sample

The array above satisfies all the requirements except for ~d_2~. It can be shown that this is the lexicographically least array that violates at most one requirement.