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

Обмеження: 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\).