Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/python3

class Node:
    pass

def kdtree(points, depth=0):
    if not points:
        return
    # dimension
    k = len(points[0][1])
    axis = depth % k

    points.sort(key=lambda x:x[1][axis])
    median = len(points)//2

    node = Node()
    node.location = points[median]
    node.left = kdtree(points[:median], depth + 1)
    node.right = kdtree(points[median + 1:], depth + 1)
    return node

def find(sx, tx, sy, ty, node, depth):
    if node == None:
        return []
    result = []
    x = node.location[1][0]
    y = node.location[1][1]
    if sx <= x <= tx and sy <= y <= ty:
        result.append(node.location[0])

    if depth % 2 == 0:
        if sx <= x:
            ret = find(sx, tx, sy, ty, node.left, depth + 1)
            result.extend(ret)
        if x <= tx:
            ret = find(sx, tx, sy, ty, node.right, depth + 1)
            result.extend(ret)
    else:
        if sy <= y:
            ret = find(sx, tx, sy, ty, node.left, depth + 1)
            result.extend(ret)
        if y <= ty:
            ret = find(sx, tx, sy, ty, node.right, depth + 1)
            result.extend(ret)
    return result

# main
n = int(input())
points = [(i, tuple(map(int, input().split()))) for i in range(n)]
tree = kdtree(points)
q = int(input())
for i in range(q):
    sx, tx, sy, ty = map(int, input().split())
    result = find(sx, tx, sy, ty, tree, 0)
    result.sort()
    for i in result:
        print(i)
    print()

Fixed submission:
#!/usr/bin/python3
from sys import stdin
import math
from operator import itemgetter
from bisect import bisect_left, bisect_right
readline = stdin.readline

def main():
    n = int(readline())
    xy = [tuple(map(int, readline().split())) + (i,) for i in range(n)]
    # [..., (x_i, y_i, i), ...]
    # sort by x
    xy.sort()

    root = int(math.sqrt(len(xy)))

    low = [x for x, y, i in xy[::root]]
    high = [x for x, y, i in xy[root - 1::root]] + [float('inf')]

    xy = [sorted(xy[i:i + root], key=itemgetter(1)) for i in range(0, len(xy), root)]
    xy = [([y for x, y, i in xyi], xyi) for xyi in xy]
    for sx, tx, sy, ty in (map(int, readline().split()) for _ in range(int(readline()))):
        ret = []
        for i in range(bisect_left(high, sx), bisect_right(low, tx)):
            k, v = xy[i]
            for i in range(bisect_left(k, sy), bisect_right(k, ty)):
                if sx <= v[i][0] <=tx:
                    ret.append(v[i][2])
        if ret:
            ret.sort()
            print('\n'.join(map(str,ret)))
        print()

main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/python3
from operator import attrgetter
class Point:
    pass

class Node:
    pass

def kdtree(points, depth=0):
    if not points:
        return
    # dimension
    k = 2
    axis = depth % k
    if depth % 2 == 0:
        points.sort(key=attrgetter('x'))
    else:
        points.sort(key=attrgetter('y'))

    median = len(points)//2

    node = Node()
    node.location = points[median]
    node.left = kdtree(points[:median], depth + 1)
    node.right = kdtree(points[median + 1:], depth + 1)
    return node

def find(sx, tx, sy, ty, node, depth):
    if node == None:
        return []
    result = []
    x = node.location.x
    y = node.location.y
    if sx <= x <= tx and sy <= y <= ty:
        result.append(node.location.id)

    if depth % 2 == 0:
        if sx <= x:
            ret = find(sx, tx, sy, ty, node.left, depth + 1)
            result.extend(ret)
        if x <= tx:
            ret = find(sx, tx, sy, ty, node.right, depth + 1)
            result.extend(ret)
    else:
        if sy <= y:
            ret = find(sx, tx, sy, ty, node.left, depth + 1)
            result.extend(ret)
        if y <= ty:
            ret = find(sx, tx, sy, ty, node.right, depth + 1)
            result.extend(ret)
    return result

# main
n = int(input())
points = []
for i in range(n):
    point = Point()
    point.id = i
    point.x, point.y = map(int, input().split())
    points.append(point)
