当前没有测试数据。

E - 纪念品

得分：$500$ 分

问题描述

有 $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\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$ ； 如果可以，这一行应包含满足上述条件的路线的 "直达航班数量" 和 "纪念品总价值" ，用空格分隔。

---

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

可能根本没有直达航班。