最近小仓鼠正在玩一款叫qaq的游戏，这款游戏中每个玩家有一棵技能树，技能树中一共有n

一个已经到达i级的技能升到i+1级需要消耗c_i点技能点。

有些技能存在前置技能，一共有k对前置关系，第i对关系为：学习技能v_i需要前置技能u_i。一个技能可以学习当且仅当它的所有前置技能都学习了至少一级。注：因为游戏还不完善，所以可能技能树中依赖关系存在环。

由于小仓鼠具有强迫症，如果他当前有k点技能点，那他就一定会把它们全部用完。请对于每个k=1,2,3,...,m计算，有多少种点技能的方式满足刚好消耗了k点技能点。两个方案不同当且仅当某个技能的学习等级在两个方案中不同。

本题输入含多组数据。第一行有一个数字T （1≤T≤10），表示数据总数。

对于每组数据，第一行有四个正整数n,m,k,s 

(1≤n≤15,1≤m≤1000,1≤k≤n*(n-1),1≤s≤1000)，分别表示技能的数量、技能点的范围、前置关系的数量以及技能的最高级数。

接下来一行包含s个正整数c₁,c₂,…,c_s(1≤c_i≤m)，依次表示把i-1级技能升一级所需的技能点。

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

输出T行。每行m个整数ans₁,ans₂,…,ans_m，其中ans_i表示恰好消耗i点技能点的方案数。因为答案可能很大，请对10⁹+7取模后输出