Buggy python submission (verdict: Time Limit Exceeded):

import random


class Node:
    __slots__ = ('x', 'y', 'left', 'right', 'value')

    def __init__(self, x, y, value):
        self.x = x
        self.y = y
        self.value = value
        self.left = None
        self.right = None

    def __str__(self):
        return "({} [{},{}:{}] {})".format(self.left, self.x, self.y,
                                           self.value, self.right)


class KdTree:

    def __init__(self):
        self.root = None

    def add(self, x, y, v=None):
        def _add(node, level=0):
            if node is None:
                return Node(x, y, v)
            if level % 2 == 0:
                if node.x > x:
                    node.left = _add(node.left, level+1)
                else:
                    node.right = _add(node.right, level+1)
            else:
                if node.y > y:
                    node.left = _add(node.left, level+1)
                else:
                    node.right = _add(node.right, level+1)
            return node
        self.root = _add(self.root, 0)

    def range(self, x1, x2, y1, y2):
        def _range(node, level):
            if node is None:
                return
            if level % 2 == 0:
                if x2 < node.x:
                    yield from _range(node.left, level+1)
                elif x1 > node.x:
                    yield from _range(node.right, level+1)
                else:
                    if y1 <= node.y <= y2:
                        yield (node.x, node.y, node.value)
                    yield from _range(node.left, level+1)
                    yield from _range(node.right, level+1)
            else:
                if y2 < node.y:
                    yield from _range(node.left, level+1)
                elif y1 > node.y:
                    yield from _range(node.right, level+1)
                else:
                    if x1 <= node.x <= x2:
                        yield (node.x, node.y, node.value)
                    yield from _range(node.left, level+1)
                    yield from _range(node.right, level+1)

        assert x1 <= x2 and y1 <= y2
        yield from _range(self.root, 0)


def run():
    n = int(input())

    t = KdTree()
    ps = []
    for i in range(n):
        x, y = [int(j) for j in input().split()]
        ps.append((x, y, i))

    random.shuffle(ps)
    for x, y, i in ps:
        t.add(x, y, i)

    q = int(input())
    for _ in range(q):
        sx, tx, sy, ty = [int(j) for j in input().split()]
        vs = [v for x, y, v in t.range(sx, tx, sy, ty)]
        for v in sorted(vs):
            print(v)
        print()


if __name__ == '__main__':
    run()



Fixed submission:
#!/usr/bin/env pypy3
# DSL_2_C: Range Search(kD Tree)

from bisect import bisect_left, bisect_right
from collections import deque
from functools import lru_cache
from itertools import islice
from math import floor, log2, sqrt
from operator import itemgetter
from sys import stdin, stdout


def sort3(i, j, k):
    if i > j:
        if j > k:
            return (2, 1, 0)
        elif i > k:
            return (1, 2, 0)
        else:
            return (1, 0, 2)
    else:
        if i > k:
            return (2, 0, 1)
        elif j > k:
            return (0, 2, 1)
        else:
            return (0, 1, 2)


def partition(ps, lo, hi, dim):
    mid = (lo + hi) // 2
    ns = (lo, mid, hi)
    n0, n1, n2 = sort3(ps[lo][dim], ps[mid][dim], ps[hi][dim])
    ps[lo], ps[mid], ps[hi] = ps[ns[n1]], ps[ns[n0]], ps[ns[n2]]
    v = ps[lo][dim]
    i, j = lo, hi
    while True:
        i, j = i+1, j-1
        while ps[i][dim] < v:
            i += 1
        while ps[j][dim] > v:
            j -= 1
        if i >= j:
            break
        ps[i], ps[j] = ps[j], ps[i]
    ps[j], ps[lo] = ps[lo], ps[j]
    return j


def sort(ps, lo, hi, dim):
    for i, p in enumerate(sorted(ps[lo:hi+1], key=itemgetter(dim))):
        ps[lo+i] = p


def halve(ps, s, t, dim):
    mid = (s+t) // 2
    while t - s > 100:
        i = partition(ps, s, t, dim)
        if i > mid:
            t = i - 1
        elif i < mid:
            s = i + 1
        else:
            return mid

    sort(ps, s, t, dim)
    return mid


def build(ps, n, sz, _dim):
    q = deque([(0, n-1, 0)])
    while q:
        s, t, lv = q.popleft()
        dim, _ = _dim(lv)
        if t - s < sz:
            sort(ps, s, t, dim)
            continue
        mid = halve(ps, s, t, dim)
        if mid-1 > s:
            q.append((s, mid-1, lv+1))
        if t > mid+1:
            q.append((mid+1, t, lv+1))


def search(ps, vs, n, sz, _dim, s, t):
    q = deque([(0, n-1, 0)])
    ret = []
    while q:
        i, j, lv = q.popleft()
        dim, rdim = _dim(lv)
        sd, td, sr, tr = s[dim], t[dim], s[rdim], t[rdim]
        if j - i < sz:
            left = bisect_left(vs[dim], sd, i, j+1)
            right = bisect_right(vs[dim], td, i, j+1)
            ret.extend([p[2] for p in ps[left:right] if sr <= p[rdim] <= tr])
            continue

        mid = (i+j) // 2
        if td < ps[mid][dim]:
            q.append((i, mid-1, lv+1))
        elif sd > ps[mid][dim]:
            q.append((mid+1, j, lv+1))
        else:
            if sr <= ps[mid][rdim] <= tr:
                ret.append(ps[mid][2])
            q.append((i, mid-1, lv+1))
            q.append((mid+1, j, lv+1))

    ret.sort()
    return ret


