Two Hash Functions, One Awkward Key Set

A table has m = 2^{r} buckets. Two classic ways to turn a key k into a bucket index:

• division: k % m
• multiplication: ((a * k) % 2**width) >> (width - r) — multiply, keep the low width bits, then take the top r of those.

Given a list of integer keys, return the tuple (worst_division, worst_multiplication), where each entry is the number of keys landing in the fullest bucket under that function.

Examples

Input:  keys = [0, 8, 16, 24], r = 3, a = 1, width = 32
Output: (4, 4)
Explanation: every key is a multiple of 8, so division sends all four to bucket 0; with a = 1 the multiplication method shifts them all to 0 as well.

Input:  keys = [1, 2, 3], r = 2, a = 1, width = 4
Output: (1, 3)
Explanation: division spreads them over buckets 1, 2 and 3; (k % 16) >> 2 is 0 for all three.

Constraints

• 0 <= len(keys) <= 10**5, 0 <= keys[i] < 2**40
• 1 <= r <= 20, 1 <= a < 2**32, r < width <= 64

Goals

• Implement the division and the multiplication hash function
• Measure a hash function by its worst bucket, not by its average
• See how a key set in step with the table size breaks the division method