using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("5");
WillReturn.Add("30 50 70 20 60");
WillReturn.Add("NYYNN");
WillReturn.Add("NNYNN");
WillReturn.Add("NNNYY");
WillReturn.Add("YNNNN");
WillReturn.Add("YNNNN");
WillReturn.Add("3");
WillReturn.Add("1 3");
WillReturn.Add("3 1");
WillReturn.Add("4 5");
//1 100
//2 160
//3 180
}
else if (InputPattern == "Input2") {
WillReturn.Add("2");
WillReturn.Add("100 100");
WillReturn.Add("NN");
WillReturn.Add("NN");
WillReturn.Add("1");
WillReturn.Add("1 2");
//Impossible
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
struct CostDef
{
internal long EdgeCnt;
internal long OmiyageSum;
}
static void Main()
{
List<string> InputList = GetInputList();
long[] wkArr = { };
Action<string> SplitAct = pStr =>
wkArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();
long N = long.Parse(InputList[0]);
long UB = N - 1;
long[] AArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();
CostDef?[,] CostArr = new CostDef?[UB + 1, UB + 1];
// 隣接行列を作る
long FromNode = 0;
foreach (string EachStr in InputList.Skip(2).Take((int)N)) {
for (long I = 0; I <= EachStr.Length - 1; I++) {
if (EachStr[(int)I] == 'N') continue;
long ToNode = I;
CostDef WillSet;
WillSet.EdgeCnt = 1;
WillSet.OmiyageSum = AArr[I];
CostArr[FromNode, ToNode] = WillSet;
}
FromNode++;
}
// ワーシャルフロイド法
for (long K = 0; K <= UB; K++) {
for (long I = 0; I <= UB; I++) {
if (CostArr[I, K].HasValue == false) continue;
for (long J = 0; J <= UB; J++) {
if (CostArr[K, J].HasValue == false) continue;
CostDef NewCost;
NewCost.EdgeCnt = CostArr[I, K].Value.EdgeCnt + CostArr[K, J].Value.EdgeCnt;
NewCost.OmiyageSum = CostArr[I, K].Value.OmiyageSum + CostArr[K, J].Value.OmiyageSum;
bool CanSet = true;
if (CostArr[I, J].HasValue) {
if (CostArr[I, J].Value.EdgeCnt < NewCost.EdgeCnt) {
CanSet = false;
}
if (CostArr[I, J].Value.EdgeCnt == NewCost.EdgeCnt) {
if (CostArr[I, J].Value.OmiyageSum > NewCost.OmiyageSum) {
CanSet = false;
}
}
}
if (CanSet) {
CostArr[I, J] = NewCost;
}
}
}
}
var sb = new System.Text.StringBuilder();
foreach (string EachStr in InputList.Skip(2 + (int)N + 1)) {
SplitAct(EachStr);
long StaNode = wkArr[0] - 1;
long GoalNode = wkArr[1] - 1;
if (CostArr[StaNode, GoalNode].HasValue) {
long EdgeCnt = CostArr[StaNode, GoalNode].Value.EdgeCnt;
long OmiyageSum = CostArr[StaNode, GoalNode].Value.OmiyageSum;
OmiyageSum += AArr[StaNode];
sb.AppendFormat("{0} {1}", EdgeCnt, OmiyageSum);
sb.AppendLine();
}
else {
sb.AppendLine("Impossible");
}
}
Console.Write(sb.ToString());
}
}