Buggy python submission (verdict: Time Limit Exceeded):
import sys

i_f = sys.stdin

n = int(i_f.readline())

P = [list(map(int, i_f.readline().split())) for _ in range(n)]

q = int(i_f.readline())

for l in i_f:
    sx, tx, sy, ty = map(int, l.split())
    for i, p in enumerate(P):
        x, y = p
        if sx <= x <= tx and sy <= y <= ty:
            print(i)
    print('')

Fixed submission:
import sys, math
from operator import itemgetter
from bisect import bisect_left, bisect_right

f_i = sys.stdin

def main():
    n = int(f_i.readline())
    
    lx = []
    ly = []
    li = []
    for i in range(n):
        x, y = map(int, f_i.readline().split())
        lx.append(x)
        ly.append(y)
        li.append(i)

    x_width = max(lx) - min(lx)
    y_width = max(ly) - min(ly)
    if x_width > y_width:
        P = list(zip(lx, ly, li))
    else:
        P = list(zip(ly, lx, li))
    P.sort()

    interval = int(math.sqrt(n))

    low = [v1 for v1, v2, i in P[::interval]]
    high = [v1 for v1, v2, i in P[interval - 1::interval]] + [float('inf')]

    S = []
    v2_sec_list = []
    for i in range(0, n, interval):
        si = P[i:i + interval]
        si.sort(key=itemgetter(1))
        v2_s = [p[1] for p in si]
        v2_sec_list.append(v2_s)
        S.append(si)

    A = []

    q = f_i.readline()

    for l in f_i:
        sx, tx, sy, ty = map(int, l.split())
        a = []
        if x_width > y_width:
            for i in range(bisect_left(high, sx), bisect_right(low, tx)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sy), bisect_right(k, ty)):
                    if sx <= v[j][0] <= tx:
                        a.append(v[j][2])
        else:
            for i in range(bisect_left(high, sy), bisect_right(low, ty)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sx), bisect_right(k, tx)):
                    if sy <= v[j][0] <= ty:
                        a.append(v[j][2])
        
        if a:
            a.sort()
            A.extend(a)
        A.append('')

    print('\n'.join(map(str, A)))

main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys

i_f = sys.stdin

n = int(i_f.readline())

class kdTreeNode:
    def __init__(self, input_num, x, y):
        self.input_num = input_num
        self.x = x
        self.y = y
        self.left = None
        self.right = None

T = [kdTreeNode(i, *map(int, i_f.readline().split())) for i in range(n)]

def make2DTree(l, r, depth):
    if l >= r:
        return None

    mid = (l + r) // 2

    if depth % 2 == 0:
        T[l:r] = sorted(T[l:r], key=lambda n: n.x)
    else:
        T[l:r] = sorted(T[l:r], key=lambda n: n.y)

    T[mid].left = make2DTree(l, mid, depth + 1)
    T[mid].right = make2DTree(mid + 1, r, depth + 1)

    return mid


make2DTree(0, n, 0)

def range_search(sx, tx, sy, yx):
    ans = []
    
    def _find(v, sx, tx, sy, ty, depth):
        node = T[v]
        x = node.x
        y = node.y

        if sx <= x <= tx and sy <= y <= ty:
            ans.append(node.input_num)

        if depth % 2 == 0:
            if node.left != None and sx <= x:
                _find(node.left, sx, tx, sy, ty, depth + 1)
            if node.right and x <= tx:
                _find(node.right, sx, tx, sy, ty, depth + 1)
        else:
            if node.left != None and sy <= y:
                _find(node.left, sx, tx, sy, ty, depth + 1)
            if node.right and y <= ty:
                _find(node.right, sx, tx, sy, ty, depth + 1)

    _find(v, sx, tx, sy, ty, 0)
    if ans:
        ans.sort()
        print(*ans, sep='\n', end='\n\n')
    else:
        print('')


q = int(i_f.readline())

v = n // 2

for l in i_f:
    sx, tx, sy, ty = map(int, l.split())
    range_search(sx, tx, sy, ty)

Fixed submission:
import sys, math
from operator import itemgetter
from bisect import bisect_left, bisect_right

f_i = sys.stdin

def main():
    n = int(f_i.readline())
    
    lx = []
    ly = []
    li = []
    for i in range(n):
        x, y = map(int, f_i.readline().split())
        lx.append(x)
        ly.append(y)
        li.append(i)

    x_width = max(lx) - min(lx)
    y_width = max(ly) - min(ly)
    if x_width > y_width:
        P = list(zip(lx, ly, li))
    else:
        P = list(zip(ly, lx, li))
    P.sort()

    interval = int(math.sqrt(n))

    low = [v1 for v1, v2, i in P[::interval]]
    high = [v1 for v1, v2, i in P[interval - 1::interval]] + [float('inf')]

    S = []
    v2_sec_list = []
    for i in range(0, n, interval):
        si = P[i:i + interval]
        si.sort(key=itemgetter(1))
        v2_s = [p[1] for p in si]
        v2_sec_list.append(v2_s)
        S.append(si)

    A = []

    q = f_i.readline()

    for l in f_i:
        sx, tx, sy, ty = map(int, l.split())
        a = []
        if x_width > y_width:
            for i in range(bisect_left(high, sx), bisect_right(low, tx)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sy), bisect_right(k, ty)):
                    if sx <= v[j][0] <= tx:
                        a.append(v[j][2])
        else:
            for i in range(bisect_left(high, sy), bisect_right(low, ty)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sx), bisect_right(k, tx)):
                    if sy <= v[j][0] <= ty:
                        a.append(v[j][2])
        
        if a:
            a.sort()
            A.extend(a)
        A.append('')

    print('\n'.join(map(str, A)))

main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys

i_f = sys.stdin

n = int(i_f.readline())

class kdTreeNode:
    def __init__(self, input_num, x, y):
        self.input_num = input_num
        self.x = x
        self.y = y
        self.left = None
        self.right = None

T = [kdTreeNode(i, *map(int, i_f.readline().split())) for i in range(n)]

def make2DTree(l, r, depth):
    if l >= r:
        return None

    mid = (l + r) // 2

    if depth % 2 == 0:
        T[l:r] = sorted(T[l:r], key=lambda n: n.x)
    else:
        T[l:r] = sorted(T[l:r], key=lambda n: n.y)

    T[mid].left = make2DTree(l, mid, depth + 1)
    T[mid].right = make2DTree(mid + 1, r, depth + 1)

    return mid


make2DTree(0, n, 0)

Ans = []

def range_search(sx, tx, sy, yx):
    ans = []
    
    def _find(v, sx, tx, sy, ty, depth):
        node = T[v]
        x = node.x
        y = node.y

        if sx <= x <= tx and sy <= y <= ty:
            ans.append(node.input_num)

        if depth % 2 == 0:
            if node.left != None and sx <= x:
                _find(node.left, sx, tx, sy, ty, depth + 1)
            if node.right and x <= tx:
                _find(node.right, sx, tx, sy, ty, depth + 1)
        else:
            if node.left != None and sy <= y:
                _find(node.left, sx, tx, sy, ty, depth + 1)
            if node.right and y <= ty:
                _find(node.right, sx, tx, sy, ty, depth + 1)

    _find(v, sx, tx, sy, ty, 0)
    
    if ans:
        ans.sort()
        Ans.extend(ans)
        Ans.append('')
    else:
        Ans.append('')


q = int(i_f.readline())

v = n // 2

for l in i_f:
    sx, tx, sy, ty = map(int, l.split())
    range_search(sx, tx, sy, ty)

print(*Ans, sep='\n')

Fixed submission:
import sys, math
from operator import itemgetter
from bisect import bisect_left, bisect_right

f_i = sys.stdin

def main():
    n = int(f_i.readline())
    
    lx = []
    ly = []
    li = []
    for i in range(n):
        x, y = map(int, f_i.readline().split())
        lx.append(x)
        ly.append(y)
        li.append(i)

    x_width = max(lx) - min(lx)
    y_width = max(ly) - min(ly)
    if x_width > y_width:
        P = list(zip(lx, ly, li))
    else:
        P = list(zip(ly, lx, li))
    P.sort()

    interval = int(math.sqrt(n))

    low = [v1 for v1, v2, i in P[::interval]]
    high = [v1 for v1, v2, i in P[interval - 1::interval]] + [float('inf')]

    S = []
    v2_sec_list = []
    for i in range(0, n, interval):
        si = P[i:i + interval]
        si.sort(key=itemgetter(1))
        v2_s = [p[1] for p in si]
        v2_sec_list.append(v2_s)
        S.append(si)

    A = []

    q = f_i.readline()

    for l in f_i:
        sx, tx, sy, ty = map(int, l.split())
        a = []
        if x_width > y_width:
            for i in range(bisect_left(high, sx), bisect_right(low, tx)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sy), bisect_right(k, ty)):
                    if sx <= v[j][0] <= tx:
                        a.append(v[j][2])
        else:
            for i in range(bisect_left(high, sy), bisect_right(low, ty)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sx), bisect_right(k, tx)):
                    if sy <= v[j][0] <= ty:
                        a.append(v[j][2])
        
        if a:
            a.sort()
            A.extend(a)
        A.append('')

    print('\n'.join(map(str, A)))

main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys

i_f = sys.stdin

n = int(i_f.readline())

class kdTreeNode:
    def __init__(self, input_num, x, y):
        self.input_num = input_num
        self.x = x
        self.y = y
        self.left = None
        self.right = None

T = [kdTreeNode(i, *map(int, i_f.readline().split())) for i in range(n)]

def make2DTree(l, r, depth):
    if l >= r:
        return None

    mid = (l + r) // 2

    if depth % 2 == 0:
        T[l:r] = sorted(T[l:r], key=lambda n: n.x)
    else:
        T[l:r] = sorted(T[l:r], key=lambda n: n.y)

    T[mid].left = make2DTree(l, mid, depth + 1)
    T[mid].right = make2DTree(mid + 1, r, depth + 1)

    return mid


make2DTree(0, n, 0)

Ans = []

def range_search(sx, tx, sy, yx):
    ans = []
    
    def _find(v, sx, tx, sy, ty, depth):
        node = T[v]
        x = node.x
        y = node.y

        if sx <= x <= tx and sy <= y <= ty:
            ans.append(node.input_num)

        if depth % 2 == 0:
            if node.left != None and sx <= x:
                _find(node.left, sx, tx, sy, ty, depth + 1)
            if node.right and x <= tx:
                _find(node.right, sx, tx, sy, ty, depth + 1)
        else:
            if node.left != None and sy <= y:
                _find(node.left, sx, tx, sy, ty, depth + 1)
            if node.right and y <= ty:
                _find(node.right, sx, tx, sy, ty, depth + 1)

    _find(v, sx, tx, sy, ty, 0)
    
    if ans:
        ans.sort()
        Ans.extend(ans)
    Ans.append('')


q = int(i_f.readline())

v = n // 2

for l in i_f:
    sx, tx, sy, ty = map(int, l.split())
    range_search(sx, tx, sy, ty)

print(*Ans, sep='\n')

Fixed submission:
import sys, math
from operator import itemgetter
from bisect import bisect_left, bisect_right

f_i = sys.stdin

