链接: https://cses.fi/problemset/task/1091

板块: Sorting and Searching

时限: 1.00 s ｜ 内存: 512 MB

题目描述

有 $n$ 张演唱会门票待售，每张票有一个价格。随后有 $m$ 位顾客依次到来。

每位顾客会说出他们愿意支付的最高票价，之后他们会得到一张价格尽可能接近、且不超过该最高价的门票。

输入

第一行包含整数 $n$ 和 $m$：门票数量和顾客数量。

下一行包含 $n$ 个整数 $h_1,h_2,\ldots,h_n$：每张票的价格。

最后一行包含 $m$ 个整数 $t_1,t_2,\ldots,t_m$：每位顾客按到达顺序给出的最高出价。

输出

对每位顾客，输出他们将为门票支付的价格。此后该票不能再被购买。

如果某顾客无法买到任何门票，输出 $-1$。

数据范围

$1 \le n, m \le 2 \cdot 10^5$ $1 \le h_i, t_i \le 10^9$

样例输入

5 3
5 3 7 8 5
4 8 3

样例输出

3
8
-1