/** Sep 19, 2015 12:41:25 PM
 * PrjName:0919-10
 * @author Semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {

    /**
     * @param args
     */
    static long[] s,l,f,ans;
    static String[] sh,sr;
    final static int maxn=201315;
    final static long mod=530600414L;
    static long mul_mod(long n, long m, long mod) {
        long ans = 0L;
        n %= mod;
        while (m > 0L) {
            if ((m & 1L) > 0L)
                ans = (ans + n) % mod;
            m >>= 1;
            n = (n + n) % mod;
        }
        return ans;
    }
    static void init(){
        s=new long[maxn];
        l=new long[maxn];
        f=new long[maxn];
        ans=new long[maxn];
        sh=new String[maxn];
        sr=new String[maxn];
        s[1]=s[2]=0;s[3]=1;s[4]=3;
        f[1]=f[2]=0;f[3]=f[4]=1;
        l[1]=1;l[2]=2;l[3]=3;l[4]=5;
        ans[1]=ans[2]=ans[3]=ans[4]=0;
        sh[3]=new String("cf");sr[3]=new String("ff");
        sr[4]=new String("ff");sr[4]=new String("ff");
    }
    static long solve(int n/*,PrintWriter out*/){
        long res=0L;
        if (n<5) return res;
        if (ans[n]>0L) return ans[n];
        res+=solve(n-2);
        res+=solve(n-1);
        //res+=solve(n-2,out);
        //res+=solve(n-1,out);
        sh[n]=sh[n-2];sr[n]=sr[n-1];
        boolean has=false;
        if (sr[n-2].compareTo("cf")==0&&sh[n-1].charAt(0)=='f'){
            has=true;s[n]+=l[n-2]-1;
            res-=s[n-2];
            res+=mul_mod((l[n-2]-1),f[n-2],mod);
        }
        if (sr[n-2].charAt(1)=='c'&&sh[n-1].compareTo("ff")==0){
            has=true;s[n]+=l[n-2];
            res-=s[n-2];
            res+=mul_mod(l[n-2],f[n-2],mod);
        }
        s[n]+=(s[n-2]+s[n-1]+mul_mod(l[n-2],f[n-1],mod))%mod;s[n]%=mod;
        f[n]=has?f[n-2]+f[n-1]+1:f[n-2]+f[n-1];f[n]%=mod;
        l[n]=l[n-2]+l[n-1];l[n]%=mod;
        //out.print(n+":");out.print(res+" ");
        res-=mul_mod(s[n-2],f[n-1],mod);//out.print(res+" ");
        //res+=s[n-1]*(has?f[n-2]+1:f[n-2]);out.print(res+" ");
        //res+=l[n-2]*f[n-1];out.println(res+" ");
        res+=mul_mod(s[n-1]+mul_mod(l[n-2],f[n-1],mod),f[n-2],mod);//out.println(res+" ");
        while(res<0L) res+=mod;
        //if (has) res+=
        res%=mod;
        ans[n]=res;
        return res;
    }
    public static void main(String[] args) throws IOException{
        // TODO Auto-generated method stub
        InputReader in=new InputReader(System.in);
        PrintWriter out=new PrintWriter(System.out);
        int T=in.nextInt(),cas=0;
        init();
        for(int i=5;i<maxn;i++)
            solve(i);
        while(T-->0){
            //long k=solve(in.nextInt(), out);
            long k=solve(in.nextInt());
            out.println("Case #"+(++cas)+": "+k);
        }
        out.flush();
        out.close();
    }
}

/** Sep 13, 2015 12:39:06 PM
 * PrjName:0913-01
 * @author Semprathlon
 */
import java.io.*;
import java.util.*;

public class Main {
	static Person[] per;
	static Pair[] cm;
	static PriorityQueue<Person> que = new PriorityQueue<Person>(new Person.Comp());
	static Vector<String> ans = new Vector<String>();

