Description

A cheating casino has $N$ dice. In this casino, there may have been $M$ games. Each game consists of rolling a die to produce a face value. We do not know which die was used, but we do know the outcome $O(i)$ of the $i$-th game.

For die $i$, the probability of rolling face $j$ is $A(i, j)$. After using die $i$, the probability that the next game uses die $j$ is $B(i, j)$. In particular, for the first game, the probability of using die $i$ is $\pi(i)$.

Curious Xiao v asks you to compute the probability that these $M$ games occurred in this casino.

Input Format

The first line contains three positive integers $N, M, Q$.

The second line contains $N$ floating-point numbers, representing $\pi(i)$.

Lines 3 to $N+2$ contain $N \times Q$ floating-point numbers; in row $i+2$ and column $j$ is $A(i, j)$.

Lines $N+3$ to $2 \times N + 2$ contain $N \times N$ floating-point numbers; in row $N+2+i$ and column $j$ is $B(i, j)$.

Line $2 \times N + 3$ contains $M$ positive integers, representing the $M$ game outcomes $O_i$, i.e., the face values rolled in each game.

Output Format

Output the required probability, rounded to four decimal places.

3 10 3
1 0 0
0.03 0.03 0.94
0.02 0.02 0.96
0.99 0.005 0.005
0.01 0.99 0
0.05 0.05 0.90
0.98 0.002 0.008 
2 2 0 2 2 0 2 2 0 2

0.4483

Hint

Constraints and notes:

• For 30% of the testdata: $M \le 100$, $1 \le N$, $Q \le 10$.
• For 100% of the testdata: $1 \le M \le 1000$, $1 \le N$, $Q \le 50$.

The matrices $A, B$ and the vector $\pi$ satisfy the characteristic conditions of probability transitions.

Translated by ChatGPT 5