Argentina Suffered one of the World Cup’s greatest shocks as Saudi Arabia came from behind to win and you are upset about the match. Sadly you couldn’t think of anything interesting so, you started solving this problem.
Given two straight lines (Parallel to x-axis) and (distance between these two lines is a positive integer). Line contains distinct integer coordinate points on it and line contains distinct integer coordinate points on it. You need to find out the maximum number of intersections possible by drawing straight lines between any two points of line and .
For example,
Line has 3 points on it (-2, 1), (0, 1), (2, 1) and
Line has 2 points on it (-1, -1), (1, -1)
Draw a straight line between (, ), (, ), (, ) and (, )
You will find three intersections between these four lines. You can see, this is the maximum number of intersections. No intersection will occur by any other line.
Each test contains multiple test cases. The first line contains the number of test cases . The description of the test cases follows.
The first line of each test case consists of two integers and — total number of integer coordinate points on line and total number of integer coordinate points on line .
The second line of each test case consists of two integers and separated by space.
represents the value for all coordinates on line
represents the value for all coordinates on line
The third line of each test case consists of integers — Which represent the value of for coordinate on line A.
The fourth line of each test case consists of integers — Which represent the value of for coordinates on line B.
and
For each test case, output a single integer — Total number of intersections possible by drawing straight lines between any two points of line and line . The answer may be large, so output it modulo .
Input | Output |
---|---|
1 3 2 1 -1 -2 0 2 -1 1 | 3 |
Test case 1 is explained in the statement. |