Group by sum

Aggregate 125,000,000 key/value records by key as fast as possible.

The task is equivalent to this query:

SELECT SUM(s * s) FROM (
    SELECT SUM(value) AS s FROM records GROUP BY key
)

Input

Exactly 125,000,000 records on STDIN, 8 bytes each, back to back (1,000,000,000 bytes in total):

Guarantees:

• The records contain exactly 4,000,000 distinct keys.
• A key is an arbitrary value in [0, 2^32) and may repeat any number of times.
• A value is an arbitrary value in [0, 2^32).

Output

Group the records by key, sum the values of each group, then write the sum of the squares of those group sums to STDOUT as a decimal string:

answer = SUM(sum_k * sum_k) over all 4,000,000 distinct keys k

Both the squaring and the outer sum are computed modulo 2^64 (unsigned 64-bit wraparound). An individual group sum never overflows uint64.

Example

For the six records

key=7 value=10
key=3 value=4000000000
key=7 value=20
key=9 value=1
key=3 value=4000000000
key=7 value=30

the group sums are sum_7 = 60, sum_3 = 8000000000 and sum_9 = 1, so

60*60 + 8000000000*8000000000 + 1*1 = 64000000000000003601
64000000000000003601 mod 2^64       = 8659767778871348753

and the program prints 8659767778871348753.