波旅甲是一个内向的人。事实上,他非常内向,以至于他独自玩“怪物与魔药”棋盘游戏。游戏的棋盘是一排 $$$n$$$ 单元格。单元格从左到右编号为 $$$1$$$ 到 $$$n$$$。单元格共有三种类型:包含单个怪物的单元格、包含单个药水的单元格或空白单元格(既不包含怪物也不包含药水)。
Polycarp 有 $$$m$$$ 代币,代表与怪物战斗的英雄,这些代币最初位于空白单元格 $$$s_1、s_2、\dots、s_m$$$ 中。波利卡普的任务是选择一个单元格(集结点)并将所有英雄一一移入该单元格。集结点可以是三种类型中任意一种的单元格。
Policarp选择集结点后,他会选择一个英雄并命令他直接移动到该点。一旦该英雄到达该点,波利卡普就会选择另一位英雄并命令他也前往该点。依此类推,直到所有英雄都到达集结点单元格。英雄在走向正题时,不能偏离正路,也不能后退一步。英雄只需朝该点的方向移动一个单元格,直到到达该点。多个英雄可能同时出现在同一个牢房中。
最初,第 $$$i$$$ 个英雄的生命值为 $$$h_i$$$ 生命值 (HP)。怪物也有生命值,不同的怪物可能有不同的生命值。而且药水也有生命值,不同的药水可能有不同的生命值。
如果英雄步入空白单元格(即不包含怪物/药水),英雄的生命值不会改变。
如果英雄走进包含怪物的牢房,那么英雄和怪物就会战斗。如果怪物的生命值严格高于英雄的生命值,则怪物获胜,波利卡普输掉整场比赛。如果英雄的生命值大于或等于怪物的生命值,则英雄获胜,英雄的生命值减去怪物的生命值。 IE。如果他的生命值降至零,英雄就会幸存,但如果他的生命值因战斗而变成负值,英雄就会死亡(波利卡普失败)。如果英雄赢得了与怪物的战斗,那么怪物就会消失,并且单元格会变成空白。
如果英雄走进装有药水的牢房,那么英雄会立即喝下药水。结果,药水的生命值被添加到英雄的生命值上,药水消失,单元格变成空白。
显然,波利卡普想要赢得比赛。这意味着他必须选择这样的集结点和英雄移动的顺序,使每个英雄都到达集结点并生存。 IE。如果英雄到达集结点但同时被怪物杀死,波利卡普就会失败。 Polycarp 可以使用任何 $$$n$$$ 单元格作为集结点 - 最初它可以包含怪物、药水,或者是包含或不包含英雄的空白单元格。
帮助波利卡普编写一个程序来选择集结点和英雄移动的顺序。
输入
输入的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 100$$$; $$$1 \le m \le n$$$) — 游戏板的长度及其上英雄的数量。
以下 $$$m$$$ 行描述了英雄。每行包含两个整数$$$s_i$$$和$$$h_i$$$($$$1 \le s_i \le n$$$; $$$1 \le h_i \le 10^6$$$),其中$$$s_i$$$是初始位置,$$$h_i$$$是第$$$i$$$个英雄的初始HP。保证每个单元格 $$$s_i$$$ 都是空白的。还保证所有 $$$s_i$$$ 都是不同的。
以下行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$-10^6 \le a_j \le 10^6$$$),其中 $$$a_j$$$ 描述游戏板的第 $$$i$$$ 个单元格:
- $$$a_j=0$$$ 表示第 $$$i$$$ 个单元格为空白,
- $$$a_j<0$$$ 表示第 $$$i$$$ 个单元格包含正 HP 为 $$$-a_j$$$ 的怪物,
- $$$a_j>0$$$ 表示第 $$$i$$$ 个单元格包含具有 $$$a_j$$$ HP 的药水。
输出
在输出的第一行打印集结点单元格的索引。
在第二行打印 $$$m$$$ 整数 - 英雄应该移动到集结点的顺序。英雄按照输入中给出的顺序从 $$$1$$$ 到 $$$m$$$ 进行编号。
如果有多个解决方案,请打印其中任何一个。
如果不可能找到所有英雄都可以到达的集结点,请在输出中打印一个整数 -1。
示例
输入 #1
8 3 8 2 1 3 4 9 0 3 -5 0 -5 -4 -1 0
输出 #1
6 3 1 2
输入 #2
1 1 1 1 0
输出 #2
1 1
输入 #3
3 2 1 1 3 1 0 -5000 0
输出 #3
-1
输入#4
8 3 1 15 5 10 8 1 0 -5 -5 -5 0 -5 -5 0
输出#4
7 2 1 3
注意
图片说明了第一个示例: