"הוא פורע חוק והוא מפורסם, Andrii Popa האמיץ.

יומם ולילה הוא רוכב, הוא גובה את המס שלו מהדרך הראשית ובכל מקום במדינה לוכדי הגנבים בורחים מהר ככל יכולתם"

— "Andrii Popa", Phoenix

ל-Ghiță יש סדרה $S$ הממוספרת החל מ-$0$ של $N$ משקלים שלמים חיוביים. מאחר שהוא מלך הקרפטים, הוא רוצה לבנות עץ בינארי שצמתיו בעלי אינדקסים $0, 1, \ldots, N - 1$ כך שמתקיים:

• סריקת תוכן (inorder traversal) של העץ מניבה את הצמתים בסדר עולה של האינדקסים. סריקת תוכן של עץ בינארי מורכבת מסריקת התוכן של תת-העץ ששורשו בבן השמאלי של השורש (אם בן כזה קיים), אחריה האינדקס של השורש, ואחריה סריקת התוכן של תת-העץ ששורשו בבן הימני של השורש (אם בן כזה קיים).
• אם צומת $x$ הוא האב של צומת $y$, אזי $S_x$ מחלק את $S_y$.

נזכיר כי עץ בינארי הוא מבנה נתונים עצי שבו לכל צומת יש לכל היותר שני בנים, הנקראים הבן השמאלי והבן הימני.

לרוע המזל, פורע החוק המפורסם Andrii Popa גנב את הסדרה $S$, ו-Ghiță אינו יכול עוד לגשת אליה ישירות. באמצעות טכנולוגיה מתקדמת (הטלפון הנייד שלו), הוא יכול, עבור כל שתי תת-סדרות רציפות $[a, b]$ ו-$[c, d]$ של $S$, לברר האם $\gcd[a, b]$ שווה ל-$\gcd[c, d]$, כאשר $\gcd[x, y]$ הוא המחלק המשותף המקסימלי של $S_x, S_{x+1}, S_{x+2}, \ldots, S_y$. למרבה הצער, הטכנולוגיה יקרה למדי — אם Ghiță ישתמש בה יותר מ-$Q$ פעמים, הוא ייאלץ לשלם קנס גבוה. עזרו לו באמצעות שימוש בטכנולוגיה לכל היותר $Q$ פעמים כדי לבנות את העץ המבוקש. מובטח שהדבר אפשרי. כל פתרון חוקי יתקבל.

אינטראקציה

על המתחרה לכלול את קובץ הכותרת popa.h (ב-C / C++) או לממש את popa.pas (ב-Pascal). על המתחרה לממש את הפונקציה הבאה:

int solve(int N, int* Left, int* Right);

function solve(N: LongInt, var Left, Right: array of LongInt): LongInt;

פונקציה זו צריכה להחזיר את שורש העץ, ולהציב ב-$\text{Left}_i$ וב-$\text{Right}_i$ את הבן השמאלי והבן הימני של צומת $i$ בהתאמה. אם לצומת $i$ אין בן שמאלי, אזי $\text{Left}_i$ צריך להיות $-1$. אם לצומת $i$ אין בן ימני, אזי $\text{Right}_i$ צריך להיות $-1$. המצביעים Left ו-Right מצביעים לשני מערכים בגודל $N$ בדיוק שכבר הוקצו.

הפונקציה solve עשויה להיקרא לכל היותר $5$ פעמים במהלך הרצה בודדת. אנו ממליצים להיזהר בשימוש במשתנים גלובליים.

המתחרה רשאי להשתמש בפונקציה הבאה:

int query(int a, int b, int c, int d);

function query(a, b, c, d: LongInt): LongInt;

פונקציה זו תחזיר $1$ אם ורק אם $\gcd[a, b]$ שווה ל-$\gcd[c, d]$, כאשר $0 \le a \le b < N$ ו-$0 \le c \le d < N$, ו-$0$ אחרת.

תת-משימות

תת-משימה 1 (37 נקודות)

• $N = 100$
• $Q = 10000$

תת-משימה 2 (24 נקודות)

• $N = 1000$
• $Q = 20000$

תת-משימה 3 (39 נקודות)

• $N = 1000$
• $Q = 2000$

דוגמאות

דוגמה לאינטראקציה עבור $S = [12, 4, 16, 2, 2, 20]$ היא:

הערה

דוגמה לעץ מהסוג ש-Ghiță רוצה עבור הדוגמה הקודמת היא: