Fast Squarier Transform
Fast Squarier Transform
You are given two arrays of integers [a_1, a_2, \dots, a_n] and [b_1, b_2, \dots, b_m].
Find the following value:
Note that \lfloor x \rfloor denotes the maximum integer not exceeding x, and |x| denotes the absolute value of x.
Input data
The first line of the input contains 2 integers n, m (1 \leq n, m \leq 10^5).
The second line of the input contains n integers a_1, a_2, \dots, a_n (0 \le a_i, a_1 + a_2 + \ldots + a_n \le 2\cdot 10^7).
The third line of the input contains m integers b_1, b_2, \dots, b_m (0 \le b_i, b_1 + b_2 + \ldots + b_m \le 2\cdot 10^7).
Output data
Print a single integer — the sum from the statement.
Examples
1 2 1 2 3
2
2 3 1 2 3 4 5
7
Note
In the first sample the answer is \lfloor \sqrt{|1 - 2|} \rfloor + \lfloor \sqrt{|1 - 3|} \rfloor = \lfloor \sqrt{1} \rfloor + \lfloor \sqrt{2} \rfloor = 1 + 1 = 2.
In the second sample, the answer is \lfloor \sqrt{|1 - 3|} \rfloor + \lfloor \sqrt{|1 - 4|} \rfloor + \lfloor \sqrt{|1 - 5|} \rfloor + \lfloor \sqrt{|2 - 3|} \rfloor + \lfloor \sqrt{|2 - 4|} \rfloor + \lfloor \sqrt{|2 - 5|} \rfloor = \lfloor \sqrt{2} \rfloor + \lfloor \sqrt{3} \rfloor + \lfloor \sqrt{4} \rfloor + \lfloor \sqrt{1} \rfloor + \lfloor \sqrt{2} \rfloor + \lfloor \sqrt{3} \rfloor = 1 + 1 + 2 + 1 + 1 + 1 = 7.