问题描述

有 $N$ 座城市。还有连接不同城市的单程直飞航班。

直飞航班的可用性由 $N$ 个长度为 $N$ 的字符串 $S_1,S_2,\ldots,S_N$ 表示。如果 $S_i$ 的 $j$ 个字符是 Y，则有从城市 $i$ 到城市 $j$ 的直飞航班；如果是 N，则没有。

每个城市都出售纪念品；城市 $i$ 出售价值 $A_i$ 的纪念品。

拓拓目前在城市 $S$ ，想去城市 $T$ (与城市 $S$ 不同)。(与城市 $S$ 不同）。 他每次去一个城市(包括 $S$ 和 $T$ )，都会在那里买一件纪念品。
如果从城市 $S$ 到城市 $T$ 有多条路线，拓拓决定路线如下：

• 他试图尽量减少从城市 $S$ 到城市 $T$ 的航线中直飞航班的数量。

• 然后，他试图使购买的纪念品总价值最大。

确定他是否可以乘坐直飞航班从城市 $S$ 前往城市 $T$ 。如果可以，求满足上述条件的路线中的 "直飞航班数 "和 "纪念品总价值"。

给你 $Q$ 对 $(U_i,V_i)$ 不同的城市。

当 $S=U_i$ 和 $T=V_i$ 时，请为每个 $1\leq i\leq Q$ 输出上述问题的答案。

输入格式

第一行一个整数 $N$。

第二行 $N$ 个整数，$A_1,A_2,...,A_N$。

接下来 $N$ 行，$N$ 个长度为 $N$ 的字符串。

第 $N + 3$ 行一个整数 $Q$，表示 $Q$ 次询问。

最后 $Q$ 行，每行两个整数 $U_i$ 和 $V_i$。

输出格式

输出 $Q$ 行，如果他不能从城市 $U_i$ 前往城市 $V_i$ ，则第 $i$ 行应输出 Impossible；如果可以，则该行应包含按上述路线选择的 "直飞航班数量 "和 "纪念品总价值"，按此顺序排列，中间用空格隔开。

样例

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

1 100
2 160
3 180

对于 $(S,T)=(U_1,V_1)=(1,3)$ 来说，有一个从城市 $1$ 到城市 $3$ 的直达航班，所以直达航班的最少可能数量是 $1$ ，当他使用该直达航班时，就达到了这个数量。在这种情况下，纪念品的总价值为 $A_1+A_3=30+70=100$ 。

对于 $(S,T)=(U_2,V_2)=(3,1)$ ，直飞航班的最少可能数量为 $2$ 。以下两条线路达到了最小值：城市 $3\to 4\to 1$ 和城市 $3\to 5\to 1$ 。由于这两条路线的纪念品总价值分别为 $70+20+30=120$ 和 $70+60+30=160$ ，所以他选择了后一条路线，纪念品的总价值为 $160$ 。

对于 $(S,T)=(U_3,V_3)=(4,5)$ ，当他前往城市 $4\to 1\to 3\to 5$ 时，直达航班的数量最少，纪念品的总价值为 $20+30+70+60=180$ 。

2
100 100
NN
NN
1
1 2

Impossible

数据范围

• $2 \leq N \leq 300$
• $1\leq A_i\leq 10^9$
• $S_i$ 是一个长度为 $N$ 的字符串，由 Y 和 N 组成。
• $S_i$ 的 $i$ -th 字符是 N。
• $1\leq Q\leq N(N-1)$
• $1\leq U_i,V_i\leq N$
• $U_i\neq V_i$
• 如果是 $i \neq j$ ，那么就是 $(U_i,V_i)\neq (U_j,V_J)$ 。
• $N,A_i,Q,U_i$ 和 $V_i$ 都是整数。