题目描述

你有一个序列 $a$ ， 有 $q$ 组询问， 每组询问给出 $A, B, C, k, x$， 对于每组询问 ，会得到 一个序列 $b$, 满足 $\texttt{bi = A × popcnt(ai and x) ＋ B × popcnt(ai or x) ＋ C × popcnt(ai xor x)}$ ， 你需查询序列 $b$ 中的第 $k$ 小值。
说明：$popcnt$ 是计算一个整数的二进制表示中有多少位是1。

输入格式

第一行输入 $n， q$ ， 接着第二行输入 $n$ 个正整数， 表示 $a$ 序列 $a_{1} a_{2} … a_{n}$
接下来输入 $q$ 行每行输入五个数 $A, B, C, k ,x$ 。

输出格式

输出 $q$ 行，表示每组询问的答案

样例输入1

5 4
1 2 3 4 5
1 0 0 1 3
1 0 1 5 3
2 7 6 4 7
3 1 9 2 6

样例输出1

0
3
35
14

样例输入2

8 5
123 312 324 412 432 231 321 423
123 231 242 4 233
132 332 313 2 223
313 331 231 8 444
312 222 211 1 999
311 333 222 5 321

样例输出2

3073
4255
5304
3767
3974

数据规模和约定

令 $S = max( max{ ^n_{i=1}} ai , x )$

特殊性质 $A$ ：保证 $B=C=0$ 。

特殊性质 $B$ ：保证 $A=B=0$ 。

特殊性质 $C$ ：保证 $C=0$ 。

对于所有测试数据： $1 \le n\le 10^5, 1 \le q< 2^{16} , 0 \le S,A,B< 2^{16}$ 。