Description

听说公主被关押在城堡里，彭大侠下定决心：不管一路上有多少坎坷，不管城堡中的看守有多少厉害，不管救了公主之后公主会不会再被抓走，不管公主是否漂亮、是否会钟情于自己，他将义无反顾地朝着城堡前进。

可是，通往城堡的路上出现了一些情况。抽象地说，假象地图在二维平面的第一象限。在每个横轴的 $x$ 位置上有一个高为$h_x$ 的支撑点，如果彭大侠没有跳到支撑点上，那么他就会掉下去，牺牲在路途。开始时彭大侠在起点 $(1,h_1)$ 处，而城堡的入口在 $(n,h_n)$处。彭大侠每次可以从支撑点 $(x,h_x)$跳到支撑点 $(x+1,h_{x+1})$。但是彭大侠每次的跳跃能量只有 $d$，也就是说，每次跳跃必须满足条件 $|h_{x+1}-h_n| \leq d$。换句话说，如果两个相邻支撑点的纵向落差大于 $d$，那么彭大侠就无法跳跃了！幸运的是，彭大侠还有一个杀手锏。在起点处，他可以花一个金币，把某个支撑点升高$1$ 个单位，或者降低 $1$ 个单位。但是，起点处和城堡入口处的支撑点高度不能改变，并且一旦离开起点彭大侠就无法使用该杀手锏。

彭大侠被告知$100$个金币可兑换一单位生命。于是他希望通过少花金币来保存更多单位的生命。他终于找到了你这位热心的高手，请你帮他规划一下以便耗费尽量少的金币来到达城堡。

Format

Input

Output

有 $m$ 行，第 $I~(1 \leq I \leq m)$ 行表示第 $I$ 次求解时彭大侠到达城堡必须耗费的最少金币数量。 若无论怎样使用杀手锏他都无法到达城堡，则输出 impossible。

输入数据保证答案在 $int64$ 范围之内。

Samples

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

6
impossible
4

Limitation