Two Logs of the Cave Survey

A cave system branches like a binary tree: every chamber (a distinct integer label) leads to at most two deeper chambers. Two surveyors explored the same cave. The first wrote down each chamber when she first entered it, always exploring the left passage before the right one (a preorder list, pre). The second wrote down each chamber when he left it for the last time, also left before right (a postorder list, post).

Several different caves can produce the same two logs, but that does not matter here. For each query [u, v] return:

• 1 if chamber u is a proper ancestor of v (v lies strictly deeper, inside u's part of the cave),
• -1 if v is a proper ancestor of u,
• 0 otherwise (neither lies inside the other's part, or u == v).

Return the answers as a list in query order. (The answers never depend on which matching cave you imagine.)

Examples

      1
     / \
    2   3
   / \   \
  4   5   6

Input:  pre = [1, 2, 4, 5, 3, 6], post = [4, 5, 2, 6, 3, 1],
        queries = [[1, 5], [5, 2], [4, 6], [3, 3], [3, 6]]
Output: [1, -1, 0, 0, 1]

Input:  pre = [7, 8], post = [8, 7], queries = [[7, 8], [8, 7]]
Output: [1, -1]
Explanation: 8 may hang left or right of 7; either way 7 is its ancestor.

Constraints

• 1 <= len(pre) == len(post) <= 10**5; both lists hold the same distinct labels and come from one binary tree.
• 0 <= len(queries) <= 10**5; every label in a query appears in the tree.
• Target complexity: O(n + q).

Goals

• Read ancestry straight off two traversal orders without rebuilding the tree
• Explain why the answer is the same for every tree matching both logs
• Answer many queries in constant time each after one pass