{"abstract":"Boxes crossing on x far apart in y create contacts.","category":"Collision detection broadphase","checks":8,"contract":"solve(prev, curr): incremental sweep-and-prune on x. Endpoints [x, 0=min/1=max, id] of prev are sorted, refreshed with curr coordinates and insertion-sorted by (x, kind). Each swap where a min passes left over a max begins a pair (if y overlaps in curr); a max passing left over a min ends a pair. Return [sorted begin pairs, sorted end pairs, swap count], pairs as [min,max].","evaluation_group":"w2-collision_detection_broadphase-incremental-sap-swaps","failed_approach":"Checking one side of the y interval still admits separated boxes.","family":"w2-collision_detection_broadphase-incremental-sap-swaps-begin-secondary-check","id":"FA-87791","implementations":{"attempt":{"sha256":"c764b74c6f8f3fa71036472c897b4d74435951f66e2c5c4e7b06893cb271248c","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nimport math\nN = 1\nobservations = []\ndef solve(prev, curr):\n    old = {b[0]: b for b in prev}\n    new = {b[0]: b for b in curr}\n    E = []\n    for i, b in old.items():\n        E.append([b[1], 0, i])\n        E.append([b[3], 1, i])\n    E.sort()\n    for e in E:\n        b = new[e[2]]\n        e[0] = b[1] if e[1] == 0 else b[3]\n    def yover(a, c):\n        return new[a][2] <= new[c][4] and new[c][2] <= new[a][4]\n    begins, ends = set(), set()\n    swaps = 0\n    for i in range(1, len(E)):\n        j = i\n        while j > 0 and (E[j - 1][0], E[j - 1][1]) > (E[j][0], E[j][1]):\n            e, f = E[j], E[j - 1]\n            E[j - 1], E[j] = e, f\n            swaps += 1\n            p = (min(e[2], f[2]), max(e[2], f[2]))\n            if e[1] == 0 and f[1] == 1:\n                if new[e[2]][2] <= new[f[2]][4]:\n                    begins.add(p)\n            elif e[1] == 1 and f[1] == 0:\n                ends.add(p)\n            j -= 1\n    return [sorted(list(p) for p in begins), sorted(list(p) for p in ends), swaps]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\nfixtures = [[[[[[4, -3.0, 4.0, -3.0, 7.0], [12, -2.0, 0.0, -1.0, 0.0], [31, -3.0, -5.0, 0.0, -2.0], [17, 2.0, -3.0, 2.0, -1.0]], [[4, -4.0, 4.0, -4.0, 7.0], [12, 2.0, 0.0, 3.0, 0.0], [31, -3.0, -6.0, 0.0, -3.0], [17, 2.0, -3.0, 2.0, -1.0]]], [[], [[4, 31], [12, 31]], 5]], [[[[8, -3.0, 4.0, 0.0, 6.0], [15, 2.0, -2.0, 4.0, -2.0], [33, -1.0, 2.0, 0.0, 2.0], [10, 2.0, -3.0, 3.0, -1.0]], [[8, -1.0, 5.0, 2.0, 7.0], [15, -1.0, -2.0, 1.0, -2.0], [33, 0.0, 3.0, 1.0, 3.0], [10, -1.0, -4.0, 0.0, -2.0]]], [[], [], 10]], [[[[36, 4.0, -1.0, 5.0, 2.0], [8, 1.0, 3.0, 1.0, 5.0], [7, -3.0, 0.0, -1.0, 3.0], [28, 1.0, 4.0, 4.0, 5.0], [2, -5.0, -2.0, -4.0, 0.0], [23, 2.0, 1.0, 4.0, 1.0]], [[36, 3.0, -2.0, 4.0, 1.0], [8, 5.0, 3.0, 5.0, 5.0], [7, -3.0, 0.0, -1.0, 3.0], [28, 0.0, 3.0, 3.0, 4.0], [2, -3.0, -1.0, -2.0, 1.0], [23, 3.0, 1.0, 5.0, 1.0]]], [[[2, 7]], [[8, 28], [8, 36]], 12]], [[[[37, 3.0, -2.0, 5.0, -1.0], [14, -2.0, -4.0, 0.0, -2.0], [18, -5.0, 4.0, -2.0, 5.0]], [[37, 5.0, -1.0, 7.0, 0.0], [14, -3.0, -4.0, -1.0, -2.0], [18, -6.0, 4.0, -3.0, 5.0]]], [[], [], 0]], [[[[25, 2.0, 0.0, 5.0, 2.0], [26, -4.0, -3.0, -2.0, 0.0], [3, 4.0, 4.0, 6.0, 6.0], [30, 4.0, 0.0, 6.0, 2.0]], [[25, 3.0, 1.0, 6.0, 3.0], [26, -7.0, -4.0, -5.0, -1.0], [3, 4.0, 5.0, 6.0, 7.0], [30, 6.0, 0.0, 8.0, 2.0]]], [[], [], 0]], [[[[12, 2.0, -4.0, 4.0, -4.0], [39, -2.0, -1.0, 1.0, -1.0], [5, -5.0, 5.0, -5.0, 7.0]], [[12, 2.0, -5.0, 4.0, -5.0], [39, -2.0, 0.0, 1.0, 0.0], [5, -1.0, 5.0, -1.0, 7.0]]], [[], [], 2]], [[[[12, -1.0, 3.0, -1.0, 6.0], [1, -1.0, -4.0, 0.0, -3.0], [16, -3.0, -2.0, -2.0, -1.0], [30, 5.0, -4.0, 8.0, -3.0], [6, -2.0, 2.0, 1.0, 2.0]], [[12, 3.0, 3.0, 3.0, 6.0], [1, -1.0, -5.0, 0.0, -4.0], [16, 1.0, -2.0, 2.0, -1.0], [30, 9.0, -4.0, 12.0, -3.0], [6, -2.0, 2.0, 1.0, 2.0]]], [[], [[1, 12], [1, 16], [6, 12]], 10]], [[[[36, -1.0, -4.0, 1.0, -4.0], [9, -1.0, -2.0, 0.0, 1.0]], [[36, 1.0, -5.0, 3.0, -5.0], [9, 0.0, -1.0, 1.0, 2.0]]], [[], [], 0]]], [[[[[36, 5.0, -4.0, 6.0, -3.0], [6, 0.0, -2.0, 2.0, -2.0], [5, -5.0, -4.0, -4.0, -2.0], [3, 5.0, 4.0, 5.0, 4.0], [7, 0.0, 0.0, 3.0, 2.0], [28, 0.0, 0.0, 2.0, 0.0], [22, -4.0, -1.0, -4.0, 1.0]], [[36, 5.0, -3.0, 6.0, -2.0], [6, 0.0, -2.0, 2.0, -2.0], [5, -4.0, -4.0, -3.0, -2.0], [3, 6.0, 4.0, 6.0, 4.0], [7, 0.0, 1.0, 3.0, 3.0], [28, 4.0, 0.0, 6.0, 0.0], [22, -4.0, -1.0, -4.0, 1.0]]], [[], [[6, 28], [7, 28]], 7]], [[[[37, -5.0, -4.0, -2.0, -2.0], [1, 1.0, 2.0, 2.0, 3.0]], [[37, -5.0, -4.0, -2.0, -2.0], [1, 1.0, 3.0, 2.0, 4.0]]], [[], [], 0]], [[[[30, -1.0, -5.0, 0.0, -5.0], [20, 4.0, -5.0, 5.0, -4.0], [1, -1.0, -2.0, -1.0, -1.0], [12, -2.0, 1.0, -2.0, 2.0], [22, 1.0, 5.0, 2.0, 7.0]], [[30, -1.0, -6.0, 0.0, -6.0], [20, 3.0, -6.0, 4.0, -5.0], [1, -1.0, -1.0, -1.0, 0.0], [12, 0.0, 0.0, 0.0, 1.0], [22, 0.0, 5.0, 1.0, 7.0]]], [[[1, 12]], [[1, 12]], 8]], [[[[25, -3.0, 5.0, -1.0, 8.0], [9, -1.0, -4.0, 0.0, -3.0], [21, 0.0, -1.0, 3.0, 0.0], [3, 0.0, 3.0, 0.0, 5.0], [4, 4.0, -2.0, 6.0, -2.0]], [[25, -3.0, 4.0, -1.0, 7.0], [9, 1.0, -4.0, 2.0, -3.0], [21, 2.0, -2.0, 5.0, -1.0], [3, 0.0, 4.0, 0.0, 6.0], [4, 4.0, -2.0, 6.0, -2.0]]], [[[4, 21]], [[3, 9], [3, 21], [9, 25]], 5]], [[[[22, -2.0, 0.0, 1.0, 0.0], [8, -1.0, -2.0, 0.0, -2.0], [2, 3.0, -1.0, 6.0, 0.0], [33, 2.0, 4.0, 4.0, 5.0], [9, 3.0, -4.0, 6.0, -3.0], [37, 1.0, -5.0, 2.0, -4.0], [32, -4.0, 0.0, -1.0, 0.0]], [[22, -5.0, 0.0, -2.0, 0.0], [8, -4.0, -3.0, -3.0, -3.0], [2, 0.0, 0.0, 3.0, 1.0], [33, 2.0, 5.0, 4.0, 6.0], [9, 3.0, -4.0, 6.0, -3.0], [37, 2.0, -4.0, 3.0, -3.0], [32, 0.0, 0.0, 3.0, 0.0]]], [[[2, 32], [9, 37]], [[8, 32], [22, 32], [22, 37]], 16]], [[[[17, -3.0, 5.0, 0.0, 7.0], [29, -3.0, 0.0, -3.0, 1.0], [20, 5.0, -3.0, 8.0, -2.0], [4, 3.0, -5.0, 5.0, -2.0], [2, -4.0, 0.0, -2.0, 2.0], [1, 1.0, -4.0, 4.0, -2.0], [24, 2.0, -2.0, 3.0, 0.0]], [[17, 1.0, 5.0, 4.0, 7.0], [29, -6.0, -1.0, -6.0, 0.0], [20, 5.0, -2.0, 8.0, -1.0], [4, 2.0, -6.0, 4.0, -3.0], [2, -4.0, 0.0, -2.0, 2.0], [1, 0.0, -5.0, 3.0, -3.0], [24, 2.0, -3.0, 3.0, -1.0]]], [[], [[2, 17], [2, 29], [4, 20], [17, 29]], 12]], [[[[30, 4.0, 3.0, 4.0, 3.0], [11, -1.0, 4.0, 1.0, 6.0], [29, -3.0, -3.0, -3.0, 0.0], [18, -1.0, -4.0, 0.0, -2.0], [31, -1.0, 5.0, 2.0, 7.0], [21, -1.0, 0.0, -1.0, 3.0]], [[30, 3.0, 3.0, 3.0, 3.0], [11, 3.0, 3.0, 5.0, 5.0], [29, -3.0, -2.0, -3.0, 1.0], [18, 0.0, -4.0, 1.0, -2.0], [31, -1.0, 5.0, 2.0, 7.0], [21, 0.0, 0.0, 0.0, 3.0]]], [[[11, 30]], [[11, 18], [11, 21], [11, 31]], 11]], [[[[26, -5.0, 4.0, -4.0, 6.0], [30, -2.0, 0.0, 0.0, 3.0], [39, -5.0, -2.0, -2.0, -2.0]], [[26, -1.0, 4.0, 0.0, 6.0], [30, -2.0, -1.0, 0.0, 2.0], [39, -8.0, -1.0, -5.0, -1.0]]], [[], [[26, 39], [30, 39]], 6]]], [[[[[8, -4.0, 4.0, -2.0, 4.0], [32, 2.0, -2.0, 4.0, -1.0], [1, -2.0, -1.0, -1.0, 0.0], [38, -5.0, 3.0, -5.0, 3.0], [35, -4.0, 4.0, -2.0, 7.0], [11, -4.0, -5.0, -3.0, -2.0], [12, 2.0, -2.0, 4.0, 1.0]], [[8, -3.0, 3.0, -1.0, 3.0], [32, -1.0, -3.0, 1.0, -2.0], [1, -5.0, 0.0, -4.0, 1.0], [38, -5.0, 3.0, -5.0, 3.0], [35, -4.0, 3.0, -2.0, 6.0], [11, -4.0, -6.0, -3.0, -3.0], [12, 3.0, -3.0, 5.0, 0.0]]], [[], [[1, 8], [12, 32]], 16]], [[[[17, -5.0, 4.0, -2.0, 6.0], [5, -2.0, -5.0, -1.0, -3.0], [22, -1.0, 0.0, 0.0, 2.0], [1, -3.0, 1.0, 0.0, 2.0], [12, -3.0, 1.0, -1.0, 4.0], [33, 3.0, 2.0, 4.0, 5.0], [19, -5.0, 5.0, -2.0, 7.0]], [[17, -3.0, 4.0, 0.0, 6.0], [5, -1.0, -4.0, 0.0, -2.0], [22, -4.0, -1.0, -3.0, 1.0], [1, -2.0, 1.0, 1.0, 2.0], [12, -3.0, 0.0, -1.0, 3.0], [33, 5.0, 3.0, 6.0, 6.0], [19, -5.0, 5.0, -2.0, 7.0]]], [[], [[1, 22], [5, 19], [5, 22]], 19]], [[[[8, 5.0, 2.0, 8.0, 5.0], [13, 2.0, -4.0, 3.0, -1.0]], [[8, 2.0, 3.0, 5.0, 6.0], [13, 1.0, -4.0, 2.0, -1.0]]], [[], [], 1]], [[[[3, -1.0, -1.0, 2.0, 2.0], [10, -5.0, -3.0, -5.0, -1.0]], [[3, -2.0, -1.0, 1.0, 2.0], [10, -4.0, -4.0, -4.0, -2.0]]], [[], [], 0]], [[[[8, 4.0, 5.0, 4.0, 5.0], [25, 2.0, -5.0, 5.0, -3.0], [26, 3.0, 5.0, 6.0, 7.0], [35, -5.0, 2.0, -3.0, 4.0], [22, 4.0, -4.0, 6.0, -3.0], [5, -5.0, -4.0, -3.0, -4.0]], [[8, 4.0, 5.0, 4.0, 5.0], [25, 3.0, -5.0, 6.0, -3.0], [26, 4.0, 6.0, 7.0, 8.0], [35, -5.0, 1.0, -3.0, 3.0], [22, 3.0, -4.0, 5.0, -3.0], [5, -6.0, -4.0, -4.0, -4.0]]], [[], [], 3]], [[[[22, 0.0, 3.0, 1.0, 4.0], [36, 3.0, -5.0, 3.0, -2.0]], [[22, 0.0, 3.0, 1.0, 4.0], [36, 0.0, -5.0, 0.0, -2.0]]], [[], [], 2]], [[[[29, 4.0, 4.0, 6.0, 5.0], [28, 4.0, 5.0, 6.0, 7.0], [15, 3.0, -4.0, 3.0, -4.0], [20, -2.0, 2.0, -2.0, 3.0], [25, -2.0, 2.0, 0.0, 4.0], [6, -3.0, 1.0, -1.0, 3.0], [35, -4.0, 4.0, -3.0, 7.0]], [[29, 8.0, 4.0, 10.0, 5.0], [28, 5.0, 5.0, 7.0, 7.0], [15, 3.0, -4.0, 3.0, -4.0], [20, -5.0, 3.0, -5.0, 4.0], [25, -1.0, 2.0, 1.0, 4.0], [6, 1.0, 1.0, 3.0, 3.0], [35, -2.0, 4.0, -1.0, 7.0]]], [[[20, 35], [25, 35]], [[6, 20], [6, 35], [20, 25], [20, 35], [28, 29]], 13]], [[[[3, -5.0, -3.0, -3.0, 0.0], [10, 1.0, 3.0, 3.0, 4.0], [38, -5.0, 5.0, -4.0, 6.0]], [[3, -8.0, -2.0, -6.0, 1.0], [10, -2.0, 4.0, 0.0, 5.0], [38, -4.0, 5.0, -3.0, 6.0]]], [[], [[3, 38]], 2]]], [[[[[31, -5.0, -2.0, -3.0, -1.0], [2, -3.0, 3.0, -3.0, 6.0], [24, 5.0, -5.0, 7.0, -3.0]], [[31, -5.0, -2.0, -3.0, -1.0], [2, -3.0, 3.0, -3.0, 6.0], [24, 6.0, -5.0, 8.0, -3.0]]], [[], [], 0]], [[[[17, 5.0, -3.0, 5.0, -1.0], [13, -5.0, 3.0, -2.0, 3.0], [28, -5.0, 1.0, -5.0, 3.0], [5, 3.0, 5.0, 6.0, 7.0], [7, -1.0, -2.0, 1.0, 1.0], [10, 4.0, 3.0, 7.0, 6.0], [1, 4.0, -5.0, 5.0, -2.0], [3, -3.0, -5.0, -1.0, -2.0], [11, 0.0, -2.0, 1.0, 0.0]], [[17, 6.0, -3.0, 6.0, -1.0], [13, -4.0, 3.0, -1.0, 3.0], [28, -5.0, 1.0, -5.0, 3.0], [5, 4.0, 4.0, 7.0, 6.0], [7, -2.0, -2.0, 0.0, 1.0], [10, 4.0, 4.0, 7.0, 7.0], [1, 4.0, -6.0, 5.0, -3.0], [3, -4.0, -5.0, -2.0, -2.0], [11, 0.0, -2.0, 1.0, 0.0]]], [[], [[1, 17], [13, 28]], 5]], [[[[24, 2.0, -2.0, 3.0, -2.0], [2, 0.0, -4.0, 1.0, -4.0], [22, -2.0, -2.0, -1.0, -1.0], [20, 3.0, -5.0, 5.0, -4.0], [10, 3.0, 3.0, 6.0, 4.0], [30, -5.0, 2.0, -4.0, 4.0], [4, 3.0, -2.0, 6.0, -2.0]], [[24, -1.0, -2.0, 0.0, -2.0], [2, 0.0, -5.0, 1.0, -5.0], [22, -2.0, -2.0, -1.0, -1.0], [20, 4.0, -5.0, 6.0, -4.0], [10, 3.0, 2.0, 6.0, 3.0], [30, -5.0, 2.0, -4.0, 4.0], [4, 0.0, -2.0, 3.0, -2.0]]], [[[22, 24]], [[4, 20], [10, 24], [20, 24]], 9]], [[[[6, 0.0, -2.0, 0.0, -2.0], [11, -2.0, 0.0, -2.0, 3.0], [39, 4.0, 0.0, 7.0, 3.0]], [[6, 1.0, -2.0, 1.0, -2.0], [11, 2.0, 1.0, 2.0, 4.0], [39, 4.0, 0.0, 7.0, 3.0]]], [[], [[6, 11]], 4]], [[[[18, -1.0, 3.0, 0.0, 4.0], [39, 5.0, 0.0, 7.0, 2.0], [2, -1.0, 1.0, -1.0, 4.0], [19, -4.0, 3.0, -3.0, 3.0], [27, -2.0, 3.0, -1.0, 6.0], [10, -3.0, -2.0, -2.0, -1.0]], [[18, 1.0, 3.0, 2.0, 4.0], [39, 2.0, 0.0, 4.0, 2.0], [2, 1.0, 1.0, 1.0, 4.0], [19, -4.0, 3.0, -3.0, 3.0], [27, 2.0, 4.0, 3.0, 7.0], [10, -3.0, -3.0, -2.0, -2.0]]], [[], [[2, 27], [10, 27]], 7]], [[[[24, -2.0, -3.0, 0.0, -1.0], [32, 0.0, -3.0, 2.0, 0.0]], [[24, 2.0, -2.0, 4.0, 0.0], [32, 4.0, -3.0, 6.0, 0.0]]], [[], [], 0]], [[[[29, -4.0, -1.0, -3.0, -1.0], [14, 4.0, -5.0, 6.0, -5.0], [20, 2.0, -4.0, 2.0, -3.0]], [[29, -7.0, 0.0, -6.0, 0.0], [14, 4.0, -4.0, 6.0, -4.0], [20, -1.0, -4.0, -1.0, -3.0]]], [[], [], 0]], [[[[15, -4.0, 5.0, -1.0, 6.0], [21, -2.0, 1.0, -1.0, 2.0], [16, 5.0, 2.0, 8.0, 3.0], [39, 1.0, 1.0, 4.0, 1.0], [27, 1.0, -3.0, 1.0, -2.0], [12, 5.0, -5.0, 8.0, -5.0]], [[15, -4.0, 4.0, -1.0, 5.0], [21, -1.0, 1.0, 0.0, 2.0], [16, 6.0, 2.0, 9.0, 3.0], [39, 3.0, 1.0, 6.0, 1.0], [27, 3.0, -3.0, 3.0, -2.0], [12, 5.0, -5.0, 8.0, -5.0]]], [[], [], 2]]], [[[[[28, 2.0, 2.0, 5.0, 2.0], [24, -3.0, 4.0, -3.0, 4.0], [29, -5.0, 4.0, -4.0, 5.0], [10, 1.0, 1.0, 4.0, 2.0], [33, -2.0, -4.0, -1.0, -3.0], [12, 2.0, 3.0, 2.0, 3.0], [39, -5.0, -3.0, -2.0, -2.0], [1, 3.0, -5.0, 4.0, -4.0]], [[28, 2.0, 2.0, 5.0, 2.0], [24, -4.0, 5.0, -4.0, 5.0], [29, -6.0, 3.0, -5.0, 4.0], [10, 3.0, 1.0, 6.0, 2.0], [33, -3.0, -4.0, -2.0, -3.0], [12, 4.0, 3.0, 4.0, 3.0], [39, -3.0, -2.0, 0.0, -1.0], [1, 2.0, -5.0, 3.0, -4.0]]], [[], [[1, 12], [24, 39], [29, 39]], 12]], [[[[37, 0.0, -3.0, 3.0, -3.0], [2, 3.0, -2.0, 5.0, -2.0], [35, 5.0, 2.0, 7.0, 3.0]], [[37, 2.0, -3.0, 5.0, -3.0], [2, 3.0, -3.0, 5.0, -3.0], [35, 5.0, 3.0, 7.0, 4.0]]], [[], [], 1]], [[[[15, 0.0, 0.0, 2.0, 0.0], [18, 3.0, 0.0, 4.0, 1.0], [30, 1.0, -3.0, 1.0, -2.0], [24, -5.0, -4.0, -5.0, -3.0], [32, 5.0, -3.0, 8.0, -2.0]], [[15, 2.0, -1.0, 4.0, -1.0], [18, 7.0, -1.0, 8.0, 0.0], [30, 1.0, -3.0, 1.0, -2.0], [24, -6.0, -3.0, -6.0, -2.0], [32, 7.0, -2.0, 10.0, -1.0]]], [[[18, 32]], [[15, 30]], 3]], [[[[29, 3.0, 3.0, 3.0, 6.0], [20, 4.0, 4.0, 5.0, 7.0], [7, 3.0, 2.0, 4.0, 4.0], [21, 3.0, -1.0, 5.0, 0.0]], [[29, 3.0, 2.0, 3.0, 5.0], [20, 5.0, 5.0, 6.0, 8.0], [7, 4.0, 3.0, 5.0, 5.0], [21, 2.0, -2.0, 4.0, -1.0]]], [[], [[7, 29], [20, 21]], 6]], [[[[25, 0.0, 3.0, 2.0, 3.0], [27, 0.0, 5.0, 0.0, 5.0], [33, -1.0, -5.0, 1.0, -4.0], [9, -5.0, 4.0, -5.0, 6.0], [21, 3.0, 4.0, 6.0, 6.0], [18, -2.0, -2.0, -2.0, -1.0], [39, -2.0, -3.0, 0.0, 0.0], [20, 3.0, -3.0, 3.0, -3.0], [2, -1.0, 0.0, 2.0, 1.0]], [[25, 0.0, 4.0, 2.0, 4.0], [27, 4.0, 6.0, 4.0, 6.0], [33, 1.0, -5.0, 3.0, -4.0], [9, -5.0, 5.0, -5.0, 7.0], [21, 4.0, 5.0, 7.0, 7.0], [18, -1.0, -2.0, -1.0, -1.0], [39, -5.0, -3.0, -3.0, 0.0], [20, 3.0, -2.0, 3.0, -2.0], [2, 3.0, 0.0, 6.0, 1.0]]], [[[21, 27]], [[2, 25], [2, 39], [18, 39], [20, 21], [20, 27], [25, 27], [25, 39], [27, 33], [27, 39], [33, 39]], 29]], [[[[17, 3.0, 1.0, 4.0, 2.0], [20, -2.0, -3.0, -1.0, -3.0], [27, 3.0, 5.0, 6.0, 8.0], [30, -3.0, 3.0, 0.0, 6.0], [6, -4.0, -4.0, -4.0, -1.0]], [[17, 3.0, 1.0, 4.0, 2.0], [20, -2.0, -4.0, -1.0, -4.0], [27, 0.0, 6.0, 3.0, 9.0], [30, -1.0, 4.0, 2.0, 7.0], [6, -7.0, -4.0, -7.0, -1.0]]], [[[27, 30]], [], 4]], [[[[22, 2.0, -1.0, 3.0, -1.0], [14, -2.0, -2.0, -1.0, 0.0], [17, 1.0, -2.0, 2.0, 0.0], [1, 0.0, -2.0, 3.0, -1.0], [16, 2.0, 3.0, 3.0, 4.0], [33, 1.0, 4.0, 3.0, 7.0], [24, 0.0, 3.0, 0.0, 6.0], [3, 3.0, -5.0, 4.0, -5.0], [38, 0.0, 3.0, 0.0, 3.0]], [[22, 2.0, -1.0, 3.0, -1.0], [14, -5.0, -2.0, -4.0, 0.0], [17, 3.0, -1.0, 4.0, 1.0], [1, 1.0, -2.0, 4.0, -1.0], [16, 4.0, 4.0, 5.0, 5.0], [33, 1.0, 4.0, 3.0, 7.0], [24, 2.0, 3.0, 2.0, 6.0], [3, 7.0, -4.0, 8.0, -4.0], [38, 2.0, 3.0, 2.0, 3.0]]], [[[24, 33]], [[1, 3], [3, 16], [3, 22], [3, 33], [16, 22], [16, 33]], 21]], [[[[20, -3.0, 1.0, -1.0, 4.0], [37, 3.0, 1.0, 4.0, 1.0], [3, 5.0, -1.0, 5.0, 2.0], [12, -4.0, 2.0, -4.0, 4.0], [21, -1.0, -2.0, 2.0, -1.0], [33, 2.0, 2.0, 5.0, 3.0], [6, 1.0, -2.0, 2.0, 0.0], [36, 3.0, 0.0, 3.0, 3.0]], [[20, 1.0, 0.0, 3.0, 3.0], [37, 4.0, 1.0, 5.0, 1.0], [3, 4.0, -1.0, 4.0, 2.0], [12, -5.0, 3.0, -5.0, 5.0], [21, -1.0, -1.0, 2.0, 0.0], [33, 1.0, 2.0, 4.0, 3.0], [6, 1.0, -3.0, 2.0, -1.0], [36, 0.0, 1.0, 0.0, 4.0]]], [[[3, 37], [20, 33], [20, 36]], [[6, 36], [20, 36], [33, 36], [36, 37]], 21]]]]\nfor i, (args, expected) in enumerate(fixtures[N-1]):\n    check(\"case %d\" % i, solve(*args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"},"broken":{"sha256":"19fd3ac8807f9adf15e4d4b2731615e97b496788c523888462ea5b1cf8545eb2","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nimport math\nN = 1\nobservations = []\ndef solve(prev, curr):\n    old = {b[0]: b for b in prev}\n    new = {b[0]: b for b in curr}\n    E = []\n    for i, b in old.items():\n        E.append([b[1], 0, i])\n        E.append([b[3], 1, i])\n    E.sort()\n    for e in E:\n        b = new[e[2]]\n        e[0] = b[1] if e[1] == 0 else b[3]\n    def yover(a, c):\n        return new[a][2] <= new[c][4] and new[c][2] <= new[a][4]\n    begins, ends = set(), set()\n    swaps = 0\n    for i in range(1, len(E)):\n        j = i\n        while j > 0 and (E[j - 1][0], E[j - 1][1]) > (E[j][0], E[j][1]):\n            e, f = E[j], E[j - 1]\n            E[j - 1], E[j] = e, f\n            swaps += 1\n            p = (min(e[2], f[2]), max(e[2], f[2]))\n            if e[1] == 0 and f[1] == 1:\n                begins.add(p)\n            elif e[1] == 1 and f[1] == 0:\n                ends.add(p)\n            j -= 1\n    return [sorted(list(p) for p in begins), sorted(list(p) for p in ends), swaps]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\nfixtures = [[[[[[4, -3.0, 4.0, -3.0, 7.0], [12, -2.0, 0.0, -1.0, 0.0], [31, -3.0, -5.0, 0.0, -2.0], [17, 2.0, -3.0, 2.0, -1.0]], [[4, -4.0, 4.0, -4.0, 7.0], [12, 2.0, 0.0, 3.0, 0.0], [31, -3.0, -6.0, 0.0, -3.0], [17, 2.0, -3.0, 2.0, -1.0]]], [[], [[4, 31], [12, 31]], 5]], [[[[8, -3.0, 4.0, 0.0, 6.0], [15, 2.0, -2.0, 4.0, -2.0], [33, -1.0, 2.0, 0.0, 2.0], [10, 2.0, -3.0, 3.0, -1.0]], [[8, -1.0, 5.0, 2.0, 7.0], [15, -1.0, -2.0, 1.0, -2.0], [33, 0.0, 3.0, 1.0, 3.0], [10, -1.0, -4.0, 0.0, -2.0]]], [[], [], 10]], [[[[36, 4.0, -1.0, 5.0, 2.0], [8, 1.0, 3.0, 1.0, 5.0], [7, -3.0, 0.0, -1.0, 3.0], [28, 1.0, 4.0, 4.0, 5.0], [2, -5.0, -2.0, -4.0, 0.0], [23, 2.0, 1.0, 4.0, 1.0]], [[36, 3.0, -2.0, 4.0, 1.0], [8, 5.0, 3.0, 5.0, 5.0], [7, -3.0, 0.0, -1.0, 3.0], [28, 0.0, 3.0, 3.0, 4.0], [2, -3.0, -1.0, -2.0, 1.0], [23, 3.0, 1.0, 5.0, 1.0]]], [[[2, 7]], [[8, 28], [8, 36]], 12]], [[[[37, 3.0, -2.0, 5.0, -1.0], [14, -2.0, -4.0, 0.0, -2.0], [18, -5.0, 4.0, -2.0, 5.0]], [[37, 5.0, -1.0, 7.0, 0.0], [14, -3.0, -4.0, -1.0, -2.0], [18, -6.0, 4.0, -3.0, 5.0]]], [[], [], 0]], [[[[25, 2.0, 0.0, 5.0, 2.0], [26, -4.0, -3.0, -2.0, 0.0], [3, 4.0, 4.0, 6.0, 6.0], [30, 4.0, 0.0, 6.0, 2.0]], [[25, 3.0, 1.0, 6.0, 3.0], [26, -7.0, -4.0, -5.0, -1.0], [3, 4.0, 5.0, 6.0, 7.0], [30, 6.0, 0.0, 8.0, 2.0]]], [[], [], 0]], [[[[12, 2.0, -4.0, 4.0, -4.0], [39, -2.0, -1.0, 1.0, -1.0], [5, -5.0, 5.0, -5.0, 7.0]], [[12, 2.0, -5.0, 4.0, -5.0], [39, -2.0, 0.0, 1.0, 0.0], [5, -1.0, 5.0, -1.0, 7.0]]], [[], [], 2]], [[[[12, -1.0, 3.0, -1.0, 6.0], [1, -1.0, -4.0, 0.0, -3.0], [16, -3.0, -2.0, -2.0, -1.0], [30, 5.0, -4.0, 8.0, -3.0], [6, -2.0, 2.0, 1.0, 2.0]], [[12, 3.0, 3.0, 3.0, 6.0], [1, -1.0, -5.0, 0.0, -4.0], [16, 1.0, -2.0, 2.0, -1.0], [30, 9.0, -4.0, 12.0, -3.0], [6, -2.0, 2.0, 1.0, 2.0]]], [[], [[1, 12], [1, 16], [6, 12]], 10]], [[[[36, -1.0, -4.0, 1.0, -4.0], [9, -1.0, -2.0, 0.0, 1.0]], [[36, 1.0, -5.0, 3.0, -5.0], [9, 0.0, -1.0, 1.0, 2.0]]], [[], [], 0]]], [[[[[36, 5.0, -4.0, 6.0, -3.0], [6, 0.0, -2.0, 2.0, -2.0], [5, -5.0, -4.0, -4.0, -2.0], [3, 5.0, 4.0, 5.0, 4.0], [7, 0.0, 0.0, 3.0, 2.0], [28, 0.0, 0.0, 2.0, 0.0], [22, -4.0, -1.0, -4.0, 1.0]], [[36, 5.0, -3.0, 6.0, -2.0], [6, 0.0, -2.0, 2.0, -2.0], [5, -4.0, -4.0, -3.0, -2.0], [3, 6.0, 4.0, 6.0, 4.0], [7, 0.0, 1.0, 3.0, 3.0], [28, 4.0, 0.0, 6.0, 0.0], [22, -4.0, -1.0, -4.0, 1.0]]], [[], [[6, 28], [7, 28]], 7]], [[[[37, -5.0, -4.0, -2.0, -2.0], [1, 1.0, 2.0, 2.0, 3.0]], [[37, -5.0, -4.0, -2.0, -2.0], [1, 1.0, 3.0, 2.0, 4.0]]], [[], [], 0]], [[[[30, -1.0, -5.0, 0.0, -5.0], [20, 4.0, -5.0, 5.0, -4.0], [1, -1.0, -2.0, -1.0, -1.0], [12, -2.0, 1.0, -2.0, 2.0], [22, 1.0, 5.0, 2.0, 7.0]], [[30, -1.0, -6.0, 0.0, -6.0], [20, 3.0, -6.0, 4.0, -5.0], [1, -1.0, -1.0, -1.0, 0.0], [12, 0.0, 0.0, 0.0, 1.0], [22, 0.0, 5.0, 1.0, 7.0]]], [[[1, 12]], [[1, 12]], 8]], [[[[25, -3.0, 5.0, -1.0, 8.0], [9, -1.0, -4.0, 0.0, -3.0], [21, 0.0, -1.0, 3.0, 0.0], [3, 0.0, 3.0, 0.0, 5.0], [4, 4.0, -2.0, 6.0, -2.0]], [[25, -3.0, 4.0, -1.0, 7.0], [9, 1.0, -4.0, 2.0, -3.0], [21, 2.0, -2.0, 5.0, -1.0], [3, 0.0, 4.0, 0.0, 6.0], [4, 4.0, -2.0, 6.0, -2.0]]], [[[4, 21]], [[3, 9], [3, 21], [9, 25]], 5]], [[[[22, -2.0, 0.0, 1.0, 0.0], [8, -1.0, -2.0, 0.0, -2.0], [2, 3.0, -1.0, 6.0, 0.0], [33, 2.0, 4.0, 4.0, 5.0], [9, 3.0, -4.0, 6.0, -3.0], [37, 1.0, -5.0, 2.0, -4.0], [32, -4.0, 0.0, -1.0, 0.0]], [[22, -5.0, 0.0, -2.0, 0.0], [8, -4.0, -3.0, -3.0, -3.0], [2, 0.0, 0.0, 3.0, 1.0], [33, 2.0, 5.0, 4.0, 6.0], [9, 3.0, -4.0, 6.0, -3.0], [37, 2.0, -4.0, 3.0, -3.0], [32, 0.0, 0.0, 3.0, 0.0]]], [[[2, 32], [9, 37]], [[8, 32], [22, 32], [22, 37]], 16]], [[[[17, -3.0, 5.0, 0.0, 7.0], [29, -3.0, 0.0, -3.0, 1.0], [20, 5.0, -3.0, 8.0, -2.0], [4, 3.0, -5.0, 5.0, -2.0], [2, -4.0, 0.0, -2.0, 2.0], [1, 1.0, -4.0, 4.0, -2.0], [24, 2.0, -2.0, 3.0, 0.0]], [[17, 1.0, 5.0, 4.0, 7.0], [29, -6.0, -1.0, -6.0, 0.0], [20, 5.0, -2.0, 8.0, -1.0], [4, 2.0, -6.0, 4.0, -3.0], [2, -4.0, 0.0, -2.0, 2.0], [1, 0.0, -5.0, 3.0, -3.0], [24, 2.0, -3.0, 3.0, -1.0]]], [[], [[2, 17], [2, 29], [4, 20], [17, 29]], 12]], [[[[30, 4.0, 3.0, 4.0, 3.0], [11, -1.0, 4.0, 1.0, 6.0], [29, -3.0, -3.0, -3.0, 0.0], [18, -1.0, -4.0, 0.0, -2.0], [31, -1.0, 5.0, 2.0, 7.0], [21, -1.0, 0.0, -1.0, 3.0]], [[30, 3.0, 3.0, 3.0, 3.0], [11, 3.0, 3.0, 5.0, 5.0], [29, -3.0, -2.0, -3.0, 1.0], [18, 0.0, -4.0, 1.0, -2.0], [31, -1.0, 5.0, 2.0, 7.0], [21, 0.0, 0.0, 0.0, 3.0]]], [[[11, 30]], [[11, 18], [11, 21], [11, 31]], 11]], [[[[26, -5.0, 4.0, -4.0, 6.0], [30, -2.0, 0.0, 0.0, 3.0], [39, -5.0, -2.0, -2.0, -2.0]], [[26, -1.0, 4.0, 0.0, 6.0], [30, -2.0, -1.0, 0.0, 2.0], [39, -8.0, -1.0, -5.0, -1.0]]], [[], [[26, 39], [30, 39]], 6]]], [[[[[8, -4.0, 4.0, -2.0, 4.0], [32, 2.0, -2.0, 4.0, -1.0], [1, -2.0, -1.0, -1.0, 0.0], [38, -5.0, 3.0, -5.0, 3.0], [35, -4.0, 4.0, -2.0, 7.0], [11, -4.0, -5.0, -3.0, -2.0], [12, 2.0, -2.0, 4.0, 1.0]], [[8, -3.0, 3.0, -1.0, 3.0], [32, -1.0, -3.0, 1.0, -2.0], [1, -5.0, 0.0, -4.0, 1.0], [38, -5.0, 3.0, -5.0, 3.0], [35, -4.0, 3.0, -2.0, 6.0], [11, -4.0, -6.0, -3.0, -3.0], [12, 3.0, -3.0, 5.0, 0.0]]], [[], [[1, 8], [12, 32]], 16]], [[[[17, -5.0, 4.0, -2.0, 6.0], [5, -2.0, -5.0, -1.0, -3.0], [22, -1.0, 0.0, 0.0, 2.0], [1, -3.0, 1.0, 0.0, 2.0], [12, -3.0, 1.0, -1.0, 4.0], [33, 3.0, 2.0, 4.0, 5.0], [19, -5.0, 5.0, -2.0, 7.0]], [[17, -3.0, 4.0, 0.0, 6.0], [5, -1.0, -4.0, 0.0, -2.0], [22, -4.0, -1.0, -3.0, 1.0], [1, -2.0, 1.0, 1.0, 2.0], [12, -3.0, 0.0, -1.0, 3.0], [33, 5.0, 3.0, 6.0, 6.0], [19, -5.0, 5.0, -2.0, 7.0]]], [[], [[1, 22], [5, 19], [5, 22]], 19]], [[[[8, 5.0, 2.0, 8.0, 5.0], [13, 2.0, -4.0, 3.0, -1.0]], [[8, 2.0, 3.0, 5.0, 6.0], [13, 1.0, -4.0, 2.0, -1.0]]], [[], [], 1]], [[[[3, -1.0, -1.0, 2.0, 2.0], [10, -5.0, -3.0, -5.0, -1.0]], [[3, -2.0, -1.0, 1.0, 2.0], [10, -4.0, -4.0, -4.0, -2.0]]], [[], [], 0]], [[[[8, 4.0, 5.0, 4.0, 5.0], [25, 2.0, -5.0, 5.0, -3.0], [26, 3.0, 5.0, 6.0, 7.0], [35, -5.0, 2.0, -3.0, 4.0], [22, 4.0, -4.0, 6.0, -3.0], [5, -5.0, -4.0, -3.0, -4.0]], [[8, 4.0, 5.0, 4.0, 5.0], [25, 3.0, -5.0, 6.0, -3.0], [26, 4.0, 6.0, 7.0, 8.0], [35, -5.0, 1.0, -3.0, 3.0], [22, 3.0, -4.0, 5.0, -3.0], [5, -6.0, -4.0, -4.0, -4.0]]], [[], [], 3]], [[[[22, 0.0, 3.0, 1.0, 4.0], [36, 3.0, -5.0, 3.0, -2.0]], [[22, 0.0, 3.0, 1.0, 4.0], [36, 0.0, -5.0, 0.0, -2.0]]], [[], [], 2]], [[[[29, 4.0, 4.0, 6.0, 5.0], [28, 4.0, 5.0, 6.0, 7.0], [15, 3.0, -4.0, 3.0, -4.0], [20, -2.0, 2.0, -2.0, 3.0], [25, -2.0, 2.0, 0.0, 4.0], [6, -3.0, 1.0, -1.0, 3.0], [35, -4.0, 4.0, -3.0, 7.0]], [[29, 8.0, 4.0, 10.0, 5.0], [28, 5.0, 5.0, 7.0, 7.0], [15, 3.0, -4.0, 3.0, -4.0], [20, -5.0, 3.0, -5.0, 4.0], [25, -1.0, 2.0, 1.0, 4.0], [6, 1.0, 1.0, 3.0, 3.0], [35, -2.0, 4.0, -1.0, 7.0]]], [[[20, 35], [25, 35]], [[6, 20], [6, 35], [20, 25], [20, 35], [28, 29]], 13]], [[[[3, -5.0, -3.0, -3.0, 0.0], [10, 1.0, 3.0, 3.0, 4.0], [38, -5.0, 5.0, -4.0, 6.0]], [[3, -8.0, -2.0, -6.0, 1.0], [10, -2.0, 4.0, 0.0, 5.0], [38, -4.0, 5.0, -3.0, 6.0]]], [[], [[3, 38]], 2]]], [[[[[31, -5.0, -2.0, -3.0, -1.0], [2, -3.0, 3.0, -3.0, 6.0], [24, 5.0, -5.0, 7.0, -3.0]], [[31, -5.0, -2.0, -3.0, -1.0], [2, -3.0, 3.0, -3.0, 6.0], [24, 6.0, -5.0, 8.0, -3.0]]], [[], [], 0]], [[[[17, 5.0, -3.0, 5.0, -1.0], [13, -5.0, 3.0, -2.0, 3.0], [28, -5.0, 1.0, -5.0, 3.0], [5, 3.0, 5.0, 6.0, 7.0], [7, -1.0, -2.0, 1.0, 1.0], [10, 4.0, 3.0, 7.0, 6.0], [1, 4.0, -5.0, 5.0, -2.0], [3, -3.0, -5.0, -1.0, -2.0], [11, 0.0, -2.0, 1.0, 0.0]], [[17, 6.0, -3.0, 6.0, -1.0], [13, -4.0, 3.0, -1.0, 3.0], [28, -5.0, 1.0, -5.0, 3.0], [5, 4.0, 4.0, 7.0, 6.0], [7, -2.0, -2.0, 0.0, 1.0], [10, 4.0, 4.0, 7.0, 7.0], [1, 4.0, -6.0, 5.0, -3.0], [3, -4.0, -5.0, -2.0, -2.0], [11, 0.0, -2.0, 1.0, 0.0]]], [[], [[1, 17], [13, 28]], 5]], [[[[24, 2.0, -2.0, 3.0, -2.0], [2, 0.0, -4.0, 1.0, -4.0], [22, -2.0, -2.0, -1.0, -1.0], [20, 3.0, -5.0, 5.0, -4.0], [10, 3.0, 3.0, 6.0, 4.0], [30, -5.0, 2.0, -4.0, 4.0], [4, 3.0, -2.0, 6.0, -2.0]], [[24, -1.0, -2.0, 0.0, -2.0], [2, 0.0, -5.0, 1.0, -5.0], [22, -2.0, -2.0, -1.0, -1.0], [20, 4.0, -5.0, 6.0, -4.0], [10, 3.0, 2.0, 6.0, 3.0], [30, -5.0, 2.0, -4.0, 4.0], [4, 0.0, -2.0, 3.0, -2.0]]], [[[22, 24]], [[4, 20], [10, 24], [20, 24]], 9]], [[[[6, 0.0, -2.0, 0.0, -2.0], [11, -2.0, 0.0, -2.0, 3.0], [39, 4.0, 0.0, 7.0, 3.0]], [[6, 1.0, -2.0, 1.0, -2.0], [11, 2.0, 1.0, 2.0, 4.0], [39, 4.0, 0.0, 7.0, 3.0]]], [[], [[6, 11]], 4]], [[[[18, -1.0, 3.0, 0.0, 4.0], [39, 5.0, 0.0, 7.0, 2.0], [2, -1.0, 1.0, -1.0, 4.0], [19, -4.0, 3.0, -3.0, 3.0], [27, -2.0, 3.0, -1.0, 6.0], [10, -3.0, -2.0, -2.0, -1.0]], [[18, 1.0, 3.0, 2.0, 4.0], [39, 2.0, 0.0, 4.0, 2.0], [2, 1.0, 1.0, 1.0, 4.0], [19, -4.0, 3.0, -3.0, 3.0], [27, 2.0, 4.0, 3.0, 7.0], [10, -3.0, -3.0, -2.0, -2.0]]], [[], [[2, 27], [10, 27]], 7]], [[[[24, -2.0, -3.0, 0.0, -1.0], [32, 0.0, -3.0, 2.0, 0.0]], [[24, 2.0, -2.0, 4.0, 0.0], [32, 4.0, -3.0, 6.0, 0.0]]], [[], [], 0]], [[[[29, -4.0, -1.0, -3.0, -1.0], [14, 4.0, -5.0, 6.0, -5.0], [20, 2.0, -4.0, 2.0, -3.0]], [[29, -7.0, 0.0, -6.0, 0.0], [14, 4.0, -4.0, 6.0, -4.0], [20, -1.0, -4.0, -1.0, -3.0]]], [[], [], 0]], [[[[15, -4.0, 5.0, -1.0, 6.0], [21, -2.0, 1.0, -1.0, 2.0], [16, 5.0, 2.0, 8.0, 3.0], [39, 1.0, 1.0, 4.0, 1.0], [27, 1.0, -3.0, 1.0, -2.0], [12, 5.0, -5.0, 8.0, -5.0]], [[15, -4.0, 4.0, -1.0, 5.0], [21, -1.0, 1.0, 0.0, 2.0], [16, 6.0, 2.0, 9.0, 3.0], [39, 3.0, 1.0, 6.0, 1.0], [27, 3.0, -3.0, 3.0, -2.0], [12, 5.0, -5.0, 8.0, -5.0]]], [[], [], 2]]], [[[[[28, 2.0, 2.0, 5.0, 2.0], [24, -3.0, 4.0, -3.0, 4.0], [29, -5.0, 4.0, -4.0, 5.0], [10, 1.0, 1.0, 4.0, 2.0], [33, -2.0, -4.0, -1.0, -3.0], [12, 2.0, 3.0, 2.0, 3.0], [39, -5.0, -3.0, -2.0, -2.0], [1, 3.0, -5.0, 4.0, -4.0]], [[28, 2.0, 2.0, 5.0, 2.0], [24, -4.0, 5.0, -4.0, 5.0], [29, -6.0, 3.0, -5.0, 4.0], [10, 3.0, 1.0, 6.0, 2.0], [33, -3.0, -4.0, -2.0, -3.0], [12, 4.0, 3.0, 4.0, 3.0], [39, -3.0, -2.0, 0.0, -1.0], [1, 2.0, -5.0, 3.0, -4.0]]], [[], [[1, 12], [24, 39], [29, 39]], 12]], [[[[37, 0.0, -3.0, 3.0, -3.0], [2, 3.0, -2.0, 5.0, -2.0], [35, 5.0, 2.0, 7.0, 3.0]], [[37, 2.0, -3.0, 5.0, -3.0], [2, 3.0, -3.0, 5.0, -3.0], [35, 5.0, 3.0, 7.0, 4.0]]], [[], [], 1]], [[[[15, 0.0, 0.0, 2.0, 0.0], [18, 3.0, 0.0, 4.0, 1.0], [30, 1.0, -3.0, 1.0, -2.0], [24, -5.0, -4.0, -5.0, -3.0], [32, 5.0, -3.0, 8.0, -2.0]], [[15, 2.0, -1.0, 4.0, -1.0], [18, 7.0, -1.0, 8.0, 0.0], [30, 1.0, -3.0, 1.0, -2.0], [24, -6.0, -3.0, -6.0, -2.0], [32, 7.0, -2.0, 10.0, -1.0]]], [[[18, 32]], [[15, 30]], 3]], [[[[29, 3.0, 3.0, 3.0, 6.0], [20, 4.0, 4.0, 5.0, 7.0], [7, 3.0, 2.0, 4.0, 4.0], [21, 3.0, -1.0, 5.0, 0.0]], [[29, 3.0, 2.0, 3.0, 5.0], [20, 5.0, 5.0, 6.0, 8.0], [7, 4.0, 3.0, 5.0, 5.0], [21, 2.0, -2.0, 4.0, -1.0]]], [[], [[7, 29], [20, 21]], 6]], [[[[25, 0.0, 3.0, 2.0, 3.0], [27, 0.0, 5.0, 0.0, 5.0], [33, -1.0, -5.0, 1.0, -4.0], [9, -5.0, 4.0, -5.0, 6.0], [21, 3.0, 4.0, 6.0, 6.0], [18, -2.0, -2.0, -2.0, -1.0], [39, -2.0, -3.0, 0.0, 0.0], [20, 3.0, -3.0, 3.0, -3.0], [2, -1.0, 0.0, 2.0, 1.0]], [[25, 0.0, 4.0, 2.0, 4.0], [27, 4.0, 6.0, 4.0, 6.0], [33, 1.0, -5.0, 3.0, -4.0], [9, -5.0, 5.0, -5.0, 7.0], [21, 4.0, 5.0, 7.0, 7.0], [18, -1.0, -2.0, -1.0, -1.0], [39, -5.0, -3.0, -3.0, 0.0], [20, 3.0, -2.0, 3.0, -2.0], [2, 3.0, 0.0, 6.0, 1.0]]], [[[21, 27]], [[2, 25], [2, 39], [18, 39], [20, 21], [20, 27], [25, 27], [25, 39], [27, 33], [27, 39], [33, 39]], 29]], [[[[17, 3.0, 1.0, 4.0, 2.0], [20, -2.0, -3.0, -1.0, -3.0], [27, 3.0, 5.0, 6.0, 8.0], [30, -3.0, 3.0, 0.0, 6.0], [6, -4.0, -4.0, -4.0, -1.0]], [[17, 3.0, 1.0, 4.0, 2.0], [20, -2.0, -4.0, -1.0, -4.0], [27, 0.0, 6.0, 3.0, 9.0], [30, -1.0, 4.0, 2.0, 7.0], [6, -7.0, -4.0, -7.0, -1.0]]], [[[27, 30]], [], 4]], [[[[22, 2.0, -1.0, 3.0, -1.0], [14, -2.0, -2.0, -1.0, 0.0], [17, 1.0, -2.0, 2.0, 0.0], [1, 0.0, -2.0, 3.0, -1.0], [16, 2.0, 3.0, 3.0, 4.0], [33, 1.0, 4.0, 3.0, 7.0], [24, 0.0, 3.0, 0.0, 6.0], [3, 3.0, -5.0, 4.0, -5.0], [38, 0.0, 3.0, 0.0, 3.0]], [[22, 2.0, -1.0, 3.0, -1.0], [14, -5.0, -2.0, -4.0, 0.0], [17, 3.0, -1.0, 4.0, 1.0], [1, 1.0, -2.0, 4.0, -1.0], [16, 4.0, 4.0, 5.0, 5.0], [33, 1.0, 4.0, 3.0, 7.0], [24, 2.0, 3.0, 2.0, 6.0], [3, 7.0, -4.0, 8.0, -4.0], [38, 2.0, 3.0, 2.0, 3.0]]], [[[24, 33]], [[1, 3], [3, 16], [3, 22], [3, 33], [16, 22], [16, 33]], 21]], [[[[20, -3.0, 1.0, -1.0, 4.0], [37, 3.0, 1.0, 4.0, 1.0], [3, 5.0, -1.0, 5.0, 2.0], [12, -4.0, 2.0, -4.0, 4.0], [21, -1.0, -2.0, 2.0, -1.0], [33, 2.0, 2.0, 5.0, 3.0], [6, 1.0, -2.0, 2.0, 0.0], [36, 3.0, 0.0, 3.0, 3.0]], [[20, 1.0, 0.0, 3.0, 3.0], [37, 4.0, 1.0, 5.0, 1.0], [3, 4.0, -1.0, 4.0, 2.0], [12, -5.0, 3.0, -5.0, 5.0], [21, -1.0, -1.0, 2.0, 0.0], [33, 1.0, 2.0, 4.0, 3.0], [6, 1.0, -3.0, 2.0, -1.0], [36, 0.0, 1.0, 0.0, 4.0]]], [[[3, 37], [20, 33], [20, 36]], [[6, 36], [20, 36], [33, 36], [36, 37]], 21]]]]\nfor i, (args, expected) in enumerate(fixtures[N-1]):\n    check(\"case %d\" % i, solve(*args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"},"fixed":{"sha256":"184d00652fff86c61c613a5b6fd57d22250f13ae8d5a684445034a33a8d88883","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nimport math\nN = 1\nobservations = []\ndef solve(prev, curr):\n    old = {b[0]: b for b in prev}\n    new = {b[0]: b for b in curr}\n    E = []\n    for i, b in old.items():\n        E.append([b[1], 0, i])\n        E.append([b[3], 1, i])\n    E.sort()\n    for e in E:\n        b = new[e[2]]\n        e[0] = b[1] if e[1] == 0 else b[3]\n    def yover(a, c):\n        return new[a][2] <= new[c][4] and new[c][2] <= new[a][4]\n    begins, ends = set(), set()\n    swaps = 0\n    for i in range(1, len(E)):\n        j = i\n        while j > 0 and (E[j - 1][0], E[j - 1][1]) > (E[j][0], E[j][1]):\n            e, f = E[j], E[j - 1]\n            E[j - 1], E[j] = e, f\n            swaps += 1\n            p = (min(e[2], f[2]), max(e[2], f[2]))\n            if e[1] == 0 and f[1] == 1:\n                if yover(e[2], f[2]):\n                    begins.add(p)\n            elif e[1] == 1 and f[1] == 0:\n                ends.add(p)\n            j -= 1\n    return [sorted(list(p) for p in begins), sorted(list(p) for p in ends), swaps]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\nfixtures = [[[[[[4, -3.0, 4.0, -3.0, 7.0], [12, -2.0, 0.0, -1.0, 0.0], [31, -3.0, -5.0, 0.0, -2.0], [17, 2.0, -3.0, 2.0, -1.0]], [[4, -4.0, 4.0, -4.0, 7.0], [12, 2.0, 0.0, 3.0, 0.0], [31, -3.0, -6.0, 0.0, -3.0], [17, 2.0, -3.0, 2.0, -1.0]]], [[], [[4, 31], [12, 31]], 5]], [[[[8, -3.0, 4.0, 0.0, 6.0], [15, 2.0, -2.0, 4.0, -2.0], [33, -1.0, 2.0, 0.0, 2.0], [10, 2.0, -3.0, 3.0, -1.0]], [[8, -1.0, 5.0, 2.0, 7.0], [15, -1.0, -2.0, 1.0, -2.0], [33, 0.0, 3.0, 1.0, 3.0], [10, -1.0, -4.0, 0.0, -2.0]]], [[], [], 10]], [[[[36, 4.0, -1.0, 5.0, 2.0], [8, 1.0, 3.0, 1.0, 5.0], [7, -3.0, 0.0, -1.0, 3.0], [28, 1.0, 4.0, 4.0, 5.0], [2, -5.0, -2.0, -4.0, 0.0], [23, 2.0, 1.0, 4.0, 1.0]], [[36, 3.0, -2.0, 4.0, 1.0], [8, 5.0, 3.0, 5.0, 5.0], [7, -3.0, 0.0, -1.0, 3.0], [28, 0.0, 3.0, 3.0, 4.0], [2, -3.0, -1.0, -2.0, 1.0], [23, 3.0, 1.0, 5.0, 1.0]]], [[[2, 7]], [[8, 28], [8, 36]], 12]], [[[[37, 3.0, -2.0, 5.0, -1.0], [14, -2.0, -4.0, 0.0, -2.0], [18, -5.0, 4.0, -2.0, 5.0]], [[37, 5.0, -1.0, 7.0, 0.0], [14, -3.0, -4.0, -1.0, -2.0], [18, -6.0, 4.0, -3.0, 5.0]]], [[], [], 0]], [[[[25, 2.0, 0.0, 5.0, 2.0], [26, -4.0, -3.0, -2.0, 0.0], [3, 4.0, 4.0, 6.0, 6.0], [30, 4.0, 0.0, 6.0, 2.0]], [[25, 3.0, 1.0, 6.0, 3.0], [26, -7.0, -4.0, -5.0, -1.0], [3, 4.0, 5.0, 6.0, 7.0], [30, 6.0, 0.0, 8.0, 2.0]]], [[], [], 0]], [[[[12, 2.0, -4.0, 4.0, -4.0], [39, -2.0, -1.0, 1.0, -1.0], [5, -5.0, 5.0, -5.0, 7.0]], [[12, 2.0, -5.0, 4.0, -5.0], [39, -2.0, 0.0, 1.0, 0.0], [5, -1.0, 5.0, -1.0, 7.0]]], [[], [], 2]], [[[[12, -1.0, 3.0, -1.0, 6.0], [1, -1.0, -4.0, 0.0, -3.0], [16, -3.0, -2.0, -2.0, -1.0], [30, 5.0, -4.0, 8.0, -3.0], [6, -2.0, 2.0, 1.0, 2.0]], [[12, 3.0, 3.0, 3.0, 6.0], [1, -1.0, -5.0, 0.0, -4.0], [16, 1.0, -2.0, 2.0, -1.0], [30, 9.0, -4.0, 12.0, -3.0], [6, -2.0, 2.0, 1.0, 2.0]]], [[], [[1, 12], [1, 16], [6, 12]], 10]], [[[[36, -1.0, -4.0, 1.0, -4.0], [9, -1.0, -2.0, 0.0, 1.0]], [[36, 1.0, -5.0, 3.0, -5.0], [9, 0.0, -1.0, 1.0, 2.0]]], [[], [], 0]]], [[[[[36, 5.0, -4.0, 6.0, -3.0], [6, 0.0, -2.0, 2.0, -2.0], [5, -5.0, -4.0, -4.0, -2.0], [3, 5.0, 4.0, 5.0, 4.0], [7, 0.0, 0.0, 3.0, 2.0], [28, 0.0, 0.0, 2.0, 0.0], [22, -4.0, -1.0, -4.0, 1.0]], [[36, 5.0, -3.0, 6.0, -2.0], [6, 0.0, -2.0, 2.0, -2.0], [5, -4.0, -4.0, -3.0, -2.0], [3, 6.0, 4.0, 6.0, 4.0], [7, 0.0, 1.0, 3.0, 3.0], [28, 4.0, 0.0, 6.0, 0.0], [22, -4.0, -1.0, -4.0, 1.0]]], [[], [[6, 28], [7, 28]], 7]], [[[[37, -5.0, -4.0, -2.0, -2.0], [1, 1.0, 2.0, 2.0, 3.0]], [[37, -5.0, -4.0, -2.0, -2.0], [1, 1.0, 3.0, 2.0, 4.0]]], [[], [], 0]], [[[[30, -1.0, -5.0, 0.0, -5.0], [20, 4.0, -5.0, 5.0, -4.0], [1, -1.0, -2.0, -1.0, -1.0], [12, -2.0, 1.0, -2.0, 2.0], [22, 1.0, 5.0, 2.0, 7.0]], [[30, -1.0, -6.0, 0.0, -6.0], [20, 3.0, -6.0, 4.0, -5.0], [1, -1.0, -1.0, -1.0, 0.0], [12, 0.0, 0.0, 0.0, 1.0], [22, 0.0, 5.0, 1.0, 7.0]]], [[[1, 12]], [[1, 12]], 8]], [[[[25, -3.0, 5.0, -1.0, 8.0], [9, -1.0, -4.0, 0.0, -3.0], [21, 0.0, -1.0, 3.0, 0.0], [3, 0.0, 3.0, 0.0, 5.0], [4, 4.0, -2.0, 6.0, -2.0]], [[25, -3.0, 4.0, -1.0, 7.0], [9, 1.0, -4.0, 2.0, -3.0], [21, 2.0, -2.0, 5.0, -1.0], [3, 0.0, 4.0, 0.0, 6.0], [4, 4.0, -2.0, 6.0, -2.0]]], [[[4, 21]], [[3, 9], [3, 21], [9, 25]], 5]], [[[[22, -2.0, 0.0, 1.0, 0.0], [8, -1.0, -2.0, 0.0, -2.0], [2, 3.0, -1.0, 6.0, 0.0], [33, 2.0, 4.0, 4.0, 5.0], [9, 3.0, -4.0, 6.0, -3.0], [37, 1.0, -5.0, 2.0, -4.0], [32, -4.0, 0.0, -1.0, 0.0]], [[22, -5.0, 0.0, -2.0, 0.0], [8, -4.0, -3.0, -3.0, -3.0], [2, 0.0, 0.0, 3.0, 1.0], [33, 2.0, 5.0, 4.0, 6.0], [9, 3.0, -4.0, 6.0, -3.0], [37, 2.0, -4.0, 3.0, -3.0], [32, 0.0, 0.0, 3.0, 0.0]]], [[[2, 32], [9, 37]], [[8, 32], [22, 32], [22, 37]], 16]], [[[[17, -3.0, 5.0, 0.0, 7.0], [29, -3.0, 0.0, -3.0, 1.0], [20, 5.0, -3.0, 8.0, -2.0], [4, 3.0, -5.0, 5.0, -2.0], [2, -4.0, 0.0, -2.0, 2.0], [1, 1.0, -4.0, 4.0, -2.0], [24, 2.0, -2.0, 3.0, 0.0]], [[17, 1.0, 5.0, 4.0, 7.0], [29, -6.0, -1.0, -6.0, 0.0], [20, 5.0, -2.0, 8.0, -1.0], [4, 2.0, -6.0, 4.0, -3.0], [2, -4.0, 0.0, -2.0, 2.0], [1, 0.0, -5.0, 3.0, -3.0], [24, 2.0, -3.0, 3.0, -1.0]]], [[], [[2, 17], [2, 29], [4, 20], [17, 29]], 12]], [[[[30, 4.0, 3.0, 4.0, 3.0], [11, -1.0, 4.0, 1.0, 6.0], [29, -3.0, -3.0, -3.0, 0.0], [18, -1.0, -4.0, 0.0, -2.0], [31, -1.0, 5.0, 2.0, 7.0], [21, -1.0, 0.0, -1.0, 3.0]], [[30, 3.0, 3.0, 3.0, 3.0], [11, 3.0, 3.0, 5.0, 5.0], [29, -3.0, -2.0, -3.0, 1.0], [18, 0.0, -4.0, 1.0, -2.0], [31, -1.0, 5.0, 2.0, 7.0], [21, 0.0, 0.0, 0.0, 3.0]]], [[[11, 30]], [[11, 18], [11, 21], [11, 31]], 11]], [[[[26, -5.0, 4.0, -4.0, 6.0], [30, -2.0, 0.0, 0.0, 3.0], [39, -5.0, -2.0, -2.0, -2.0]], [[26, -1.0, 4.0, 0.0, 6.0], [30, -2.0, -1.0, 0.0, 2.0], [39, -8.0, -1.0, -5.0, -1.0]]], [[], [[26, 39], [30, 39]], 6]]], [[[[[8, -4.0, 4.0, -2.0, 4.0], [32, 2.0, -2.0, 4.0, -1.0], [1, -2.0, -1.0, -1.0, 0.0], [38, -5.0, 3.0, -5.0, 3.0], [35, -4.0, 4.0, -2.0, 7.0], [11, -4.0, -5.0, -3.0, -2.0], [12, 2.0, -2.0, 4.0, 1.0]], [[8, -3.0, 3.0, -1.0, 3.0], [32, -1.0, -3.0, 1.0, -2.0], [1, -5.0, 0.0, -4.0, 1.0], [38, -5.0, 3.0, -5.0, 3.0], [35, -4.0, 3.0, -2.0, 6.0], [11, -4.0, -6.0, -3.0, -3.0], [12, 3.0, -3.0, 5.0, 0.0]]], [[], [[1, 8], [12, 32]], 16]], [[[[17, -5.0, 4.0, -2.0, 6.0], [5, -2.0, -5.0, -1.0, -3.0], [22, -1.0, 0.0, 0.0, 2.0], [1, -3.0, 1.0, 0.0, 2.0], [12, -3.0, 1.0, -1.0, 4.0], [33, 3.0, 2.0, 4.0, 5.0], [19, -5.0, 5.0, -2.0, 7.0]], [[17, -3.0, 4.0, 0.0, 6.0], [5, -1.0, -4.0, 0.0, -2.0], [22, -4.0, -1.0, -3.0, 1.0], [1, -2.0, 1.0, 1.0, 2.0], [12, -3.0, 0.0, -1.0, 3.0], [33, 5.0, 3.0, 6.0, 6.0], [19, -5.0, 5.0, -2.0, 7.0]]], [[], [[1, 22], [5, 19], [5, 22]], 19]], [[[[8, 5.0, 2.0, 8.0, 5.0], [13, 2.0, -4.0, 3.0, -1.0]], [[8, 2.0, 3.0, 5.0, 6.0], [13, 1.0, -4.0, 2.0, -1.0]]], [[], [], 1]], [[[[3, -1.0, -1.0, 2.0, 2.0], [10, -5.0, -3.0, -5.0, -1.0]], [[3, -2.0, -1.0, 1.0, 2.0], [10, -4.0, -4.0, -4.0, -2.0]]], [[], [], 0]], [[[[8, 4.0, 5.0, 4.0, 5.0], [25, 2.0, -5.0, 5.0, -3.0], [26, 3.0, 5.0, 6.0, 7.0], [35, -5.0, 2.0, -3.0, 4.0], [22, 4.0, -4.0, 6.0, -3.0], [5, -5.0, -4.0, -3.0, -4.0]], [[8, 4.0, 5.0, 4.0, 5.0], [25, 3.0, -5.0, 6.0, -3.0], [26, 4.0, 6.0, 7.0, 8.0], [35, -5.0, 1.0, -3.0, 3.0], [22, 3.0, -4.0, 5.0, -3.0], [5, -6.0, -4.0, -4.0, -4.0]]], [[], [], 3]], [[[[22, 0.0, 3.0, 1.0, 4.0], [36, 3.0, -5.0, 3.0, -2.0]], [[22, 0.0, 3.0, 1.0, 4.0], [36, 0.0, -5.0, 0.0, -2.0]]], [[], [], 2]], [[[[29, 4.0, 4.0, 6.0, 5.0], [28, 4.0, 5.0, 6.0, 7.0], [15, 3.0, -4.0, 3.0, -4.0], [20, -2.0, 2.0, -2.0, 3.0], [25, -2.0, 2.0, 0.0, 4.0], [6, -3.0, 1.0, -1.0, 3.0], [35, -4.0, 4.0, -3.0, 7.0]], [[29, 8.0, 4.0, 10.0, 5.0], [28, 5.0, 5.0, 7.0, 7.0], [15, 3.0, -4.0, 3.0, -4.0], [20, -5.0, 3.0, -5.0, 4.0], [25, -1.0, 2.0, 1.0, 4.0], [6, 1.0, 1.0, 3.0, 3.0], [35, -2.0, 4.0, -1.0, 7.0]]], [[[20, 35], [25, 35]], [[6, 20], [6, 35], [20, 25], [20, 35], [28, 29]], 13]], [[[[3, -5.0, -3.0, -3.0, 0.0], [10, 1.0, 3.0, 3.0, 4.0], [38, -5.0, 5.0, -4.0, 6.0]], [[3, -8.0, -2.0, -6.0, 1.0], [10, -2.0, 4.0, 0.0, 5.0], [38, -4.0, 5.0, -3.0, 6.0]]], [[], [[3, 38]], 2]]], [[[[[31, -5.0, -2.0, -3.0, -1.0], [2, -3.0, 3.0, -3.0, 6.0], [24, 5.0, -5.0, 7.0, -3.0]], [[31, -5.0, -2.0, -3.0, -1.0], [2, -3.0, 3.0, -3.0, 6.0], [24, 6.0, -5.0, 8.0, -3.0]]], [[], [], 0]], [[[[17, 5.0, -3.0, 5.0, -1.0], [13, -5.0, 3.0, -2.0, 3.0], [28, -5.0, 1.0, -5.0, 3.0], [5, 3.0, 5.0, 6.0, 7.0], [7, -1.0, -2.0, 1.0, 1.0], [10, 4.0, 3.0, 7.0, 6.0], [1, 4.0, -5.0, 5.0, -2.0], [3, -3.0, -5.0, -1.0, -2.0], [11, 0.0, -2.0, 1.0, 0.0]], [[17, 6.0, -3.0, 6.0, -1.0], [13, -4.0, 3.0, -1.0, 3.0], [28, -5.0, 1.0, -5.0, 3.0], [5, 4.0, 4.0, 7.0, 6.0], [7, -2.0, -2.0, 0.0, 1.0], [10, 4.0, 4.0, 7.0, 7.0], [1, 4.0, -6.0, 5.0, -3.0], [3, -4.0, -5.0, -2.0, -2.0], [11, 0.0, -2.0, 1.0, 0.0]]], [[], [[1, 17], [13, 28]], 5]], [[[[24, 2.0, -2.0, 3.0, -2.0], [2, 0.0, -4.0, 1.0, -4.0], [22, -2.0, -2.0, -1.0, -1.0], [20, 3.0, -5.0, 5.0, -4.0], [10, 3.0, 3.0, 6.0, 4.0], [30, -5.0, 2.0, -4.0, 4.0], [4, 3.0, -2.0, 6.0, -2.0]], [[24, -1.0, -2.0, 0.0, -2.0], [2, 0.0, -5.0, 1.0, -5.0], [22, -2.0, -2.0, -1.0, -1.0], [20, 4.0, -5.0, 6.0, -4.0], [10, 3.0, 2.0, 6.0, 3.0], [30, -5.0, 2.0, -4.0, 4.0], [4, 0.0, -2.0, 3.0, -2.0]]], [[[22, 24]], [[4, 20], [10, 24], [20, 24]], 9]], [[[[6, 0.0, -2.0, 0.0, -2.0], [11, -2.0, 0.0, -2.0, 3.0], [39, 4.0, 0.0, 7.0, 3.0]], [[6, 1.0, -2.0, 1.0, -2.0], [11, 2.0, 1.0, 2.0, 4.0], [39, 4.0, 0.0, 7.0, 3.0]]], [[], [[6, 11]], 4]], [[[[18, -1.0, 3.0, 0.0, 4.0], [39, 5.0, 0.0, 7.0, 2.0], [2, -1.0, 1.0, -1.0, 4.0], [19, -4.0, 3.0, -3.0, 3.0], [27, -2.0, 3.0, -1.0, 6.0], [10, -3.0, -2.0, -2.0, -1.0]], [[18, 1.0, 3.0, 2.0, 4.0], [39, 2.0, 0.0, 4.0, 2.0], [2, 1.0, 1.0, 1.0, 4.0], [19, -4.0, 3.0, -3.0, 3.0], [27, 2.0, 4.0, 3.0, 7.0], [10, -3.0, -3.0, -2.0, -2.0]]], [[], [[2, 27], [10, 27]], 7]], [[[[24, -2.0, -3.0, 0.0, -1.0], [32, 0.0, -3.0, 2.0, 0.0]], [[24, 2.0, -2.0, 4.0, 0.0], [32, 4.0, -3.0, 6.0, 0.0]]], [[], [], 0]], [[[[29, -4.0, -1.0, -3.0, -1.0], [14, 4.0, -5.0, 6.0, -5.0], [20, 2.0, -4.0, 2.0, -3.0]], [[29, -7.0, 0.0, -6.0, 0.0], [14, 4.0, -4.0, 6.0, -4.0], [20, -1.0, -4.0, -1.0, -3.0]]], [[], [], 0]], [[[[15, -4.0, 5.0, -1.0, 6.0], [21, -2.0, 1.0, -1.0, 2.0], [16, 5.0, 2.0, 8.0, 3.0], [39, 1.0, 1.0, 4.0, 1.0], [27, 1.0, -3.0, 1.0, -2.0], [12, 5.0, -5.0, 8.0, -5.0]], [[15, -4.0, 4.0, -1.0, 5.0], [21, -1.0, 1.0, 0.0, 2.0], [16, 6.0, 2.0, 9.0, 3.0], [39, 3.0, 1.0, 6.0, 1.0], [27, 3.0, -3.0, 3.0, -2.0], [12, 5.0, -5.0, 8.0, -5.0]]], [[], [], 2]]], [[[[[28, 2.0, 2.0, 5.0, 2.0], [24, -3.0, 4.0, -3.0, 4.0], [29, -5.0, 4.0, -4.0, 5.0], [10, 1.0, 1.0, 4.0, 2.0], [33, -2.0, -4.0, -1.0, -3.0], [12, 2.0, 3.0, 2.0, 3.0], [39, -5.0, -3.0, -2.0, -2.0], [1, 3.0, -5.0, 4.0, -4.0]], [[28, 2.0, 2.0, 5.0, 2.0], [24, -4.0, 5.0, -4.0, 5.0], [29, -6.0, 3.0, -5.0, 4.0], [10, 3.0, 1.0, 6.0, 2.0], [33, -3.0, -4.0, -2.0, -3.0], [12, 4.0, 3.0, 4.0, 3.0], [39, -3.0, -2.0, 0.0, -1.0], [1, 2.0, -5.0, 3.0, -4.0]]], [[], [[1, 12], [24, 39], [29, 39]], 12]], [[[[37, 0.0, -3.0, 3.0, -3.0], [2, 3.0, -2.0, 5.0, -2.0], [35, 5.0, 2.0, 7.0, 3.0]], [[37, 2.0, -3.0, 5.0, -3.0], [2, 3.0, -3.0, 5.0, -3.0], [35, 5.0, 3.0, 7.0, 4.0]]], [[], [], 1]], [[[[15, 0.0, 0.0, 2.0, 0.0], [18, 3.0, 0.0, 4.0, 1.0], [30, 1.0, -3.0, 1.0, -2.0], [24, -5.0, -4.0, -5.0, -3.0], [32, 5.0, -3.0, 8.0, -2.0]], [[15, 2.0, -1.0, 4.0, -1.0], [18, 7.0, -1.0, 8.0, 0.0], [30, 1.0, -3.0, 1.0, -2.0], [24, -6.0, -3.0, -6.0, -2.0], [32, 7.0, -2.0, 10.0, -1.0]]], [[[18, 32]], [[15, 30]], 3]], [[[[29, 3.0, 3.0, 3.0, 6.0], [20, 4.0, 4.0, 5.0, 7.0], [7, 3.0, 2.0, 4.0, 4.0], [21, 3.0, -1.0, 5.0, 0.0]], [[29, 3.0, 2.0, 3.0, 5.0], [20, 5.0, 5.0, 6.0, 8.0], [7, 4.0, 3.0, 5.0, 5.0], [21, 2.0, -2.0, 4.0, -1.0]]], [[], [[7, 29], [20, 21]], 6]], [[[[25, 0.0, 3.0, 2.0, 3.0], [27, 0.0, 5.0, 0.0, 5.0], [33, -1.0, -5.0, 1.0, -4.0], [9, -5.0, 4.0, -5.0, 6.0], [21, 3.0, 4.0, 6.0, 6.0], [18, -2.0, -2.0, -2.0, -1.0], [39, -2.0, -3.0, 0.0, 0.0], [20, 3.0, -3.0, 3.0, -3.0], [2, -1.0, 0.0, 2.0, 1.0]], [[25, 0.0, 4.0, 2.0, 4.0], [27, 4.0, 6.0, 4.0, 6.0], [33, 1.0, -5.0, 3.0, -4.0], [9, -5.0, 5.0, -5.0, 7.0], [21, 4.0, 5.0, 7.0, 7.0], [18, -1.0, -2.0, -1.0, -1.0], [39, -5.0, -3.0, -3.0, 0.0], [20, 3.0, -2.0, 3.0, -2.0], [2, 3.0, 0.0, 6.0, 1.0]]], [[[21, 27]], [[2, 25], [2, 39], [18, 39], [20, 21], [20, 27], [25, 27], [25, 39], [27, 33], [27, 39], [33, 39]], 29]], [[[[17, 3.0, 1.0, 4.0, 2.0], [20, -2.0, -3.0, -1.0, -3.0], [27, 3.0, 5.0, 6.0, 8.0], [30, -3.0, 3.0, 0.0, 6.0], [6, -4.0, -4.0, -4.0, -1.0]], [[17, 3.0, 1.0, 4.0, 2.0], [20, -2.0, -4.0, -1.0, -4.0], [27, 0.0, 6.0, 3.0, 9.0], [30, -1.0, 4.0, 2.0, 7.0], [6, -7.0, -4.0, -7.0, -1.0]]], [[[27, 30]], [], 4]], [[[[22, 2.0, -1.0, 3.0, -1.0], [14, -2.0, -2.0, -1.0, 0.0], [17, 1.0, -2.0, 2.0, 0.0], [1, 0.0, -2.0, 3.0, -1.0], [16, 2.0, 3.0, 3.0, 4.0], [33, 1.0, 4.0, 3.0, 7.0], [24, 0.0, 3.0, 0.0, 6.0], [3, 3.0, -5.0, 4.0, -5.0], [38, 0.0, 3.0, 0.0, 3.0]], [[22, 2.0, -1.0, 3.0, -1.0], [14, -5.0, -2.0, -4.0, 0.0], [17, 3.0, -1.0, 4.0, 1.0], [1, 1.0, -2.0, 4.0, -1.0], [16, 4.0, 4.0, 5.0, 5.0], [33, 1.0, 4.0, 3.0, 7.0], [24, 2.0, 3.0, 2.0, 6.0], [3, 7.0, -4.0, 8.0, -4.0], [38, 2.0, 3.0, 2.0, 3.0]]], [[[24, 33]], [[1, 3], [3, 16], [3, 22], [3, 33], [16, 22], [16, 33]], 21]], [[[[20, -3.0, 1.0, -1.0, 4.0], [37, 3.0, 1.0, 4.0, 1.0], [3, 5.0, -1.0, 5.0, 2.0], [12, -4.0, 2.0, -4.0, 4.0], [21, -1.0, -2.0, 2.0, -1.0], [33, 2.0, 2.0, 5.0, 3.0], [6, 1.0, -2.0, 2.0, 0.0], [36, 3.0, 0.0, 3.0, 3.0]], [[20, 1.0, 0.0, 3.0, 3.0], [37, 4.0, 1.0, 5.0, 1.0], [3, 4.0, -1.0, 4.0, 2.0], [12, -5.0, 3.0, -5.0, 5.0], [21, -1.0, -1.0, 2.0, 0.0], [33, 1.0, 2.0, 4.0, 3.0], [6, 1.0, -3.0, 2.0, -1.0], [36, 0.0, 1.0, 0.0, 4.0]]], [[[3, 37], [20, 33], [20, 36]], [[6, 36], [20, 36], [33, 36], [36, 37]], 21]]]]\nfor i, (args, expected) in enumerate(fixtures[N-1]):\n    check(\"case %d\" % i, solve(*args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"}},"limitations":"A deterministic bounded teaching model with stipulated toy conventions; not a production physics engine or spatial index. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.","method":"Deterministic executable model with adversarial boundary fixtures.","provenance":{"created_by":"Failure Map","dependencies":"Python standard library","family":"w2-collision_detection_broadphase-incremental-sap-swaps-begin-secondary-check","generated_at":"2026-09-29T14:51:02.181387+00:00","license":"CC0-1.0","python":"3.12.14","seed":1,"split":"open-access"},"relevance":"Broadphase stages decide which object pairs ever reach narrowphase; a wrong boundary, ordering or bookkeeping rule silently drops real contacts or floods the solver with false candidates.","repair":"Begin only when y intervals overlap in the new frame.","root_cause":"Every min-over-max swap adds a begin pair.","sha256":"7ddeb8bff1a19b191ff94297a71ff190db76c5addffa6438662f0c4d0ad32446","title":"Swap-begin events skip the y overlap check · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verification":{"attempt":{"elapsed_ms":43.912,"exit_code":1,"observations":[{"actual":[[[12,17]],[[4,31],[12,31]],5],"check":"case 0","expected":[[],[[4,31],[12,31]],5],"passed":false},{"actual":[[[8,10],[8,15],[10,33],[15,33]],[],10],"check":"case 1","expected":[[],[],10],"passed":false},{"actual":[[[2,7],[8,23],[8,36]],[[8,28],[8,36]],12],"check":"case 2","expected":[[[2,7]],[[8,28],[8,36]],12],"passed":false},{"actual":[[],[],0],"check":"case 3","expected":[[],[],0],"passed":true},{"actual":[[],[],0],"check":"case 4","expected":[[],[],0],"passed":true},{"actual":[[[5,39]],[],2],"check":"case 5","expected":[[],[],2],"passed":false},{"actual":[[[1,16]],[[1,12],[1,16],[6,12]],10],"check":"case 6","expected":[[],[[1,12],[1,16],[6,12]],10],"passed":false},{"actual":[[],[],0],"check":"case 7","expected":[[],[],0],"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"case 0\", \"actual\": [[[12, 17]], [[4, 31], [12, 31]], 5], \"expected\": [[], [[4, 31], [12, 31]], 5], \"passed\": false}, {\"check\": \"case 1\", \"actual\": [[[8, 10], [8, 15], [10, 33], [15, 33]], [], 10], \"expected\": [[], [], 10], \"passed\": false}, {\"check\": \"case 2\", \"actual\": [[[2, 7], [8, 23], [8, 36]], [[8, 28], [8, 36]], 12], \"expected\": [[[2, 7]], [[8, 28], [8, 36]], 12], \"passed\": false}, {\"check\": \"case 3\", \"actual\": [[], [], 0], \"expected\": [[], [], 0], \"passed\": true}, {\"check\": \"case 4\", \"actual\": [[], [], 0], \"expected\": [[], [], 0], \"passed\": true}, {\"check\": \"case 5\", \"actual\": [[[5, 39]], [], 2], \"expected\": [[], [], 2], \"passed\": false}, {\"check\": \"case 6\", \"actual\": [[[1, 16]], [[1, 12], [1, 16], [6, 12]], 10], \"expected\": [[], [[1, 12], [1, 16], [6, 12]], 10], \"passed\": false}, {\"check\": \"case 7\", \"actual\": [[], [], 0], \"expected\": [[], [], 0], \"passed\": true}], \"passed\": false}\n"},"broken":{"elapsed_ms":45.92,"exit_code":1,"observations":[{"actual":[[[12,17]],[[4,31],[12,31]],5],"check":"case 0","expected":[[],[[4,31],[12,31]],5],"passed":false},{"actual":[[[8,10],[8,15],[10,33],[15,33]],[],10],"check":"case 1","expected":[[],[],10],"passed":false},{"actual":[[[2,7],[8,23],[8,36]],[[8,28],[8,36]],12],"check":"case 2","expected":[[[2,7]],[[8,28],[8,36]],12],"passed":false},{"actual":[[],[],0],"check":"case 3","expected":[[],[],0],"passed":true},{"actual":[[],[],0],"check":"case 4","expected":[[],[],0],"passed":true},{"actual":[[[5,39]],[],2],"check":"case 5","expected":[[],[],2],"passed":false},{"actual":[[[1,16]],[[1,12],[1,16],[6,12]],10],"check":"case 6","expected":[[],[[1,12],[1,16],[6,12]],10],"passed":false},{"actual":[[],[],0],"check":"case 7","expected":[[],[],0],"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"case 0\", \"actual\": [[[12, 17]], [[4, 31], [12, 31]], 5], \"expected\": [[], [[4, 31], [12, 31]], 5], \"passed\": false}, {\"check\": \"case 1\", \"actual\": [[[8, 10], [8, 15], [10, 33], [15, 33]], [], 10], \"expected\": [[], [], 10], \"passed\": false}, {\"check\": \"case 2\", \"actual\": [[[2, 7], [8, 23], [8, 36]], [[8, 28], [8, 36]], 12], \"expected\": [[[2, 7]], [[8, 28], [8, 36]], 12], \"passed\": false}, {\"check\": \"case 3\", \"actual\": [[], [], 0], \"expected\": [[], [], 0], \"passed\": true}, {\"check\": \"case 4\", \"actual\": [[], [], 0], \"expected\": [[], [], 0], \"passed\": true}, {\"check\": \"case 5\", \"actual\": [[[5, 39]], [], 2], \"expected\": [[], [], 2], \"passed\": false}, {\"check\": \"case 6\", \"actual\": [[[1, 16]], [[1, 12], [1, 16], [6, 12]], 10], \"expected\": [[], [[1, 12], [1, 16], [6, 12]], 10], \"passed\": false}, {\"check\": \"case 7\", \"actual\": [[], [], 0], \"expected\": [[], [], 0], \"passed\": true}], \"passed\": false}\n"},"fixed":{"elapsed_ms":46.455,"exit_code":0,"observations":[{"actual":[[],[[4,31],[12,31]],5],"check":"case 0","expected":[[],[[4,31],[12,31]],5],"passed":true},{"actual":[[],[],10],"check":"case 1","expected":[[],[],10],"passed":true},{"actual":[[[2,7]],[[8,28],[8,36]],12],"check":"case 2","expected":[[[2,7]],[[8,28],[8,36]],12],"passed":true},{"actual":[[],[],0],"check":"case 3","expected":[[],[],0],"passed":true},{"actual":[[],[],0],"check":"case 4","expected":[[],[],0],"passed":true},{"actual":[[],[],2],"check":"case 5","expected":[[],[],2],"passed":true},{"actual":[[],[[1,12],[1,16],[6,12]],10],"check":"case 6","expected":[[],[[1,12],[1,16],[6,12]],10],"passed":true},{"actual":[[],[],0],"check":"case 7","expected":[[],[],0],"passed":true}],"passed":true,"stderr":"","stdout":"{\"observations\": [{\"check\": \"case 0\", \"actual\": [[], [[4, 31], [12, 31]], 5], \"expected\": [[], [[4, 31], [12, 31]], 5], \"passed\": true}, {\"check\": \"case 1\", \"actual\": [[], [], 10], \"expected\": [[], [], 10], \"passed\": true}, {\"check\": \"case 2\", \"actual\": [[[2, 7]], [[8, 28], [8, 36]], 12], \"expected\": [[[2, 7]], [[8, 28], [8, 36]], 12], \"passed\": true}, {\"check\": \"case 3\", \"actual\": [[], [], 0], \"expected\": [[], [], 0], \"passed\": true}, {\"check\": \"case 4\", \"actual\": [[], [], 0], \"expected\": [[], [], 0], \"passed\": true}, {\"check\": \"case 5\", \"actual\": [[], [], 2], \"expected\": [[], [], 2], \"passed\": true}, {\"check\": \"case 6\", \"actual\": [[], [[1, 12], [1, 16], [6, 12]], 10], \"expected\": [[], [[1, 12], [1, 16], [6, 12]], 10], \"passed\": true}, {\"check\": \"case 7\", \"actual\": [[], [], 0], \"expected\": [[], [], 0], \"passed\": true}], \"passed\": true}\n"}},"verified":true,"visibility":"public"}