题目描述

有 $N$ 座编号为 $1$ 至 $N$ 的城市，城市间由单向直达航班连接。航班的可用性通过 $N$ 个长度为 $N$ 的字符串 $S_1, S_2, \cdots, S_N$ 表示，若 $S_i$ 的第 $j$ 个字符为 'Y' ，则表示从编号为 $i$ 的城市到编号为 $j$ 的城市有直达航班；若为 'N' ，则无直达航班。

每座城市都销售一种纪念品，编号为 $i$ 的城市所售纪念品价值为 $A_i$ 。

小T目前位于城市 $S$ ，想要通过直达航班前往城市 $T$（$T$ 与 $S$ 不同 ），且每到达一个城市（包括 $S$ 和 $T$ ）都会购买一件纪念品。当从城市 $S$ 到城市 $T$ 存在多条路线时，小T遵循以下决策规则：

1. 优先减少从城市 $S$ 到城市 $T$ 所经过的直达航班数量。
2. 在航班数量相同的情况下，尽量使购买纪念品的总价值最大化。

给定 $Q$ 对不同的城市 $(U_i, V_i)$ ，需要针对每一对城市判断小T能否从 $U_i$ 到 $V_i$ 旅行。若能，找出满足上述规则的路线中所经过的“直达航班数量”和“纪念品总价值”；若不能，则输出 “Impossible” 。

输入格式

• 第一行：输入整数 $N$（$2 \leq N \leq 300$ ），表示城市的数量。
• 第二行：输入 $N$ 个整数 $A_1$ 至 $A_N$（$1 \leq A_i \leq 10^9$ ），代表各城市纪念品的价值。
• 接下来 $N$ 行：每行输入长度为 $N$ 的字符串 $S_1$ 至 $S_N$ ，由 'Y' 和 'N' 组成，代表直达航班的信息。
• 再接下来输入整数 $Q$（$1 \leq Q \leq N(N - 1)$ ），表示询问的总数。
• 最后 $Q$ 行：每行输入两个整数 $U_i, V_i$（$1 \leq U_i, V_i \leq N$ 且 $U_i \neq V_i$ ），代表起止城市的编号。

输出格式

输出 $Q$ 行：

• 若无法从城市 $U_i$ 到城市 $V_i$ 旅行，则输出 "Impossible" 。
• 若可以旅行，则按照顺序输出所经过的“直达航班数量”和“纪念品总价值”，两者用空格分隔。

示例

• 输入示例1

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

• 输出示例1

1 90
1 130
2 150

• 解释：

对于第1个询问，从4到3有2条不同路线，4 -> 3 直达的路线航班最少，经过1个航班，纪念品总价值为 $20 + 70 = 90$ ；对于第2个询问，从3到5有2条不同路线，3 -> 5 直达的路线航班最少，经过1个航班，纪念品总价值为 $70 + 60 = 130$ ；对于第3个询问，从1到3有2条不同路线，路线1 -> 2 -> 3 与路线1 -> 4 -> 3 都经过2个航班，前者纪念品总价值为 $30 + 50 + 70 = 150$ ，后者为 $30 + 20 + 70 = 120$ ，选择总价值大的，即输出2 150 。

• 输入示例2

10
1 2 1 2 5 2 1 4 3 1
NYNNNYYNYN
NNYNNNNNNN
NNNYNNNNNN
NNNNNNNNNN
NNNYNNNNNN
NNNNYNNNNN
NNNNNNNYNN
NNNYNNNNNN
NNNNNNNNNY
NNNYNNNNNN
3
1 4
4 1
1 10

• 输出示例2

3 10
Impossible
2 5

数据范围

• 城市数量 $N$ 满足 $2 \leq N \leq 300$ 。
• 纪念品价值 $A_i$ 满足 $1 \leq A_i \leq 10^9$ 。
• 字符串 $S_i$ 长度为 $N$ ，由 'Y' 和 'N' 组成。
• 询问次数 $Q$ 满足 $1 \leq Q \leq N(N - 1)$ ，起止城市编号 $U_i, V_i$ 满足 $1 \leq U_i, V_i \leq N$ 且 $U_i \neq V_i$ 。