def main():
    n = int(f_i.readline())
    
    lx = []
    ly = []
    li = []
    for i in range(n):
        x, y = map(int, f_i.readline().split())
        lx.append(x)
        ly.append(y)
        li.append(i)

    x_width = max(lx) - min(lx)
    y_width = max(ly) - min(ly)
    if x_width > y_width:
        P = list(zip(lx, ly, li))
    else:
        P = list(zip(ly, lx, li))
    P.sort()

    interval = int(math.sqrt(n))

    low = [v1 for v1, v2, i in P[::interval]]
    high = [v1 for v1, v2, i in P[interval - 1::interval]] + [float('inf')]

    S = []
    v2_sec_list = []
    for i in range(0, n, interval):
        si = P[i:i + interval]
        si.sort(key=itemgetter(1))
        v2_s = [p[1] for p in si]
        v2_sec_list.append(v2_s)
        S.append(si)

    A = []

    q = f_i.readline()

    for l in f_i:
        sx, tx, sy, ty = map(int, l.split())
        a = []
        if x_width > y_width:
            for i in range(bisect_left(high, sx), bisect_right(low, tx)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sy), bisect_right(k, ty)):
                    if sx <= v[j][0] <= tx:
                        a.append(v[j][2])
        else:
            for i in range(bisect_left(high, sy), bisect_right(low, ty)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sx), bisect_right(k, tx)):
                    if sy <= v[j][0] <= ty:
                        a.append(v[j][2])
        
        if a:
            a.sort()
            A.extend(a)
        A.append('')

    print('\n'.join(map(str, A)))

main()

Buggy python submission (verdict: Runtime Error):
import sys

i_f = sys.stdin

n = int(i_f.readline())

T = [[i, *map(int, i_f.readline().split()), None, None] for i in range(n)]

def make2DTree(l, r, depth):
    if l >= r:
        return None

    mid = (l + r) // 2

    if depth % 2 == 0:
        T[l:r] = sorted(T[l:r], key=lambda n: n[1])
    else:
        T[l:r] = sorted(T[l:r], key=lambda n: n[2])

    T[mid][3] = make2DTree(l, mid, depth + 1)
    T[mid][4] = make2DTree(mid + 1, r, depth + 1)

    return mid


make2DTree(0, n, 0)

Ans = []

def range_search(sx, tx, sy, yx):
    ans = []
    
    def _find(v, sx, tx, sy, ty, depth):
        node = T[v]
        x = node[1]
        y = node[2]

        if sx <= x <= tx and sy <= y <= ty:
            ans.append(node[0])

        if depth % 2 == 0:
            if node[3] != None and sx <= x:
                _find(node[3], sx, tx, sy, ty, depth + 1)
            if node[4] and x <= tx:
                _find(node[4], sx, tx, sy, ty, depth + 1)
        else:
            if node[3] != None and sy <= y:
                _find(node[3], sx, tx, sy, ty, depth + 1)
            if node[4] and y <= ty:
                _find(node[4], sx, tx, sy, ty, depth + 1)

    _find(v, sx, tx, sy, ty, 0)
    
    if ans:
        ans.sort()
        Ans.extend(ans)
    Ans.append('')


q = int(i_f.readline())

v = n // 2

for l in i_f:
    sx, tx, sy, ty = map(int, l.split())
    range_search(sx, tx, sy, ty)

print(*Ans, sep='\n')

Fixed submission:
import sys, math
from operator import itemgetter
from bisect import bisect_left, bisect_right

f_i = sys.stdin

def main():
    n = int(f_i.readline())
    
    lx = []
    ly = []
    li = []
    for i in range(n):
        x, y = map(int, f_i.readline().split())
        lx.append(x)
        ly.append(y)
        li.append(i)

    x_width = max(lx) - min(lx)
    y_width = max(ly) - min(ly)
    if x_width > y_width:
        P = list(zip(lx, ly, li))
    else:
        P = list(zip(ly, lx, li))
    P.sort()

    interval = int(math.sqrt(n))

    low = [v1 for v1, v2, i in P[::interval]]
    high = [v1 for v1, v2, i in P[interval - 1::interval]] + [float('inf')]

    S = []
    v2_sec_list = []
    for i in range(0, n, interval):
        si = P[i:i + interval]
        si.sort(key=itemgetter(1))
        v2_s = [p[1] for p in si]
        v2_sec_list.append(v2_s)
        S.append(si)

    A = []

    q = f_i.readline()

    for l in f_i:
        sx, tx, sy, ty = map(int, l.split())
        a = []
        if x_width > y_width:
            for i in range(bisect_left(high, sx), bisect_right(low, tx)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sy), bisect_right(k, ty)):
                    if sx <= v[j][0] <= tx:
                        a.append(v[j][2])
        else:
            for i in range(bisect_left(high, sy), bisect_right(low, ty)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sx), bisect_right(k, tx)):
                    if sy <= v[j][0] <= ty:
                        a.append(v[j][2])
        
        if a:
            a.sort()
            A.extend(a)
        A.append('')

    print('\n'.join(map(str, A)))

main()

Buggy python submission (verdict: Runtime Error):
import sys

i_f = sys.stdin

n = int(i_f.readline())

T = [[i, *map(int, i_f.readline().split()), None, None] for i in range(n)]

def make2DTree(l, r, depth):
    if l >= r:
        return None

    mid = (l + r) // 2

    if depth % 2 == 0:
        T[l:r] = sorted(T[l:r], key=lambda n: n[1])
    else:
        T[l:r] = sorted(T[l:r], key=lambda n: n[2])

    T[mid][3] = make2DTree(l, mid, depth + 1)
    T[mid][4] = make2DTree(mid + 1, r, depth + 1)

    return mid


make2DTree(0, n, 0)

Ans = []

def range_search(sx, tx, sy, yx):
    ans = []
    
    def _find(v, sx, tx, sy, ty, depth):
        node = T[v]
        x = node[1]
        y = node[2]

        if sx <= x <= tx and sy <= y <= ty:
            ans.append(node[0])

        if depth % 2 == 0:
            if node[3] != None and sx <= x:
                _find(node[3], sx, tx, sy, ty, depth + 1)
            if node[4] and x <= tx:
                _find(node[4], sx, tx, sy, ty, depth + 1)
        else:
            if node[3] != None and sy <= y:
                _find(node[3], sx, tx, sy, ty, depth + 1)
            if node[4] and y <= ty:
                _find(node[4], sx, tx, sy, ty, depth + 1)

    _find(v, sx, tx, sy, ty, 0)
    
    if ans:
        ans.sort()
        Ans.extend(ans)
    Ans.append('')


q = int(i_f.readline())

v = n // 2

for l in i_f:
    sx, tx, sy, ty = map(int, l.split())
    range_search(sx, tx, sy, ty)

print(*Ans, sep='\n')

Fixed submission:
import sys, math
from operator import itemgetter
from bisect import bisect_left, bisect_right

f_i = sys.stdin

def main():
    n = int(f_i.readline())
    
    lx = []
    ly = []
    li = []
    for i in range(n):
        x, y = map(int, f_i.readline().split())
        lx.append(x)
        ly.append(y)
        li.append(i)

    x_width = max(lx) - min(lx)
    y_width = max(ly) - min(ly)
    if x_width > y_width:
        P = list(zip(lx, ly, li))
    else:
        P = list(zip(ly, lx, li))
    P.sort()

    interval = int(math.sqrt(n))

    low = [v1 for v1, v2, i in P[::interval]]
    high = [v1 for v1, v2, i in P[interval - 1::interval]] + [float('inf')]

    S = []
    v2_sec_list = []
    for i in range(0, n, interval):
        si = P[i:i + interval]
        si.sort(key=itemgetter(1))
        v2_s = [p[1] for p in si]
        v2_sec_list.append(v2_s)
        S.append(si)

    A = []

    q = f_i.readline()

    for l in f_i:
        sx, tx, sy, ty = map(int, l.split())
        a = []
        if x_width > y_width:
            for i in range(bisect_left(high, sx), bisect_right(low, tx)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sy), bisect_right(k, ty)):
                    if sx <= v[j][0] <= tx:
                        a.append(v[j][2])
        else:
            for i in range(bisect_left(high, sy), bisect_right(low, ty)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sx), bisect_right(k, tx)):
                    if sy <= v[j][0] <= ty:
                        a.append(v[j][2])
        
        if a:
            a.sort()
            A.extend(a)
        A.append('')

    print('\n'.join(map(str, A)))

main()

Buggy python submission (verdict: Runtime Error):
import sys

i_f = sys.stdin

n = int(i_f.readline())

T = [[i, *map(int, i_f.readline().split()), None, None] for i in range(n)]

def make2DTree(l, r, depth):
    if l >= r:
        return None

    mid = (l + r) // 2

    if depth % 2 == 0:
        T[l:r] = sorted(T[l:r], key=lambda n: n[1])
    else:
        T[l:r] = sorted(T[l:r], key=lambda n: n[2])

    T[mid][3] = make2DTree(l, mid, depth + 1)
    T[mid][4] = make2DTree(mid + 1, r, depth + 1)

    return mid


make2DTree(0, n, 0)

Ans = []

def range_search(sx, tx, sy, yx):
    ans = []
    
    def _find(v, sx, tx, sy, ty, depth):
        node = T[v]
        x = node[1]
        y = node[2]

        if sx <= x <= tx and sy <= y <= ty:
            ans.append(node[0])

        if depth % 2 == 0:
            if node[3] != None and sx <= x:
                _find(node[3], sx, tx, sy, ty, depth + 1)
            if node[4] and x <= tx:
                _find(node[4], sx, tx, sy, ty, depth + 1)
        else:
            if node[3] != None and sy <= y:
                _find(node[3], sx, tx, sy, ty, depth + 1)
            if node[4] and y <= ty:
                _find(node[4], sx, tx, sy, ty, depth + 1)

    _find(v, sx, tx, sy, ty, 0)
    
    if ans:
        ans.sort()
        Ans.extend(ans)
    Ans.append('')


q = int(i_f.readline())

v = n // 2

for l in i_f:
    sx, tx, sy, ty = map(int, l.split())
    range_search(sx, tx, sy, ty)

print(*Ans, sep='\n')

Fixed submission:
import sys, math
from operator import itemgetter
from bisect import bisect_left, bisect_right

f_i = sys.stdin

def main():
    n = int(f_i.readline())
    
    lx = []
    ly = []
    li = []
    for i in range(n):
        x, y = map(int, f_i.readline().split())
        lx.append(x)
        ly.append(y)
        li.append(i)

    x_width = max(lx) - min(lx)
    y_width = max(ly) - min(ly)
    if x_width > y_width:
        P = list(zip(lx, ly, li))
    else:
        P = list(zip(ly, lx, li))
    P.sort()

    interval = int(math.sqrt(n))

    low = [v1 for v1, v2, i in P[::interval]]
    high = [v1 for v1, v2, i in P[interval - 1::interval]] + [float('inf')]

    S = []
    v2_sec_list = []
    for i in range(0, n, interval):
        si = P[i:i + interval]
        si.sort(key=itemgetter(1))
        v2_s = [p[1] for p in si]
        v2_sec_list.append(v2_s)
        S.append(si)

    A = []

    q = f_i.readline()

    for l in f_i:
        sx, tx, sy, ty = map(int, l.split())
        a = []
        if x_width > y_width:
            for i in range(bisect_left(high, sx), bisect_right(low, tx)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sy), bisect_right(k, ty)):
                    if sx <= v[j][0] <= tx:
                        a.append(v[j][2])
        else:
            for i in range(bisect_left(high, sy), bisect_right(low, ty)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sx), bisect_right(k, tx)):
                    if sy <= v[j][0] <= ty:
                        a.append(v[j][2])
        
        if a:
            a.sort()
            A.extend(a)
        A.append('')

    print('\n'.join(map(str, A)))

