Background

Welcome to DSAI 2201, ^_^

Description

You are given a sorted integer array of length $n$ (non-decreasing), and then $n$ queries. For each query value $q$:

• If $q$ exists in the array, output $q$ itself.
• If $q$ does not exist in the array, output the number in the array that is closest to $q$.
• If two numbers are equally close, output the smaller one.

Format

Input

• The first line contains one integer $n$ ($1 \leq n \leq 10^5$).
• The second line contains $n$ integers $a_1, a_2, \dots, a_n$ (non-decreasing, $-10^9 \leq a_i \leq 10^9$).
• The third line contains $n$ integers $q_1, q_2, \dots, q_n$ (queries, $-10^9 \leq q_i \leq 10^9$).

Output

Output $n$ integers, where the $i$-th integer is the answer to the $i$-th query.

Samples

5
1 4 7 10 15
5 10 2 20 6

4 10 1 15 7

Limitation

1s, 128MiB for each test case.