class Solution {
    private var tree: [Int] = []

    // Building the segment tree
    private func buildTree(_ start: Int, _ end: Int, _ p: Int) -> Int {
        if start == end {
            tree[p] = 1
            return tree[p]
        }
        let mid = (start + end) / 2
        tree[p] = buildTree(start, mid, 2 * p + 1) + buildTree(mid + 1, end, 2 * p + 2)
        return tree[p]
    }

    // Comparator function for sorting
    private static func cmp(_ a: [Int], _ b: [Int]) -> Bool {
        if a[0] == b[0] {
            return a[1] > b[1]
        }
        return a[0] < b[0]
    }

    // Function to get the index using the segment tree
    private func getIndex(_ start: Int, _ end: Int, _ value: inout Int, _ p: Int, _ index: inout Int) {
        if start > end { return }
        if start == end {
            tree[p] -= 1
            index = start
            return
        }

        let mid = (start + end) / 2
        if tree[2 * p + 1] > value {
            tree[p] -= 1
            getIndex(start, mid, &value, 2 * p + 1, &index)
        } else {
            tree[p] -= 1
            value -= tree[2 * p + 1]
            getIndex(mid + 1, end, &value, 2 * p + 2, &index)
        }
    }

    // Reconstruct the queue using the segment tree
    func reconstructQueue(_ people: [[Int]]) -> [[Int]] {
        var people = people
        people.sort(by: Solution.cmp)

        let n = people.count
        var size = 1
        while size < n {
            size *= 2
        }
        let arrSize = size - 1
        size *= 2
        tree = Array(repeating: 0, count: size)

        buildTree(0, n - 1, 0)
        var res = Array(repeating: [Int](), count: n)

        for person in people {
            var index = 0
            var k = person[1]
            getIndex(0, n - 1, &k, 0, &index)
            res[index].append(person[0])
            res[index].append(person[1])
        }

        return res
    }
}