עצי הקפוק המעטים שבגן הישן עדיין צומחים בזיכרונותיה של N הקטנה, ההולכים ומתערפלים. אפשר לייצג את זיכרונה של N הקטנה מהגן הישן באמצעות סדרה באורך $n$, $[a_0,a_1,\ldots,a_{n-1}]$.

כל עץ קפוק בגן הישן הוא עץ לא מושרש בעל צמתים ממוספרים. אפשר לתאר את הרושם של N הקטנה מעץ קפוק באמצעות קטע $[l,r)$ בזיכרונה מהגן הישן:

• מספר הצמתים בעץ הוא $k=r-l+2$, והם ממוספרים מ־$0$ עד $k-1$.
• $[\min(a_l,k-1),\min(a_{l+1},k-1),\ldots,\min(a_{r-1},k-1)]$ היא סדרת Prüfer של העץ. הגדרת סדרת Prüfer מפורטת בסעיף ״רמז״.

בזמן שהיא נזכרת בעבר, N הקטנה מציגה לכם $m$ שאילתות. השאילתה ה־$i$ ($0\le i<m$) היא:

• האם הצמתים $x_i,y_i$ סמוכים בעץ הקפוק המתאים לקטע $[l_i,r_i)$ בזיכרונה מהגן הישן?

פרטי מימוש

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

עליכם לוודא שקובץ קוד המקור המוגש כולל את קובץ הכותרת kapok.h, כלומר להוסיף בתחילת התוכנית את הקוד הבא:

#include "kapok.h"

עליכם לממש בקובץ קוד המקור המוגש kapok.cpp את הפונקציה הבאה:

std::vector<bool> kapok(int c, int n, int m,
    std::vector<int> a, std::vector<int> l, std::vector<int>
    r, std::vector<int> x, std::vector<int> y);

• $c,n,m$ מציינים, בהתאמה, את מספר הבדיקה, את אורך סדרת הזיכרונות מהגן הישן ואת מספר השאילתות. $c=0$ מציין שזו דוגמה.
• $a$ היא סדרת הזיכרונות מהגן הישן.
• $l,r$ מציינים את שני קצות הקטע הנתון בכל שאילתה, בהתאמה.
• $x,y$ מציינים את מספרי שני הצמתים הנתונים בכל שאילתה, בהתאמה.
• הפונקציה צריכה להחזיר סדרה באורך בדיוק $m$, $f_0,f_1,\ldots,f_{m-1}$, כאשר $f_i$ ($0\le i<m$) היא התוצאה של השאילתה ה־$i$.
• בכל בדיקה, תוכנית השיפוט תקרא לפונקציה זו בדיוק פעם אחת.

הקובץ template_kapok.cpp שבתיקיית הבעיה הוא קוד דוגמה שסופק. תוכלו להיעזר בו כדי לממש את הקוד שלכם.

כיצד לבדוק את התוכנית

אפשר להריץ בתיקיית הבעיה את הפקודה הבאה כדי לקמפל קובץ הרצה:

g++ grader.cpp kapok.cpp -o kapok -O2 -std=c++14 -static

לגבי קובץ ההרצה kapok המתקבל:

• קובץ ההרצה יקרא מהקלט הסטנדרטי נתונים בפורמט הבא:

  • השורה הראשונה מכילה שלושה מספרים שלמים אי־שליליים $c,n,m$.
  • השורה השנייה מכילה $n$ מספרים שלמים אי־שליליים $a_0,a_1,\ldots,a_{n-1}$.
  • השורה ה־$i+3$ ($0\le i<m$) מכילה ארבעה מספרים שלמים אי־שליליים $l_i,r_i,x_i,y_i$.

• קובץ ההרצה יכתוב לפלט הסטנדרטי נתונים בפורמט הבא:

  • השורה ה־$i+1$ ($0\le i<m$) מכילה מספר שלם אי־שלילי אחד, כאשר $0$ מציין ש־$f_i$ הוא false, ו־$1$ מציין ש־$f_i$ הוא true.

דוגמאות

קלט 1

0 8 3
2 0 2 6 0 7 2 2
0 3 0 2
3 5 1 2
0 0 0 1

פלט 1

1
0
1

הסבר

• העץ המתאים לקטע $[0,3)$ מכיל $5$ צמתים, סדרת Prüfer שלו היא $[2,0,2]$, וקבוצת קשתותיו היא $\{(1,2),(0,3),(0,2),(2,4)\}$. לכן הצמתים $0,2$ סמוכים.
• העץ המתאים לקטע $[3,5)$ מכיל $4$ צמתים, סדרת Prüfer שלו היא $[3,0]$, וקבוצת קשתותיו היא $\{(1,3),(0,2),(0,3)\}$. לכן הצמתים $1,2$ אינם סמוכים.
• העץ המתאים לקטע $[0,0)$ מכיל $2$ צמתים, סדרת Prüfer שלו ריקה, והקשת היחידה שלו היא $(0,1)$. לכן הצמתים $0,1$ סמוכים.

דוגמה 2

ראו את הקבצים kapok/kapok2.in ו־kapok/kapok2.ans בתיקיית המתחרה.

דוגמה זו מקיימת את מגבלות הבדיקות $3\sim5$.

דוגמה 3

ראו את הקבצים kapok/kapok3.in ו־kapok/kapok3.ans בתיקיית המתחרה.

דוגמה זו מקיימת את מגבלות הבדיקות $3\sim5$.

מגבלות

לכל נתוני הבדיקה מתקיים:

• $1\le n,m\le2\times10^5$.
• לכל $0\le i<n$, מתקיים $0\le a_i<n+2$.
• לכל $0\le i<m$, מתקיים $0\le l_i\le r_i\le n$ ו־$0\le x_i,y_i<r_i-l_i+2$.

• תכונה מיוחדת A: לכל $0\le i<m$, לאחר קביעת $l_i,r_i$, שני הערכים $x_i,y_i$ נוצרים באופן אקראי, בלתי תלוי ואחיד, מבין כל זוגות הצמתים הסדורים המקיימים את המגבלות.

רמז

לעץ לא מושרש $T$, שצמתיו ממוספרים מ־$0$ עד $c-1$ ($c\ge2$):

• מבצעים $c-2$ פעולות בזו אחר זו. הפעולה ה־$i$ ($0\le i<c-2$) היא:

  • מוצאים את העלה הנוכחי בעל המספר הקטן ביותר, $v_i$.
  • רושמים את מספר השכן היחיד שלו, $p_i$.
  • לאחר מכן מסירים מ־$T$ את $v_i$ ואת הקשת היחידה המחוברת אליו.

• הסדרה באורך $c-2$ המתקבלת כך, $[p_0,p_1,\ldots,p_{c-3}]$, היא סדרת Prüfer של $T$.