main()

Buggy python submission (verdict: Runtime Error):
import sys

i_f = sys.stdin

n = int(i_f.readline())

T = [[i, map(int, i_f.readline().split()), None, None] for i in range(n)]

def make2DTree(l, r, depth):
    if l >= r:
        return None

    mid = (l + r) // 2

    if depth % 2 == 0:
        T[l:r] = sorted(T[l:r], key=lambda n: n[1])
    else:
        T[l:r] = sorted(T[l:r], key=lambda n: n[2])

    T[mid][3] = make2DTree(l, mid, depth + 1)
    T[mid][4] = make2DTree(mid + 1, r, depth + 1)

    return mid


make2DTree(0, n, 0)

Ans = []

def range_search(sx, tx, sy, yx):
    ans = []
    
    def _find(v, sx, tx, sy, ty, depth):
        node = T[v]
        x = node[1]
        y = node[2]

        if sx <= x <= tx and sy <= y <= ty:
            ans.append(node[0])

        if depth % 2 == 0:
            if node[3] != None and sx <= x:
                _find(node[3], sx, tx, sy, ty, depth + 1)
            if node[4] and x <= tx:
                _find(node[4], sx, tx, sy, ty, depth + 1)
        else:
            if node[3] != None and sy <= y:
                _find(node[3], sx, tx, sy, ty, depth + 1)
            if node[4] and y <= ty:
                _find(node[4], sx, tx, sy, ty, depth + 1)

    _find(v, sx, tx, sy, ty, 0)
    
    if ans:
        ans.sort()
        Ans.extend(ans)
    Ans.append('')


q = int(i_f.readline())

v = n // 2

for l in i_f:
    sx, tx, sy, ty = map(int, l.split())
    range_search(sx, tx, sy, ty)

print(*Ans, sep='\n')

Fixed submission:
import sys, math
from operator import itemgetter
from bisect import bisect_left, bisect_right

f_i = sys.stdin

def main():
    n = int(f_i.readline())
    
    lx = []
    ly = []
    li = []
    for i in range(n):
        x, y = map(int, f_i.readline().split())
        lx.append(x)
        ly.append(y)
        li.append(i)

    x_width = max(lx) - min(lx)
    y_width = max(ly) - min(ly)
    if x_width > y_width:
        P = list(zip(lx, ly, li))
    else:
        P = list(zip(ly, lx, li))
    P.sort()

    interval = int(math.sqrt(n))

    low = [v1 for v1, v2, i in P[::interval]]
    high = [v1 for v1, v2, i in P[interval - 1::interval]] + [float('inf')]

    S = []
    v2_sec_list = []
    for i in range(0, n, interval):
        si = P[i:i + interval]
        si.sort(key=itemgetter(1))
        v2_s = [p[1] for p in si]
        v2_sec_list.append(v2_s)
        S.append(si)

    A = []

    q = f_i.readline()

    for l in f_i:
        sx, tx, sy, ty = map(int, l.split())
        a = []
        if x_width > y_width:
            for i in range(bisect_left(high, sx), bisect_right(low, tx)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sy), bisect_right(k, ty)):
                    if sx <= v[j][0] <= tx:
                        a.append(v[j][2])
        else:
            for i in range(bisect_left(high, sy), bisect_right(low, ty)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sx), bisect_right(k, tx)):
                    if sy <= v[j][0] <= ty:
                        a.append(v[j][2])
        
        if a:
            a.sort()
            A.extend(a)
        A.append('')

    print('\n'.join(map(str, A)))

main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys

i_f = sys.stdin

n = int(i_f.readline())

# T = [[i, *map(int, i_f.readline().split()), None, None] for i in range(n)]

T = []

for i in range(n):
    node = [i]
    x, y = map(int, i_f.readline().split())
    node.append(x)
    node.append(y)
    node.append(None)
    node.append(None)
    T.append(node)

def make2DTree(l, r, depth):
    if l >= r:
        return None

    mid = (l + r) // 2

    if depth % 2 == 0:
        T[l:r] = sorted(T[l:r], key=lambda n: n[1])
    else:
        T[l:r] = sorted(T[l:r], key=lambda n: n[2])

    T[mid][3] = make2DTree(l, mid, depth + 1)
    T[mid][4] = make2DTree(mid + 1, r, depth + 1)

    return mid


make2DTree(0, n, 0)

Ans = []

def range_search(sx, tx, sy, yx):
    ans = []
    
    def _find(v, sx, tx, sy, ty, depth):
        node = T[v]
        x = node[1]
        y = node[2]

        if sx <= x <= tx and sy <= y <= ty:
            ans.append(node[0])

        if depth % 2 == 0:
            if node[3] != None and sx <= x:
                _find(node[3], sx, tx, sy, ty, depth + 1)
            if node[4] and x <= tx:
                _find(node[4], sx, tx, sy, ty, depth + 1)
        else:
            if node[3] != None and sy <= y:
                _find(node[3], sx, tx, sy, ty, depth + 1)
            if node[4] and y <= ty:
                _find(node[4], sx, tx, sy, ty, depth + 1)

    _find(v, sx, tx, sy, ty, 0)
    
    if ans:
        ans.sort()
        Ans.extend(ans)
    Ans.append('')


q = int(i_f.readline())

v = n // 2

for l in i_f:
    sx, tx, sy, ty = map(int, l.split())
    range_search(sx, tx, sy, ty)

print(*Ans, sep='\n')

Fixed submission:
import sys, math
from operator import itemgetter
from bisect import bisect_left, bisect_right

f_i = sys.stdin

def main():
    n = int(f_i.readline())
    
    lx = []
    ly = []
    li = []
    for i in range(n):
        x, y = map(int, f_i.readline().split())
        lx.append(x)
        ly.append(y)
        li.append(i)

    x_width = max(lx) - min(lx)
    y_width = max(ly) - min(ly)
    if x_width > y_width:
        P = list(zip(lx, ly, li))
    else:
        P = list(zip(ly, lx, li))
    P.sort()

    interval = int(math.sqrt(n))

    low = [v1 for v1, v2, i in P[::interval]]
    high = [v1 for v1, v2, i in P[interval - 1::interval]] + [float('inf')]

    S = []
    v2_sec_list = []
    for i in range(0, n, interval):
        si = P[i:i + interval]
        si.sort(key=itemgetter(1))
        v2_s = [p[1] for p in si]
        v2_sec_list.append(v2_s)
        S.append(si)

    A = []

    q = f_i.readline()

    for l in f_i:
        sx, tx, sy, ty = map(int, l.split())
        a = []
        if x_width > y_width:
            for i in range(bisect_left(high, sx), bisect_right(low, tx)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sy), bisect_right(k, ty)):
                    if sx <= v[j][0] <= tx:
                        a.append(v[j][2])
        else:
            for i in range(bisect_left(high, sy), bisect_right(low, ty)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sx), bisect_right(k, tx)):
                    if sy <= v[j][0] <= ty:
                        a.append(v[j][2])
        
        if a:
            a.sort()
            A.extend(a)
        A.append('')

    print('\n'.join(map(str, A)))

main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys

i_f = sys.stdin

n = int(i_f.readline())

T = []

for i in range(n):
    x, y = map(int, i_f.readline().split())
    T.append([i, x, y, None, None])

def make2DTree(l, r, depth):
    if l >= r:
        return None

    mid = (l + r) // 2

    if depth % 2 == 0:
        T[l:r] = sorted(T[l:r], key=lambda n: n[1])
    else:
        T[l:r] = sorted(T[l:r], key=lambda n: n[2])

    T[mid][3] = make2DTree(l, mid, depth + 1)
    T[mid][4] = make2DTree(mid + 1, r, depth + 1)

    return mid


make2DTree(0, n, 0)

Ans = []

def range_search(sx, tx, sy, yx):
    ans = []
    
    def _find(v, sx, tx, sy, ty, depth):
        node = T[v]
        x = node[1]
        y = node[2]

        if sx <= x <= tx and sy <= y <= ty:
            ans.append(node[0])

        if depth % 2 == 0:
            if node[3] != None and sx <= x:
                _find(node[3], sx, tx, sy, ty, depth + 1)
            if node[4] and x <= tx:
                _find(node[4], sx, tx, sy, ty, depth + 1)
        else:
            if node[3] != None and sy <= y:
                _find(node[3], sx, tx, sy, ty, depth + 1)
            if node[4] and y <= ty:
                _find(node[4], sx, tx, sy, ty, depth + 1)

    _find(v, sx, tx, sy, ty, 0)
    
    if ans:
        ans.sort()
        Ans.extend(ans)
    Ans.append('')


q = int(i_f.readline())

v = n // 2

for l in i_f:
    sx, tx, sy, ty = map(int, l.split())
    range_search(sx, tx, sy, ty)

print(*Ans, sep='\n')

Fixed submission:
import sys, math
from operator import itemgetter
from bisect import bisect_left, bisect_right

f_i = sys.stdin

def main():
    n = int(f_i.readline())
    
    lx = []
    ly = []
    li = []
    for i in range(n):
        x, y = map(int, f_i.readline().split())
        lx.append(x)
        ly.append(y)
        li.append(i)

    x_width = max(lx) - min(lx)
    y_width = max(ly) - min(ly)
    if x_width > y_width:
        P = list(zip(lx, ly, li))
    else:
        P = list(zip(ly, lx, li))
    P.sort()

    interval = int(math.sqrt(n))

    low = [v1 for v1, v2, i in P[::interval]]
    high = [v1 for v1, v2, i in P[interval - 1::interval]] + [float('inf')]

    S = []
    v2_sec_list = []
    for i in range(0, n, interval):
        si = P[i:i + interval]
        si.sort(key=itemgetter(1))
        v2_s = [p[1] for p in si]
        v2_sec_list.append(v2_s)
        S.append(si)

    A = []

    q = f_i.readline()

    for l in f_i:
        sx, tx, sy, ty = map(int, l.split())
        a = []
        if x_width > y_width:
            for i in range(bisect_left(high, sx), bisect_right(low, tx)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sy), bisect_right(k, ty)):
                    if sx <= v[j][0] <= tx:
                        a.append(v[j][2])
        else:
            for i in range(bisect_left(high, sy), bisect_right(low, ty)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sx), bisect_right(k, tx)):
                    if sy <= v[j][0] <= ty:
                        a.append(v[j][2])
        
        if a:
            a.sort()
            A.extend(a)
        A.append('')

    print('\n'.join(map(str, A)))

main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys

i_f = sys.stdin

n = int(i_f.readline())

T = []

for i in range(n):
    x, y = map(int, i_f.readline().split())
    T.append([i, x, y, None, None])

def make2DTree(l, r, depth):
    if l >= r:
        return None

    mid = (l + r) // 2

    if depth % 2 == 0:
        T[l:r] = sorted(T[l:r], key=lambda n: n[1])
    else:
        T[l:r] = sorted(T[l:r], key=lambda n: n[2])

    T[mid][3] = make2DTree(l, mid, depth + 1)
    T[mid][4] = make2DTree(mid + 1, r, depth + 1)

    return mid


make2DTree(0, n, 0)

