AT_abc286_e [ABC286E] Souvenir

从前有 $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](https://www.luogu.com.cn/user/689673)

### 制約 - $ 2\ \leq\ N\ \leq\ 300 $ - $ 1\leq\ A_i\leq\ 10^9 $ - $ S_i $ は `Y` と `N` のみからなる長さ $ 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 $ は全て整数 ### Sample Explanation 1 $ (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 $ の $ 2 $ 通りが考えられます。 それぞれの経路の時のお土産の価値の総和は $ 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 $ となります。 ### Sample Explanation 2 直行便が全く存在しないこともあります。