#CS1143. 酒店查询

酒店查询

题目背景

翻译自 CSES-1143 题。

题目描述

街上有 n 家酒店。每家酒店有一定数量的空闲房间。你的任务是为一组组游客分配酒店房间。每个小组的所有成员都希望住在同一家酒店。

这些小组会一个接一个地到达，对于每个小组，系统已经知道它们需要的房间数量。你总是将一个小组分配给第一个拥有足够房间的酒店。分配之后，该酒店的空闲房间数量减少。

输入格式

第一行包含两个整数 n 和 m：分别表示酒店的数量和小组的数量。酒店编号为 1,2,...,n1,2,...,n1,2,...,n。

第二行包含 n 个整数 h1,h2,…,hnh_1,h_2,…,h_nh1​,h2​,…,hn​：表示每家酒店的空闲房间数量。

第三行包含 m 个整数 r1,r2,…,rmr_1,r_2,…,r_mr1​,r2​,…,rm​：表示每个小组需要的房间数量。

输出格式

对于每个小组，输出分配的酒店编号。如果某个小组无法被分配酒店，则输出 0。

样例

8 5
3 2 4 1 5 5 2 6
4 4 7 1 1

3 5 0 1 1

说明/提示

$1 \leq n,m \leq 2 \cdot 10^5$

1≤hi≤1091 \leq h_i \leq 10^91≤hi​≤109；

1≤ri≤1091 \leq r_i \leq 10^91≤ri​≤109。