P10919 Transport Planning

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

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$.

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 one line with $m$ integers representing $F$.

**This problem uses bundled tests.** | Subtask ID | Special Property | Score | | :-----------: | :-----------: | :-----------: | | $1$ | $n, m \leq 50$ | $10$ | | $2$ | For any $1 < i \leq n$, $h_i < h_{i-1}$ | $25$ | | $3$ | $n, m \leq 10^3$ | $25$ | | $4$ | No special property | $40$ | 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