UOJ Logo Universal Online Judge

UOJ

#682. 【UR #22】月球铁轨

附件下载 统计

伏特再次找到了工程师,请他们设计铁轨。工程师很快给出了一张模板图纸作为候选方案。

图纸上 n 段铁轨排成一行,依次编号为 1,,n。根据工程师们的设计,第 i 段铁轨的尾部只能和第 i+1 段铁轨的头部相连 (1i<n),否则铁轨会变的极为不稳定。

伏特不必铺设所有的铁轨。伏特可以选择一个编号区间,如 [l,r],然后下令只铺设编号在区间 [l,r] 中的铁轨。显然区间的选择方案一共只有 n(n+1)2 种。

跳蚤国拥有独特的材料科学,每段铁轨都可以使用两种材料中的一种构建,稳定度分别为 ai,bi,且不同段铁轨可以使用不同材料。根据工程师们的建模,对于一个区间选择方案 [l,r],如果第 i 段铁轨选择了稳定度为 pi 的材料 (pi{ai,bi}),那么铺设区间 [l,r] 中的所有铁轨的总稳定度为该区间内所有 pi 的异或和,即 plpl+1pr,其中 表示异或。

对于每个区间 [l,r],工程师早已算好了在所有可能的材料选择方案中总稳定度的最大值,称之为该区间的最优稳定度

现在伏特找到了你,希望你能帮工程师们验算一番。请你求出所有可能的区间中,第 k 小的最优稳定度是多少。

输入格式

第一行两个整数 n,k,表示铁轨段数和要求的最优稳定度排名。

第二行 n 个整数,第 i 个整数为 ai,表示使用材料一修建的稳定度。

第三行 n 个整数,第 i 个整数为 bi,表示使用材料二修建的稳定度。

输出格式

一行一个整数表示第 k 小的最优稳定度。

样例一

input

3 3
1 2 3
4 5 6

output

6

explanation

六种区间选择方案对应的最优稳定度分别为

  • 区间 [1,1]: 最优稳定度为 4;
  • 区间 [1,2]: 最优稳定度为 6;
  • 区间 [1,3]: 最优稳定度为 7;
  • 区间 [2,2]: 最优稳定度为 5;
  • 区间 [2,3]: 最优稳定度为 6;
  • 区间 [3,3]: 最优稳定度为 6.

样例二

input

10 1
3 30 30 20 10 4 24 0 17 16
3 3 14 19 26 28 13 13 2 27

output

3

样例三、四、五、六

见附件下载。

样例四,五分别满足特殊性质 A,B

限制与约定

对于 100% 的数据,1n105,1m30,0ai,bi<2m,1kn(n+1)2,其中 m 是用于限定值域的参数。

子任务编号 n m= 特殊性质 分值
1 103 20 10
2 3×104 15
3 105 30 A 15
4 B 15
5 C 15
6 30

特殊性质说明:

  • A: ai,bi (1in) 均在 [0,2m) 范围内独立等概率随机。
  • B: ai=bi (1in)。
  • C: ai=0 (1in)。

时间限制:4s

空间限制:512MB