The End of the Pilgrimage

A pilgrim keeps making a pilgrimage that seems like it will never end. The pilgrim moves from the holy site where they are to another holy site, and each time they arrive at a holy site, they pray to God. They repeat this over and over.

There are $N$ holy sites on earth, numbered from 1 to $N$. Moving from holy site $i$ to holy site $j$ takes exactly $L_{i,j}$ minutes. The time to travel between two different holy sites can differ by direction. When the pilgrim arrives at holy site $i$, they pray there for exactly $P_i$ minutes.

After finishing a prayer, the pilgrim moves to the next holy site immediately, following God's revelation. God picks one of the other $N-1$ holy sites, excluding the one where the pilgrim is, with equal probability $\frac{1}{N-1}$, and tells the pilgrim. The pilgrim goes there at once. God is almighty and the pilgrim is very quick, so the time between a move and a prayer, or between a prayer and a move, is 0 minutes.

If the last $N$ holy sites the pilgrim visited, counted when a prayer ends, are all different, the pilgrimage ends and the pilgrim enters the kingdom God has prepared.

The last $N$ holy sites the pilgrim visited are given in order. Find the expected time from the moment the pilgrim finishes praying at their current holy site and starts moving again until the pilgrimage ends.

The first line contains the number of holy sites $N$ and a prime $X$ ($10^9 \leq X \leq 10^9 + 10^4$). The use of $X$ is explained in the output section.

The second line contains the prayer times $P_1, P_2, \cdots, P_N$ ($1 \leq P_i \leq 10^6$), where $P_i$ is the time spent praying at holy site $i$.

The next $N$ lines contain the travel times. The $i$-th of these lines contains $L_{i,1}, L_{i,2}, \cdots, L_{i,N}$ ($0 \leq L_{i,j} \leq 10^6$, $L_{i,i}=0$).

The next line contains the number of queries $Q$ ($1 \leq Q \leq 10^5$).

Each of the next $Q$ lines contains $N$ positive integers $M_1, M_2, \cdots, M_N$ ($1 \leq M_i \leq N$, $M_{i-1} \neq M_i$). $M_1$ is the oldest visited holy site, and $M_N$ is the most recently visited one.

Print $Q$ lines of answers. For every valid input, the expected value is proven to be a rational number.

Let the expected value for the $i$-th visit sequence be the irreducible fraction $\frac{P_i}{Q_i}$. On the $i$-th line, print the integer $R_i$ with $0 \leq R_i < X$ that satisfies $P_i \equiv Q_i R_i \pmod{X}$. It is verified that such an $R_i$ exists and is unique for every valid input.