def range_search(sx, tx, sy, yx):
    ans = []
    
    def _find(v, sx, tx, sy, ty, depth):
        node = T[v]
        x = node[1]
        y = node[2]

        if sx <= x <= tx and sy <= y <= ty:
            ans.append(node[0])

        if depth % 2 == 0:
            if node[3] != None and sx <= x:
                _find(node[3], sx, tx, sy, ty, depth + 1)
            if node[4] and x <= tx:
                _find(node[4], sx, tx, sy, ty, depth + 1)
        else:
            if node[3] != None and sy <= y:
                _find(node[3], sx, tx, sy, ty, depth + 1)
            if node[4] and y <= ty:
                _find(node[4], sx, tx, sy, ty, depth + 1)

    _find(v, sx, tx, sy, ty, 0)
    
    ans.sort()
    if ans:
        print('\n'.join(map(str, ans)))
    print('')


q = int(i_f.readline())

v = n // 2

for l in i_f:
    sx, tx, sy, ty = map(int, l.split())
    range_search(sx, tx, sy, ty)

Fixed submission:
import sys, math
from operator import itemgetter
from bisect import bisect_left, bisect_right

f_i = sys.stdin

def main():
    n = int(f_i.readline())
    
    lx = []
    ly = []
    li = []
    for i in range(n):
        x, y = map(int, f_i.readline().split())
        lx.append(x)
        ly.append(y)
        li.append(i)

    x_width = max(lx) - min(lx)
    y_width = max(ly) - min(ly)
    if x_width > y_width:
        P = list(zip(lx, ly, li))
    else:
        P = list(zip(ly, lx, li))
    P.sort()

    interval = int(math.sqrt(n))

    low = [v1 for v1, v2, i in P[::interval]]
    high = [v1 for v1, v2, i in P[interval - 1::interval]] + [float('inf')]

    S = []
    v2_sec_list = []
    for i in range(0, n, interval):
        si = P[i:i + interval]
        si.sort(key=itemgetter(1))
        v2_s = [p[1] for p in si]
        v2_sec_list.append(v2_s)
        S.append(si)

    A = []

    q = f_i.readline()

    for l in f_i:
        sx, tx, sy, ty = map(int, l.split())
        a = []
        if x_width > y_width:
            for i in range(bisect_left(high, sx), bisect_right(low, tx)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sy), bisect_right(k, ty)):
                    if sx <= v[j][0] <= tx:
                        a.append(v[j][2])
        else:
            for i in range(bisect_left(high, sy), bisect_right(low, ty)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sx), bisect_right(k, tx)):
                    if sy <= v[j][0] <= ty:
                        a.append(v[j][2])
        
        if a:
            a.sort()
            A.extend(a)
        A.append('')

    print('\n'.join(map(str, A)))

main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
 
i_f = sys.stdin
 
n = int(i_f.readline())
 
T = []
 
for i in range(n):
    x, y = map(int, i_f.readline().split())
    T.append([i, x, y, None, None])
 
def make2DTree(l, r, depth):
    if l >= r:
        return None
 
    mid = (l + r) // 2
 
    if depth % 2 == 0:
        T[l:r] = sorted(T[l:r], key=lambda n: n[1])
    else:
        T[l:r] = sorted(T[l:r], key=lambda n: n[2])
 
    T[mid][3] = make2DTree(l, mid, depth + 1)
    T[mid][4] = make2DTree(mid + 1, r, depth + 1)
 
    return mid
 
 
make2DTree(0, n, 0)
 
Ans = []
 
def range_search(sx, tx, sy, yx):
    ans = []
     
    def _find(v, sx, tx, sy, ty, depth):
        node = T[v]
        x = node[1]
        y = node[2]
 
        if sx <= x <= tx and sy <= y <= ty:
            ans.append(node[0])
 
        if depth % 2 == 0:
            if node[3] != None and sx <= x:
                _find(node[3], sx, tx, sy, ty, depth + 1)
            if node[4] and x <= tx:
                _find(node[4], sx, tx, sy, ty, depth + 1)
        else:
            if node[3] != None and sy <= y:
                _find(node[3], sx, tx, sy, ty, depth + 1)
            if node[4] and y <= ty:
                _find(node[4], sx, tx, sy, ty, depth + 1)
 
    _find(v, sx, tx, sy, ty, 0)
     
    if ans:
        ans.sort()
        Ans.extend(ans)
    Ans.append('')
 
 
q = int(i_f.readline())
 
v = n // 2
 
for l in i_f:
    sx, tx, sy, ty = map(int, l.split())
    range_search(sx, tx, sy, ty)
 
print('\n'.join(map(str, Ans)))

Fixed submission:
import sys, math
from operator import itemgetter
from bisect import bisect_left, bisect_right

f_i = sys.stdin

def main():
    n = int(f_i.readline())
    
    lx = []
    ly = []
    li = []
    for i in range(n):
        x, y = map(int, f_i.readline().split())
        lx.append(x)
        ly.append(y)
        li.append(i)

    x_width = max(lx) - min(lx)
    y_width = max(ly) - min(ly)
    if x_width > y_width:
        P = list(zip(lx, ly, li))
    else:
        P = list(zip(ly, lx, li))
    P.sort()

    interval = int(math.sqrt(n))

    low = [v1 for v1, v2, i in P[::interval]]
    high = [v1 for v1, v2, i in P[interval - 1::interval]] + [float('inf')]

    S = []
    v2_sec_list = []
    for i in range(0, n, interval):
        si = P[i:i + interval]
        si.sort(key=itemgetter(1))
        v2_s = [p[1] for p in si]
        v2_sec_list.append(v2_s)
        S.append(si)

    A = []

    q = f_i.readline()

    for l in f_i:
        sx, tx, sy, ty = map(int, l.split())
        a = []
        if x_width > y_width:
            for i in range(bisect_left(high, sx), bisect_right(low, tx)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sy), bisect_right(k, ty)):
                    if sx <= v[j][0] <= tx:
                        a.append(v[j][2])
        else:
            for i in range(bisect_left(high, sy), bisect_right(low, ty)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sx), bisect_right(k, tx)):
                    if sy <= v[j][0] <= ty:
                        a.append(v[j][2])
        
        if a:
            a.sort()
            A.extend(a)
        A.append('')

    print('\n'.join(map(str, A)))

main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys

i_f = sys.stdin

n = int(i_f.readline())

T = []
for i in range(n):
    x, y = map(int, i_f.readline().split())
    # [3] is left and [4] is right node.
    T.append([i, x, y, None, None])

def make2DTree(l, r, depth):
    if l >= r:
        return None

    mid = (l + r) // 2

    if depth % 2 == 0:
        T[l:r] = sorted(T[l:r], key=lambda n: n[1])
    else:
        T[l:r] = sorted(T[l:r], key=lambda n: n[2])

    T[mid][3] = make2DTree(l, mid, depth + 1)
    T[mid][4] = make2DTree(mid + 1, r, depth + 1)

    return T[mid]


make2DTree(0, n, 0)

root_node = T[n // 2]

Ans = []

def range_search(sx, tx, sy, yx):
    ans = []
    
    def _find(node, sx, tx, sy, ty, depth):
        x = node[1]
        y = node[2]

        if sx <= x <= tx and sy <= y <= ty:
            ans.append(node[0])

        if depth % 2 == 0:
            if node[3] != None and sx <= x:
                _find(node[3], sx, tx, sy, ty, depth + 1)
            if node[4] and x <= tx:
                _find(node[4], sx, tx, sy, ty, depth + 1)
        else:
            if node[3] != None and sy <= y:
                _find(node[3], sx, tx, sy, ty, depth + 1)
            if node[4] and y <= ty:
                _find(node[4], sx, tx, sy, ty, depth + 1)

    _find(root_node, sx, tx, sy, ty, 0)

    if ans:
        ans.sort()
        Ans.extend(ans)
    Ans.append('')


q = int(i_f.readline())


for l in i_f:
    sx, tx, sy, ty = map(int, l.split())
    range_search(sx, tx, sy, ty)

print('\n'.join(map(str, Ans)))

Fixed submission:
import sys, math
from operator import itemgetter
from bisect import bisect_left, bisect_right

f_i = sys.stdin

def main():
    n = int(f_i.readline())
    
    lx = []
    ly = []
    li = []
    for i in range(n):
        x, y = map(int, f_i.readline().split())
        lx.append(x)
        ly.append(y)
        li.append(i)

    x_width = max(lx) - min(lx)
    y_width = max(ly) - min(ly)
    if x_width > y_width:
        P = list(zip(lx, ly, li))
    else:
        P = list(zip(ly, lx, li))
    P.sort()

    interval = int(math.sqrt(n))

    low = [v1 for v1, v2, i in P[::interval]]
    high = [v1 for v1, v2, i in P[interval - 1::interval]] + [float('inf')]

    S = []
    v2_sec_list = []
    for i in range(0, n, interval):
        si = P[i:i + interval]
        si.sort(key=itemgetter(1))
        v2_s = [p[1] for p in si]
        v2_sec_list.append(v2_s)
        S.append(si)

    A = []

    q = f_i.readline()

    for l in f_i:
        sx, tx, sy, ty = map(int, l.split())
        a = []
        if x_width > y_width:
            for i in range(bisect_left(high, sx), bisect_right(low, tx)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sy), bisect_right(k, ty)):
                    if sx <= v[j][0] <= tx:
                        a.append(v[j][2])
        else:
            for i in range(bisect_left(high, sy), bisect_right(low, ty)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sx), bisect_right(k, tx)):
                    if sy <= v[j][0] <= ty:
                        a.append(v[j][2])
        
        if a:
            a.sort()
            A.extend(a)
        A.append('')

    print('\n'.join(map(str, A)))

main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys

i_f = sys.stdin

n = int(i_f.readline())

T = []
for i in range(n):
    x, y = map(int, i_f.readline().split())
    # [3] is left and [4] is right node.
    T.append([i, x, y, None, None])

def make2DTree(l, r, depth):
    if l >= r:
        return None

    mid = (l + r) // 2

    if depth % 2 == 0:
        T[l:r] = sorted(T[l:r], key=lambda n: n[1])
    else:
        T[l:r] = sorted(T[l:r], key=lambda n: n[2])

    T[mid][3] = make2DTree(l, mid, depth + 1)
    T[mid][4] = make2DTree(mid + 1, r, depth + 1)

    return T[mid]


make2DTree(0, n, 0)

root_node = T[n // 2]

Ans = []

def range_search(sx, tx, sy, yx):
    ans = []
    
    def _find(node, sx, tx, sy, ty, depth):
        x = node[1]
        y = node[2]

        if sx <= x <= tx and sy <= y <= ty:
            ans.append(node[0])

        if depth % 2 == 0:
            if node[3] and sx <= x:
                _find(node[3], sx, tx, sy, ty, depth + 1)
            if node[4] and x <= tx:
                _find(node[4], sx, tx, sy, ty, depth + 1)
        else:
            if node[3] and sy <= y:
                _find(node[3], sx, tx, sy, ty, depth + 1)
            if node[4] and y <= ty:
                _find(node[4], sx, tx, sy, ty, depth + 1)

    _find(root_node, sx, tx, sy, ty, 0)

    if ans:
        ans.sort()
        Ans.extend(ans)
    Ans.append('')


q = int(i_f.readline())


for l in i_f:
    sx, tx, sy, ty = map(int, l.split())
    range_search(sx, tx, sy, ty)

print('\n'.join(map(str, Ans)))

Fixed submission:
import sys, math
from operator import itemgetter
from bisect import bisect_left, bisect_right

f_i = sys.stdin

def main():
    n = int(f_i.readline())
    
    lx = []
    ly = []
    li = []
    for i in range(n):
        x, y = map(int, f_i.readline().split())
        lx.append(x)
        ly.append(y)
        li.append(i)

    x_width = max(lx) - min(lx)
    y_width = max(ly) - min(ly)
    if x_width > y_width:
        P = list(zip(lx, ly, li))
    else:
        P = list(zip(ly, lx, li))
    P.sort()

    interval = int(math.sqrt(n))

    low = [v1 for v1, v2, i in P[::interval]]
    high = [v1 for v1, v2, i in P[interval - 1::interval]] + [float('inf')]

    S = []
    v2_sec_list = []
    for i in range(0, n, interval):
        si = P[i:i + interval]
        si.sort(key=itemgetter(1))
        v2_s = [p[1] for p in si]
        v2_sec_list.append(v2_s)
        S.append(si)

    A = []

    q = f_i.readline()

    for l in f_i:
        sx, tx, sy, ty = map(int, l.split())
        a = []
        if x_width > y_width:
            for i in range(bisect_left(high, sx), bisect_right(low, tx)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sy), bisect_right(k, ty)):
                    if sx <= v[j][0] <= tx:
                        a.append(v[j][2])
        else:
            for i in range(bisect_left(high, sy), bisect_right(low, ty)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sx), bisect_right(k, tx)):
                    if sy <= v[j][0] <= ty:
                        a.append(v[j][2])
        
        if a:
            a.sort()
            A.extend(a)
        A.append('')

    print('\n'.join(map(str, A)))

