Truck Transportation Challenge

You are given n cities arranged in a line numbered from 1 to n. For every city i with i > 1, there is a bidirectional road connecting city i-1 and city i. Each city i has a truck height limit \(h_i\) (all \(h_i\) are distinct), meaning that only trucks with height \(\le h_i\) can pass through city i.

There are m transport tasks. For each task \(i\) (\(1 \le i \le m\)), a truck numbered \(i\) with height exactly \(h_{S_i}\) starts at city \(S_i\) (all \(S_i\) are distinct) and must reach an airport. There are exactly m airports located at cities \(T_1, T_2, \dots, T_m\) (all \(T_i\) are distinct); note that an airport city can be passed by any number of trucks, but in a valid assignment, each airport must have exactly one truck arrive at it. (A truck is said to have reached an airport if it can legally travel to that city according to the height restrictions.)

For each truck (task) \(i\), let its starting city be \(S_i\) and its truck height be \(h_{S_i}\). Since a truck can only pass through cities that satisfy the height constraint, it can only travel from its starting city \(S_i\) to a city \(x\) if and only if every city along the unique path between \(S_i\) and \(x\) (inclusive) has a height limit \(\ge h_{S_i}\). It is not hard to see that if you precompute for every city the nearest city to the left and right having a height limit smaller than \(h_i\), then the reachable interval for a truck starting at city \(S_i\) is exactly \([L_i+1, R_i-1]\) (in cities index) where \(L_i\) is the index of the nearest city to the left of \(S_i\) with \(h < h_{S_i}\) (or 0 if none exists) and \(R_i\) is the index of the nearest city to the right of \(S_i\) with \(h < h_{S_i}\) (or \(n+1\) if none exists).

Define an array \(F = [c_1, c_2, \dots, c_m]\), where \(c_j\) is the number of the truck that arrives at the airport located at city \(T_j\). Your task is to choose a valid pairing of trucks to airports (i.e. a permutation of the tasks) so that every truck reaches an airport (and each airport is the destination of exactly one truck) and the array \(F\) is lexicographically minimum.

We define the lexicographical order as follows: for two arrays \(A\) and \(B\) of length \(L\), \(A\) is lexicographically smaller than \(B\) if there exists an index \(0 \le i < L\) such that \(A_1 = B_1, A_2 = B_2, \dots, A_i = B_i\) and \(A_{i+1} < B_{i+1}\).

It is guaranteed that a solution exists.

inputFormat

The first line contains two integers n and m (n &ge m).

The second line contains n distinct integers \(h_1, h_2, \dots, h_n\), where \(h_i\) is the height limit of city i.

The third line contains m distinct integers \(S_1, S_2, \dots, S_m\) representing the starting cities of the trucks.

The fourth line contains m distinct integers \(T_1, T_2, \dots, T_m\) representing the cities with airports.

Note that it is possible that for some indices, \(S_i = T_j\) for some \(i, j\>.

outputFormat

Output m integers \(F_1, F_2, \dots, F_m\) separated by spaces, where \(F_j\) is the truck number that arrives at the airport at city \(T_j\). The array \(F\) must be lexicographically minimum among all valid assignments.

sample

5 2
1 2 3 4 5
2 4
2 4

1 2