맛을 찾아서
시간 제한3초메모리 제한512 MB
N개의 수 중 최대 K개를 골라 비트wise OR 값을 최대로 만드는 문제입니다.
문제
Fouad는 식당에 갔고, 메뉴를 읽던 중 각 음식에 대한 흥미로운 정보를 발견했다. 그 정보는 각 음식이 포함하는 맛이었다.
메뉴에는 N개의 음식이 있고, 각 음식은 정수 Ai로 표현된다. Ai의 이진 표현에서 j번째 비트는 이 음식에 j번째 맛이 있는지 나타낸다(1이면 먹을 때 j번째 맛을 느끼고, 0이면 느끼지 않는다).
여러 음식을 먹을 때, 그중 하나라도 j번째 비트가 1이면 j번째 맛을 느낀다. 즉, 음식 Ai와 Aj를 먹어서 얻는 맛은 Ai | Aj의 맛과 같다. 여기서 |는 비트 OR 연산이다.
Fouad는 음식을 최대한 즐기기 위해 많은 음식을 먹고 싶지만, 엄격한 식단 때문에 K개를 초과하여 먹을 수 없다. 모든 맛이 같은 가치를 가지는 것은 아니므로, 그는 K개 이하의 음식을 골라 전체 음식을 나타내는 수가 최대가 되도록(고른 음식들의 비트 OR이 최대가 되도록) 도움을 청하고 있다.
입력
첫 줄에는 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스는 공백으로 구분된 두 정수 N, K가 있는 줄로 시작한다(20 ≤ K ≤ N ≤ 105).
테스트 케이스의 둘째 줄에는 N개의 공백으로 구분된 정수 A1, ..., AN이 있다(모든 i에 대해 0 ≤ Ai ≤ 106).
출력
각 테스트 케이스마다, Fouad가 K개 이하의 음식을 먹어 느낄 수 있는 맛의 최댓값을 나타내는 정수 X를 한 줄에 출력한다. Fouad가 먹을 음식 집합에 i번째 맛이 포함되면 X의 i번째 비트는 1이어야 하고, 그렇지 않으면 0이어야 한다.
힌트
예제에서는 모든 음식을 먹을 수 있으므로, 결과는 주어진 모든 수의 비트 OR이다.