broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(x):
    m = x['m']
    k = x['k']
    c = [0] * m
    def positions(item):
        h1 = item % m
        h2 = 1 + (item // m) % (m - 1)
        out = []
        for i in range(k):
            p = (h1 + i * h2) % m
            if p not in out:
                out.append(p)
        return out
    res = []
    for op, item in x['ops']:
        pos = positions(item)
        if op == 'add':
            for p in pos:
                if c[p] < 15:
                    c[p] = c[p] + 1
            res.append('added')
        elif op == 'remove':
            if any(c[p] == 0 for p in pos):
                res.append('absent')
                continue
            for p in pos:
                if c[p] < 15:
                    c[p] = c[p] - 1
            res.append('removed')
        else:
            res.append(any(c[p] > 0 for p in pos))
    return [res, c]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['duplicate probe positions',
   {'k': 4,
    'm': 12,
    'ops': [['add', 63], ['add', 1], ['has', 63], ['remove', 63], ['has', 63], ['has', 1]]},
   [['added', 'added', True, 'removed', False, True], [0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0]]],
  ['hot item with repeated positions',
   {'k': 4,
    'm': 12,
    'ops': [['add', 63],
            ['add', 63],
            ['add', 63],
            ['add', 63],
            ['add', 63],
            ['add', 63],
            ['add', 63],
            ['add', 63],
            ['remove', 63],
            ['remove', 63],
            ['remove', 63],
            ['remove', 63],
            ['remove', 63],
            ['remove', 63],
            ['remove', 63],
            ['remove', 63],
            ['has', 63]]},
   [['added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     False],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
  ['wide stride item',
   {'k': 3, 'm': 12, 'ops': [['add', 137], ['add', 8], ['has', 137], ['remove', 8]]},
   [['added', 'added', True, 'removed'], [0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0]]],
  ['saturating counter',
   {'k': 2,
    'm': 12,
    'ops': [['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['remove', 4],
            ['has', 4]]},
   [['added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'removed',
     True],
    [0, 0, 0, 0, 15, 15, 0, 0, 0, 0, 0, 0]]],
  ['atomic removal of absent item',
   {'k': 3, 'm': 12, 'ops': [['add', 6], ['remove', 42], ['has', 6]]},
   [['added', 'absent', True], [0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0]]],
  ['partial overlap membership',
   {'k': 3, 'm': 12, 'ops': [['add', 2], ['add', 14], ['has', 26], ['has', 3], ['has', 2]]},
   [['added', 'added', False, False, True], [0, 0, 2, 1, 2, 0, 1, 0, 0, 0, 0, 0]]],
  ['normal add and remove',
   {'k': 2, 'm': 12, 'ops': [['add', 31], ['add', 32], ['remove', 31], ['has', 31], ['has', 32]]},
   [['added', 'added', 'removed', False, True], [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1]]],
  ['remove absent from empty',
   {'k': 2, 'm': 12, 'ops': [['remove', 9], ['has', 9]]},
   [['absent', False], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
  ['saturated then drained',
   {'k': 1,
    'm': 12,
    'ops': [['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['has', 6]]},
   [['added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     True],
    [0, 0, 0, 0, 0, 0, 15, 0, 0, 0, 0, 0]]]],
 [['duplicate probe positions',
   {'k': 4,
    'm': 14,
    'ops': [['add', 87], ['add', 1], ['has', 87], ['remove', 87], ['has', 87], ['has', 1]]},
   [['added', 'added', True, 'removed', False, True], [0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
  ['hot item with repeated positions',
   {'k': 4,
    'm': 14,
    'ops': [['add', 87],
            ['add', 87],
            ['add', 87],
            ['add', 87],
            ['add', 87],
            ['add', 87],
            ['add', 87],
            ['add', 87],
            ['remove', 87],
            ['remove', 87],
            ['remove', 87],
            ['remove', 87],
            ['remove', 87],
            ['remove', 87],
            ['remove', 87],
            ['remove', 87],
            ['has', 87]]},
   [['added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     False],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
  ['wide stride item',
   {'k': 3, 'm': 14, 'ops': [['add', 187], ['add', 9], ['has', 187], ['remove', 9]]},
   [['added', 'added', True, 'removed'], [0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0]]],
  ['saturating counter',
   {'k': 2,
    'm': 14,
    'ops': [['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['remove', 4],
            ['has', 4]]},
   [['added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'removed',
     True],
    [0, 0, 0, 0, 15, 15, 0, 0, 0, 0, 0, 0, 0, 0]]],
  ['atomic removal of absent item',
   {'k': 3, 'm': 14, 'ops': [['add', 7], ['remove', 49], ['has', 7]]},
   [['added', 'absent', True], [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0]]],
  ['partial overlap membership',
   {'k': 3, 'm': 14, 'ops': [['add', 2], ['add', 16], ['has', 30], ['has', 3], ['has', 2]]},
   [['added', 'added', False, False, True], [0, 0, 2, 1, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0]]],
  ['normal add and remove',
   {'k': 2, 'm': 14, 'ops': [['add', 32], ['add', 33], ['remove', 32], ['has', 32], ['has', 33]]},
   [['added', 'added', 'removed', False, True], [0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0]]],
  ['remove absent from empty',
   {'k': 2, 'm': 14, 'ops': [['remove', 9], ['has', 9]]},
   [['absent', False], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
  ['saturated then drained',
   {'k': 1,
    'm': 14,
    'ops': [['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['has', 6]]},
   [['added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     True],
    [0, 0, 0, 0, 0, 0, 15, 0, 0, 0, 0, 0, 0, 0]]]],
 [['duplicate probe positions',
   {'k': 4,
    'm': 15,
    'ops': [['add', 63], ['add', 1], ['has', 63], ['remove', 63], ['has', 63], ['has', 1]]},
   [['added', 'added', True, 'removed', False, True],
    [0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
  ['hot item with repeated positions',
   {'k': 4,
    'm': 15,
    'ops': [['add', 63],
            ['add', 63],
            ['add', 63],
            ['add', 63],
            ['add', 63],
            ['add', 63],
            ['add', 63],
            ['add', 63],
            ['remove', 63],
            ['remove', 63],
            ['remove', 63],
            ['remove', 63],
            ['remove', 63],
            ['remove', 63],
            ['remove', 63],
            ['remove', 63],
            ['has', 63]]},
   [['added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     False],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
  ['wide stride item',
   {'k': 3, 'm': 15, 'ops': [['add', 215], ['add', 10], ['has', 215], ['remove', 10]]},
   [['added', 'added', True, 'removed'], [0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0]]],
  ['saturating counter',
   {'k': 2,
    'm': 15,
    'ops': [['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['remove', 4],
            ['has', 4]]},
   [['added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'removed',
     True],
    [0, 0, 0, 0, 15, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
  ['atomic removal of absent item',
   {'k': 3, 'm': 15, 'ops': [['add', 8], ['remove', 53], ['has', 8]]},
   [['added', 'absent', True], [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0]]],
  ['partial overlap membership',
   {'k': 3, 'm': 15, 'ops': [['add', 2], ['add', 17], ['has', 32], ['has', 3], ['has', 2]]},
   [['added', 'added', False, False, True], [0, 0, 2, 1, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]]],
  ['normal add and remove',
   {'k': 2, 'm': 15, 'ops': [['add', 33], ['add', 34], ['remove', 33], ['has', 33], ['has', 34]]},
   [['added', 'added', 'removed', False, True], [0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0]]],
  ['remove absent from empty',
   {'k': 2, 'm': 15, 'ops': [['remove', 9], ['has', 9]]},
   [['absent', False], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
  ['saturated then drained',
   {'k': 1,
    'm': 15,
    'ops': [['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['has', 6]]},
   [['added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     True],
    [0, 0, 0, 0, 0, 0, 15, 0, 0, 0, 0, 0, 0, 0, 0]]]],
 [['duplicate probe positions',
   {'k': 4,
    'm': 16,
    'ops': [['add', 115], ['add', 1], ['has', 115], ['remove', 115], ['has', 115], ['has', 1]]},
   [['added', 'added', True, 'removed', False, True],
    [0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
  ['hot item with repeated positions',
   {'k': 4,
    'm': 16,
    'ops': [['add', 115],
            ['add', 115],
            ['add', 115],
            ['add', 115],
            ['add', 115],
            ['add', 115],
            ['add', 115],
            ['add', 115],
            ['remove', 115],
            ['remove', 115],
            ['remove', 115],
            ['remove', 115],
            ['remove', 115],
            ['remove', 115],
            ['remove', 115],
            ['remove', 115],
            ['has', 115]]},
   [['added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     False],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
  ['wide stride item',
   {'k': 3, 'm': 16, 'ops': [['add', 245], ['add', 11], ['has', 245], ['remove', 11]]},
   [['added', 'added', True, 'removed'], [0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0]]],
  ['saturating counter',
   {'k': 2,
    'm': 16,
    'ops': [['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['remove', 4],
            ['has', 4]]},
   [['added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'removed',
     True],
    [0, 0, 0, 0, 15, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
  ['atomic removal of absent item',
   {'k': 3, 'm': 16, 'ops': [['add', 9], ['remove', 57], ['has', 9]]},
   [['added', 'absent', True], [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0]]],
  ['partial overlap membership',
   {'k': 3, 'm': 16, 'ops': [['add', 2], ['add', 18], ['has', 34], ['has', 3], ['has', 2]]},
   [['added', 'added', False, False, True], [0, 0, 2, 1, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
  ['normal add and remove',
   {'k': 2, 'm': 16, 'ops': [['add', 34], ['add', 35], ['remove', 34], ['has', 34], ['has', 35]]},
   [['added', 'added', 'removed', False, True], [0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
  ['remove absent from empty',
   {'k': 2, 'm': 16, 'ops': [['remove', 9], ['has', 9]]},
   [['absent', False], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
  ['saturated then drained',
   {'k': 1,
    'm': 16,
    'ops': [['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['has', 6]]},
   [['added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     True],
    [0, 0, 0, 0, 0, 0, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0]]]],
 [['duplicate probe positions',
   {'k': 4,
    'm': 18,
    'ops': [['add', 147], ['add', 1], ['has', 147], ['remove', 147], ['has', 147], ['has', 1]]},
   [['added', 'added', True, 'removed', False, True],
    [0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
  ['hot item with repeated positions',
   {'k': 4,
    'm': 18,
    'ops': [['add', 147],
            ['add', 147],
            ['add', 147],
            ['add', 147],
            ['add', 147],
            ['add', 147],
            ['add', 147],
            ['add', 147],
            ['remove', 147],
            ['remove', 147],
            ['remove', 147],
            ['remove', 147],
            ['remove', 147],
            ['remove', 147],
            ['remove', 147],
            ['remove', 147],
            ['has', 147]]},
   [['added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     False],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
  ['wide stride item',
   {'k': 3, 'm': 18, 'ops': [['add', 311], ['add', 12], ['has', 311], ['remove', 12]]},
   [['added', 'added', True, 'removed'], [0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
  ['saturating counter',
   {'k': 2,
    'm': 18,
    'ops': [['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['remove', 4],
            ['has', 4]]},
   [['added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'removed',
     True],
    [0, 0, 0, 0, 15, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
  ['atomic removal of absent item',
   {'k': 3, 'm': 18, 'ops': [['add', 10], ['remove', 64], ['has', 10]]},
   [['added', 'absent', True], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0]]],
  ['partial overlap membership',
   {'k': 3, 'm': 18, 'ops': [['add', 2], ['add', 20], ['has', 38], ['has', 3], ['has', 2]]},
   [['added', 'added', False, False, True],
    [0, 0, 2, 1, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
  ['normal add and remove',
   {'k': 2, 'm': 18, 'ops': [['add', 35], ['add', 36], ['remove', 35], ['has', 35], ['has', 36]]},
   [['added', 'added', 'removed', False, True],
    [1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
  ['remove absent from empty',
   {'k': 2, 'm': 18, 'ops': [['remove', 9], ['has', 9]]},
   [['absent', False], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
  ['saturated then drained',
   {'k': 1,
    'm': 18,
    'ops': [['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['has', 6]]},
   [['added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     True],
    [0, 0, 0, 0, 0, 0, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]]]]
for label, args, expected in cases[N - 1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(x):
    m = x['m']
    k = x['k']
    c = [0] * m
    def positions(item):
        h1 = item % m
        h2 = 1 + (item // m) % (m - 1)
        out = []
        for i in range(k):
            p = (h1 + i * h2) % m
            if p not in out:
                out.append(p)
        return out
    res = []
    for op, item in x['ops']:
        pos = positions(item)
        if op == 'add':
            for p in pos:
                if c[p] < 15:
                    c[p] = c[p] + 1
            res.append('added')
        elif op == 'remove':
            if any(c[p] == 0 for p in pos):
                res.append('absent')
                continue
            for p in pos:
                if c[p] < 15:
                    c[p] = c[p] - 1
            res.append('removed')
        else:
            res.append(sum(1 for p in pos if c[p] > 0) >= len(pos) - 1)
    return [res, c]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['duplicate probe positions',
   {'k': 4,
    'm': 12,
    'ops': [['add', 63], ['add', 1], ['has', 63], ['remove', 63], ['has', 63], ['has', 1]]},
   [['added', 'added', True, 'removed', False, True], [0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0]]],
  ['hot item with repeated positions',
   {'k': 4,
    'm': 12,
    'ops': [['add', 63],
            ['add', 63],
            ['add', 63],
            ['add', 63],
            ['add', 63],
            ['add', 63],
            ['add', 63],
            ['add', 63],
            ['remove', 63],
            ['remove', 63],
            ['remove', 63],
            ['remove', 63],
            ['remove', 63],
            ['remove', 63],
            ['remove', 63],
            ['remove', 63],
            ['has', 63]]},
   [['added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     False],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
  ['wide stride item',
   {'k': 3, 'm': 12, 'ops': [['add', 137], ['add', 8], ['has', 137], ['remove', 8]]},
   [['added', 'added', True, 'removed'], [0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0]]],
  ['saturating counter',
   {'k': 2,
    'm': 12,
    'ops': [['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['remove', 4],
            ['has', 4]]},
   [['added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'removed',
     True],
    [0, 0, 0, 0, 15, 15, 0, 0, 0, 0, 0, 0]]],
  ['atomic removal of absent item',
   {'k': 3, 'm': 12, 'ops': [['add', 6], ['remove', 42], ['has', 6]]},
   [['added', 'absent', True], [0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0]]],
  ['partial overlap membership',
   {'k': 3, 'm': 12, 'ops': [['add', 2], ['add', 14], ['has', 26], ['has', 3], ['has', 2]]},
   [['added', 'added', False, False, True], [0, 0, 2, 1, 2, 0, 1, 0, 0, 0, 0, 0]]],
  ['normal add and remove',
   {'k': 2, 'm': 12, 'ops': [['add', 31], ['add', 32], ['remove', 31], ['has', 31], ['has', 32]]},
   [['added', 'added', 'removed', False, True], [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1]]],
  ['remove absent from empty',
   {'k': 2, 'm': 12, 'ops': [['remove', 9], ['has', 9]]},
   [['absent', False], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
  ['saturated then drained',
   {'k': 1,
    'm': 12,
    'ops': [['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['has', 6]]},
   [['added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     True],
    [0, 0, 0, 0, 0, 0, 15, 0, 0, 0, 0, 0]]]],
 [['duplicate probe positions',
   {'k': 4,
    'm': 14,
    'ops': [['add', 87], ['add', 1], ['has', 87], ['remove', 87], ['has', 87], ['has', 1]]},
   [['added', 'added', True, 'removed', False, True], [0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
  ['hot item with repeated positions',
   {'k': 4,
    'm': 14,
    'ops': [['add', 87],
            ['add', 87],
            ['add', 87],
            ['add', 87],
            ['add', 87],
            ['add', 87],
            ['add', 87],
            ['add', 87],
            ['remove', 87],
            ['remove', 87],
            ['remove', 87],
            ['remove', 87],
            ['remove', 87],
            ['remove', 87],
            ['remove', 87],
            ['remove', 87],
            ['has', 87]]},
   [['added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     False],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
  ['wide stride item',
   {'k': 3, 'm': 14, 'ops': [['add', 187], ['add', 9], ['has', 187], ['remove', 9]]},
   [['added', 'added', True, 'removed'], [0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0]]],
  ['saturating counter',
   {'k': 2,
    'm': 14,
    'ops': [['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['remove', 4],
            ['has', 4]]},
   [['added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'removed',
     True],
    [0, 0, 0, 0, 15, 15, 0, 0, 0, 0, 0, 0, 0, 0]]],
  ['atomic removal of absent item',
   {'k': 3, 'm': 14, 'ops': [['add', 7], ['remove', 49], ['has', 7]]},
   [['added', 'absent', True], [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0]]],
  ['partial overlap membership',
   {'k': 3, 'm': 14, 'ops': [['add', 2], ['add', 16], ['has', 30], ['has', 3], ['has', 2]]},
   [['added', 'added', False, False, True], [0, 0, 2, 1, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0]]],
  ['normal add and remove',
   {'k': 2, 'm': 14, 'ops': [['add', 32], ['add', 33], ['remove', 32], ['has', 32], ['has', 33]]},
   [['added', 'added', 'removed', False, True], [0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0]]],
  ['remove absent from empty',
   {'k': 2, 'm': 14, 'ops': [['remove', 9], ['has', 9]]},
   [['absent', False], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
  ['saturated then drained',
   {'k': 1,
    'm': 14,
    'ops': [['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['has', 6]]},
   [['added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     True],
    [0, 0, 0, 0, 0, 0, 15, 0, 0, 0, 0, 0, 0, 0]]]],
 [['duplicate probe positions',
   {'k': 4,
    'm': 15,
    'ops': [['add', 63], ['add', 1], ['has', 63], ['remove', 63], ['has', 63], ['has', 1]]},
   [['added', 'added', True, 'removed', False, True],
    [0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
  ['hot item with repeated positions',
   {'k': 4,
    'm': 15,
    'ops': [['add', 63],
            ['add', 63],
            ['add', 63],
            ['add', 63],
            ['add', 63],
            ['add', 63],
            ['add', 63],
            ['add', 63],
            ['remove', 63],
            ['remove', 63],
            ['remove', 63],
            ['remove', 63],
            ['remove', 63],
            ['remove', 63],
            ['remove', 63],
            ['remove', 63],
            ['has', 63]]},
   [['added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     False],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
  ['wide stride item',
   {'k': 3, 'm': 15, 'ops': [['add', 215], ['add', 10], ['has', 215], ['remove', 10]]},
   [['added', 'added', True, 'removed'], [0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0]]],
  ['saturating counter',
   {'k': 2,
    'm': 15,
    'ops': [['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['remove', 4],
            ['has', 4]]},
   [['added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'removed',
     True],
    [0, 0, 0, 0, 15, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
  ['atomic removal of absent item',
   {'k': 3, 'm': 15, 'ops': [['add', 8], ['remove', 53], ['has', 8]]},
   [['added', 'absent', True], [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0]]],
  ['partial overlap membership',
   {'k': 3, 'm': 15, 'ops': [['add', 2], ['add', 17], ['has', 32], ['has', 3], ['has', 2]]},
   [['added', 'added', False, False, True], [0, 0, 2, 1, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]]],
  ['normal add and remove',
   {'k': 2, 'm': 15, 'ops': [['add', 33], ['add', 34], ['remove', 33], ['has', 33], ['has', 34]]},
   [['added', 'added', 'removed', False, True], [0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0]]],
  ['remove absent from empty',
   {'k': 2, 'm': 15, 'ops': [['remove', 9], ['has', 9]]},
   [['absent', False], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
  ['saturated then drained',
   {'k': 1,
    'm': 15,
    'ops': [['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['has', 6]]},
   [['added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     True],
    [0, 0, 0, 0, 0, 0, 15, 0, 0, 0, 0, 0, 0, 0, 0]]]],
 [['duplicate probe positions',
   {'k': 4,
    'm': 16,
    'ops': [['add', 115], ['add', 1], ['has', 115], ['remove', 115], ['has', 115], ['has', 1]]},
   [['added', 'added', True, 'removed', False, True],
    [0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
  ['hot item with repeated positions',
   {'k': 4,
    'm': 16,
    'ops': [['add', 115],
            ['add', 115],
            ['add', 115],
            ['add', 115],
            ['add', 115],
            ['add', 115],
            ['add', 115],
            ['add', 115],
            ['remove', 115],
            ['remove', 115],
            ['remove', 115],
            ['remove', 115],
            ['remove', 115],
            ['remove', 115],
            ['remove', 115],
            ['remove', 115],
            ['has', 115]]},
   [['added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     False],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
  ['wide stride item',
   {'k': 3, 'm': 16, 'ops': [['add', 245], ['add', 11], ['has', 245], ['remove', 11]]},
   [['added', 'added', True, 'removed'], [0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0]]],
  ['saturating counter',
   {'k': 2,
    'm': 16,
    'ops': [['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['remove', 4],
            ['has', 4]]},
   [['added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'removed',
     True],
    [0, 0, 0, 0, 15, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
  ['atomic removal of absent item',
   {'k': 3, 'm': 16, 'ops': [['add', 9], ['remove', 57], ['has', 9]]},
   [['added', 'absent', True], [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0]]],
  ['partial overlap membership',
   {'k': 3, 'm': 16, 'ops': [['add', 2], ['add', 18], ['has', 34], ['has', 3], ['has', 2]]},
   [['added', 'added', False, False, True], [0, 0, 2, 1, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
  ['normal add and remove',
   {'k': 2, 'm': 16, 'ops': [['add', 34], ['add', 35], ['remove', 34], ['has', 34], ['has', 35]]},
   [['added', 'added', 'removed', False, True], [0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
  ['remove absent from empty',
   {'k': 2, 'm': 16, 'ops': [['remove', 9], ['has', 9]]},
   [['absent', False], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
  ['saturated then drained',
   {'k': 1,
    'm': 16,
    'ops': [['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['has', 6]]},
   [['added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     True],
    [0, 0, 0, 0, 0, 0, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0]]]],
 [['duplicate probe positions',
   {'k': 4,
    'm': 18,
    'ops': [['add', 147], ['add', 1], ['has', 147], ['remove', 147], ['has', 147], ['has', 1]]},
   [['added', 'added', True, 'removed', False, True],
    [0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
  ['hot item with repeated positions',
   {'k': 4,
    'm': 18,
    'ops': [['add', 147],
            ['add', 147],
            ['add', 147],
            ['add', 147],
            ['add', 147],
            ['add', 147],
            ['add', 147],
            ['add', 147],
            ['remove', 147],
            ['remove', 147],
            ['remove', 147],
            ['remove', 147],
            ['remove', 147],
            ['remove', 147],
            ['remove', 147],
            ['remove', 147],
            ['has', 147]]},
   [['added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     False],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
  ['wide stride item',
   {'k': 3, 'm': 18, 'ops': [['add', 311], ['add', 12], ['has', 311], ['remove', 12]]},
   [['added', 'added', True, 'removed'], [0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
  ['saturating counter',
   {'k': 2,
    'm': 18,
    'ops': [['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['add', 4],
            ['remove', 4],
            ['has', 4]]},
   [['added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'removed',
     True],
    [0, 0, 0, 0, 15, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
  ['atomic removal of absent item',
   {'k': 3, 'm': 18, 'ops': [['add', 10], ['remove', 64], ['has', 10]]},
   [['added', 'absent', True], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0]]],
  ['partial overlap membership',
   {'k': 3, 'm': 18, 'ops': [['add', 2], ['add', 20], ['has', 38], ['has', 3], ['has', 2]]},
   [['added', 'added', False, False, True],
    [0, 0, 2, 1, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
  ['normal add and remove',
   {'k': 2, 'm': 18, 'ops': [['add', 35], ['add', 36], ['remove', 35], ['has', 35], ['has', 36]]},
   [['added', 'added', 'removed', False, True],
    [1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
  ['remove absent from empty',
   {'k': 2, 'm': 18, 'ops': [['remove', 9], ['has', 9]]},
   [['absent', False], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]],
  ['saturated then drained',
   {'k': 1,
    'm': 18,
    'ops': [['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['add', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['remove', 6],
            ['has', 6]]},
   [['added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'added',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     'removed',
     True],
    [0, 0, 0, 0, 0, 0, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]]]]
for label, args, expected in cases[N - 1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
Items sharing only one counter with a stored item are reported present.

Input {m, k, ops}; items are pre-hashed non-negative integers. Positions are the distinct values of (h1 + i*h2) mod m for i in 0..k-1 with h1 = item mod m and h2 = 1 + (item div m) mod (m-1), in first-seen order. add increments each distinct position once, saturating at 15. A saturated counter is sticky: remove never decrements it. remove is atomic: if any position is zero the result is "absent" and nothing changes; otherwise it decrements every non-saturated position. has requires every position to be positive. Return [results, counters].

split: open-access


meaning: Fixture-count band, not measured model difficulty

deps: stdlib

prompt:
Registers are indexed by bits that also feed the rank, correlating index and rho and biasing the estimate.

Input {p, hashes}. Each hash is reduced to its low 32 bits. The register index is the top p bits; the remaining 32-p bits, left-aligned in a 32-bit word, give rho = leading zeros + 1, and an all-zero remainder gives rho = 32 - p + 1. Each register keeps the maximum rho seen. Return the list of 2^p registers.

split: open-access


prompt:
Ranks come out too small (even zero or negative) because index bits remain above the word.

Input {p, hashes}. Each hash is reduced to its low 32 bits. The register index is the top p bits; the remaining 32-p bits, left-aligned in a 32-bit word, give rho = leading zeros + 1, and an all-zero remainder gives rho = 32 - p + 1. Each register keeps the maximum rho seen. Return the list of 2^p registers.

split: open-access


prompt:
A hash whose remainder is zero stores a rank larger than any valid value for the precision.

Input {p, hashes}. Each hash is reduced to its low 32 bits. The register index is the top p bits; the remaining 32-p bits, left-aligned in a 32-bit word, give rho = leading zeros + 1, and an all-zero remainder gives rho = 32 - p + 1. Each register keeps the maximum rho seen. Return the list of 2^p registers.

split: open-access


prompt:
A later small rank erases the maximum, making estimates depend on arrival order.

Input {p, hashes}. Each hash is reduced to its low 32 bits. The register index is the top p bits; the remaining 32-p bits, left-aligned in a 32-bit word, give rho = leading zeros + 1, and an all-zero remainder gives rho = 32 - p + 1. Each register keeps the maximum rho seen. Return the list of 2^p registers.

split: open-access


prompt:
Every register is one lower, shrinking the estimate by about half.

Input {p, hashes}. Each hash is reduced to its low 32 bits. The register index is the top p bits; the remaining 32-p bits, left-aligned in a 32-bit word, give rho = leading zeros + 1, and an all-zero remainder gives rho = 32 - p + 1. Each register keeps the maximum rho seen. Return the list of 2^p registers.

split: open-access


prompt:
A port that stores hashes in signed 32-bit integers never uses the upper half of the registers.

Input {p, hashes}. Each hash is reduced to its low 32 bits. The register index is the top p bits; the remaining 32-p bits, left-aligned in a 32-bit word, give rho = leading zeros + 1, and an all-zero remainder gives rho = 32 - p + 1. Each register keeps the maximum rho seen. Return the list of 2^p registers.

split: open-access


prompt:
Estimates for 16, 32 and 64 registers are biased by the asymptotic constant.

Input {regs} with 16, 32, 64 or 128 registers. alpha is 0.673, 0.697, 0.709 for m = 16, 32, 64 and 0.7213/(1 + 1.079/m) otherwise. Raw E = alpha m^2 / sum 2^-r. If E <= 2.5m and V (zero registers) > 0, use linear counting m ln(m/V); otherwise if E > 2^32/30 apply the large-range correction -2^32 ln(1 - E/2^32). Return [round(E), V].

split: open-access


prompt:
Raw estimates explode for sparse sketches because empty registers no longer contribute 1 each.

Input {regs} with 16, 32, 64 or 128 registers. alpha is 0.673, 0.697, 0.709 for m = 16, 32, 64 and 0.7213/(1 + 1.079/m) otherwise. Raw E = alpha m^2 / sum 2^-r. If E <= 2.5m and V (zero registers) > 0, use linear counting m ln(m/V); otherwise if E > 2^32/30 apply the large-range correction -2^32 ln(1 - E/2^32). Return [round(E), V].

split: open-access


prompt:
Small cardinalities are estimated from the wrong register population.

Input {regs} with 16, 32, 64 or 128 registers. alpha is 0.673, 0.697, 0.709 for m = 16, 32, 64 and 0.7213/(1 + 1.079/m) otherwise. Raw E = alpha m^2 / sum 2^-r. If E <= 2.5m and V (zero registers) > 0, use linear counting m ln(m/V); otherwise if E > 2^32/30 apply the large-range correction -2^32 ln(1 - E/2^32). Return [round(E), V].

split: open-access


prompt:
A sketch with no empty registers is forced through linear counting with a fake empty register.

Input {regs} with 16, 32, 64 or 128 registers. alpha is 0.673, 0.697, 0.709 for m = 16, 32, 64 and 0.7213/(1 + 1.079/m) otherwise. Raw E = alpha m^2 / sum 2^-r. If E <= 2.5m and V (zero registers) > 0, use linear counting m ln(m/V); otherwise if E > 2^32/30 apply the large-range correction -2^32 ln(1 - E/2^32). Return [round(E), V].

split: open-access


prompt:
Very large cardinalities are underestimated because hash collisions are never corrected.

Input {regs} with 16, 32, 64 or 128 registers. alpha is 0.673, 0.697, 0.709 for m = 16, 32, 64 and 0.7213/(1 + 1.079/m) otherwise. Raw E = alpha m^2 / sum 2^-r. If E <= 2.5m and V (zero registers) > 0, use linear counting m ln(m/V); otherwise if E > 2^32/30 apply the large-range correction -2^32 ln(1 - E/2^32). Return [round(E), V].

split: open-access


prompt:
Reported counts are systematically one lower whenever the fractional part is at least one half.

Input {regs} with 16, 32, 64 or 128 registers. alpha is 0.673, 0.697, 0.709 for m = 16, 32, 64 and 0.7213/(1 + 1.079/m) otherwise. Raw E = alpha m^2 / sum 2^-r. If E <= 2.5m and V (zero registers) > 0, use linear counting m ln(m/V); otherwise if E > 2^32/30 apply the large-range correction -2^32 ln(1 - E/2^32). Return [round(E), V].

split: open-access


prompt:
The folded sketch underestimates because moved index bits are not credited to the rank.

Input {a, b}, each {p, regs}. Both sketches are folded to q = min precision. Folding from p to q with d = p - q maps register j to j >> d; if the low d bits of j are non-zero they become the leading bits of the new remainder, giving rank d - bitlen(low) + 1, otherwise the rank is r + d. Empty registers contribute nothing. The merged sketch is the element-wise maximum. Return [q, regs].

split: open-access


prompt:
Registers are merged into slots that the lower-precision sketch would never have chosen.

Input {a, b}, each {p, regs}. Both sketches are folded to q = min precision. Folding from p to q with d = p - q maps register j to j >> d; if the low d bits of j are non-zero they become the leading bits of the new remainder, giving rank d - bitlen(low) + 1, otherwise the rank is r + d. Empty registers contribute nothing. The merged sketch is the element-wise maximum. Return [q, regs].

split: open-access


prompt:
Folded ranks grow with the value of displaced bits rather than with leading zeros.

Input {a, b}, each {p, regs}. Both sketches are folded to q = min precision. Folding from p to q with d = p - q maps register j to j >> d; if the low d bits of j are non-zero they become the leading bits of the new remainder, giving rank d - bitlen(low) + 1, otherwise the rank is r + d. Empty registers contribute nothing. The merged sketch is the element-wise maximum. Return [q, regs].

split: open-access


prompt:
Registers that never saw a hash contribute non-zero ranks after folding, inflating the estimate.

Input {a, b}, each {p, regs}. Both sketches are folded to q = min precision. Folding from p to q with d = p - q maps register j to j >> d; if the low d bits of j are non-zero they become the leading bits of the new remainder, giving rank d - bitlen(low) + 1, otherwise the rank is r + d. Empty registers contribute nothing. The merged sketch is the element-wise maximum. Return [q, regs].

split: open-access


prompt:
Merged ranks exceed any rank either stream could produce, massively overestimating the union.

Input {a, b}, each {p, regs}. Both sketches are folded to q = min precision. Folding from p to q with d = p - q maps register j to j >> d; if the low d bits of j are non-zero they become the leading bits of the new remainder, giving rank d - bitlen(low) + 1, otherwise the rank is r + d. Empty registers contribute nothing. The merged sketch is the element-wise maximum. Return [q, regs].

split: open-access


prompt:
Cells already inflated by other keys are lowered to this key's target, so other keys become underestimated.

Input {w, d, ops}. Row r hashes key to ((A_r*key + B_r) mod 2^31-1) mod w with fixed A and B. add with count <= 0 is "rejected" (conservative update cannot represent deletions). Otherwise the current estimate e is the minimum of the key's cells, and each cell is raised to max(cell, e + count). The stream total counts accepted mass and the overestimate bound is ceil(e/w * total). q returns the minimum of the key's cells. Return [results, total, bound, table].

split: open-access


prompt:
Early rows are raised from a partial minimum, overestimating keys whose smallest cell is in a later row.

Input {w, d, ops}. Row r hashes key to ((A_r*key + B_r) mod 2^31-1) mod w with fixed A and B. add with count <= 0 is "rejected" (conservative update cannot represent deletions). Otherwise the current estimate e is the minimum of the key's cells, and each cell is raised to max(cell, e + count). The stream total counts accepted mass and the overestimate bound is ceil(e/w * total). q returns the minimum of the key's cells. Return [results, total, bound, table].

split: open-access


prompt:
Deletions are acknowledged although conservative cells cannot decrease, and the stream total drifts.

Input {w, d, ops}. Row r hashes key to ((A_r*key + B_r) mod 2^31-1) mod w with fixed A and B. add with count <= 0 is "rejected" (conservative update cannot represent deletions). Otherwise the current estimate e is the minimum of the key's cells, and each cell is raised to max(cell, e + count). The stream total counts accepted mass and the overestimate bound is ceil(e/w * total). q returns the minimum of the key's cells. Return [results, total, bound, table].

split: open-access


prompt:
Callers trust estimates to be within a bound that Count-Min does not guarantee.

Input {w, d, ops}. Row r hashes key to ((A_r*key + B_r) mod 2^31-1) mod w with fixed A and B. add with count <= 0 is "rejected" (conservative update cannot represent deletions). Otherwise the current estimate e is the minimum of the key's cells, and each cell is raised to max(cell, e + count). The stream total counts accepted mass and the overestimate bound is ceil(e/w * total). q returns the minimum of the key's cells. Return [results, total, bound, table].

split: open-access


prompt:
Large keys land in buckets that differ from other nodes using the specified hash family.

Input {w, d, ops}. Row r hashes key to ((A_r*key + B_r) mod 2^31-1) mod w with fixed A and B. add with count <= 0 is "rejected" (conservative update cannot represent deletions). Otherwise the current estimate e is the minimum of the key's cells, and each cell is raised to max(cell, e + count). The stream total counts accepted mass and the overestimate bound is ceil(e/w * total). q returns the minimum of the key's cells. Return [results, total, bound, table].

split: open-access


prompt:
Rows where the key was stored with a negative sign vote with the wrong polarity.

Input {w, d, stream, queries}; stream entries are [key, signed count]. Row r uses bucket ((A_r key + B_r) mod 2^31-1) mod w and sign +1 when ((C_r key + D_r) mod 2^31-1) is odd, else -1, from an independent hash. Updates add sign*count. A query returns the median over rows of sign*cell; for even d the median is the mean of the two middle values. Negative estimates are returned unchanged (turnstile streams).

split: open-access


prompt:
Keys sharing a bucket also share a sign more often, so collisions no longer cancel in expectation.

Input {w, d, stream, queries}; stream entries are [key, signed count]. Row r uses bucket ((A_r key + B_r) mod 2^31-1) mod w and sign +1 when ((C_r key + D_r) mod 2^31-1) is odd, else -1, from an independent hash. Updates add sign*count. A query returns the median over rows of sign*cell; for even d the median is the mean of the two middle values. Negative estimates are returned unchanged (turnstile streams).

split: open-access


prompt:
A single heavily colliding row skews the estimate instead of being outvoted.

Input {w, d, stream, queries}; stream entries are [key, signed count]. Row r uses bucket ((A_r key + B_r) mod 2^31-1) mod w and sign +1 when ((C_r key + D_r) mod 2^31-1) is odd, else -1, from an independent hash. Updates add sign*count. A query returns the median over rows of sign*cell; for even d the median is the mean of the two middle values. Negative estimates are returned unchanged (turnstile streams).

split: open-access


prompt:
Sketches with an even number of rows systematically underestimate.

Input {w, d, stream, queries}; stream entries are [key, signed count]. Row r uses bucket ((A_r key + B_r) mod 2^31-1) mod w and sign +1 when ((C_r key + D_r) mod 2^31-1) is odd, else -1, from an independent hash. Updates add sign*count. A query returns the median over rows of sign*cell; for even d the median is the mean of the two middle values. Negative estimates are returned unchanged (turnstile streams).

split: open-access


prompt:
Colliding keys accumulate instead of cancelling, and queries multiply unsigned cells by a sign.

Input {w, d, stream, queries}; stream entries are [key, signed count]. Row r uses bucket ((A_r key + B_r) mod 2^31-1) mod w and sign +1 when ((C_r key + D_r) mod 2^31-1) is odd, else -1, from an independent hash. Updates add sign*count. A query returns the median over rows of sign*cell; for even d the median is the mean of the two middle values. Negative estimates are returned unchanged (turnstile streams).

split: open-access


prompt:
Counters exceed the true frequency and the error guarantee no longer holds.

Input {k, stream} of [item, positive weight]. Keep at most k counters. A tracked item adds its weight; an untracked item takes a free counter. Otherwise dec = min(smallest counter, weight) is subtracted from every counter and from the incoming weight, counters reaching 0 are dropped, and a positive remainder is inserted. removed accumulates dec*(k+1), the discarded mass. Return [sorted [item, count] pairs, removed].

split: open-access


prompt:
Zero counters occupy slots, so later items keep triggering decrements instead of being tracked.

Input {k, stream} of [item, positive weight]. Keep at most k counters. A tracked item adds its weight; an untracked item takes a free counter. Otherwise dec = min(smallest counter, weight) is subtracted from every counter and from the incoming weight, counters reaching 0 are dropped, and a positive remainder is inserted. removed accumulates dec*(k+1), the discarded mass. Return [sorted [item, count] pairs, removed].

split: open-access


prompt:
A heavy newcomer loses only one unit and stale counters linger, violating the weighted algorithm.

Input {k, stream} of [item, positive weight]. Keep at most k counters. A tracked item adds its weight; an untracked item takes a free counter. Otherwise dec = min(smallest counter, weight) is subtracted from every counter and from the incoming weight, counters reaching 0 are dropped, and a positive remainder is inserted. removed accumulates dec*(k+1), the discarded mass. Return [sorted [item, count] pairs, removed].

split: open-access


prompt:
The reported error bound is smaller than the mass actually discarded.

Input {k, stream} of [item, positive weight]. Keep at most k counters. A tracked item adds its weight; an untracked item takes a free counter. Otherwise dec = min(smallest counter, weight) is subtracted from every counter and from the incoming weight, counters reaching 0 are dropped, and a positive remainder is inserted. removed accumulates dec*(k+1), the discarded mass. Return [sorted [item, count] pairs, removed].

split: open-access


prompt:
The summary holds k+1 counters, exceeding its memory budget and changing every later decrement.

Input {k, stream} of [item, positive weight]. Keep at most k counters. A tracked item adds its weight; an untracked item takes a free counter. Otherwise dec = min(smallest counter, weight) is subtracted from every counter and from the incoming weight, counters reaching 0 are dropped, and a positive remainder is inserted. removed accumulates dec*(k+1), the discarded mass. Return [sorted [item, count] pairs, removed].

split: open-access


prompt:
Evicted mass disappears, so counts underestimate and the overestimate-only property is lost.

Input {k, stream, phi=[num, den]}. Keep k entries [count, error, last-touch tick]. A hit increments count and refreshes the tick. A miss with free space inserts [1, 0, tick]. Otherwise evict the entry with the smallest count, ties broken by the oldest tick, and insert the newcomer with count = victim count + 1 and error = victim count. Return [rows sorted by count descending then item, sorted items whose guaranteed count (count - error) exceeds phi * stream length].

split: open-access


prompt:
Newcomers look like guaranteed heavy hitters although their count is mostly inherited.

Input {k, stream, phi=[num, den]}. Keep k entries [count, error, last-touch tick]. A hit increments count and refreshes the tick. A miss with free space inserts [1, 0, tick]. Otherwise evict the entry with the smallest count, ties broken by the oldest tick, and insert the newcomer with count = victim count + 1 and error = victim count. Return [rows sorted by count descending then item, sorted items whose guaranteed count (count - error) exceeds phi * stream length].

split: open-access


prompt:
A burst of distinct items keeps replacing the newest entry, churning the summary.

Input {k, stream, phi=[num, den]}. Keep k entries [count, error, last-touch tick]. A hit increments count and refreshes the tick. A miss with free space inserts [1, 0, tick]. Otherwise evict the entry with the smallest count, ties broken by the oldest tick, and insert the newcomer with count = victim count + 1 and error = victim count. Return [rows sorted by count descending then item, sorted items whose guaranteed count (count - error) exceeds phi * stream length].

split: open-access


prompt:
Recently active entries are evicted as if they were stale.

Input {k, stream, phi=[num, den]}. Keep k entries [count, error, last-touch tick]. A hit increments count and refreshes the tick. A miss with free space inserts [1, 0, tick]. Otherwise evict the entry with the smallest count, ties broken by the oldest tick, and insert the newcomer with count = victim count + 1 and error = victim count. Return [rows sorted by count descending then item, sorted items whose guaranteed count (count - error) exceeds phi * stream length].

split: open-access


prompt:
Items whose count is mostly inherited error are reported as guaranteed heavy hitters.

Input {k, stream, phi=[num, den]}. Keep k entries [count, error, last-touch tick]. A hit increments count and refreshes the tick. A miss with free space inserts [1, 0, tick]. Otherwise evict the entry with the smallest count, ties broken by the oldest tick, and insert the newcomer with count = victim count + 1 and error = victim count. Return [rows sorted by count descending then item, sorted items whose guaranteed count (count - error) exceeds phi * stream length].

split: open-access


prompt:
Top-k reports with tied counts are ordered inconsistently between runs with different arrival orders.

Input {k, stream, phi=[num, den]}. Keep k entries [count, error, last-touch tick]. A hit increments count and refreshes the tick. A miss with free space inserts [1, 0, tick]. Otherwise evict the entry with the smallest count, ties broken by the oldest tick, and insert the newcomer with count = victim count + 1 and error = victim count. Return [rows sorted by count descending then item, sorted items whose guaranteed count (count - error) exceeds phi * stream length].

split: open-access


prompt:
Later items are over-sampled because the acceptance probability is k/i instead of k/(i+1).

Input {k, items, draws}. The first k items fill the reservoir. For 0-based index i >= k the draw draws[i - k] gives j = draw mod (i + 1); when j < k slot j is replaced. Exactly one draw is consumed per item after the fill phase. Return the reservoir.

split: open-access


prompt:
The sampler skips the first k draws, so a replayed sample does not match the recorded random tape.

Input {k, items, draws}. The first k items fill the reservoir. For 0-based index i >= k the draw draws[i - k] gives j = draw mod (i + 1); when j < k slot j is replaced. Exactly one draw is consumed per item after the fill phase. Return the reservoir.

split: open-access


prompt:
The reservoir behaves like a FIFO window, over-representing recent items.

Input {k, items, draws}. The first k items fill the reservoir. For 0-based index i >= k the draw draws[i - k] gives j = draw mod (i + 1); when j < k slot j is replaced. Exactly one draw is consumed per item after the fill phase. Return the reservoir.

split: open-access


prompt:
Rejected items do not consume randomness, so later decisions reuse the same draw.

Input {k, items, draws}. The first k items fill the reservoir. For 0-based index i >= k the draw draws[i - k] gives j = draw mod (i + 1); when j < k slot j is replaced. Exactly one draw is consumed per item after the fill phase. Return the reservoir.

split: open-access


prompt:
Heavier items receive smaller keys and are sampled less often than light ones.

Input {k, items} where each item is [id, weight, num, den] with u = num/den in (0,1). Items with weight <= 0 are ineligible. Each eligible item gets key u^(1/weight), compared as ln(u)/weight. Return the ids of the k largest keys, largest first, ties broken by smaller id.

split: open-access


prompt:
The sample favours the lightest items.

Input {k, items} where each item is [id, weight, num, den] with u = num/den in (0,1). Items with weight <= 0 are ineligible. Each eligible item gets key u^(1/weight), compared as ln(u)/weight. Return the ids of the k largest keys, largest first, ties broken by smaller id.

split: open-access


prompt:
An item with negative weight gets a key above every legitimate item and is always sampled.

Input {k, items} where each item is [id, weight, num, den] with u = num/den in (0,1). Items with weight <= 0 are ineligible. Each eligible item gets key u^(1/weight), compared as ln(u)/weight. Return the ids of the k largest keys, largest first, ties broken by smaller id.

split: open-access


prompt:
Equal keys resolve differently from the contract, making replays disagree.

Input {k, items} where each item is [id, weight, num, den] with u = num/den in (0,1). Items with weight <= 0 are ineligible. Each eligible item gets key u^(1/weight), compared as ln(u)/weight. Return the ids of the k largest keys, largest first, ties broken by smaller id.

split: open-access


prompt:
Every signature component comes from the same element, so the estimate is 0 or 1.

Input {k, A, B} integer sets. Signature component i is min over v of (A_i v + B_i) mod 2^31-1 with fixed coefficients. The estimate is the fraction of positions where both signatures agree, rounded to 4 decimals. Two empty sets have undefined similarity (None, with empty signatures); exactly one empty set gives 0.0. Return [sigA, sigB, estimate].

split: open-access


prompt:
Empty documents are reported as maximally dissimilar instead of undefined.

Input {k, A, B} integer sets. Signature component i is min over v of (A_i v + B_i) mod 2^31-1 with fixed coefficients. The estimate is the fraction of positions where both signatures agree, rounded to 4 decimals. Two empty sets have undefined similarity (None, with empty signatures); exactly one empty set gives 0.0. Return [sigA, sigB, estimate].

split: open-access


prompt:
Similarity estimates are systematically deflated for partially overlapping sets.

Input {k, A, B} integer sets. Signature component i is min over v of (A_i v + B_i) mod 2^31-1 with fixed coefficients. The estimate is the fraction of positions where both signatures agree, rounded to 4 decimals. Two empty sets have undefined similarity (None, with empty signatures); exactly one empty set gives 0.0. Return [sigA, sigB, estimate].

split: open-access


prompt:
Signature values exceed the field and disagree with producers that reduce the full expression.

Input {k, A, B} integer sets. Signature component i is min over v of (A_i v + B_i) mod 2^31-1 with fixed coefficients. The estimate is the fraction of positions where both signatures agree, rounded to 4 decimals. Two empty sets have undefined similarity (None, with empty signatures); exactly one empty set gives 0.0. Return [sigA, sigB, estimate].

split: open-access


prompt:
A document compared with an empty one is treated as undefined instead of disjoint.

Input {k, A, B} integer sets. Signature component i is min over v of (A_i v + B_i) mod 2^31-1 with fixed coefficients. The estimate is the fraction of positions where both signatures agree, rounded to 4 decimals. Two empty sets have undefined similarity (None, with empty signatures); exactly one empty set gives 0.0. Return [sigA, sigB, estimate].

split: open-access


prompt:
Two signatures that agree on different bands are paired although no band matches.

Input {b, r, sigs} with sigs a list of [id, signature]. Every signature must have exactly b*r components, otherwise "invalid". Band i covers components i*r .. i*r+r-1 and hashes to the key (i, band tuple). Ids sharing any band key form a candidate pair [smaller, larger], reported once, sorted. Also return the similarity threshold (1/b)^(1/r) rounded to 3 decimals.

split: open-access


prompt:
Band boundaries shift whenever b differs from r, so candidate pairs change.

Input {b, r, sigs} with sigs a list of [id, signature]. Every signature must have exactly b*r components, otherwise "invalid". Band i covers components i*r .. i*r+r-1 and hashes to the key (i, band tuple). Ids sharing any band key form a candidate pair [smaller, larger], reported once, sorted. Also return the similarity threshold (1/b)^(1/r) rounded to 3 decimals.

split: open-access


prompt:
Signatures produced with a different hash count are compared on a prefix instead of being rejected.

Input {b, r, sigs} with sigs a list of [id, signature]. Every signature must have exactly b*r components, otherwise "invalid". Band i covers components i*r .. i*r+r-1 and hashes to the key (i, band tuple). Ids sharing any band key form a candidate pair [smaller, larger], reported once, sorted. Also return the similarity threshold (1/b)^(1/r) rounded to 3 decimals.

split: open-access


prompt:
Operators tune b and r against a threshold that describes a different S-curve.

Input {b, r, sigs} with sigs a list of [id, signature]. Every signature must have exactly b*r components, otherwise "invalid". Band i covers components i*r .. i*r+r-1 and hashes to the key (i, band tuple). Ids sharing any band key form a candidate pair [smaller, larger], reported once, sorted. Also return the similarity threshold (1/b)^(1/r) rounded to 3 decimals.

split: open-access


prompt:
The verifier compares every candidate twice, once per ordering.

Input {b, r, sigs} with sigs a list of [id, signature]. Every signature must have exactly b*r components, otherwise "invalid". Band i covers components i*r .. i*r+r-1 and hashes to the key (i, band tuple). Ids sharing any band key form a candidate pair [smaller, larger], reported once, sorted. Also return the similarity threshold (1/b)^(1/r) rounded to 3 decimals.

split: open-access


prompt:
A stream that repeats one small hash looks like it has few distinct values beyond it, inflating the estimate.

Input {k, a, b} lists of 32-bit hashes. Each sketch keeps the k smallest distinct hashes. With fewer than k kept values the count is exact (their number); otherwise the estimate is round((k-1) * 2^32 / v_k) with v_k the k-th smallest. The union sketch is the k smallest distinct values of both kept sets. The intersection is exact when the union has fewer than k values, else round(c/k * union estimate) where c counts union-sketch values kept by both inputs. Return [estA, estB, estUnion, estIntersection].

split: open-access


prompt:
Distinct counts are biased upward by a factor k/(k-1).

Input {k, a, b} lists of 32-bit hashes. Each sketch keeps the k smallest distinct hashes. With fewer than k kept values the count is exact (their number); otherwise the estimate is round((k-1) * 2^32 / v_k) with v_k the k-th smallest. The union sketch is the k smallest distinct values of both kept sets. The intersection is exact when the union has fewer than k values, else round(c/k * union estimate) where c counts union-sketch values kept by both inputs. Return [estA, estB, estUnion, estIntersection].

split: open-access


prompt:
A sketch holding exactly k values reports k, although the true distinct count may be far larger.

Input {k, a, b} lists of 32-bit hashes. Each sketch keeps the k smallest distinct hashes. With fewer than k kept values the count is exact (their number); otherwise the estimate is round((k-1) * 2^32 / v_k) with v_k the k-th smallest. The union sketch is the k smallest distinct values of both kept sets. The intersection is exact when the union has fewer than k values, else round(c/k * union estimate) where c counts union-sketch values kept by both inputs. Return [estA, estB, estUnion, estIntersection].

split: open-access


prompt:
Values present in both sketches occupy two union slots, overstating the union and its overlap.

Input {k, a, b} lists of 32-bit hashes. Each sketch keeps the k smallest distinct hashes. With fewer than k kept values the count is exact (their number); otherwise the estimate is round((k-1) * 2^32 / v_k) with v_k the k-th smallest. The union sketch is the k smallest distinct values of both kept sets. The intersection is exact when the union has fewer than k values, else round(c/k * union estimate) where c counts union-sketch values kept by both inputs. Return [estA, estB, estUnion, estIntersection].

split: open-access


prompt:
Shared values larger than the union's k-th value inflate the intersection estimate.

Input {k, a, b} lists of 32-bit hashes. Each sketch keeps the k smallest distinct hashes. With fewer than k kept values the count is exact (their number); otherwise the estimate is round((k-1) * 2^32 / v_k) with v_k the k-th smallest. The union sketch is the k smallest distinct values of both kept sets. The intersection is exact when the union has fewer than k values, else round(c/k * union estimate) where c counts union-sketch values kept by both inputs. Return [estA, estB, estUnion, estIntersection].

split: open-access


prompt:
Intersection estimates are biased down by up to one.

Input {k, a, b} lists of 32-bit hashes. Each sketch keeps the k smallest distinct hashes. With fewer than k kept values the count is exact (their number); otherwise the estimate is round((k-1) * 2^32 / v_k) with v_k the k-th smallest. The union sketch is the k smallest distinct values of both kept sets. The intersection is exact when the union has fewer than k values, else round(c/k * union estimate) where c counts union-sketch values kept by both inputs. Return [estA, estB, estUnion, estIntersection].

split: open-access