P17880 玉兰 / yulan

给定长度为 $n$ 的正整数序列 $a,b$，定义序列 $c$ 的逆康托展开序列为： - 设 $m$ 为序列长度，对于所有 $1\le i\le m$，$c_i\gets \min\{c_i,i\}$； - 构造一个 $1\sim m$ 的排列 $p$，使得对于所有 $1\le i\le m$，均有 $\sum_{j=1}^{i}[p_j\le p_i]=c_i$；可以证明这样的 $p$ 是存在且唯一的，这个排列 $p$ 就是 $c$ 的逆康托展开序列。其中 $[P]$ 在命题 $P$ 成立时为 $1$，否则为 $0$。 $q$ 次查询，每次给定 $l,r,k$，求以 $a_l$ 个 $b_l$，$a_{l+1}$ 个 $b_{l+1}$，$\cdots$，$a_r$ 个 $b_r$ 依次组成的序列的逆康托展开序列中，第 $k$ 个元素的值。 **本题输入经过加密**，输入会给定 $type$，设某次输入的三个数为 $l',r',k'$，设上一次询问的答案为 $lst$（若当前为第一次询问则 $lst=0$），则 $l=l'\oplus (lst\times type),r=r' \oplus (lst\times type),k=k'\oplus (lst\times type)$，其中 $\oplus$ 表示按位异或运算。

输入的第一行包含两个非负整数 $c,type$，分别表示测试点编号和加密参数。$c=0$ 表示该测试点为样例。 第二行包含两个正整数 $n, q$，分别表示序列长度与查询次数。 第三行包含 $n$ 个正整数 $a_1, a_2, \ldots, a_n$。 第四行包含 $n$ 个正整数 $b_1, b_2, \ldots, b_n$。 输入的第 $i+4$ $(1\le i\le q)$ 行包含三个非负整数 $l',r',k'$，分别表示加密后的 $l,r,k$。

对于每次询问，输出一行一个数，表示以 $a_l$ 个 $b_l$，$a_{l+1}$ 个 $b_{l+1}$，$\cdots$，$a_r$ 个 $b_r$ 依次组成的序列的逆康托展开序列中，第 $k$ 个元素的值。

**【样例 1 解释】** 前两次询问的区间均为 $[1,4]$。展开后得到 $[2,2,4,2,2,2,1]$，将第 $i$ 项与 $i$ 取最小值后，得到 $[1,2,3,2,2,2,1]$。对应的排列为 $[2,6,7,5,4,3,1]$，其第 $2$ 项和第 $5$ 项分别为 $6$ 和 $4$。 **【样例 2 解释】** 该样例满足 $type=1$，且序列与解密后的查询都与样例 1 相同。 **【样例 3 解释】** 第一次询问所得到的排列为 $[5\times 10^9,5\times 10^9-1,\ldots,1]$，其中第一个数为 $5\times 10^9$。 **【样例 4】** 见选手目录下的 `yulan/yulan4.in` 与 `yulan/yulan4.ans`。 该样例满足测试点 $1$ 的条件限制。 **【样例 5】** 见选手目录下的 `yulan/yulan5.in` 与 `yulan/yulan5.ans`。 该样例满足测试点 $2$ 的条件限制。 **【样例 6】** 见选手目录下的 `yulan/yulan6.in` 与 `yulan/yulan6.ans`。 该样例满足测试点 $3\sim 4$ 的条件限制。 **【样例 7】** 见选手目录下的 `yulan/yulan7.in` 与 `yulan/yulan7.ans`。 该样例满足测试点 $5\sim 6$ 的条件限制。 **【样例 8】** 见选手目录下的 `yulan/yulan8.in` 与 `yulan/yulan8.ans`。 该样例满足测试点 $7\sim 9$ 的条件限制。 **【样例 9】** 见选手目录下的 `yulan/yulan9.in` 与 `yulan/yulan9.ans`。 该样例满足测试点 $10$ 的条件限制。 **【样例 10】** 见选手目录下的 `yulan/yulan10.in` 与 `yulan/yulan10.ans`。 该样例满足测试点 $11$ 的条件限制。 **【样例 11】** 见选手目录下的 `yulan/yulan11.in` 与 `yulan/yulan11.ans`。 该样例满足测试点 $12\sim 13$ 的条件限制。 **【样例 12】** 见选手目录下的 `yulan/yulan12.in` 与 `yulan/yulan12.ans`。 该样例满足测试点 $14\sim 15$ 的条件限制。 **【样例 13】** 见选手目录下的 `yulan/yulan13.in` 与 `yulan/yulan13.ans`。 该样例满足测试点 $16$ 的条件限制。 **【样例 14】** 见选手目录下的 `yulan/yulan14.in` 与 `yulan/yulan14.ans`。 该样例满足测试点 $17$ 的条件限制。 **【样例 15】** 见选手目录下的 `yulan/yulan15.in` 与 `yulan/yulan15.ans`。 该样例满足测试点 $18\sim 19$ 的条件限制。 **【样例 16】** 见选手目录下的 `yulan/yulan16.in` 与 `yulan/yulan16.ans`。 该样例满足测试点 $20\sim 21$ 的条件限制。 **【样例 17】** 见选手目录下的 `yulan/yulan17.in` 与 `yulan/yulan17.ans`。 该样例满足测试点 $22\sim 25$ 的条件限制。 **【数据范围】** 对于所有测试数据，均有： - $1\le n\le 5\times10^5$； - $1\le q\le 5\times10^5$； - $type\in\{0,1\}$； - 对于所有 $1\le i\le n$，均有 $1\le a_i,b_i\le 10^9$； - 对于每组询问，均有 $1\le l\le r\le n$，$1\le k\le \sum_{i=l}^ra_i$。 ::cute-table{tuack} |测试点编号 |$n,q\le$ |$type=$|特殊性质| |:-------:|:--------:|:-----:|:--:| |$1$ |$18$ |$0$ |A | |$2$ |$500$ |^ |^ | |$3,4$ |$2\,500$ |^ |^ | |$5,6$ |$8\,000$ |^ |^ | |$7\sim 9$|^ |^ |无 | |$10$ |$10^5$ |^ |A | |$11$ |^ |^ |B | |$12,13$ |^ |^ |无 | |$14,15$ |^ |$1$ |^ | |$16$ |$5\times 10^5$|$0$ |A | |$17$ |^ |^ |B | |$18,19$ |^ |^ |无 | |$20,21$ |^ |$1$ |A | |$22\sim 25$ |^ |^ |无 | 特殊性质 A：对于所有 $1\le i\le n$，均有 $a_i=1$。 特殊性质 B：对于所有 $1\le i