순례의 끝

순례자는 끝나지 않을 것처럼 보이는 순례를 계속하고 있다. 순례자는 지금 있는 성지에서 다른 성지로 이동하고, 성지에 도착할 때마다 신께 기도를 드린다. 이 과정을 계속 반복한다.

지상에는 성지가 $N$개 있고, 1번부터 $N$번까지 번호가 붙어 있다. 순례자가 $i$번 성지에서 $j$번 성지로 이동하는 데는 정확히 $L_{i,j}$분이 걸린다. 서로 다른 두 성지를 오가는 데 걸리는 시간은 다를 수 있다. 순례자가 $i$번 성지에 도착하면 정확히 $P_i$분 동안 기도한다.

기도를 마친 순례자는 신의 계시에 따라 지체 없이 다음 성지로 이동한다. 신은 순례자가 있는 성지를 뺀 나머지 $N-1$개 성지 중 하나를 모두 같은 확률 $\frac{1}{N-1}$로 골라 순례자에게 알려 주고, 순례자는 즉시 그곳으로 간다. 신은 전능하고 순례자는 매우 기민하므로, 이동과 기도 사이, 기도와 이동 사이에 걸리는 시간은 0분이다.

순례자가 기도를 마친 시점에 가장 최근에 들른 성지 $N$개가 모두 서로 다르면, 순례는 끝나고 순례자는 신이 준비한 나라에 들어간다.

순례자가 가장 최근에 들른 성지 $N$개가 방문한 순서대로 주어진다. 순례자가 현재 성지에서 기도를 마치고 다시 이동을 시작하는 시점부터 순례가 끝날 때까지 걸리는 시간의 기댓값을 구하여라.

첫째 줄에 성지의 개수 $N$과 소수 $X$ ($10^9 \leq X \leq 10^9 + 10^4$)가 주어진다. $X$의 용도는 출력 부분에 나온다.

둘째 줄에 각 성지에서 기도하는 시간 $P_1, P_2, \cdots, P_N$ ($1 \leq P_i \leq 10^6$)이 주어진다.

다음 $N$개 줄의 $i$번째 줄에는 $i$번 성지에서 각 성지로 이동하는 시간 $L_{i,1}, L_{i,2}, \cdots, L_{i,N}$ ($0 \leq L_{i,j} \leq 10^6$, $L_{i,i}=0$)이 주어진다.

다음 줄에는 기댓값을 구해야 하는 횟수 $Q$ ($1 \leq Q \leq 10^5$)가 주어진다.

다음 $Q$개 줄에는 각각 자연수 $N$개 $M_1, M_2, \cdots, M_N$ ($1 \leq M_i \leq N$, $M_{i-1} \neq M_i$)이 주어진다. $M_1$은 가장 오래전에 방문한 성지 번호이고, $M_N$은 가장 최근에 방문한 성지 번호이다.

$Q$개 줄에 걸쳐 답을 출력한다. 모든 입력에 대해 기댓값이 유리수임이 증명되어 있다.

$i$번째로 주어진 방문 순서에 대한 기댓값을 기약분수 $\frac{P_i}{Q_i}$로 나타냈다고 하자. $i$번째 줄에는 $P_i \equiv Q_i R_i \pmod{X}$를 만족하는 $0$ 이상 $X$ 미만의 정수 $R_i$를 출력한다. 모든 입력에 대해 이런 $R_i$가 하나만 존재함이 확인되어 있다.