题目描述

有 $N$ 座城市，编号为 $1$ 到 $N$。城市之间开设了一些单向直达航班。

用 $N$ 个长度均为 $N$ 的字符串 $S_1,S_2,\ldots,S_N$ 表示航班信息。如果 $S_i$ 的第 $j$ 个字符为 Y，表示存在从城市 $i$ 到城市 $j$ 的直达航班；如果该字符为 N，表示不存在这样的航班。

城市 $i$ 出售价值为 $A_i$ 的纪念品。一次旅行会在经过的每座城市购买一件纪念品，出发城市和到达城市也包括在内。

对于每次从城市 $U$ 到城市 $V$ 的旅行，按以下顺序选择路线：

1. 经过的直达航班数量尽可能少。
2. 在满足第一个条件的路线中，购买的纪念品总价值尽可能大。

请回答每次询问。

输入格式

第一行包含一个整数 $N$，表示城市数量。

第二行包含 $N$ 个整数 $A_1,A_2,\ldots,A_N$，表示各城市纪念品的价值。

接下来 $N$ 行，每行包含一个长度为 $N$ 的字符串。其中第 $i$ 行为 $S_i$。

接下来一行包含一个整数 $Q$，表示询问数量。

接下来 $Q$ 行，每行包含两个整数 $U_i,V_i$，表示一次旅行的出发城市和到达城市。

输出格式

对于每次询问输出一行。

如果无法从城市 $U_i$ 到达城市 $V_i$，输出 Impossible。

否则，依次输出最少经过的直达航班数量和在此条件下最大的纪念品总价值，两个整数之间用一个空格分隔。

样例

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

1 90
1 130
2 150

样例解释

从城市 $1$ 到城市 $3$ 的最少航班数为 $2$。路线 $1\to2\to3$ 和路线 $1\to4\to3$ 都经过 $2$ 个航班，两条路线的纪念品总价值分别为 $150$ 和 $120$，因此选择前一条路线。

10
1 2 1 2 5 2 1 4 3 1
NYNNNYYNYN
NNYNNNNNNN
NNNYNNNNNN
NNNNNNNNNN
NNNYNNNNNN
NNNNYNNNNN
NNNNNNNYNN
NNNYNNNNNN
NNNNNNNNNY
NNNYNNNNNN
3
1 4
4 1
1 10

3 10
Impossible
2 5

数据范围与提示

• $2 \le N \le 300$。
• $1 \le A_i \le 10^9$。
• $S_i$ 的长度为 $N$，且只包含字符 Y 和 N。
• $S_i$ 的第 $i$ 个字符为 N。
• $1 \le Q \le N(N-1)$。
• $1 \le U_i,V_i \le N$，且 $U_i \ne V_i$。
• 任意两次询问给出的有序城市对不同。