题目描述

从前有 $n$ 座岛，每个岛上有 $a_i$ 个金币，各个岛间有若干条单向航线相连。

你从某个岛开始旅行，经过一个岛（包括最开始所在的岛）就会拿走上面的金币。

现在问你 $q$ 个问题：从岛 $u_i$ 旅行到岛 $v_i$，最少要走几条航线，以及恰好走这么多条航线最多能获得多少金币。如果根本无法到达 $v_i$，输出 Impossible。

询问之间相互独立。

输入格式

输入第一行一个整数 $n$ 表示岛的数量。

接下来一行 $n$ 个整数表示每个岛上的金币数。

接下来 $n$ 行每行一个长为 $n$ 的字符串，第 $i$ 行字符串的第 $j$ 个字符若为 Y 则表示岛 $i$ 和 $j$ 间有单向航线，否则表示没有。

接下来一行一个整数 $q$ 表示询问次数。

最后 $q$ 行每行两个整数 $u_i,v_i$，询问你从岛 $u_i$ 旅行到岛 $v_i$ 最少要走几条航线，以及恰好走这么多条航线最多能获得多少金币。

输出格式

对于每个询问输出一行：

• 若 $u_i$ 不能到达 $v_i$，输出 Impossible；
• 否则，输出从岛 $u_i$ 旅行到岛 $v_i$ 最少要走几条航线，以及恰好走这么多条航线最多能获得多少金币。

样例解释 1

这些岛的结构如下：

• 对于第 $1$ 个询问，因为岛 $1$ 有一条航线通往岛 $3$，显然最少航线为 $1$ 条，此时能拿到岛 $1$ 和岛 $3$ 上的金币共 $30+70=100$ 个。
• 对于第 $2$ 个询问，可以证明最少航线为 $2$ 条，有两种方案 $3 \rarr 4 \rarr 1$ 和 $3 \rarr 5 \rarr 1$，总金币分别为 $70+20+30=120$ 和 $70+60+30=160$，故最多金币为 $160$。
• 对于第 $3$ 个询问，只有一种方案 $4 \rarr 1 \rarr 3 \rarr 5$ 可以使航线数最少为 $3$，所得金币为 $20+30+70+60=180$。

样例解释 2

笑死，连航线都没有。

数据范围与约定

对于 $100\%$ 的数据，$2\le n\le 300,1\le a_i\le 10^9,1\le q\le n(n-1),1\le u_i,v_i\le n$，且询问中的 $u_i,v_i$ 各不相同。

翻译者：not_Rick_Astley