310875: CF1903D1. Maximum And Queries (easy version)

D1. Maximum And Queries (easy version)time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

This is the easy version of the problem. The only difference between the two versions is the constraint on $n$ and $q$, the memory and time limits. You can make hacks only if all versions of the problem are solved.

Theofanis really likes to play with the bits of numbers. He has an array $a$ of size $n$ and an integer $k$. He can make at most $k$ operations in the array. In each operation, he picks a single element and increases it by $1$.

He found the maximum bitwise AND that array $a$ can have after at most $k$ operations.

Theofanis has put a lot of work into finding this value and was very happy with his result. Unfortunately, Adaś, being the evil person that he is, decided to bully him by repeatedly changing the value of $k$.

Help Theofanis by calculating the maximum possible bitwise AND for $q$ different values of $k$. Note that queries are independent.

Input

The first line contains two integers $n$ and $q$ ($1 \le n, q \le 10^5$ and $n \cdot q \le 10^5$) — the size of the array and the number of queries.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^6$) — the elements of the array.

Next $q$ lines describe the queries. The $i$-th line contains one integer $k_i$ ($0 \le k_i \le 10^{18}$) — the number of operations that can be done in the $i$-th query.

Output

For each query, print one integer — the maximum bitwise AND that array $a$ can have after at most $k_i$ operations.

ExamplesInput

4 2
1 3 7 5
2
10

Output

2
6

Input

3 5
4 0 2
9
8
17
1
3

Output

5
4
7
0
1

Input

1 2
10
5
2318381298321

Output

15
2318381298331

Note

In the first test case, in the first query, we add $1$ in the first and last elements of the array.

Thus, the array becomes $[2,3,7,6]$ with bitwise AND equal to $2$.

In the second test case, in the first query, we add $1$ in the first element, $5$ in the second, and $3$ in the third and now all the elements are equal to $5$.

题目大意：
这是一个关于位运算的题目。给定一个长度为n的数组a和一个整数k，你可以对数组进行最多k次操作，每次操作可以选择数组中的一个元素并将其加1。你的任务是计算在进行最多k次操作后，数组a可能达到的最大按位与（bitwise AND）结果。题目要求对q个不同的k值进行查询，且每个查询是独立的。

输入数据格式：
第一行包含两个整数n和q（1≤n,q≤10^5，n*q≤10^5）——数组的大小和查询的数量。
第二行包含n个整数a_1, a_2, …, a_n（0≤a_i≤10^6）——数组的元素。
接下来q行描述查询。第i行包含一个整数k_i（0≤k_i≤10^18）——第i个查询中可以进行的操作次数。

输出数据格式：
对于每个查询，输出一个整数——在最多进行k_i次操作后，数组a可能达到的最大按位与结果。

示例：
输入：
4 2
1 3 7 5
2
10

输出：
2
6

注意：
在第一个测试案例中，第一个查询中，我们对数组的第一个和最后一个元素加1。因此，数组变为[2,3,7,6]，其按位与等于2。
在第二个测试案例中，第一个查询中，我们对第一个元素加1，第二个元素加5，第三个元素加3，现在所有元素都等于5。题目大意： 这是一个关于位运算的题目。给定一个长度为n的数组a和一个整数k，你可以对数组进行最多k次操作，每次操作可以选择数组中的一个元素并将其加1。你的任务是计算在进行最多k次操作后，数组a可能达到的最大按位与（bitwise AND）结果。题目要求对q个不同的k值进行查询，且每个查询是独立的。 输入数据格式： 第一行包含两个整数n和q（1≤n,q≤10^5，n*q≤10^5）——数组的大小和查询的数量。 第二行包含n个整数a_1, a_2, …, a_n（0≤a_i≤10^6）——数组的元素。 接下来q行描述查询。第i行包含一个整数k_i（0≤k_i≤10^18）——第i个查询中可以进行的操作次数。 输出数据格式： 对于每个查询，输出一个整数——在最多进行k_i次操作后，数组a可能达到的最大按位与结果。 示例： 输入： 4 2 1 3 7 5 2 10 输出： 2 6 注意： 在第一个测试案例中，第一个查询中，我们对数组的第一个和最后一个元素加1。因此，数组变为[2,3,7,6]，其按位与等于2。 在第二个测试案例中，第一个查询中，我们对第一个元素加1，第二个元素加5，第三个元素加3，现在所有元素都等于5。