tree = kdtree(points)
q = int(input())
for i in range(q):
    sx, tx, sy, ty = map(int, input().split())
    result = find(sx, tx, sy, ty, tree, 0)
    result.sort()
    for i in result:
        print(i)
    print()

Fixed submission:
#!/usr/bin/python3
from sys import stdin
import math
from operator import itemgetter
from bisect import bisect_left, bisect_right
readline = stdin.readline

def main():
    n = int(readline())
    xy = [tuple(map(int, readline().split())) + (i,) for i in range(n)]
    # [..., (x_i, y_i, i), ...]
    # sort by x
    xy.sort()

    root = int(math.sqrt(len(xy)))

    low = [x for x, y, i in xy[::root]]
    high = [x for x, y, i in xy[root - 1::root]] + [float('inf')]

    xy = [sorted(xy[i:i + root], key=itemgetter(1)) for i in range(0, len(xy), root)]
    xy = [([y for x, y, i in xyi], xyi) for xyi in xy]
    for sx, tx, sy, ty in (map(int, readline().split()) for _ in range(int(readline()))):
        ret = []
        for i in range(bisect_left(high, sx), bisect_right(low, tx)):
            k, v = xy[i]
            for i in range(bisect_left(k, sy), bisect_right(k, ty)):
                if sx <= v[i][0] <=tx:
                    ret.append(v[i][2])
        if ret:
            ret.sort()
            print('\n'.join(map(str,ret)))
        print()

main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/python3
from operator import attrgetter
import sys
class Point:
    pass

class Node:
    pass

def kdtree(points, depth=0):
    if not points:
        return
    # dimension
    if depth % 2 == 0:
        points.sort(key=attrgetter('x'))
    else:
        points.sort(key=attrgetter('y'))

    median = len(points)//2

    node = Node()
    node.location = points[median]
    node.left = kdtree(points[:median], depth + 1)
    node.right = kdtree(points[median + 1:], depth + 1)
    return node

def find(sx, tx, sy, ty, node, depth):
    if node == None:
        return []
    result = []
    x = node.location.x
    y = node.location.y
    if sx <= x <= tx and sy <= y <= ty:
        result.append(node.location.id)

    if depth % 2 == 0:
        if sx <= x:
            result.extend(find(sx, tx, sy, ty, node.left, depth + 1))
        if x <= tx:
            result.extend(find(sx, tx, sy, ty, node.right, depth + 1))
    else:
        if sy <= y:
            result.extend(find(sx, tx, sy, ty, node.left, depth + 1))
        if y <= ty:
            result.extend(find(sx, tx, sy, ty, node.right, depth + 1))
    return result

# main
n = int(input())
points = []
for i in range(n):
    point = Point()
    point.id = i
    point.x, point.y = map(int, sys.stdin.readline().split())
    points.append(point)
tree = kdtree(points)
q = int(input())
for i in range(q):
    sx, tx, sy, ty = map(int, input().split())
    result = find(sx, tx, sy, ty, tree, 0)
    result.sort()
    for i in result:
        print(i)
    print()

Fixed submission:
#!/usr/bin/python3
from sys import stdin
import math
from operator import itemgetter
from bisect import bisect_left, bisect_right
readline = stdin.readline

def main():
    n = int(readline())
    xy = [tuple(map(int, readline().split())) + (i,) for i in range(n)]
    # [..., (x_i, y_i, i), ...]
    # sort by x
    xy.sort()

    root = int(math.sqrt(len(xy)))

    low = [x for x, y, i in xy[::root]]
    high = [x for x, y, i in xy[root - 1::root]] + [float('inf')]

    xy = [sorted(xy[i:i + root], key=itemgetter(1)) for i in range(0, len(xy), root)]
    xy = [([y for x, y, i in xyi], xyi) for xyi in xy]
    for sx, tx, sy, ty in (map(int, readline().split()) for _ in range(int(readline()))):
        ret = []
        for i in range(bisect_left(high, sx), bisect_right(low, tx)):
            k, v = xy[i]
            for i in range(bisect_left(k, sy), bisect_right(k, ty)):
                if sx <= v[i][0] <=tx:
                    ret.append(v[i][2])
        if ret:
            ret.sort()
            print('\n'.join(map(str,ret)))
        print()

