Background

You need to plan truck transportation routes. To help you solve the problem better, please read the statement carefully.

Problem Description

There are $n$ cities. For any $1 < i \leq n$, there is a bidirectional road between city $i$ and city $i-1$. Each city has a truck height limit $h_i$, meaning only trucks with height less than or equal to $h_i$ can pass through this city. Now there are $m$ cities $S_{1}, S_{2}, ..., S_{m}$, each having exactly one transportation task. The task requires the truck with index $i$ and height $h_{S_{i}}$ to depart from city $S_{i}$ and arrive at any city that has an airport. There are $m$ cities with airports, which are $T_{1}, T_{2}, ..., T_{m}$. For a valid transportation plan, it must be guaranteed that each truck arrives at an airport and each airport has exactly one truck arriving. An airport can be passed through by multiple trucks at the same time. Note that if you cannot pass through a city, then you also cannot arrive at that city.

Let $c_i$ denote the truck index that arrives at the airport located in city $T_i$. Let the array $F = \{c_1, c_2, ..., c_m\}$. Please minimize the lexicographic order of $F$ and output $F$.

We define two arrays $A, B$ of length $len$. $A$ is lexicographically smaller than $B$ if and only if there exists $0 \leq i < len$ such that for all $1 \leq j \leq i$, $A_j = B_j$, and $A_{i+1} < B_{i+1}$.

The testdata guarantees that a solution exists. It also guarantees that all $h_i$ are pairwise distinct, all $T_i$ are pairwise distinct, and all $S_i$ are pairwise distinct. However, it may happen that there exist $i, j$ such that $S_i = T_j$.

Input Format

The first line contains two integers $n, m$.

The next line contains $n$ integers $h_1, h_2, ..., h_n$.

The next line contains $m$ integers $S_{1}, S_{2}, ..., S_{m}$.

The next line contains $m$ integers $T_{1}, T_{2}, ..., T_{m}$.

Output Format

Output one line with $m$ integers representing $F$.

10 3 
1 2 3 5 4 10 8 6 7 9
1 2 8
6 10 3

1 3 2

20 5
12 13 14 15 16 17 18 19 20 22 21 30 29 28 27 26 23 24 25 1
1 20 2 5 3 
10 12 11 9 13 

1 2 3 4 5

Hint

This problem uses bundled tests.

For $100\%$ of the testdata, it is guaranteed that $1 \leq m \leq n \leq 2 \times 10^5$ and $0 < h_i \leq 10^9$.

Translated by ChatGPT 5