שני חברים אספו $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$.