main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys

i_f = sys.stdin

n = int(i_f.readline())

T = []
for i in range(n):
    x, y = map(int, i_f.readline().split())
    # [3] is left and [4] is right node.
    T.append([i, x, y, None, None])

def make2DTree(l, r, depth):
    if l >= r:
        return None

    mid = (l + r) // 2

    if depth % 2 == 0:
        t_lr = T[l:r]
        t_lr.sort(key=lambda n: n[1])
        T[l:r] = t_lr
    else:
        t_lr = T[l:r]
        t_lr.sort(key=lambda n: n[2])
        T[l:r] = t_lr

    T[mid][3] = make2DTree(l, mid, depth + 1)
    T[mid][4] = make2DTree(mid + 1, r, depth + 1)

    return T[mid]


make2DTree(0, n, 0)

root_node = T[n // 2]

Ans = []

def range_search(sx, tx, sy, yx):
    ans = []
    
    def _find(node, sx, tx, sy, ty, depth):
        x = node[1]
        y = node[2]

        if sx <= x <= tx and sy <= y <= ty:
            ans.append(node[0])

        if depth % 2 == 0:
            if node[3] and sx <= x:
                _find(node[3], sx, tx, sy, ty, depth + 1)
            if node[4] and x <= tx:
                _find(node[4], sx, tx, sy, ty, depth + 1)
        else:
            if node[3] and sy <= y:
                _find(node[3], sx, tx, sy, ty, depth + 1)
            if node[4] and y <= ty:
                _find(node[4], sx, tx, sy, ty, depth + 1)

    _find(root_node, sx, tx, sy, ty, 0)

    if ans:
        ans.sort()
        Ans.extend(ans)
    Ans.append('')


q = int(i_f.readline())


for l in i_f:
    sx, tx, sy, ty = map(int, l.split())
    range_search(sx, tx, sy, ty)

print('\n'.join(map(str, Ans)))

Fixed submission:
import sys, math
from operator import itemgetter
from bisect import bisect_left, bisect_right

f_i = sys.stdin

def main():
    n = int(f_i.readline())
    
    lx = []
    ly = []
    li = []
    for i in range(n):
        x, y = map(int, f_i.readline().split())
        lx.append(x)
        ly.append(y)
        li.append(i)

    x_width = max(lx) - min(lx)
    y_width = max(ly) - min(ly)
    if x_width > y_width:
        P = list(zip(lx, ly, li))
    else:
        P = list(zip(ly, lx, li))
    P.sort()

    interval = int(math.sqrt(n))

    low = [v1 for v1, v2, i in P[::interval]]
    high = [v1 for v1, v2, i in P[interval - 1::interval]] + [float('inf')]

    S = []
    v2_sec_list = []
    for i in range(0, n, interval):
        si = P[i:i + interval]
        si.sort(key=itemgetter(1))
        v2_s = [p[1] for p in si]
        v2_sec_list.append(v2_s)
        S.append(si)

    A = []

    q = f_i.readline()

    for l in f_i:
        sx, tx, sy, ty = map(int, l.split())
        a = []
        if x_width > y_width:
            for i in range(bisect_left(high, sx), bisect_right(low, tx)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sy), bisect_right(k, ty)):
                    if sx <= v[j][0] <= tx:
                        a.append(v[j][2])
        else:
            for i in range(bisect_left(high, sy), bisect_right(low, ty)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sx), bisect_right(k, tx)):
                    if sy <= v[j][0] <= ty:
                        a.append(v[j][2])
        
        if a:
            a.sort()
            A.extend(a)
        A.append('')

    print('\n'.join(map(str, A)))

main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys

i_f = sys.stdin

n = int(i_f.readline())

T = []
for i in range(n):
    x, y = map(int, i_f.readline().split())
    # [2] is input number.
    # [3] is left node, and [4] is right node.
    T.append([x, y, i, None, None])

def make2DTree(l, r, depth):
    if not l < r:
        return None

    mid = (l + r) // 2

    axis = depth % 2

    t_lr = T[l:r]
    t_lr.sort(key=lambda n: n[axis])
    T[l:r] = t_lr

    T[mid][3] = make2DTree(l, mid, depth + 1)
    T[mid][4] = make2DTree(mid + 1, r, depth + 1)

    return T[mid]


make2DTree(0, n, 0)

root_node = T[n // 2]

Ans = []

def range_search(sx, tx, sy, yx):
    ans = []
    
    def _find(node, sx, tx, sy, ty, depth):
        x = node[0]
        y = node[1]

        if sx <= x <= tx and sy <= y <= ty:
            ans.append(node[2])

        if depth % 2 == 0:
            if node[3] and sx <= x:
                _find(node[3], sx, tx, sy, ty, depth + 1)
            if node[4] and x <= tx:
                _find(node[4], sx, tx, sy, ty, depth + 1)
        else:
            if node[3] and sy <= y:
                _find(node[3], sx, tx, sy, ty, depth + 1)
            if node[4] and y <= ty:
                _find(node[4], sx, tx, sy, ty, depth + 1)

    _find(root_node, sx, tx, sy, ty, 0)

    if ans:
        ans.sort()
        Ans.extend(ans)
    Ans.append('')


q = int(i_f.readline())


for l in i_f:
    sx, tx, sy, ty = map(int, l.split())
    range_search(sx, tx, sy, ty)

print('\n'.join(map(str, Ans)))

Fixed submission:
import sys, math
from operator import itemgetter
from bisect import bisect_left, bisect_right

f_i = sys.stdin

def main():
    n = int(f_i.readline())
    
    lx = []
    ly = []
    li = []
    for i in range(n):
        x, y = map(int, f_i.readline().split())
        lx.append(x)
        ly.append(y)
        li.append(i)

    x_width = max(lx) - min(lx)
    y_width = max(ly) - min(ly)
    if x_width > y_width:
        P = list(zip(lx, ly, li))
    else:
        P = list(zip(ly, lx, li))
    P.sort()

    interval = int(math.sqrt(n))

    low = [v1 for v1, v2, i in P[::interval]]
    high = [v1 for v1, v2, i in P[interval - 1::interval]] + [float('inf')]

    S = []
    v2_sec_list = []
    for i in range(0, n, interval):
        si = P[i:i + interval]
        si.sort(key=itemgetter(1))
        v2_s = [p[1] for p in si]
        v2_sec_list.append(v2_s)
        S.append(si)

    A = []

    q = f_i.readline()

    for l in f_i:
        sx, tx, sy, ty = map(int, l.split())
        a = []
        if x_width > y_width:
            for i in range(bisect_left(high, sx), bisect_right(low, tx)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sy), bisect_right(k, ty)):
                    if sx <= v[j][0] <= tx:
                        a.append(v[j][2])
        else:
            for i in range(bisect_left(high, sy), bisect_right(low, ty)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sx), bisect_right(k, tx)):
                    if sy <= v[j][0] <= ty:
                        a.append(v[j][2])
        
        if a:
            a.sort()
            A.extend(a)
        A.append('')

    print('\n'.join(map(str, A)))

main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys

i_f = sys.stdin

n = int(i_f.readline())

T = []
for i in range(n):
    x, y = map(int, i_f.readline().split())
    # [0] is input number.
    # [3] is left node, and [4] is right node.
    T.append([i, x, y, None, None])

def partition(A, l, r, key):
    x = A[r][key]
    i = l - 1
    for j in range(l, r):
        if A[j][key] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[r] = A[r], A[i + 1]
    return i + 1

def median_divide(A, l, r, mid, key):
    if r > l:
        i = partition(A, l, r, key)
        if mid < i:
            median_divide(A, l, i - 1, mid, key)
        else:
            median_divide(A, i + 1, r, mid, key)


def make2DTree(l, r, depth):
    if l == r:
        return None

    mid = (l + r) // 2

    if depth % 2 == 0:
        median_divide(T, l, r - 1, mid, 1)
    else:
        t_lr = T[l:r]
        median_divide(T, l, r - 1, mid, 2)

    T[mid][3] = make2DTree(l, mid, depth + 1)
    T[mid][4] = make2DTree(mid + 1, r, depth + 1)

    return T[mid]


make2DTree(0, n, 0)

root_node = T[n // 2]

Ans = []

def range_search(sx, tx, sy, yx):
    ans = []
    
    def _find(node, sx, tx, sy, ty, depth):
        x = node[1]
        y = node[2]

        if sx <= x <= tx and sy <= y <= ty:
            ans.append(node[0])

        if depth % 2 == 0:
            if node[3] and sx <= x:
                _find(node[3], sx, tx, sy, ty, depth + 1)
            if node[4] and x <= tx:
                _find(node[4], sx, tx, sy, ty, depth + 1)
        else:
            if node[3] and sy <= y:
                _find(node[3], sx, tx, sy, ty, depth + 1)
            if node[4] and y <= ty:
                _find(node[4], sx, tx, sy, ty, depth + 1)

    _find(root_node, sx, tx, sy, ty, 0)

    if ans:
        ans.sort()
        Ans.extend(ans)
    Ans.append('')


q = int(i_f.readline())


for l in i_f:
    sx, tx, sy, ty = map(int, l.split())
    range_search(sx, tx, sy, ty)

print('\n'.join(map(str, Ans)))

Fixed submission:
import sys, math
from operator import itemgetter
from bisect import bisect_left, bisect_right

f_i = sys.stdin

def main():
    n = int(f_i.readline())
    
    lx = []
    ly = []
    li = []
    for i in range(n):
        x, y = map(int, f_i.readline().split())
        lx.append(x)
        ly.append(y)
        li.append(i)

    x_width = max(lx) - min(lx)
    y_width = max(ly) - min(ly)
    if x_width > y_width:
        P = list(zip(lx, ly, li))
    else:
        P = list(zip(ly, lx, li))
    P.sort()

    interval = int(math.sqrt(n))

    low = [v1 for v1, v2, i in P[::interval]]
    high = [v1 for v1, v2, i in P[interval - 1::interval]] + [float('inf')]

    S = []
    v2_sec_list = []
    for i in range(0, n, interval):
        si = P[i:i + interval]
        si.sort(key=itemgetter(1))
        v2_s = [p[1] for p in si]
        v2_sec_list.append(v2_s)
        S.append(si)

    A = []

    q = f_i.readline()

    for l in f_i:
        sx, tx, sy, ty = map(int, l.split())
        a = []
        if x_width > y_width:
            for i in range(bisect_left(high, sx), bisect_right(low, tx)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sy), bisect_right(k, ty)):
                    if sx <= v[j][0] <= tx:
                        a.append(v[j][2])
        else:
            for i in range(bisect_left(high, sy), bisect_right(low, ty)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sx), bisect_right(k, tx)):
                    if sy <= v[j][0] <= ty:
                        a.append(v[j][2])
        
        if a:
            a.sort()
            A.extend(a)
        A.append('')

    print('\n'.join(map(str, A)))

