小 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$ היא $x_i$, הרעש יכול להפוך לכל היותר $k_i$ סיביות בה. כלומר, המחרוזת הבינארית $y_i$ שקיבל Bob עשויה להיות שונה מ־$x_i$ בלכל היותר $k_i$ סיביות, וייתכן שאינה מופיעה במילון $S$.

בינתיים מגלה Bob שהנבל Eve חדר גם הוא לערוץ ומתכנן לשבש את התקשורת. הוא יכול לשנות את המחרוזת שקיבל Bob לכל מחרוזת בינארית בת $256$ סיביות, שגם היא עשויה לא להופיע במילון $S$. Eve ערמומי מאוד, והוא לא בהכרח משבש כל שידור.

כעת Bob מבקש את עזרתכם. לכל שידור עליכם לקבוע, לפי המחרוזת הסופית שקיבל ולפי סף הרעש $k_i$, כאשר $0\leq k_i\leq15$, אם ייתכן שהשידור לא שובש על ידי Eve. כלומר, האם אפשר לקבל את המחרוזת שקיבל Bob על ידי הפיכת לכל היותר $k_i$ סיביות במילה כלשהי במילון? אם ייתכן שלא היה שיבוש של Eve, הדפיסו $1$; אחרת הדפיסו $0$. Bob סומך על יכולתכם, ולכן עליכם לענות על השאילתות באופן מקוון, לפי הדרישות בפורמט הקלט.

כדי להפחית את זמן הקריאה, המחרוזות שקיבל Bob ניתנות כמחרוזות הקסדצימליות באורך $64$. הן מכילות את הספרות 0 עד 9 ואת האותיות האנגליות הגדולות 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$ סיביות יש לבצע XOR של כל סיבית עם $lastans$ כדי לקבל את המחרוזת האמיתית שקיבל Bob בשידור הזה. כאן $lastans\in\{0,1\}$ הוא התשובה לשאילתה הקודמת, וערכו ההתחלתי לפני השאילתה הראשונה הוא $0$.

שימו לב: בעת שימוש ב־scanf וב־printf לקריאה או לכתיבה של משתנים מסוג unsigned long long, מציין הפורמט המתאים הוא llu.

פלט

יש לכתוב את הפלט לקובץ qi.out.

יש להדפיס $m$ שורות, ובכל אחת מספר שלם $0$ או $1$ המציין את התשובה לשאילתה הנוכחית.

דוגמאות לשאילתות

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

נניח שגודל המילון $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]$.