def dimension(ps, n):
    @lru_cache(maxsize=n)
    def _dimension(lv):
        return pat[lv % len(pat)]

    cx = len(set([p[0] for p in ps]))
    cy = len(set([p[1] for p in ps]))

    if cx < cy:
        m, s = 1, 0
        ratio = min(cy // cx, floor(log2(n)))
    else:
        m, s = 0, 1
        ratio = min(cx // cy, floor(log2(n)))

    pat = []
    for _ in range(ratio):
        pat.append((m, s))
    pat.append((s, m))

    return _dimension


def run():
    n = int(input())
    sz = floor(sqrt(n))
    ps = []
    for i, line in enumerate(islice(stdin, n)):
        x, y = map(int, line.split())
        ps.append((x, y, i))

    dim = dimension(ps, n)
    build(ps, n, sz, dim)

    input()  # q
    vs = ([p[0] for p in ps], [p[1] for p in ps])
    for line in stdin:
        sx, tx, sy, ty = [int(v) for v in line.split()]
        s = "".join([f"{id_}\n" for id_ in
                     search(ps, vs, n, sz, dim, (sx, sy), (tx, ty))])
        stdout.write(s + "\n")


if __name__ == '__main__':
    run()

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


class Node:
    __slots__ = ('x', 'y', 'left', 'right', 'value')

    def __init__(self, x, y, value):
        self.x = x
        self.y = y
        self.value = value
        self.left = None
        self.right = None

    def __str__(self):
        return "({} [{},{}:{}] {})".format(self.left, self.x, self.y,
                                           self.value, self.right)


class KdTree:

    def __init__(self):
        self.root = None

    def add(self, x, y, v=None):
        def _add(node, level=0):
            if node is None:
                return Node(x, y, v)
            if level % 2 == 0:
                if node.x > x:
                    node.left = _add(node.left, level+1)
                else:
                    node.right = _add(node.right, level+1)
            else:
                if node.y > y:
                    node.left = _add(node.left, level+1)
                else:
                    node.right = _add(node.right, level+1)
            return node
        self.root = _add(self.root, 0)

    def range(self, x1, x2, y1, y2):
        def _range(node, level):
            if node is None:
                return
            if level % 2 == 0:
                if x2 < node.x:
                    yield from _range(node.left, level+1)
                elif x1 > node.x:
                    yield from _range(node.right, level+1)
                else:
                    if y1 <= node.y <= y2:
                        yield (node.x, node.y, node.value)
                    yield from _range(node.left, level+1)
                    yield from _range(node.right, level+1)
            else:
                if y2 < node.y:
                    yield from _range(node.left, level+1)
                elif y1 > node.y:
                    yield from _range(node.right, level+1)
                else:
                    if x1 <= node.x <= x2:
                        yield (node.x, node.y, node.value)
                    yield from _range(node.left, level+1)
                    yield from _range(node.right, level+1)

        yield from _range(self.root, 0)


def run():
    n = int(input())

    t = KdTree()
    ps = []
    for i in range(n):
        x, y = [int(j) for j in input().split()]
        ps.append((x, y, i))

    random.shuffle(ps)
    for x, y, i in ps:
        t.add(x, y, i)

    q = int(input())
    for _ in range(q):
        sx, tx, sy, ty = [int(j) for j in input().split()]
        vs = [v for x, y, v in t.range(sx, tx, sy, ty)]
        for v in sorted(vs):
            print(v)
        print()


if __name__ == '__main__':
    run()




Fixed submission:
#!/usr/bin/env pypy3
# DSL_2_C: Range Search(kD Tree)

from bisect import bisect_left, bisect_right
from collections import deque
from functools import lru_cache
from itertools import islice
from math import floor, log2, sqrt
from operator import itemgetter
from sys import stdin, stdout


def sort3(i, j, k):
    if i > j:
        if j > k:
            return (2, 1, 0)
        elif i > k:
            return (1, 2, 0)
        else:
            return (1, 0, 2)
    else:
        if i > k:
            return (2, 0, 1)
        elif j > k:
            return (0, 2, 1)
        else:
            return (0, 1, 2)


def partition(ps, lo, hi, dim):
    mid = (lo + hi) // 2
    ns = (lo, mid, hi)
    n0, n1, n2 = sort3(ps[lo][dim], ps[mid][dim], ps[hi][dim])
    ps[lo], ps[mid], ps[hi] = ps[ns[n1]], ps[ns[n0]], ps[ns[n2]]
    v = ps[lo][dim]
    i, j = lo, hi
    while True:
        i, j = i+1, j-1
        while ps[i][dim] < v:
            i += 1
        while ps[j][dim] > v:
            j -= 1
        if i >= j:
            break
        ps[i], ps[j] = ps[j], ps[i]
    ps[j], ps[lo] = ps[lo], ps[j]
    return j


def sort(ps, lo, hi, dim):
    for i, p in enumerate(sorted(ps[lo:hi+1], key=itemgetter(dim))):
        ps[lo+i] = p


def halve(ps, s, t, dim):
    mid = (s+t) // 2
    while t - s > 100:
        i = partition(ps, s, t, dim)
        if i > mid:
            t = i - 1
        elif i < mid:
            s = i + 1
        else:
            return mid

    sort(ps, s, t, dim)
    return mid


def build(ps, n, sz, _dim):
    q = deque([(0, n-1, 0)])
    while q:
        s, t, lv = q.popleft()
        dim, _ = _dim(lv)
        if t - s < sz:
            sort(ps, s, t, dim)
            continue
        mid = halve(ps, s, t, dim)
        if mid-1 > s:
            q.append((s, mid-1, lv+1))
        if t > mid+1:
            q.append((mid+1, t, lv+1))


def search(ps, vs, n, sz, _dim, s, t):
    q = deque([(0, n-1, 0)])
    ret = []
    while q:
        i, j, lv = q.popleft()
        dim, rdim = _dim(lv)
        sd, td, sr, tr = s[dim], t[dim], s[rdim], t[rdim]
        if j - i < sz:
            left = bisect_left(vs[dim], sd, i, j+1)
            right = bisect_right(vs[dim], td, i, j+1)
            ret.extend([p[2] for p in ps[left:right] if sr <= p[rdim] <= tr])
            continue

        mid = (i+j) // 2
        if td < ps[mid][dim]:
            q.append((i, mid-1, lv+1))
        elif sd > ps[mid][dim]:
            q.append((mid+1, j, lv+1))
        else:
            if sr <= ps[mid][rdim] <= tr:
                ret.append(ps[mid][2])
            q.append((i, mid-1, lv+1))
            q.append((mid+1, j, lv+1))

    ret.sort()
    return ret


def dimension(ps, n):
    @lru_cache(maxsize=n)
    def _dimension(lv):
        return pat[lv % len(pat)]

    cx = len(set([p[0] for p in ps]))
    cy = len(set([p[1] for p in ps]))

    if cx < cy:
        m, s = 1, 0
        ratio = min(cy // cx, floor(log2(n)))
    else:
        m, s = 0, 1
        ratio = min(cx // cy, floor(log2(n)))

    pat = []
    for _ in range(ratio):
        pat.append((m, s))
    pat.append((s, m))

    return _dimension


def run():
    n = int(input())
    sz = floor(sqrt(n))
    ps = []
    for i, line in enumerate(islice(stdin, n)):
        x, y = map(int, line.split())
        ps.append((x, y, i))

    dim = dimension(ps, n)
    build(ps, n, sz, dim)

    input()  # q
    vs = ([p[0] for p in ps], [p[1] for p in ps])
    for line in stdin:
        sx, tx, sy, ty = [int(v) for v in line.split()]
        s = "".join([f"{id_}\n" for id_ in
                     search(ps, vs, n, sz, dim, (sx, sy), (tx, ty))])
        stdout.write(s + "\n")


if __name__ == '__main__':
    run()

Buggy python submission (verdict: Time Limit Exceeded):

import random


class Node:
    __slots__ = ('x', 'y', 'left', 'right', 'value')

    def __init__(self, x, y, value):
        self.x = x
        self.y = y
        self.value = value
        self.left = None
        self.right = None

    def __str__(self):
        return "({} [{},{}:{}] {})".format(self.left, self.x, self.y,
                                           self.value, self.right)


class KdTree:

    def __init__(self):
        self.root = None

    def add(self, x, y, v=None):
        if self.root is None:
            self.root = Node(x, y, v)
            return

        node = self.root
        level = 0
        while True:
            if level % 2 == 0:
                if node.x > x:
                    if node.left is None:
                        node.left = Node(x, y, v)
                        break
                    else:
                        node = node.left
                else:
                    if node.right is None:
                        node.right = Node(x, y, v)
                        break
                    else:
                        node = node.right
            else:
                if node.y > y:
                    if node.left is None:
                        node.left = Node(x, y, v)
                        break
                    else:
                        node = node.left
                else:
                    if node.right is None:
                        node.right = Node(x, y, v)
                        break
                    else:
                        node = node.right
            level += 1
        return node

    def range(self, x1, x2, y1, y2):
        def _range(node, level):
            if node is None:
                return
            if level % 2 == 0:
                if x2 < node.x:
                    yield from _range(node.left, level+1)
                elif x1 > node.x:
                    yield from _range(node.right, level+1)
                else:
                    if y1 <= node.y <= y2:
                        yield (node.x, node.y, node.value)
                    yield from _range(node.left, level+1)
                    yield from _range(node.right, level+1)
            else:
                if y2 < node.y:
                    yield from _range(node.left, level+1)
                elif y1 > node.y:
                    yield from _range(node.right, level+1)
                else:
                    if x1 <= node.x <= x2:
                        yield (node.x, node.y, node.value)
                    yield from _range(node.left, level+1)
                    yield from _range(node.right, level+1)

        yield from _range(self.root, 0)


def run():
    n = int(input())

    t = KdTree()
    ps = []
    for i in range(n):
        x, y = [int(j) for j in input().split()]
        ps.append((x, y, i))

    random.shuffle(ps)
    for x, y, i in ps:
        t.add(x, y, i)

    q = int(input())
    for _ in range(q):
        sx, tx, sy, ty = [int(j) for j in input().split()]
        for v in sorted(v for x, y, v in t.range(sx, tx, sy, ty)):
            print(v)
        print()


if __name__ == '__main__':
    run()




Fixed submission:
#!/usr/bin/env pypy3
# DSL_2_C: Range Search(kD Tree)

from bisect import bisect_left, bisect_right
from collections import deque
from functools import lru_cache
from itertools import islice
from math import floor, log2, sqrt
from operator import itemgetter
from sys import stdin, stdout


def sort3(i, j, k):
    if i > j:
        if j > k:
            return (2, 1, 0)
        elif i > k:
            return (1, 2, 0)
        else:
            return (1, 0, 2)
    else:
        if i > k:
            return (2, 0, 1)
        elif j > k:
            return (0, 2, 1)
        else:
            return (0, 1, 2)


def partition(ps, lo, hi, dim):
    mid = (lo + hi) // 2
    ns = (lo, mid, hi)
    n0, n1, n2 = sort3(ps[lo][dim], ps[mid][dim], ps[hi][dim])
    ps[lo], ps[mid], ps[hi] = ps[ns[n1]], ps[ns[n0]], ps[ns[n2]]
    v = ps[lo][dim]
    i, j = lo, hi
    while True:
        i, j = i+1, j-1
        while ps[i][dim] < v:
            i += 1
        while ps[j][dim] > v:
            j -= 1
        if i >= j:
            break
        ps[i], ps[j] = ps[j], ps[i]
    ps[j], ps[lo] = ps[lo], ps[j]
    return j


def sort(ps, lo, hi, dim):
    for i, p in enumerate(sorted(ps[lo:hi+1], key=itemgetter(dim))):
        ps[lo+i] = p


def halve(ps, s, t, dim):
    mid = (s+t) // 2
    while t - s > 100:
        i = partition(ps, s, t, dim)
        if i > mid:
            t = i - 1
        elif i < mid:
            s = i + 1
        else:
            return mid

    sort(ps, s, t, dim)
    return mid


def build(ps, n, sz, _dim):
    q = deque([(0, n-1, 0)])
    while q:
        s, t, lv = q.popleft()
        dim, _ = _dim(lv)
        if t - s < sz:
            sort(ps, s, t, dim)
            continue
        mid = halve(ps, s, t, dim)
        if mid-1 > s:
            q.append((s, mid-1, lv+1))
        if t > mid+1:
            q.append((mid+1, t, lv+1))


def search(ps, vs, n, sz, _dim, s, t):
    q = deque([(0, n-1, 0)])
    ret = []
    while q:
        i, j, lv = q.popleft()
        dim, rdim = _dim(lv)
        sd, td, sr, tr = s[dim], t[dim], s[rdim], t[rdim]
        if j - i < sz:
            left = bisect_left(vs[dim], sd, i, j+1)
            right = bisect_right(vs[dim], td, i, j+1)
            ret.extend([p[2] for p in ps[left:right] if sr <= p[rdim] <= tr])
            continue

        mid = (i+j) // 2
        if td < ps[mid][dim]:
            q.append((i, mid-1, lv+1))
        elif sd > ps[mid][dim]:
            q.append((mid+1, j, lv+1))
        else:
            if sr <= ps[mid][rdim] <= tr:
                ret.append(ps[mid][2])
            q.append((i, mid-1, lv+1))
            q.append((mid+1, j, lv+1))

    ret.sort()
    return ret


def dimension(ps, n):
    @lru_cache(maxsize=n)
    def _dimension(lv):
        return pat[lv % len(pat)]

    cx = len(set([p[0] for p in ps]))
    cy = len(set([p[1] for p in ps]))

    if cx < cy:
        m, s = 1, 0
        ratio = min(cy // cx, floor(log2(n)))
    else:
        m, s = 0, 1
        ratio = min(cx // cy, floor(log2(n)))

    pat = []
    for _ in range(ratio):
        pat.append((m, s))
    pat.append((s, m))

    return _dimension


def run():
    n = int(input())
    sz = floor(sqrt(n))
    ps = []
    for i, line in enumerate(islice(stdin, n)):
        x, y = map(int, line.split())
        ps.append((x, y, i))

    dim = dimension(ps, n)
    build(ps, n, sz, dim)

    input()  # q
    vs = ([p[0] for p in ps], [p[1] for p in ps])
    for line in stdin:
        sx, tx, sy, ty = [int(v) for v in line.split()]
        s = "".join([f"{id_}\n" for id_ in
                     search(ps, vs, n, sz, dim, (sx, sy), (tx, ty))])
        stdout.write(s + "\n")


if __name__ == '__main__':
    run()

Buggy python submission (verdict: Time Limit Exceeded):

class Node:
    __slots__ = ('x', 'y', 'left', 'right', 'value')

    def __init__(self, x, y, value):
        self.x = x
        self.y = y
        self.value = value
        self.left = None
        self.right = None

    def __str__(self):
        return "({} [{},{}:{}] {})".format(self.left, self.x, self.y,
                                           self.value, self.right)


class KdTree:

    def __init__(self):
        self.root = None

    def add(self, x, y, v=None):
        if self.root is None:
            self.root = Node(x, y, v)
            return

        node = self.root
        level = 0
        while True:
            if level % 2 == 0:
                if node.x > x:
                    if node.left is None:
                        node.left = Node(x, y, v)
                        break
                    else:
                        node = node.left
                else:
                    if node.right is None:
                        node.right = Node(x, y, v)
                        break
                    else:
                        node = node.right
            else:
                if node.y > y:
                    if node.left is None:
                        node.left = Node(x, y, v)
                        break
                    else:
                        node = node.left
                else:
                    if node.right is None:
                        node.right = Node(x, y, v)
                        break
                    else:
                        node = node.right
            level += 1
        # print(level)

    def range(self, x1, x2, y1, y2):
        def _range(node, level):
            if node is None:
                return
            if level % 2 == 0:
                if x2 < node.x:
                    yield from _range(node.left, level+1)
                elif x1 > node.x:
                    yield from _range(node.right, level+1)
                else:
                    if y1 <= node.y <= y2:
                        yield (node.x, node.y, node.value)
                    yield from _range(node.left, level+1)
                    yield from _range(node.right, level+1)
            else:
                if y2 < node.y:
                    yield from _range(node.left, level+1)
                elif y1 > node.y:
                    yield from _range(node.right, level+1)
                else:
                    if x1 <= node.x <= x2:
                        yield (node.x, node.y, node.value)
                    yield from _range(node.left, level+1)
                    yield from _range(node.right, level+1)

        yield from _range(self.root, 0)


def run():
    n = int(input())

    t = KdTree()
    for i in range(n):
        x, y = [int(j) for j in input().split()]
        t.add(x, y, i)

    q = int(input())
    for _ in range(q):
        sx, tx, sy, ty = [int(j) for j in input().split()]
        for v in sorted(v for x, y, v in t.range(sx, tx, sy, ty)):
            print(v)
        print()


if __name__ == '__main__':
    run()



Fixed submission:
#!/usr/bin/env pypy3
# DSL_2_C: Range Search(kD Tree)

from bisect import bisect_left, bisect_right
from collections import deque
from functools import lru_cache
from itertools import islice
from math import floor, log2, sqrt
from operator import itemgetter
from sys import stdin, stdout


def sort3(i, j, k):
    if i > j:
        if j > k:
            return (2, 1, 0)
        elif i > k:
            return (1, 2, 0)
        else:
            return (1, 0, 2)
    else:
        if i > k:
            return (2, 0, 1)
        elif j > k:
            return (0, 2, 1)
        else:
            return (0, 1, 2)


def partition(ps, lo, hi, dim):
    mid = (lo + hi) // 2
    ns = (lo, mid, hi)
    n0, n1, n2 = sort3(ps[lo][dim], ps[mid][dim], ps[hi][dim])
    ps[lo], ps[mid], ps[hi] = ps[ns[n1]], ps[ns[n0]], ps[ns[n2]]
    v = ps[lo][dim]
    i, j = lo, hi
    while True:
        i, j = i+1, j-1
        while ps[i][dim] < v:
            i += 1
        while ps[j][dim] > v:
            j -= 1
        if i >= j:
            break
        ps[i], ps[j] = ps[j], ps[i]
    ps[j], ps[lo] = ps[lo], ps[j]
    return j


def sort(ps, lo, hi, dim):
    for i, p in enumerate(sorted(ps[lo:hi+1], key=itemgetter(dim))):
        ps[lo+i] = p


def halve(ps, s, t, dim):
    mid = (s+t) // 2
    while t - s > 100:
        i = partition(ps, s, t, dim)
        if i > mid:
            t = i - 1
        elif i < mid:
            s = i + 1
        else:
            return mid

    sort(ps, s, t, dim)
    return mid


def build(ps, n, sz, _dim):
    q = deque([(0, n-1, 0)])
    while q:
        s, t, lv = q.popleft()
        dim, _ = _dim(lv)
        if t - s < sz:
            sort(ps, s, t, dim)
            continue
        mid = halve(ps, s, t, dim)
        if mid-1 > s:
            q.append((s, mid-1, lv+1))
        if t > mid+1:
            q.append((mid+1, t, lv+1))


def search(ps, vs, n, sz, _dim, s, t):
    q = deque([(0, n-1, 0)])
    ret = []
    while q:
        i, j, lv = q.popleft()
        dim, rdim = _dim(lv)
        sd, td, sr, tr = s[dim], t[dim], s[rdim], t[rdim]
        if j - i < sz:
            left = bisect_left(vs[dim], sd, i, j+1)
            right = bisect_right(vs[dim], td, i, j+1)
            ret.extend([p[2] for p in ps[left:right] if sr <= p[rdim] <= tr])
            continue

        mid = (i+j) // 2
        if td < ps[mid][dim]:
            q.append((i, mid-1, lv+1))
        elif sd > ps[mid][dim]:
            q.append((mid+1, j, lv+1))
        else:
            if sr <= ps[mid][rdim] <= tr:
                ret.append(ps[mid][2])
            q.append((i, mid-1, lv+1))
            q.append((mid+1, j, lv+1))

    ret.sort()
    return ret


def dimension(ps, n):
    @lru_cache(maxsize=n)
    def _dimension(lv):
        return pat[lv % len(pat)]

    cx = len(set([p[0] for p in ps]))
    cy = len(set([p[1] for p in ps]))

    if cx < cy:
        m, s = 1, 0
        ratio = min(cy // cx, floor(log2(n)))
    else:
        m, s = 0, 1
        ratio = min(cx // cy, floor(log2(n)))

    pat = []
    for _ in range(ratio):
        pat.append((m, s))
    pat.append((s, m))

    return _dimension


def run():
    n = int(input())
    sz = floor(sqrt(n))
    ps = []
    for i, line in enumerate(islice(stdin, n)):
        x, y = map(int, line.split())
        ps.append((x, y, i))

    dim = dimension(ps, n)
    build(ps, n, sz, dim)

    input()  # q
    vs = ([p[0] for p in ps], [p[1] for p in ps])
    for line in stdin:
        sx, tx, sy, ty = [int(v) for v in line.split()]
        s = "".join([f"{id_}\n" for id_ in
                     search(ps, vs, n, sz, dim, (sx, sy), (tx, ty))])
        stdout.write(s + "\n")


if __name__ == '__main__':
    run()

Buggy python submission (verdict: Time Limit Exceeded):

def run():
    def add(i):
        xi, yi = ps[i]
        dim = 0
        j = root
        if i == j or ps[j] is None:
            return
        while True:
            if ps[j][dim] > ps[i][dim]:
                if left[j] == -1:
                    left[j] = i
                    return
                else:
                    j = left[j]
            else:
                if right[j] == -1:
                    right[j] = i
                    return
                else:
                    j = right[j]
            dim = (dim+1) % 2

    def search(x1, x2, y1, y2):
        def _search(i, dim):
            if i is None or ps[i] is None:
                return
            x, y = ps[i]
            if dim % 2 == 0:
                if x2 < x:
                    yield from _search(left[i], dim+1)
                elif x1 > x:
                    yield from _search(right[i], dim+1)
                else:
                    if y1 <= y <= y2:
                        yield i
                    yield from _search(left[i], dim+1)
                    yield from _search(right[i], dim+1)
            else:
                if y2 < y:
                    yield from _search(left[i], dim+1)
                elif y1 > y:
                    yield from _search(right[i], dim+1)
                else:
                    if x1 <= x <= x2:
                        yield i
                    yield from _search(left[i], dim+1)
                    yield from _search(right[i], dim+1)

        yield from _search(root, 0)

    n = int(input())
    root = None
    ps = [None] * (n+1)
    left = [-1] * n
    right = [-1] * n
    for i in range(n):
        x, y = [int(j) for j in input().split()]
        ps[i] = (x, y)
        if root is None:
            root = i
        add(i)

    q = int(input())
    for _ in range(q):
        sx, tx, sy, ty = [int(j) for j in input().split()]
        for v in sorted(search(sx, tx, sy, ty)):
            print(v)
        print()


if __name__ == '__main__':
    run()



Fixed submission:
#!/usr/bin/env pypy3
# DSL_2_C: Range Search(kD Tree)

from bisect import bisect_left, bisect_right
from collections import deque
from functools import lru_cache
from itertools import islice
from math import floor, log2, sqrt
from operator import itemgetter
from sys import stdin, stdout


def sort3(i, j, k):
    if i > j:
        if j > k:
            return (2, 1, 0)
        elif i > k:
            return (1, 2, 0)
        else:
            return (1, 0, 2)
    else:
        if i > k:
            return (2, 0, 1)
        elif j > k:
            return (0, 2, 1)
        else:
            return (0, 1, 2)


def partition(ps, lo, hi, dim):
    mid = (lo + hi) // 2
    ns = (lo, mid, hi)
    n0, n1, n2 = sort3(ps[lo][dim], ps[mid][dim], ps[hi][dim])
    ps[lo], ps[mid], ps[hi] = ps[ns[n1]], ps[ns[n0]], ps[ns[n2]]
    v = ps[lo][dim]
    i, j = lo, hi
    while True:
        i, j = i+1, j-1
        while ps[i][dim] < v:
            i += 1
        while ps[j][dim] > v:
            j -= 1
        if i >= j:
            break
        ps[i], ps[j] = ps[j], ps[i]
    ps[j], ps[lo] = ps[lo], ps[j]
    return j


def sort(ps, lo, hi, dim):
    for i, p in enumerate(sorted(ps[lo:hi+1], key=itemgetter(dim))):
        ps[lo+i] = p


def halve(ps, s, t, dim):
    mid = (s+t) // 2
    while t - s > 100:
        i = partition(ps, s, t, dim)
        if i > mid:
            t = i - 1
        elif i < mid:
            s = i + 1
        else:
            return mid

    sort(ps, s, t, dim)
    return mid


def build(ps, n, sz, _dim):
    q = deque([(0, n-1, 0)])
    while q:
        s, t, lv = q.popleft()
        dim, _ = _dim(lv)
        if t - s < sz:
            sort(ps, s, t, dim)
            continue
        mid = halve(ps, s, t, dim)
        if mid-1 > s:
            q.append((s, mid-1, lv+1))
        if t > mid+1:
            q.append((mid+1, t, lv+1))


def search(ps, vs, n, sz, _dim, s, t):
    q = deque([(0, n-1, 0)])
    ret = []
    while q:
        i, j, lv = q.popleft()
        dim, rdim = _dim(lv)
        sd, td, sr, tr = s[dim], t[dim], s[rdim], t[rdim]
        if j - i < sz:
            left = bisect_left(vs[dim], sd, i, j+1)
            right = bisect_right(vs[dim], td, i, j+1)
            ret.extend([p[2] for p in ps[left:right] if sr <= p[rdim] <= tr])
            continue

        mid = (i+j) // 2
        if td < ps[mid][dim]:
            q.append((i, mid-1, lv+1))
        elif sd > ps[mid][dim]:
            q.append((mid+1, j, lv+1))
        else:
            if sr <= ps[mid][rdim] <= tr:
                ret.append(ps[mid][2])
            q.append((i, mid-1, lv+1))
            q.append((mid+1, j, lv+1))

    ret.sort()
    return ret


def dimension(ps, n):
    @lru_cache(maxsize=n)
    def _dimension(lv):
        return pat[lv % len(pat)]

    cx = len(set([p[0] for p in ps]))
    cy = len(set([p[1] for p in ps]))

    if cx < cy:
        m, s = 1, 0
        ratio = min(cy // cx, floor(log2(n)))
    else:
        m, s = 0, 1
        ratio = min(cx // cy, floor(log2(n)))

    pat = []
    for _ in range(ratio):
        pat.append((m, s))
    pat.append((s, m))

    return _dimension


def run():
    n = int(input())
    sz = floor(sqrt(n))
    ps = []
    for i, line in enumerate(islice(stdin, n)):
        x, y = map(int, line.split())
        ps.append((x, y, i))

    dim = dimension(ps, n)
    build(ps, n, sz, dim)

    input()  # q
    vs = ([p[0] for p in ps], [p[1] for p in ps])
    for line in stdin:
        sx, tx, sy, ty = [int(v) for v in line.split()]
        s = "".join([f"{id_}\n" for id_ in
                     search(ps, vs, n, sz, dim, (sx, sy), (tx, ty))])
        stdout.write(s + "\n")


if __name__ == '__main__':
    run()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
# DSL_2_C: Range Search(kD Tree)
# クラスを配列に展開


def run():
    def add(i):
        dim = 0
        j = root
        if i == j or ps[j] is None:
            return
        while True:
            if ps[j][dim] > ps[i][dim]:
                if left[j] == -1:
                    left[j] = i
                    return
                else:
                    j = left[j]
            else:
                if right[j] == -1:
                    right[j] = i
                    return
                else:
                    j = right[j]
            dim = (dim+1) % 2

    def search(x1, x2, y1, y2):
        def _search(i, dim):
            if i is None or ps[i] is None:
                return
            x, y = ps[i]
            if dim % 2 == 0:
                if x2 < x:
                    yield from _search(left[i], dim+1)
                elif x1 > x:
                    yield from _search(right[i], dim+1)
                else:
                    if y1 <= y <= y2:
                        yield i
                    yield from _search(left[i], dim+1)
                    yield from _search(right[i], dim+1)
            else:
                if y2 < y:
                    yield from _search(left[i], dim+1)
                elif y1 > y:
                    yield from _search(right[i], dim+1)
                else:
                    if x1 <= x <= x2:
                        yield i
                    yield from _search(left[i], dim+1)
                    yield from _search(right[i], dim+1)

        yield from _search(root, 0)

    n = int(input())
    root = None
    ps = [None] * (n+1)
    left = [-1] * n
    right = [-1] * n
    for i in range(n):
        x, y = [int(j) for j in input().split()]
        ps[i] = (x, y)
        if root is None:
            root = i
        add(i)

    q = int(input())
    for _ in range(q):
        sx, tx, sy, ty = [int(j) for j in input().split()]
        for v in sorted(search(sx, tx, sy, ty)):
            print(v)
        print()


if __name__ == '__main__':
    run()



Fixed submission:
#!/usr/bin/env pypy3
# DSL_2_C: Range Search(kD Tree)

from bisect import bisect_left, bisect_right
from collections import deque
from functools import lru_cache
from itertools import islice
from math import floor, log2, sqrt
from operator import itemgetter
from sys import stdin, stdout


def sort3(i, j, k):
    if i > j:
        if j > k:
            return (2, 1, 0)
        elif i > k:
            return (1, 2, 0)
        else:
            return (1, 0, 2)
    else:
        if i > k:
            return (2, 0, 1)
        elif j > k:
            return (0, 2, 1)
        else:
            return (0, 1, 2)


def partition(ps, lo, hi, dim):
    mid = (lo + hi) // 2
    ns = (lo, mid, hi)
    n0, n1, n2 = sort3(ps[lo][dim], ps[mid][dim], ps[hi][dim])
    ps[lo], ps[mid], ps[hi] = ps[ns[n1]], ps[ns[n0]], ps[ns[n2]]
    v = ps[lo][dim]
    i, j = lo, hi
    while True:
        i, j = i+1, j-1
        while ps[i][dim] < v:
            i += 1
        while ps[j][dim] > v:
            j -= 1
        if i >= j:
            break
        ps[i], ps[j] = ps[j], ps[i]
    ps[j], ps[lo] = ps[lo], ps[j]
    return j


def sort(ps, lo, hi, dim):
    for i, p in enumerate(sorted(ps[lo:hi+1], key=itemgetter(dim))):
        ps[lo+i] = p


def halve(ps, s, t, dim):
    mid = (s+t) // 2
    while t - s > 100:
        i = partition(ps, s, t, dim)
        if i > mid:
            t = i - 1
        elif i < mid:
            s = i + 1
        else:
            return mid

    sort(ps, s, t, dim)
    return mid


def build(ps, n, sz, _dim):
    q = deque([(0, n-1, 0)])
    while q:
        s, t, lv = q.popleft()
        dim, _ = _dim(lv)
        if t - s < sz:
            sort(ps, s, t, dim)
            continue
        mid = halve(ps, s, t, dim)
        if mid-1 > s:
            q.append((s, mid-1, lv+1))
        if t > mid+1:
            q.append((mid+1, t, lv+1))


def search(ps, vs, n, sz, _dim, s, t):
    q = deque([(0, n-1, 0)])
    ret = []
    while q:
        i, j, lv = q.popleft()
        dim, rdim = _dim(lv)
        sd, td, sr, tr = s[dim], t[dim], s[rdim], t[rdim]
        if j - i < sz:
            left = bisect_left(vs[dim], sd, i, j+1)
            right = bisect_right(vs[dim], td, i, j+1)
            ret.extend([p[2] for p in ps[left:right] if sr <= p[rdim] <= tr])
            continue

        mid = (i+j) // 2
        if td < ps[mid][dim]:
            q.append((i, mid-1, lv+1))
        elif sd > ps[mid][dim]:
            q.append((mid+1, j, lv+1))
        else:
            if sr <= ps[mid][rdim] <= tr:
                ret.append(ps[mid][2])
            q.append((i, mid-1, lv+1))
            q.append((mid+1, j, lv+1))

    ret.sort()
    return ret


def dimension(ps, n):
    @lru_cache(maxsize=n)
    def _dimension(lv):
        return pat[lv % len(pat)]

    cx = len(set([p[0] for p in ps]))
    cy = len(set([p[1] for p in ps]))

    if cx < cy:
        m, s = 1, 0
        ratio = min(cy // cx, floor(log2(n)))
    else:
        m, s = 0, 1
        ratio = min(cx // cy, floor(log2(n)))

    pat = []
    for _ in range(ratio):
        pat.append((m, s))
    pat.append((s, m))

    return _dimension


def run():
    n = int(input())
    sz = floor(sqrt(n))
    ps = []
    for i, line in enumerate(islice(stdin, n)):
        x, y = map(int, line.split())
        ps.append((x, y, i))

    dim = dimension(ps, n)
    build(ps, n, sz, dim)

    input()  # q
    vs = ([p[0] for p in ps], [p[1] for p in ps])
    for line in stdin:
        sx, tx, sy, ty = [int(v) for v in line.split()]
        s = "".join([f"{id_}\n" for id_ in
                     search(ps, vs, n, sz, dim, (sx, sy), (tx, ty))])
        stdout.write(s + "\n")


if __name__ == '__main__':
    run()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
# DSL_2_C: Range Search(kD Tree)
# クラスを配列に展開


def run():
    def add(i):
        dim = 0
        if i == 0:
            return
        j = 0
        while True:
            left, right = cs[j]
            if ps[j][dim] > ps[i][dim]:
                if left == -1:
                    cs[j] = (i, right)
                    return
                else:
                    j = left
            else:
                if right == -1:
                    cs[j] = (left, i)
                    return
                else:
                    j = right
            dim = (dim+1) % 2

    def search(x1, x2, y1, y2):
        def _search(i, dim):
            if i == -1:
                return
            x, y = ps[i]
            left, right = cs[i]
            if dim % 2 == 0:
                if x2 < x:
                    yield from _search(left, dim+1)
                elif x1 > x:
                    yield from _search(right, dim+1)
                else:
                    if y1 <= y <= y2:
                        yield i
                    yield from _search(left, dim+1)
                    yield from _search(right, dim+1)
            else:
                if y2 < y:
                    yield from _search(left, dim+1)
                elif y1 > y:
                    yield from _search(right, dim+1)
                else:
                    if x1 <= x <= x2:
                        yield i
                    yield from _search(left, dim+1)
                    yield from _search(right, dim+1)

        yield from _search(root, 0)

    n = int(input())
    root = 0
    ps = []
    cs = [(-1, -1)] * n
    for i in range(n):
        ps.append(tuple(int(n) for n in input().split()))
        add(i)

    q = int(input())
    for _ in range(q):
        sx, tx, sy, ty = [int(j) for j in input().split()]
        for v in sorted(search(sx, tx, sy, ty)):
            print(v)
        print()


if __name__ == '__main__':
    run()



Fixed submission:
#!/usr/bin/env pypy3
# DSL_2_C: Range Search(kD Tree)

from bisect import bisect_left, bisect_right
from collections import deque
from functools import lru_cache
from itertools import islice
from math import floor, log2, sqrt
from operator import itemgetter
from sys import stdin, stdout


def sort3(i, j, k):
    if i > j:
        if j > k:
            return (2, 1, 0)
        elif i > k:
            return (1, 2, 0)
        else:
            return (1, 0, 2)
    else:
        if i > k:
            return (2, 0, 1)
        elif j > k:
            return (0, 2, 1)
        else:
            return (0, 1, 2)


def partition(ps, lo, hi, dim):
    mid = (lo + hi) // 2
    ns = (lo, mid, hi)
    n0, n1, n2 = sort3(ps[lo][dim], ps[mid][dim], ps[hi][dim])
    ps[lo], ps[mid], ps[hi] = ps[ns[n1]], ps[ns[n0]], ps[ns[n2]]
    v = ps[lo][dim]
    i, j = lo, hi
    while True:
        i, j = i+1, j-1
        while ps[i][dim] < v:
            i += 1
        while ps[j][dim] > v:
            j -= 1
        if i >= j:
            break
        ps[i], ps[j] = ps[j], ps[i]
    ps[j], ps[lo] = ps[lo], ps[j]
    return j


def sort(ps, lo, hi, dim):
    for i, p in enumerate(sorted(ps[lo:hi+1], key=itemgetter(dim))):
        ps[lo+i] = p


def halve(ps, s, t, dim):
    mid = (s+t) // 2
    while t - s > 100:
        i = partition(ps, s, t, dim)
        if i > mid:
            t = i - 1
        elif i < mid:
            s = i + 1
        else:
            return mid

    sort(ps, s, t, dim)
    return mid


def build(ps, n, sz, _dim):
    q = deque([(0, n-1, 0)])
    while q:
        s, t, lv = q.popleft()
        dim, _ = _dim(lv)
        if t - s < sz:
            sort(ps, s, t, dim)
            continue
        mid = halve(ps, s, t, dim)
        if mid-1 > s:
            q.append((s, mid-1, lv+1))
        if t > mid+1:
            q.append((mid+1, t, lv+1))


def search(ps, vs, n, sz, _dim, s, t):
    q = deque([(0, n-1, 0)])
    ret = []
    while q:
        i, j, lv = q.popleft()
        dim, rdim = _dim(lv)
        sd, td, sr, tr = s[dim], t[dim], s[rdim], t[rdim]
        if j - i < sz:
            left = bisect_left(vs[dim], sd, i, j+1)
            right = bisect_right(vs[dim], td, i, j+1)
            ret.extend([p[2] for p in ps[left:right] if sr <= p[rdim] <= tr])
            continue

        mid = (i+j) // 2
        if td < ps[mid][dim]:
            q.append((i, mid-1, lv+1))
        elif sd > ps[mid][dim]:
            q.append((mid+1, j, lv+1))
        else:
            if sr <= ps[mid][rdim] <= tr:
                ret.append(ps[mid][2])
            q.append((i, mid-1, lv+1))
            q.append((mid+1, j, lv+1))

    ret.sort()
    return ret


def dimension(ps, n):
    @lru_cache(maxsize=n)
    def _dimension(lv):
        return pat[lv % len(pat)]

    cx = len(set([p[0] for p in ps]))
    cy = len(set([p[1] for p in ps]))

    if cx < cy:
        m, s = 1, 0
        ratio = min(cy // cx, floor(log2(n)))
    else:
        m, s = 0, 1
        ratio = min(cx // cy, floor(log2(n)))

    pat = []
    for _ in range(ratio):
        pat.append((m, s))
    pat.append((s, m))

    return _dimension


def run():
    n = int(input())
    sz = floor(sqrt(n))
    ps = []
    for i, line in enumerate(islice(stdin, n)):
        x, y = map(int, line.split())
        ps.append((x, y, i))

    dim = dimension(ps, n)
    build(ps, n, sz, dim)

    input()  # q
    vs = ([p[0] for p in ps], [p[1] for p in ps])
    for line in stdin:
        sx, tx, sy, ty = [int(v) for v in line.split()]
        s = "".join([f"{id_}\n" for id_ in
                     search(ps, vs, n, sz, dim, (sx, sy), (tx, ty))])
        stdout.write(s + "\n")


if __name__ == '__main__':
    run()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
# DSL_2_C: Range Search(kD Tree)
# クラスを配列に展開

import sys
import bisect


def run():
    def add(i, p):
        ps.append(p)
        cs.append(nc)
        if i == 0:
            return
        dim = 0
        j = 0
        while True:
            left, right = cs[j]
            if ps[j][dim] > p[dim]:
                if left == -1:
                    cs[j] = (i, right)
                    return
                j = left
            else:
                if right == -1:
                    cs[j] = (left, i)
                    return
                j = right
            dim = rev[dim]

    def search(s, t):
        stack = [(0, 0)]
        ret = []
        while len(stack) > 0:
            i, dim = stack.pop()
            left, right = cs[i]
            if t[dim] < ps[i][dim]:
                if left != -1:
                    stack.append((left, rev[dim]))
            elif s[dim] > ps[i][dim]:
                if right != -1:
                    stack.append((right, rev[dim]))
            else:
                rd = rev[dim]
                if s[rd] <= ps[i][rd] <= t[rd]:
                    bisect.insort(ret, i)
                if left != -1:
                    stack.append((left, rd))
                if right != -1:
                    stack.append((right, rd))
        return ret

    n = int(input())
    ps = []
    cs = []
    nc = (-1, -1)
    rev = (1, 0)
    i = 0
    for line in sys.stdin:
        if i == n:
            break
        add(i, tuple(int(v) for v in line.split()))
        i += 1

    # q = int(line)
    for line in sys.stdin:
        sx, tx, sy, ty = [int(v) for v in line.split()]
        for v in search((sx, sy), (tx, ty)):
            print(v)
        print()


if __name__ == '__main__':
    run()



Fixed submission:
#!/usr/bin/env pypy3
# DSL_2_C: Range Search(kD Tree)

from bisect import bisect_left, bisect_right
from collections import deque
from functools import lru_cache
from itertools import islice
from math import floor, log2, sqrt
from operator import itemgetter
from sys import stdin, stdout


def sort3(i, j, k):
    if i > j:
        if j > k:
            return (2, 1, 0)
        elif i > k:
            return (1, 2, 0)
        else:
            return (1, 0, 2)
    else:
        if i > k:
            return (2, 0, 1)
        elif j > k:
            return (0, 2, 1)
        else:
            return (0, 1, 2)


def partition(ps, lo, hi, dim):
    mid = (lo + hi) // 2
    ns = (lo, mid, hi)
    n0, n1, n2 = sort3(ps[lo][dim], ps[mid][dim], ps[hi][dim])
    ps[lo], ps[mid], ps[hi] = ps[ns[n1]], ps[ns[n0]], ps[ns[n2]]
    v = ps[lo][dim]
    i, j = lo, hi
    while True:
        i, j = i+1, j-1
        while ps[i][dim] < v:
            i += 1
        while ps[j][dim] > v:
            j -= 1
        if i >= j:
            break
        ps[i], ps[j] = ps[j], ps[i]
    ps[j], ps[lo] = ps[lo], ps[j]
    return j


def sort(ps, lo, hi, dim):
    for i, p in enumerate(sorted(ps[lo:hi+1], key=itemgetter(dim))):
        ps[lo+i] = p


def halve(ps, s, t, dim):
    mid = (s+t) // 2
    while t - s > 100:
        i = partition(ps, s, t, dim)
        if i > mid:
            t = i - 1
        elif i < mid:
            s = i + 1
        else:
            return mid

    sort(ps, s, t, dim)
    return mid


def build(ps, n, sz, _dim):
    q = deque([(0, n-1, 0)])
    while q:
        s, t, lv = q.popleft()
        dim, _ = _dim(lv)
        if t - s < sz:
            sort(ps, s, t, dim)
            continue
        mid = halve(ps, s, t, dim)
        if mid-1 > s:
            q.append((s, mid-1, lv+1))
        if t > mid+1:
            q.append((mid+1, t, lv+1))


def search(ps, vs, n, sz, _dim, s, t):
    q = deque([(0, n-1, 0)])
    ret = []
    while q:
        i, j, lv = q.popleft()
        dim, rdim = _dim(lv)
        sd, td, sr, tr = s[dim], t[dim], s[rdim], t[rdim]
        if j - i < sz:
            left = bisect_left(vs[dim], sd, i, j+1)
            right = bisect_right(vs[dim], td, i, j+1)
            ret.extend([p[2] for p in ps[left:right] if sr <= p[rdim] <= tr])
            continue

        mid = (i+j) // 2
        if td < ps[mid][dim]:
            q.append((i, mid-1, lv+1))
        elif sd > ps[mid][dim]:
            q.append((mid+1, j, lv+1))
        else:
            if sr <= ps[mid][rdim] <= tr:
                ret.append(ps[mid][2])
            q.append((i, mid-1, lv+1))
            q.append((mid+1, j, lv+1))

    ret.sort()
    return ret


def dimension(ps, n):
    @lru_cache(maxsize=n)
    def _dimension(lv):
        return pat[lv % len(pat)]

    cx = len(set([p[0] for p in ps]))
    cy = len(set([p[1] for p in ps]))

    if cx < cy:
        m, s = 1, 0
        ratio = min(cy // cx, floor(log2(n)))
    else:
        m, s = 0, 1
        ratio = min(cx // cy, floor(log2(n)))

    pat = []
    for _ in range(ratio):
        pat.append((m, s))
    pat.append((s, m))

    return _dimension


def run():
    n = int(input())
    sz = floor(sqrt(n))
    ps = []
    for i, line in enumerate(islice(stdin, n)):
        x, y = map(int, line.split())
        ps.append((x, y, i))

    dim = dimension(ps, n)
    build(ps, n, sz, dim)

    input()  # q
    vs = ([p[0] for p in ps], [p[1] for p in ps])
    for line in stdin:
        sx, tx, sy, ty = [int(v) for v in line.split()]
        s = "".join([f"{id_}\n" for id_ in
                     search(ps, vs, n, sz, dim, (sx, sy), (tx, ty))])
        stdout.write(s + "\n")


if __name__ == '__main__':
    run()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
# DSL_2_C: Range Search(kD Tree)
# ツリーを作成せず配列で保持する

import sys
from collections import deque


def run():
    def sort3(i, j, k):
        if i > j:
            if j > k:
                return (0, 1, 2)
            elif i > k:
                return (0, 2, 1)
            else:
                return (2, 0, 1)
        else:
            if i > k:
                return (1, 0, 2)
            elif j > k:
                return (1, 2, 0)
            else:
                return (2, 1, 0)

    def move_max(lo, hi, lv):
        j, v = hi, ps[hi][lv]
        for i in range(lo, hi):
            if ps[i][lv] > v:
                j, v = i, ps[i][lv]
        if j < hi:
            ps[j], ps[hi] = ps[hi], ps[j]
        return hi

    def move_min(lo, hi, lv):
        j, v = lo, ps[lo][lv]
        for i in range(hi, lo, -1):
            if ps[i][lv] < v:
                j, v = i, ps[i][lv]
        if j > lo:
            ps[j], ps[lo] = ps[lo], ps[j]
        return lo

    def sort(lo, hi, lv):
        for i in range(lo+1, hi+1):
            for j in range(i, lo, -1):
                if ps[j-1][lv] > ps[j][lv]:
                    ps[j-1], ps[j] = ps[j], ps[j-1]
                else:
                    break

    def partition(lo, hi, lv):
        mid = (lo+hi)//2
        ns = (lo, mid, hi)
        n0, n1, n2 = sort3(ps[lo][lv], ps[mid][lv], ps[hi][lv])
        v = ps[ns[n1]][lv]
        ps[lo], ps[mid], ps[hi] = ps[ns[n1]], ps[ns[n2]], ps[ns[n0]]
        i, j = lo, hi
        while True:
            i, j = i+1, j-1
            while ps[i][lv] < v:
                i += 1
            while ps[j][lv] > v:
                j -= 1
            if i >= j:
                break
            ps[i], ps[j] = ps[j], ps[i]
        ps[j], ps[lo] = ps[lo], ps[j]
        """
        assert all(ps[j][lv] >= ps[n][lv] for n in range(lo, j)), \
            [(n, ps[n][lv]) for n in range(lo, j+1) if ps[n][lv] > ps[j][lv]]
        assert all(ps[j][lv] <= ps[n][lv] for n in range(j, hi+1)), \
            [(n, ps[n][lv]) for n in range(j, hi+1) if ps[n][lv] < ps[j][lv]]
        """
        return j

    def halve(s, t, lv):
        def _halve(mid, lo, hi):
            if mid == lo:
                return move_min(lo, hi, lv)
            elif mid == hi:
                return move_max(lo, hi, lv)
            elif hi-lo < 7:
                sort(lo, hi, lv)
                return mid
            i = partition(lo, hi, lv)
            if i == mid:
                return i
            elif i > mid:
                return _halve(mid, lo, i-1)
            else:
                return _halve(mid, i+1, hi)

        k = _halve((s+t)//2, s, t)
        assert k == (s+t)//2, (k, s, t, (s+t)//2)
        return k

    def build():
        rev = (1, 0)
        q = deque([(0, len(ps)-1, 0)])
        while len(q) > 0:
            s, t, lv = q.popleft()
            mid = halve(s, t, lv)
            if mid-1 > s:
                q.append((s, mid-1, rev[lv]))
            if t > mid+1:
                q.append((mid+1, t, rev[lv]))

    def search(s, t):
        stack = [(0, n-1, 0)]
        rev = (1, 0)
        ret = []
        while len(stack) > 0:
            i, j, dim = stack.pop()
            if i > j:
                continue
            mid = (i+j) // 2
            if t[dim] < ps[mid][dim]:
                stack.append((i, mid-1, rev[dim]))
            elif s[dim] > ps[mid][dim]:
                stack.append((mid+1, j, rev[dim]))
            else:
                rd = rev[dim]
                if s[rd] <= ps[mid][rd] <= t[rd]:
                    ret.append(ps[mid][2])
                stack.append((i, mid-1, rd))
                stack.append((mid+1, j, rd))
        return sorted(ret)

    n = int(input())
    ps = []
    i = 0
    for line in sys.stdin:
        if i < n:
            x, y = [int(v) for v in line.split()]
            ps.append((x, y, i))
            i += 1
        else:
            break

    build()

    # q = int(line)
    for line in sys.stdin:
        sx, tx, sy, ty = [int(v) for v in line.split()]
        for v in search((sx, sy), (tx, ty)):
            print(v)
        print()


if __name__ == '__main__':
    run()



Fixed submission:
#!/usr/bin/env pypy3
# DSL_2_C: Range Search(kD Tree)

from bisect import bisect_left, bisect_right
from collections import deque
from functools import lru_cache
from itertools import islice
from math import floor, log2, sqrt
from operator import itemgetter
from sys import stdin, stdout


def sort3(i, j, k):
    if i > j:
        if j > k:
            return (2, 1, 0)
        elif i > k:
            return (1, 2, 0)
        else:
            return (1, 0, 2)
    else:
        if i > k:
            return (2, 0, 1)
        elif j > k:
            return (0, 2, 1)
        else:
            return (0, 1, 2)


def partition(ps, lo, hi, dim):
    mid = (lo + hi) // 2
    ns = (lo, mid, hi)
    n0, n1, n2 = sort3(ps[lo][dim], ps[mid][dim], ps[hi][dim])
    ps[lo], ps[mid], ps[hi] = ps[ns[n1]], ps[ns[n0]], ps[ns[n2]]
    v = ps[lo][dim]
    i, j = lo, hi
    while True:
        i, j = i+1, j-1
        while ps[i][dim] < v:
            i += 1
        while ps[j][dim] > v:
            j -= 1
        if i >= j:
            break
        ps[i], ps[j] = ps[j], ps[i]
    ps[j], ps[lo] = ps[lo], ps[j]
    return j


def sort(ps, lo, hi, dim):
    for i, p in enumerate(sorted(ps[lo:hi+1], key=itemgetter(dim))):
        ps[lo+i] = p


def halve(ps, s, t, dim):
    mid = (s+t) // 2
    while t - s > 100:
        i = partition(ps, s, t, dim)
        if i > mid:
            t = i - 1
        elif i < mid:
            s = i + 1
        else:
            return mid

    sort(ps, s, t, dim)
    return mid


def build(ps, n, sz, _dim):
    q = deque([(0, n-1, 0)])
    while q:
        s, t, lv = q.popleft()
        dim, _ = _dim(lv)
        if t - s < sz:
            sort(ps, s, t, dim)
            continue
        mid = halve(ps, s, t, dim)
        if mid-1 > s:
            q.append((s, mid-1, lv+1))
        if t > mid+1:
            q.append((mid+1, t, lv+1))


def search(ps, vs, n, sz, _dim, s, t):
    q = deque([(0, n-1, 0)])
    ret = []
    while q:
        i, j, lv = q.popleft()
        dim, rdim = _dim(lv)
        sd, td, sr, tr = s[dim], t[dim], s[rdim], t[rdim]
        if j - i < sz:
            left = bisect_left(vs[dim], sd, i, j+1)
            right = bisect_right(vs[dim], td, i, j+1)
            ret.extend([p[2] for p in ps[left:right] if sr <= p[rdim] <= tr])
            continue

        mid = (i+j) // 2
        if td < ps[mid][dim]:
            q.append((i, mid-1, lv+1))
        elif sd > ps[mid][dim]:
            q.append((mid+1, j, lv+1))
        else:
            if sr <= ps[mid][rdim] <= tr:
                ret.append(ps[mid][2])
            q.append((i, mid-1, lv+1))
            q.append((mid+1, j, lv+1))

    ret.sort()
    return ret


def dimension(ps, n):
    @lru_cache(maxsize=n)
    def _dimension(lv):
        return pat[lv % len(pat)]

    cx = len(set([p[0] for p in ps]))
    cy = len(set([p[1] for p in ps]))

    if cx < cy:
        m, s = 1, 0
        ratio = min(cy // cx, floor(log2(n)))
    else:
        m, s = 0, 1
        ratio = min(cx // cy, floor(log2(n)))

    pat = []
    for _ in range(ratio):
        pat.append((m, s))
    pat.append((s, m))

    return _dimension


def run():
    n = int(input())
    sz = floor(sqrt(n))
    ps = []
    for i, line in enumerate(islice(stdin, n)):
        x, y = map(int, line.split())
        ps.append((x, y, i))

    dim = dimension(ps, n)
    build(ps, n, sz, dim)

    input()  # q
    vs = ([p[0] for p in ps], [p[1] for p in ps])
    for line in stdin:
        sx, tx, sy, ty = [int(v) for v in line.split()]
        s = "".join([f"{id_}\n" for id_ in
                     search(ps, vs, n, sz, dim, (sx, sy), (tx, ty))])
        stdout.write(s + "\n")


if __name__ == '__main__':
    run()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env pypy3
# DSL_2_C: Range Search(kD Tree)

from bisect import bisect_left, bisect_right


def run():
    n = int(input())
    ps = []
    i = 0
    for _ in range(n):
        x, y = [int(v) for v in input().split()]
        ps.append((i, x, y))
        i += 1

    xs, ys, xids, yids = [], [], [], []
    for i, x in sorted(((i, x) for i, x, y in ps), key=lambda p: p[1]):
        xids.append(i)
        xs.append(x)

    for i, y in sorted(((i, y) for i, x, y in ps), key=lambda p: p[1]):
        yids.append(i)
        ys.append(y)

    q = int(input())
    for _ in range(q):
        sx, tx, sy, ty = [int(v) for v in input().split()]
        xmin = bisect_left(xs, sx)
        xmax = bisect_right(xs, tx)
        ymin = bisect_left(ys, sy)
        ymax = bisect_right(ys, ty)

        xwid = xmax - xmin
        ywid = ymax - ymin

        ids = set()
        if xwid * 100 > ywid:
            for i in yids[ymin:ymax]:
                if sx <= ps[i][1] <= tx:
                    ids.add(i)
        elif ywid * 100 > xwid:
            for i in xids[xmin:xmax]:
                if sy <= ps[i][2] <= ty:
                    ids.add(i)
        else:
            ids = set(xids[xmin:xmax]) & set(yids[ymin:ymax])

        for v in sorted(ids):
            print(v)
        print()


if __name__ == '__main__':
    run()



Fixed submission:
#!/usr/bin/env pypy3
# DSL_2_C: Range Search(kD Tree)

from bisect import bisect_left, bisect_right
from collections import deque
from functools import lru_cache
from itertools import islice
from math import floor, log2, sqrt
from operator import itemgetter
from sys import stdin, stdout


def sort3(i, j, k):
    if i > j:
        if j > k:
            return (2, 1, 0)
        elif i > k:
            return (1, 2, 0)
        else:
            return (1, 0, 2)
    else:
        if i > k:
            return (2, 0, 1)
        elif j > k:
            return (0, 2, 1)
        else:
            return (0, 1, 2)


def partition(ps, lo, hi, dim):
    mid = (lo + hi) // 2
    ns = (lo, mid, hi)
    n0, n1, n2 = sort3(ps[lo][dim], ps[mid][dim], ps[hi][dim])
    ps[lo], ps[mid], ps[hi] = ps[ns[n1]], ps[ns[n0]], ps[ns[n2]]
    v = ps[lo][dim]
    i, j = lo, hi
    while True:
        i, j = i+1, j-1
        while ps[i][dim] < v:
            i += 1
        while ps[j][dim] > v:
            j -= 1
        if i >= j:
            break
        ps[i], ps[j] = ps[j], ps[i]
    ps[j], ps[lo] = ps[lo], ps[j]
    return j


def sort(ps, lo, hi, dim):
    for i, p in enumerate(sorted(ps[lo:hi+1], key=itemgetter(dim))):
        ps[lo+i] = p


def halve(ps, s, t, dim):
    mid = (s+t) // 2
    while t - s > 100:
        i = partition(ps, s, t, dim)
        if i > mid:
            t = i - 1
        elif i < mid:
            s = i + 1
        else:
            return mid

    sort(ps, s, t, dim)
    return mid


def build(ps, n, sz, _dim):
    q = deque([(0, n-1, 0)])
    while q:
        s, t, lv = q.popleft()
        dim, _ = _dim(lv)
        if t - s < sz:
            sort(ps, s, t, dim)
            continue
        mid = halve(ps, s, t, dim)
        if mid-1 > s:
            q.append((s, mid-1, lv+1))
        if t > mid+1:
            q.append((mid+1, t, lv+1))


def search(ps, vs, n, sz, _dim, s, t):
    q = deque([(0, n-1, 0)])
    ret = []
    while q:
        i, j, lv = q.popleft()
        dim, rdim = _dim(lv)
        sd, td, sr, tr = s[dim], t[dim], s[rdim], t[rdim]
        if j - i < sz:
            left = bisect_left(vs[dim], sd, i, j+1)
            right = bisect_right(vs[dim], td, i, j+1)
            ret.extend([p[2] for p in ps[left:right] if sr <= p[rdim] <= tr])
            continue

        mid = (i+j) // 2
        if td < ps[mid][dim]:
            q.append((i, mid-1, lv+1))
        elif sd > ps[mid][dim]:
            q.append((mid+1, j, lv+1))
        else:
            if sr <= ps[mid][rdim] <= tr:
                ret.append(ps[mid][2])
            q.append((i, mid-1, lv+1))
            q.append((mid+1, j, lv+1))

    ret.sort()
    return ret


def dimension(ps, n):
    @lru_cache(maxsize=n)
    def _dimension(lv):
        return pat[lv % len(pat)]

    cx = len(set([p[0] for p in ps]))
    cy = len(set([p[1] for p in ps]))

    if cx < cy:
        m, s = 1, 0
        ratio = min(cy // cx, floor(log2(n)))
    else:
        m, s = 0, 1
        ratio = min(cx // cy, floor(log2(n)))

    pat = []
    for _ in range(ratio):
        pat.append((m, s))
    pat.append((s, m))

    return _dimension


def run():
    n = int(input())
    sz = floor(sqrt(n))
    ps = []
    for i, line in enumerate(islice(stdin, n)):
        x, y = map(int, line.split())
        ps.append((x, y, i))

    dim = dimension(ps, n)
    build(ps, n, sz, dim)

    input()  # q
    vs = ([p[0] for p in ps], [p[1] for p in ps])
    for line in stdin:
        sx, tx, sy, ty = [int(v) for v in line.split()]
        s = "".join([f"{id_}\n" for id_ in
                     search(ps, vs, n, sz, dim, (sx, sy), (tx, ty))])
        stdout.write(s + "\n")


if __name__ == '__main__':
    run()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env pypy3
# DSL_2_C: Range Search(kD Tree)

from bisect import bisect_left, bisect_right
from math import floor, sqrt
import sys


def run():
    n = int(input())
    ps = []
    i = 0
    for line in sys.stdin:
        if i >= n:
            break
        x, y = [int(v) for v in line.split()]
        ps.append((i, x, y))
        i += 1

    xs, ys, xids, yids = [], [], [], []
    for i, x in sorted(((i, x) for i, x, y in ps), key=lambda p: p[1]):
        xids.append(i)
        xs.append(x)

    for i, y in sorted(((i, y) for i, x, y in ps), key=lambda p: p[1]):
        yids.append(i)
        ys.append(y)

    sz = n//max(1, floor(sqrt(n)))
    idmap = [[None] * (n//sz+1) for _ in range(n//sz+1)]
    xidmap = [frozenset(xids[i*sz:(i+1)*sz]) for i in range(n//sz+1)]
    yidmap = [frozenset(yids[j*sz:(j+1)*sz]) for j in range(n//sz+1)]
    for line in sys.stdin:
        sx, tx, sy, ty = [int(v) for v in line.split()]
        xmin = bisect_left(xs, sx)
        xmax = bisect_right(xs, tx)
        ymin = bisect_left(ys, sy)
        ymax = bisect_right(ys, ty)

        ids = set()
        for i in range(xmin//sz, (xmax-1)//sz+1):
            xpart = xmin > i*sz or xmax < (i+1)*sz
            for j in range(ymin//sz, (ymax-1)//sz+1):
                if idmap[i][j] is None:
                    idmap[i][j] = xidmap[i] & yidmap[j]
                ypart = ymin > j*sz or ymax < (j+1)*sz
                if xpart or ypart:
                    ids |= {p for p in idmap[i][j] if (sx <= ps[p][1] <= tx and
                                                       sy <= ps[p][2] <= ty)}
                else:
                    ids |= idmap[i][j]

        for v in sorted(ids):
            print(v)
        print()


if __name__ == '__main__':
    run()



Fixed submission:
#!/usr/bin/env pypy3
# DSL_2_C: Range Search(kD Tree)

from bisect import bisect_left, bisect_right
from collections import deque
from functools import lru_cache
from itertools import islice
from math import floor, log2, sqrt
from operator import itemgetter
from sys import stdin, stdout


def sort3(i, j, k):
    if i > j:
        if j > k:
            return (2, 1, 0)
        elif i > k:
            return (1, 2, 0)
        else:
            return (1, 0, 2)
    else:
        if i > k:
            return (2, 0, 1)
        elif j > k:
            return (0, 2, 1)
        else:
            return (0, 1, 2)


def partition(ps, lo, hi, dim):
    mid = (lo + hi) // 2
    ns = (lo, mid, hi)
    n0, n1, n2 = sort3(ps[lo][dim], ps[mid][dim], ps[hi][dim])
    ps[lo], ps[mid], ps[hi] = ps[ns[n1]], ps[ns[n0]], ps[ns[n2]]
    v = ps[lo][dim]
    i, j = lo, hi
    while True:
        i, j = i+1, j-1
        while ps[i][dim] < v:
            i += 1
        while ps[j][dim] > v:
            j -= 1
        if i >= j:
            break
        ps[i], ps[j] = ps[j], ps[i]
    ps[j], ps[lo] = ps[lo], ps[j]
    return j


def sort(ps, lo, hi, dim):
    for i, p in enumerate(sorted(ps[lo:hi+1], key=itemgetter(dim))):
        ps[lo+i] = p


def halve(ps, s, t, dim):
    mid = (s+t) // 2
    while t - s > 100:
        i = partition(ps, s, t, dim)
        if i > mid:
            t = i - 1
        elif i < mid:
            s = i + 1
        else:
            return mid

    sort(ps, s, t, dim)
    return mid


def build(ps, n, sz, _dim):
    q = deque([(0, n-1, 0)])
    while q:
        s, t, lv = q.popleft()
        dim, _ = _dim(lv)
        if t - s < sz:
            sort(ps, s, t, dim)
            continue
        mid = halve(ps, s, t, dim)
        if mid-1 > s:
            q.append((s, mid-1, lv+1))
        if t > mid+1:
            q.append((mid+1, t, lv+1))


def search(ps, vs, n, sz, _dim, s, t):
    q = deque([(0, n-1, 0)])
    ret = []
    while q:
        i, j, lv = q.popleft()
        dim, rdim = _dim(lv)
        sd, td, sr, tr = s[dim], t[dim], s[rdim], t[rdim]
        if j - i < sz:
            left = bisect_left(vs[dim], sd, i, j+1)
            right = bisect_right(vs[dim], td, i, j+1)
            ret.extend([p[2] for p in ps[left:right] if sr <= p[rdim] <= tr])
            continue

        mid = (i+j) // 2
        if td < ps[mid][dim]:
            q.append((i, mid-1, lv+1))
        elif sd > ps[mid][dim]:
            q.append((mid+1, j, lv+1))
        else:
            if sr <= ps[mid][rdim] <= tr:
                ret.append(ps[mid][2])
            q.append((i, mid-1, lv+1))
            q.append((mid+1, j, lv+1))

    ret.sort()
    return ret


def dimension(ps, n):
    @lru_cache(maxsize=n)
    def _dimension(lv):
        return pat[lv % len(pat)]

    cx = len(set([p[0] for p in ps]))
    cy = len(set([p[1] for p in ps]))

    if cx < cy:
        m, s = 1, 0
        ratio = min(cy // cx, floor(log2(n)))
    else:
        m, s = 0, 1
        ratio = min(cx // cy, floor(log2(n)))

    pat = []
    for _ in range(ratio):
        pat.append((m, s))
    pat.append((s, m))

    return _dimension


def run():
    n = int(input())
    sz = floor(sqrt(n))
    ps = []
    for i, line in enumerate(islice(stdin, n)):
        x, y = map(int, line.split())
        ps.append((x, y, i))

    dim = dimension(ps, n)
    build(ps, n, sz, dim)

    input()  # q
    vs = ([p[0] for p in ps], [p[1] for p in ps])
    for line in stdin:
        sx, tx, sy, ty = [int(v) for v in line.split()]
        s = "".join([f"{id_}\n" for id_ in
                     search(ps, vs, n, sz, dim, (sx, sy), (tx, ty))])
        stdout.write(s + "\n")


if __name__ == '__main__':
    run()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env pypy3
# DSL_2_C: Range Search(kD Tree)

from bisect import bisect_left, bisect_right
from math import floor, sqrt
import sys


def run():
    n = int(input())
    ps = []
    i = 0
    for line in sys.stdin:
        if i >= n:
            break
        x, y = [int(v) for v in line.split()]
        ps.append((i, x, y))
        i += 1

    xs, ys, xids, yids = [], [], [], []
    for i, x in sorted(((i, x) for i, x, y in ps), key=lambda p: p[1]):
        xids.append(i)
        xs.append(x)

    for i, y in sorted(((i, y) for i, x, y in ps), key=lambda p: p[1]):
        yids.append(i)
        ys.append(y)

    sz = n//max(1, floor(sqrt(n)))
    idmap = [[None] * (n//sz+1) for _ in range(n//sz+1)]
    xidmap = [frozenset(xids[i*sz:(i+1)*sz]) for i in range(n//sz+1)]
    yidmap = [frozenset(yids[j*sz:(j+1)*sz]) for j in range(n//sz+1)]

    for line in sys.stdin:
        sx, tx, sy, ty = [int(v) for v in line.split()]
        xmin = bisect_left(xs, sx)
        xmax = bisect_right(xs, tx)
        ymin = bisect_left(ys, sy)
        ymax = bisect_right(ys, ty)

        ids = []
        x1, x2, y1, y2 = xmin//sz, (xmax-1)//sz+1, ymin//sz, (ymax-1)//sz+1
        for i in range(x1, x2):
            xpart = xmin > i*sz or xmax < (i+1)*sz
            for j in range(y1, y2):
                if idmap[i][j] is None:
                    idmap[i][j] = xidmap[i] & yidmap[j]
                ypart = ymin > j*sz or ymax < (j+1)*sz
                if xpart and ypart:
                    ids.extend([p for p in idmap[i][j]
                                if (sx <= ps[p][1] <= tx
                                    and sy <= ps[p][2] <= ty)])
                elif xpart:
                    ids.extend([p for p in idmap[i][j]
                                if (sx <= ps[p][1] <= tx)])
                elif ypart:
                    ids.extend([p for p in idmap[i][j]
                                if (sy <= ps[p][2] <= ty)])
                else:
                    ids.extend(idmap[i][j])

        for v in sorted(ids):
            print(v)
        print()


if __name__ == '__main__':
    run()



Fixed submission:
#!/usr/bin/env pypy3
# DSL_2_C: Range Search(kD Tree)

from bisect import bisect_left, bisect_right
from collections import deque
from functools import lru_cache
from itertools import islice
from math import floor, log2, sqrt
from operator import itemgetter
from sys import stdin, stdout


def sort3(i, j, k):
    if i > j:
        if j > k:
            return (2, 1, 0)
        elif i > k:
            return (1, 2, 0)
        else:
            return (1, 0, 2)
    else:
        if i > k:
            return (2, 0, 1)
        elif j > k:
            return (0, 2, 1)
        else:
            return (0, 1, 2)


def partition(ps, lo, hi, dim):
    mid = (lo + hi) // 2
    ns = (lo, mid, hi)
    n0, n1, n2 = sort3(ps[lo][dim], ps[mid][dim], ps[hi][dim])
    ps[lo], ps[mid], ps[hi] = ps[ns[n1]], ps[ns[n0]], ps[ns[n2]]
    v = ps[lo][dim]
    i, j = lo, hi
    while True:
        i, j = i+1, j-1
        while ps[i][dim] < v:
            i += 1
        while ps[j][dim] > v:
            j -= 1
        if i >= j:
            break
        ps[i], ps[j] = ps[j], ps[i]
    ps[j], ps[lo] = ps[lo], ps[j]
    return j


def sort(ps, lo, hi, dim):
    for i, p in enumerate(sorted(ps[lo:hi+1], key=itemgetter(dim))):
        ps[lo+i] = p


def halve(ps, s, t, dim):
    mid = (s+t) // 2
    while t - s > 100:
        i = partition(ps, s, t, dim)
        if i > mid:
            t = i - 1
        elif i < mid:
            s = i + 1
        else:
            return mid

    sort(ps, s, t, dim)
    return mid


def build(ps, n, sz, _dim):
    q = deque([(0, n-1, 0)])
    while q:
        s, t, lv = q.popleft()
        dim, _ = _dim(lv)
        if t - s < sz:
            sort(ps, s, t, dim)
            continue
        mid = halve(ps, s, t, dim)
        if mid-1 > s:
            q.append((s, mid-1, lv+1))
        if t > mid+1:
            q.append((mid+1, t, lv+1))


def search(ps, vs, n, sz, _dim, s, t):
    q = deque([(0, n-1, 0)])
    ret = []
    while q:
        i, j, lv = q.popleft()
        dim, rdim = _dim(lv)
        sd, td, sr, tr = s[dim], t[dim], s[rdim], t[rdim]
        if j - i < sz:
            left = bisect_left(vs[dim], sd, i, j+1)
            right = bisect_right(vs[dim], td, i, j+1)
            ret.extend([p[2] for p in ps[left:right] if sr <= p[rdim] <= tr])
            continue

        mid = (i+j) // 2
        if td < ps[mid][dim]:
            q.append((i, mid-1, lv+1))
        elif sd > ps[mid][dim]:
            q.append((mid+1, j, lv+1))
        else:
            if sr <= ps[mid][rdim] <= tr:
                ret.append(ps[mid][2])
            q.append((i, mid-1, lv+1))
            q.append((mid+1, j, lv+1))

    ret.sort()
    return ret


def dimension(ps, n):
    @lru_cache(maxsize=n)
    def _dimension(lv):
        return pat[lv % len(pat)]

    cx = len(set([p[0] for p in ps]))
    cy = len(set([p[1] for p in ps]))

    if cx < cy:
        m, s = 1, 0
        ratio = min(cy // cx, floor(log2(n)))
    else:
        m, s = 0, 1
        ratio = min(cx // cy, floor(log2(n)))

    pat = []
    for _ in range(ratio):
        pat.append((m, s))
    pat.append((s, m))

    return _dimension


def run():
    n = int(input())
    sz = floor(sqrt(n))
    ps = []
    for i, line in enumerate(islice(stdin, n)):
        x, y = map(int, line.split())
        ps.append((x, y, i))

    dim = dimension(ps, n)
    build(ps, n, sz, dim)

    input()  # q
    vs = ([p[0] for p in ps], [p[1] for p in ps])
    for line in stdin:
        sx, tx, sy, ty = [int(v) for v in line.split()]
        s = "".join([f"{id_}\n" for id_ in
                     search(ps, vs, n, sz, dim, (sx, sy), (tx, ty))])
        stdout.write(s + "\n")


if __name__ == '__main__':
    run()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env pypy3
# DSL_2_C: Range Search(kD Tree)

import sys
from collections import deque
from functools import lru_cache
from math import floor, log2, sqrt


def sort3(i, j, k):
    if i > j:
        if j > k:
            return (0, 1, 2)
        elif i > k:
            return (0, 2, 1)
        else:
            return (2, 0, 1)
    else:
        if i > k:
            return (1, 0, 2)
        elif j > k:
            return (1, 2, 0)
        else:
            return (2, 1, 0)


def partition(ps, lo, hi, dim):
    mid = (lo+hi)//2
    ns = (lo, mid, hi)
    n0, n1, n2 = sort3(ps[lo][dim], ps[mid][dim], ps[hi][dim])
    ps[lo], ps[mid], ps[hi] = ps[ns[n1]], ps[ns[n2]], ps[ns[n0]]
    i, j = lo, hi
    v = ps[lo][dim]
    while True:
        i, j = i+1, j-1
        while ps[i][dim] < v:
            i += 1
        while ps[j][dim] > v:
            j -= 1
        if i >= j:
            break
        ps[i], ps[j] = ps[j], ps[i]
    ps[j], ps[lo] = ps[lo], ps[j]
    return j


def sort(ps, lo, hi, dim):
    i = lo
    for p in sorted(ps[lo:hi+1], key=lambda p: p[dim]):
        ps[i] = p
        i += 1


def halve(ps, s, t, dim):
    def _halve(lo, hi):
        if hi - lo < 10:
            sort(ps, lo, hi, dim)
            return mid
        i = partition(ps, lo, hi, dim)
        if i > mid:
            return _halve(lo, i-1)
        elif i < mid:
            return _halve(i+1, hi)
        else:
            return mid

    mid = (s+t) // 2
    return _halve(s, t)


def build(ps):
    n = len(ps)
    _dim = dimension(ps)
    q = deque([(0, n-1, 0)])
    while len(q) > 0:
        s, t, lv = q.popleft()
        mid = halve(ps, s, t, _dim(lv))
        if mid-1 > s:
            q.append((s, mid-1, lv+1))
        if t > mid+1:
            q.append((mid+1, t, lv+1))

    return ps, _dim


def search(ps, _dim, s, t):
    n = len(ps)
    stack = [(0, n-1, 0)]
    rev = (1, 0)
    while len(stack) > 0:
        i, j, lv = stack.pop()
        dim = _dim(lv)
        if i > j:
            continue
        mid = (i+j) // 2
        if t[dim] < ps[mid][dim]:
            stack.append((i, mid-1, lv+1))
        elif s[dim] > ps[mid][dim]:
            stack.append((mid+1, j, lv+1))
        else:
            rd = rev[dim]
            if s[rd] <= ps[mid][rd] <= t[rd]:
                yield ps[mid][2]
            stack.append((i, mid-1, lv+1))
            stack.append((mid+1, j, lv+1))


def dimension(ps):
    @lru_cache(maxsize=len(ps))
    def _dimension(lv):
        return pat[lv % len(pat)]

    xs = [p[0] for p in ps]
    ys = [p[1] for p in ps]

    cx = len(set(xs))
    cy = len(set(ys))
    depth = floor(log2(sqrt(len(ps))))

    if cx < cy:
        m, s = 1, 0
        ratio = min(cy // cx, depth)
    else:
        m, s = 0, 1
        ratio = min(cx // cy, depth)

    pat = []
    for i in range(ratio):
        pat.append(m)
    pat.append(s)

    return _dimension


def run():
    n = int(input())
    ps = []
    i = 0
    for line in sys.stdin:
        if i < n:
            x, y = [int(v) for v in line.split()]
            ps.append((x, y, i))
            i += 1
        else:
            break

    dim = dimension(ps)
    base = dim(0)
    trees = []
    size = n//floor(sqrt(n))
    ps.sort(key=lambda p: p[base])
    for i in range((n-1)//size+1):
        min_ = ps[i*size][base]
        max_ = ps[min((i+1)*size-1, n-1)][base]
        tree, dim = build(ps[i*size:(i+1)*size])
        trees.append((tree, dim, min_, max_))

    # q = int(line)
    for line in sys.stdin:
        sx, tx, sy, ty = [int(v) for v in line.split()]
        s, t = (sx, sy)[base], (tx, ty)[base]
        ids = []
        for tree, dim, min_, max_ in trees:
            if max_ < s:
                continue
            elif min_ > t:
                break
            else:
                ids.extend(list(search(tree, dim, (sx, sy), (tx, ty))))

        for v in sorted(ids):
            print(v)
        print()


if __name__ == '__main__':
    run()



Fixed submission:
#!/usr/bin/env pypy3
# DSL_2_C: Range Search(kD Tree)

from bisect import bisect_left, bisect_right
from collections import deque
from functools import lru_cache
from itertools import islice
from math import floor, log2, sqrt
from operator import itemgetter
from sys import stdin, stdout


def sort3(i, j, k):
    if i > j:
        if j > k:
            return (2, 1, 0)
        elif i > k:
            return (1, 2, 0)
        else:
            return (1, 0, 2)
    else:
        if i > k:
            return (2, 0, 1)
        elif j > k:
            return (0, 2, 1)
        else:
            return (0, 1, 2)


def partition(ps, lo, hi, dim):
    mid = (lo + hi) // 2
    ns = (lo, mid, hi)
    n0, n1, n2 = sort3(ps[lo][dim], ps[mid][dim], ps[hi][dim])
    ps[lo], ps[mid], ps[hi] = ps[ns[n1]], ps[ns[n0]], ps[ns[n2]]
    v = ps[lo][dim]
    i, j = lo, hi
    while True:
        i, j = i+1, j-1
        while ps[i][dim] < v:
            i += 1
        while ps[j][dim] > v:
            j -= 1
        if i >= j:
            break
        ps[i], ps[j] = ps[j], ps[i]
    ps[j], ps[lo] = ps[lo], ps[j]
    return j


def sort(ps, lo, hi, dim):
    for i, p in enumerate(sorted(ps[lo:hi+1], key=itemgetter(dim))):
        ps[lo+i] = p


def halve(ps, s, t, dim):
    mid = (s+t) // 2
    while t - s > 100:
        i = partition(ps, s, t, dim)
        if i > mid:
            t = i - 1
        elif i < mid:
            s = i + 1
        else:
            return mid

    sort(ps, s, t, dim)
    return mid


def build(ps, n, sz, _dim):
    q = deque([(0, n-1, 0)])
    while q:
        s, t, lv = q.popleft()
        dim, _ = _dim(lv)
        if t - s < sz:
            sort(ps, s, t, dim)
            continue
        mid = halve(ps, s, t, dim)
        if mid-1 > s:
            q.append((s, mid-1, lv+1))
        if t > mid+1:
            q.append((mid+1, t, lv+1))


def search(ps, vs, n, sz, _dim, s, t):
    q = deque([(0, n-1, 0)])
    ret = []
    while q:
        i, j, lv = q.popleft()
        dim, rdim = _dim(lv)
        sd, td, sr, tr = s[dim], t[dim], s[rdim], t[rdim]
        if j - i < sz:
            left = bisect_left(vs[dim], sd, i, j+1)
            right = bisect_right(vs[dim], td, i, j+1)
            ret.extend([p[2] for p in ps[left:right] if sr <= p[rdim] <= tr])
            continue

        mid = (i+j) // 2
        if td < ps[mid][dim]:
            q.append((i, mid-1, lv+1))
        elif sd > ps[mid][dim]:
            q.append((mid+1, j, lv+1))
        else:
            if sr <= ps[mid][rdim] <= tr:
                ret.append(ps[mid][2])
            q.append((i, mid-1, lv+1))
            q.append((mid+1, j, lv+1))

    ret.sort()
    return ret


def dimension(ps, n):
    @lru_cache(maxsize=n)
    def _dimension(lv):
        return pat[lv % len(pat)]

    cx = len(set([p[0] for p in ps]))
    cy = len(set([p[1] for p in ps]))

    if cx < cy:
        m, s = 1, 0
        ratio = min(cy // cx, floor(log2(n)))
    else:
        m, s = 0, 1
        ratio = min(cx // cy, floor(log2(n)))

    pat = []
    for _ in range(ratio):
        pat.append((m, s))
    pat.append((s, m))

    return _dimension


def run():
    n = int(input())
    sz = floor(sqrt(n))
    ps = []
    for i, line in enumerate(islice(stdin, n)):
        x, y = map(int, line.split())
        ps.append((x, y, i))

    dim = dimension(ps, n)
    build(ps, n, sz, dim)

    input()  # q
    vs = ([p[0] for p in ps], [p[1] for p in ps])
    for line in stdin:
        sx, tx, sy, ty = [int(v) for v in line.split()]
        s = "".join([f"{id_}\n" for id_ in
                     search(ps, vs, n, sz, dim, (sx, sy), (tx, ty))])
        stdout.write(s + "\n")


if __name__ == '__main__':
    run()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env pypy3
# DSL_2_C: Range Search(kD Tree)
# 偏り対策

import sys
from collections import deque
from functools import lru_cache
from math import floor, log2


def sort3(i, j, k):
    if i > j:
        if j > k:
            return (2, 1, 0)
        elif i > k:
            return (1, 2, 0)
        else:
            return (1, 0, 2)
    else:
        if i > k:
            return (2, 0, 1)
        elif j > k:
            return (0, 2, 1)
        else:
            return (0, 1, 2)


def partition(ps, lo, hi, dim):
    mid = (lo + hi) // 2
    ns = (lo, mid, hi)
    n0, n1, n2 = sort3(ps[lo][dim], ps[mid][dim], ps[hi][dim])
    ps[lo], ps[mid], ps[hi] = ps[ns[n1]], ps[ns[n0]], ps[ns[n2]]
    v = ps[lo][dim]
    i, j = lo, hi
    while True:
        # print(mid, i, j, ps[i][dim], ps[j][dim])
        i, j = i+1, j-1
        while ps[i][dim] < v:
            i += 1
        while ps[j][dim] > v:
            j -= 1
        if i >= j:
            break
        ps[i], ps[j] = ps[j], ps[i]
    ps[j], ps[lo] = ps[lo], ps[j]
    return j


def sort(ps, lo, hi, dim):
    for i, p in enumerate(sorted(ps[lo:hi+1], key=lambda p: p[dim])):
        ps[lo+i] = p


def halve(ps, s, t, dim):
    mid = (s+t) // 2
    # while t - s > 100:
    #     i = partition(ps, s, t, dim)
    #     if i > mid:
    #         t = i - 1
    #     elif i < mid:
    #         s = i + 1
    #     else:
    #         return mid

    sort(ps, s, t, dim)
    return mid


def build(ps, _dim):
    n = len(ps)
    q = deque([(0, n-1, 0)])
    while len(q) > 0:
        s, t, lv = q.popleft()
        mid = halve(ps, s, t, _dim(lv))
        if t - s < 100:
            continue
        if mid-1 > s:
            q.append((s, mid-1, lv+1))
        if t > mid+1:
            q.append((mid+1, t, lv+1))


def search(ps, _dim, s, t):
    n = len(ps)
    stack = [(0, n-1, 0)]
    ret = []
    while len(stack) > 0:
        i, j, lv = stack.pop()
        dim = _dim(lv)
        mid = (i+j) // 2
        left, right = t[dim] < ps[mid][dim], s[dim] > ps[mid][dim]
        if j - i < 100:
            if left:
                j = mid-1
            elif right:
                i = mid+1
            ret.extend([p[2] for p in ps[i:j+1]
                        if (s[0] <= p[0] <= t[0] and
                            s[1] <= p[1] <= t[1])])
            continue

        if left:
            stack.append((i, mid-1, lv+1))
        elif right:
            stack.append((mid+1, j, lv+1))
        else:
            if s[0] <= ps[mid][0] <= t[0] and s[1] <= ps[mid][1] <= t[1]:
                ret.append(ps[mid][2])
            stack.append((i, mid-1, lv+1))
            stack.append((mid+1, j, lv+1))

    return ret


def dimension(ps):
    @lru_cache(maxsize=len(ps))
    def _dimension(lv):
        return pat[lv % len(pat)]

    xs = [p[0] for p in ps]
    ys = [p[1] for p in ps]

    cx = len(set(xs))
    cy = len(set(ys))

    if cx < cy:
        m, s = 1, 0
        ratio = min(cy // cx, floor(log2(len(ps))))
    else:
        m, s = 0, 1
        ratio = min(cx // cy, floor(log2(len(ps))))

    pat = []
    for i in range(ratio):
        pat.append(m)
    pat.append(s)

    return _dimension


def run():
    n = int(input())
    ps = []
    i = 0
    for line in sys.stdin:
        if i < n:
            x, y = [int(v) for v in line.split()]
            ps.append((x, y, i))
            i += 1
        else:
            break

    dim = dimension(ps)
    build(ps, dim)

    # q = int(line)
    # fmt = "{}\n"
    for line in sys.stdin:
        sx, tx, sy, ty = [int(v) for v in line.split()]
        # s = "".join([fmt.format(id_) for id_ in sorted(search(ps, dim, (sx, sy), (tx, ty)))])
        s = "".join([f"{id_}\n" for id_ in sorted(search(ps, dim, (sx, sy), (tx, ty)))])
        sys.stdout.write(s + "\n")


if __name__ == '__main__':
    run()



Fixed submission:
#!/usr/bin/env pypy3
# DSL_2_C: Range Search(kD Tree)

from bisect import bisect_left, bisect_right
from collections import deque
from functools import lru_cache
from itertools import islice
from math import floor, log2, sqrt
from operator import itemgetter
from sys import stdin, stdout


def sort3(i, j, k):
    if i > j:
        if j > k:
            return (2, 1, 0)
        elif i > k:
            return (1, 2, 0)
        else:
            return (1, 0, 2)
    else:
        if i > k:
            return (2, 0, 1)
        elif j > k:
            return (0, 2, 1)
        else:
            return (0, 1, 2)


def partition(ps, lo, hi, dim):
    mid = (lo + hi) // 2
    ns = (lo, mid, hi)
    n0, n1, n2 = sort3(ps[lo][dim], ps[mid][dim], ps[hi][dim])
    ps[lo], ps[mid], ps[hi] = ps[ns[n1]], ps[ns[n0]], ps[ns[n2]]
    v = ps[lo][dim]
    i, j = lo, hi
    while True:
        i, j = i+1, j-1
        while ps[i][dim] < v:
            i += 1
        while ps[j][dim] > v:
            j -= 1
        if i >= j:
            break
        ps[i], ps[j] = ps[j], ps[i]
    ps[j], ps[lo] = ps[lo], ps[j]
    return j


def sort(ps, lo, hi, dim):
    for i, p in enumerate(sorted(ps[lo:hi+1], key=itemgetter(dim))):
        ps[lo+i] = p


def halve(ps, s, t, dim):
    mid = (s+t) // 2
    while t - s > 100:
        i = partition(ps, s, t, dim)
        if i > mid:
            t = i - 1
        elif i < mid:
            s = i + 1
        else:
            return mid

    sort(ps, s, t, dim)
    return mid


def build(ps, n, sz, _dim):
    q = deque([(0, n-1, 0)])
    while q:
        s, t, lv = q.popleft()
        dim, _ = _dim(lv)
        if t - s < sz:
            sort(ps, s, t, dim)
            continue
        mid = halve(ps, s, t, dim)
        if mid-1 > s:
            q.append((s, mid-1, lv+1))
        if t > mid+1:
            q.append((mid+1, t, lv+1))


def search(ps, vs, n, sz, _dim, s, t):
    q = deque([(0, n-1, 0)])
    ret = []
    while q:
        i, j, lv = q.popleft()
        dim, rdim = _dim(lv)
        sd, td, sr, tr = s[dim], t[dim], s[rdim], t[rdim]
        if j - i < sz:
            left = bisect_left(vs[dim], sd, i, j+1)
            right = bisect_right(vs[dim], td, i, j+1)
            ret.extend([p[2] for p in ps[left:right] if sr <= p[rdim] <= tr])
            continue

        mid = (i+j) // 2
        if td < ps[mid][dim]:
            q.append((i, mid-1, lv+1))
        elif sd > ps[mid][dim]:
            q.append((mid+1, j, lv+1))
        else:
            if sr <= ps[mid][rdim] <= tr:
                ret.append(ps[mid][2])
            q.append((i, mid-1, lv+1))
            q.append((mid+1, j, lv+1))

    ret.sort()
    return ret


def dimension(ps, n):
    @lru_cache(maxsize=n)
    def _dimension(lv):
        return pat[lv % len(pat)]

    cx = len(set([p[0] for p in ps]))
    cy = len(set([p[1] for p in ps]))

    if cx < cy:
        m, s = 1, 0
        ratio = min(cy // cx, floor(log2(n)))
    else:
        m, s = 0, 1
        ratio = min(cx // cy, floor(log2(n)))

    pat = []
    for _ in range(ratio):
        pat.append((m, s))
    pat.append((s, m))

    return _dimension


def run():
    n = int(input())
    sz = floor(sqrt(n))
    ps = []
    for i, line in enumerate(islice(stdin, n)):
        x, y = map(int, line.split())
        ps.append((x, y, i))

    dim = dimension(ps, n)
    build(ps, n, sz, dim)

    input()  # q
    vs = ([p[0] for p in ps], [p[1] for p in ps])
    for line in stdin:
        sx, tx, sy, ty = [int(v) for v in line.split()]
        s = "".join([f"{id_}\n" for id_ in
                     search(ps, vs, n, sz, dim, (sx, sy), (tx, ty))])
        stdout.write(s + "\n")


if __name__ == '__main__':
    run()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env pypy3
# DSL_2_C: Range Search(kD Tree)
# 偏り対策

from bisect import bisect_left, bisect_right
from collections import deque
from functools import lru_cache
from itertools import islice
from math import floor, log2, sqrt
from operator import itemgetter
from sys import stdin, stdout


def sort3(i, j, k):
    if i > j:
        if j > k:
            return (2, 1, 0)
        elif i > k:
            return (1, 2, 0)
        else:
            return (1, 0, 2)
    else:
        if i > k:
            return (2, 0, 1)
        elif j > k:
            return (0, 2, 1)
        else:
            return (0, 1, 2)


def partition(ps, lo, hi, dim):
    mid = (lo + hi) // 2
    ns = (lo, mid, hi)
    n0, n1, n2 = sort3(ps[lo][dim], ps[mid][dim], ps[hi][dim])
    ps[lo], ps[mid], ps[hi] = ps[ns[n1]], ps[ns[n0]], ps[ns[n2]]
    v = ps[lo][dim]
    i, j = lo, hi
    while True:
        i, j = i+1, j-1
        while ps[i][dim] < v:
            i += 1
        while ps[j][dim] > v:
            j -= 1
        if i >= j:
            break
        ps[i], ps[j] = ps[j], ps[i]
    ps[j], ps[lo] = ps[lo], ps[j]
    return j


def sort(ps, lo, hi, dim):
    for i, p in enumerate(sorted(ps[lo:hi+1], key=itemgetter(dim))):
        ps[lo+i] = p


def halve(ps, s, t, dim):
    mid = (s+t) // 2
    while t - s > 100:
        i = partition(ps, s, t, dim)
        if i > mid:
            t = i - 1
        elif i < mid:
            s = i + 1
        else:
            return mid

    sort(ps, s, t, dim)
    return mid


def build(ps, n, sz, _dim):
    q = deque([(0, n-1, 0)])
    while q:
        s, t, lv = q.popleft()
        dim, _ = _dim(lv)
        if t - s < sz:
            sort(ps, s, t, dim)
            continue
        mid = halve(ps, s, t, dim)
        if mid-1 > s:
            q.append((s, mid-1, lv+1))
        if t > mid+1:
            q.append((mid+1, t, lv+1))


def search(ps, vs, n, sz, _dim, s, t):
    q = deque([(0, n-1, 0)])
    ret = []
    while q:
        i, j, lv = q.popleft()
        dim, rdim = _dim(lv)
        sd, td, sr, tr = s[dim], t[dim], s[rdim], t[rdim]
        if j - i < sz:
            left = bisect_left(vs[dim], sd, i, j+1)
            right = bisect_right(vs[dim], td, i, j+1)
            ret.extend([p[2] for p in ps[left:right] if sr <= p[rdim] <= tr])
            continue

        mid = (i+j) // 2
        if td < ps[mid][dim]:
            q.append((i, mid-1, lv+1))
        elif sd > ps[mid][dim]:
            q.append((mid+1, j, lv+1))
        else:
            if sr <= ps[mid][rdim] <= tr:
                ret.append(ps[mid][2])
            q.append((i, mid-1, lv+1))
            q.append((mid+1, j, lv+1))

    ret.sort()
    return ret


def dimension(ps, n):
    @lru_cache(maxsize=n)
    def _dimension(lv):
        return pat[lv % len(pat)]

    cx = len(set([p[0] for p in ps]))
    cy = len(set([p[1] for p in ps]))

    if cx < cy:
        m, s = 1, 0
        ratio = min(cy // cx, floor(log2(n)))
    else:
        m, s = 0, 1
        ratio = min(cx // cy, floor(log2(n)))

    pat = []
    for _ in range(ratio):
        pat.append((m, s))
    pat.append((s, m))

    return _dimension


def run():
    n = int(input())
    sz = floor(sqrt(n))
    ps = []
    for i, line in enumerate(islice(stdin, n)):
        x, y = [int(v) for v in line.split()]
        ps.append((x, y, i))

    dim = dimension(ps, n)
    build(ps, n, sz, dim)

    input()  # q
    # fmt = "{}\n"
    vs = ([p[0] for p in ps], [p[1] for p in ps])
    for line in stdin:
        sx, tx, sy, ty = [int(v) for v in line.split()]
        # s = "".join([fmt.format(id_) for id_ in
        #              search(ps, dim, (sx, sy), (tx, ty))])
        s = "".join([f"{id_}\n" for id_ in
                     search(ps, vs, n, sz, dim, (sx, sy), (tx, ty))])
        stdout.write(s + "\n")


if __name__ == '__main__':
    run()



Fixed submission:
#!/usr/bin/env pypy3
# DSL_2_C: Range Search(kD Tree)

from bisect import bisect_left, bisect_right
from collections import deque
from functools import lru_cache
from itertools import islice
from math import floor, log2, sqrt
from operator import itemgetter
from sys import stdin, stdout


def sort3(i, j, k):
    if i > j:
        if j > k:
            return (2, 1, 0)
        elif i > k:
            return (1, 2, 0)
        else:
            return (1, 0, 2)
    else:
        if i > k:
            return (2, 0, 1)
        elif j > k:
            return (0, 2, 1)
        else:
            return (0, 1, 2)


def partition(ps, lo, hi, dim):
    mid = (lo + hi) // 2
    ns = (lo, mid, hi)
    n0, n1, n2 = sort3(ps[lo][dim], ps[mid][dim], ps[hi][dim])
    ps[lo], ps[mid], ps[hi] = ps[ns[n1]], ps[ns[n0]], ps[ns[n2]]
    v = ps[lo][dim]
    i, j = lo, hi
    while True:
        i, j = i+1, j-1
        while ps[i][dim] < v:
            i += 1
        while ps[j][dim] > v:
            j -= 1
        if i >= j:
            break
        ps[i], ps[j] = ps[j], ps[i]
    ps[j], ps[lo] = ps[lo], ps[j]
    return j


def sort(ps, lo, hi, dim):
    for i, p in enumerate(sorted(ps[lo:hi+1], key=itemgetter(dim))):
        ps[lo+i] = p


def halve(ps, s, t, dim):
    mid = (s+t) // 2
    while t - s > 100:
        i = partition(ps, s, t, dim)
        if i > mid:
            t = i - 1
        elif i < mid:
            s = i + 1
        else:
            return mid

    sort(ps, s, t, dim)
    return mid


def build(ps, n, sz, _dim):
    q = deque([(0, n-1, 0)])
    while q:
        s, t, lv = q.popleft()
        dim, _ = _dim(lv)
        if t - s < sz:
            sort(ps, s, t, dim)
            continue
        mid = halve(ps, s, t, dim)
        if mid-1 > s:
            q.append((s, mid-1, lv+1))
        if t > mid+1:
            q.append((mid+1, t, lv+1))


def search(ps, vs, n, sz, _dim, s, t):
    q = deque([(0, n-1, 0)])
    ret = []
    while q:
        i, j, lv = q.popleft()
        dim, rdim = _dim(lv)
        sd, td, sr, tr = s[dim], t[dim], s[rdim], t[rdim]
        if j - i < sz:
            left = bisect_left(vs[dim], sd, i, j+1)
            right = bisect_right(vs[dim], td, i, j+1)
            ret.extend([p[2] for p in ps[left:right] if sr <= p[rdim] <= tr])
            continue

        mid = (i+j) // 2
        if td < ps[mid][dim]:
            q.append((i, mid-1, lv+1))
        elif sd > ps[mid][dim]:
            q.append((mid+1, j, lv+1))
        else:
            if sr <= ps[mid][rdim] <= tr:
                ret.append(ps[mid][2])
            q.append((i, mid-1, lv+1))
            q.append((mid+1, j, lv+1))

    ret.sort()
    return ret


def dimension(ps, n):
    @lru_cache(maxsize=n)
    def _dimension(lv):
        return pat[lv % len(pat)]

    cx = len(set([p[0] for p in ps]))
    cy = len(set([p[1] for p in ps]))

    if cx < cy:
        m, s = 1, 0
        ratio = min(cy // cx, floor(log2(n)))
    else:
        m, s = 0, 1
        ratio = min(cx // cy, floor(log2(n)))

    pat = []
    for _ in range(ratio):
        pat.append((m, s))
    pat.append((s, m))

    return _dimension


def run():
    n = int(input())
    sz = floor(sqrt(n))
    ps = []
    for i, line in enumerate(islice(stdin, n)):
        x, y = map(int, line.split())
        ps.append((x, y, i))

    dim = dimension(ps, n)
    build(ps, n, sz, dim)

    input()  # q
    vs = ([p[0] for p in ps], [p[1] for p in ps])
    for line in stdin:
        sx, tx, sy, ty = [int(v) for v in line.split()]
        s = "".join([f"{id_}\n" for id_ in
                     search(ps, vs, n, sz, dim, (sx, sy), (tx, ty))])
        stdout.write(s + "\n")


if __name__ == '__main__':
    run()