Mathematical Equation

[hacker9876]

Problem Statement:
Prakhar is fond of solving the mathematical equations,one day his girlfriend asked him a new equation to solve.Equation is as follows:
K*(K+1) = 4*A*B + 2*max(A,B)
She also gives him an array(A) of pair(A,B) of size N,and asks Q queries,in each query she gives the value of K and asks for the number of pairs which is present in the array(A) and satisfies the given equation for given K.
Prakhar got stucked in solving the given equation but he don't want to dissapoint his girlfriend,so he is asking for your help,can you help him out?


INPUT:
First line contains two space seperated integer N [size of the array(A)] and Q (number of query to ask).
Next N lines contains two space separated integers each lines denotes [information of pair(A,B)] of array(A).
Next line contains Q space sepereted integers (value of K).

OUTPUT:
For each Q, print a single integer in new line denoting inverse modulo of the number of pairs which satisfies the given equation and also present in the given array(A) with 10^9+9 or -1 if there is no such pair exist.

CONSTRAINTS:
1<=N<=10^5
1<=A[i],B[i]<=10^9
1<=Q<=10^5
1<=K<=2*10^9

SUBTASKS:
Subtask #1(100 points)
Original constraints

Example
Input:
4 3
1 1
2 2
13 5
1 1
1 4 2


Output:
-1
1
500000005


Explanation:
Testcase 1 :
For first query for [ k=1 ] there exist no such pair so answer is -1.
For second query for [ k=4 ] there is exist a pair (2,2) which satisfies the equation so answer is inverse modulo of 1 with 10^9+9.
For third query for [ k=4 ] there is exist a pair (1,1) which satisfies the equation and present 2 times in the array(A) so answer is inverse modulo of 2 with 10^9+9.



Can anyone give me a hint how to solve this problem?? My doubt was that suppose as per given input a[i]=1 and b[i]=1 so as per the given equation we calculate 4*a[i]*b[i]+2*max(a[i],b[i]) and the value is 6 when a[i]=1 and b[i]=1. So i will take another array and increment 6th index of array. But when a[i]=10^9 and b[i]=10^9 then it is not possible to take array of that size!!??

[ne555]

then change your approach, you're asking for too much memory.

[hacker9876]

can u hint me the other approach

[ne555]

you are computing the right side of the equation and storing it in a set
the representation that you used for that set requires too much memory
¿what other representations do you know?

[dhayden]

Each A,B pair produces a value V for the right hand side of the equation. Use a map to map V values to the the number of times that they occur. Populate the map as you read the A,B pairs.

Then when you read the values of K, compute the left hand side of the equation. Try to find that value in the map. If it's present then the count is the number of A,B pairs that satisfy the equation. If not present then no pair satisfies the equation.

[hacker9876]

@dhayden
I couldn't understand your approach.Can u explian it clearly

[ne555]

//construction
for (a,b) in array:
   value = 4*a*b + 2*max(a, b)
   dictionary[value] += 1

//query
value = k * (k+1)
return dictionary[value]

[ghostrideriit]

Expand the formula Chech rhs and LHS .....

U will get a relation between a,b and k....

[hacker9876]

@ne555
But it leads to memory issue and we cannot initailize an array with that size

[dhayden]

we cannot initailize an array with that size

Who said anything about using an array. I said "map" and ne555 said "dictionary".

[jonnin]

you probably can, actually. 10^9 for a 4-byte int is what, 4-5 gigs? Well not a stack array, but a heap / vector can hold this much. I often open xml files this big in a single chunk. Its a lot of memory but not impossible. I wouldn't do it this way unless you can show that it is the best /fastest way, but don't ignore this as a possibility either.