XOR шлях#9088
Дана матриця розміру n \times n, що складається з цілих чисел.
Рядки матриці пронумеровані зверху вниз від до , а стовпці — зліва направо від до . Позначимо через a_{i,j} елемент, розташований на перетині -го рядка та -го стовпця.
Ви починаєте шлях у клітинці і можете переміщатися лише вниз або вправо. Шлях має завершуватися в клітинці . Нехай b_1, b_2, \ldots, b_{2n-1} — послідовність цілих чисел, записаних у клітинках, які ви відвідали в порядку проходження по шляху.
Ціна шляху визначається виразом b_1 \oplus b_2 \oplus \ldots \oplus b_{2n-1}.
Знайдіть такий шлях від до , для якого ціна мінімальна.
Перший рядок містить одне ціле число n~(2 \le n \le 20) — розмір матриці.
Кожен з наступних рядків містить по цілих чисел a_{i_1}, a_{i_2}, \ldots, a_{i_n}~(1 \le a_{ij} \le 10^9) — елементи матриці.
Виведіть одне ціле число — мінімально можливу ціну шляху.
Приклад 1
Приклад 2
Вираз x \oplus y позначає застосування побітової операції XOR до чисел та . Ця операція підтримується у всіх сучасних мовах програмування. Наприклад, у мовах C++ та Java вона позначається як ^, а в Pascal — як xor.