题目描述

在你的帮助之下，Miaoyao 成功完成了他的编程作业，于是他又开始了一局新的游戏。这次他玩的游戏背景为一个仙侠世界。当前，Miaoyao 被困在一个阵法中。阵法可以视为一个 $n$ 行 $m$ 列的矩形区域，每个小格都各有玄机，一旦踏入就需要耗费一定量的灵气抵御（离开后重新进入，同样需要消耗灵气）。还有一些位置暗藏杀阵，不可进入。Miaoyao 每次只能向上下左右这四个方向移动一格。阵法包含 $k$ 个阵眼和一个阵核。想要破阵而出，必须要在每个阵眼处各放置一件法宝，然后再从阵核离阵。显然，Miaoyao 不希望消耗过多的灵气，于是他想要你帮助他算出破阵所需消耗的最小灵气值。

输入格式

第一行两个整数 $n$, $m$。

接下来 $n$ 行，每行 $m$ 个整数，第 $i$ 行第 $j$ 列的整数 $w_{i,j}$ 表示到达该位置所消耗的灵气值。若 $w_{i,j}$ 为 $-1$，则表示该点不可进入。

接下来一行，一个整数 $k$。

接下来 $k$ 行，每行两个整数 $r$, $c$，表示阵眼所在的行列。

接下来一行，四个整数 $sr$, $sc$, $tr$, $tc$，分别表示起点所在的行、起点所在的列、阵核所在的行、阵核所在的列。

输入保证 $w_{sr,sc} = 0$，阵眼各不相同、不与阵核重合，且阵眼与阵核均不在无法进入（即 $w_{i,j} = -1$）的格子。

输出格式

若能破阵，则输出一个整数，表示最小的灵气消耗，否则输出 Impossible（不含引号）。

样例输入

5 5
0 2 -1 -1 -1
-1 3 -1 -1 -1
-1 1 2 3 4
-1 4 3 2 1
-1 -1 -1 -1 5
2
3 3
4 2
1 1 5 5

样例输出

24

提示

$1 \leq n, m \leq 50$。

$-1 \leq w_{i,j} \leq 1000$。

$1 \leq k \leq 9$。

$1 \leq r, sr, tr \leq n$。

$1 \leq c, sc, tc \leq m$。