You are given two arrays a and b of lengths n and m respectively.
Let real number x be a root of an equation if the equation holds for it. Calculate the number of roots for the following equation or determine if it has infinitely many roots:
Here ∣a∣ denotes the absolute value of a number, i.e., ∣a∣=a if a≥0 and ∣a∣=−a if a<0.
The first line of the input contains two integers n and m (1≤n≤2⋅105; 1≤m≤2⋅105).
The second line contains n integers a1,a2,…,an (∣ai∣≤109).
The third line contains m integers b1,b2,…,bm (∣bi∣≤109).
In the only line, you need to output the number of roots for the given equation, or "Infinity
" if there are infinitely many roots.
In the first test case, the equation is ∣x−1∣=∣x−1∣, which holds for any x.
In the second test, the equation is
The root for this equation is x=8:
It can be proved that this equation does not have other roots.
In the third test, the equation is
The are 3 roots for this equation: x=2,x=632,x=10. Notice that roots can be not only integers.
It can be proved that this equation does not have other roots.
(14 points): n=m; ai=bi (1≤i≤n);
(30 points): n=m=1;
(61 points): ∣ai∣≤20 (1≤i≤n); ∣bi∣≤20 (1≤i≤m);
(84 points): n,m≤1000;
(161 points): no additional constraints.