Sort By Kth Bit

Given an array or list ARR of N positive integers and an integer K, your task is to rearrange all elements such that those with the K-th bit (considering the rightmost bit as '1st' bit) equal to 0 are followed by those with the K-th bit equal to 1.

Input:

The first line contains a single integer T, the number of test cases. 
Each test case consists of: 
 - A line with two space-separated integers, N and K.
 - A line with N space-separated integers representing the elements of ARR.

Output:

For each test case, return the modified array where all elements with the K-th bit 0 come first, maintaining their relative order, followed by those with the K-th bit 1, also in their original relative order.

Example:

Input:

ARR = {1, 2, 3, 4}, K = 1

Output:

Result = {2, 4, 1, 3}

Explanation:

The first bit (rightmost) of {2, 4} is 0, and the first bit of {1, 3} is 1.

Constraints:

• 1 <= T <= 10
• 1 <= N <= 10^4
• 1 <= ARR[i] <= 10^9
• 1 <= K <= 31

Note: The relative order inside both the groups should remain as it was in the input.

You don’t need to print anything; it has already been taken care of. Just implement the given function.

Follow Up:

Can you do it in linear time?