分数: 333 分
问题陈述
高桥正在进行滚球实验 M 方块排成一排。
方块的编号为 1 to M,其中正方形 1 位于最高位置并呈正方形 M 位于最低位置。每对相邻的方格之间有一个台阶,方格之间的台阶 i (1 \leq i \leq M - 1)和正方形 i + 1 有体重阈值 W_i 确定球是否可以通过。一个至少有重量的球 W_i 可以将此步骤滚动到正方形 i+1,但是重量小于的球 W_i 无法通过此步骤并停在那里。
Takahashi 使用以下方法进行实验 N 球。球 j (1 \leq j \leq N) 有重量 B_j。对于每个球,独立于其他球进行以下实验。
当高桥放球时 j 在广场上 1,球按照以下规则滚动:
- 让 p 是球的当前方格。最初, p = 1.
- If p < M 和 B_j \geq W_p,球滚到正方形 p + 1 (更新 p to p + 1)。只要满足条件,就重复此步骤。
- If p = M or B_j < W_p,球停在方格处 p.
对于每个球,确定它最终停止的方格的编号。
约束
- 1 \leq N \leq 2 \times 10^5
- 2 \leq M \leq 2 \times 10^5
- 1 \leq W_i \leq 10^9 (1 \leq i \leq M - 1)
- 1 \leq B_j \leq 10^9 (1 \leq j \leq N)
- 所有输入值均为整数
输入
N M
W_1 W_2 \ldots W_{M-1}
B_1 B_2 \ldots B_N
- 第一行包含一个整数 N 代表球的数量和一个整数 M 代表方格数量,以空格分隔。
- 第二行包含 M - 1 整数 W_1, W_2, \ldots, W_{M-1} 代表每一步的权重阈值,以空格分隔。
- 第三行包含 N 整数 B_1, B_2, \ldots, B_N 代表每个球的重量,以空格分隔。
输出
打印 N 行。的 j- 第行 (1 \leq j \leq N) 应包含球所在方格的编号 j 终于停了下来。
示例输入 1
3 5 2 5 3 1 4 1 10
示例输出 1
2 1 5
示例输入 2
5 6 3 3 3 3 3 1 2 3 4 5
示例输出 2
1 1 6 6 6
示例输入 3
7 10 5 12 8 20 3 15 6 10 25 10 20 5 30 1 8 100
示例输出 3
2 9 2 10 1 2 10