圆锥仙人掌

题目背景

圆锥仙人掌：中心节点与3个附加节点相连，每个附加节点都有3个度数为2的附加节点。

题目描述

二叉搜索树（BST，Binary Search Tree），也称二叉排序树或二叉查找树。 二叉搜索树：一棵二叉树，可以为空；如果不为空，满足以下性质：

1. 非空左子树的所有键值小于其根结点的键值。
2. 非空右子树的所有键值大于其根结点的键值。
3. 左、右子树都是二叉搜索树。

以下是在二叉搜索树中插入一个节点的代码：

Node* insert(Node* root, int key) {  
    if (root == nullptr) {  
        return new Node(key);  
    } 
    else {  
        if (key < root->val) {  
            root->left = insert(root->left, key);  
        } 
        else if (key > root->val) {  
            root->right = insert(root->right, key);  
        }  
        return root;  
    }  
}

给定一个排列，多次询问，每次询问先给出一个区间，你需要将序列中该区间内的元素从左往右依次插入一棵二叉搜索树，然后再给若干区间内的下标，你要求出这些下标的节点在树上的父亲的权值。如果下标的节点是树根则认为答案为 0。

你需要解决两种问题。题目会给出一个 $tp$，若 $tp=0$，则每次询问时插入的二叉搜索树初始都是空的；若 $tp=1$，则每次询问时初始的二叉搜索树会继承之前询问的二叉搜索树（即包含之前插入的节点）。

输入格式

第一行两个整数 $tp,n$，分别表示你需要解决的问题类型和序列的长度；

第二行 $n$ 个整数 $a_i$，表示序列的每个元素；

第三行一个整数 $q$，表示询问次数；

接下来 $q$ 行每行包括若干整数：两个整数 $l,r$ 表示依次将下标在 $[l,r]$ 中的元素插入二叉搜索树，一个整数 $k_i$ 表示本次询问的下标数量，$k_i$ 个整数 $x$ 表示每个询问的下标。

输出格式

输出共 $q$ 行，每行 $k_i$ 个整数表示询问的答案。
大样例

数据范围与约定

对于所有数据，保证 $n,q,\sum k_i\le 5\times 10^5,1\le a_i\le n,1\le l \le x\le r \le n,tp=\{0,1\}$。