يتعلم 小 Z بنفسه المعارف المتعلقة بالحواسيب الكمية. وقد كان مؤخرًا يدرس فصل الاتصالات الكمية، فواجه مسألة مثيرة للاهتمام. فيها، يتواصل Alice وBob اتصالًا كميًا، ولغة تواصلهما قاموس $S$ حجمه $n$، ويمكن تمثيل كل كلمة $s_i$ فيه، حيث $1\leq i\leq n$، بسلسلة ثنائية طولها 256 بت. في هذه المسألة، يمكن توليد $s_i$ باستدعاء الدالة gen الموجودة في gen.cpp في دليل المسألة، وتُعطى معاملات هذه الدالة n وa1 وa2 في الإدخال.
سيجري Alice وBob عددًا من الاتصالات يساوي $m$، وفي كل اتصال يرسل Alice إلى Bob كلمة واحدة بالضبط من القاموس. لكن قناة اتصالهما غير موثوقة وتتأثر بالضوضاء. وبصورة أدق، في الإرسال رقم $i$، لتكن الكلمة الأصلية التي أرسلها Alice هي $x_i$. قد تقلب الضوضاء عددًا من البتات لا يتجاوز $k_i$ في هذه السلسلة. وبعبارة أخرى، إذا كانت السلسلة التي استقبلها Bob هي $y_i$، فقد تختلف عن $x_i$ في عدد أقصاه $k_i$ من البتات، وقد لا تظهر $y_i$ في القاموس $S$.
وفي الوقت نفسه، علم Bob أن الشرير Eve تسلل إلى قناة الاتصال ويستعد للتشويش عليهما. وطريقته هي تغيير السلسلة الثنائية التي يستقبلها Bob إلى أي سلسلة ثنائية طولها 256 بت، وقد لا تظهر هذه السلسلة في القاموس $S$. Eve ماكر جدًا، وليس من الضروري أن يشوش كل اتصال.
استعان Bob بك الآن. لكل اتصال مقبل، يجب أن تحدد، بالاعتماد على السلسلة الثنائية التي استقبلها Bob في النهاية وحد الضوضاء $k_i$، حيث $0\leq k_i\leq15$، هل من الممكن ألا يكون Eve قد شوش هذا الاتصال، أي هل يمكن الحصول على السلسلة المستقبلة بقلب عدد لا يتجاوز $k_i$ من بتات إحدى كلمات القاموس. إذا كان ذلك ممكنًا، فأخرج $1$، وإلا فأخرج $0$. يثق Bob بقدرتك، ولذلك يجب أن تجيب الاستعلامات بالتتابع أثناء قراءتها، وفق التفاصيل في صيغة الإدخال.
لتقليل زمن القراءة، تُعطى السلاسل التي يستقبلها Bob كسلاسل ست عشرية طولها 64 محرفًا، تحتوي على المحارف 0 إلى 9 والأحرف الإنجليزية الكبيرة A إلى F، حيث تمثل A إلى F القيم من $10$ إلى $15$ على التوالي.
يمكن تحويل السلسلة الست عشرية إلى سلسلة ثنائية محرفًا بمحرف. فمثلًا، يقابل 5 السلسلة 0101، ويقابل A السلسلة 1010، ويقابل C السلسلة 1100.
الإدخال
اقرأ البيانات من الملف qi.in.
يحتوي السطر الأول من الإدخال على أربعة أعداد صحيحة غير سالبة $n,m,a_1,a_2$، تمثل حجم القاموس، وعدد الاتصالات، والقيمتين الابتدائيتين للمعاملين a1 وa2 في الدالة gen على التوالي.
يجب أن تستدعي في برنامجك الدالة gen المذكورة في وصف المسألة لتوليد قائمة الكلمات. ويمكنك نسخ الكود في gen.cpp واستخدامه، وتمثل المصفوفة المنطقية s[N+1][256] في البرنامج جميع الكلمات.
يحتوي كل من الأسطر $m$ التالية على سلسلة ست عشرية طولها 64 محرفًا وعدد صحيح غير سالب $k_i$، يمثلان السلسلة الثنائية التي استقبلها Bob في النهاية في الاتصال رقم $i$ وحد الضوضاء على التوالي.
لإجبارك على الإجابة بالتتابع، بعد استعادة السلسلة الثنائية ذات 256 بت من السلسلة الست عشرية، يجب تطبيق أو الحصرية مع $lastans$ على كل بت منها للحصول على السلسلة الحقيقية التي استقبلها Bob في هذا الاتصال. حيث $lastans\in\{0,1\}$ إجابة الاستعلام السابق، وقيمته الابتدائية قبل الاستعلام الأول هي $0$.
انتبه: عند استخدام الدالتين scanf وprintf لقراءة متغيرات النوع unsigned long long أو إخراجها، يكون محدد التنسيق المقابل هو llu.
الإخراج
اكتب الإخراج إلى الملف qi.out.
أخرج $m$ سطرًا، يحتوي كل سطر على عدد صحيح $0$ أو $1$، يمثل إجابة الاستعلام الحالي.
أمثلة على الاستعلامات
لتسهيل شرح المسألة، نعرض حالة مبسطة تُعطى فيها كلمات القاموس مباشرة، ويُقلص طول الكلمات إلى 4، ويُسمح بالإجابة عن الاستعلامات دون اشتراط التتابع أثناء القراءة.
افترض قاموسًا حجمه $n=2$، وكلمتاه 1010 و0111.
للاستعلام B = 1011 و$k_1=1$، يجب أن تكون الإجابة $1$، إذ يمكن الحصول عليه بقلب البت الرابع من 1010، مع ترقيم البتات من الأعلى أهمية إلى الأدنى، وكذلك فيما يلي.
للاستعلام 1 = 0001 و$k_2=2$، يجب أن تكون الإجابة $1$، إذ يمكن الحصول عليه بقلب البتين الثاني والثالث من 0111.
للاستعلام 1 = 0001 و$k_3=1$، يجب أن تكون الإجابة $0$.
- بقلب بت واحد على الأكثر من
1010، يمكن الحصول على1010و0010و1110و1000و1011. - بقلب بت واحد على الأكثر من
0111، يمكن الحصول على0111و1111و0011و0101و0110. - لا يمكن الحصول على
1 = 0001، فلا بد أن يكون قد نتج عن تشويش Eve.
أمثلة
مثال 1
راجع الملفين qi/qi1.in وqi/qi1.ans في دليل المتسابق.
مثال 2
راجع الملفين qi/qi2.in وqi/qi2.ans في دليل المتسابق.
مثال 3
راجع الملفين qi/qi3.in وqi/qi3.ans في دليل المتسابق.
القيود
لجميع حالات الاختبار: $1\leq n\leq4\times10^5$، و$1\leq m\leq1.2\times10^5$، و$0\leq k\leq15$، وتُولد $a_1,a_2$ عشوائيًا بانتظام في المجال $[0,2^{64}-1]$.
| رقم حالة الاختبار | $n=$ | $m=$ | $k_i\leq$ | خصائص خاصة |
|---|---|---|---|---|
| $1$ | $10$ | $10$ | $2$ | لا شيء |
| $2$ | $500$ | $500$ | $15$ | |
| $3$ | $1000$ | $1000$ | $0$ | |
| $4$ | $2000$ | $2000$ | $2$ | |
| $5$ | $5000$ | $5000$ | $15$ | |
| $6$ | $10000$ | $10000$ | ||
| $7$ | $20000$ | $20000$ | ||
| $8$ | $100000$ | $100000$ | $1$ | |
| $9$ | $400000$ | $120000$ | ||
| $10$ | $50000$ | $50000$ | $2$ | |
| $11$ | $70000$ | $70000$ | $3$ | |
| $12$ | $100000$ | $100000$ | $2$ | |
| $13$ | $30000$ | $30000$ | $5$ | |
| $14$ | $60000$ | $60000$ | $4$ | |
| $15$ | $120000$ | $120000$ | $5$ | |
| $16$ | $60000$ | $60000$ | $8$ | جميع سلاسل الاستعلامات مولدة عشوائيًا |
| $17$ | $120000$ | $120000$ | $12$ | |
| $18$ | $400000$ | $100000$ | $15$ | |
| $19$ | $30000$ | $30000$ | $7$ | لا شيء |
| $20$ | $60000$ | $60000$ | $9$ | |
| $21$ | $90000$ | $90000$ | $11$ | |
| $22$ | $200000$ | $120000$ | $12$ | |
| $23$ | $400000$ | $80000$ | $15$ | |
| $24$ | $400000$ | $100000$ | ||
| $25$ | $400000$ | $120000$ |