זוהי בעיה אינטראקטיבית.

על הדלפק בחנות הקינוחים של הפרעושים מונחות שתי שורות של ג׳לי צבעוני בעל שתי שכבות (השכבה העליונה היא $a$, והתחתונה היא $b$). לפי כלל ״ההתמצקות המשלימה״ של החנות, סכום הגבהים של השכבה העליונה והתחתונה בכל זוג הוא בדיוק $n+1$. בתחילה העובדים כבר סידרו את שתי השורות לפי הגובה, כך שכל אחת הייתה תמורה מושלמת של $1 \sim n$, אך אמש עובד פרעוש נמרץ הפך בטעות את השכבה העליונה והתחתונה בחלק מהמיקומים!

כעת פסטיבל הקינוחים השנתי עומד להיפתח, והעובדים חייבים לשחזר את סידור הג׳לי המקורי, לפני ההיפוכים (כלומר, את סדרת גבהי השכבה העליונה $a$ לפני ההיפוכים).

אינכם יכולים לצפות ישירות בגובה הג׳לי, אך אתם יכולים לשלוח הוראות למכשיר המדידה האוטומטי של החנות: ציינו כמה מיקומים $i$, והמכשיר יחליף עבורכם את השכבה העליונה והתחתונה במיקומים האלה. הוא יחזיר את ההפרש בין הגובה המרבי לגובה המזערי (הטווח) בשכבה העליונה הנוכחית, וכן את ההפרש בין הגובה המרבי לגובה המזערי (הטווח) בשכבה התחתונה. שימו לב: השפעתו של כל היפוך נשמרת.

האם תוכלו לשחזר בהצלחה את סדרת הסידור המקורית של השכבה העליונה באמצעות מספר מוגבל של מדידות הכרוכות בהיפוכים?

הספרייה האינטראקטיבית בוחרת תחילה תמורה $p$ של $1\sim n$, ובונה את התמורה $b_i=n+1-p_i$. לאחר מכן, עבור כל אינדקס $i$, הספרייה מחליטה באופן בלתי תלוי אם להחליף בין שני המספרים במיקום $i$. נסמן את המערכים המתקבלים לאחר ההחלפות ב־$a,b$. בשלב זה תמיד מתקיים $a_i+b_i=n+1$, אך $a,b$ אינם בהכרח תמורות עוד.

אתם יודעים את $n$, אך אינכם יודעים את שני המערכים האלה. אתם יכולים לבחור כמה מיקומים ולהחליף בהם בין $a_i,b_i$; הספרייה האינטראקטיבית תמסור לכם את הטווח של כל אחד משני המערכים לאחר ההחלפות. השפעתה של כל החלפה נשמרת.

משימתכם היא לשחזר את המערך $a$ כפי שהיה לפני השאילתה הראשונה. גם אם המערך המוחזר שווה למערך המבוקש רק לאחר החלפת כל ערך $x$ בו, בו־זמנית, ב־$n+1-x$, התשובה נחשבת נכונה.

פרטי מימוש

אינכם צריכים, וגם אינכם אמורים, לממש את הפונקציה main.

עליכם לכלול את קובץ הכותרת range.h בקובץ המקור recover.cpp, ולממש את הפונקציה הבאה:

std::vector<int> recover(int c, int n);

• $c$ הוא מספר תת־המשימה הנוכחית: בבדיקות הרשמיות ערכו הוא $1,2,3,4$, ובדוגמה ערכו הוא $0$. $n$ הוא אורך המערך. הספרייה האינטראקטיבית קוראת ל־recover בדיוק פעם אחת בכל מקרה בדיקה.
• הערך המוחזר חייב להיות מערך של מספרים שלמים באורך $n$, המייצג את $a$ לפני השאילתה הראשונה, או את המשלים של המערך כולו.

אתם יכולים לקרוא לפונקציה הבאה:

std::pair<int, int> query(const std::vector<int>& positions);

