暂无测试数据。

小 X 正困在一个密室里，他希望尽快逃出密室。

密室中有 $N$ 个房间，初始时，小 X 在 $1$ 号房间，而出口在 $N$ 号房间。

密室的每一个房间中可能有着一些钥匙和一些传送门，一个传送门会单向地创造一条从房间 $X$ 到房间 $Y$ 的通道。另外，想要通过某个传送门，就必须具备一些种类的钥匙（每种钥匙都要有才能通过）。幸运的是，钥匙在打开传送门的封印后，并不会消失。

然而，通过密室的传送门需要耗费大量的时间，因此，小 X 希望通过尽可能少的传送门到达出口，你能告诉小 X 这个数值吗？

另外，小 X 有可能不能逃出这个密室，如果是这样，请输出 "No Solution"。

输入格式

第一行三个整数 $N,M,K$，分别表示房间的数量、传送门的数量以及钥匙的种类数。

接下来 $N$ 行，每行 $K$ 个 $0$ 或 $1$，若第 $i$ 个数为 $1$，则表示该房间内有第 $i$ 种钥匙，若第 $i$ 个数为 $0$，则表示该房间内没有第 $i$ 种钥匙。

接下来 $M$ 行，每行先读入两个整数 $X,Y$，表示该传送门是建立在 $X$ 号房间，通向 $Y$ 号房间的，再读入 $K$ 个 $0$ 或 $1$，若第 $i$ 个数为 $1$，则表示通过该传送门需要 $i$ 种钥匙，若第 $i$ 个数为 $0$，则表示通过该传送门不需要第 $i$ 种钥匙。

输出格式

输出一行一个 "No Solution"，或一个整数，表示最少通过的传送门数。

数据规模与约定

更多测试样例

输入样例 4

输出样例 4

3 3 2
1 0
0 1
0 0
1 3 1 1
1 2 1 0
2 3 1 1

2

20 40 0
10 18 
18 14 
19 13 
4 14 
13 10 
5 18 
14 1 
13 13 
10 16 
19 11 
11 15 
10 18 
5 8 
12 19 
7 8 
18 6 
14 5 
9 5 
2 17 
13 14 
18 15 
8 18 
7 1 
13 5 
4 6 
17 4 
1 4 
10 10 
13 8 
19 2 
4 9 
3 3 
5 10 
17 5 
12 8 
19 11 
3 16 
17 10 
18 16 
13 13 

No Solution

20 50 0
8 10 
7 17 
5 11 
14 20 
20 16 
8 19 
12 11 
18 7 
17 5 
4 15 
16 11 
11 8 
10 12 
8 9 
16 8 
3 16 
1 6 
3 20 
6 10 
11 12 
6 8 
18 17 
14 17 
3 11 
4 19 
9 2 
8 6 
13 2 
5 2 
12 19 
8 10 
14 7 
6 12 
6 4 
13 2 
8 7 
13 19 
17 9 
3 14 
18 20 
2 14 
4 17 
20 15 
14 15 
2 15 
7 20 
12 12 
18 10 
15 9 
15 9 

4