F. 动物园派对
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

动物园正在举行一场疯狂的动物派对！派对上聚集了来自世界各地的动物，有喜欢美美隐身的鳄鱼 、 躲在地下打洞的老鼠 、 还有到处游走的蜥蜴等 。 它们排成了一排，依次编号为 $$$1$$$ 到 $$$n$$$ 。

为了在嘈杂的派对中保持联系，小动物们需要建立水平激光通讯链路 。 每只小动物 $$$i$$$ 都有一个所在的位置高度 $$$h_i$$$ （例如长颈鹿的高度是正数，而潜水的鳄鱼高度可能是负数） ， 以及一个通讯频段特征值 $$$a_i$$$ 。

当小动物 $$$l$$$ 和小动物 $$$r$$$ （ $$$1 \le l \lt r \le n$$$ ） 尝试进行通讯时，为了保证信号不被中间的动物挡住，通讯信号所在的有效高度 $$$H$$$ 取决于它们之间 （包含它们自己） 所有动物的最低高度，即： $$$$$$H = \min_{i=l}^r h_i$$$$$$

同时，派对专门的环境会对通讯产生干扰，干扰系数为一个常数 $$$K$$$ 。 链路的通讯强度不仅与有效高度有关，还受到两只动物频段异或值的影响。具体来说，它们之间的通讯强度定义为： $$$$$$S(l, r) = H \times ( ( a_l \oplus a_r ) - K )$$$$$$ 其中 $$$\oplus$$$ 表示按位异或运算 。

现在派对到达了高潮，请你作为动物园的网络管理员，计算出在所有可能的通讯对 $$$(l, r)$$$ 中，通讯强度的 最大值 是多少。

Input

第一行包含一个整数 $$$T$$$ （ $$$1 \le T \le 10^4$$$ ） ， 表示测试数据的组数 。

对于每组测试数据： 第一行包含两个整数 $$$n$$$ 和 $$$K$$$ （ $$$2 \le n \le 2 \cdot 10^5$$$ ， $$$0 \le K \lt 2^{31}$$$ ） ， 分别表示小动物的数量和环境干扰系数 。

第二行包含 $$$n$$$ 个整数 $$$h_1, h_2, \dots, h_n$$$ （ $$$-10^8 \le h_i \le 10^8$$$ ） ， 表示每只小动物所在的高度 。

第三行包含 $$$n$$$ 个整数 $$$a_1, a_2, \dots, a_n$$$ （ $$$0 \le a_i \lt 2^{31}$$$ ） ， 表示每只小动物的通讯频段特征值 。

数据保证所有测试数据的 $$$\sum n \le 2 \cdot 10^5$$$ 。

Output

对于每组测试数据，输出一行，包含一个整数，表示所有通讯对中通讯强度的最高值 。

Example
Input
2
5 10
10 -10 10 -10 10
12 5 2 8 14
3 8
2 -5 3
8 9 1
Output
80
35
Note

对于第一组测试数据： $$$n = 5$$$ ， $$$K = 10$$$ 。

当 $$$l = 1$$$ , $$$r = 5$$$ 时，它们之间的最低高度 $$$H = \min(10, -10, 10, -10, 10) = -10$$$ 。

频段异或值为 $$$a_1 \oplus a_5 = 12 \oplus 14 = 2$$$ 。

通讯强度为 $$$S(1, 5) = -10 \times (2 - 10) = -10 \times (-8) = 80$$$ ，这是所有组合中的最高值 。