#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

Lower Bound Queries - Classic Problems | Repovive

CLS46. Lower Bound Queries

2s256 MB

Given a non-decreasing array and $q$ query values, answer each query with the first position whose value is at least the query value.

Constraints

$1 \le n, q \le 2 \cdot 10^5$
$-10^9 \le a_i, x \le 10^9$
$a_1 \le a_2 \le \cdots \le a_n$

Input

\begin{array}{l} n \quad q \\ a_1 \quad a_2 \quad \ldots \quad a_n \\ x_1 \\ x_2 \\ \vdots \\ x_q \end{array}

Output

\begin{array}{l} ans_1 \\ ans_2 \\ \vdots \\ ans_q \end{array}

Samples

Input

Explanation

The answers are positions 1, 2, 4, and -1 for the four query values.

Output

Input

Explanation

The first values not smaller than the queries are at positions 2, 4, and none.

Output

2
4
-1

Input

Explanation

All values are equal, so queries 1, 2, and 3 answer 1, 1, and -1.

Output

1
1
-1

Given a non-decreasing array and $q$ query values, answer each query with the first position whose value is at least the query value.

$1 \le n, q \le 2 \cdot 10^5$
$-10^9 \le a_i, x \le 10^9$
$a_1 \le a_2 \le \cdots \le a_n$

\begin{array}{l} n \quad q \\ a_1 \quad a_2 \quad \ldots \quad a_n \\ x_1 \\ x_2 \\ \vdots \\ x_q \end{array}

\begin{array}{l} ans_1 \\ ans_2 \\ \vdots \\ ans_q \end{array}