يحاول مبرمج مشهور أن يؤدي دور ساحر. وتتكون خدعته المميزة مما يلي.
لمصفوفة معطاة من $n$ أعداد صحيحة غير سالبة $a_1,a_2,\ldots,a_n$، يختار بسرعة عددًا سحريًا $b$. يسمى العدد الصحيح غير السالب $b$ سحريًا للمصفوفة إذا أدى تطبيق عملية «أو الحصرية» على مستوى البتات بين هذا العدد وكل عنصر من عناصر المصفوفة إلى تحويلها إلى مصفوفة مرتبة. بعبارة أخرى،
$$ (a_1\oplus b)\le(a_2\oplus b)\le\ldots\le(a_n\oplus b), $$
حيث $\oplus$ هي عملية «أو الحصرية» على مستوى البتات.
لجعل الخدعة أكثر إبهارًا، بعد عرض العدد السحري للمصفوفة المعطاة، ينفذ الساحر الإجراء التالي $q$ مرات. يدعو الجمهور إلى تغيير أحد عناصر المصفوفة، ثم يحاول مجددًا عرض عدد سحري. وقد أتقن المبرمج مهارته كساحر إلى حد أنه يعرض على الجمهور في كل مرة أصغر عدد سحري ممكن. أحيانًا تفشل الخدعة، إذ يستحيل اختيار عدد سحري للمصفوفة الناتجة.
المطلوب كتابة برنامج يحسب أصغر عدد سحري للمصفوفة المعطاة في البداية، وكذلك للمصفوفة الناتجة بعد كل تغيير لعنصر، أو يحدد عدم وجود مثل هذا العدد.
ملاحظة
«أو الحصرية» عملية منطقية يرمز إليها بالعلامة $\oplus$ ويحددها جدول الحقيقة التالي:
| $x$ | $y$ | $x\oplus y$ |
|---|---|---|
| $0$ | $0$ | $0$ |
| $0$ | $1$ | $1$ |
| $1$ | $0$ | $1$ |
| $1$ | $1$ | $0$ |
لنعرّف عملية «أو الحصرية» على مستوى البتات لعددين صحيحين غير سالبين $x$ و$y$. نكتب كلًا من العددين $x$ و$y$ بالنظام الثنائي، ونضيف عند الحاجة أصفارًا بادئة إلى العدد الأقصر حتى يصبح طولاهما متساويين. نتيجة «أو الحصرية» على مستوى البتات للعددين الصحيحين $x$ و$y$، ويرمز إليها أيضًا بـ$x\oplus y$، هي عدد صحيح غير سالب يكون كل بت في تمثيله الثنائي نتيجة عملية «أو الحصرية» بين البتين المناظرين في العددين $x$ و$y$. مثلًا، $5\oplus22=101_2\oplus10110_2=10011_2=19$.
من بين لغات البرمجة المتاحة في الأولمبياد، تستخدم لغة Pascal العامل 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
المهام الفرعية
| المهمة الفرعية | النقاط | القيود على $n$ | القيود على $q$ | القيود على $a_i,v_i$ | المهام الفرعية المطلوبة | النتائج أثناء الجولة |
|---|---|---|---|---|---|---|
| $1$ | $30$ | $1\le n\le500$ | $0\le q\le500$ | $0\le a_i,v_i<2^9$ | نتيجة كل اختبار | |
| $2$ | $29$ | $1\le n\le1000$ | $0\le q\le1000$ | $0\le a_i,v_i<2^{30}$ | $1$ | نتيجة كل اختبار |
| $3$ | $21$ | $1\le n\le10^5$ | $0\le q\le10^5$ | $0\le a_i,v_i<2^{30}$ | $1,2$ | النقاط |
| $4$ | $20$ | $1\le n\le10^6$ | $0\le q\le10^6$ | $0\le a_i,v_i<2^{30}$ | $1$–$3$ | النقاط |