Кінські команди

Обмеження: 2 сек., 512 МіБ

Зеник з Марічкою мають ферму з $n$ жеребцями.

Фермери вишикували коней у шеренгу. У кожного коня є табличка з його улюбленим невід’ємним цілим числом. Улюблене число $i$-ого коня — $a_i$.

Зеник з Марічкою хочуть поділити коней на команди для участі в Кінських Олімпійських іграх 2025. Фермери відведуть деяких коней із шеренги до стайні. Ці коні не братимуть участі в іграх.

Після цього в шерензі утворяться порожні місця, що розділяють коней, котрих не відвели до стайні, на проміжки. Кожен такий проміжок утворить одну команду.

Силою кінської команди є побітовий XOR улюблених чисел коней у команді, що записані в них на табличках.

Нагадаємо, що XOR позначає операцiю побiтового виключного АБО. Наприклад, $13 \text{ XOR } 6 = 11$, адже в двiйковому записi $13_{10} = 1101_2$, а $6_{10} = 0110_2$, тому їхній XOR дорівнює $1011_2=11_{10}$.

Знайдіть максимальну можливу суму сил кінських команд.

Якщо ви хочете розв’язати задачу на повний бал, також знайдіть, яких коней потрібно відвести до стайні, щоб досягнути такої суми.

Вхідні дані

У першому рядку задано ціле число $x$, яке дорівнює $0$ або $1$. Якщо $x=0$, вам потрібно знайти лише максимальну суму сил кінських команд. Якщо $x=1$, крім цього ви ще повинні знайти, яких коней потрібно відвести до стайні.

У другому рядку задано ціле число $n$ — кількість коней у шерензі.

У третьому рядку записано $n$ цілих чисел $a_i$ — улюблені числа коней у порядку шеренги.

Вихідні дані

У першому рядку виведіть одне ціле число — максимальну суму сил кінських команд. Якщо $x=0$, ви не повинні більше нічого виводити — інакше ваша відповідь не буде зарахована.

Якщо $x=1$, у другому рядку виведіть $n$ символів 0 і 1 — 0 позначає, що відповідний кінь залишиться в шерензі, а 1 позначає, що відповідного коня відведуть до стайні.

Обмеження

$0 \le x \le 1$,

$1 \le n \le 2 \cdot 10^5$,

$0 \le a_i \le 10^9$.

Оцінювання складається з таких блоків:

• по 1 балу за кожен приклад з умови,

• 3 бали: $n = 1$, $x = 0$,

• 4 бали: $n \le 2$, $x = 0$,

• 10 балів: $n \le 3$, $x = 0$,

• 10 балів: $n \le 15$, $x = 0$,

• 17 балів: $n \le 2 \cdot 10^3$, $x = 0$,

• 22 бали: $a_i \le 63$, $x = 0$,

• 32 бали: без додаткових обмежень.

Бали за блок ви отримаєте, тільки якщо ваша програма пройде всі тести з блоку.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
1 7 4 8 12 7 3 9 4	32 0010100

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
0 4 1 3 5 7	10

Примітки

У першому прикладі потрібно відвести до стайні третього та п’ятого коня. Тоді утворяться такі кінські команди: $(4, 8)$, $(7)$ і $(9, 4)$.

• Сила команди $(4, 8)$ дорівнює $4 \text{ XOR } 8 = 12$.

• Сила команди $(7)$ дорівнює $7$.

• Сила команди $(9, 4)$ дорівнює $9 \text{ XOR } 4 = 13$.

Сума сил усіх команд дорівнює $12 + 7 + 13 = 32$.