AND Lớn Nhất Sau Khi Bật Bit · canuc80k1424

Cho dãy $a_{1}, a_{2}, \dots, a_{n}$ và số nguyên không âm $k$ . Trong một thao tác, bạn chọn một phần tử và một vị trí bit từ $0$ đến $30$ , rồi bật bit đó thành $1$ bằng phép OR với $2^{j}$ .

Được thực hiện không quá $k$ thao tác. Hãy tìm giá trị lớn nhất có thể của

a_{1} & a_{2} & \dots & a_{n} .

Input

Dòng đầu chứa số nguyên $t$ .
Mỗi bộ test gồm một dòng chứa $n, k$ , sau đó một dòng chứa $n$ số nguyên $a_{i}$ .

Output

Với mỗi bộ test, in giá trị AND lớn nhất có thể.

Constraints

$1 \leq t \leq 100$ .
$1 \leq n \leq 2 \cdot 1 0^{5}$ và tổng $n$ không vượt $2 \cdot 1 0^{5}$ .
$0 \leq k \leq 1 0^{9}$ .
$0 \leq a_{i} < 2^{31}$ .

Scoring

Subtask $1$ ( $50$ điểm): $10$ test có ít bit và $n$ nhỏ, cho phép thử mọi mặt nạ đích.
Subtask $2$ ( $50$ điểm): $10$ test đầy đủ; test $19$ có $100$ bộ và tổng $n = 2 \cdot 1 0^{5}$ , test $20$ có một bộ với $n = 2 \cdot 1 0^{5}$ .

Example

Test 1

Input

Output

3
1

Giải thích: Ở bộ đầu, bật bit $1$ của số $1$ và bit $0$ của số $2$ ; khi đó cả ba số đều chứa hai bit thấp, nên AND bằng $3$ . Bộ hai không có thao tác; $7&3&5 = 1$ .

Ý tưởng: Chi phí để bit b xuất hiện trong AND là số phần tử đang có bit b bằng 0. Xét bit từ cao xuống thấp và mua bit nếu chi phí không vượt ngân sách còn lại.
Chứng minh đúng đắn: Mỗi bước của thuật toán duy trì đúng đại lượng hoặc điều kiện nêu trong ý tưởng. Quy tắc chọn được áp dụng độc lập trên từng bit hoặc từng prefix theo đúng hợp đồng; vì vậy mọi phương án bị loại đều không thể tốt hơn, còn phương án được chọn đạt giá trị tối ưu. Suy ra đầu ra của thuật toán là hợp lệ và tối ưu.
Độ phức tạp: Thuật toán đáp ứng cận lớn nhất của đề; phần cài đặt chỉ dùng bộ nhớ tuyến tính theo kích thước input hoặc hằng số theo số bit.