开始: 2026-10-05 11:05:00

【集训03】CSP-J模拟赛1005

结束: 2026-10-06 00:00:00
当前  2026-11-04 12:29:49  类型: IOI  状态: 已经结束 

P1. 回转寿司(sushi)
描述

某家回转寿司店来了 N 位客人,编号 1\sim N。第 i 位客人的**美食度**为 A_i。

接着传送带上会依次流过 M 贯寿司,第 j 贯寿司的**美味度**为 B_j。

每一贯寿司都会**依次**经过 1,2,\dots,N 号客人的面前。

- 每位客人看到流到自己面前的寿司时,若**美味度不小于自己的美食度**(即 B \ge A_i),就会取下这贯寿司吃掉;否则什么也不做。

- 客人 i 取走的寿司,此后再也不会经过客人 j\ (j>i) 的面前。

请对 M 贯寿司中的每一贯,输出是谁吃掉了它;若没有人吃,输出 `-1`。


输入

第一行两个整数 N,M(1 \leq N,M \leq 2\times 10^5),分别表示客人数与寿司贯数。

第二行 N 个整数 A_1,A_2,\dots,A_N(1 \leq A_i \leq 2\times 10^5)。

第三行 M 个整数 B_1,B_2,\dots,B_M(1 \leq B_j \leq 2\times 10^5)。


输出

输出 M 行,第 j 行为吃掉第 j 贯寿司的客人编号,或 `-1`。

样例

输入

3 3
3 8 2
5 2 1

输出

1
3
-1

输入

3 3
1 1 1
1 1 1

输出

1
1
1

输入

10 5
60 83 76 45 70 91 37 58 94 22
70 39 52 33 18

输出

1
7
4
10
-1
提示

**样例1说明**:

- 第 1 贯 B_1=5\ge A_1=3,被 1 号客人吃掉,不再流向后面的人;

- 第 2 贯 B_2=2:2(1 号不动)、2(2 号不动)、2\ge A_3=2(3 号吃掉);

- 第 3 贯 B_3=1:三人的美食度都比它大,无人食用。

数据范围:

- 1\le N,M\le 2\times 10^5;

- 1\le A_i,B_j\le 2\times 10^5;

| 20% | 1~5 | 20 | N,M \le 30 | 

| 60% | 6~15 | 40 | N,M \le 5000 | 

| 100% | 16~25 | 40 | N,M \le 2\times 10^5 | 

提交

题目参数
时间限制 1 秒
内存限制 128 MB
提交