纪念品

题目描述

有 $N$ 个城市,以及连接不同城市之间的单向直飞航班。

直飞航班的可用情况由 $N$ 个长度为 $N$ 的字符串 $S_1,S_2,\ldots,S_N$ 表示。如果 $S_i$ 的第 $j$ 个字符是 Y,则存在从城市 $i$ 到城市 $j$ 的直飞航班;如果是 N,则不存在。

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

考虑以下问题:

高桥君目前在城市 $S$,想要乘坐若干直飞航班前往城市 $T$(与城市 $S$ 不同)。

每当他访问一个城市(包括 $S$ 和 $T$)时,他都会在那里购买纪念品。

如果从城市 $S$ 到城市 $T$ 有多条路线,高桥君按如下方式决定路线:

他首先尽量最小化从城市 $S$ 到城市 $T$ 的路线中直飞航班的数量。

然后他尽量最大化所购买纪念品的总价值。

判断他能否使用直飞航班从城市 $S$ 前往城市 $T$。如果可以,求出满足上述条件的路线中的「直飞航班数量」和「纪念品总价值」。

给定 $Q$ 对互不相同的城市 $(U_i,V_i)$。

对于每个 $1 \le i \le Q$,当 $S=U_i$、$T=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 \le i \le Q)$:如果无法从城市 $U_i$ 前往城市 $V_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 \le N \le 300$
• $1 \le A_i \le 10^9$
• $S_i$ 是由 Y 和 N 组成的长度为 $N$ 的字符串。
• $S_i$ 的第 $i$ 个字符是 N。
• $1 \le Q \le N(N-1)$
• $1 \le U_i,V_i \le 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$ 均为整数。