main()

Buggy python submission (verdict: Runtime Error):
import sys

i_f = sys.stdin

n = int(i_f.readline())

T = []
for i in range(n):
    x, y = map(int, i_f.readline().split())
    # [0] is input number.
    # [3] is left node, and [4] is right node.
    T.append([i, x, y, None, None])

def partition(A, l, r, key):
    x = A[r][key]
    i = l - 1
    for j in range(l, r):
        if A[j][key] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[r] = A[r], A[i + 1]
    return i + 1

def make2DTree(l, r, depth):
    if l == r:
        return None

    if depth % 2 == 0:
        separator = partition(T, l, r - 1, 1)
    else:
        separator = partition(T, l, r - 1, 2)

    T[separator][3] = make2DTree(l, separator, depth + 1)
    T[separator][4] = make2DTree(separator + 1, r, depth + 1)

    return T[separator]


root_node = make2DTree(0, n, 0)

Ans = []

def range_search(sx, tx, sy, yx):
    ans = []
    
    def _find(node, sx, tx, sy, ty, depth):
        x = node[1]
        y = node[2]

        if sx <= x <= tx and sy <= y <= ty:
            ans.append(node[0])

        if depth % 2 == 0:
            if node[3] and sx <= x:
                _find(node[3], sx, tx, sy, ty, depth + 1)
            if node[4] and x <= tx:
                _find(node[4], sx, tx, sy, ty, depth + 1)
        else:
            if node[3] and sy <= y:
                _find(node[3], sx, tx, sy, ty, depth + 1)
            if node[4] and y <= ty:
                _find(node[4], sx, tx, sy, ty, depth + 1)

    _find(root_node, sx, tx, sy, ty, 0)

    if ans:
        ans.sort()
        Ans.extend(ans)
    Ans.append('')


q = int(i_f.readline())


for l in i_f:
    sx, tx, sy, ty = map(int, l.split())
    range_search(sx, tx, sy, ty)

print('\n'.join(map(str, Ans)))

Fixed submission:
import sys, math
from operator import itemgetter
from bisect import bisect_left, bisect_right

f_i = sys.stdin

def main():
    n = int(f_i.readline())
    
    lx = []
    ly = []
    li = []
    for i in range(n):
        x, y = map(int, f_i.readline().split())
        lx.append(x)
        ly.append(y)
        li.append(i)

    x_width = max(lx) - min(lx)
    y_width = max(ly) - min(ly)
    if x_width > y_width:
        P = list(zip(lx, ly, li))
    else:
        P = list(zip(ly, lx, li))
    P.sort()

    interval = int(math.sqrt(n))

    low = [v1 for v1, v2, i in P[::interval]]
    high = [v1 for v1, v2, i in P[interval - 1::interval]] + [float('inf')]

    S = []
    v2_sec_list = []
    for i in range(0, n, interval):
        si = P[i:i + interval]
        si.sort(key=itemgetter(1))
        v2_s = [p[1] for p in si]
        v2_sec_list.append(v2_s)
        S.append(si)

    A = []

    q = f_i.readline()

    for l in f_i:
        sx, tx, sy, ty = map(int, l.split())
        a = []
        if x_width > y_width:
            for i in range(bisect_left(high, sx), bisect_right(low, tx)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sy), bisect_right(k, ty)):
                    if sx <= v[j][0] <= tx:
                        a.append(v[j][2])
        else:
            for i in range(bisect_left(high, sy), bisect_right(low, ty)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sx), bisect_right(k, tx)):
                    if sy <= v[j][0] <= ty:
                        a.append(v[j][2])
        
        if a:
            a.sort()
            A.extend(a)
        A.append('')

    print('\n'.join(map(str, A)))

main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys

i_f = sys.stdin

n = int(i_f.readline())

T = []
for i in range(n):
    x, y = map(int, i_f.readline().split())
    # [0] is input number.
    # [3] is left node, and [4] is right node.
    T.append([i, x, y, None, None])

def partition(A, first, end, key):
    mid = (first + end) // 2
    mid_node = A[mid]
    v = mid_node[key]
    former = []
    latter = []
    for node in A[first:mid]:
        if node[key] <= v:
            former.append(node)
        else:
            latter.append(node)
    for node in A[mid+1:end]:
        if node[key] <= v:
            former.append(node)
        else:
            latter.append(node)
    A[first:end] = former + [mid_node] + latter
    return first + len(former)

def make2DTree(l, r, depth):
    if l == r:
        return None

    if depth % 2 == 0:
        separator = partition(T, l, r, 1)
    else:
        separator = partition(T, l, r, 2)

    T[separator][3] = make2DTree(l, separator, depth + 1)
    T[separator][4] = make2DTree(separator + 1, r, depth + 1)

    return T[separator]


root_node = make2DTree(0, n, 0)

Ans = []

def range_search(sx, tx, sy, yx):
    ans = []
    
    def _find(node, sx, tx, sy, ty, depth):
        x = node[1]
        y = node[2]

        if sx <= x <= tx and sy <= y <= ty:
            ans.append(node[0])

        if depth % 2 == 0:
            if node[3] and sx <= x:
                _find(node[3], sx, tx, sy, ty, depth + 1)
            if node[4] and x <= tx:
                _find(node[4], sx, tx, sy, ty, depth + 1)
        else:
            if node[3] and sy <= y:
                _find(node[3], sx, tx, sy, ty, depth + 1)
            if node[4] and y <= ty:
                _find(node[4], sx, tx, sy, ty, depth + 1)

    _find(root_node, sx, tx, sy, ty, 0)

    if ans:
        ans.sort()
        Ans.extend(ans)
    Ans.append('')


q = int(i_f.readline())


for l in i_f:
    sx, tx, sy, ty = map(int, l.split())
    range_search(sx, tx, sy, ty)

print('\n'.join(map(str, Ans)))

Fixed submission:
import sys, math
from operator import itemgetter
from bisect import bisect_left, bisect_right

f_i = sys.stdin

def main():
    n = int(f_i.readline())
    
    lx = []
    ly = []
    li = []
    for i in range(n):
        x, y = map(int, f_i.readline().split())
        lx.append(x)
        ly.append(y)
        li.append(i)

    x_width = max(lx) - min(lx)
    y_width = max(ly) - min(ly)
    if x_width > y_width:
        P = list(zip(lx, ly, li))
    else:
        P = list(zip(ly, lx, li))
    P.sort()

    interval = int(math.sqrt(n))

    low = [v1 for v1, v2, i in P[::interval]]
    high = [v1 for v1, v2, i in P[interval - 1::interval]] + [float('inf')]

    S = []
    v2_sec_list = []
    for i in range(0, n, interval):
        si = P[i:i + interval]
        si.sort(key=itemgetter(1))
        v2_s = [p[1] for p in si]
        v2_sec_list.append(v2_s)
        S.append(si)

    A = []

    q = f_i.readline()

    for l in f_i:
        sx, tx, sy, ty = map(int, l.split())
        a = []
        if x_width > y_width:
            for i in range(bisect_left(high, sx), bisect_right(low, tx)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sy), bisect_right(k, ty)):
                    if sx <= v[j][0] <= tx:
                        a.append(v[j][2])
        else:
            for i in range(bisect_left(high, sy), bisect_right(low, ty)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sx), bisect_right(k, tx)):
                    if sy <= v[j][0] <= ty:
                        a.append(v[j][2])
        
        if a:
            a.sort()
            A.extend(a)
        A.append('')

    print('\n'.join(map(str, A)))

main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys

i_f = sys.stdin

n = int(i_f.readline())

T = []
for i in range(n):
    x, y = map(int, i_f.readline().split())
    # [0] is input number.
    # [3] is left node, and [4] is right node.
    T.append([i, x, y, None, None])

def partition(A, l, r, key):
    mid = (l + r) // 2
    last = r - 1
    mid_node = A[mid]
    last_node = A[last]
    A[mid] = last_node
    A[last] = mid_node
    v = mid_node[key]
    i = l - 1
    for j in range(l, last):
        if A[j][key] <= v:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[last] = A[last], A[i + 1]
    return i + 1

def make2DTree(l, r, depth):
    if l == r:
        return None

    if depth % 2 == 0:
        separator = partition(T, l, r, 1)
    else:
        separator = partition(T, l, r, 2)

    T[separator][3] = make2DTree(l, separator, depth + 1)
    T[separator][4] = make2DTree(separator + 1, r, depth + 1)

    return T[separator]


root_node = make2DTree(0, n, 0)

Ans = []

def range_search(sx, tx, sy, yx):
    ans = []
    
    def _find(node, sx, tx, sy, ty, depth):
        x = node[1]
        y = node[2]

        if sx <= x <= tx and sy <= y <= ty:
            ans.append(node[0])

        if depth % 2 == 0:
            if node[3] and sx <= x:
                _find(node[3], sx, tx, sy, ty, depth + 1)
            if node[4] and x <= tx:
                _find(node[4], sx, tx, sy, ty, depth + 1)
        else:
            if node[3] and sy <= y:
                _find(node[3], sx, tx, sy, ty, depth + 1)
            if node[4] and y <= ty:
                _find(node[4], sx, tx, sy, ty, depth + 1)

    _find(root_node, sx, tx, sy, ty, 0)

    if ans:
        ans.sort()
        Ans.extend(ans)
    Ans.append('')


q = int(i_f.readline())


for l in i_f:
    sx, tx, sy, ty = map(int, l.split())
    range_search(sx, tx, sy, ty)

print('\n'.join(map(str, Ans)))

Fixed submission:
import sys, math
from operator import itemgetter
from bisect import bisect_left, bisect_right

f_i = sys.stdin

def main():
    n = int(f_i.readline())
    
    lx = []
    ly = []
    li = []
    for i in range(n):
        x, y = map(int, f_i.readline().split())
        lx.append(x)
        ly.append(y)
        li.append(i)

    x_width = max(lx) - min(lx)
    y_width = max(ly) - min(ly)
    if x_width > y_width:
        P = list(zip(lx, ly, li))
    else:
        P = list(zip(ly, lx, li))
    P.sort()

    interval = int(math.sqrt(n))

    low = [v1 for v1, v2, i in P[::interval]]
    high = [v1 for v1, v2, i in P[interval - 1::interval]] + [float('inf')]

    S = []
    v2_sec_list = []
    for i in range(0, n, interval):
        si = P[i:i + interval]
        si.sort(key=itemgetter(1))
        v2_s = [p[1] for p in si]
        v2_sec_list.append(v2_s)
        S.append(si)

    A = []

    q = f_i.readline()

    for l in f_i:
        sx, tx, sy, ty = map(int, l.split())
        a = []
        if x_width > y_width:
            for i in range(bisect_left(high, sx), bisect_right(low, tx)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sy), bisect_right(k, ty)):
                    if sx <= v[j][0] <= tx:
                        a.append(v[j][2])
        else:
            for i in range(bisect_left(high, sy), bisect_right(low, ty)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sx), bisect_right(k, tx)):
                    if sy <= v[j][0] <= ty:
                        a.append(v[j][2])
        
        if a:
            a.sort()
            A.extend(a)
        A.append('')

    print('\n'.join(map(str, A)))

