【UR #22】月球铁轨
伏特再次找到了工程师，请他们设计铁轨。工程师很快给出了一张模板图纸作为候选方案。
图纸上 $n$ 段铁轨排成一行，依次编号为 $1, \dots, n$。根据工程师们的设计，第 $i$ 段铁轨的尾部只能和第 $i+1$ 段铁轨的头部相连 $(1\leq i < n)$，否则铁轨会变的极为不稳定。
伏特不必铺设所有的铁轨。伏特可以选择一个编号区间，如 $[l, r]$，然后下令只铺设编号在区间 $[l, r]$ 中的铁轨。显然区间的选择方案一共只有 $\frac{n(n+1)}{2}$ 种。
跳蚤国拥有独特的材料科学，每段铁轨都可以使用两种材料中的一种构建，稳定度分别为 $a_i,b_i$，且不同段铁轨可以使用不同材料。根据工程师们的建模，对于一个区间选择方案 $[l, r]$，如果第 $i$ 段铁轨选择了稳定度为 $p_i$ 的材料 ($p_i \in \{a_i, b_i\}$)，那么铺设区间 $[l, r]$ 中的所有铁轨的总稳定度为该区间内所有 $p_i$ 的异或和，即 $p_l \oplus p_{l+1} \oplus \cdots \oplus p_r$，其中 $\oplus$ 表示异或。
对于每个区间 $[l, r]$，工程师早已算好了在所有可能的材料选择方案中总稳定度的最大值，称之为该区间的最优稳定度。
现在伏特找到了你，希望你能帮工程师们验算一番。请你求出所有可能的区间中，第 $k$ 小的最优稳定度是多少。
输入格式
第一行两个整数 $n, k$，表示铁轨段数和要求的最优稳定度排名。
第二行 $n$ 个整数，第 $i$ 个整数为 $a_i$，表示使用材料一修建的稳定度。
第三行 $n$ 个整数，第 $i$ 个整数为 $b_i$，表示使用材料二修建的稳定度。
输出格式
一行一个整数表示第 $k$ 小的最优稳定度。
3 3
1 2 3
4 5 6
6
六种区间选择方案对应的最优稳定度分别为
- 区间 $[1,1]$: 最优稳定度为 $4$;
- 区间 $[1,2]$: 最优稳定度为 $6$;
- 区间 $[1,3]$: 最优稳定度为 $7$;
- 区间 $[2,2]$: 最优稳定度为 $5$;
- 区间 $[2,3]$: 最优稳定度为 $6$;
- 区间 $[3,3]$: 最优稳定度为 $6$.
10 1
3 30 30 20 10 4 24 0 17 16
3 3 14 19 26 28 13 13 2 27
3
样例三、四、五、六
见附件下载。
样例四，五分别满足特殊性质 A,B
限制与约定
对于 $100\%$ 的数据，$1\leq n\leq 10^5,1\leq m \leq 30,0\leq a_i,b_i\lt 2^m,1\leq k\leq \frac{n(n+1)}{2}$，其中 $m$ 是用于限定值域的参数。
| 子任务编号 | $n\leq$ | $m=$ | 特殊性质 | 分值 |
|---|---|---|---|---|
| 1 | $10^3$ | $20$ | 无 | $10$ |
| 2 | $3\times 10^4$ | $15$ | ||
| 3 | $10^5$ | $30$ | A | $15$ |
| 4 | B | $15$ | ||
| 5 | C | $15$ | ||
| 6 | 无 | $30$ |
特殊性质说明：
- A: $a_i,b_i$ ($1\leq i\leq n$) 均在 $[0,2^m)$ 范围内独立等概率随机。
- B: $a_i=b_i$ ($1\leq i\leq n$)。
- C: $a_i=0$ ($1\leq i\leq n$)。
时间限制：$\texttt{4s}$
空间限制：$\texttt{512MB}$