XOR yolu

Verilmiş matris $a$ ölçüsü $n\times n$ olan tam ədədlərdən ibarətdir.

Matrisin sətirləri yuxarıdan aşağıya doğru $1$-dən $n$-ə qədər, sütunları isə soldan sağa doğru $1$-dən $n$-ə qədər nömrələnmişdir. Burada $a_{i,j}$, $i$-ci sətir və $j$-ci sütunun kəsişməsindəki ədədi göstərir.

Siz yolunuza $(1,1)$ hüceyrəsində başlayırsınız və yalnız aşağıya və ya sağa hərəkət edə bilərsiniz. Yol $(n,n)$ hüceyrəsində bitməlidir. Qoy $b_1,b_2,\dots ,b_{2n-1}$ ziyarət etdiyiniz hüceyrələrdə yazılmış tam ədədlər olsun.

Yolun qiyməti $b_1\oplus b_2\oplus \dots \oplus b_{2n-1}$ ifadəsi ilə müəyyən edilir.

$(1,1)$-dən $(n,n)$-ə minimal qiymətli yolu tapın.

Giriş verilənləri

Birinci sətir bir tam ədəd $n(2\le n\le 20)$ — matrisin ölçüsünü ehtiva edir.

Növbəti $n$ sətirin hər biri $n$ tam ədəd $a_{i_1},a_{i_2},\dots ,a_{i_n}(1\le a_{ij}\le 10^9)$ ehtiva edir.

Çıxış verilənləri

Bir tam ədəd çıxarın — yolun mümkün olan minimal qiyməti.

Nümunələr

Qeyd

$x\oplus y$ ifadəsi $x$ və $y$ ədədlərinə bitwise XOR əməliyyatının tətbiqini bildirir. Bu əməliyyat bütün müasir proqramlaşdırma dillərində dəstəklənir, məsələn, C++ və Java dillərində «^», Pascalda isə «xor» kimi göstərilir.