The k-th Badge in Any Department

A company stores staff badge numbers (distinct integers) in a binary search tree. Every node is a manager whose department is the manager together with everybody in their subtree.

You receive queries, a list of pairs (x, k). For each, find the k-th smallest badge number in the department of the manager with badge x (k = 1 is the smallest). If that department has fewer than k people, the answer is -1. Return the answers as a list, in query order.

Examples

            50
          /    \
        30      70
       /  \    /  \
     20   40  60   80
         /  \
       35    45

Input:  root = build_tree([50, 30, 70, 20, 40, 60, 80, None, None, 35, 45]),
        queries = [(30, 3), (70, 1), (30, 6), (50, 7)]
Output: [35, 60, -1, 60]
Explanation: 30's department is 20, 30, 35, 40, 45; its 3rd smallest is 35 and it has no 6th.

Input:  same tree, queries = [(45, 1), (40, 2)]
Output: [45, 40]

Constraints

• 1 <= number of nodes <= 2 * 10**4; the tree may be one long path
• 0 <= len(queries) <= 2 * 10**4; every x is a badge in the tree; 1 <= k <= 10**5
• Walking a department once per query is far too slow for the largest tests.

Goals

• See that a subtree's values form one contiguous block of the sorted order
• Locate that block from a node's inorder position and its left subtree size
• Answer many queries after one linear preprocessing pass