{"abstract":"The same pair appears as both (a,b) and (b,a).","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":"Using (f id, e id) is equally orientation dependent.","family":"w2-collision_detection_broadphase-incremental-sap-swaps-event-pair-orientation","id":"FA-87811","implementations":{"attempt":{"sha256":"c04bdb571d8c42cb9ccb8ad496bee7dcb3169031cb6ed6792c6d5b9d7ad59d72","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 = (f[2], e[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 = [[[[[[27, 0.0, -1.0, 1.0, 1.0], [2, -2.0, 3.0, 1.0, 3.0], [10, -3.0, 0.0, 0.0, 0.0], [32, 2.0, -2.0, 2.0, 1.0], [14, -4.0, 4.0, -3.0, 4.0], [21, 5.0, 5.0, 6.0, 6.0]], [[27, 0.0, -1.0, 1.0, 1.0], [2, 2.0, 3.0, 5.0, 3.0], [10, 1.0, 0.0, 4.0, 0.0], [32, 2.0, -3.0, 2.0, 0.0], [14, -3.0, 5.0, -2.0, 5.0], [21, 2.0, 6.0, 3.0, 7.0]]], [[[10, 32]], [[2, 27], [10, 14]], 15]], [[[[20, -5.0, 5.0, -2.0, 6.0], [5, 0.0, 5.0, 3.0, 7.0]], [[20, -1.0, 6.0, 2.0, 7.0], [5, 2.0, 5.0, 5.0, 7.0]]], [[[5, 20]], [], 1]], [[[[35, -4.0, 0.0, -3.0, 1.0], [4, -4.0, 0.0, -4.0, 3.0], [36, 5.0, -2.0, 5.0, 1.0], [25, 4.0, -1.0, 4.0, 1.0]], [[35, -7.0, -1.0, -6.0, 0.0], [4, -4.0, 0.0, -4.0, 3.0], [36, 7.0, -2.0, 7.0, 1.0], [25, 4.0, 0.0, 4.0, 2.0]]], [[], [[4, 35]], 3]], [[[[5, -2.0, -3.0, -1.0, -3.0], [22, 4.0, -1.0, 6.0, 2.0], [14, -2.0, 3.0, 1.0, 4.0], [8, -4.0, 1.0, -1.0, 3.0], [21, 4.0, 0.0, 4.0, 2.0]], [[5, -2.0, -3.0, -1.0, -3.0], [22, 8.0, -2.0, 10.0, 1.0], [14, -1.0, 3.0, 2.0, 4.0], [8, 0.0, 2.0, 3.0, 4.0], [21, 5.0, 1.0, 5.0, 3.0]]], [[], [[5, 8], [21, 22]], 5]], [[[[30, 2.0, 2.0, 3.0, 2.0], [11, 4.0, -1.0, 4.0, 1.0], [13, 5.0, 4.0, 6.0, 7.0], [4, 3.0, -1.0, 4.0, 1.0]], [[30, 6.0, 1.0, 7.0, 1.0], [11, 8.0, 0.0, 8.0, 2.0], [13, 9.0, 4.0, 10.0, 7.0], [4, 3.0, -2.0, 4.0, 0.0]]], [[], [[4, 11], [4, 30]], 4]], [[[[29, -1.0, -2.0, 2.0, 1.0], [38, 5.0, 1.0, 5.0, 3.0], [28, 3.0, -3.0, 3.0, -2.0], [17, 5.0, 1.0, 8.0, 3.0], [9, -5.0, -2.0, -4.0, 0.0]], [[29, 1.0, -1.0, 4.0, 2.0], [38, 9.0, 1.0, 9.0, 3.0], [28, 2.0, -2.0, 2.0, -1.0], [17, 2.0, 1.0, 5.0, 3.0], [9, -1.0, -1.0, 0.0, 1.0]]], [[[17, 29], [28, 29]], [[17, 38]], 6]], [[[[32, -2.0, -1.0, -2.0, 2.0], [33, 1.0, -4.0, 2.0, -2.0], [12, 3.0, 1.0, 5.0, 2.0], [5, 1.0, 5.0, 3.0, 7.0]], [[32, -1.0, -1.0, -1.0, 2.0], [33, 1.0, -5.0, 2.0, -3.0], [12, 7.0, 1.0, 9.0, 2.0], [5, -2.0, 6.0, 0.0, 8.0]]], [[], [[5, 12], [5, 33]], 5]], [[[[2, 0.0, 5.0, 3.0, 8.0], [38, 5.0, -5.0, 5.0, -3.0], [19, -2.0, 0.0, -2.0, 0.0], [10, -1.0, -4.0, 1.0, -1.0], [29, 3.0, -5.0, 3.0, -3.0]], [[2, -1.0, 4.0, 2.0, 7.0], [38, 4.0, -5.0, 4.0, -3.0], [19, -2.0, 0.0, -2.0, 0.0], [10, -1.0, -5.0, 1.0, -2.0], [29, 7.0, -4.0, 7.0, -2.0]]], [[[29, 38]], [[2, 29], [29, 38]], 5]]], [[[[[10, 1.0, -3.0, 3.0, -3.0], [33, 1.0, 0.0, 4.0, 2.0], [16, -2.0, 4.0, -2.0, 7.0], [38, -3.0, 1.0, -2.0, 3.0]], [[10, 1.0, -3.0, 3.0, -3.0], [33, 2.0, 0.0, 5.0, 2.0], [16, -2.0, 4.0, -2.0, 7.0], [38, -1.0, 1.0, 0.0, 3.0]]], [[], [[16, 38]], 2]], [[[[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]], [[[[1, -3.0, 0.0, -1.0, 3.0], [27, -3.0, 5.0, -1.0, 7.0], [23, -5.0, 0.0, -5.0, 0.0], [36, 0.0, 3.0, 0.0, 3.0], [33, -1.0, -4.0, 1.0, -2.0], [32, 4.0, -1.0, 5.0, 1.0]], [[1, -6.0, 0.0, -4.0, 3.0], [27, -3.0, 5.0, -1.0, 7.0], [23, -1.0, 0.0, -1.0, 0.0], [36, 4.0, 2.0, 4.0, 2.0], [33, -2.0, -3.0, 0.0, -1.0], [32, 4.0, 0.0, 5.0, 2.0]]], [[[1, 23], [32, 36]], [[1, 23], [1, 27], [1, 33], [33, 36]], 13]], [[[[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]], [[[[12, -2.0, 0.0, 0.0, 2.0], [19, 0.0, -5.0, 3.0, -5.0], [10, -1.0, -4.0, 0.0, -2.0], [39, 4.0, -3.0, 7.0, -1.0], [17, -4.0, 1.0, -2.0, 4.0], [28, -2.0, -5.0, -1.0, -3.0], [35, 0.0, 5.0, 3.0, 6.0]], [[12, -1.0, -1.0, 1.0, 1.0], [19, 4.0, -5.0, 7.0, -5.0], [10, 1.0, -3.0, 2.0, -1.0], [39, 3.0, -2.0, 6.0, 0.0], [17, -3.0, 1.0, -1.0, 4.0], [28, -3.0, -5.0, -2.0, -3.0], [35, -3.0, 5.0, 0.0, 6.0]]], [[], [[10, 19], [10, 28], [10, 35], [12, 19], [12, 28], [19, 35]], 20]], [[[[32, 1.0, 5.0, 2.0, 6.0], [6, 0.0, 5.0, 2.0, 5.0], [9, 0.0, -2.0, 3.0, 1.0], [24, -5.0, 0.0, -3.0, 3.0]], [[32, -2.0, 6.0, -1.0, 7.0], [6, 1.0, 4.0, 3.0, 4.0], [9, 4.0, -1.0, 7.0, 2.0], [24, -5.0, 1.0, -3.0, 4.0]]], [[], [[6, 9], [6, 32], [9, 32]], 6]], [[[[23, -4.0, 0.0, -1.0, 1.0], [13, -4.0, -2.0, -4.0, 1.0], [6, -2.0, -5.0, 0.0, -3.0], [8, 5.0, 2.0, 5.0, 3.0], [9, -5.0, 0.0, -4.0, 2.0]], [[23, -7.0, 0.0, -4.0, 1.0], [13, -5.0, -1.0, -5.0, 2.0], [6, 0.0, -5.0, 2.0, -3.0], [8, 5.0, 3.0, 5.0, 4.0], [9, -8.0, 1.0, -7.0, 3.0]]], [[], [[6, 23], [9, 13]], 3]], [[[[6, 5.0, 4.0, 5.0, 7.0], [38, -3.0, 0.0, 0.0, 3.0], [18, -5.0, -3.0, -4.0, -2.0], [9, -5.0, 5.0, -5.0, 7.0], [27, 0.0, 4.0, 1.0, 6.0]], [[6, 7.0, 4.0, 7.0, 7.0], [38, -3.0, 0.0, 0.0, 3.0], [18, -4.0, -3.0, -3.0, -2.0], [9, -5.0, 5.0, -5.0, 7.0], [27, -1.0, 4.0, 0.0, 6.0]]], [[], [[9, 18]], 2]]], [[[[[39, 3.0, 1.0, 6.0, 4.0], [22, -5.0, 4.0, -4.0, 7.0], [27, 2.0, -5.0, 5.0, -5.0]], [[39, 3.0, 2.0, 6.0, 5.0], [22, -5.0, 3.0, -4.0, 6.0], [27, 6.0, -4.0, 9.0, -4.0]]], [[], [], 2]], [[[[2, 3.0, -2.0, 4.0, 1.0], [32, 3.0, 5.0, 6.0, 7.0], [14, 1.0, -3.0, 2.0, -3.0], [25, -1.0, -2.0, 2.0, 1.0], [24, -1.0, -2.0, 0.0, 0.0], [29, 5.0, -2.0, 5.0, 0.0]], [[2, 0.0, -2.0, 1.0, 1.0], [32, 4.0, 4.0, 7.0, 6.0], [14, 2.0, -4.0, 3.0, -4.0], [25, 3.0, -2.0, 6.0, 1.0], [24, 1.0, -1.0, 2.0, 1.0], [29, 9.0, -2.0, 9.0, 0.0]]], [[[2, 24], [2, 25]], [[2, 14], [2, 25], [2, 32], [24, 25], [29, 32]], 18]], [[[[26, -5.0, -4.0, -2.0, -2.0], [6, 4.0, 1.0, 5.0, 2.0], [18, -2.0, 2.0, -2.0, 2.0], [24, -4.0, -5.0, -2.0, -3.0], [19, -5.0, -2.0, -4.0, -1.0]], [[26, -6.0, -4.0, -3.0, -2.0], [6, 1.0, 1.0, 2.0, 2.0], [18, -5.0, 2.0, -5.0, 2.0], [24, -5.0, -5.0, -3.0, -3.0], [19, -3.0, -2.0, -2.0, -1.0]]], [[], [[18, 19]], 8]], [[[[18, -4.0, -5.0, -3.0, -4.0], [26, 4.0, -4.0, 6.0, -1.0], [8, -4.0, -4.0, -2.0, -3.0], [7, 5.0, 1.0, 5.0, 1.0], [3, 1.0, -2.0, 4.0, 0.0], [23, 2.0, -5.0, 2.0, -2.0]], [[18, -2.0, -6.0, -1.0, -5.0], [26, 5.0, -4.0, 7.0, -1.0], [8, -2.0, -5.0, 0.0, -4.0], [7, 5.0, 1.0, 5.0, 1.0], [3, 5.0, -3.0, 8.0, -1.0], [23, 1.0, -4.0, 1.0, -1.0]]], [[], [[3, 23]], 5]], [[[[13, 5.0, -2.0, 6.0, 0.0], [39, 4.0, 5.0, 7.0, 7.0], [11, 0.0, 5.0, 3.0, 5.0], [10, 3.0, -4.0, 4.0, -3.0], [18, -2.0, -4.0, -1.0, -2.0], [30, -3.0, -4.0, -1.0, -1.0], [36, 1.0, 1.0, 3.0, 3.0]], [[13, 2.0, -3.0, 3.0, -1.0], [39, 1.0, 5.0, 4.0, 7.0], [11, -3.0, 6.0, 0.0, 6.0], [10, 5.0, -5.0, 6.0, -4.0], [18, -2.0, -3.0, -1.0, -1.0], [30, 1.0, -5.0, 3.0, -2.0], [36, 2.0, 0.0, 4.0, 2.0]]], [[[13, 30]], [[10, 11], [10, 13], [10, 36], [10, 39], [11, 30], [11, 36], [18, 30]], 25]], [[[[20, -2.0, -4.0, 0.0, -4.0], [8, 0.0, -2.0, 0.0, 0.0], [2, 0.0, -4.0, 2.0, -3.0], [14, 1.0, 5.0, 2.0, 7.0], [39, -4.0, 3.0, -4.0, 5.0], [18, -3.0, -5.0, -3.0, -3.0]], [[20, -2.0, -4.0, 0.0, -4.0], [8, -3.0, -1.0, -3.0, 1.0], [2, 0.0, -4.0, 2.0, -3.0], [14, 2.0, 4.0, 3.0, 6.0], [39, -4.0, 4.0, -4.0, 6.0], [18, 1.0, -4.0, 1.0, -2.0]]], [[[2, 18], [18, 20]], [[2, 8], [8, 18], [8, 20], [18, 20]], 14]], [[[[38, -3.0, -5.0, -3.0, -4.0], [10, 4.0, 1.0, 6.0, 3.0], [15, 1.0, 0.0, 3.0, 3.0], [23, -4.0, -2.0, -1.0, 0.0], [24, -1.0, 3.0, 2.0, 4.0], [14, 3.0, -4.0, 5.0, -3.0], [26, -2.0, 3.0, 1.0, 5.0], [20, -5.0, 4.0, -4.0, 5.0]], [[38, -6.0, -6.0, -6.0, -5.0], [10, 1.0, 0.0, 3.0, 2.0], [15, 1.0, 1.0, 3.0, 4.0], [23, 0.0, -2.0, 3.0, 0.0], [24, 0.0, 2.0, 3.0, 3.0], [14, 5.0, -5.0, 7.0, -4.0], [26, -2.0, 2.0, 1.0, 4.0], [20, -3.0, 5.0, -2.0, 6.0]]], [[[10, 15], [10, 23], [10, 24], [10, 26]], [[10, 14], [14, 15], [20, 23], [20, 38], [23, 38]], 19]], [[[[34, 3.0, 5.0, 3.0, 7.0], [13, -3.0, -2.0, 0.0, 1.0], [31, 0.0, 1.0, 3.0, 3.0]], [[34, 3.0, 5.0, 3.0, 7.0], [13, -3.0, -1.0, 0.0, 2.0], [31, 0.0, 2.0, 3.0, 4.0]]], [[], [], 0]]], [[[[[39, 5.0, 0.0, 5.0, 3.0], [11, -4.0, 0.0, -4.0, 1.0], [18, -4.0, 1.0, -3.0, 3.0], [12, -2.0, 5.0, 1.0, 8.0], [36, 3.0, 0.0, 5.0, 0.0]], [[39, 7.0, 0.0, 7.0, 3.0], [11, -3.0, -1.0, -3.0, 0.0], [18, -2.0, 0.0, -1.0, 2.0], [12, -5.0, 5.0, -2.0, 8.0], [36, 5.0, 0.0, 7.0, 0.0]]], [[], [[11, 18]], 6]], [[[[8, -1.0, -1.0, -1.0, -1.0], [9, 4.0, 0.0, 4.0, 3.0], [30, -3.0, 5.0, -1.0, 5.0], [32, 0.0, 2.0, 1.0, 5.0], [3, -3.0, 1.0, 0.0, 1.0], [18, -2.0, 4.0, -2.0, 7.0], [23, 5.0, 2.0, 5.0, 2.0], [39, -4.0, 4.0, -1.0, 5.0]], [[8, 0.0, -1.0, 0.0, -1.0], [9, 1.0, -1.0, 1.0, 2.0], [30, -6.0, 4.0, -4.0, 4.0], [32, -1.0, 1.0, 0.0, 4.0], [3, -3.0, 2.0, 0.0, 2.0], [18, -3.0, 4.0, -3.0, 7.0], [23, 5.0, 1.0, 5.0, 1.0], [39, -4.0, 3.0, -1.0, 4.0]]], [[[32, 39]], [[3, 30], [8, 30], [8, 39], [18, 30]], 12]], [[[[19, -5.0, 4.0, -3.0, 6.0], [29, 2.0, 0.0, 4.0, 0.0], [7, -5.0, 3.0, -4.0, 5.0], [11, 2.0, 3.0, 5.0, 3.0]], [[19, -3.0, 4.0, -1.0, 6.0], [29, -1.0, 1.0, 1.0, 1.0], [7, -1.0, 3.0, 0.0, 5.0], [11, 1.0, 3.0, 4.0, 3.0]]], [[], [], 5]], [[[[7, 3.0, -1.0, 3.0, 0.0], [27, -5.0, -5.0, -2.0, -2.0], [15, 3.0, 5.0, 5.0, 6.0], [31, -2.0, -2.0, -2.0, -1.0], [26, 4.0, 1.0, 4.0, 3.0], [30, 3.0, -4.0, 5.0, -3.0], [29, 4.0, 4.0, 7.0, 4.0], [1, -5.0, -5.0, -3.0, -3.0], [39, 3.0, -2.0, 3.0, 1.0]], [[7, 7.0, -1.0, 7.0, 0.0], [27, -4.0, -5.0, -1.0, -2.0], [15, 2.0, 4.0, 4.0, 5.0], [31, -5.0, -1.0, -5.0, 0.0], [26, 3.0, 1.0, 3.0, 3.0], [30, 4.0, -3.0, 6.0, -2.0], [29, 6.0, 3.0, 9.0, 3.0], [1, -1.0, -5.0, 1.0, -3.0], [39, 5.0, -3.0, 5.0, 0.0]]], [[], [[1, 31], [7, 15], [7, 26], [7, 30], [7, 39], [15, 29], [15, 39], [26, 29], [26, 30], [26, 39], [27, 31]], 34]], [[[[1, 5.0, -4.0, 6.0, -1.0], [27, -1.0, 3.0, 2.0, 3.0]], [[1, 2.0, -4.0, 3.0, -1.0], [27, -1.0, 3.0, 2.0, 3.0]]], [[], [], 1]], [[[[38, 1.0, 3.0, 4.0, 6.0], [31, -2.0, -3.0, 1.0, -3.0], [37, 0.0, 1.0, 0.0, 3.0], [9, -5.0, 3.0, -5.0, 4.0], [4, -5.0, 4.0, -4.0, 6.0], [14, -1.0, -2.0, 0.0, 0.0], [35, -3.0, 5.0, -2.0, 5.0]], [[38, 1.0, 2.0, 4.0, 5.0], [31, -3.0, -3.0, 0.0, -3.0], [37, 4.0, 2.0, 4.0, 4.0], [9, -6.0, 2.0, -6.0, 3.0], [4, -3.0, 4.0, -2.0, 6.0], [14, -1.0, -2.0, 0.0, 0.0], [35, -3.0, 6.0, -2.0, 6.0]]], [[[4, 35], [37, 38]], [[4, 9], [14, 37], [31, 37], [31, 38]], 10]], [[[[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]], [[[[38, 0.0, 0.0, 1.0, 2.0], [20, -3.0, 5.0, -2.0, 7.0], [35, 2.0, 0.0, 5.0, 0.0], [39, 0.0, 1.0, 3.0, 1.0], [7, -4.0, -1.0, -2.0, 1.0], [19, 5.0, -3.0, 5.0, -1.0], [26, -2.0, -3.0, -1.0, -2.0], [21, -5.0, 3.0, -4.0, 4.0]], [[38, 4.0, 0.0, 5.0, 2.0], [20, -6.0, 6.0, -5.0, 8.0], [35, -1.0, 1.0, 2.0, 1.0], [39, 0.0, 2.0, 3.0, 2.0], [7, -7.0, -1.0, -5.0, 1.0], [19, 4.0, -4.0, 4.0, -2.0], [26, -2.0, -3.0, -1.0, -2.0], [21, -3.0, 4.0, -2.0, 5.0]]], [[[35, 38]], [[7, 21], [7, 26], [19, 35], [20, 21], [20, 26], [35, 38], [38, 39]], 24]]], [[[[[7, -2.0, 5.0, -2.0, 5.0], [15, 0.0, 1.0, 1.0, 1.0], [5, 4.0, -5.0, 5.0, -4.0], [2, 0.0, -2.0, 0.0, -1.0], [11, 4.0, 3.0, 6.0, 3.0], [34, -1.0, 5.0, -1.0, 6.0], [20, -1.0, -1.0, 2.0, 0.0]], [[7, -3.0, 5.0, -3.0, 5.0], [15, -1.0, 1.0, 0.0, 1.0], [5, 6.0, -6.0, 7.0, -5.0], [2, 2.0, -2.0, 2.0, -1.0], [11, 1.0, 2.0, 3.0, 2.0], [34, -4.0, 6.0, -4.0, 7.0], [20, -1.0, 0.0, 2.0, 1.0]]], [[], [[2, 15], [5, 11], [7, 34], [20, 34]], 15]], [[[[37, -1.0, 5.0, 0.0, 5.0], [38, -1.0, 4.0, 1.0, 7.0], [32, 4.0, -4.0, 5.0, -2.0], [31, -5.0, -2.0, -4.0, -1.0], [13, 4.0, 1.0, 5.0, 3.0]], [[37, -1.0, 5.0, 0.0, 5.0], [38, 0.0, 3.0, 2.0, 6.0], [32, 8.0, -3.0, 9.0, -1.0], [31, -1.0, -3.0, 0.0, -2.0], [13, 4.0, 2.0, 5.0, 4.0]]], [[], [[13, 32]], 3]], [[[[9, 4.0, -4.0, 5.0, -3.0], [28, -4.0, 1.0, -4.0, 3.0], [22, 5.0, 3.0, 5.0, 5.0], [17, 0.0, 2.0, 0.0, 2.0], [24, 5.0, 0.0, 6.0, 2.0], [21, -1.0, -3.0, 2.0, -3.0], [6, 3.0, -3.0, 5.0, -2.0], [32, -4.0, -4.0, -4.0, -1.0], [18, 3.0, 4.0, 6.0, 5.0], [8, 2.0, 3.0, 4.0, 5.0]], [[9, 6.0, -4.0, 7.0, -3.0], [28, -4.0, 1.0, -4.0, 3.0], [22, 9.0, 4.0, 9.0, 6.0], [17, 0.0, 1.0, 0.0, 1.0], [24, 9.0, -1.0, 10.0, 1.0], [21, -4.0, -3.0, -1.0, -3.0], [6, 3.0, -3.0, 5.0, -2.0], [32, -7.0, -5.0, -7.0, -2.0], [18, 2.0, 3.0, 5.0, 4.0], [8, 6.0, 3.0, 8.0, 5.0]]], [[], [[6, 8], [6, 9], [6, 22], [6, 24], [8, 18], [8, 21], [9, 18], [9, 22], [9, 24], [17, 21], [18, 22], [18, 24], [28, 32]], 25]], [[[[34, 4.0, -3.0, 5.0, -2.0], [39, -5.0, 2.0, -5.0, 5.0]], [[34, 1.0, -3.0, 2.0, -2.0], [39, -5.0, 1.0, -5.0, 4.0]]], [[], [], 0]], [[[[15, -1.0, -1.0, 2.0, 0.0], [13, 4.0, -1.0, 7.0, 2.0], [4, 5.0, 3.0, 7.0, 5.0], [30, 1.0, 1.0, 2.0, 3.0], [26, -3.0, -3.0, -2.0, -1.0], [21, -1.0, 3.0, 0.0, 3.0], [6, 2.0, 5.0, 2.0, 6.0]], [[15, 1.0, -2.0, 4.0, -1.0], [13, 4.0, -1.0, 7.0, 2.0], [4, 4.0, 3.0, 6.0, 5.0], [30, 3.0, 1.0, 4.0, 3.0], [26, -3.0, -4.0, -2.0, -2.0], [21, 1.0, 3.0, 2.0, 3.0], [6, 2.0, 5.0, 2.0, 6.0]]], [[[4, 30], [13, 15], [13, 30]], [[6, 30]], 7]], [[[[13, 2.0, 3.0, 5.0, 3.0], [8, 0.0, 5.0, 0.0, 8.0], [18, 1.0, 2.0, 1.0, 2.0], [15, 2.0, 1.0, 2.0, 3.0]], [[13, 2.0, 2.0, 5.0, 2.0], [8, 1.0, 4.0, 1.0, 7.0], [18, 1.0, 2.0, 1.0, 2.0], [15, 6.0, 2.0, 6.0, 4.0]]], [[], [[13, 15]], 3]], [[[[15, 4.0, 1.0, 5.0, 1.0], [23, 0.0, 5.0, 2.0, 5.0], [18, -5.0, 4.0, -2.0, 5.0], [39, -3.0, 0.0, -2.0, 2.0], [4, -1.0, 4.0, 2.0, 5.0], [7, 3.0, 1.0, 4.0, 2.0], [16, -3.0, -3.0, -2.0, 0.0]], [[15, 4.0, 0.0, 5.0, 0.0], [23, 2.0, 5.0, 4.0, 5.0], [18, -6.0, 4.0, -3.0, 5.0], [39, 1.0, -1.0, 2.0, 1.0], [4, -1.0, 3.0, 2.0, 4.0], [7, 0.0, 1.0, 1.0, 2.0], [16, -6.0, -3.0, -5.0, 0.0]]], [[[7, 39]], [[7, 15], [7, 23], [16, 39], [18, 39]], 16]], [[[[15, -4.0, 0.0, -4.0, 1.0], [38, 5.0, 5.0, 6.0, 8.0], [35, -5.0, 1.0, -2.0, 2.0], [22, -3.0, 4.0, 0.0, 7.0], [3, 2.0, 0.0, 2.0, 0.0], [32, 3.0, 5.0, 4.0, 8.0], [11, 0.0, 0.0, 3.0, 1.0], [24, 4.0, 0.0, 4.0, 2.0]], [[15, 0.0, 0.0, 0.0, 1.0], [38, 5.0, 6.0, 6.0, 9.0], [35, -3.0, 1.0, 0.0, 2.0], [22, 1.0, 4.0, 4.0, 7.0], [3, 3.0, 0.0, 3.0, 0.0], [32, 2.0, 5.0, 3.0, 8.0], [11, 0.0, -1.0, 3.0, 0.0], [24, 1.0, 0.0, 1.0, 2.0]]], [[[3, 24], [11, 15], [11, 24], [22, 32]], [[3, 24], [22, 35], [24, 32]], 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":"3dfe65eef419b8e9570569e1bf46b858d9810384e500c2b4f5ea758bb0a550c0","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 = (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 = [[[[[[27, 0.0, -1.0, 1.0, 1.0], [2, -2.0, 3.0, 1.0, 3.0], [10, -3.0, 0.0, 0.0, 0.0], [32, 2.0, -2.0, 2.0, 1.0], [14, -4.0, 4.0, -3.0, 4.0], [21, 5.0, 5.0, 6.0, 6.0]], [[27, 0.0, -1.0, 1.0, 1.0], [2, 2.0, 3.0, 5.0, 3.0], [10, 1.0, 0.0, 4.0, 0.0], [32, 2.0, -3.0, 2.0, 0.0], [14, -3.0, 5.0, -2.0, 5.0], [21, 2.0, 6.0, 3.0, 7.0]]], [[[10, 32]], [[2, 27], [10, 14]], 15]], [[[[20, -5.0, 5.0, -2.0, 6.0], [5, 0.0, 5.0, 3.0, 7.0]], [[20, -1.0, 6.0, 2.0, 7.0], [5, 2.0, 5.0, 5.0, 7.0]]], [[[5, 20]], [], 1]], [[[[35, -4.0, 0.0, -3.0, 1.0], [4, -4.0, 0.0, -4.0, 3.0], [36, 5.0, -2.0, 5.0, 1.0], [25, 4.0, -1.0, 4.0, 1.0]], [[35, -7.0, -1.0, -6.0, 0.0], [4, -4.0, 0.0, -4.0, 3.0], [36, 7.0, -2.0, 7.0, 1.0], [25, 4.0, 0.0, 4.0, 2.0]]], [[], [[4, 35]], 3]], [[[[5, -2.0, -3.0, -1.0, -3.0], [22, 4.0, -1.0, 6.0, 2.0], [14, -2.0, 3.0, 1.0, 4.0], [8, -4.0, 1.0, -1.0, 3.0], [21, 4.0, 0.0, 4.0, 2.0]], [[5, -2.0, -3.0, -1.0, -3.0], [22, 8.0, -2.0, 10.0, 1.0], [14, -1.0, 3.0, 2.0, 4.0], [8, 0.0, 2.0, 3.0, 4.0], [21, 5.0, 1.0, 5.0, 3.0]]], [[], [[5, 8], [21, 22]], 5]], [[[[30, 2.0, 2.0, 3.0, 2.0], [11, 4.0, -1.0, 4.0, 1.0], [13, 5.0, 4.0, 6.0, 7.0], [4, 3.0, -1.0, 4.0, 1.0]], [[30, 6.0, 1.0, 7.0, 1.0], [11, 8.0, 0.0, 8.0, 2.0], [13, 9.0, 4.0, 10.0, 7.0], [4, 3.0, -2.0, 4.0, 0.0]]], [[], [[4, 11], [4, 30]], 4]], [[[[29, -1.0, -2.0, 2.0, 1.0], [38, 5.0, 1.0, 5.0, 3.0], [28, 3.0, -3.0, 3.0, -2.0], [17, 5.0, 1.0, 8.0, 3.0], [9, -5.0, -2.0, -4.0, 0.0]], [[29, 1.0, -1.0, 4.0, 2.0], [38, 9.0, 1.0, 9.0, 3.0], [28, 2.0, -2.0, 2.0, -1.0], [17, 2.0, 1.0, 5.0, 3.0], [9, -1.0, -1.0, 0.0, 1.0]]], [[[17, 29], [28, 29]], [[17, 38]], 6]], [[[[32, -2.0, -1.0, -2.0, 2.0], [33, 1.0, -4.0, 2.0, -2.0], [12, 3.0, 1.0, 5.0, 2.0], [5, 1.0, 5.0, 3.0, 7.0]], [[32, -1.0, -1.0, -1.0, 2.0], [33, 1.0, -5.0, 2.0, -3.0], [12, 7.0, 1.0, 9.0, 2.0], [5, -2.0, 6.0, 0.0, 8.0]]], [[], [[5, 12], [5, 33]], 5]], [[[[2, 0.0, 5.0, 3.0, 8.0], [38, 5.0, -5.0, 5.0, -3.0], [19, -2.0, 0.0, -2.0, 0.0], [10, -1.0, -4.0, 1.0, -1.0], [29, 3.0, -5.0, 3.0, -3.0]], [[2, -1.0, 4.0, 2.0, 7.0], [38, 4.0, -5.0, 4.0, -3.0], [19, -2.0, 0.0, -2.0, 0.0], [10, -1.0, -5.0, 1.0, -2.0], [29, 7.0, -4.0, 7.0, -2.0]]], [[[29, 38]], [[2, 29], [29, 38]], 5]]], [[[[[10, 1.0, -3.0, 3.0, -3.0], [33, 1.0, 0.0, 4.0, 2.0], [16, -2.0, 4.0, -2.0, 7.0], [38, -3.0, 1.0, -2.0, 3.0]], [[10, 1.0, -3.0, 3.0, -3.0], [33, 2.0, 0.0, 5.0, 2.0], [16, -2.0, 4.0, -2.0, 7.0], [38, -1.0, 1.0, 0.0, 3.0]]], [[], [[16, 38]], 2]], [[[[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]], [[[[1, -3.0, 0.0, -1.0, 3.0], [27, -3.0, 5.0, -1.0, 7.0], [23, -5.0, 0.0, -5.0, 0.0], [36, 0.0, 3.0, 0.0, 3.0], [33, -1.0, -4.0, 1.0, -2.0], [32, 4.0, -1.0, 5.0, 1.0]], [[1, -6.0, 0.0, -4.0, 3.0], [27, -3.0, 5.0, -1.0, 7.0], [23, -1.0, 0.0, -1.0, 0.0], [36, 4.0, 2.0, 4.0, 2.0], [33, -2.0, -3.0, 0.0, -1.0], [32, 4.0, 0.0, 5.0, 2.0]]], [[[1, 23], [32, 36]], [[1, 23], [1, 27], [1, 33], [33, 36]], 13]], [[[[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]], [[[[12, -2.0, 0.0, 0.0, 2.0], [19, 0.0, -5.0, 3.0, -5.0], [10, -1.0, -4.0, 0.0, -2.0], [39, 4.0, -3.0, 7.0, -1.0], [17, -4.0, 1.0, -2.0, 4.0], [28, -2.0, -5.0, -1.0, -3.0], [35, 0.0, 5.0, 3.0, 6.0]], [[12, -1.0, -1.0, 1.0, 1.0], [19, 4.0, -5.0, 7.0, -5.0], [10, 1.0, -3.0, 2.0, -1.0], [39, 3.0, -2.0, 6.0, 0.0], [17, -3.0, 1.0, -1.0, 4.0], [28, -3.0, -5.0, -2.0, -3.0], [35, -3.0, 5.0, 0.0, 6.0]]], [[], [[10, 19], [10, 28], [10, 35], [12, 19], [12, 28], [19, 35]], 20]], [[[[32, 1.0, 5.0, 2.0, 6.0], [6, 0.0, 5.0, 2.0, 5.0], [9, 0.0, -2.0, 3.0, 1.0], [24, -5.0, 0.0, -3.0, 3.0]], [[32, -2.0, 6.0, -1.0, 7.0], [6, 1.0, 4.0, 3.0, 4.0], [9, 4.0, -1.0, 7.0, 2.0], [24, -5.0, 1.0, -3.0, 4.0]]], [[], [[6, 9], [6, 32], [9, 32]], 6]], [[[[23, -4.0, 0.0, -1.0, 1.0], [13, -4.0, -2.0, -4.0, 1.0], [6, -2.0, -5.0, 0.0, -3.0], [8, 5.0, 2.0, 5.0, 3.0], [9, -5.0, 0.0, -4.0, 2.0]], [[23, -7.0, 0.0, -4.0, 1.0], [13, -5.0, -1.0, -5.0, 2.0], [6, 0.0, -5.0, 2.0, -3.0], [8, 5.0, 3.0, 5.0, 4.0], [9, -8.0, 1.0, -7.0, 3.0]]], [[], [[6, 23], [9, 13]], 3]], [[[[6, 5.0, 4.0, 5.0, 7.0], [38, -3.0, 0.0, 0.0, 3.0], [18, -5.0, -3.0, -4.0, -2.0], [9, -5.0, 5.0, -5.0, 7.0], [27, 0.0, 4.0, 1.0, 6.0]], [[6, 7.0, 4.0, 7.0, 7.0], [38, -3.0, 0.0, 0.0, 3.0], [18, -4.0, -3.0, -3.0, -2.0], [9, -5.0, 5.0, -5.0, 7.0], [27, -1.0, 4.0, 0.0, 6.0]]], [[], [[9, 18]], 2]]], [[[[[39, 3.0, 1.0, 6.0, 4.0], [22, -5.0, 4.0, -4.0, 7.0], [27, 2.0, -5.0, 5.0, -5.0]], [[39, 3.0, 2.0, 6.0, 5.0], [22, -5.0, 3.0, -4.0, 6.0], [27, 6.0, -4.0, 9.0, -4.0]]], [[], [], 2]], [[[[2, 3.0, -2.0, 4.0, 1.0], [32, 3.0, 5.0, 6.0, 7.0], [14, 1.0, -3.0, 2.0, -3.0], [25, -1.0, -2.0, 2.0, 1.0], [24, -1.0, -2.0, 0.0, 0.0], [29, 5.0, -2.0, 5.0, 0.0]], [[2, 0.0, -2.0, 1.0, 1.0], [32, 4.0, 4.0, 7.0, 6.0], [14, 2.0, -4.0, 3.0, -4.0], [25, 3.0, -2.0, 6.0, 1.0], [24, 1.0, -1.0, 2.0, 1.0], [29, 9.0, -2.0, 9.0, 0.0]]], [[[2, 24], [2, 25]], [[2, 14], [2, 25], [2, 32], [24, 25], [29, 32]], 18]], [[[[26, -5.0, -4.0, -2.0, -2.0], [6, 4.0, 1.0, 5.0, 2.0], [18, -2.0, 2.0, -2.0, 2.0], [24, -4.0, -5.0, -2.0, -3.0], [19, -5.0, -2.0, -4.0, -1.0]], [[26, -6.0, -4.0, -3.0, -2.0], [6, 1.0, 1.0, 2.0, 2.0], [18, -5.0, 2.0, -5.0, 2.0], [24, -5.0, -5.0, -3.0, -3.0], [19, -3.0, -2.0, -2.0, -1.0]]], [[], [[18, 19]], 8]], [[[[18, -4.0, -5.0, -3.0, -4.0], [26, 4.0, -4.0, 6.0, -1.0], [8, -4.0, -4.0, -2.0, -3.0], [7, 5.0, 1.0, 5.0, 1.0], [3, 1.0, -2.0, 4.0, 0.0], [23, 2.0, -5.0, 2.0, -2.0]], [[18, -2.0, -6.0, -1.0, -5.0], [26, 5.0, -4.0, 7.0, -1.0], [8, -2.0, -5.0, 0.0, -4.0], [7, 5.0, 1.0, 5.0, 1.0], [3, 5.0, -3.0, 8.0, -1.0], [23, 1.0, -4.0, 1.0, -1.0]]], [[], [[3, 23]], 5]], [[[[13, 5.0, -2.0, 6.0, 0.0], [39, 4.0, 5.0, 7.0, 7.0], [11, 0.0, 5.0, 3.0, 5.0], [10, 3.0, -4.0, 4.0, -3.0], [18, -2.0, -4.0, -1.0, -2.0], [30, -3.0, -4.0, -1.0, -1.0], [36, 1.0, 1.0, 3.0, 3.0]], [[13, 2.0, -3.0, 3.0, -1.0], [39, 1.0, 5.0, 4.0, 7.0], [11, -3.0, 6.0, 0.0, 6.0], [10, 5.0, -5.0, 6.0, -4.0], [18, -2.0, -3.0, -1.0, -1.0], [30, 1.0, -5.0, 3.0, -2.0], [36, 2.0, 0.0, 4.0, 2.0]]], [[[13, 30]], [[10, 11], [10, 13], [10, 36], [10, 39], [11, 30], [11, 36], [18, 30]], 25]], [[[[20, -2.0, -4.0, 0.0, -4.0], [8, 0.0, -2.0, 0.0, 0.0], [2, 0.0, -4.0, 2.0, -3.0], [14, 1.0, 5.0, 2.0, 7.0], [39, -4.0, 3.0, -4.0, 5.0], [18, -3.0, -5.0, -3.0, -3.0]], [[20, -2.0, -4.0, 0.0, -4.0], [8, -3.0, -1.0, -3.0, 1.0], [2, 0.0, -4.0, 2.0, -3.0], [14, 2.0, 4.0, 3.0, 6.0], [39, -4.0, 4.0, -4.0, 6.0], [18, 1.0, -4.0, 1.0, -2.0]]], [[[2, 18], [18, 20]], [[2, 8], [8, 18], [8, 20], [18, 20]], 14]], [[[[38, -3.0, -5.0, -3.0, -4.0], [10, 4.0, 1.0, 6.0, 3.0], [15, 1.0, 0.0, 3.0, 3.0], [23, -4.0, -2.0, -1.0, 0.0], [24, -1.0, 3.0, 2.0, 4.0], [14, 3.0, -4.0, 5.0, -3.0], [26, -2.0, 3.0, 1.0, 5.0], [20, -5.0, 4.0, -4.0, 5.0]], [[38, -6.0, -6.0, -6.0, -5.0], [10, 1.0, 0.0, 3.0, 2.0], [15, 1.0, 1.0, 3.0, 4.0], [23, 0.0, -2.0, 3.0, 0.0], [24, 0.0, 2.0, 3.0, 3.0], [14, 5.0, -5.0, 7.0, -4.0], [26, -2.0, 2.0, 1.0, 4.0], [20, -3.0, 5.0, -2.0, 6.0]]], [[[10, 15], [10, 23], [10, 24], [10, 26]], [[10, 14], [14, 15], [20, 23], [20, 38], [23, 38]], 19]], [[[[34, 3.0, 5.0, 3.0, 7.0], [13, -3.0, -2.0, 0.0, 1.0], [31, 0.0, 1.0, 3.0, 3.0]], [[34, 3.0, 5.0, 3.0, 7.0], [13, -3.0, -1.0, 0.0, 2.0], [31, 0.0, 2.0, 3.0, 4.0]]], [[], [], 0]]], [[[[[39, 5.0, 0.0, 5.0, 3.0], [11, -4.0, 0.0, -4.0, 1.0], [18, -4.0, 1.0, -3.0, 3.0], [12, -2.0, 5.0, 1.0, 8.0], [36, 3.0, 0.0, 5.0, 0.0]], [[39, 7.0, 0.0, 7.0, 3.0], [11, -3.0, -1.0, -3.0, 0.0], [18, -2.0, 0.0, -1.0, 2.0], [12, -5.0, 5.0, -2.0, 8.0], [36, 5.0, 0.0, 7.0, 0.0]]], [[], [[11, 18]], 6]], [[[[8, -1.0, -1.0, -1.0, -1.0], [9, 4.0, 0.0, 4.0, 3.0], [30, -3.0, 5.0, -1.0, 5.0], [32, 0.0, 2.0, 1.0, 5.0], [3, -3.0, 1.0, 0.0, 1.0], [18, -2.0, 4.0, -2.0, 7.0], [23, 5.0, 2.0, 5.0, 2.0], [39, -4.0, 4.0, -1.0, 5.0]], [[8, 0.0, -1.0, 0.0, -1.0], [9, 1.0, -1.0, 1.0, 2.0], [30, -6.0, 4.0, -4.0, 4.0], [32, -1.0, 1.0, 0.0, 4.0], [3, -3.0, 2.0, 0.0, 2.0], [18, -3.0, 4.0, -3.0, 7.0], [23, 5.0, 1.0, 5.0, 1.0], [39, -4.0, 3.0, -1.0, 4.0]]], [[[32, 39]], [[3, 30], [8, 30], [8, 39], [18, 30]], 12]], [[[[19, -5.0, 4.0, -3.0, 6.0], [29, 2.0, 0.0, 4.0, 0.0], [7, -5.0, 3.0, -4.0, 5.0], [11, 2.0, 3.0, 5.0, 3.0]], [[19, -3.0, 4.0, -1.0, 6.0], [29, -1.0, 1.0, 1.0, 1.0], [7, -1.0, 3.0, 0.0, 5.0], [11, 1.0, 3.0, 4.0, 3.0]]], [[], [], 5]], [[[[7, 3.0, -1.0, 3.0, 0.0], [27, -5.0, -5.0, -2.0, -2.0], [15, 3.0, 5.0, 5.0, 6.0], [31, -2.0, -2.0, -2.0, -1.0], [26, 4.0, 1.0, 4.0, 3.0], [30, 3.0, -4.0, 5.0, -3.0], [29, 4.0, 4.0, 7.0, 4.0], [1, -5.0, -5.0, -3.0, -3.0], [39, 3.0, -2.0, 3.0, 1.0]], [[7, 7.0, -1.0, 7.0, 0.0], [27, -4.0, -5.0, -1.0, -2.0], [15, 2.0, 4.0, 4.0, 5.0], [31, -5.0, -1.0, -5.0, 0.0], [26, 3.0, 1.0, 3.0, 3.0], [30, 4.0, -3.0, 6.0, -2.0], [29, 6.0, 3.0, 9.0, 3.0], [1, -1.0, -5.0, 1.0, -3.0], [39, 5.0, -3.0, 5.0, 0.0]]], [[], [[1, 31], [7, 15], [7, 26], [7, 30], [7, 39], [15, 29], [15, 39], [26, 29], [26, 30], [26, 39], [27, 31]], 34]], [[[[1, 5.0, -4.0, 6.0, -1.0], [27, -1.0, 3.0, 2.0, 3.0]], [[1, 2.0, -4.0, 3.0, -1.0], [27, -1.0, 3.0, 2.0, 3.0]]], [[], [], 1]], [[[[38, 1.0, 3.0, 4.0, 6.0], [31, -2.0, -3.0, 1.0, -3.0], [37, 0.0, 1.0, 0.0, 3.0], [9, -5.0, 3.0, -5.0, 4.0], [4, -5.0, 4.0, -4.0, 6.0], [14, -1.0, -2.0, 0.0, 0.0], [35, -3.0, 5.0, -2.0, 5.0]], [[38, 1.0, 2.0, 4.0, 5.0], [31, -3.0, -3.0, 0.0, -3.0], [37, 4.0, 2.0, 4.0, 4.0], [9, -6.0, 2.0, -6.0, 3.0], [4, -3.0, 4.0, -2.0, 6.0], [14, -1.0, -2.0, 0.0, 0.0], [35, -3.0, 6.0, -2.0, 6.0]]], [[[4, 35], [37, 38]], [[4, 9], [14, 37], [31, 37], [31, 38]], 10]], [[[[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]], [[[[38, 0.0, 0.0, 1.0, 2.0], [20, -3.0, 5.0, -2.0, 7.0], [35, 2.0, 0.0, 5.0, 0.0], [39, 0.0, 1.0, 3.0, 1.0], [7, -4.0, -1.0, -2.0, 1.0], [19, 5.0, -3.0, 5.0, -1.0], [26, -2.0, -3.0, -1.0, -2.0], [21, -5.0, 3.0, -4.0, 4.0]], [[38, 4.0, 0.0, 5.0, 2.0], [20, -6.0, 6.0, -5.0, 8.0], [35, -1.0, 1.0, 2.0, 1.0], [39, 0.0, 2.0, 3.0, 2.0], [7, -7.0, -1.0, -5.0, 1.0], [19, 4.0, -4.0, 4.0, -2.0], [26, -2.0, -3.0, -1.0, -2.0], [21, -3.0, 4.0, -2.0, 5.0]]], [[[35, 38]], [[7, 21], [7, 26], [19, 35], [20, 21], [20, 26], [35, 38], [38, 39]], 24]]], [[[[[7, -2.0, 5.0, -2.0, 5.0], [15, 0.0, 1.0, 1.0, 1.0], [5, 4.0, -5.0, 5.0, -4.0], [2, 0.0, -2.0, 0.0, -1.0], [11, 4.0, 3.0, 6.0, 3.0], [34, -1.0, 5.0, -1.0, 6.0], [20, -1.0, -1.0, 2.0, 0.0]], [[7, -3.0, 5.0, -3.0, 5.0], [15, -1.0, 1.0, 0.0, 1.0], [5, 6.0, -6.0, 7.0, -5.0], [2, 2.0, -2.0, 2.0, -1.0], [11, 1.0, 2.0, 3.0, 2.0], [34, -4.0, 6.0, -4.0, 7.0], [20, -1.0, 0.0, 2.0, 1.0]]], [[], [[2, 15], [5, 11], [7, 34], [20, 34]], 15]], [[[[37, -1.0, 5.0, 0.0, 5.0], [38, -1.0, 4.0, 1.0, 7.0], [32, 4.0, -4.0, 5.0, -2.0], [31, -5.0, -2.0, -4.0, -1.0], [13, 4.0, 1.0, 5.0, 3.0]], [[37, -1.0, 5.0, 0.0, 5.0], [38, 0.0, 3.0, 2.0, 6.0], [32, 8.0, -3.0, 9.0, -1.0], [31, -1.0, -3.0, 0.0, -2.0], [13, 4.0, 2.0, 5.0, 4.0]]], [[], [[13, 32]], 3]], [[[[9, 4.0, -4.0, 5.0, -3.0], [28, -4.0, 1.0, -4.0, 3.0], [22, 5.0, 3.0, 5.0, 5.0], [17, 0.0, 2.0, 0.0, 2.0], [24, 5.0, 0.0, 6.0, 2.0], [21, -1.0, -3.0, 2.0, -3.0], [6, 3.0, -3.0, 5.0, -2.0], [32, -4.0, -4.0, -4.0, -1.0], [18, 3.0, 4.0, 6.0, 5.0], [8, 2.0, 3.0, 4.0, 5.0]], [[9, 6.0, -4.0, 7.0, -3.0], [28, -4.0, 1.0, -4.0, 3.0], [22, 9.0, 4.0, 9.0, 6.0], [17, 0.0, 1.0, 0.0, 1.0], [24, 9.0, -1.0, 10.0, 1.0], [21, -4.0, -3.0, -1.0, -3.0], [6, 3.0, -3.0, 5.0, -2.0], [32, -7.0, -5.0, -7.0, -2.0], [18, 2.0, 3.0, 5.0, 4.0], [8, 6.0, 3.0, 8.0, 5.0]]], [[], [[6, 8], [6, 9], [6, 22], [6, 24], [8, 18], [8, 21], [9, 18], [9, 22], [9, 24], [17, 21], [18, 22], [18, 24], [28, 32]], 25]], [[[[34, 4.0, -3.0, 5.0, -2.0], [39, -5.0, 2.0, -5.0, 5.0]], [[34, 1.0, -3.0, 2.0, -2.0], [39, -5.0, 1.0, -5.0, 4.0]]], [[], [], 0]], [[[[15, -1.0, -1.0, 2.0, 0.0], [13, 4.0, -1.0, 7.0, 2.0], [4, 5.0, 3.0, 7.0, 5.0], [30, 1.0, 1.0, 2.0, 3.0], [26, -3.0, -3.0, -2.0, -1.0], [21, -1.0, 3.0, 0.0, 3.0], [6, 2.0, 5.0, 2.0, 6.0]], [[15, 1.0, -2.0, 4.0, -1.0], [13, 4.0, -1.0, 7.0, 2.0], [4, 4.0, 3.0, 6.0, 5.0], [30, 3.0, 1.0, 4.0, 3.0], [26, -3.0, -4.0, -2.0, -2.0], [21, 1.0, 3.0, 2.0, 3.0], [6, 2.0, 5.0, 2.0, 6.0]]], [[[4, 30], [13, 15], [13, 30]], [[6, 30]], 7]], [[[[13, 2.0, 3.0, 5.0, 3.0], [8, 0.0, 5.0, 0.0, 8.0], [18, 1.0, 2.0, 1.0, 2.0], [15, 2.0, 1.0, 2.0, 3.0]], [[13, 2.0, 2.0, 5.0, 2.0], [8, 1.0, 4.0, 1.0, 7.0], [18, 1.0, 2.0, 1.0, 2.0], [15, 6.0, 2.0, 6.0, 4.0]]], [[], [[13, 15]], 3]], [[[[15, 4.0, 1.0, 5.0, 1.0], [23, 0.0, 5.0, 2.0, 5.0], [18, -5.0, 4.0, -2.0, 5.0], [39, -3.0, 0.0, -2.0, 2.0], [4, -1.0, 4.0, 2.0, 5.0], [7, 3.0, 1.0, 4.0, 2.0], [16, -3.0, -3.0, -2.0, 0.0]], [[15, 4.0, 0.0, 5.0, 0.0], [23, 2.0, 5.0, 4.0, 5.0], [18, -6.0, 4.0, -3.0, 5.0], [39, 1.0, -1.0, 2.0, 1.0], [4, -1.0, 3.0, 2.0, 4.0], [7, 0.0, 1.0, 1.0, 2.0], [16, -6.0, -3.0, -5.0, 0.0]]], [[[7, 39]], [[7, 15], [7, 23], [16, 39], [18, 39]], 16]], [[[[15, -4.0, 0.0, -4.0, 1.0], [38, 5.0, 5.0, 6.0, 8.0], [35, -5.0, 1.0, -2.0, 2.0], [22, -3.0, 4.0, 0.0, 7.0], [3, 2.0, 0.0, 2.0, 0.0], [32, 3.0, 5.0, 4.0, 8.0], [11, 0.0, 0.0, 3.0, 1.0], [24, 4.0, 0.0, 4.0, 2.0]], [[15, 0.0, 0.0, 0.0, 1.0], [38, 5.0, 6.0, 6.0, 9.0], [35, -3.0, 1.0, 0.0, 2.0], [22, 1.0, 4.0, 4.0, 7.0], [3, 3.0, 0.0, 3.0, 0.0], [32, 2.0, 5.0, 3.0, 8.0], [11, 0.0, -1.0, 3.0, 0.0], [24, 1.0, 0.0, 1.0, 2.0]]], [[[3, 24], [11, 15], [11, 24], [22, 32]], [[3, 24], [22, 35], [24, 32]], 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":"4318783a4bf03ecc528ad40706f2ac3ce3c3b1f40ffb0d4fb661617c5a70b6c1","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 = [[[[[[27, 0.0, -1.0, 1.0, 1.0], [2, -2.0, 3.0, 1.0, 3.0], [10, -3.0, 0.0, 0.0, 0.0], [32, 2.0, -2.0, 2.0, 1.0], [14, -4.0, 4.0, -3.0, 4.0], [21, 5.0, 5.0, 6.0, 6.0]], [[27, 0.0, -1.0, 1.0, 1.0], [2, 2.0, 3.0, 5.0, 3.0], [10, 1.0, 0.0, 4.0, 0.0], [32, 2.0, -3.0, 2.0, 0.0], [14, -3.0, 5.0, -2.0, 5.0], [21, 2.0, 6.0, 3.0, 7.0]]], [[[10, 32]], [[2, 27], [10, 14]], 15]], [[[[20, -5.0, 5.0, -2.0, 6.0], [5, 0.0, 5.0, 3.0, 7.0]], [[20, -1.0, 6.0, 2.0, 7.0], [5, 2.0, 5.0, 5.0, 7.0]]], [[[5, 20]], [], 1]], [[[[35, -4.0, 0.0, -3.0, 1.0], [4, -4.0, 0.0, -4.0, 3.0], [36, 5.0, -2.0, 5.0, 1.0], [25, 4.0, -1.0, 4.0, 1.0]], [[35, -7.0, -1.0, -6.0, 0.0], [4, -4.0, 0.0, -4.0, 3.0], [36, 7.0, -2.0, 7.0, 1.0], [25, 4.0, 0.0, 4.0, 2.0]]], [[], [[4, 35]], 3]], [[[[5, -2.0, -3.0, -1.0, -3.0], [22, 4.0, -1.0, 6.0, 2.0], [14, -2.0, 3.0, 1.0, 4.0], [8, -4.0, 1.0, -1.0, 3.0], [21, 4.0, 0.0, 4.0, 2.0]], [[5, -2.0, -3.0, -1.0, -3.0], [22, 8.0, -2.0, 10.0, 1.0], [14, -1.0, 3.0, 2.0, 4.0], [8, 0.0, 2.0, 3.0, 4.0], [21, 5.0, 1.0, 5.0, 3.0]]], [[], [[5, 8], [21, 22]], 5]], [[[[30, 2.0, 2.0, 3.0, 2.0], [11, 4.0, -1.0, 4.0, 1.0], [13, 5.0, 4.0, 6.0, 7.0], [4, 3.0, -1.0, 4.0, 1.0]], [[30, 6.0, 1.0, 7.0, 1.0], [11, 8.0, 0.0, 8.0, 2.0], [13, 9.0, 4.0, 10.0, 7.0], [4, 3.0, -2.0, 4.0, 0.0]]], [[], [[4, 11], [4, 30]], 4]], [[[[29, -1.0, -2.0, 2.0, 1.0], [38, 5.0, 1.0, 5.0, 3.0], [28, 3.0, -3.0, 3.0, -2.0], [17, 5.0, 1.0, 8.0, 3.0], [9, -5.0, -2.0, -4.0, 0.0]], [[29, 1.0, -1.0, 4.0, 2.0], [38, 9.0, 1.0, 9.0, 3.0], [28, 2.0, -2.0, 2.0, -1.0], [17, 2.0, 1.0, 5.0, 3.0], [9, -1.0, -1.0, 0.0, 1.0]]], [[[17, 29], [28, 29]], [[17, 38]], 6]], [[[[32, -2.0, -1.0, -2.0, 2.0], [33, 1.0, -4.0, 2.0, -2.0], [12, 3.0, 1.0, 5.0, 2.0], [5, 1.0, 5.0, 3.0, 7.0]], [[32, -1.0, -1.0, -1.0, 2.0], [33, 1.0, -5.0, 2.0, -3.0], [12, 7.0, 1.0, 9.0, 2.0], [5, -2.0, 6.0, 0.0, 8.0]]], [[], [[5, 12], [5, 33]], 5]], [[[[2, 0.0, 5.0, 3.0, 8.0], [38, 5.0, -5.0, 5.0, -3.0], [19, -2.0, 0.0, -2.0, 0.0], [10, -1.0, -4.0, 1.0, -1.0], [29, 3.0, -5.0, 3.0, -3.0]], [[2, -1.0, 4.0, 2.0, 7.0], [38, 4.0, -5.0, 4.0, -3.0], [19, -2.0, 0.0, -2.0, 0.0], [10, -1.0, -5.0, 1.0, -2.0], [29, 7.0, -4.0, 7.0, -2.0]]], [[[29, 38]], [[2, 29], [29, 38]], 5]]], [[[[[10, 1.0, -3.0, 3.0, -3.0], [33, 1.0, 0.0, 4.0, 2.0], [16, -2.0, 4.0, -2.0, 7.0], [38, -3.0, 1.0, -2.0, 3.0]], [[10, 1.0, -3.0, 3.0, -3.0], [33, 2.0, 0.0, 5.0, 2.0], [16, -2.0, 4.0, -2.0, 7.0], [38, -1.0, 1.0, 0.0, 3.0]]], [[], [[16, 38]], 2]], [[[[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]], [[[[1, -3.0, 0.0, -1.0, 3.0], [27, -3.0, 5.0, -1.0, 7.0], [23, -5.0, 0.0, -5.0, 0.0], [36, 0.0, 3.0, 0.0, 3.0], [33, -1.0, -4.0, 1.0, -2.0], [32, 4.0, -1.0, 5.0, 1.0]], [[1, -6.0, 0.0, -4.0, 3.0], [27, -3.0, 5.0, -1.0, 7.0], [23, -1.0, 0.0, -1.0, 0.0], [36, 4.0, 2.0, 4.0, 2.0], [33, -2.0, -3.0, 0.0, -1.0], [32, 4.0, 0.0, 5.0, 2.0]]], [[[1, 23], [32, 36]], [[1, 23], [1, 27], [1, 33], [33, 36]], 13]], [[[[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]], [[[[12, -2.0, 0.0, 0.0, 2.0], [19, 0.0, -5.0, 3.0, -5.0], [10, -1.0, -4.0, 0.0, -2.0], [39, 4.0, -3.0, 7.0, -1.0], [17, -4.0, 1.0, -2.0, 4.0], [28, -2.0, -5.0, -1.0, -3.0], [35, 0.0, 5.0, 3.0, 6.0]], [[12, -1.0, -1.0, 1.0, 1.0], [19, 4.0, -5.0, 7.0, -5.0], [10, 1.0, -3.0, 2.0, -1.0], [39, 3.0, -2.0, 6.0, 0.0], [17, -3.0, 1.0, -1.0, 4.0], [28, -3.0, -5.0, -2.0, -3.0], [35, -3.0, 5.0, 0.0, 6.0]]], [[], [[10, 19], [10, 28], [10, 35], [12, 19], [12, 28], [19, 35]], 20]], [[[[32, 1.0, 5.0, 2.0, 6.0], [6, 0.0, 5.0, 2.0, 5.0], [9, 0.0, -2.0, 3.0, 1.0], [24, -5.0, 0.0, -3.0, 3.0]], [[32, -2.0, 6.0, -1.0, 7.0], [6, 1.0, 4.0, 3.0, 4.0], [9, 4.0, -1.0, 7.0, 2.0], [24, -5.0, 1.0, -3.0, 4.0]]], [[], [[6, 9], [6, 32], [9, 32]], 6]], [[[[23, -4.0, 0.0, -1.0, 1.0], [13, -4.0, -2.0, -4.0, 1.0], [6, -2.0, -5.0, 0.0, -3.0], [8, 5.0, 2.0, 5.0, 3.0], [9, -5.0, 0.0, -4.0, 2.0]], [[23, -7.0, 0.0, -4.0, 1.0], [13, -5.0, -1.0, -5.0, 2.0], [6, 0.0, -5.0, 2.0, -3.0], [8, 5.0, 3.0, 5.0, 4.0], [9, -8.0, 1.0, -7.0, 3.0]]], [[], [[6, 23], [9, 13]], 3]], [[[[6, 5.0, 4.0, 5.0, 7.0], [38, -3.0, 0.0, 0.0, 3.0], [18, -5.0, -3.0, -4.0, -2.0], [9, -5.0, 5.0, -5.0, 7.0], [27, 0.0, 4.0, 1.0, 6.0]], [[6, 7.0, 4.0, 7.0, 7.0], [38, -3.0, 0.0, 0.0, 3.0], [18, -4.0, -3.0, -3.0, -2.0], [9, -5.0, 5.0, -5.0, 7.0], [27, -1.0, 4.0, 0.0, 6.0]]], [[], [[9, 18]], 2]]], [[[[[39, 3.0, 1.0, 6.0, 4.0], [22, -5.0, 4.0, -4.0, 7.0], [27, 2.0, -5.0, 5.0, -5.0]], [[39, 3.0, 2.0, 6.0, 5.0], [22, -5.0, 3.0, -4.0, 6.0], [27, 6.0, -4.0, 9.0, -4.0]]], [[], [], 2]], [[[[2, 3.0, -2.0, 4.0, 1.0], [32, 3.0, 5.0, 6.0, 7.0], [14, 1.0, -3.0, 2.0, -3.0], [25, -1.0, -2.0, 2.0, 1.0], [24, -1.0, -2.0, 0.0, 0.0], [29, 5.0, -2.0, 5.0, 0.0]], [[2, 0.0, -2.0, 1.0, 1.0], [32, 4.0, 4.0, 7.0, 6.0], [14, 2.0, -4.0, 3.0, -4.0], [25, 3.0, -2.0, 6.0, 1.0], [24, 1.0, -1.0, 2.0, 1.0], [29, 9.0, -2.0, 9.0, 0.0]]], [[[2, 24], [2, 25]], [[2, 14], [2, 25], [2, 32], [24, 25], [29, 32]], 18]], [[[[26, -5.0, -4.0, -2.0, -2.0], [6, 4.0, 1.0, 5.0, 2.0], [18, -2.0, 2.0, -2.0, 2.0], [24, -4.0, -5.0, -2.0, -3.0], [19, -5.0, -2.0, -4.0, -1.0]], [[26, -6.0, -4.0, -3.0, -2.0], [6, 1.0, 1.0, 2.0, 2.0], [18, -5.0, 2.0, -5.0, 2.0], [24, -5.0, -5.0, -3.0, -3.0], [19, -3.0, -2.0, -2.0, -1.0]]], [[], [[18, 19]], 8]], [[[[18, -4.0, -5.0, -3.0, -4.0], [26, 4.0, -4.0, 6.0, -1.0], [8, -4.0, -4.0, -2.0, -3.0], [7, 5.0, 1.0, 5.0, 1.0], [3, 1.0, -2.0, 4.0, 0.0], [23, 2.0, -5.0, 2.0, -2.0]], [[18, -2.0, -6.0, -1.0, -5.0], [26, 5.0, -4.0, 7.0, -1.0], [8, -2.0, -5.0, 0.0, -4.0], [7, 5.0, 1.0, 5.0, 1.0], [3, 5.0, -3.0, 8.0, -1.0], [23, 1.0, -4.0, 1.0, -1.0]]], [[], [[3, 23]], 5]], [[[[13, 5.0, -2.0, 6.0, 0.0], [39, 4.0, 5.0, 7.0, 7.0], [11, 0.0, 5.0, 3.0, 5.0], [10, 3.0, -4.0, 4.0, -3.0], [18, -2.0, -4.0, -1.0, -2.0], [30, -3.0, -4.0, -1.0, -1.0], [36, 1.0, 1.0, 3.0, 3.0]], [[13, 2.0, -3.0, 3.0, -1.0], [39, 1.0, 5.0, 4.0, 7.0], [11, -3.0, 6.0, 0.0, 6.0], [10, 5.0, -5.0, 6.0, -4.0], [18, -2.0, -3.0, -1.0, -1.0], [30, 1.0, -5.0, 3.0, -2.0], [36, 2.0, 0.0, 4.0, 2.0]]], [[[13, 30]], [[10, 11], [10, 13], [10, 36], [10, 39], [11, 30], [11, 36], [18, 30]], 25]], [[[[20, -2.0, -4.0, 0.0, -4.0], [8, 0.0, -2.0, 0.0, 0.0], [2, 0.0, -4.0, 2.0, -3.0], [14, 1.0, 5.0, 2.0, 7.0], [39, -4.0, 3.0, -4.0, 5.0], [18, -3.0, -5.0, -3.0, -3.0]], [[20, -2.0, -4.0, 0.0, -4.0], [8, -3.0, -1.0, -3.0, 1.0], [2, 0.0, -4.0, 2.0, -3.0], [14, 2.0, 4.0, 3.0, 6.0], [39, -4.0, 4.0, -4.0, 6.0], [18, 1.0, -4.0, 1.0, -2.0]]], [[[2, 18], [18, 20]], [[2, 8], [8, 18], [8, 20], [18, 20]], 14]], [[[[38, -3.0, -5.0, -3.0, -4.0], [10, 4.0, 1.0, 6.0, 3.0], [15, 1.0, 0.0, 3.0, 3.0], [23, -4.0, -2.0, -1.0, 0.0], [24, -1.0, 3.0, 2.0, 4.0], [14, 3.0, -4.0, 5.0, -3.0], [26, -2.0, 3.0, 1.0, 5.0], [20, -5.0, 4.0, -4.0, 5.0]], [[38, -6.0, -6.0, -6.0, -5.0], [10, 1.0, 0.0, 3.0, 2.0], [15, 1.0, 1.0, 3.0, 4.0], [23, 0.0, -2.0, 3.0, 0.0], [24, 0.0, 2.0, 3.0, 3.0], [14, 5.0, -5.0, 7.0, -4.0], [26, -2.0, 2.0, 1.0, 4.0], [20, -3.0, 5.0, -2.0, 6.0]]], [[[10, 15], [10, 23], [10, 24], [10, 26]], [[10, 14], [14, 15], [20, 23], [20, 38], [23, 38]], 19]], [[[[34, 3.0, 5.0, 3.0, 7.0], [13, -3.0, -2.0, 0.0, 1.0], [31, 0.0, 1.0, 3.0, 3.0]], [[34, 3.0, 5.0, 3.0, 7.0], [13, -3.0, -1.0, 0.0, 2.0], [31, 0.0, 2.0, 3.0, 4.0]]], [[], [], 0]]], [[[[[39, 5.0, 0.0, 5.0, 3.0], [11, -4.0, 0.0, -4.0, 1.0], [18, -4.0, 1.0, -3.0, 3.0], [12, -2.0, 5.0, 1.0, 8.0], [36, 3.0, 0.0, 5.0, 0.0]], [[39, 7.0, 0.0, 7.0, 3.0], [11, -3.0, -1.0, -3.0, 0.0], [18, -2.0, 0.0, -1.0, 2.0], [12, -5.0, 5.0, -2.0, 8.0], [36, 5.0, 0.0, 7.0, 0.0]]], [[], [[11, 18]], 6]], [[[[8, -1.0, -1.0, -1.0, -1.0], [9, 4.0, 0.0, 4.0, 3.0], [30, -3.0, 5.0, -1.0, 5.0], [32, 0.0, 2.0, 1.0, 5.0], [3, -3.0, 1.0, 0.0, 1.0], [18, -2.0, 4.0, -2.0, 7.0], [23, 5.0, 2.0, 5.0, 2.0], [39, -4.0, 4.0, -1.0, 5.0]], [[8, 0.0, -1.0, 0.0, -1.0], [9, 1.0, -1.0, 1.0, 2.0], [30, -6.0, 4.0, -4.0, 4.0], [32, -1.0, 1.0, 0.0, 4.0], [3, -3.0, 2.0, 0.0, 2.0], [18, -3.0, 4.0, -3.0, 7.0], [23, 5.0, 1.0, 5.0, 1.0], [39, -4.0, 3.0, -1.0, 4.0]]], [[[32, 39]], [[3, 30], [8, 30], [8, 39], [18, 30]], 12]], [[[[19, -5.0, 4.0, -3.0, 6.0], [29, 2.0, 0.0, 4.0, 0.0], [7, -5.0, 3.0, -4.0, 5.0], [11, 2.0, 3.0, 5.0, 3.0]], [[19, -3.0, 4.0, -1.0, 6.0], [29, -1.0, 1.0, 1.0, 1.0], [7, -1.0, 3.0, 0.0, 5.0], [11, 1.0, 3.0, 4.0, 3.0]]], [[], [], 5]], [[[[7, 3.0, -1.0, 3.0, 0.0], [27, -5.0, -5.0, -2.0, -2.0], [15, 3.0, 5.0, 5.0, 6.0], [31, -2.0, -2.0, -2.0, -1.0], [26, 4.0, 1.0, 4.0, 3.0], [30, 3.0, -4.0, 5.0, -3.0], [29, 4.0, 4.0, 7.0, 4.0], [1, -5.0, -5.0, -3.0, -3.0], [39, 3.0, -2.0, 3.0, 1.0]], [[7, 7.0, -1.0, 7.0, 0.0], [27, -4.0, -5.0, -1.0, -2.0], [15, 2.0, 4.0, 4.0, 5.0], [31, -5.0, -1.0, -5.0, 0.0], [26, 3.0, 1.0, 3.0, 3.0], [30, 4.0, -3.0, 6.0, -2.0], [29, 6.0, 3.0, 9.0, 3.0], [1, -1.0, -5.0, 1.0, -3.0], [39, 5.0, -3.0, 5.0, 0.0]]], [[], [[1, 31], [7, 15], [7, 26], [7, 30], [7, 39], [15, 29], [15, 39], [26, 29], [26, 30], [26, 39], [27, 31]], 34]], [[[[1, 5.0, -4.0, 6.0, -1.0], [27, -1.0, 3.0, 2.0, 3.0]], [[1, 2.0, -4.0, 3.0, -1.0], [27, -1.0, 3.0, 2.0, 3.0]]], [[], [], 1]], [[[[38, 1.0, 3.0, 4.0, 6.0], [31, -2.0, -3.0, 1.0, -3.0], [37, 0.0, 1.0, 0.0, 3.0], [9, -5.0, 3.0, -5.0, 4.0], [4, -5.0, 4.0, -4.0, 6.0], [14, -1.0, -2.0, 0.0, 0.0], [35, -3.0, 5.0, -2.0, 5.0]], [[38, 1.0, 2.0, 4.0, 5.0], [31, -3.0, -3.0, 0.0, -3.0], [37, 4.0, 2.0, 4.0, 4.0], [9, -6.0, 2.0, -6.0, 3.0], [4, -3.0, 4.0, -2.0, 6.0], [14, -1.0, -2.0, 0.0, 0.0], [35, -3.0, 6.0, -2.0, 6.0]]], [[[4, 35], [37, 38]], [[4, 9], [14, 37], [31, 37], [31, 38]], 10]], [[[[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]], [[[[38, 0.0, 0.0, 1.0, 2.0], [20, -3.0, 5.0, -2.0, 7.0], [35, 2.0, 0.0, 5.0, 0.0], [39, 0.0, 1.0, 3.0, 1.0], [7, -4.0, -1.0, -2.0, 1.0], [19, 5.0, -3.0, 5.0, -1.0], [26, -2.0, -3.0, -1.0, -2.0], [21, -5.0, 3.0, -4.0, 4.0]], [[38, 4.0, 0.0, 5.0, 2.0], [20, -6.0, 6.0, -5.0, 8.0], [35, -1.0, 1.0, 2.0, 1.0], [39, 0.0, 2.0, 3.0, 2.0], [7, -7.0, -1.0, -5.0, 1.0], [19, 4.0, -4.0, 4.0, -2.0], [26, -2.0, -3.0, -1.0, -2.0], [21, -3.0, 4.0, -2.0, 5.0]]], [[[35, 38]], [[7, 21], [7, 26], [19, 35], [20, 21], [20, 26], [35, 38], [38, 39]], 24]]], [[[[[7, -2.0, 5.0, -2.0, 5.0], [15, 0.0, 1.0, 1.0, 1.0], [5, 4.0, -5.0, 5.0, -4.0], [2, 0.0, -2.0, 0.0, -1.0], [11, 4.0, 3.0, 6.0, 3.0], [34, -1.0, 5.0, -1.0, 6.0], [20, -1.0, -1.0, 2.0, 0.0]], [[7, -3.0, 5.0, -3.0, 5.0], [15, -1.0, 1.0, 0.0, 1.0], [5, 6.0, -6.0, 7.0, -5.0], [2, 2.0, -2.0, 2.0, -1.0], [11, 1.0, 2.0, 3.0, 2.0], [34, -4.0, 6.0, -4.0, 7.0], [20, -1.0, 0.0, 2.0, 1.0]]], [[], [[2, 15], [5, 11], [7, 34], [20, 34]], 15]], [[[[37, -1.0, 5.0, 0.0, 5.0], [38, -1.0, 4.0, 1.0, 7.0], [32, 4.0, -4.0, 5.0, -2.0], [31, -5.0, -2.0, -4.0, -1.0], [13, 4.0, 1.0, 5.0, 3.0]], [[37, -1.0, 5.0, 0.0, 5.0], [38, 0.0, 3.0, 2.0, 6.0], [32, 8.0, -3.0, 9.0, -1.0], [31, -1.0, -3.0, 0.0, -2.0], [13, 4.0, 2.0, 5.0, 4.0]]], [[], [[13, 32]], 3]], [[[[9, 4.0, -4.0, 5.0, -3.0], [28, -4.0, 1.0, -4.0, 3.0], [22, 5.0, 3.0, 5.0, 5.0], [17, 0.0, 2.0, 0.0, 2.0], [24, 5.0, 0.0, 6.0, 2.0], [21, -1.0, -3.0, 2.0, -3.0], [6, 3.0, -3.0, 5.0, -2.0], [32, -4.0, -4.0, -4.0, -1.0], [18, 3.0, 4.0, 6.0, 5.0], [8, 2.0, 3.0, 4.0, 5.0]], [[9, 6.0, -4.0, 7.0, -3.0], [28, -4.0, 1.0, -4.0, 3.0], [22, 9.0, 4.0, 9.0, 6.0], [17, 0.0, 1.0, 0.0, 1.0], [24, 9.0, -1.0, 10.0, 1.0], [21, -4.0, -3.0, -1.0, -3.0], [6, 3.0, -3.0, 5.0, -2.0], [32, -7.0, -5.0, -7.0, -2.0], [18, 2.0, 3.0, 5.0, 4.0], [8, 6.0, 3.0, 8.0, 5.0]]], [[], [[6, 8], [6, 9], [6, 22], [6, 24], [8, 18], [8, 21], [9, 18], [9, 22], [9, 24], [17, 21], [18, 22], [18, 24], [28, 32]], 25]], [[[[34, 4.0, -3.0, 5.0, -2.0], [39, -5.0, 2.0, -5.0, 5.0]], [[34, 1.0, -3.0, 2.0, -2.0], [39, -5.0, 1.0, -5.0, 4.0]]], [[], [], 0]], [[[[15, -1.0, -1.0, 2.0, 0.0], [13, 4.0, -1.0, 7.0, 2.0], [4, 5.0, 3.0, 7.0, 5.0], [30, 1.0, 1.0, 2.0, 3.0], [26, -3.0, -3.0, -2.0, -1.0], [21, -1.0, 3.0, 0.0, 3.0], [6, 2.0, 5.0, 2.0, 6.0]], [[15, 1.0, -2.0, 4.0, -1.0], [13, 4.0, -1.0, 7.0, 2.0], [4, 4.0, 3.0, 6.0, 5.0], [30, 3.0, 1.0, 4.0, 3.0], [26, -3.0, -4.0, -2.0, -2.0], [21, 1.0, 3.0, 2.0, 3.0], [6, 2.0, 5.0, 2.0, 6.0]]], [[[4, 30], [13, 15], [13, 30]], [[6, 30]], 7]], [[[[13, 2.0, 3.0, 5.0, 3.0], [8, 0.0, 5.0, 0.0, 8.0], [18, 1.0, 2.0, 1.0, 2.0], [15, 2.0, 1.0, 2.0, 3.0]], [[13, 2.0, 2.0, 5.0, 2.0], [8, 1.0, 4.0, 1.0, 7.0], [18, 1.0, 2.0, 1.0, 2.0], [15, 6.0, 2.0, 6.0, 4.0]]], [[], [[13, 15]], 3]], [[[[15, 4.0, 1.0, 5.0, 1.0], [23, 0.0, 5.0, 2.0, 5.0], [18, -5.0, 4.0, -2.0, 5.0], [39, -3.0, 0.0, -2.0, 2.0], [4, -1.0, 4.0, 2.0, 5.0], [7, 3.0, 1.0, 4.0, 2.0], [16, -3.0, -3.0, -2.0, 0.0]], [[15, 4.0, 0.0, 5.0, 0.0], [23, 2.0, 5.0, 4.0, 5.0], [18, -6.0, 4.0, -3.0, 5.0], [39, 1.0, -1.0, 2.0, 1.0], [4, -1.0, 3.0, 2.0, 4.0], [7, 0.0, 1.0, 1.0, 2.0], [16, -6.0, -3.0, -5.0, 0.0]]], [[[7, 39]], [[7, 15], [7, 23], [16, 39], [18, 39]], 16]], [[[[15, -4.0, 0.0, -4.0, 1.0], [38, 5.0, 5.0, 6.0, 8.0], [35, -5.0, 1.0, -2.0, 2.0], [22, -3.0, 4.0, 0.0, 7.0], [3, 2.0, 0.0, 2.0, 0.0], [32, 3.0, 5.0, 4.0, 8.0], [11, 0.0, 0.0, 3.0, 1.0], [24, 4.0, 0.0, 4.0, 2.0]], [[15, 0.0, 0.0, 0.0, 1.0], [38, 5.0, 6.0, 6.0, 9.0], [35, -3.0, 1.0, 0.0, 2.0], [22, 1.0, 4.0, 4.0, 7.0], [3, 3.0, 0.0, 3.0, 0.0], [32, 2.0, 5.0, 3.0, 8.0], [11, 0.0, -1.0, 3.0, 0.0], [24, 1.0, 0.0, 1.0, 2.0]]], [[[3, 24], [11, 15], [11, 24], [22, 32]], [[3, 24], [22, 35], [24, 32]], 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-event-pair-orientation","generated_at":"2026-09-29T14:51:02.370411+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":"Normalize to (min,max).","root_cause":"p = (e id, f id).","sha256":"82a7e69e8583203741a23eafd54b993c525581ca4a44c8bc395e5be2d577091b","title":"Swap events record pairs in swap orientation · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verification":{"attempt":{"elapsed_ms":42.608,"exit_code":1,"observations":[{"actual":[[[10,32]],[[2,27],[10,14]],15],"check":"case 0","expected":[[[10,32]],[[2,27],[10,14]],15],"passed":true},{"actual":[[[20,5]],[],1],"check":"case 1","expected":[[[5,20]],[],1],"passed":false},{"actual":[[],[[4,35]],3],"check":"case 2","expected":[[],[[4,35]],3],"passed":true},{"actual":[[],[[8,5],[22,21]],5],"check":"case 3","expected":[[],[[5,8],[21,22]],5],"passed":false},{"actual":[[],[[11,4],[30,4]],4],"check":"case 4","expected":[[],[[4,11],[4,30]],4],"passed":false},{"actual":[[[29,17],[29,28]],[[38,17]],6],"check":"case 5","expected":[[[17,29],[28,29]],[[17,38]],6],"passed":false},{"actual":[[],[[12,5],[33,5]],5],"check":"case 6","expected":[[],[[5,12],[5,33]],5],"passed":false},{"actual":[[[29,38]],[[29,2],[29,38]],5],"check":"case 7","expected":[[[29,38]],[[2,29],[29,38]],5],"passed":false}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"case 0\", \"actual\": [[[10, 32]], [[2, 27], [10, 14]], 15], \"expected\": [[[10, 32]], [[2, 27], [10, 14]], 15], \"passed\": true}, {\"check\": \"case 1\", \"actual\": [[[20, 5]], [], 1], \"expected\": [[[5, 20]], [], 1], \"passed\": false}, {\"check\": \"case 2\", \"actual\": [[], [[4, 35]], 3], \"expected\": [[], [[4, 35]], 3], \"passed\": true}, {\"check\": \"case 3\", \"actual\": [[], [[8, 5], [22, 21]], 5], \"expected\": [[], [[5, 8], [21, 22]], 5], \"passed\": false}, {\"check\": \"case 4\", \"actual\": [[], [[11, 4], [30, 4]], 4], \"expected\": [[], [[4, 11], [4, 30]], 4], \"passed\": false}, {\"check\": \"case 5\", \"actual\": [[[29, 17], [29, 28]], [[38, 17]], 6], \"expected\": [[[17, 29], [28, 29]], [[17, 38]], 6], \"passed\": false}, {\"check\": \"case 6\", \"actual\": [[], [[12, 5], [33, 5]], 5], \"expected\": [[], [[5, 12], [5, 33]], 5], \"passed\": false}, {\"check\": \"case 7\", \"actual\": [[[29, 38]], [[29, 2], [29, 38]], 5], \"expected\": [[[29, 38]], [[2, 29], [29, 38]], 5], \"passed\": false}], \"passed\": false}\n"},"broken":{"elapsed_ms":43.445,"exit_code":1,"observations":[{"actual":[[[32,10]],[[14,10],[27,2]],15],"check":"case 0","expected":[[[10,32]],[[2,27],[10,14]],15],"passed":false},{"actual":[[[5,20]],[],1],"check":"case 1","expected":[[[5,20]],[],1],"passed":true},{"actual":[[],[[35,4]],3],"check":"case 2","expected":[[],[[4,35]],3],"passed":false},{"actual":[[],[[5,8],[21,22]],5],"check":"case 3","expected":[[],[[5,8],[21,22]],5],"passed":true},{"actual":[[],[[4,11],[4,30]],4],"check":"case 4","expected":[[],[[4,11],[4,30]],4],"passed":true},{"actual":[[[17,29],[28,29]],[[17,38]],6],"check":"case 5","expected":[[[17,29],[28,29]],[[17,38]],6],"passed":true},{"actual":[[],[[5,12],[5,33]],5],"check":"case 6","expected":[[],[[5,12],[5,33]],5],"passed":true},{"actual":[[[38,29]],[[2,29],[38,29]],5],"check":"case 7","expected":[[[29,38]],[[2,29],[29,38]],5],"passed":false}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"case 0\", \"actual\": [[[32, 10]], [[14, 10], [27, 2]], 15], \"expected\": [[[10, 32]], [[2, 27], [10, 14]], 15], \"passed\": false}, {\"check\": \"case 1\", \"actual\": [[[5, 20]], [], 1], \"expected\": [[[5, 20]], [], 1], \"passed\": true}, {\"check\": \"case 2\", \"actual\": [[], [[35, 4]], 3], \"expected\": [[], [[4, 35]], 3], \"passed\": false}, {\"check\": \"case 3\", \"actual\": [[], [[5, 8], [21, 22]], 5], \"expected\": [[], [[5, 8], [21, 22]], 5], \"passed\": true}, {\"check\": \"case 4\", \"actual\": [[], [[4, 11], [4, 30]], 4], \"expected\": [[], [[4, 11], [4, 30]], 4], \"passed\": true}, {\"check\": \"case 5\", \"actual\": [[[17, 29], [28, 29]], [[17, 38]], 6], \"expected\": [[[17, 29], [28, 29]], [[17, 38]], 6], \"passed\": true}, {\"check\": \"case 6\", \"actual\": [[], [[5, 12], [5, 33]], 5], \"expected\": [[], [[5, 12], [5, 33]], 5], \"passed\": true}, {\"check\": \"case 7\", \"actual\": [[[38, 29]], [[2, 29], [38, 29]], 5], \"expected\": [[[29, 38]], [[2, 29], [29, 38]], 5], \"passed\": false}], \"passed\": false}\n"},"fixed":{"elapsed_ms":43.454,"exit_code":0,"observations":[{"actual":[[[10,32]],[[2,27],[10,14]],15],"check":"case 0","expected":[[[10,32]],[[2,27],[10,14]],15],"passed":true},{"actual":[[[5,20]],[],1],"check":"case 1","expected":[[[5,20]],[],1],"passed":true},{"actual":[[],[[4,35]],3],"check":"case 2","expected":[[],[[4,35]],3],"passed":true},{"actual":[[],[[5,8],[21,22]],5],"check":"case 3","expected":[[],[[5,8],[21,22]],5],"passed":true},{"actual":[[],[[4,11],[4,30]],4],"check":"case 4","expected":[[],[[4,11],[4,30]],4],"passed":true},{"actual":[[[17,29],[28,29]],[[17,38]],6],"check":"case 5","expected":[[[17,29],[28,29]],[[17,38]],6],"passed":true},{"actual":[[],[[5,12],[5,33]],5],"check":"case 6","expected":[[],[[5,12],[5,33]],5],"passed":true},{"actual":[[[29,38]],[[2,29],[29,38]],5],"check":"case 7","expected":[[[29,38]],[[2,29],[29,38]],5],"passed":true}],"passed":true,"stderr":"","stdout":"{\"observations\": [{\"check\": \"case 0\", \"actual\": [[[10, 32]], [[2, 27], [10, 14]], 15], \"expected\": [[[10, 32]], [[2, 27], [10, 14]], 15], \"passed\": true}, {\"check\": \"case 1\", \"actual\": [[[5, 20]], [], 1], \"expected\": [[[5, 20]], [], 1], \"passed\": true}, {\"check\": \"case 2\", \"actual\": [[], [[4, 35]], 3], \"expected\": [[], [[4, 35]], 3], \"passed\": true}, {\"check\": \"case 3\", \"actual\": [[], [[5, 8], [21, 22]], 5], \"expected\": [[], [[5, 8], [21, 22]], 5], \"passed\": true}, {\"check\": \"case 4\", \"actual\": [[], [[4, 11], [4, 30]], 4], \"expected\": [[], [[4, 11], [4, 30]], 4], \"passed\": true}, {\"check\": \"case 5\", \"actual\": [[[17, 29], [28, 29]], [[17, 38]], 6], \"expected\": [[[17, 29], [28, 29]], [[17, 38]], 6], \"passed\": true}, {\"check\": \"case 6\", \"actual\": [[], [[5, 12], [5, 33]], 5], \"expected\": [[], [[5, 12], [5, 33]], 5], \"passed\": true}, {\"check\": \"case 7\", \"actual\": [[[29, 38]], [[2, 29], [29, 38]], 5], \"expected\": [[[29, 38]], [[2, 29], [29, 38]], 5], \"passed\": true}], \"passed\": true}\n"}},"verified":true,"visibility":"public"}