main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/python3
from operator import attrgetter
import sys
class Point:
    pass

class Node:
    pass

def kdtree(points, depth=0):
    if not points:
        return
    # dimension
    if depth % 2 == 0:
        points.sort(key=attrgetter('x'))
    else:
        points.sort(key=attrgetter('y'))

    median = len(points)//2

    node = Node()
    node.location = points[median]
    node.left = kdtree(points[:median], depth + 1)
    node.right = kdtree(points[median + 1:], depth + 1)
    return node

def find(sx, tx, sy, ty, node, depth, result):
    if node == None:
        return
    if sx <= node.location.x <= tx and sy <= node.location.y <= ty:
        result.append(node.location.id)

    if depth % 2 == 0:
        if sx <= node.location.x:
            find(sx, tx, sy, ty, node.left, depth + 1, result)
        if node.location.x <= tx:
            find(sx, tx, sy, ty, node.right, depth + 1, result)
    else:
        if sy <= node.location.y:
            find(sx, tx, sy, ty, node.left, depth + 1, result)
        if node.location.y <= ty:
            find(sx, tx, sy, ty, node.right, depth + 1, result)

# main
n = int(input())
points = []
for i in range(n):
    point = Point()
    point.id = i
    point.x, point.y = map(int, sys.stdin.readline().split())
    points.append(point)
tree = kdtree(points)
q = int(input())
for i in range(q):
    sx, tx, sy, ty = map(int, sys.stdin.readline().split())
    result = []
    find(sx, tx, sy, ty, tree, 0, result)
    result.sort()
    for i in result:
        print(i)
    print()

Fixed submission:
#!/usr/bin/python3
from sys import stdin
import math
from operator import itemgetter
from bisect import bisect_left, bisect_right
readline = stdin.readline

def main():
    n = int(readline())
    xy = [tuple(map(int, readline().split())) + (i,) for i in range(n)]
    # [..., (x_i, y_i, i), ...]
    # sort by x
    xy.sort()

    root = int(math.sqrt(len(xy)))

    low = [x for x, y, i in xy[::root]]
    high = [x for x, y, i in xy[root - 1::root]] + [float('inf')]

    xy = [sorted(xy[i:i + root], key=itemgetter(1)) for i in range(0, len(xy), root)]
    xy = [([y for x, y, i in xyi], xyi) for xyi in xy]
    for sx, tx, sy, ty in (map(int, readline().split()) for _ in range(int(readline()))):
        ret = []
        for i in range(bisect_left(high, sx), bisect_right(low, tx)):
            k, v = xy[i]
            for i in range(bisect_left(k, sy), bisect_right(k, ty)):
                if sx <= v[i][0] <=tx:
                    ret.append(v[i][2])
        if ret:
            ret.sort()
            print('\n'.join(map(str,ret)))
        print()

main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/python3
from operator import attrgetter
import sys
class Point:
    pass

class Node:
    pass

def kdtree(points, depth=0):
    if not points:
        return
    # dimension
    if depth % 2 == 0:
        points.sort(key=attrgetter('x'))
    else:
        points.sort(key=attrgetter('y'))

    median = len(points)//2

    node = Node()
    node.location = points[median]
    node.left = kdtree(points[:median], depth + 1)
    node.right = kdtree(points[median + 1:], depth + 1)
    return node

def find(sx, tx, sy, ty, node, depth, result):
    if node == None:
        return
    if sx <= node.location.x <= tx and sy <= node.location.y <= ty:
        result.append(node.location.id)

    if depth % 2 == 0:
        if sx <= node.location.x:
            find(sx, tx, sy, ty, node.left, depth + 1, result)
        if node.location.x <= tx:
            find(sx, tx, sy, ty, node.right, depth + 1, result)
    else:
        if sy <= node.location.y:
            find(sx, tx, sy, ty, node.left, depth + 1, result)
        if node.location.y <= ty:
            find(sx, tx, sy, ty, node.right, depth + 1, result)

# main
n = int(input())
points = []
for i in range(n):
    point = Point()
    point.id = i
    point.x, point.y = map(int, sys.stdin.readline().split())
    points.append(point)
