Inference

Problem Description

Given $m$ features, you want to infer the last feature's value of Alice by the value of her first $m-1$ features, based on massive data. The relationship between features can be represented as a directed acyclic graph, where a node $A$ pointing to a node $B$ indicates that $B$ is a random variable dependent on $A$. The following formula can calculate the probability of the last feature's value of Alice based on other data, in which $x_i$ represents the $i-$th feature, $\pi(x_i)$ represents nodes that point to $x_i$, and $cnt$ represents their number of occurrences:

$$P(x_m|x_1,\dots,x_{m-1})=cP(x_1,\dots,x_m)=\prod_{i=1}^m P(x_i|\pi(x_i)) $$$$P(x_i|\pi(x_i))=\frac{P(\pi(x_i), x_i)}{P(\pi(x_i))}=\begin{cases}\frac{cnt(\pi(x_i), x_i)}{cnt(\pi(x_i))},\text{ if }cnt(\pi(x_i))\ne 0\\\\0,\text{ if }cnt(\pi(x_i))=0\end{cases} $$

It is guaranteed that the last feature has zero out-degree, and there exists at least one case of value such that $cnt(\pi(x_i))\ne0$. Now, given $n$ people's data, what is the most likely value of the $m-$th feature of Alice, given the value of her first $m-1$ features.

Input

At the beginning of the input section, there is an integer $T(1\le T\le 10)$, indicating the number of test cases. For every test case, the first line consists of three integers $n(1\le n\le 10^4)$, $m(1\le m\le 100)$, $k(1\le k\le 300)$, indicating the number of data, the number of features, and the number of the relationship between the features. In the next $k$ rows, each row contains two integers $x,y(1\le x,y \le m)$, indicating node $x$ point to node $y$, thus $y-$th feature is dependent on $x-$th feature. Every point has an in-degree less than 5. In the next $n$ rows, each row contains $m$ integers indicating one person's values of each feature. Every feature's value is among $0,1,2$. In the last line, there are $m-1$ integers indicating Alice's values of the first $m-1$ features. (请不要使用 scanf 进行读入)

Output

An integer denoting the most probable value of Alice's $m-$th feature. It is guaranteed that there exists only $1$ value which has the biggest probability.

Sample Input

1
10 5 4
1 4
2 4
3 5
4 5
0 1 0 1 0
0 1 1 1 1
0 0 0 0 0
0 0 1 0 0
1 1 1 0 1
1 0 0 1 1
1 1 0 1 1
1 0 1 0 0
1 1 1 1 1
0 1 0 1 1
1 1 0 0

Sample Output

0

Hint

Source

2023“钉耙编程”中国大学生算法设计超级联赛（9）