N. [Light blue] Can you find the passion ?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Void has recently hit a mental block and is struggling to write competitive programming problems. To spark some ideas, he decides to visit an art museum.

The museum contains $$$n$$$ paintings. Each painting $$$i$$$ grants Void $$$a_i$$$ units of inspiration. There is also a global museum constant, $$$m$$$.

Void is very moody. Every day, he wakes up with a specific mood, represented by an integer $$$r$$$. On a day with mood $$$r$$$, Void will only look at paintings that satisfy the condition: $$$a_i \bmod m = r$$$. His total inspiration for the day will be the sum of the $$$a_i$$$ values of all paintings that satisfy this condition.

You are given $$$q$$$ queries, each representing a different day. For each query, Void needs at least $$$x$$$ units of total inspiration to write a problem, and he has a mood of $$$r$$$. Determine if Void will gather enough inspiration on each day.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 10^5$$$) — denotes the number of paintings and the modulo constant.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — denotes the inspiration provided by each painting.

The third line contains a single integer $$$q$$$ ($$$1 \le q \le 10^5$$$) — denotes the number of queries.

The next $$$q$$$ lines each contain two integers $$$x$$$ and $$$r$$$ ($$$1 \le x \le 10^{14}$$$, $$$0 \le r \lt m$$$) — denotes the minimum required inspiration and Void's mood for that day.

Output

For each query, print "YES" (without quotes) if Void can gather at least $$$x$$$ units of inspiration. Otherwise, print "NO".

Example
Input
5 3
4 7 10 2 8
4
15 1
16 1
10 2
11 2
Output
YES
YES
YES
NO