Horse Teams

Limits: 2 sec., 512 MiB

This statement was translated automatically from Ukrainian.

Zenyk and Marichka have a farm with \(n\) stallions.

The farmers lined up the horses in a row. Each horse has a sign with its favorite non-negative integer. The favorite number of the \(i\)-th horse is \(a_i\).

Zenyk and Marichka want to divide the horses into teams to participate in the 2025 Horse Olympic Games. The farmers will take some horses from the line to the stable. These horses will not participate in the games.

After this, empty spaces will form in the line, separating the horses that were not taken to the stable into segments. Each such segment will form one team.

The strength of a horse team is the bitwise XOR of the favorite numbers of the horses in the team, as written on their signs.

Recall that XOR denotes the bitwise exclusive OR operation. For example, \(13 \text{ XOR } 6 = 11\), because in binary notation \(13_{10} = 1101_2\) and \(6_{10} = 0110_2\), so their XOR is equal to \(1011_2=11_{10}\).

Find the maximum possible sum of the strengths of the horse teams.

If you want to solve the problem for full points, also find which horses need to be taken to the stable to achieve such a sum.

Input

The first line contains an integer \(x\), which is equal to \(0\) or \(1\). If \(x=0\), you only need to find the maximum sum of the strengths of the horse teams. If \(x=1\), besides that you also need to find which horses need to be taken to the stable.

The second line contains an integer \(n\) — the number of horses in the line.

The third line contains \(n\) integers \(a_i\) — the favorite numbers of the horses in the order of the line.

Output

In the first line, print a single integer — the maximum sum of the strengths of the horse teams. If \(x=0\), you should not print anything else — otherwise, your answer will not be graded.

If \(x=1\), in the second line print \(n\) characters 0 and 1 — 0 indicates that the corresponding horse stays in the line, and 1 indicates that the corresponding horse is taken to the stable.

Constraints

\(0 \le x \le 1\),

\(1 \le n \le 2 \cdot 10^5\),

\(0 \le a_i \le 10^9\).

Scoring consists of the following subtasks:

• 1 point for each sample test from the statement,

• 3 points: \(n = 1\), \(x = 0\),

• 4 points: \(n \le 2\), \(x = 0\),

• 10 points: \(n \le 3\), \(x = 0\),

• 10 points: \(n \le 15\), \(x = 0\),

• 17 points: \(n \le 2 \cdot 10^3\), \(x = 0\),

• 22 points: \(a_i \le 63\), \(x = 0\),

• 32 points: without additional constraints.

You will receive points for a subtask only if your program passes all tests in that subtask.

Samples

Input (stdin) сopy	Output (stdout) сopy
1 7 4 8 12 7 3 9 4	32 0010100

Input (stdin) сopy	Output (stdout) сopy
0 4 1 3 5 7	10

Notes

In the first example, it is necessary to take the third and fifth horses to the stable. Then the following horse teams will be formed: \((4, 8)\), \((7)\), and \((9, 4)\).

• The strength of the team \((4, 8)\) is \(4 \text{ XOR } 8 = 12\).

• The strength of the team \((7)\) is \(7\).

• The strength of the team \((9, 4)\) is \(9 \text{ XOR } 4 = 13\).

The sum of the strengths of all teams is \(12 + 7 + 13 = 32\).