جمع صديقان $n^2$ من الأصداف على الشاطئ، ورتباها في شبكة مكونة من $n$ صفوف و $n$ أعمدة. ثم رسما بعض الخطوط الأفقية وبعض الخطوط العمودية في الرمل، مما قسّم الشاطئ إلى مناطق تحتوي كل منها على عدد موجب من الأصداف من مجموعتهما.
الآن يلعب الصديقان لعبة نيم (Nim) الشهيرة. يتناوبان في الحركات؛ في كل حركة، يأخذ اللاعب عدداً موجباً من الأصداف من أي منطقة واحدة. اللاعب الذي يأخذ آخر الأصداف يفوز.
يعرف الصديقان أنه لتحديد ما إذا كان لدى اللاعب الأول استراتيجية فوز، وأي حركة هي المثلى، يجب عدّ الأصداف في كل منطقة وحساب عملية XOR البتية (bitwise xor) لهذه الأعداد. يبدو هذا عملاً شاقاً. ساعدهما!
الإدخال
يحتوي السطر الأول من الإدخال على عدد صحيح واحد $n$ ($1 \le n \le 10^6$). نفترض أن الصفوف مرقمة من $1$ إلى $n$ من الأعلى إلى الأسفل، والأعمدة أيضاً مرقمة من $1$ إلى $n$ من اليسار إلى اليمين.
يحتوي السطر الثاني على سلسلة من $n - 1$ أرقام 0 أو 1؛ الرقم $i$ ($1 \le i < n$) يكون 1 إذا كان هناك خط أفقي بين الصف $i$ والصف $i + 1$.
يحتوي السطر الثالث على سلسلة من $n - 1$ أرقام 0 أو 1؛ الرقم $i$ ($1 \le i < n$) يكون 1 إذا كان هناك خط عمودي بين العمود $i$ والعمود $i + 1$.
الإخراج
اطبع عدداً صحيحاً واحداً، وهو ناتج عملية XOR البتية لأعداد الأصداف في جميع المناطق.
مثال
الإدخال
4 001 101
الإخراج
4
ملاحظة
توجد ست مناطق تحتوي على $3, 1, 6, 2, 3, 1$ أصداف على التوالي. ناتج XOR البتي يساوي $3 \oplus 1 \oplus 6 \oplus 2 \oplus 3 \oplus 1 = 4$.
