You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

在一款游戏中，在你的面前有 $n$ 只怪物依次排成一排，他们的血量分别是 $a_1,a_2,\ldots , a_n$ 你的初始攻击力为 $1$ , 在每轮游戏中，你有$m$次操作，对于每次操作你有三种出牌方式：

• $1$:用当前攻击力对前方怪物造成伤害，攻击后攻击力重置为$1$。若前方怪物血量降至$0$或更低，则该怪物被击败，后续攻击将针对下一只存活的前方怪物。
• $2$:提高一点攻击力。
• $3$:过牌

请输出每只怪物被击败时所执行的操作序号（从 $1$ 到 ​$m$ 依次编号）。

输入格式

第一行两个整数 $n，m$ , 代表怪物的数量和操作的次数。 接下来一行输入 $n$ 个整数 $a_1,a_2,\ldots , a_n$，代表每只怪物的初始血量，以空格分隔。 接下来一行输入一个长度为 $m$ 的只含有 $1,2,3$ 的字符串，代表你的操作序列。 数据保证，所有怪物最终都会被击败。

输出格式

一行 $n$ 个整数，依次表示每只怪物被击败时的操作序号。

样例

输入

2 6
3 3
221211

输出

3 6

样例解释

• 操作 $1$（类型 $2$）：攻击力从 $1→2$,当前攻击力 $2$​
• 操作 $2$（类型 $2$）：攻击力从 $2→3$,当前攻击力 $3$​
• 操作 $3$（类型 $1$）：攻击前方怪物,伤害：$3→3-3=0$（击败），攻击力重置 $1$ 记录第一只怪物死亡时间：$3$ 剩余怪物：$[3]$
• 操作 $4$（类型 $2$）：攻击力从 $1→2$,当前攻击力 $2$
• 操作 $5$（类型 $1$）：攻击前方怪物：$3-2=1$，攻击力重置 $1$ 怪物仍未被击败
• 操作 $6$（类型 $1$）：攻击前方怪物：$1-1=0$，击败怪物，记录时间 $6$ 故输出 $3,6$

数据分布

$40\%$的样例， $1\le n \le 100$ , $1 \le m \le 100$ $1 \le a_i \le 100 ( 1 \le i \le n)$

$100\%$的样例， $1\le n \le 10^6$ , $1 \le m \le 10^6$ $1 \le a_i \le 10^6 ( 1 \le i \le n)$, 数据保证，所有怪物最终都会被击败。

时空限制

• 时间限制：$1s$
• 空间限制：$256M$