Problem Description

As a cold-blooded, hot-blooded, and iron-blooded vampire, Shinobu loves traveling around.

There are $P$ countries in total, numbered $0,1,\dots ,P-1$.(It is guaranteed that $P$ is a prime number)

It is known that when Shinobu is in the country numbered $i$, the next country she visits must be the country numbered $(i\cdot a) \mod P$ ($a$ is a constant parameter), and it takes Shinobu $1$ day to go from one country to another.

In order to travel smoothly, Shinobu has customized $n$ travel plans, and the $i$-th travel plan is represented by the starting country $s_i$ and the travel days $d_i$.

For example, if $P = 233,\ a = 2$, a plan's starting country is $1$ and travel days is $2$, then Shinobu will visit the city $\{ 1,2,4 \}$ according to this plan.

Playf knows these travel plans and the value of parameter $a$, now he wants to ask you $q$ questions. The $i$-th question asks how many travel plans will make shinobu visit the country $x_i$.

Input

The first line of the input contains one integer $T$ $($$1\leq T\leq 5$ $)$ --- the number of test cases. Then $T$ test cases follow.

For each testcase, the first line contains four integers $P,\ a,\ n,\ q(2\le a< P \le 1000000007, 1\le n \le 1000, 1\le q \le 1000 )$ --- the number of countries, the value of $a$, the number of Shinobu's travel plans and the number of playf's questions.

Each of the next $n$ lines contains two integers $s_i,\ d_i(0\le s_i< P, 1\le d_i \le 200000 )$ --- the starting country and the travel days.

Each of the next $q$ lines contains one integer $x_i(0\le x_i< P)$ --- playf's questions.

It is guaranteed that $P$ is a prime number.

Output

For each testcase, print $q$ lines, the $i$-th line contains one integer --- the answer to the $i$-th question.

2
3 2 1 1
1 1
2
5 4 3 2
1 4
4 3
2 100000
4
2

1
2
1