题目描述

英国特许登山者协会最近的日子不太好过。

这项步行运动的发展几乎陷入停滞。年轻人不再选择登山，而是转向斯诺克、抢椅子和程序设计竞赛等更加温暖的室内活动。

为了吸引更多会员，协会准备在明年举办一系列新的定向越野计时赛。第一场比赛的路线是一条穿越凯恩戈姆山脉的短程路线。所有选手沿着由若干标记点指定的同一条路线前进，但出发时间各不相同。

由于徒步可能有危险，而且许多参赛者经验不足，竞赛委员会制定了两条规则：

• 在任何时刻，相邻两名选手之间的距离都不能超过规定的最大距离 $B$；
• 每名选手都需要一定的个人空间。若第 $i$ 名选手需要 $A_i$ 米的个人空间，则任何其他选手与他的距离都不能小于 $A_i$。不同选手所需的个人空间可能不同。

定向越野最困难的部分是寻找路线。一旦一名选手知道下一个目的地，他几乎可以立即到达；在本题中，选手从一个标记点移动到下一个标记点被视为瞬间完成。

比赛已经开始，但大家无法判断下一步应该让谁移动，才能始终满足最小距离与最大距离限制。

请给出一份移动顺序，使所有选手最终都到达路线终点。

输入格式

第一行包含一个整数 $B$（$1\le B\le 50000$），表示相邻选手之间允许的最大距离。

第二行包含一个整数 $P$（$3\le P\le 1000$），表示路线上的标记点数量。

第三行包含 $P$ 个互不相同的整数 $d_1,d_2,\ldots,d_P$（$0\le d_i\le 10^6$），其中 $d_i$ 表示第 $i$ 个标记点到起点的距离，并且 $d_1=0$。标记点按路线上的先后顺序给出。

第四行包含一个整数 $K$（$2\le K\le 1000$），表示选手数量。

接下来 $K$ 行，第 $i$ 行包含两个整数 $A_i,V_i$（$1\le A_i\le 10^6$，$1\le V_i\le P$）：

• $A_i$ 表示第 $i$ 名选手所需的最小个人空间；
• $V_i$ 表示第 $i$ 名选手当前所在的标记点编号。

初始状态保证满足所有最小距离和最大距离限制。选手按照其到起点距离递增的顺序编号。

输出格式

若无法在始终满足所有距离限制的前提下让所有选手到达终点，输出：

impossible

否则，在一行中输出一个以空格分隔的选手编号序列。序列中的每个编号表示下一次应让哪名选手从当前标记点移动到下一个标记点。

移动序列不能使任何选手越过路线终点。

一名选手到达终点后，便不再参与任何最小距离或最大距离限制的判断。

由于合法移动序列可能不唯一，本题需要 Special Judge。

样例 1

输入

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

输出

1 2 1 2 1 2 1 2 1 1 1

样例 2

输入

10
10
0 1 3 6 10 14 17 19 20 21
3
3 1
1 3
3 5

输出

2 1 1 3 2 1 3 2 1 3 3 2 1 3 2 2 1 2 1 1 1

样例 3

输入

5
5
0 2 5 9 14
2
2 1
2 2

输出

impossible