	public static void main(String[] args) throws IOException {
		InputReader in = new InputReader(System.in);
		PrintWriter out = new PrintWriter(System.out);
		int T = in.nextInt();
		while (T-- > 0) {
			int n = in.nextInt();
			int m = in.nextInt();
			int q = in.nextInt();
			per = new Person[n];
			for (int i = 0; i < n; i++)
				per[i] = new Person(in.next(), in.nextInt(), i + 1);
			cm = new Pair[m];
			for (int i = 0; i < m; i++)
				cm[i] = new Pair(in.nextInt(), in.nextInt());
			Arrays.sort(cm, new Pair.Comp());
			que.clear();
			int t = 0;
			ans.clear();
			for (int i = 0; i < n; i++) {
				que.add(per[i]);
				if (t < m && cm[t].l == i + 1) {
					for (int j = 0; j < cm[t].r && !que.isEmpty(); j++)
						ans.add(que.poll().name);
					t++;
				}
			}
			while (!que.isEmpty())
				ans.add(que.poll().name);
			while (q-- > 0) {
				out.print(ans.get(in.nextInt() - 1) + (q > 0 ? " " : ""));
			}
			out.println();
		}
		out.flush();
		out.close();
	}
}

class Person {
	String name;
	int v, t;
	Person() {
	}
	Person(String _nm, int _v, int _t) {
		name = _nm;
		v = _v;
		t = _t;
	}
	static class Comp implements Comparator<Person> {
		public int compare(Person p1, Person p2) {
			if (p1.v == p2.v)
				return Integer.compare(p1.t, p2.t);
			return -Integer.compare(p1.v, p2.v);
		}
	}
}

class Pair {
	int l, r;
	Pair() {
	}
	Pair(int a, int b) {
		l = a;
		r = b;
	}
	static class Comp implements Comparator<Pair> {
		public int compare(Pair o1, Pair o2) {
			if (o1.l == o2.l)
				return Integer.compare(o1.r, o2.r);
			return Integer.compare(o1.l, o2.l);
		}
	}
}

/** Sep 13, 2015 9:26:58 AM
 * PrjName:0913-10
 * @author Semprathlon
 */
import java.io.*;
import java.util.*;

public class Main {

    final static int maxn = 110000;
    static long[] fac = new long[maxn];
    static long[] p, a;
    static long x, y;

    static void Get_Fac(long n) {
        fac[0] = 1;
        for (int i = 1; i <= n; i++) {
            fac[i] = fac[i - 1] * i;
            fac[i] %= n;
        }
    }

    static void extgcd(long a, long b) {
        if (b == 0L) {
            x = 1L;
            y = 0L;
            return;
        }
        extgcd(b, a % b);
        long t = x;
        x = y;
        y = t - a / b * y;
    }

    static long pow_mod(long n, long m, long mod) {
        long res = 1L;
        n %= mod;
        while (m > 0L) {
            if ((m & 1L) > 0L)
                res = res * n % mod;
            n = n * n % mod;
            m >>= 1;
        }
        return res;
    }

    static long mul_mod(long n, long m, long mod) {
        long ans = 0L;
        n %= mod;
        while (m > 0L) {
            if ((m & 1L) > 0L)
                ans = (ans + n) % mod;
            m >>= 1;
            n = (n + n) % mod;
        }
        return ans;
    }

    static long div_mod(long n, long m, long mod) {
        return n * pow_mod(m, mod - 2, mod) % mod;
    }

    static long C(long n, long m, long mod) {
        int a = (int) (n % mod), b = (int) (m % mod);
        return div_mod(fac[a], mul_mod(fac[a - b], fac[b], mod), mod);
    }

    static long Lucas(long n, long m, long mod) {
        long ret = 1L;
        while (n > 0L && m > 0L) {
            if (n % mod < m % mod)
                return 0L;
            ret = mul_mod(ret, C(n, m, mod), mod);
            ret %= mod;
            n /= mod;
            m /= mod;
        }
        return ret;
    }

    // 中国剩余定理 x == a[i] (mod m[i]) 共有n个方程。
    static long CRT(long n, long[] a, long[] m) {
        long pro = 1L, res = 0L;
        for (int i = 0; i < n; i++)
            pro *= m[i];
        for (int i = 0; i < n; i++) {
            long w = pro / m[i];
            extgcd(m[i], w);
            res = (res + mul_mod(y, mul_mod(w, a[i], pro), pro)) % pro;
        }
        return (res + pro) % pro;
    }

    public static void main(String[] args) {
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int T = in.nextInt();
        while (T-- > 0) {
            long n = in.nextLong();
            long m = in.nextLong();
            long num = in.nextLong();
            p = new long[15];
            a = new long[15];
            for (int i = 0; i < num; i++)
                p[i] = in.nextLong();
            for (int i = 0; i < num; i++) {
                Get_Fac(p[i]);
                a[i] = Lucas(n, m, p[i]);
            }
            out.println(CRT(num, a, p));
        }
        out.flush();
        out.close();
    }

}