题目描述

强哥所在的地区有 $n$ 个村庄，每个村庄储备了 $a_i$ 份爱心物资。各村之间有一些单向的运输路线。

强哥从某个村庄出发运送物资，每经过一个村庄（包括起点）就会收集该村庄的物资。

现在有 $q$ 个运输任务：从村庄 $u_i$ 运送物资到村庄 $v_i$。对于每个任务，需要求出：

1. 最少需要经过几条运输路线
2. 在走最少路线的情况下，最多能收集多少份物资

如果无法从 $u_i$ 到达 $v_i$，则输出 Impossible。

各个运输任务之间相互独立。

输入格式

第一行一个整数 $n$，表示村庄数量。

第二行 $n$ 个整数，表示每个村庄的物资数量。

接下来 $n$ 行，每行一个长度为 $n$ 的字符串。第 $i$ 行第 $j$ 个字符为 Y 表示存在从村庄 $i$ 到村庄 $j$ 的单向运输路线，为 N 表示没有。

接下来一行一个整数 $q$，表示运输任务数量。

最后 $q$ 行，每行两个整数 $u_i, v_i$，表示一个运输任务的起点和终点。

输出格式

对于每个运输任务输出一行：

• 如果无法到达，输出 Impossible
• 否则输出两个整数：最少路线条数和最多物资数量

输入输出样例

样例 1

输入

5
30 50 70 20 60
NYYNN
NNYNN
NNNYY
YNNNN
YNNNN
3
1 3
3 1
4 5

输出

1 100
2 160
3 180

说明

• 任务1：村庄1→村庄3，最少1条路线，物资30+70=100
• 任务2：村庄3→村庄1，最少2条路线（3→4→1），物资70+20+30=120？等等需要重新计算...

让我重新分析样例输出：

• 1→3：直接走，路线数1，金币30+70=100 ✓
• 3→1：3→5→1，路线数2，金币70+60+30=160 ✓
• 4→5：4→1→3→5，路线数3，金币20+30+70+60=180 ✓

样例 2

输入

2
100 100
NN
NN
1
1 2

输出

Impossible

数据范围

• $2 \le n \le 300$
• $1 \le a_i \le 10^9$
• $1 \le q \le n(n-1)$
• $1 \le u_i, v_i \le n$，且 $u_i \neq v_i$