{"abstract":"Every leaf under an overlapping parent is returned as a hit.","category":"Collision detection broadphase","checks":8,"contract":"solve(nodes, q): BVH nodes [minx,miny,maxx,maxy,left,right,leaf_id], leaves have left=-1; root is node 0. Stack traversal tests every popped node against the closed query box (counting each test) and descends only into overlapping internal nodes. Return [sorted leaf ids overlapping q, number of node tests].","evaluation_group":"w2-collision_detection_broadphase-bvh-stack-query","failed_approach":"Testing leaves but not counting the tests hides the traversal cost.","family":"w2-collision_detection_broadphase-bvh-stack-query-leaf-overlap-test","id":"FA-87461","implementations":{"attempt":{"sha256":"f5697213328a1ab7e95ea42d1f4966bd49e2783edbeb4e98bcc09858440ef939","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nimport math\nN = 1\nobservations = []\ndef solve(nodes, q):\n    if not nodes:\n        return [[], 0]\n    stack = [0]\n    hits = []\n    tests = 0\n    while stack:\n        i = stack.pop()\n        nd = nodes[i]\n        tests += 1 if nd[4] >= 0 else 0\n        if not (nd[0] <= q[2] and q[0] <= nd[2] and nd[1] <= q[3] and q[1] <= nd[3]):\n            continue\n        if nd[4] < 0:\n            hits.append(nd[6])\n        else:\n            stack.append(nd[4])\n            stack.append(nd[5])\n    return [sorted(hits), tests]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\nfixtures = [[[[[[0, 2, 12, 12, 1, 4, -1], [0, 2, 7, 4, 2, 3, -1], [0, 4, 2, 4, -1, -1, 100], [5, 2, 7, 2, -1, -1, 103], [8, 4, 12, 12, 5, 6, -1], [8, 4, 9, 6, -1, -1, 104], [10, 6, 12, 12, 7, 8, -1], [11, 10, 11, 12, -1, -1, 101], [10, 6, 12, 8, -1, -1, 102]], [6, 5, 7, 7]], [[], 3]], [[[[2, 1, 11, 12, 1, 6, -1], [2, 1, 6, 5, 2, 3, -1], [2, 1, 5, 3, -1, -1, 104], [5, 2, 6, 5, 4, 5, -1], [5, 2, 5, 5, -1, -1, 103], [6, 3, 6, 3, -1, -1, 105], [6, 1, 11, 12, 7, 10, -1], [6, 1, 8, 12, 8, 9, -1], [6, 11, 7, 12, -1, -1, 102], [6, 1, 8, 2, -1, -1, 106], [9, 6, 11, 8, 11, 12, -1], [9, 6, 9, 7, -1, -1, 101], [10, 6, 11, 8, -1, -1, 100]], [7, 6, 10, 9]], [[100, 101], 9]], [[[[0, 4, 13, 14, 1, 6, -1], [0, 4, 5, 14, 2, 3, -1], [0, 4, 1, 4, -1, -1, 104], [1, 6, 5, 14, 4, 5, -1], [1, 6, 3, 7, -1, -1, 102], [2, 12, 5, 14, -1, -1, 105], [6, 4, 13, 13, 7, 10, -1], [6, 11, 8, 13, 8, 9, -1], [6, 11, 8, 13, -1, -1, 101], [7, 11, 8, 11, -1, -1, 100], [7, 4, 13, 7, 11, 12, -1], [7, 4, 8, 4, -1, -1, 106], [12, 5, 13, 7, -1, -1, 103]], [0, 2, 0, 4]], [[104], 5]], [[[[0, 5, 8, 13, 1, 4, -1], [0, 5, 1, 13, 2, 3, -1], [0, 5, 0, 6, -1, -1, 101], [1, 12, 1, 13, -1, -1, 104], [5, 8, 8, 13, 5, 6, -1], [5, 8, 7, 10, -1, -1, 102], [6, 12, 8, 13, 7, 8, -1], [6, 12, 7, 12, -1, -1, 103], [6, 12, 8, 13, -1, -1, 100]], [12, 3, 13, 6]], [[], 1]], [[[[1, 1, 13, 15, 1, 6, -1], [1, 1, 8, 11, 2, 3, -1], [1, 9, 4, 11, -1, -1, 100], [2, 1, 8, 5, 4, 5, -1], [2, 3, 4, 5, -1, -1, 104], [6, 1, 8, 3, -1, -1, 103], [6, 4, 13, 15, 7, 8, -1], [6, 4, 9, 6, -1, -1, 105], [10, 10, 13, 15, 9, 10, -1], [10, 12, 12, 15, -1, -1, 101], [10, 10, 13, 12, -1, -1, 102]], [1, 8, 5, 11]], [[100], 5]], [[[[0, 1, 13, 15, 1, 6, -1], [0, 6, 5, 15, 2, 3, -1], [0, 12, 0, 15, -1, -1, 100], [2, 6, 5, 12, 4, 5, -1], [2, 10, 5, 12, -1, -1, 103], [3, 6, 5, 8, -1, -1, 101], [8, 1, 13, 7, 7, 8, -1], [8, 1, 9, 4, -1, -1, 104], [9, 4, 13, 7, 9, 10, -1], [9, 5, 11, 7, -1, -1, 105], [11, 4, 13, 5, -1, -1, 102]], [3, 11, 6, 12]], [[103], 7]], [[[[3, 5, 10, 10, 1, 2, -1], [3, 5, 4, 7, -1, -1, 100], [4, 6, 10, 10, 3, 4, -1], [4, 10, 6, 10, -1, -1, 102], [8, 6, 10, 8, -1, -1, 101]], [3, 3, 6, 4]], [[], 1]], [[[[0, 1, 12, 12, 1, 2, -1], [0, 9, 3, 10, -1, -1, 102], [10, 1, 12, 12, 3, 4, -1], [10, 11, 10, 12, -1, -1, 101], [11, 1, 12, 4, -1, -1, 100]], [4, 10, 8, 10]], [[], 3]]], [[[[[4, 0, 10, 13, 1, 6, -1], [4, 5, 7, 12, 2, 3, -1], [4, 8, 4, 8, -1, -1, 103], [5, 5, 7, 12, 4, 5, -1], [5, 11, 5, 12, -1, -1, 105], [6, 5, 7, 8, -1, -1, 102], [7, 0, 10, 13, 7, 8, -1], [7, 0, 7, 2, -1, -1, 101], [8, 2, 10, 13, 9, 10, -1], [8, 2, 10, 2, -1, -1, 100], [9, 12, 10, 13, -1, -1, 104]], [3, 9, 5, 13]], [[105], 7]], [[[[9, 4, 14, 10, 1, 4, -1], [9, 8, 12, 10, 2, 3, -1], [9, 9, 12, 10, -1, -1, 101], [10, 8, 11, 9, -1, -1, 102], [9, 4, 14, 10, 5, 6, -1], [9, 10, 12, 10, -1, -1, 103], [12, 4, 14, 4, -1, -1, 100]], [7, 5, 7, 8]], [[], 1]], [[[[2, 3, 15, 14, 1, 8, -1], [2, 3, 11, 12, 2, 5, -1], [2, 5, 10, 12, 3, 4, -1], [2, 5, 3, 7, -1, -1, 100], [8, 12, 10, 12, -1, -1, 105], [8, 3, 11, 6, 6, 7, -1], [8, 3, 11, 3, -1, -1, 101], [11, 4, 11, 6, -1, -1, 102], [12, 4, 15, 14, 9, 12, -1], [12, 4, 13, 14, 10, 11, -1], [12, 11, 13, 14, -1, -1, 103], [12, 4, 13, 6, -1, -1, 104], [12, 5, 15, 10, 13, 14, -1], [12, 5, 13, 7, -1, -1, 107], [12, 7, 15, 10, -1, -1, 106]], [3, 2, 3, 2]], [[], 1]], [[[[0, 0, 12, 11, 1, 4, -1], [0, 6, 3, 11, 2, 3, -1], [1, 10, 1, 11, -1, -1, 101], [0, 6, 3, 8, -1, -1, 104], [5, 0, 12, 4, 5, 6, -1], [5, 1, 5, 3, -1, -1, 103], [8, 0, 12, 4, 7, 8, -1], [8, 0, 9, 0, -1, -1, 102], [11, 4, 12, 4, -1, -1, 100]], [11, 9, 14, 11]], [[], 3]], [[[[1, 3, 12, 12, 1, 6, -1], [1, 4, 6, 6, 2, 3, -1], [1, 5, 1, 6, -1, -1, 103], [5, 4, 6, 6, 4, 5, -1], [5, 4, 6, 5, -1, -1, 100], [6, 5, 6, 6, -1, -1, 104], [7, 3, 12, 12, 7, 8, -1], [7, 3, 9, 6, -1, -1, 105], [8, 3, 12, 12, 9, 10, -1], [8, 10, 10, 12, -1, -1, 101], [11, 3, 12, 6, -1, -1, 102]], [9, 6, 13, 6]], [[102, 105], 7]], [[[[1, 0, 12, 14, 1, 4, -1], [1, 2, 3, 5, 2, 3, -1], [2, 2, 2, 2, -1, -1, 101], [1, 3, 3, 5, -1, -1, 102], [2, 0, 12, 14, 5, 6, -1], [2, 6, 4, 8, -1, -1, 104], [3, 0, 12, 14, 7, 8, -1], [3, 12, 4, 14, -1, -1, 100], [11, 0, 12, 0, -1, -1, 103]], [11, 10, 14, 13]], [[], 7]], [[[[1, 0, 12, 11, 1, 6, -1], [1, 0, 4, 11, 2, 3, -1], [1, 0, 2, 0, -1, -1, 100], [2, 7, 4, 11, 4, 5, -1], [2, 7, 2, 7, -1, -1, 105], [3, 11, 4, 11, -1, -1, 104], [5, 4, 12, 8, 7, 8, -1], [5, 6, 5, 8, -1, -1, 102], [6, 4, 12, 6, 9, 10, -1], [6, 4, 8, 6, -1, -1, 101], [10, 4, 12, 4, -1, -1, 103]], [6, 7, 7, 7]], [[], 5]], [[[[0, 5, 14, 14, 1, 6, -1], [0, 5, 5, 14, 2, 3, -1], [0, 5, 0, 8, -1, -1, 105], [2, 8, 5, 14, 4, 5, -1], [2, 12, 3, 14, -1, -1, 103], [4, 8, 5, 9, -1, -1, 102], [6, 11, 14, 12, 7, 8, -1], [6, 11, 9, 11, -1, -1, 101], [10, 11, 14, 12, 9, 10, -1], [10, 11, 13, 11, -1, -1, 100], [11, 12, 14, 12, -1, -1, 104]], [2, 2, 5, 6]], [[], 5]]], [[[[[4, 2, 6, 13, 1, 2, -1], [4, 11, 6, 13, -1, -1, 100], [4, 2, 6, 8, 3, 4, -1], [4, 2, 6, 4, -1, -1, 102], [6, 6, 6, 8, -1, -1, 101]], [11, 12, 11, 13]], [[], 1]], [[[[0, 0, 14, 11, 1, 8, -1], [0, 4, 2, 11, 2, 5, -1], [0, 6, 2, 9, 3, 4, -1], [0, 6, 1, 9, -1, -1, 106], [0, 9, 2, 9, -1, -1, 104], [1, 4, 2, 11, 6, 7, -1], [1, 8, 2, 11, -1, -1, 101], [1, 4, 2, 6, -1, -1, 107], [2, 0, 14, 11, 9, 12, -1], [2, 0, 6, 11, 10, 11, -1], [2, 0, 4, 1, -1, -1, 105], [6, 10, 6, 11, -1, -1, 100], [8, 1, 14, 10, 13, 14, -1], [8, 2, 9, 4, -1, -1, 103], [9, 1, 14, 10, 15, 16, -1], [9, 9, 12, 10, -1, -1, 108], [11, 1, 14, 1, -1, -1, 102]], [4, 6, 5, 7]], [[], 7]], [[[[7, 6, 14, 12, 1, 4, -1], [7, 6, 9, 8, 2, 3, -1], [7, 6, 8, 8, -1, -1, 102], [7, 7, 9, 7, -1, -1, 103], [10, 7, 14, 12, 5, 6, -1], [10, 10, 13, 12, -1, -1, 101], [11, 7, 14, 7, -1, -1, 100]], [11, 6, 12, 10]], [[100, 101], 5]], [[[[0, 0, 11, 14, 1, 8, -1], [0, 1, 8, 10, 2, 5, -1], [0, 4, 3, 9, 3, 4, -1], [0, 4, 1, 4, -1, -1, 101], [3, 9, 3, 9, -1, -1, 106], [3, 1, 8, 10, 6, 7, -1], [3, 10, 6, 10, -1, -1, 104], [7, 1, 8, 4, -1, -1, 103], [8, 0, 11, 14, 9, 12, -1], [8, 0, 11, 14, 10, 11, -1], [8, 11, 10, 14, -1, -1, 107], [8, 0, 11, 3, -1, -1, 100], [9, 8, 11, 14, 13, 14, -1], [9, 8, 10, 8, -1, -1, 105], [11, 11, 11, 14, -1, -1, 102]], [12, 2, 14, 4]], [[], 1]], [[[[2, 0, 14, 14, 1, 8, -1], [2, 4, 5, 14, 2, 5, -1], [2, 5, 4, 12, 3, 4, -1], [2, 11, 2, 12, -1, -1, 106], [4, 5, 4, 5, -1, -1, 102], [4, 4, 5, 14, 6, 7, -1], [4, 4, 5, 7, -1, -1, 107], [5, 12, 5, 14, -1, -1, 105], [7, 0, 14, 8, 9, 12, -1], [7, 0, 10, 3, 10, 11, -1], [7, 0, 7, 3, -1, -1, 104], [8, 1, 10, 2, -1, -1, 101], [8, 0, 14, 8, 13, 14, -1], [8, 5, 11, 8, -1, -1, 100], [12, 0, 14, 3, -1, -1, 103]], [6, 0, 8, 1]], [[101, 104], 9]], [[[[10, 2, 11, 5, -1, -1, 100]], [0, 11, 3, 14]], [[], 1]], [[[[0, 0, 15, 14, 1, 8, -1], [0, 7, 7, 14, 2, 5, -1], [0, 7, 2, 13, 3, 4, -1], [0, 11, 2, 13, -1, -1, 106], [1, 7, 1, 10, -1, -1, 107], [6, 10, 7, 14, 6, 7, -1], [6, 10, 6, 11, -1, -1, 105], [6, 11, 7, 14, -1, -1, 104], [8, 0, 15, 11, 9, 12, -1], [8, 6, 13, 11, 10, 11, -1], [8, 9, 10, 11, -1, -1, 103], [11, 6, 13, 9, -1, -1, 100], [11, 0, 15, 9, 13, 14, -1], [11, 0, 13, 0, -1, -1, 102], [12, 9, 15, 9, -1, -1, 101]], [10, 4, 11, 7]], [[100], 9]], [[[[2, 0, 14, 13, 1, 8, -1], [2, 1, 7, 13, 2, 5, -1], [2, 1, 4, 7, 3, 4, -1], [2, 1, 2, 3, -1, -1, 104], [2, 5, 4, 7, -1, -1, 101], [4, 4, 7, 13, 6, 7, -1], [4, 11, 5, 13, -1, -1, 103], [7, 4, 7, 4, -1, -1, 102], [8, 0, 14, 10, 9, 12, -1], [8, 4, 9, 4, 10, 11, -1], [8, 4, 8, 4, -1, -1, 100], [8, 4, 9, 4, -1, -1, 105], [10, 0, 14, 10, 13, 14, -1], [10, 8, 12, 10, -1, -1, 107], [11, 0, 14, 5, 15, 16, -1], [11, 0, 12, 2, -1, -1, 106], [12, 4, 14, 5, -1, -1, 108]], [12, 12, 14, 16]], [[], 3]]], [[[[[0, 1, 14, 13, 1, 10, -1], [0, 1, 3, 13, 2, 5, -1], [0, 2, 2, 13, 3, 4, -1], [0, 11, 1, 13, -1, -1, 104], [0, 2, 2, 2, -1, -1, 106], [0, 1, 3, 12, 6, 7, -1], [0, 11, 3, 12, -1, -1, 102], [1, 1, 3, 7, 8, 9, -1], [1, 1, 3, 2, -1, -1, 107], [3, 4, 3, 7, -1, -1, 109], [4, 3, 14, 12, 11, 14, -1], [4, 7, 7, 10, 12, 13, -1], [4, 8, 5, 10, -1, -1, 101], [4, 7, 7, 9, -1, -1, 105], [8, 3, 14, 12, 15, 16, -1], [8, 10, 11, 12, -1, -1, 108], [11, 3, 14, 8, 17, 18, -1], [11, 7, 13, 8, -1, -1, 103], [11, 3, 14, 4, -1, -1, 100]], [8, 3, 8, 7]], [[], 7]], [[[[5, 0, 6, 10, 1, 2, -1], [5, 0, 5, 0, -1, -1, 101], [6, 7, 6, 10, -1, -1, 100]], [9, 9, 13, 13]], [[], 1]], [[[[5, 4, 7, 4, -1, -1, 100]], [10, 7, 10, 11]], [[], 1]], [[[[1, 0, 15, 13, 1, 8, -1], [1, 2, 4, 8, 2, 5, -1], [1, 5, 3, 8, 3, 4, -1], [1, 5, 3, 7, -1, -1, 101], [1, 6, 3, 8, -1, -1, 106], [1, 2, 4, 4, 6, 7, -1], [1, 2, 4, 2, -1, -1, 103], [4, 3, 4, 4, -1, -1, 104], [3, 0, 15, 13, 9, 12, -1], [3, 0, 6, 3, 10, 11, -1], [3, 1, 6, 2, -1, -1, 108], [5, 0, 5, 3, -1, -1, 105], [9, 9, 15, 13, 13, 14, -1], [9, 11, 10, 13, -1, -1, 102], [12, 9, 15, 11, 15, 16, -1], [12, 9, 13, 10, -1, -1, 100], [12, 10, 15, 11, -1, -1, 107]], [6, 10, 6, 13]], [[], 5]], [[[[2, 1, 7, 8, 1, 2, -1], [2, 1, 5, 2, -1, -1, 101], [4, 5, 7, 8, 3, 4, -1], [4, 6, 7, 8, -1, -1, 102], [5, 5, 7, 8, -1, -1, 100]], [5, 9, 6, 12]], [[], 1]], [[[[8, 5, 9, 12, 1, 2, -1], [8, 10, 9, 12, -1, -1, 100], [8, 5, 9, 5, -1, -1, 101]], [5, 7, 5, 9]], [[], 1]], [[[[1, 1, 12, 13, 1, 6, -1], [1, 1, 7, 13, 2, 3, -1], [1, 11, 2, 13, -1, -1, 102], [4, 1, 7, 13, 4, 5, -1], [5, 1, 5, 3, -1, -1, 104], [4, 11, 7, 13, -1, -1, 103], [5, 1, 12, 6, 7, 8, -1], [5, 1, 7, 2, -1, -1, 101], [10, 2, 12, 6, 9, 10, -1], [10, 6, 12, 6, -1, -1, 100], [12, 2, 12, 4, -1, -1, 105]], [6, 6, 8, 9]], [[], 9]], [[[[0, 0, 14, 14, 1, 6, -1], [0, 4, 6, 14, 2, 3, -1], [0, 4, 0, 5, -1, -1, 102], [1, 7, 6, 14, 4, 5, -1], [1, 7, 1, 8, -1, -1, 103], [6, 11, 6, 14, -1, -1, 104], [8, 0, 14, 14, 7, 10, -1], [8, 0, 11, 7, 8, 9, -1], [8, 5, 11, 7, -1, -1, 101], [9, 0, 11, 3, -1, -1, 100], [11, 6, 14, 14, 11, 12, -1], [11, 6, 14, 8, -1, -1, 106], [12, 12, 14, 14, -1, -1, 105]], [12, 9, 15, 9]], [[], 7]]], [[[[[8, 0, 13, 15, 1, 4, -1], [8, 4, 12, 15, 2, 3, -1], [8, 12, 9, 15, -1, -1, 100], [9, 4, 12, 4, -1, -1, 101], [10, 0, 13, 11, 5, 6, -1], [10, 8, 12, 11, -1, -1, 102], [11, 0, 13, 3, -1, -1, 103]], [2, 0, 5, 1]], [[], 1]], [[[[3, 3, 12, 13, 1, 6, -1], [3, 8, 8, 13, 2, 3, -1], [3, 10, 6, 13, -1, -1, 104], [5, 8, 8, 11, 4, 5, -1], [5, 9, 5, 9, -1, -1, 101], [5, 8, 8, 11, -1, -1, 100], [6, 3, 12, 11, 7, 8, -1], [6, 8, 8, 11, -1, -1, 103], [9, 3, 12, 11, 9, 10, -1], [9, 8, 12, 11, -1, -1, 105], [11, 3, 11, 5, -1, -1, 102]], [11, 11, 14, 12]], [[105], 7]], [[[[0, 0, 8, 14, 1, 4, -1], [0, 0, 2, 3, 2, 3, -1], [0, 0, 2, 2, -1, -1, 101], [0, 0, 2, 3, -1, -1, 104], [0, 9, 8, 14, 5, 6, -1], [0, 9, 3, 12, -1, -1, 102], [6, 12, 8, 14, 7, 8, -1], [6, 12, 6, 14, -1, -1, 103], [6, 12, 8, 14, -1, -1, 100]], [5, 9, 9, 11]], [[], 5]], [[[[0, 2, 13, 12, 1, 4, -1], [0, 5, 5, 8, 2, 3, -1], [0, 5, 1, 7, -1, -1, 103], [2, 8, 5, 8, -1, -1, 104], [8, 2, 13, 12, 5, 6, -1], [8, 11, 11, 12, -1, -1, 100], [11, 2, 13, 5, 7, 8, -1], [11, 2, 13, 2, -1, -1, 101], [12, 4, 12, 5, -1, -1, 102]], [8, 4, 10, 7]], [[], 5]], [[[[0, 0, 15, 15, 1, 10, -1], [0, 0, 11, 14, 2, 5, -1], [0, 5, 1, 14, 3, 4, -1], [0, 5, 0, 8, -1, -1, 110], [1, 12, 1, 14, -1, -1, 105], [8, 0, 11, 10, 6, 7, -1], [8, 1, 10, 2, -1, -1, 102], [8, 0, 11, 10, 8, 9, -1], [8, 0, 10, 1, -1, -1, 108], [8, 8, 11, 10, -1, -1, 101], [10, 2, 15, 15, 11, 16, -1], [10, 6, 12, 15, 12, 13, -1], [10, 6, 12, 7, -1, -1, 104], [10, 11, 12, 15, 14, 15, -1], [10, 11, 12, 14, -1, -1, 106], [11, 12, 12, 15, -1, -1, 100], [11, 2, 15, 11, 17, 18, -1], [11, 11, 13, 11, -1, -1, 109], [11, 2, 15, 7, 19, 20, -1], [11, 7, 14, 7, -1, -1, 103], [12, 2, 15, 5, -1, -1, 107]], [10, 9, 10, 12]], [[101, 106], 15]], [[[[1, 0, 11, 11, 1, 6, -1], [1, 4, 6, 11, 2, 3, -1], [1, 9, 1, 11, -1, -1, 105], [2, 4, 6, 10, 4, 5, -1], [2, 4, 2, 5, -1, -1, 104], [6, 9, 6, 10, -1, -1, 100], [6, 0, 11, 8, 7, 8, -1], [6, 8, 8, 8, -1, -1, 102], [7, 0, 11, 4, 9, 10, -1], [7, 3, 9, 4, -1, -1, 101], [9, 0, 11, 1, -1, -1, 103]], [9, 9, 10, 9]], [[], 3]], [[[[0, 2, 13, 14, 1, 10, -1], [0, 4, 4, 14, 2, 5, -1], [0, 5, 1, 14, 3, 4, -1], [0, 12, 0, 14, -1, -1, 100], [0, 5, 1, 6, -1, -1, 105], [1, 4, 4, 12, 6, 7, -1], [1, 8, 1, 8, -1, -1, 102], [1, 4, 4, 12, 8, 9, -1], [1, 9, 2, 12, -1, -1, 106], [4, 4, 4, 7, -1, -1, 101], [6, 2, 13, 12, 11, 14, -1], [6, 9, 8, 12, 12, 13, -1], [6, 9, 7, 12, -1, -1, 103], [7, 9, 8, 9, -1, -1, 107], [6, 2, 13, 5, 15, 16, -1], [6, 3, 9, 3, -1, -1, 109], [11, 2, 13, 5, 17, 18, -1], [11, 2, 12, 5, -1, -1, 108], [11, 2, 13, 2, -1, -1, 104]], [8, 4, 10, 6]], [[], 7]], [[[[0, 2, 8, 11, 1, 6, -1], [0, 2, 4, 10, 2, 3, -1], [0, 7, 0, 10, -1, -1, 103], [0, 2, 4, 8, 4, 5, -1], [0, 2, 1, 2, -1, -1, 100], [4, 8, 4, 8, -1, -1, 102], [5, 4, 8, 11, 7, 8, -1], [6, 6, 6, 9, -1, -1, 101], [5, 4, 8, 11, 9, 10, -1], [5, 8, 8, 11, -1, -1, 105], [7, 4, 8, 7, -1, -1, 104]], [7, 1, 9, 2]], [[], 3]]]]\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":"15b2e50198be0c16d0882b925c51ba165c381892c491101f69ff0a171b3638df","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nimport math\nN = 1\nobservations = []\ndef solve(nodes, q):\n    if not nodes:\n        return [[], 0]\n    stack = [0]\n    hits = []\n    tests = 0\n    while stack:\n        i = stack.pop()\n        nd = nodes[i]\n        if nd[4] < 0:\n            hits.append(nd[6])\n            continue\n        tests += 1\n        if not (nd[0] <= q[2] and q[0] <= nd[2] and nd[1] <= q[3] and q[1] <= nd[3]):\n            continue\n        if nd[4] < 0:\n            hits.append(nd[6])\n        else:\n            stack.append(nd[4])\n            stack.append(nd[5])\n    return [sorted(hits), tests]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\nfixtures = [[[[[[0, 2, 12, 12, 1, 4, -1], [0, 2, 7, 4, 2, 3, -1], [0, 4, 2, 4, -1, -1, 100], [5, 2, 7, 2, -1, -1, 103], [8, 4, 12, 12, 5, 6, -1], [8, 4, 9, 6, -1, -1, 104], [10, 6, 12, 12, 7, 8, -1], [11, 10, 11, 12, -1, -1, 101], [10, 6, 12, 8, -1, -1, 102]], [6, 5, 7, 7]], [[], 3]], [[[[2, 1, 11, 12, 1, 6, -1], [2, 1, 6, 5, 2, 3, -1], [2, 1, 5, 3, -1, -1, 104], [5, 2, 6, 5, 4, 5, -1], [5, 2, 5, 5, -1, -1, 103], [6, 3, 6, 3, -1, -1, 105], [6, 1, 11, 12, 7, 10, -1], [6, 1, 8, 12, 8, 9, -1], [6, 11, 7, 12, -1, -1, 102], [6, 1, 8, 2, -1, -1, 106], [9, 6, 11, 8, 11, 12, -1], [9, 6, 9, 7, -1, -1, 101], [10, 6, 11, 8, -1, -1, 100]], [7, 6, 10, 9]], [[100, 101], 9]], [[[[0, 4, 13, 14, 1, 6, -1], [0, 4, 5, 14, 2, 3, -1], [0, 4, 1, 4, -1, -1, 104], [1, 6, 5, 14, 4, 5, -1], [1, 6, 3, 7, -1, -1, 102], [2, 12, 5, 14, -1, -1, 105], [6, 4, 13, 13, 7, 10, -1], [6, 11, 8, 13, 8, 9, -1], [6, 11, 8, 13, -1, -1, 101], [7, 11, 8, 11, -1, -1, 100], [7, 4, 13, 7, 11, 12, -1], [7, 4, 8, 4, -1, -1, 106], [12, 5, 13, 7, -1, -1, 103]], [0, 2, 0, 4]], [[104], 5]], [[[[0, 5, 8, 13, 1, 4, -1], [0, 5, 1, 13, 2, 3, -1], [0, 5, 0, 6, -1, -1, 101], [1, 12, 1, 13, -1, -1, 104], [5, 8, 8, 13, 5, 6, -1], [5, 8, 7, 10, -1, -1, 102], [6, 12, 8, 13, 7, 8, -1], [6, 12, 7, 12, -1, -1, 103], [6, 12, 8, 13, -1, -1, 100]], [12, 3, 13, 6]], [[], 1]], [[[[1, 1, 13, 15, 1, 6, -1], [1, 1, 8, 11, 2, 3, -1], [1, 9, 4, 11, -1, -1, 100], [2, 1, 8, 5, 4, 5, -1], [2, 3, 4, 5, -1, -1, 104], [6, 1, 8, 3, -1, -1, 103], [6, 4, 13, 15, 7, 8, -1], [6, 4, 9, 6, -1, -1, 105], [10, 10, 13, 15, 9, 10, -1], [10, 12, 12, 15, -1, -1, 101], [10, 10, 13, 12, -1, -1, 102]], [1, 8, 5, 11]], [[100], 5]], [[[[0, 1, 13, 15, 1, 6, -1], [0, 6, 5, 15, 2, 3, -1], [0, 12, 0, 15, -1, -1, 100], [2, 6, 5, 12, 4, 5, -1], [2, 10, 5, 12, -1, -1, 103], [3, 6, 5, 8, -1, -1, 101], [8, 1, 13, 7, 7, 8, -1], [8, 1, 9, 4, -1, -1, 104], [9, 4, 13, 7, 9, 10, -1], [9, 5, 11, 7, -1, -1, 105], [11, 4, 13, 5, -1, -1, 102]], [3, 11, 6, 12]], [[103], 7]], [[[[3, 5, 10, 10, 1, 2, -1], [3, 5, 4, 7, -1, -1, 100], [4, 6, 10, 10, 3, 4, -1], [4, 10, 6, 10, -1, -1, 102], [8, 6, 10, 8, -1, -1, 101]], [3, 3, 6, 4]], [[], 1]], [[[[0, 1, 12, 12, 1, 2, -1], [0, 9, 3, 10, -1, -1, 102], [10, 1, 12, 12, 3, 4, -1], [10, 11, 10, 12, -1, -1, 101], [11, 1, 12, 4, -1, -1, 100]], [4, 10, 8, 10]], [[], 3]]], [[[[[4, 0, 10, 13, 1, 6, -1], [4, 5, 7, 12, 2, 3, -1], [4, 8, 4, 8, -1, -1, 103], [5, 5, 7, 12, 4, 5, -1], [5, 11, 5, 12, -1, -1, 105], [6, 5, 7, 8, -1, -1, 102], [7, 0, 10, 13, 7, 8, -1], [7, 0, 7, 2, -1, -1, 101], [8, 2, 10, 13, 9, 10, -1], [8, 2, 10, 2, -1, -1, 100], [9, 12, 10, 13, -1, -1, 104]], [3, 9, 5, 13]], [[105], 7]], [[[[9, 4, 14, 10, 1, 4, -1], [9, 8, 12, 10, 2, 3, -1], [9, 9, 12, 10, -1, -1, 101], [10, 8, 11, 9, -1, -1, 102], [9, 4, 14, 10, 5, 6, -1], [9, 10, 12, 10, -1, -1, 103], [12, 4, 14, 4, -1, -1, 100]], [7, 5, 7, 8]], [[], 1]], [[[[2, 3, 15, 14, 1, 8, -1], [2, 3, 11, 12, 2, 5, -1], [2, 5, 10, 12, 3, 4, -1], [2, 5, 3, 7, -1, -1, 100], [8, 12, 10, 12, -1, -1, 105], [8, 3, 11, 6, 6, 7, -1], [8, 3, 11, 3, -1, -1, 101], [11, 4, 11, 6, -1, -1, 102], [12, 4, 15, 14, 9, 12, -1], [12, 4, 13, 14, 10, 11, -1], [12, 11, 13, 14, -1, -1, 103], [12, 4, 13, 6, -1, -1, 104], [12, 5, 15, 10, 13, 14, -1], [12, 5, 13, 7, -1, -1, 107], [12, 7, 15, 10, -1, -1, 106]], [3, 2, 3, 2]], [[], 1]], [[[[0, 0, 12, 11, 1, 4, -1], [0, 6, 3, 11, 2, 3, -1], [1, 10, 1, 11, -1, -1, 101], [0, 6, 3, 8, -1, -1, 104], [5, 0, 12, 4, 5, 6, -1], [5, 1, 5, 3, -1, -1, 103], [8, 0, 12, 4, 7, 8, -1], [8, 0, 9, 0, -1, -1, 102], [11, 4, 12, 4, -1, -1, 100]], [11, 9, 14, 11]], [[], 3]], [[[[1, 3, 12, 12, 1, 6, -1], [1, 4, 6, 6, 2, 3, -1], [1, 5, 1, 6, -1, -1, 103], [5, 4, 6, 6, 4, 5, -1], [5, 4, 6, 5, -1, -1, 100], [6, 5, 6, 6, -1, -1, 104], [7, 3, 12, 12, 7, 8, -1], [7, 3, 9, 6, -1, -1, 105], [8, 3, 12, 12, 9, 10, -1], [8, 10, 10, 12, -1, -1, 101], [11, 3, 12, 6, -1, -1, 102]], [9, 6, 13, 6]], [[102, 105], 7]], [[[[1, 0, 12, 14, 1, 4, -1], [1, 2, 3, 5, 2, 3, -1], [2, 2, 2, 2, -1, -1, 101], [1, 3, 3, 5, -1, -1, 102], [2, 0, 12, 14, 5, 6, -1], [2, 6, 4, 8, -1, -1, 104], [3, 0, 12, 14, 7, 8, -1], [3, 12, 4, 14, -1, -1, 100], [11, 0, 12, 0, -1, -1, 103]], [11, 10, 14, 13]], [[], 7]], [[[[1, 0, 12, 11, 1, 6, -1], [1, 0, 4, 11, 2, 3, -1], [1, 0, 2, 0, -1, -1, 100], [2, 7, 4, 11, 4, 5, -1], [2, 7, 2, 7, -1, -1, 105], [3, 11, 4, 11, -1, -1, 104], [5, 4, 12, 8, 7, 8, -1], [5, 6, 5, 8, -1, -1, 102], [6, 4, 12, 6, 9, 10, -1], [6, 4, 8, 6, -1, -1, 101], [10, 4, 12, 4, -1, -1, 103]], [6, 7, 7, 7]], [[], 5]], [[[[0, 5, 14, 14, 1, 6, -1], [0, 5, 5, 14, 2, 3, -1], [0, 5, 0, 8, -1, -1, 105], [2, 8, 5, 14, 4, 5, -1], [2, 12, 3, 14, -1, -1, 103], [4, 8, 5, 9, -1, -1, 102], [6, 11, 14, 12, 7, 8, -1], [6, 11, 9, 11, -1, -1, 101], [10, 11, 14, 12, 9, 10, -1], [10, 11, 13, 11, -1, -1, 100], [11, 12, 14, 12, -1, -1, 104]], [2, 2, 5, 6]], [[], 5]]], [[[[[4, 2, 6, 13, 1, 2, -1], [4, 11, 6, 13, -1, -1, 100], [4, 2, 6, 8, 3, 4, -1], [4, 2, 6, 4, -1, -1, 102], [6, 6, 6, 8, -1, -1, 101]], [11, 12, 11, 13]], [[], 1]], [[[[0, 0, 14, 11, 1, 8, -1], [0, 4, 2, 11, 2, 5, -1], [0, 6, 2, 9, 3, 4, -1], [0, 6, 1, 9, -1, -1, 106], [0, 9, 2, 9, -1, -1, 104], [1, 4, 2, 11, 6, 7, -1], [1, 8, 2, 11, -1, -1, 101], [1, 4, 2, 6, -1, -1, 107], [2, 0, 14, 11, 9, 12, -1], [2, 0, 6, 11, 10, 11, -1], [2, 0, 4, 1, -1, -1, 105], [6, 10, 6, 11, -1, -1, 100], [8, 1, 14, 10, 13, 14, -1], [8, 2, 9, 4, -1, -1, 103], [9, 1, 14, 10, 15, 16, -1], [9, 9, 12, 10, -1, -1, 108], [11, 1, 14, 1, -1, -1, 102]], [4, 6, 5, 7]], [[], 7]], [[[[7, 6, 14, 12, 1, 4, -1], [7, 6, 9, 8, 2, 3, -1], [7, 6, 8, 8, -1, -1, 102], [7, 7, 9, 7, -1, -1, 103], [10, 7, 14, 12, 5, 6, -1], [10, 10, 13, 12, -1, -1, 101], [11, 7, 14, 7, -1, -1, 100]], [11, 6, 12, 10]], [[100, 101], 5]], [[[[0, 0, 11, 14, 1, 8, -1], [0, 1, 8, 10, 2, 5, -1], [0, 4, 3, 9, 3, 4, -1], [0, 4, 1, 4, -1, -1, 101], [3, 9, 3, 9, -1, -1, 106], [3, 1, 8, 10, 6, 7, -1], [3, 10, 6, 10, -1, -1, 104], [7, 1, 8, 4, -1, -1, 103], [8, 0, 11, 14, 9, 12, -1], [8, 0, 11, 14, 10, 11, -1], [8, 11, 10, 14, -1, -1, 107], [8, 0, 11, 3, -1, -1, 100], [9, 8, 11, 14, 13, 14, -1], [9, 8, 10, 8, -1, -1, 105], [11, 11, 11, 14, -1, -1, 102]], [12, 2, 14, 4]], [[], 1]], [[[[2, 0, 14, 14, 1, 8, -1], [2, 4, 5, 14, 2, 5, -1], [2, 5, 4, 12, 3, 4, -1], [2, 11, 2, 12, -1, -1, 106], [4, 5, 4, 5, -1, -1, 102], [4, 4, 5, 14, 6, 7, -1], [4, 4, 5, 7, -1, -1, 107], [5, 12, 5, 14, -1, -1, 105], [7, 0, 14, 8, 9, 12, -1], [7, 0, 10, 3, 10, 11, -1], [7, 0, 7, 3, -1, -1, 104], [8, 1, 10, 2, -1, -1, 101], [8, 0, 14, 8, 13, 14, -1], [8, 5, 11, 8, -1, -1, 100], [12, 0, 14, 3, -1, -1, 103]], [6, 0, 8, 1]], [[101, 104], 9]], [[[[10, 2, 11, 5, -1, -1, 100]], [0, 11, 3, 14]], [[], 1]], [[[[0, 0, 15, 14, 1, 8, -1], [0, 7, 7, 14, 2, 5, -1], [0, 7, 2, 13, 3, 4, -1], [0, 11, 2, 13, -1, -1, 106], [1, 7, 1, 10, -1, -1, 107], [6, 10, 7, 14, 6, 7, -1], [6, 10, 6, 11, -1, -1, 105], [6, 11, 7, 14, -1, -1, 104], [8, 0, 15, 11, 9, 12, -1], [8, 6, 13, 11, 10, 11, -1], [8, 9, 10, 11, -1, -1, 103], [11, 6, 13, 9, -1, -1, 100], [11, 0, 15, 9, 13, 14, -1], [11, 0, 13, 0, -1, -1, 102], [12, 9, 15, 9, -1, -1, 101]], [10, 4, 11, 7]], [[100], 9]], [[[[2, 0, 14, 13, 1, 8, -1], [2, 1, 7, 13, 2, 5, -1], [2, 1, 4, 7, 3, 4, -1], [2, 1, 2, 3, -1, -1, 104], [2, 5, 4, 7, -1, -1, 101], [4, 4, 7, 13, 6, 7, -1], [4, 11, 5, 13, -1, -1, 103], [7, 4, 7, 4, -1, -1, 102], [8, 0, 14, 10, 9, 12, -1], [8, 4, 9, 4, 10, 11, -1], [8, 4, 8, 4, -1, -1, 100], [8, 4, 9, 4, -1, -1, 105], [10, 0, 14, 10, 13, 14, -1], [10, 8, 12, 10, -1, -1, 107], [11, 0, 14, 5, 15, 16, -1], [11, 0, 12, 2, -1, -1, 106], [12, 4, 14, 5, -1, -1, 108]], [12, 12, 14, 16]], [[], 3]]], [[[[[0, 1, 14, 13, 1, 10, -1], [0, 1, 3, 13, 2, 5, -1], [0, 2, 2, 13, 3, 4, -1], [0, 11, 1, 13, -1, -1, 104], [0, 2, 2, 2, -1, -1, 106], [0, 1, 3, 12, 6, 7, -1], [0, 11, 3, 12, -1, -1, 102], [1, 1, 3, 7, 8, 9, -1], [1, 1, 3, 2, -1, -1, 107], [3, 4, 3, 7, -1, -1, 109], [4, 3, 14, 12, 11, 14, -1], [4, 7, 7, 10, 12, 13, -1], [4, 8, 5, 10, -1, -1, 101], [4, 7, 7, 9, -1, -1, 105], [8, 3, 14, 12, 15, 16, -1], [8, 10, 11, 12, -1, -1, 108], [11, 3, 14, 8, 17, 18, -1], [11, 7, 13, 8, -1, -1, 103], [11, 3, 14, 4, -1, -1, 100]], [8, 3, 8, 7]], [[], 7]], [[[[5, 0, 6, 10, 1, 2, -1], [5, 0, 5, 0, -1, -1, 101], [6, 7, 6, 10, -1, -1, 100]], [9, 9, 13, 13]], [[], 1]], [[[[5, 4, 7, 4, -1, -1, 100]], [10, 7, 10, 11]], [[], 1]], [[[[1, 0, 15, 13, 1, 8, -1], [1, 2, 4, 8, 2, 5, -1], [1, 5, 3, 8, 3, 4, -1], [1, 5, 3, 7, -1, -1, 101], [1, 6, 3, 8, -1, -1, 106], [1, 2, 4, 4, 6, 7, -1], [1, 2, 4, 2, -1, -1, 103], [4, 3, 4, 4, -1, -1, 104], [3, 0, 15, 13, 9, 12, -1], [3, 0, 6, 3, 10, 11, -1], [3, 1, 6, 2, -1, -1, 108], [5, 0, 5, 3, -1, -1, 105], [9, 9, 15, 13, 13, 14, -1], [9, 11, 10, 13, -1, -1, 102], [12, 9, 15, 11, 15, 16, -1], [12, 9, 13, 10, -1, -1, 100], [12, 10, 15, 11, -1, -1, 107]], [6, 10, 6, 13]], [[], 5]], [[[[2, 1, 7, 8, 1, 2, -1], [2, 1, 5, 2, -1, -1, 101], [4, 5, 7, 8, 3, 4, -1], [4, 6, 7, 8, -1, -1, 102], [5, 5, 7, 8, -1, -1, 100]], [5, 9, 6, 12]], [[], 1]], [[[[8, 5, 9, 12, 1, 2, -1], [8, 10, 9, 12, -1, -1, 100], [8, 5, 9, 5, -1, -1, 101]], [5, 7, 5, 9]], [[], 1]], [[[[1, 1, 12, 13, 1, 6, -1], [1, 1, 7, 13, 2, 3, -1], [1, 11, 2, 13, -1, -1, 102], [4, 1, 7, 13, 4, 5, -1], [5, 1, 5, 3, -1, -1, 104], [4, 11, 7, 13, -1, -1, 103], [5, 1, 12, 6, 7, 8, -1], [5, 1, 7, 2, -1, -1, 101], [10, 2, 12, 6, 9, 10, -1], [10, 6, 12, 6, -1, -1, 100], [12, 2, 12, 4, -1, -1, 105]], [6, 6, 8, 9]], [[], 9]], [[[[0, 0, 14, 14, 1, 6, -1], [0, 4, 6, 14, 2, 3, -1], [0, 4, 0, 5, -1, -1, 102], [1, 7, 6, 14, 4, 5, -1], [1, 7, 1, 8, -1, -1, 103], [6, 11, 6, 14, -1, -1, 104], [8, 0, 14, 14, 7, 10, -1], [8, 0, 11, 7, 8, 9, -1], [8, 5, 11, 7, -1, -1, 101], [9, 0, 11, 3, -1, -1, 100], [11, 6, 14, 14, 11, 12, -1], [11, 6, 14, 8, -1, -1, 106], [12, 12, 14, 14, -1, -1, 105]], [12, 9, 15, 9]], [[], 7]]], [[[[[8, 0, 13, 15, 1, 4, -1], [8, 4, 12, 15, 2, 3, -1], [8, 12, 9, 15, -1, -1, 100], [9, 4, 12, 4, -1, -1, 101], [10, 0, 13, 11, 5, 6, -1], [10, 8, 12, 11, -1, -1, 102], [11, 0, 13, 3, -1, -1, 103]], [2, 0, 5, 1]], [[], 1]], [[[[3, 3, 12, 13, 1, 6, -1], [3, 8, 8, 13, 2, 3, -1], [3, 10, 6, 13, -1, -1, 104], [5, 8, 8, 11, 4, 5, -1], [5, 9, 5, 9, -1, -1, 101], [5, 8, 8, 11, -1, -1, 100], [6, 3, 12, 11, 7, 8, -1], [6, 8, 8, 11, -1, -1, 103], [9, 3, 12, 11, 9, 10, -1], [9, 8, 12, 11, -1, -1, 105], [11, 3, 11, 5, -1, -1, 102]], [11, 11, 14, 12]], [[105], 7]], [[[[0, 0, 8, 14, 1, 4, -1], [0, 0, 2, 3, 2, 3, -1], [0, 0, 2, 2, -1, -1, 101], [0, 0, 2, 3, -1, -1, 104], [0, 9, 8, 14, 5, 6, -1], [0, 9, 3, 12, -1, -1, 102], [6, 12, 8, 14, 7, 8, -1], [6, 12, 6, 14, -1, -1, 103], [6, 12, 8, 14, -1, -1, 100]], [5, 9, 9, 11]], [[], 5]], [[[[0, 2, 13, 12, 1, 4, -1], [0, 5, 5, 8, 2, 3, -1], [0, 5, 1, 7, -1, -1, 103], [2, 8, 5, 8, -1, -1, 104], [8, 2, 13, 12, 5, 6, -1], [8, 11, 11, 12, -1, -1, 100], [11, 2, 13, 5, 7, 8, -1], [11, 2, 13, 2, -1, -1, 101], [12, 4, 12, 5, -1, -1, 102]], [8, 4, 10, 7]], [[], 5]], [[[[0, 0, 15, 15, 1, 10, -1], [0, 0, 11, 14, 2, 5, -1], [0, 5, 1, 14, 3, 4, -1], [0, 5, 0, 8, -1, -1, 110], [1, 12, 1, 14, -1, -1, 105], [8, 0, 11, 10, 6, 7, -1], [8, 1, 10, 2, -1, -1, 102], [8, 0, 11, 10, 8, 9, -1], [8, 0, 10, 1, -1, -1, 108], [8, 8, 11, 10, -1, -1, 101], [10, 2, 15, 15, 11, 16, -1], [10, 6, 12, 15, 12, 13, -1], [10, 6, 12, 7, -1, -1, 104], [10, 11, 12, 15, 14, 15, -1], [10, 11, 12, 14, -1, -1, 106], [11, 12, 12, 15, -1, -1, 100], [11, 2, 15, 11, 17, 18, -1], [11, 11, 13, 11, -1, -1, 109], [11, 2, 15, 7, 19, 20, -1], [11, 7, 14, 7, -1, -1, 103], [12, 2, 15, 5, -1, -1, 107]], [10, 9, 10, 12]], [[101, 106], 15]], [[[[1, 0, 11, 11, 1, 6, -1], [1, 4, 6, 11, 2, 3, -1], [1, 9, 1, 11, -1, -1, 105], [2, 4, 6, 10, 4, 5, -1], [2, 4, 2, 5, -1, -1, 104], [6, 9, 6, 10, -1, -1, 100], [6, 0, 11, 8, 7, 8, -1], [6, 8, 8, 8, -1, -1, 102], [7, 0, 11, 4, 9, 10, -1], [7, 3, 9, 4, -1, -1, 101], [9, 0, 11, 1, -1, -1, 103]], [9, 9, 10, 9]], [[], 3]], [[[[0, 2, 13, 14, 1, 10, -1], [0, 4, 4, 14, 2, 5, -1], [0, 5, 1, 14, 3, 4, -1], [0, 12, 0, 14, -1, -1, 100], [0, 5, 1, 6, -1, -1, 105], [1, 4, 4, 12, 6, 7, -1], [1, 8, 1, 8, -1, -1, 102], [1, 4, 4, 12, 8, 9, -1], [1, 9, 2, 12, -1, -1, 106], [4, 4, 4, 7, -1, -1, 101], [6, 2, 13, 12, 11, 14, -1], [6, 9, 8, 12, 12, 13, -1], [6, 9, 7, 12, -1, -1, 103], [7, 9, 8, 9, -1, -1, 107], [6, 2, 13, 5, 15, 16, -1], [6, 3, 9, 3, -1, -1, 109], [11, 2, 13, 5, 17, 18, -1], [11, 2, 12, 5, -1, -1, 108], [11, 2, 13, 2, -1, -1, 104]], [8, 4, 10, 6]], [[], 7]], [[[[0, 2, 8, 11, 1, 6, -1], [0, 2, 4, 10, 2, 3, -1], [0, 7, 0, 10, -1, -1, 103], [0, 2, 4, 8, 4, 5, -1], [0, 2, 1, 2, -1, -1, 100], [4, 8, 4, 8, -1, -1, 102], [5, 4, 8, 11, 7, 8, -1], [6, 6, 6, 9, -1, -1, 101], [5, 4, 8, 11, 9, 10, -1], [5, 8, 8, 11, -1, -1, 105], [7, 4, 8, 7, -1, -1, 104]], [7, 1, 9, 2]], [[], 3]]]]\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":"abbfb42562ce2beecb91d4de7996cbe5702549d9201ea89e43e7e51a1b09ceee","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nimport math\nN = 1\nobservations = []\ndef solve(nodes, q):\n    if not nodes:\n        return [[], 0]\n    stack = [0]\n    hits = []\n    tests = 0\n    while stack:\n        i = stack.pop()\n        nd = nodes[i]\n        tests += 1\n        if not (nd[0] <= q[2] and q[0] <= nd[2] and nd[1] <= q[3] and q[1] <= nd[3]):\n            continue\n        if nd[4] < 0:\n            hits.append(nd[6])\n        else:\n            stack.append(nd[4])\n            stack.append(nd[5])\n    return [sorted(hits), tests]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\nfixtures = [[[[[[0, 2, 12, 12, 1, 4, -1], [0, 2, 7, 4, 2, 3, -1], [0, 4, 2, 4, -1, -1, 100], [5, 2, 7, 2, -1, -1, 103], [8, 4, 12, 12, 5, 6, -1], [8, 4, 9, 6, -1, -1, 104], [10, 6, 12, 12, 7, 8, -1], [11, 10, 11, 12, -1, -1, 101], [10, 6, 12, 8, -1, -1, 102]], [6, 5, 7, 7]], [[], 3]], [[[[2, 1, 11, 12, 1, 6, -1], [2, 1, 6, 5, 2, 3, -1], [2, 1, 5, 3, -1, -1, 104], [5, 2, 6, 5, 4, 5, -1], [5, 2, 5, 5, -1, -1, 103], [6, 3, 6, 3, -1, -1, 105], [6, 1, 11, 12, 7, 10, -1], [6, 1, 8, 12, 8, 9, -1], [6, 11, 7, 12, -1, -1, 102], [6, 1, 8, 2, -1, -1, 106], [9, 6, 11, 8, 11, 12, -1], [9, 6, 9, 7, -1, -1, 101], [10, 6, 11, 8, -1, -1, 100]], [7, 6, 10, 9]], [[100, 101], 9]], [[[[0, 4, 13, 14, 1, 6, -1], [0, 4, 5, 14, 2, 3, -1], [0, 4, 1, 4, -1, -1, 104], [1, 6, 5, 14, 4, 5, -1], [1, 6, 3, 7, -1, -1, 102], [2, 12, 5, 14, -1, -1, 105], [6, 4, 13, 13, 7, 10, -1], [6, 11, 8, 13, 8, 9, -1], [6, 11, 8, 13, -1, -1, 101], [7, 11, 8, 11, -1, -1, 100], [7, 4, 13, 7, 11, 12, -1], [7, 4, 8, 4, -1, -1, 106], [12, 5, 13, 7, -1, -1, 103]], [0, 2, 0, 4]], [[104], 5]], [[[[0, 5, 8, 13, 1, 4, -1], [0, 5, 1, 13, 2, 3, -1], [0, 5, 0, 6, -1, -1, 101], [1, 12, 1, 13, -1, -1, 104], [5, 8, 8, 13, 5, 6, -1], [5, 8, 7, 10, -1, -1, 102], [6, 12, 8, 13, 7, 8, -1], [6, 12, 7, 12, -1, -1, 103], [6, 12, 8, 13, -1, -1, 100]], [12, 3, 13, 6]], [[], 1]], [[[[1, 1, 13, 15, 1, 6, -1], [1, 1, 8, 11, 2, 3, -1], [1, 9, 4, 11, -1, -1, 100], [2, 1, 8, 5, 4, 5, -1], [2, 3, 4, 5, -1, -1, 104], [6, 1, 8, 3, -1, -1, 103], [6, 4, 13, 15, 7, 8, -1], [6, 4, 9, 6, -1, -1, 105], [10, 10, 13, 15, 9, 10, -1], [10, 12, 12, 15, -1, -1, 101], [10, 10, 13, 12, -1, -1, 102]], [1, 8, 5, 11]], [[100], 5]], [[[[0, 1, 13, 15, 1, 6, -1], [0, 6, 5, 15, 2, 3, -1], [0, 12, 0, 15, -1, -1, 100], [2, 6, 5, 12, 4, 5, -1], [2, 10, 5, 12, -1, -1, 103], [3, 6, 5, 8, -1, -1, 101], [8, 1, 13, 7, 7, 8, -1], [8, 1, 9, 4, -1, -1, 104], [9, 4, 13, 7, 9, 10, -1], [9, 5, 11, 7, -1, -1, 105], [11, 4, 13, 5, -1, -1, 102]], [3, 11, 6, 12]], [[103], 7]], [[[[3, 5, 10, 10, 1, 2, -1], [3, 5, 4, 7, -1, -1, 100], [4, 6, 10, 10, 3, 4, -1], [4, 10, 6, 10, -1, -1, 102], [8, 6, 10, 8, -1, -1, 101]], [3, 3, 6, 4]], [[], 1]], [[[[0, 1, 12, 12, 1, 2, -1], [0, 9, 3, 10, -1, -1, 102], [10, 1, 12, 12, 3, 4, -1], [10, 11, 10, 12, -1, -1, 101], [11, 1, 12, 4, -1, -1, 100]], [4, 10, 8, 10]], [[], 3]]], [[[[[4, 0, 10, 13, 1, 6, -1], [4, 5, 7, 12, 2, 3, -1], [4, 8, 4, 8, -1, -1, 103], [5, 5, 7, 12, 4, 5, -1], [5, 11, 5, 12, -1, -1, 105], [6, 5, 7, 8, -1, -1, 102], [7, 0, 10, 13, 7, 8, -1], [7, 0, 7, 2, -1, -1, 101], [8, 2, 10, 13, 9, 10, -1], [8, 2, 10, 2, -1, -1, 100], [9, 12, 10, 13, -1, -1, 104]], [3, 9, 5, 13]], [[105], 7]], [[[[9, 4, 14, 10, 1, 4, -1], [9, 8, 12, 10, 2, 3, -1], [9, 9, 12, 10, -1, -1, 101], [10, 8, 11, 9, -1, -1, 102], [9, 4, 14, 10, 5, 6, -1], [9, 10, 12, 10, -1, -1, 103], [12, 4, 14, 4, -1, -1, 100]], [7, 5, 7, 8]], [[], 1]], [[[[2, 3, 15, 14, 1, 8, -1], [2, 3, 11, 12, 2, 5, -1], [2, 5, 10, 12, 3, 4, -1], [2, 5, 3, 7, -1, -1, 100], [8, 12, 10, 12, -1, -1, 105], [8, 3, 11, 6, 6, 7, -1], [8, 3, 11, 3, -1, -1, 101], [11, 4, 11, 6, -1, -1, 102], [12, 4, 15, 14, 9, 12, -1], [12, 4, 13, 14, 10, 11, -1], [12, 11, 13, 14, -1, -1, 103], [12, 4, 13, 6, -1, -1, 104], [12, 5, 15, 10, 13, 14, -1], [12, 5, 13, 7, -1, -1, 107], [12, 7, 15, 10, -1, -1, 106]], [3, 2, 3, 2]], [[], 1]], [[[[0, 0, 12, 11, 1, 4, -1], [0, 6, 3, 11, 2, 3, -1], [1, 10, 1, 11, -1, -1, 101], [0, 6, 3, 8, -1, -1, 104], [5, 0, 12, 4, 5, 6, -1], [5, 1, 5, 3, -1, -1, 103], [8, 0, 12, 4, 7, 8, -1], [8, 0, 9, 0, -1, -1, 102], [11, 4, 12, 4, -1, -1, 100]], [11, 9, 14, 11]], [[], 3]], [[[[1, 3, 12, 12, 1, 6, -1], [1, 4, 6, 6, 2, 3, -1], [1, 5, 1, 6, -1, -1, 103], [5, 4, 6, 6, 4, 5, -1], [5, 4, 6, 5, -1, -1, 100], [6, 5, 6, 6, -1, -1, 104], [7, 3, 12, 12, 7, 8, -1], [7, 3, 9, 6, -1, -1, 105], [8, 3, 12, 12, 9, 10, -1], [8, 10, 10, 12, -1, -1, 101], [11, 3, 12, 6, -1, -1, 102]], [9, 6, 13, 6]], [[102, 105], 7]], [[[[1, 0, 12, 14, 1, 4, -1], [1, 2, 3, 5, 2, 3, -1], [2, 2, 2, 2, -1, -1, 101], [1, 3, 3, 5, -1, -1, 102], [2, 0, 12, 14, 5, 6, -1], [2, 6, 4, 8, -1, -1, 104], [3, 0, 12, 14, 7, 8, -1], [3, 12, 4, 14, -1, -1, 100], [11, 0, 12, 0, -1, -1, 103]], [11, 10, 14, 13]], [[], 7]], [[[[1, 0, 12, 11, 1, 6, -1], [1, 0, 4, 11, 2, 3, -1], [1, 0, 2, 0, -1, -1, 100], [2, 7, 4, 11, 4, 5, -1], [2, 7, 2, 7, -1, -1, 105], [3, 11, 4, 11, -1, -1, 104], [5, 4, 12, 8, 7, 8, -1], [5, 6, 5, 8, -1, -1, 102], [6, 4, 12, 6, 9, 10, -1], [6, 4, 8, 6, -1, -1, 101], [10, 4, 12, 4, -1, -1, 103]], [6, 7, 7, 7]], [[], 5]], [[[[0, 5, 14, 14, 1, 6, -1], [0, 5, 5, 14, 2, 3, -1], [0, 5, 0, 8, -1, -1, 105], [2, 8, 5, 14, 4, 5, -1], [2, 12, 3, 14, -1, -1, 103], [4, 8, 5, 9, -1, -1, 102], [6, 11, 14, 12, 7, 8, -1], [6, 11, 9, 11, -1, -1, 101], [10, 11, 14, 12, 9, 10, -1], [10, 11, 13, 11, -1, -1, 100], [11, 12, 14, 12, -1, -1, 104]], [2, 2, 5, 6]], [[], 5]]], [[[[[4, 2, 6, 13, 1, 2, -1], [4, 11, 6, 13, -1, -1, 100], [4, 2, 6, 8, 3, 4, -1], [4, 2, 6, 4, -1, -1, 102], [6, 6, 6, 8, -1, -1, 101]], [11, 12, 11, 13]], [[], 1]], [[[[0, 0, 14, 11, 1, 8, -1], [0, 4, 2, 11, 2, 5, -1], [0, 6, 2, 9, 3, 4, -1], [0, 6, 1, 9, -1, -1, 106], [0, 9, 2, 9, -1, -1, 104], [1, 4, 2, 11, 6, 7, -1], [1, 8, 2, 11, -1, -1, 101], [1, 4, 2, 6, -1, -1, 107], [2, 0, 14, 11, 9, 12, -1], [2, 0, 6, 11, 10, 11, -1], [2, 0, 4, 1, -1, -1, 105], [6, 10, 6, 11, -1, -1, 100], [8, 1, 14, 10, 13, 14, -1], [8, 2, 9, 4, -1, -1, 103], [9, 1, 14, 10, 15, 16, -1], [9, 9, 12, 10, -1, -1, 108], [11, 1, 14, 1, -1, -1, 102]], [4, 6, 5, 7]], [[], 7]], [[[[7, 6, 14, 12, 1, 4, -1], [7, 6, 9, 8, 2, 3, -1], [7, 6, 8, 8, -1, -1, 102], [7, 7, 9, 7, -1, -1, 103], [10, 7, 14, 12, 5, 6, -1], [10, 10, 13, 12, -1, -1, 101], [11, 7, 14, 7, -1, -1, 100]], [11, 6, 12, 10]], [[100, 101], 5]], [[[[0, 0, 11, 14, 1, 8, -1], [0, 1, 8, 10, 2, 5, -1], [0, 4, 3, 9, 3, 4, -1], [0, 4, 1, 4, -1, -1, 101], [3, 9, 3, 9, -1, -1, 106], [3, 1, 8, 10, 6, 7, -1], [3, 10, 6, 10, -1, -1, 104], [7, 1, 8, 4, -1, -1, 103], [8, 0, 11, 14, 9, 12, -1], [8, 0, 11, 14, 10, 11, -1], [8, 11, 10, 14, -1, -1, 107], [8, 0, 11, 3, -1, -1, 100], [9, 8, 11, 14, 13, 14, -1], [9, 8, 10, 8, -1, -1, 105], [11, 11, 11, 14, -1, -1, 102]], [12, 2, 14, 4]], [[], 1]], [[[[2, 0, 14, 14, 1, 8, -1], [2, 4, 5, 14, 2, 5, -1], [2, 5, 4, 12, 3, 4, -1], [2, 11, 2, 12, -1, -1, 106], [4, 5, 4, 5, -1, -1, 102], [4, 4, 5, 14, 6, 7, -1], [4, 4, 5, 7, -1, -1, 107], [5, 12, 5, 14, -1, -1, 105], [7, 0, 14, 8, 9, 12, -1], [7, 0, 10, 3, 10, 11, -1], [7, 0, 7, 3, -1, -1, 104], [8, 1, 10, 2, -1, -1, 101], [8, 0, 14, 8, 13, 14, -1], [8, 5, 11, 8, -1, -1, 100], [12, 0, 14, 3, -1, -1, 103]], [6, 0, 8, 1]], [[101, 104], 9]], [[[[10, 2, 11, 5, -1, -1, 100]], [0, 11, 3, 14]], [[], 1]], [[[[0, 0, 15, 14, 1, 8, -1], [0, 7, 7, 14, 2, 5, -1], [0, 7, 2, 13, 3, 4, -1], [0, 11, 2, 13, -1, -1, 106], [1, 7, 1, 10, -1, -1, 107], [6, 10, 7, 14, 6, 7, -1], [6, 10, 6, 11, -1, -1, 105], [6, 11, 7, 14, -1, -1, 104], [8, 0, 15, 11, 9, 12, -1], [8, 6, 13, 11, 10, 11, -1], [8, 9, 10, 11, -1, -1, 103], [11, 6, 13, 9, -1, -1, 100], [11, 0, 15, 9, 13, 14, -1], [11, 0, 13, 0, -1, -1, 102], [12, 9, 15, 9, -1, -1, 101]], [10, 4, 11, 7]], [[100], 9]], [[[[2, 0, 14, 13, 1, 8, -1], [2, 1, 7, 13, 2, 5, -1], [2, 1, 4, 7, 3, 4, -1], [2, 1, 2, 3, -1, -1, 104], [2, 5, 4, 7, -1, -1, 101], [4, 4, 7, 13, 6, 7, -1], [4, 11, 5, 13, -1, -1, 103], [7, 4, 7, 4, -1, -1, 102], [8, 0, 14, 10, 9, 12, -1], [8, 4, 9, 4, 10, 11, -1], [8, 4, 8, 4, -1, -1, 100], [8, 4, 9, 4, -1, -1, 105], [10, 0, 14, 10, 13, 14, -1], [10, 8, 12, 10, -1, -1, 107], [11, 0, 14, 5, 15, 16, -1], [11, 0, 12, 2, -1, -1, 106], [12, 4, 14, 5, -1, -1, 108]], [12, 12, 14, 16]], [[], 3]]], [[[[[0, 1, 14, 13, 1, 10, -1], [0, 1, 3, 13, 2, 5, -1], [0, 2, 2, 13, 3, 4, -1], [0, 11, 1, 13, -1, -1, 104], [0, 2, 2, 2, -1, -1, 106], [0, 1, 3, 12, 6, 7, -1], [0, 11, 3, 12, -1, -1, 102], [1, 1, 3, 7, 8, 9, -1], [1, 1, 3, 2, -1, -1, 107], [3, 4, 3, 7, -1, -1, 109], [4, 3, 14, 12, 11, 14, -1], [4, 7, 7, 10, 12, 13, -1], [4, 8, 5, 10, -1, -1, 101], [4, 7, 7, 9, -1, -1, 105], [8, 3, 14, 12, 15, 16, -1], [8, 10, 11, 12, -1, -1, 108], [11, 3, 14, 8, 17, 18, -1], [11, 7, 13, 8, -1, -1, 103], [11, 3, 14, 4, -1, -1, 100]], [8, 3, 8, 7]], [[], 7]], [[[[5, 0, 6, 10, 1, 2, -1], [5, 0, 5, 0, -1, -1, 101], [6, 7, 6, 10, -1, -1, 100]], [9, 9, 13, 13]], [[], 1]], [[[[5, 4, 7, 4, -1, -1, 100]], [10, 7, 10, 11]], [[], 1]], [[[[1, 0, 15, 13, 1, 8, -1], [1, 2, 4, 8, 2, 5, -1], [1, 5, 3, 8, 3, 4, -1], [1, 5, 3, 7, -1, -1, 101], [1, 6, 3, 8, -1, -1, 106], [1, 2, 4, 4, 6, 7, -1], [1, 2, 4, 2, -1, -1, 103], [4, 3, 4, 4, -1, -1, 104], [3, 0, 15, 13, 9, 12, -1], [3, 0, 6, 3, 10, 11, -1], [3, 1, 6, 2, -1, -1, 108], [5, 0, 5, 3, -1, -1, 105], [9, 9, 15, 13, 13, 14, -1], [9, 11, 10, 13, -1, -1, 102], [12, 9, 15, 11, 15, 16, -1], [12, 9, 13, 10, -1, -1, 100], [12, 10, 15, 11, -1, -1, 107]], [6, 10, 6, 13]], [[], 5]], [[[[2, 1, 7, 8, 1, 2, -1], [2, 1, 5, 2, -1, -1, 101], [4, 5, 7, 8, 3, 4, -1], [4, 6, 7, 8, -1, -1, 102], [5, 5, 7, 8, -1, -1, 100]], [5, 9, 6, 12]], [[], 1]], [[[[8, 5, 9, 12, 1, 2, -1], [8, 10, 9, 12, -1, -1, 100], [8, 5, 9, 5, -1, -1, 101]], [5, 7, 5, 9]], [[], 1]], [[[[1, 1, 12, 13, 1, 6, -1], [1, 1, 7, 13, 2, 3, -1], [1, 11, 2, 13, -1, -1, 102], [4, 1, 7, 13, 4, 5, -1], [5, 1, 5, 3, -1, -1, 104], [4, 11, 7, 13, -1, -1, 103], [5, 1, 12, 6, 7, 8, -1], [5, 1, 7, 2, -1, -1, 101], [10, 2, 12, 6, 9, 10, -1], [10, 6, 12, 6, -1, -1, 100], [12, 2, 12, 4, -1, -1, 105]], [6, 6, 8, 9]], [[], 9]], [[[[0, 0, 14, 14, 1, 6, -1], [0, 4, 6, 14, 2, 3, -1], [0, 4, 0, 5, -1, -1, 102], [1, 7, 6, 14, 4, 5, -1], [1, 7, 1, 8, -1, -1, 103], [6, 11, 6, 14, -1, -1, 104], [8, 0, 14, 14, 7, 10, -1], [8, 0, 11, 7, 8, 9, -1], [8, 5, 11, 7, -1, -1, 101], [9, 0, 11, 3, -1, -1, 100], [11, 6, 14, 14, 11, 12, -1], [11, 6, 14, 8, -1, -1, 106], [12, 12, 14, 14, -1, -1, 105]], [12, 9, 15, 9]], [[], 7]]], [[[[[8, 0, 13, 15, 1, 4, -1], [8, 4, 12, 15, 2, 3, -1], [8, 12, 9, 15, -1, -1, 100], [9, 4, 12, 4, -1, -1, 101], [10, 0, 13, 11, 5, 6, -1], [10, 8, 12, 11, -1, -1, 102], [11, 0, 13, 3, -1, -1, 103]], [2, 0, 5, 1]], [[], 1]], [[[[3, 3, 12, 13, 1, 6, -1], [3, 8, 8, 13, 2, 3, -1], [3, 10, 6, 13, -1, -1, 104], [5, 8, 8, 11, 4, 5, -1], [5, 9, 5, 9, -1, -1, 101], [5, 8, 8, 11, -1, -1, 100], [6, 3, 12, 11, 7, 8, -1], [6, 8, 8, 11, -1, -1, 103], [9, 3, 12, 11, 9, 10, -1], [9, 8, 12, 11, -1, -1, 105], [11, 3, 11, 5, -1, -1, 102]], [11, 11, 14, 12]], [[105], 7]], [[[[0, 0, 8, 14, 1, 4, -1], [0, 0, 2, 3, 2, 3, -1], [0, 0, 2, 2, -1, -1, 101], [0, 0, 2, 3, -1, -1, 104], [0, 9, 8, 14, 5, 6, -1], [0, 9, 3, 12, -1, -1, 102], [6, 12, 8, 14, 7, 8, -1], [6, 12, 6, 14, -1, -1, 103], [6, 12, 8, 14, -1, -1, 100]], [5, 9, 9, 11]], [[], 5]], [[[[0, 2, 13, 12, 1, 4, -1], [0, 5, 5, 8, 2, 3, -1], [0, 5, 1, 7, -1, -1, 103], [2, 8, 5, 8, -1, -1, 104], [8, 2, 13, 12, 5, 6, -1], [8, 11, 11, 12, -1, -1, 100], [11, 2, 13, 5, 7, 8, -1], [11, 2, 13, 2, -1, -1, 101], [12, 4, 12, 5, -1, -1, 102]], [8, 4, 10, 7]], [[], 5]], [[[[0, 0, 15, 15, 1, 10, -1], [0, 0, 11, 14, 2, 5, -1], [0, 5, 1, 14, 3, 4, -1], [0, 5, 0, 8, -1, -1, 110], [1, 12, 1, 14, -1, -1, 105], [8, 0, 11, 10, 6, 7, -1], [8, 1, 10, 2, -1, -1, 102], [8, 0, 11, 10, 8, 9, -1], [8, 0, 10, 1, -1, -1, 108], [8, 8, 11, 10, -1, -1, 101], [10, 2, 15, 15, 11, 16, -1], [10, 6, 12, 15, 12, 13, -1], [10, 6, 12, 7, -1, -1, 104], [10, 11, 12, 15, 14, 15, -1], [10, 11, 12, 14, -1, -1, 106], [11, 12, 12, 15, -1, -1, 100], [11, 2, 15, 11, 17, 18, -1], [11, 11, 13, 11, -1, -1, 109], [11, 2, 15, 7, 19, 20, -1], [11, 7, 14, 7, -1, -1, 103], [12, 2, 15, 5, -1, -1, 107]], [10, 9, 10, 12]], [[101, 106], 15]], [[[[1, 0, 11, 11, 1, 6, -1], [1, 4, 6, 11, 2, 3, -1], [1, 9, 1, 11, -1, -1, 105], [2, 4, 6, 10, 4, 5, -1], [2, 4, 2, 5, -1, -1, 104], [6, 9, 6, 10, -1, -1, 100], [6, 0, 11, 8, 7, 8, -1], [6, 8, 8, 8, -1, -1, 102], [7, 0, 11, 4, 9, 10, -1], [7, 3, 9, 4, -1, -1, 101], [9, 0, 11, 1, -1, -1, 103]], [9, 9, 10, 9]], [[], 3]], [[[[0, 2, 13, 14, 1, 10, -1], [0, 4, 4, 14, 2, 5, -1], [0, 5, 1, 14, 3, 4, -1], [0, 12, 0, 14, -1, -1, 100], [0, 5, 1, 6, -1, -1, 105], [1, 4, 4, 12, 6, 7, -1], [1, 8, 1, 8, -1, -1, 102], [1, 4, 4, 12, 8, 9, -1], [1, 9, 2, 12, -1, -1, 106], [4, 4, 4, 7, -1, -1, 101], [6, 2, 13, 12, 11, 14, -1], [6, 9, 8, 12, 12, 13, -1], [6, 9, 7, 12, -1, -1, 103], [7, 9, 8, 9, -1, -1, 107], [6, 2, 13, 5, 15, 16, -1], [6, 3, 9, 3, -1, -1, 109], [11, 2, 13, 5, 17, 18, -1], [11, 2, 12, 5, -1, -1, 108], [11, 2, 13, 2, -1, -1, 104]], [8, 4, 10, 6]], [[], 7]], [[[[0, 2, 8, 11, 1, 6, -1], [0, 2, 4, 10, 2, 3, -1], [0, 7, 0, 10, -1, -1, 103], [0, 2, 4, 8, 4, 5, -1], [0, 2, 1, 2, -1, -1, 100], [4, 8, 4, 8, -1, -1, 102], [5, 4, 8, 11, 7, 8, -1], [6, 6, 6, 9, -1, -1, 101], [5, 4, 8, 11, 9, 10, -1], [5, 8, 8, 11, -1, -1, 105], [7, 4, 8, 7, -1, -1, 104]], [7, 1, 9, 2]], [[], 3]]]]\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-bvh-stack-query-leaf-overlap-test","generated_at":"2026-09-29T14:50:59.007991+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":"Test leaves like any other node before reporting them.","root_cause":"The traversal appends leaf ids before the overlap test.","sha256":"ff04a75a8b4fef56c8d99a4c3e3eb076d44594b59350954cd7d22fc5ac750db6","title":"Leaves are accepted without testing their own bounds · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verification":{"attempt":{"elapsed_ms":43.209,"exit_code":1,"observations":[{"actual":[[],3],"check":"case 0","expected":[[],3],"passed":true},{"actual":[[100,101],5],"check":"case 1","expected":[[100,101],9],"passed":false},{"actual":[[104],4],"check":"case 2","expected":[[104],5],"passed":false},{"actual":[[],1],"check":"case 3","expected":[[],1],"passed":true},{"actual":[[100],4],"check":"case 4","expected":[[100],5],"passed":false},{"actual":[[103],4],"check":"case 5","expected":[[103],7],"passed":false},{"actual":[[],1],"check":"case 6","expected":[[],1],"passed":true},{"actual":[[],2],"check":"case 7","expected":[[],3],"passed":false}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"case 0\", \"actual\": [[], 3], \"expected\": [[], 3], \"passed\": true}, {\"check\": \"case 1\", \"actual\": [[100, 101], 5], \"expected\": [[100, 101], 9], \"passed\": false}, {\"check\": \"case 2\", \"actual\": [[104], 4], \"expected\": [[104], 5], \"passed\": false}, {\"check\": \"case 3\", \"actual\": [[], 1], \"expected\": [[], 1], \"passed\": true}, {\"check\": \"case 4\", \"actual\": [[100], 4], \"expected\": [[100], 5], \"passed\": false}, {\"check\": \"case 5\", \"actual\": [[103], 4], \"expected\": [[103], 7], \"passed\": false}, {\"check\": \"case 6\", \"actual\": [[], 1], \"expected\": [[], 1], \"passed\": true}, {\"check\": \"case 7\", \"actual\": [[], 2], \"expected\": [[], 3], \"passed\": false}], \"passed\": false}\n"},"broken":{"elapsed_ms":43.0,"exit_code":1,"observations":[{"actual":[[],3],"check":"case 0","expected":[[],3],"passed":true},{"actual":[[100,101,102,106],5],"check":"case 1","expected":[[100,101],9],"passed":false},{"actual":[[104],4],"check":"case 2","expected":[[104],5],"passed":false},{"actual":[[],1],"check":"case 3","expected":[[],1],"passed":true},{"actual":[[100],4],"check":"case 4","expected":[[100],5],"passed":false},{"actual":[[100,101,103],4],"check":"case 5","expected":[[103],7],"passed":false},{"actual":[[],1],"check":"case 6","expected":[[],1],"passed":true},{"actual":[[102],2],"check":"case 7","expected":[[],3],"passed":false}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"case 0\", \"actual\": [[], 3], \"expected\": [[], 3], \"passed\": true}, {\"check\": \"case 1\", \"actual\": [[100, 101, 102, 106], 5], \"expected\": [[100, 101], 9], \"passed\": false}, {\"check\": \"case 2\", \"actual\": [[104], 4], \"expected\": [[104], 5], \"passed\": false}, {\"check\": \"case 3\", \"actual\": [[], 1], \"expected\": [[], 1], \"passed\": true}, {\"check\": \"case 4\", \"actual\": [[100], 4], \"expected\": [[100], 5], \"passed\": false}, {\"check\": \"case 5\", \"actual\": [[100, 101, 103], 4], \"expected\": [[103], 7], \"passed\": false}, {\"check\": \"case 6\", \"actual\": [[], 1], \"expected\": [[], 1], \"passed\": true}, {\"check\": \"case 7\", \"actual\": [[102], 2], \"expected\": [[], 3], \"passed\": false}], \"passed\": false}\n"},"fixed":{"elapsed_ms":42.111,"exit_code":0,"observations":[{"actual":[[],3],"check":"case 0","expected":[[],3],"passed":true},{"actual":[[100,101],9],"check":"case 1","expected":[[100,101],9],"passed":true},{"actual":[[104],5],"check":"case 2","expected":[[104],5],"passed":true},{"actual":[[],1],"check":"case 3","expected":[[],1],"passed":true},{"actual":[[100],5],"check":"case 4","expected":[[100],5],"passed":true},{"actual":[[103],7],"check":"case 5","expected":[[103],7],"passed":true},{"actual":[[],1],"check":"case 6","expected":[[],1],"passed":true},{"actual":[[],3],"check":"case 7","expected":[[],3],"passed":true}],"passed":true,"stderr":"","stdout":"{\"observations\": [{\"check\": \"case 0\", \"actual\": [[], 3], \"expected\": [[], 3], \"passed\": true}, {\"check\": \"case 1\", \"actual\": [[100, 101], 9], \"expected\": [[100, 101], 9], \"passed\": true}, {\"check\": \"case 2\", \"actual\": [[104], 5], \"expected\": [[104], 5], \"passed\": true}, {\"check\": \"case 3\", \"actual\": [[], 1], \"expected\": [[], 1], \"passed\": true}, {\"check\": \"case 4\", \"actual\": [[100], 5], \"expected\": [[100], 5], \"passed\": true}, {\"check\": \"case 5\", \"actual\": [[103], 7], \"expected\": [[103], 7], \"passed\": true}, {\"check\": \"case 6\", \"actual\": [[], 1], \"expected\": [[], 1], \"passed\": true}, {\"check\": \"case 7\", \"actual\": [[], 3], \"expected\": [[], 3], \"passed\": true}], \"passed\": true}\n"}},"verified":true,"visibility":"public"}