순례의 끝

순례자는 영원히 끝나지 않을 것만 같은 순례를 계속하고 있다. 순례자는 위치한 성지에서 다른 성지로 이동하고, 성지에 도착할 때마다 신께 기도를 드린다. 그리고 이것을 계속 반복한다.

지상에는 총 $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$ 번째 줄에, 각 성지를 이동하는 데 드는 시간을 나타내는 음이 아닌 정수 $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$이 가장 최근에 방문한 성지 번호다. $M$이 주어진 순서대로 성지를 방문했을 때, $M\_N$번 성지에서 기도를 마치고 다시 이동을 시작하는 시점부터, 순례가 끝을 맺는 데 드는 시간의 기댓값을 구해 출력해야 한다.

$Q$ 개의 줄에 걸쳐 정답을 출력한다. 이 문제에서 주어질 수 있는 모든 입력에 대해 기댓값이 유리수임이 증명되어 있으므로 다음과 같은 방식으로 출력한다.

$i$번째로 주어진 방문 순서에 대한 기댓값을 기약분수로 나타냈을 때, $\frac{P\_i}{Q\_i}$ 라고 하자. $i$번째 줄에는 $P\_i \equiv Q\_i R\_i (mod \\; X)$을 만족하는 $0$이상 $X$미만의 정수 $R\_i$를 출력하면 된다. 이 문제에서 주어질 수 있는 모든 입력에 대해 이런 $R\_i$가 유일하게 존재함이 확인되어 있다.