Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

All the Cuts

Limits: 3s, 512 MB

In a two dimensional plane, there are “R” red points, “B” blue points and “G” green points. These points are expressed as ordered pair (x, y), x being the abscissa and y being the ordinate. For red points, y > 0. For other points, y < 0. We will call CD a cut on AB if line segment AB intersects line segment CD where A is a red point, B is a blue point and C, D are green points. For a line segment AB there can be arbitrary number of cuts.

Let us define a function F(i, j) to be the number of ways there can be “i” cuts on line segment “j” where “j” is a line segment connecting a red point and a blue point as mentioned above. Again, let us define a function g(p, q, j) as:

g(p, q, j) = (F(p, j) - F(p+1, j) + F(p+2, j) - F(p+3, j) …….. upto F(q, j)) modulo (10^9 + 7)

Find the sum of g(p, q, j) for all “j” modulo (10^9 + 7).

Input

The first line will contain integer T denoting number of test cases.

The next line will contain integer R denoting number of red points. Next R lines will contain two integer denoting the co-ordinate of the red points.

The next line will contain integer B denoting number of blue points. Next B lines will contain two integer denoting the co-ordinate of the blue points.

The next line will contain integer G denoting number of green points. Next G lines will contain two integer denoting the co-ordinate of the green points.

Next line will contain two integer denoting p and q.

1 <= sum of red points over all test cases <= 2000

1 <= sum of blue points over all test cases <= 2000

1 <= sum of green points over all test cases <= 2000

1 <= p <= q <= 10^8

For any point, -10^8 <= x, y <= 10^8.

For a single test case, there will not be any 3 points lying on same straight line.

Output

Print one line for each test case denoting the answer. Check sample output for actual output format.

Samples

InputOutput
2

1
0 5
1
0 -500
3
-1 -1
1 -1
1 -2
1 2

1
0 5
2
0 -500
-1 -501
3
-1 -1
1 -1
1 -2
1 2
1
2

In the first test case, for segment AB joining point (0, 5) and (0, -500) there can be at most 2 cuts. So,

F(1, AB) = 2

F(2, AB) = 1

So, g(1, 2, AB) = F(1, AB) - F(2,AB) = 2 - 1 = 1

Since, in there can be only one segment joining red points and blue points g(1, 2, AB) is the answer.

In the second test case, there will be two segment for which we have to calculate function g. For both of them the value of function g is 1. So, the answer is 1 + 1 = 2.

Discussion
Submit

Login to submit

Editorial

Login to unlock editorial