#13403. 【区间DP练习题】开灯

【区间DP练习题】开灯

题目描述

一排一共NN个灯,第ii个灯在坐标DiD_i处,一开始都是灭的,当你走到这个坐标,可以瞬间按下开关,让它亮起来,但是它TiT_i秒后又会熄灭。

你从一个坐标,走到它相邻的整数坐标,所需的时间都是11秒。

问:是否可以从11号灯出发,点亮所有的灯,如果可以,输出字典序最小的点亮的顺序,如果不行,输出“Mission Impossible”。

备注:这个题实际上有点问题,最小字典序是没法算的,因为有可能最小字典序里面,中间的某些点早早就被点亮了,请按讲的写法写吧,因为我懒得写SPJ了。

输入格式

多组数据(最多1010组),以EOF结束。

每组数据第一行N(1N200)N(1\leq N\leq 200)

第二行NN个数字表示Ti(1Ti2×106)T_i(1\leq T_i \leq 2\times 10^6)

第三行NN个数字表示Di(0Di106)D_i(0\leq D_i \leq 10^6),保证DiD_i是递增的。

输出格式

对于每组数据,输出一个数字表示答案。

样例输入1

2
4 3
0 3
2
3 3
0 3
4
5 200 1 2
0 1 2 3

样例输出1

1 2
Mission Impossible
1 2 4 3

样例解释

没有解释就是最好的解释。