Problem H

在天赋系统中，一共有$n$个技能，编号依次为1到$n$，每个技能可以学习很多级，也可以不学习。

一共有$m$点技能点，第$i$个技能每往上多点一级需要消耗$c_i$点技能点。

有些技能存在前置技能，一共有$k$对前置关系，第$i$对关系为：学习技能$v_i$需要前置技能$u_i$。如果$u_i$学习了0级，那么不能学习$v_i$。一个技能可以学习当且仅当它的所有前置技能都学习了至少一级。

请对于每个$k=1,2,3,\dots,m$计算，有多少种点技能的方式满足刚好消耗了$k$点技能点。两个方案不同当且仅当某个技能的学习等级在两个方案中不同。

第一行包含一个正整数$T(1\leq T\leq 10)$，表示测试数据的组数。

每组测试数据第一行包含三个正整数$n,m,k(1\leq n\leq 15,1\leq m\leq 1000,1\leq k\leq \frac{n(n-1)}{2})$，分别表示技能的数量、技能点的数量以及前置关系的数量。

第二行包含$n$个正整数$c_1,c_2,\dots,c_n(1\leq c_i\leq m)$，依次表示每个技能所需的技能点。

接下来$k$行，每行包含两个正整数$u_i,v_i(1\leq u_i<v_i\leq n)$，描述一对前置关系。输入数据保证同一对关系不会被输入多次。

对于每组数据，输出一行$m$个整数$ans_1,ans_2,\dots,ans_m$，其中$ans_i$表示恰好消耗$i$点技能点的方案数。因为答案可能很大，请对$10^9+7$取模输出。

1
3 8 1
2 4 3
1 3

0 1 0 2 1 2 1 4

"字节跳动杯"杭州电子科技大学第二十届程序设计竞赛