6580: Shinobu loves trip
内存限制：256 MB
时间限制：3.000 S
评测方式：文本比较
命题人：
提交：3
解决：3
题目描述
As a cold-blooded, hot-blooded, and iron-blooded vampire, Shinobu loves traveling around.
There are P countries in total, numbered 0,1,…,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⋅a)modP (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 si and the travel days di.
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 xi.
There are P countries in total, numbered 0,1,…,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⋅a)modP (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 si and the travel days di.
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 xi.
输入
The first line of the input contains one integer T (1≤T≤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≤a<P≤1000000007,1≤n≤1000,1≤q≤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 si, di(0≤si<P,1≤di≤200000) --- the starting country and the travel days.
Each of the next q lines contains one integer xi(0≤xi<P) --- playf's questions.
It is guaranteed that P is a prime number.
For each testcase, the first line contains four integers P, a, n, q(2≤a<P≤1000000007,1≤n≤1000,1≤q≤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 si, di(0≤si<P,1≤di≤200000) --- the starting country and the travel days.
Each of the next q lines contains one integer xi(0≤xi<P) --- playf's questions.
It is guaranteed that P is a prime number.
输出
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