main()

Buggy python submission (verdict: Time Limit Exceeded):
# Not using k-d tree.

import sys
 
i_f = sys.stdin
 
n = int(i_f.readline())

Px = []
Py = []
for i in range(n):
    x, y = map(int, i_f.readline().split())
    Px.append([x, y, i])
    Py.append([y, x, i])

Px.sort()
Py.sort()

q = int(i_f.readline())

A = []

import bisect

for l in i_f:
    a = []
    
    sx, tx, sy, ty = map(int, l.split())
    
    x_low = bisect.bisect_left(Px, [sx, sy, 0])
    x_high = bisect.bisect_right(Px, [tx, ty, n], lo=x_low)
    y_low = bisect.bisect_left(Py, [sy, sx, 0])
    y_high = bisect.bisect_left(Py, [ty, tx, n], lo=y_low)
    
    x_width = x_high - x_low
    y_width = y_high - y_low

    if x_width < y_width:
        for p in Px[x_low:x_high]:
            if sy <= p[1] <= ty:
                a.append(p[2])
    else:
        for p in Py[y_low:y_high]:
            if sx <= p[1] <= tx:
                a.append(p[2])

    a.sort()
    if a:
        A.extend(a)
    A.append('')

print('\n'.join(map(str, A)))

Fixed submission:
import sys, math
from operator import itemgetter
from bisect import bisect_left, bisect_right

f_i = sys.stdin

def main():
    n = int(f_i.readline())
    
    lx = []
    ly = []
    li = []
    for i in range(n):
        x, y = map(int, f_i.readline().split())
        lx.append(x)
        ly.append(y)
        li.append(i)

    x_width = max(lx) - min(lx)
    y_width = max(ly) - min(ly)
    if x_width > y_width:
        P = list(zip(lx, ly, li))
    else:
        P = list(zip(ly, lx, li))
    P.sort()

    interval = int(math.sqrt(n))

    low = [v1 for v1, v2, i in P[::interval]]
    high = [v1 for v1, v2, i in P[interval - 1::interval]] + [float('inf')]

    S = []
    v2_sec_list = []
    for i in range(0, n, interval):
        si = P[i:i + interval]
        si.sort(key=itemgetter(1))
        v2_s = [p[1] for p in si]
        v2_sec_list.append(v2_s)
        S.append(si)

    A = []

    q = f_i.readline()

    for l in f_i:
        sx, tx, sy, ty = map(int, l.split())
        a = []
        if x_width > y_width:
            for i in range(bisect_left(high, sx), bisect_right(low, tx)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sy), bisect_right(k, ty)):
                    if sx <= v[j][0] <= tx:
                        a.append(v[j][2])
        else:
            for i in range(bisect_left(high, sy), bisect_right(low, ty)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sx), bisect_right(k, tx)):
                    if sy <= v[j][0] <= ty:
                        a.append(v[j][2])
        
        if a:
            a.sort()
            A.extend(a)
        A.append('')

    print('\n'.join(map(str, A)))

main()

Buggy python submission (verdict: Time Limit Exceeded):
# Not using k-d tree.

import sys
 
i_f = sys.stdin
 
n = int(i_f.readline())

Px = []
Py = []
for i in range(n):
    x, y = map(int, i_f.readline().split())
    Px.append([x, y, i])
    Py.append([y, x, i])

Px.sort()
Py.sort()

q = int(i_f.readline())

A = []

import bisect

for l in i_f:
    a = []
    
    sx, tx, sy, ty = map(int, l.split())
    
    x_low = bisect.bisect_left(Px, [sx, sy, 0])
    x_high = bisect.bisect_right(Px, [tx, ty, n], lo=x_low)
    y_low = bisect.bisect_left(Py, [sy, sx, 0])
    y_high = bisect.bisect_left(Py, [ty, tx, n], lo=y_low)
    
    x_width = x_high - x_low
    y_width = y_high - y_low

    if x_width < y_width:
        for p in Px[x_low:x_high]:
            if sy <= p[1] <= ty:
                a.append(p[2])
    else:
        for p in Py[y_low:y_high]:
            if sx <= p[1] <= tx:
                a.append(p[2])

    a.sort()
    if a:
        A.extend(a)
    A.append('')

print('\n'.join(map(str, A)))

Fixed submission:
import sys, math
from operator import itemgetter
from bisect import bisect_left, bisect_right

f_i = sys.stdin

def main():
    n = int(f_i.readline())
    
    lx = []
    ly = []
    li = []
    for i in range(n):
        x, y = map(int, f_i.readline().split())
        lx.append(x)
        ly.append(y)
        li.append(i)

    x_width = max(lx) - min(lx)
    y_width = max(ly) - min(ly)
    if x_width > y_width:
        P = list(zip(lx, ly, li))
    else:
        P = list(zip(ly, lx, li))
    P.sort()

    interval = int(math.sqrt(n))

    low = [v1 for v1, v2, i in P[::interval]]
    high = [v1 for v1, v2, i in P[interval - 1::interval]] + [float('inf')]

    S = []
    v2_sec_list = []
    for i in range(0, n, interval):
        si = P[i:i + interval]
        si.sort(key=itemgetter(1))
        v2_s = [p[1] for p in si]
        v2_sec_list.append(v2_s)
        S.append(si)

    A = []

    q = f_i.readline()

    for l in f_i:
        sx, tx, sy, ty = map(int, l.split())
        a = []
        if x_width > y_width:
            for i in range(bisect_left(high, sx), bisect_right(low, tx)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sy), bisect_right(k, ty)):
                    if sx <= v[j][0] <= tx:
                        a.append(v[j][2])
        else:
            for i in range(bisect_left(high, sy), bisect_right(low, ty)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sx), bisect_right(k, tx)):
                    if sy <= v[j][0] <= ty:
                        a.append(v[j][2])
        
        if a:
            a.sort()
            A.extend(a)
        A.append('')

    print('\n'.join(map(str, A)))

main()

Buggy python submission (verdict: Time Limit Exceeded):
# Not using k-d tree.

import sys
import bisect
 
i_f = sys.stdin
 
n = int(i_f.readline())

Px = []
Py = []
for i in range(n):
    x, y = map(int, i_f.readline().split())
    Px.append([x, y, i])
    Py.append([y, x, i])

Px.sort()
Py.sort()

q = int(i_f.readline())

A = []

for l in i_f:
    sx, tx, sy, ty = map(int, l.split())
    
    x_low = bisect.bisect_left(Px, [sx, sy, 0])
    x_high = bisect.bisect_right(Px, [tx, ty, n], lo=x_low)
    y_low = bisect.bisect_left(Py, [sy, sx, 0])
    y_high = bisect.bisect_left(Py, [ty, tx, n], lo=y_low)
    
    x_width = x_high - x_low
    y_width = y_high - y_low

    a = []
    if x_width < y_width:
        for p in Px[x_low:x_high]:
            if sy <= p[1] <= ty:
                a.append(p[2])
    else:
        for p in Py[y_low:y_high]:
            if sx <= p[1] <= tx:
                a.append(p[2])

    a.sort()

    for i in a:
        print(i)
    print('')

Fixed submission:
import sys, math
from operator import itemgetter
from bisect import bisect_left, bisect_right

f_i = sys.stdin

def main():
    n = int(f_i.readline())
    
    lx = []
    ly = []
    li = []
    for i in range(n):
        x, y = map(int, f_i.readline().split())
        lx.append(x)
        ly.append(y)
        li.append(i)

    x_width = max(lx) - min(lx)
    y_width = max(ly) - min(ly)
    if x_width > y_width:
        P = list(zip(lx, ly, li))
    else:
        P = list(zip(ly, lx, li))
    P.sort()

    interval = int(math.sqrt(n))

    low = [v1 for v1, v2, i in P[::interval]]
    high = [v1 for v1, v2, i in P[interval - 1::interval]] + [float('inf')]

    S = []
    v2_sec_list = []
    for i in range(0, n, interval):
        si = P[i:i + interval]
        si.sort(key=itemgetter(1))
        v2_s = [p[1] for p in si]
        v2_sec_list.append(v2_s)
        S.append(si)

    A = []

    q = f_i.readline()

    for l in f_i:
        sx, tx, sy, ty = map(int, l.split())
        a = []
        if x_width > y_width:
            for i in range(bisect_left(high, sx), bisect_right(low, tx)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sy), bisect_right(k, ty)):
                    if sx <= v[j][0] <= tx:
                        a.append(v[j][2])
        else:
            for i in range(bisect_left(high, sy), bisect_right(low, ty)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sx), bisect_right(k, tx)):
                    if sy <= v[j][0] <= ty:
                        a.append(v[j][2])
        
        if a:
            a.sort()
            A.extend(a)
        A.append('')

    print('\n'.join(map(str, A)))

main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import bisect
 
i_f = sys.stdin
 
n = int(i_f.readline())

Px = []
Py = []
for i in range(n):
    x, y = map(int, i_f.readline().split())
    Px.append([x, y, i])
    Py.append([y, x, i])

Px.sort()
Py.sort()

q = int(i_f.readline())

A = []

for l in i_f:
    sx, tx, sy, ty = map(int, l.split())
    
    x_low = bisect.bisect_left(Px, [sx, sy, 0])
    x_high = bisect.bisect_right(Px, [tx, ty, n], lo=x_low)
    y_low = bisect.bisect_left(Py, [sy, sx, 0])
    y_high = bisect.bisect_left(Py, [ty, tx, n], lo=y_low)
    
    x_width = x_high - x_low
    y_width = y_high - y_low

    a = []
    if x_width < y_width:
        for p in Px[x_low:x_high]:
            if sy <= p[1] <= ty:
                a.append(p[2])
    else:
        for p in Py[y_low:y_high]:
            if sx <= p[1] <= tx:
                a.append(p[2])

    a.sort()
    a.append('')

    print(*a, sep='\n')

Fixed submission:
import sys, math
from operator import itemgetter
from bisect import bisect_left, bisect_right

f_i = sys.stdin

def main():
    n = int(f_i.readline())
    
    lx = []
    ly = []
    li = []
    for i in range(n):
        x, y = map(int, f_i.readline().split())
        lx.append(x)
        ly.append(y)
        li.append(i)

    x_width = max(lx) - min(lx)
    y_width = max(ly) - min(ly)
    if x_width > y_width:
        P = list(zip(lx, ly, li))
    else:
        P = list(zip(ly, lx, li))
    P.sort()

    interval = int(math.sqrt(n))

    low = [v1 for v1, v2, i in P[::interval]]
    high = [v1 for v1, v2, i in P[interval - 1::interval]] + [float('inf')]

    S = []
    v2_sec_list = []
    for i in range(0, n, interval):
        si = P[i:i + interval]
        si.sort(key=itemgetter(1))
        v2_s = [p[1] for p in si]
        v2_sec_list.append(v2_s)
        S.append(si)

    A = []

    q = f_i.readline()

    for l in f_i:
        sx, tx, sy, ty = map(int, l.split())
        a = []
        if x_width > y_width:
            for i in range(bisect_left(high, sx), bisect_right(low, tx)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sy), bisect_right(k, ty)):
                    if sx <= v[j][0] <= tx:
                        a.append(v[j][2])
        else:
            for i in range(bisect_left(high, sy), bisect_right(low, ty)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sx), bisect_right(k, tx)):
                    if sy <= v[j][0] <= ty:
                        a.append(v[j][2])
        
        if a:
            a.sort()
            A.extend(a)
        A.append('')

    print('\n'.join(map(str, A)))

