ما زالت أشجار الكابوك القليلة في الديار القديمة تنمو في ذكريات 小 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$ رقمي العقدتين المعطاتين في كل استعلام على الترتيب.
• يجب أن تعيد الدالة متتالية $f_0,f_1,\ldots,f_{m-1}$ طولها $m$ بالضبط، حيث يمثل $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$ على أنه 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)$ خمس عقد، ومتتالية Prüfer لها هي $[2,0,2]$، ومجموعة حوافها $\{(1,2),(0,3),(0,2),(2,4)\}$، ولذلك العقدتان $0,2$ متجاورتان.
• للشجرة الموافقة للمقطع $[3,5)$ أربع عقد، ومتتالية Prüfer لها هي $[3,0]$، ومجموعة حوافها $\{(1,3),(0,2),(0,3)\}$، ولذلك العقدتان $1,2$ غير متجاورتين.
• للشجرة الموافقة للمقطع $[0,0)$ عقدتان، ومتتالية 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$.
  • احذف بعد ذلك $v_i$ وحافتها الوحيدة من $T$.

• المتتالية الناتجة $[p_0,p_1,\ldots,p_{c-3}]$، وطولها $c-2$، هي متتالية Prüfer للشجرة $T$.