Hai người bạn nhặt được $n^2$ vỏ sò trên bãi biển và xếp chúng thành một lưới gồm $n$ hàng và $n$ cột. Sau đó, họ vẽ một số đường nằm ngang và một số đường thẳng đứng trên cát, chia bãi biển thành các khu vực, mỗi khu vực chứa một số nguyên dương vỏ sò trong bộ sưu tập của họ.
Bây giờ, hai người bạn chơi trò chơi Nim nổi tiếng. Họ lần lượt thực hiện các nước đi; ở mỗi nước đi, một người chơi lấy đi một số lượng dương vỏ sò từ một khu vực bất kỳ. Người chơi lấy những vỏ sò cuối cùng sẽ chiến thắng.
Hai người bạn biết rằng để xác định xem người đi trước có chiến thuật thắng hay không và nước đi nào là tối ưu, ta cần đếm số lượng vỏ sò trong mỗi khu vực và tính tổng XOR theo bit (bitwise xor) của các số này. Nghe có vẻ rất tốn công sức. Hãy giúp họ!
Dữ liệu vào
Dòng đầu tiên của dữ liệu vào chứa một số nguyên $n$ ($1 \le n \le 10^6$). Ta giả sử các hàng được đánh số từ $1$ đến $n$ từ trên xuống dưới. Các cột cũng được đánh số từ $1$ đến $n$ từ trái sang phải.
Dòng thứ hai chứa một xâu gồm $n - 1$ chữ số 0 hoặc 1; chữ số thứ $i$ ($1 \le i < n$) là 1 nếu có một đường nằm ngang giữa hàng $i$ và hàng $i + 1$.
Dòng thứ ba chứa một xâu gồm $n - 1$ chữ số 0 hoặc 1; chữ số thứ $i$ ($1 \le i < n$) là 1 nếu có một đường thẳng đứng giữa cột $i$ và cột $i + 1$.
Kết quả
In ra một số nguyên duy nhất là tổng XOR theo bit của số lượng vỏ sò trong tất cả các khu vực.
Ví dụ
Dữ liệu vào
4 001 101
Kết quả
4
Giải thích
Có sáu khu vực, lần lượt có $3, 1, 6, 2, 3, 1$ vỏ sò. Tổng XOR theo bit bằng $3 \oplus 1 \oplus 6 \oplus 2 \oplus 3 \oplus 1 = 4$.
