问题描述

有 $N$ 个城市。还有一些连接不同城市的单向直达航班。 直达航班的可用性由 $N$ 个长度为 $N$ 的字符串 $S_1,S_2,\\ldots,S_N$ 表示。如果第 $i$ 个字符串 $S_i$ 的第 $j$ 个字符是 Y，表示从城市 $i$ 到城市 $j$ 有一次直达航班；如果是 N，则没有。 每个城市都销售纪念品；城市 $i$ 销售价值为 $A_i$ 的纪念品。

考虑下面的问题：

Takahashi 目前在城市 $S$，想要通过一些直达航班到达城市 $T$（城市 $S$ 和城市 $T$ 不同）。 每次他访问一个城市（包括 $S$ 和 $T$），他都会在那里购买一个纪念品。 如果从城市 $S$ 到城市 $T$ 存在多条路线，Takahashi 将按照以下方式选择路线：

• 他试图使得从城市 $S$ 到城市 $T$ 的直达航班数最小。
• 然后，他试图最大化他购买的纪念品的总价值。

确定他是否可以使用直达航班从城市 $S$ 到达城市 $T$。如果可以，找到满足上述条件的路线中的“直达航班数”和“纪念品的总价值”。

给定 $Q$ 对不同城市的 $(U_i,V_i)$。 对于每个 $1\\leq i\\leq Q$，当 $S=U_i$ 且 $T=V_i$ 时，打印出上述问题的答案。

约束条件

• $2 \\leq N \\leq 300$
• $1\\leq A_i\\leq 10^9$
• $S_i$ 是长度为 $N$ 的字符串，由 Y 和 N 组成。
• $S_i$ 的第 $i$ 个字符是 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$ 都是整数。

输入

输入以以下格式从标准输入给出：

$N$ $A_1$ $A_2$ $\\ldots$ $A_N$ $S_1$ $S_2$ $\\vdots$ $S_N$ $Q$ $U_1$ $V_1$ $U_2$ $V_2$ $\\vdots$ $U_Q$ $V_Q$

输出

输出共 $Q$ 行。 第 $i$ 行 $(1\\leq i\\leq Q)$ 应打印出 Impossible，如果他无法从城市 $U_i$ 出发到达城市 $V_i$；否则，这一行应按照上述要求给出选择的路线中的“直达航班数”和“纪念品的总价值”，用一个空格隔开。

示例输入 1

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

示例输出 1

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

2
100 100
NN
NN
1
1 2

示例输出 2

Impossible

可能根本没有直达航班。