#P2479. 航班

航班

问题描述

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

直飞航班的可用性由 NN 个长度为 NN 的字符串 S1,S2,,SNS_1,S_2,\ldots,S_N 表示。如果 SiS_ijj 个字符是 Y,则有从城市 ii 到城市 jj 的直飞航班;如果是 N,则没有。

每个城市都出售纪念品;城市 ii 出售价值 AiA_i 的纪念品。

拓拓目前在城市 SS ,想去城市 TT (与城市 SS 不同)。(与城市 SS 不同)。 他每次去一个城市(包括 SSTT ),都会在那里买一件纪念品。
如果从城市 SS 到城市 TT 有多条路线,拓拓决定路线如下:

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

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

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

给你 QQ(Ui,Vi)(U_i,V_i) 不同的城市。

S=UiS=U_iT=ViT=V_i 时,请为每个 1iQ1\leq i\leq Q 输出上述问题的答案。

输入格式

第一行一个整数 NN

第二行 NN 个整数,A1,A2,...,ANA_1,A_2,...,A_N

接下来 NN 行,NN 个长度为 NN 的字符串。

N+3N + 3 行一个整数 QQ,表示 QQ 次询问。

最后 QQ 行,每行两个整数 UiU_iViV_i

输出格式

输出 QQ 行,如果他不能从城市 UiU_i 前往城市 ViV_i ,则第 ii 行应输出 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)=(U1,V1)=(1,3)(S,T)=(U_1,V_1)=(1,3) 来说,有一个从城市 11 到城市 33 的直达航班,所以直达航班的最少可能数量是 11 ,当他使用该直达航班时,就达到了这个数量。在这种情况下,纪念品的总价值为 A1+A3=30+70=100A_1+A_3=30+70=100

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

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

2
100 100
NN
NN
1
1 2
Impossible

数据范围

  • 2N3002 \leq N \leq 300
  • 1Ai1091\leq A_i\leq 10^9
  • SiS_i 是一个长度为 NN 的字符串,由 YN 组成。
  • SiS_iii -th 字符是 N
  • 1QN(N1)1\leq Q\leq N(N-1)
  • 1Ui,ViN1\leq U_i,V_i\leq N
  • UiViU_i\neq V_i
  • 如果是 iji \neq j ,那么就是 (Ui,Vi)(Uj,VJ)(U_i,V_i)\neq (U_j,V_J)
  • N,Ai,Q,UiN,A_i,Q,U_iViV_i 都是整数。