tree = kdtree(points)
q = int(input())
for i in range(q):
    sx, tx, sy, ty = map(int, sys.stdin.readline().split())
    result = []
    find(sx, tx, sy, ty, tree, 0, result)
    result.sort()
    for r in result:
        print(r)
    print()

Fixed submission:
#!/usr/bin/python3
from sys import stdin
import math
from operator import itemgetter
from bisect import bisect_left, bisect_right
readline = stdin.readline

def main():
    n = int(readline())
    xy = [tuple(map(int, readline().split())) + (i,) for i in range(n)]
    # [..., (x_i, y_i, i), ...]
    # sort by x
    xy.sort()

    root = int(math.sqrt(len(xy)))

    low = [x for x, y, i in xy[::root]]
    high = [x for x, y, i in xy[root - 1::root]] + [float('inf')]

    xy = [sorted(xy[i:i + root], key=itemgetter(1)) for i in range(0, len(xy), root)]
    xy = [([y for x, y, i in xyi], xyi) for xyi in xy]
    for sx, tx, sy, ty in (map(int, readline().split()) for _ in range(int(readline()))):
        ret = []
        for i in range(bisect_left(high, sx), bisect_right(low, tx)):
            k, v = xy[i]
            for i in range(bisect_left(k, sy), bisect_right(k, ty)):
                if sx <= v[i][0] <=tx:
                    ret.append(v[i][2])
        if ret:
            ret.sort()
            print('\n'.join(map(str,ret)))
        print()

main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/python3
import sys
import math
from operator import itemgetter
from bisect import bisect_left, bisect_right
readline = sys.stdin.readline

# main
n = int(readline())
xy = [tuple(map(int, readline().split())) + (i,) for i in range(n)]
# [..., (x_i, y_i, i), ...]
# sort by x
xy.sort()

root = int(math.sqrt(len(xy)))

low = [x for x, y, i in xy[::root]]
high = [x for x, y, i in xy[root - 1::root]] + [float('inf')]

xy = [sorted(xy[i:i + root], key=itemgetter(1)) for i in range(0, len(xy), root)]
xy = [([y for x, y, i in xyi], xyi) for xyi in xy]
for sx, tx, sy, ty in (map(int, readline().split()) for _ in range(int(readline()))):
    ret = []
    for i in range(bisect_left(high, sx), bisect_right(low, tx)):
        k, v = xy[i]
        for i in range(bisect_left(k, sy), bisect_right(k, ty)):
            if sx <= v[i][0] <=tx:
                ret.append(v[i][2])
    if ret:
        ret.sort()
        print('\n'.join(map(str,ret)))
    print()

Fixed submission:
#!/usr/bin/python3
from sys import stdin
import math
from operator import itemgetter
from bisect import bisect_left, bisect_right
readline = stdin.readline

def main():
    n = int(readline())
    xy = [tuple(map(int, readline().split())) + (i,) for i in range(n)]
    # [..., (x_i, y_i, i), ...]
    # sort by x
    xy.sort()

    root = int(math.sqrt(len(xy)))

    low = [x for x, y, i in xy[::root]]
    high = [x for x, y, i in xy[root - 1::root]] + [float('inf')]

    xy = [sorted(xy[i:i + root], key=itemgetter(1)) for i in range(0, len(xy), root)]
    xy = [([y for x, y, i in xyi], xyi) for xyi in xy]
    for sx, tx, sy, ty in (map(int, readline().split()) for _ in range(int(readline()))):
        ret = []
        for i in range(bisect_left(high, sx), bisect_right(low, tx)):
            k, v = xy[i]
            for i in range(bisect_left(k, sy), bisect_right(k, ty)):
                if sx <= v[i][0] <=tx:
                    ret.append(v[i][2])
        if ret:
            ret.sort()
            print('\n'.join(map(str,ret)))
        print()

main()

Buggy python submission (verdict: Runtime Error):
import sys
import stdin
import math
from operator import itemgetter
from bisect import bisect_left, bisect_right
readline = stdin.readline

# main
n = int(readline())
xy = [tuple(map(int, readline().split())) + (i,) for i in range(n)]
# [..., (x_i, y_i, i), ...]
# sort by x
xy.sort()

root = int(math.sqrt(len(xy)))

low = [x for x, y, i in xy[::root]]
high = [x for x, y, i in xy[root - 1::root]] + [float('inf')]

