Background

At the end of a盛夏, even at night, the heat persists.
Another reunion and separation begins with sadness.
Is it the shyness under the fan, or the destruction by rain?
Everywhere is worth lingering over.

——Yin Lin, "Glowworm"

Problem Description

As night falls, fireflies, called by the night, begin to venture out on a straight path through the woods.

Consider the path as a number line. Initially, there are $n$ fireflies at some integer points on the number line, numbered from $1$ to $n$ from left to right, with the initial coordinate of the $i$-th firefly being $x_i$. Each firefly has a distinct brightness value, with the $i$-th firefly's brightness being $a_i$.

At any moment, for any surviving firefly $i$, it flies according to the following rules:

• Among the currently surviving fireflies, find the one(s) adjacent to $i$ (which could be one or two) with the highest brightness, denoted by $j$. If $a_i < a_j$, then $i$ flies towards $j$; otherwise, $i$ stays in place.
• Two fireflies are considered 'adjacent' if there is no other surviving firefly between them.
• The speed of all fireflies is one unit length per second.

Fireflies have a short lifespan. When two fireflies meet (i.e., their coordinates coincide), the one with the lower brightness will exhaust its life and disappear from the path. Clearly, only one firefly will remain in the end. For each of the other fireflies, determine the coordinate at which they exhaust their life.

Input Format

The first line contains an integer $n$, the number of fireflies.
The second line contains $n$ integers, the $i$-th of which is the initial coordinate $x_i$ of the $i$-th firefly. It is guaranteed that $x_i$ is monotonically increasing.
The third line contains $n$ integers, the $i$-th of which is the brightness value $a_i$ of the $i$-th firefly. It is guaranteed that the brightness values are distinct.

Output Format

Output one line with $n$ integers separated by single spaces. The $i$-th integer represents the coordinate at which the $i$-th firefly exhausts its life. If the $i$-th firefly survives, output 0 for that position.

Sample Input and Output

Sample Input #1

4
1 2 3 4
2 3 1 4

Sample Output #1

2 4 4 0

Sample Input #2

5
1 2 3 4 5
5 3 2 1 4

Sample Output #2

0 1 1 5 1

Sample Input #3

5
2 4 6 10 12
5 3 1 4 2

Sample Output #3

0 2 2 2 10

Sample Input #4

7
2 4 6 8 12 14 16
5 3 2 6 1 4 7

Sample Output #4

8 2 8 16 16 16 0

Sample Input #5

7
2 4 6 8 12 14 16
7 1 6 3 5 4 2

Sample Output #5

0 2 2 6 2 12 2

Notes

Sample 1 Explanation

• In the first second, firefly #1 moves right, firefly #2 stays, firefly #3 moves right, and firefly #4 stays.
• At the start of the second second, firefly #1 meets firefly #2 and exhausts its life at coordinate 2; firefly #3 meets firefly #4 and exhausts its life at coordinate 4.
• Subsequently, firefly #2 moves right until it meets firefly #4 at coordinate 4, exhausting its life.

Data Constraints

• For $5\%$ of the data, $n = 2$.
• For $30\%$ of the data, $n \leq 100$, $x_i \leq 200$.
• For $60\%$ of the data, $n \leq 10^3$.
• For an additional $5\%$ of the data, special condition A holds.
• For another additional $5\%$ of the data, special condition B holds.
• For $100\%$ of the data, $2 \leq n \leq 5 \times 10^5$, $1 \leq x_i \leq 10^9$, $1 \leq a_i \leq n$. Additionally, $x_i < x_{i + 1}$ and $a_i$ is a permutation of length $n$.

Special Conditions:

• Special Condition A: The sequence $a$ is monotonically increasing.
• Special Condition B: The sequence $a$ is unimodal with a single maximum. That is, there exists a $p$ such that $1 \leq p < n$ and $a_1 \sim a_p$ is monotonically increasing, and $a_p \sim a_n$ is monotonically decreasing.

Hints

• Be mindful of the impact of input/output operations on program efficiency, and choose appropriate methods to avoid timeouts.
• Consider the constant factors in time complexity that may affect program performance.

Notes

This problem includes 7 additional sample files, available in the attached glowworm.zip file.

见题面 Input 部分

见题面 Output 部分