Limits
1s, 256 MB

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) $A$ and $B$ (distance between these two lines is a positive integer). Line $A$ contains $n$ distinct integer coordinate points on it and line $B$ contains $m$ 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** $A$ **and** $B$**.**

For example,

Line $A$ has 3 points on it $A_1$ (-2, 1), $A_2$ (0, 1), $A_3$ (2, 1) and

Line $B$ has 2 points on it $B_1$ (-1, -1), $B_2$ (1, -1)

Draw a straight line between ($A_1$, $B_2$), ($A_2$, $B_1$), ($A_2$, $B_2$) and ($A_3$, $B_1$)

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 $t$**.** The description of the test cases follows.

The first line of each test case consists of two integers $n$ and $m$ — total number of integer coordinate points on line $A$ and total number of integer coordinate points on line $B$.

The second line of each test case consists of two integers $A_Y$ and $B_Y$ separated by space.

$A_Y$ represents the $Y$ value for all coordinates on line $A.$

$B_Y$ represents the $Y$ value for all coordinates on line $B.$

The third line of each test case consists of $n$ integers $A_{X_{i}}$ — Which represent the value of $X$ for $i^{th}$coordinate on line A.

The fourth line of each test case consists of $m$ integers $B_{X_{i}}$ — Which represent the value of $X$ for $i^{th}$ coordinates on line B.

$1$ $≤$ $t$ $≤$ $10$

$1$ $≤$ $n ,$$m$ $≤$ $10^5$

$-10^2$ $≤$ $A_Y,$ $B_Y$ $≤$ $10^2$ **and** $A_Y$ $≠$ $B_Y$

$-10^5$ $≤$ $A_{X_{i}}$ $≤$ $10^5$

$-10^5$ $≤$ $B_{X_{i}}$ $≤$ $10^5$

For each test case, output a single integer — Total number of intersections possible by drawing straight lines between any two points of line $A$ and line $B$. The answer may be large, so output it modulo $10^9$ $+$ $7$.

Input | Output |
---|---|

1 3 2 1 -1 -2 0 2 -1 1 | 3 |

Test case 1 is explained in the statement. |

Login to submit.

0%
Solution Ratio

Toph uses cookies. By continuing you agree to our Cookie Policy.