xy = [sorted(xy[i:i + root], key=itemgetter(1)) for i in range(0, len(xy), root)]
xy = [([y for x, y, i in xyi], xyi) for xyi in xy]
for sx, tx, sy, ty in (map(int, readline().split()) for _ in range(int(readline()))):
    ret = []
    for i in range(bisect_left(high, sx), bisect_right(low, tx)):
        k, v = xy[i]
        for i in range(bisect_left(k, sy), bisect_right(k, ty)):
            if sx <= v[i][0] <=tx:
                ret.append(v[i][2])
    if ret:
        ret.sort()
        print('\n'.join(map(str,ret)))
    print()

Fixed submission:
#!/usr/bin/python3
from sys import stdin
import math
from operator import itemgetter
from bisect import bisect_left, bisect_right
readline = stdin.readline

def main():
    n = int(readline())
    xy = [tuple(map(int, readline().split())) + (i,) for i in range(n)]
    # [..., (x_i, y_i, i), ...]
    # sort by x
    xy.sort()

    root = int(math.sqrt(len(xy)))

    low = [x for x, y, i in xy[::root]]
    high = [x for x, y, i in xy[root - 1::root]] + [float('inf')]

    xy = [sorted(xy[i:i + root], key=itemgetter(1)) for i in range(0, len(xy), root)]
    xy = [([y for x, y, i in xyi], xyi) for xyi in xy]
    for sx, tx, sy, ty in (map(int, readline().split()) for _ in range(int(readline()))):
        ret = []
        for i in range(bisect_left(high, sx), bisect_right(low, tx)):
            k, v = xy[i]
            for i in range(bisect_left(k, sy), bisect_right(k, ty)):
                if sx <= v[i][0] <=tx:
                    ret.append(v[i][2])
        if ret:
            ret.sort()
            print('\n'.join(map(str,ret)))
        print()

main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/python3
from sys import stdin
import math
from operator import itemgetter
from bisect import bisect_left, bisect_right
readline = stdin.readline

# main
n = int(readline())
xy = [tuple(map(int, readline().split())) + (i,) for i in range(n)]
# [..., (x_i, y_i, i), ...]
# sort by x
xy.sort()

root = int(math.sqrt(len(xy)))

low = [x for x, y, i in xy[::root]]
high = [x for x, y, i in xy[root - 1::root]] + [float('inf')]

xy = [sorted(xy[i:i + root], key=itemgetter(1)) for i in range(0, len(xy), root)]
xy = [([y for x, y, i in xyi], xyi) for xyi in xy]
for sx, tx, sy, ty in (map(int, readline().split()) for _ in range(int(readline()))):
    ret = []
    for i in range(bisect_left(high, sx), bisect_right(low, tx)):
        k, v = xy[i]
        for i in range(bisect_left(k, sy), bisect_right(k, ty)):
            if sx <= v[i][0] <=tx:
                ret.append(v[i][2])
    if ret:
        ret.sort()
        print('\n'.join(map(str,ret)))
    print()

Fixed submission:
#!/usr/bin/python3
from sys import stdin
import math
from operator import itemgetter
from bisect import bisect_left, bisect_right
readline = stdin.readline

def main():
    n = int(readline())
    xy = [tuple(map(int, readline().split())) + (i,) for i in range(n)]
    # [..., (x_i, y_i, i), ...]
    # sort by x
    xy.sort()

    root = int(math.sqrt(len(xy)))

    low = [x for x, y, i in xy[::root]]
    high = [x for x, y, i in xy[root - 1::root]] + [float('inf')]

    xy = [sorted(xy[i:i + root], key=itemgetter(1)) for i in range(0, len(xy), root)]
    xy = [([y for x, y, i in xyi], xyi) for xyi in xy]
    for sx, tx, sy, ty in (map(int, readline().split()) for _ in range(int(readline()))):
        ret = []
        for i in range(bisect_left(high, sx), bisect_right(low, tx)):
            k, v = xy[i]
            for i in range(bisect_left(k, sy), bisect_right(k, ty)):
                if sx <= v[i][0] <=tx:
                    ret.append(v[i][2])
        if ret:
            ret.sort()
            print('\n'.join(map(str,ret)))
        print()

main()