[Solution] ANDfinity Codeforces Solution | Codeforces Problem Solution 2022

[Solution] ANDfinity Codeforces Solution | Codeforces Problem Solution 2022

E. ANDfinity

time limit per test

4 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Bit Lightyear, to the ANDfinity and beyond!

After graduating from computer sciences, Vlad has been awarded an array a1,a2,…,an$a_1,a_2,\dots ,a_n$ of n$n$ non-negative integers. As it is natural, he wanted to construct a graph consisting of n$n$ vertices, numbered 1,2,…,n$1,2,\dots ,n$. He decided to add an edge between i$i$ and j$j$ if and only if ai&aj>0$a_i\mathrm{\&}{a}_j>0$, where &$\mathrm{\&}$ denotes the bitwise AND operation.

Vlad also wants the graph to be connected, which might not be the case initially. In order to satisfy that, he can do the following two types of operations on the array:

1. Choose some element ai$a_i$ and increment it by 1$1$.
2. Choose some element ai$a_i$ and decrement it by 1$1$ (possible only if ai>0$a_i>0$).

Solution Click Below:-  CLICK HERE

It can be proven that there exists a finite sequence of operations such that the graph will be connected. So, can you please help Vlad find the minimum possible number of operations to do that and also provide the way how to do that?

Input

There are several test cases in the input data. The first line contains a single integer t$t$ (1≤t≤1000$1\le t\le 1000$) — the number of test cases. This is followed by the test cases description.
The first line of each test case contains an integer n$n$ (2≤n≤2000$2\le n\le 2000$).

ANDfinity Codeforces Solution

Lena and Matrix Codeforces Solution

Lex String Codeforces Solution

Mystic Permutation Codeforces Solution 

Infected Tree Codeforces Solution

The second line of each test case contains n$n$ integers a1,a2,…,an$a_1,a_2,\dots ,a_n$ (0≤ai<230$0\le a_i<2^{30}$) — the elements of the array.

It is guaranteed that the sum of n$n$ over all test cases does not exceed 2000$2000$.

Output

For each test case, print a single integer m$m$ in the first line — the minimum number of operations. In the second line print the array after a valid sequence of operations that have been done such that the graph from the task becomes connected.

If there are multiple solutions, output any.