• האינדקסים ב־positions חייבים להיות שונים זה מזה ולהשתייך ל־$[0,n-1]$. מותר להעביר מערך ריק.
• הספרייה האינטראקטיבית מחליפה פעם אחת בין הערכים הנוכחיים $a_i,b_i$ בכל אחד מהאינדקסים ב־positions, ואז מחזירה את הטווח של $a$ הנוכחי ואת הטווח של $b$ הנוכחי. ההחלפות מצטברות בין השאילתות, אך בעת החזרת התשובה יש לשחזר את המערך ההתחלתי, לפני ההחלפות.
• הטווח מוגדר כערך המרבי במערך פחות הערך המזערי בו. מכיוון שתמיד מתקיים $b_i=n+1-a_i$, שני הטווחים בהכרח שווים.
• מספר הקריאות ל־query אינו יכול לעלות על המגבלה $Q_{\max}$ של מקרה הבדיקה הנוכחי.

הספרייה האינטראקטיבית אינה אדפטיבית: המערכים ההתחלתיים נקבעים לפני תחילת recover, ואינם משתנים בהתאם לשאילתות שלכם. הספרייה האינטראקטיבית המשמשת להערכה הסופית עשויה להיות שונה מספריית הדוגמה המסופקת; אסור לתוכניתכם לקרוא נתונים פנימיים של הספרייה או לפעול ישירות על זרמי הקלט והפלט הסטנדרטיים.

בדיקת התוכנית

הניחו את recover.cpp, את range.h ואת grader.cpp שבקבצים המצורפים באותה תיקייה, והדרו באמצעות C++17:

g++ grader.cpp recover.cpp -o recover -O2 -std=c++17
./recover < ex_range1.in

השורה הראשונה שהספרייה האינטראקטיבית המקומית קוראת מכילה את $c,n,Q_{\max}$; השורה השנייה מכילה את התמורה $p_0,\ldots,p_{n-1}$; והשורה השלישית מכילה $n$ מספרים מסוג $0/1$, כאשר $1$ מציין שבוצעה החלפה במיקום זה לפני תחילת האינטראקציה. רק $c,n$ נמסרים לכם באמצעות פרמטרי הפונקציה; התמורה, סימוני ההחלפות ומגבלת השאילתות אינם נמסרים ישירות לתוכניתכם.

אם התשובה נכונה, הספרייה האינטראקטיבית המקומית מדפיסה Correct! בשורה הראשונה ו־Queries used: Q בשורה השנייה, כאשר $Q$ הוא מספר השאילתות שבהן נעשה שימוש בקריאה זו. אם התשובה שגויה, היא מדפיסה Wrong answer.; אם קריאה לממשק אינה חוקית, היא גם מציינת את סיבת השגיאה בזרם השגיאות הסטנדרטי.

דוגמאות

קלט 1

0 6 67
3 1 6 4 2 5
0 1 1 0 1 0

פלט 1

Correct!
Queries used: 16

הסבר

בדוגמה, לפני תחילת האינטראקציה מתקיים $a=(3,6,1,4,5,5)$; המשלים של המערך כולו הוא $(4,1,6,3,2,2)$. החזרת כל אחד משני המערכים האלה נחשבת נכונה. הקריאה הראשונה query({}) מחזירה $(5,5)$. הפלט שלעיל הוא תוצאת הרצת תוכנית הפתרון הסטנדרטית שבקבצים המצורפים; מספר השאילתות עשוי להיות שונה בתוכניות נכונות אחרות.

מגבלות

בכל נתוני הבדיקה מתקיים $1\le n\le 500$.

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

ניקוד

אם התשובה שמחזירה recover אינה נכונה, הפרמטרים של query אינם חוקיים, או שמספר השאילתות עולה על $Q_{\max}$, הניקוד למקרה הבדיקה הוא $0$.

אחרת, בתת־המשימות $1,2$ מקרה הבדיקה מקבל ניקוד מלא. בתת־המשימות $3,4$, נסמן ב־$Q$ את מספר השאילתות שבהן נעשה שימוש בפועל במקרה הבדיקה. מקדם הניקוד $f(Q)$ מחושב לפי הטבלה הבאה:

הניקוד בתת־משימה $3$ הוא $40f(Q)$, והניקוד בתת־משימה $4$ הוא $40f(Q)$. הניקוד הסופי מעוגל ל־$3$ ספרות אחרי הנקודה העשרונית.

מגבלת זמן: $2\ \mathrm{s}$.

מגבלת זיכרון: $512\ \mathrm{MiB}$.