main()

Buggy python submission (verdict: Time Limit Exceeded):
# Not using k-d tree.

import sys
import bisect

def main():
    i_f = sys.stdin
     
    n = int(i_f.readline())

    Px = []
    Py = []
    for i in range(n):
        x, y = map(int, i_f.readline().split())
        Px.append([x, y, i])
        Py.append([y, x, i])

    Px.sort()
    Py.sort()

    q = int(i_f.readline())

    A = []

    for l in i_f:
        sx, tx, sy, ty = map(int, l.split())
        
        x_low = bisect.bisect_left(Px, [sx, sy, 0])
        x_high = bisect.bisect_right(Px, [tx, ty, n], lo=x_low)
        y_low = bisect.bisect_left(Py, [sy, sx, 0])
        y_high = bisect.bisect_left(Py, [ty, tx, n], lo=y_low)
        
        x_width = x_high - x_low
        y_width = y_high - y_low

        a = []
        if x_width < y_width:
            for p in Px[x_low:x_high]:
                if sy <= p[1] <= ty:
                    a.append(p[2])
        else:
            for p in Py[y_low:y_high]:
                if sx <= p[1] <= tx:
                    a.append(p[2])

        if a:
            a.sort()
            A.extend(a)
        A.append('')

    print('\n'.join(map(str, A)))

main()

Fixed submission:
import sys, math
from operator import itemgetter
from bisect import bisect_left, bisect_right

f_i = sys.stdin

def main():
    n = int(f_i.readline())
    
    lx = []
    ly = []
    li = []
    for i in range(n):
        x, y = map(int, f_i.readline().split())
        lx.append(x)
        ly.append(y)
        li.append(i)

    x_width = max(lx) - min(lx)
    y_width = max(ly) - min(ly)
    if x_width > y_width:
        P = list(zip(lx, ly, li))
    else:
        P = list(zip(ly, lx, li))
    P.sort()

    interval = int(math.sqrt(n))

    low = [v1 for v1, v2, i in P[::interval]]
    high = [v1 for v1, v2, i in P[interval - 1::interval]] + [float('inf')]

    S = []
    v2_sec_list = []
    for i in range(0, n, interval):
        si = P[i:i + interval]
        si.sort(key=itemgetter(1))
        v2_s = [p[1] for p in si]
        v2_sec_list.append(v2_s)
        S.append(si)

    A = []

    q = f_i.readline()

    for l in f_i:
        sx, tx, sy, ty = map(int, l.split())
        a = []
        if x_width > y_width:
            for i in range(bisect_left(high, sx), bisect_right(low, tx)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sy), bisect_right(k, ty)):
                    if sx <= v[j][0] <= tx:
                        a.append(v[j][2])
        else:
            for i in range(bisect_left(high, sy), bisect_right(low, ty)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sx), bisect_right(k, tx)):
                    if sy <= v[j][0] <= ty:
                        a.append(v[j][2])
        
        if a:
            a.sort()
            A.extend(a)
        A.append('')

    print('\n'.join(map(str, A)))

main()

Buggy python submission (verdict: Time Limit Exceeded):
# Not using k-d tree.

import sys
import bisect


i_f = sys.stdin

n = int(i_f.readline())

P = [list(map(int, i_f.readline().split())) + [i] for i in range(n)]

P.sort()

q = int(i_f.readline())

A = []

for l in i_f:
    sx, tx, sy, ty = map(int, l.split())
    
    x_low = bisect.bisect_left(P, [sx, sy, 0])
    x_high = bisect.bisect_right(P, [tx, ty, n], lo=x_low)
    P_s = P[x_low:x_high]

    P_s.sort(key=lambda p: p[1])
    y_low = bisect.bisect_left(P_s, [sx, sy, 0])
    y_high = bisect.bisect_right(P_s, [tx, ty, n], lo=y_low)
    P_s = P_s[y_low:y_high]
    
    a = []
    for p in P_s:
        if sy <= p[1] <= ty:
            a.append(p[2])
    if a:
        a.sort()
        A.extend(a)
    A.append('')

print('\n'.join(map(str, A)))

Fixed submission:
import sys, math
from operator import itemgetter
from bisect import bisect_left, bisect_right

f_i = sys.stdin

def main():
    n = int(f_i.readline())
    
    lx = []
    ly = []
    li = []
    for i in range(n):
        x, y = map(int, f_i.readline().split())
        lx.append(x)
        ly.append(y)
        li.append(i)

    x_width = max(lx) - min(lx)
    y_width = max(ly) - min(ly)
    if x_width > y_width:
        P = list(zip(lx, ly, li))
    else:
        P = list(zip(ly, lx, li))
    P.sort()

    interval = int(math.sqrt(n))

    low = [v1 for v1, v2, i in P[::interval]]
    high = [v1 for v1, v2, i in P[interval - 1::interval]] + [float('inf')]

    S = []
    v2_sec_list = []
    for i in range(0, n, interval):
        si = P[i:i + interval]
        si.sort(key=itemgetter(1))
        v2_s = [p[1] for p in si]
        v2_sec_list.append(v2_s)
        S.append(si)

    A = []

    q = f_i.readline()

    for l in f_i:
        sx, tx, sy, ty = map(int, l.split())
        a = []
        if x_width > y_width:
            for i in range(bisect_left(high, sx), bisect_right(low, tx)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sy), bisect_right(k, ty)):
                    if sx <= v[j][0] <= tx:
                        a.append(v[j][2])
        else:
            for i in range(bisect_left(high, sy), bisect_right(low, ty)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sx), bisect_right(k, tx)):
                    if sy <= v[j][0] <= ty:
                        a.append(v[j][2])
        
        if a:
            a.sort()
            A.extend(a)
        A.append('')

    print('\n'.join(map(str, A)))

main()

Buggy python submission (verdict: Time Limit Exceeded):
# Not using k-d tree.

import sys, math
from operator import itemgetter
from bisect import bisect_left, bisect_right

f_i = sys.stdin

n = int(f_i.readline())
P = [tuple(map(int, f_i.readline().split())) + (i,) for i in range(n)]
P.sort()

interval = int(math.sqrt(len(P)))

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

S = []
yRanges = []
for i in range(0, len(P), interval):
    s = P[i:i + interval]
    s.sort(key=itemgetter(1))
    y_range = [p[1] for p in s]
    yRanges.append(y_range)
    S.append(s)

A = []

q = f_i.readline()

for l in f_i:
    sx, tx, sy, ty = map(int, l.split())
    a = []
    for i in range(bisect_left(high, sx), bisect_right(low, tx)):
        v = S[i]
        k = yRanges[i]
        for j in range(bisect_left(k, sy), bisect_right(k, ty)):
            if sx <= v[j][0] <= tx:
                a.append(v[j][2])
    
    if a:
        a.sort()
        A.extend(a)
    A.append('')

print('\n'.join(map(str, A)))

Fixed submission:
import sys, math
from operator import itemgetter
from bisect import bisect_left, bisect_right

f_i = sys.stdin

def main():
    n = int(f_i.readline())
    
    lx = []
    ly = []
    li = []
    for i in range(n):
        x, y = map(int, f_i.readline().split())
        lx.append(x)
        ly.append(y)
        li.append(i)

    x_width = max(lx) - min(lx)
    y_width = max(ly) - min(ly)
    if x_width > y_width:
        P = list(zip(lx, ly, li))
    else:
        P = list(zip(ly, lx, li))
    P.sort()

    interval = int(math.sqrt(n))

    low = [v1 for v1, v2, i in P[::interval]]
    high = [v1 for v1, v2, i in P[interval - 1::interval]] + [float('inf')]

    S = []
    v2_sec_list = []
    for i in range(0, n, interval):
        si = P[i:i + interval]
        si.sort(key=itemgetter(1))
        v2_s = [p[1] for p in si]
        v2_sec_list.append(v2_s)
        S.append(si)

    A = []

    q = f_i.readline()

    for l in f_i:
        sx, tx, sy, ty = map(int, l.split())
        a = []
        if x_width > y_width:
            for i in range(bisect_left(high, sx), bisect_right(low, tx)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sy), bisect_right(k, ty)):
                    if sx <= v[j][0] <= tx:
                        a.append(v[j][2])
        else:
            for i in range(bisect_left(high, sy), bisect_right(low, ty)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sx), bisect_right(k, tx)):
                    if sy <= v[j][0] <= ty:
                        a.append(v[j][2])
        
        if a:
            a.sort()
            A.extend(a)
        A.append('')

    print('\n'.join(map(str, A)))

main()

Buggy python submission (verdict: Time Limit Exceeded):
# Not using k-d tree.

import sys, math
from operator import itemgetter
from bisect import bisect_left, bisect_right

f_i = sys.stdin

n = int(f_i.readline())
P = [tuple(map(int, f_i.readline().split())) + (i,) for i in range(n)]
P.sort()

interval = int(math.sqrt(len(P)))

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

P = [sorted(P[i:i + interval], key=itemgetter(1)) for i in range(0, len(P), interval)]
P = [([y for x, y, i in p_b], p_b) for p_b in P]

A = []

q = f_i.readline()

for l in f_i:
    sx, tx, sy, ty = map(int, l.split())
    ret = []
    for i in range(bisect_left(high, sx), bisect_right(low, tx)):
        k, v = P[i]
        for j in range(bisect_left(k, sy), bisect_right(k, ty)):
            if sx <= v[j][0] <=tx:
                ret.append(v[j][2])
    if ret:
        ret.sort()
        A.extend(ret)
    A.append('')

print('\n'.join(map(str, A)))

Fixed submission:
import sys, math
from operator import itemgetter
from bisect import bisect_left, bisect_right

f_i = sys.stdin

def main():
    n = int(f_i.readline())
    
    lx = []
    ly = []
    li = []
    for i in range(n):
        x, y = map(int, f_i.readline().split())
        lx.append(x)
        ly.append(y)
        li.append(i)

    x_width = max(lx) - min(lx)
    y_width = max(ly) - min(ly)
    if x_width > y_width:
        P = list(zip(lx, ly, li))
    else:
        P = list(zip(ly, lx, li))
    P.sort()

    interval = int(math.sqrt(n))

    low = [v1 for v1, v2, i in P[::interval]]
    high = [v1 for v1, v2, i in P[interval - 1::interval]] + [float('inf')]

    S = []
    v2_sec_list = []
    for i in range(0, n, interval):
        si = P[i:i + interval]
        si.sort(key=itemgetter(1))
        v2_s = [p[1] for p in si]
        v2_sec_list.append(v2_s)
        S.append(si)

    A = []

    q = f_i.readline()

    for l in f_i:
        sx, tx, sy, ty = map(int, l.split())
        a = []
        if x_width > y_width:
            for i in range(bisect_left(high, sx), bisect_right(low, tx)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sy), bisect_right(k, ty)):
                    if sx <= v[j][0] <= tx:
                        a.append(v[j][2])
        else:
            for i in range(bisect_left(high, sy), bisect_right(low, ty)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sx), bisect_right(k, tx)):
                    if sy <= v[j][0] <= ty:
                        a.append(v[j][2])
        
        if a:
            a.sort()
            A.extend(a)
        A.append('')

    print('\n'.join(map(str, A)))

main()