מתכנת ידוע מנסה את כוחו כאמן אשליות. הקסם המפורסם שלו הוא כדלקמן.

עבור מערך נתון של $n$ מספרים שלמים אי־שליליים $a_1,a_2,\ldots,a_n$, הוא מוצא במהירות מספר קסום $b$. מספר שלם אי־שלילי $b$ נקרא קסום עבור המערך אם הפעלת פעולת XOR סיבית עם מספר זה על כל איבר במערך הופכת אותו למערך ממוין. במילים אחרות,

$$(a_1\oplus b)\le(a_2\oplus b)\le\ldots\le(a_n\oplus b),$$

כאשר $\oplus$ היא פעולת XOR סיבית.

כדי להפוך את הקסם למרשים יותר, לאחר הצגת מספר קסום עבור המערך הנתון, אמן האשליות מבצע את הפעולה הבאה $q$ פעמים. הוא מציע לצופים לשנות אחד מאיברי המערך, ולאחר מכן מנסה שוב להציג מספר קסום. המתכנת שכלל את מיומנותו כאמן אשליות עד כדי כך שבכל פעם הוא מציג לצופים את המספר הקסום הקטן ביותר האפשרי. לפעמים הקסם נכשל, משום שלא ניתן למצוא מספר קסום עבור המערך שהתקבל.

עליכם לכתוב תוכנית אשר מחשבת את המספר הקסום הקטן ביותר עבור המערך ההתחלתי הנתון, וכן עבור המערך המתקבל לאחר כל שינוי של איבר, או קובעת שאין מספר כזה.

הערה

XOR היא פעולה לוגית המסומנת בסימן $\oplus$, המוגדרת באמצעות טבלת האמת הבאה:

נגדיר XOR סיבי עבור שני מספרים שלמים אי־שליליים $x$ ו־$y$. נכתוב כל אחד מהמספרים השלמים $x$ ו־$y$ בבסיס בינארי, ובמידת הצורך נוסיף אפסים מובילים למספר הקצר יותר, עד שאורכם יהיה שווה. XOR סיבי של שני המספרים השלמים $x$ ו־$y$, המסומן גם הוא $x\oplus y$, הוא מספר שלם אי־שלילי שכל סיבית בייצוגו הבינארי היא ה־XOR של הסיביות המתאימות במספרים $x$ ו־$y$. למשל, $5\oplus22=101_2\oplus10110_2=10011_2=19$.

מבין שפות התכנות המוצעות באולימפיאדה, בשפת Pascal משתמשים באופרטור xor לציון XOR; בשפות התכנות האחרות משתמשים באופרטור ^.

קלט

השורה הראשונה של הקלט מכילה מספר שלם $n$ — מספר האיברים במערך ($1\le n\le10^6$).

השורה השנייה מכילה $n$ מספרים שלמים $a_1,a_2,\ldots,a_n$ — איברי המערך ($0\le a_i<2^{30}$).

השורה השלישית מכילה מספר שלם $q$ — מספר השינויים של איבר במערך ($0\le q\le10^6$).

כל אחת מ־$q$ השורות הבאות מכילה שני מספרים שלמים $p_i$ ו־$v_i$, כאשר $p_i$ הוא מספרו של איבר המערך שיש להחליף ($1\le p_i\le n$), ו־$v_i$ הוא ערכו החדש של איבר זה ($0\le v_i<2^{30}$).

פלט

הפלט צריך להכיל $(q+1)$ מספרים שלמים $b_0,b_1,\ldots,b_q$, אחד בכל שורה.

הערך $b_0$ הוא המספר הקסום הקטן ביותר האפשרי עבור המערך ההתחלתי, או $-1$ אם מספר כזה אינו קיים.

עבור $i$ מ־$1$ עד $q$, הערך $b_i$ הוא המספר הקסום הקטן ביותר האפשרי עבור המערך לאחר $i$ השינויים הראשונים, או $-1$ אם מספר כזה אינו קיים.

דוגמאות

קלט 1

3
0 1 4
3
2 7
3 3
1 4

פלט 1

0
2
-1
4

ניקוד