Dua orang teman mengumpulkan $n^2$ kerang di sebuah pantai, lalu menyusunnya dalam sebuah kisi berukuran $n$ baris dan $n$ kolom. Mereka kemudian menggambar beberapa garis horizontal dan beberapa garis vertikal di pasir, yang membagi pantai menjadi beberapa zona, dengan sejumlah positif kerang dari koleksi mereka di setiap zona.
Sekarang, kedua teman tersebut memainkan permainan Nim yang terkenal. Mereka melangkah secara bergantian; pada setiap langkah, seorang pemain mengambil sejumlah positif kerang dari satu zona mana saja. Pemain yang mengambil kerang terakhir menang.
Kedua teman itu tahu bahwa untuk menentukan apakah pemain pertama memiliki strategi menang dan langkah mana yang optimal, mereka harus menghitung jumlah kerang di setiap zona lalu menghitung bitwise xor dari bilangan-bilangan tersebut. Itu terdengar seperti pekerjaan yang sangat melelahkan. Bantulah mereka!
Masukan
Baris pertama masukan berisi satu bilangan bulat $n$ ($1 \le n \le 10^6$). Kita asumsikan baris-baris dinomori $1$ sampai $n$ dari atas ke bawah. Kolom-kolom juga dinomori $1$ sampai $n$ dari kiri ke kanan.
Baris kedua berisi string sepanjang $n - 1$ digit 0 atau 1; digit ke-$i$ ($1 \le i < n$) bernilai 1 jika terdapat garis horizontal di antara baris $i$ dan baris $i + 1$.
Baris ketiga berisi string sepanjang $n - 1$ digit 0 atau 1; digit ke-$i$ ($1 \le i < n$) bernilai 1 jika terdapat garis vertikal di antara kolom $i$ dan kolom $i + 1$.
Keluaran
Keluarkan satu bilangan bulat, yaitu hasil bitwise xor dari jumlah kerang di semua zona.
Contoh
Masukan
4 001 101
Keluaran
4
Catatan
Terdapat enam zona yang masing-masing memiliki $3, 1, 6, 2, 3, 1$ kerang. Nilai bitwise xor-nya sama dengan $3 \oplus 1 \oplus 6 \oplus 2 \oplus 3 \oplus 1 = 4$.
