היחסים בין העובדים בחברה מסוימת מאורגנים במבנה היררכי. בחברה עובדים $n$ עובדים. לכל עובד מוקצה מספר ייחודי מ-$1$ עד $n$, ולמנהל החברה מוקצה המספר $1$. לכל עובד פרט למנהל החברה יש בדיוק ממונה ישיר אחד. מספרו של הממונה הישיר של עובד $i$ הוא $p_i$, ומתקיים $p_i<i$.

עובד $x$ הוא כפוף ברמה $1$ של עובד $y$ אם $p_x=y$. עבור $k>1$, עובד $x$ הוא כפוף ברמה $k$ של עובד $y$ אם העובד $p_x$ הוא כפוף ברמה $k-1$ של עובד $y$.

למנהל החברה ניתנה הזדמנות לשלוח חלק מהעובדים לקורסי השתלמות מקצועית. לשם כך הוא החליט לבחור שני מספרים $L$ ו-$R$ ולשלוח לקורסים את כל העובדים שמספריהם $i$ מקיימים $L\le i\le R$.

לפני בחירת $L$ ו-$R$, קיבל המנהל $m$ בקשות מעובדי החברה. הבקשה ה-$j$ מתוארת בשני מספרים $u_j$ ו-$k_j$, ופירושה שהעובד $u_j$ מבקש לשלוח לקורסים אחד מהכפופים לו ברמה $k_j$. כדי לחסוך כסף, המנהל רוצה לבחור $L$ ו-$R$ כך שמספר העובדים שיישלחו להשתלמות יהיה קטן ככל האפשר, וכל הבקשות ימולאו.

כתבו תוכנית אשר, בהינתן יחסי הממונים והכפופים בחברה ובקשות העובדים, מוצאת $L$ ו-$R$ כך ששליחת כל העובדים שמספריהם מ-$L$ עד $R$, כולל שני הקצוות, תמלא את כל הבקשות, ומספר העובדים שיישלחו להשתלמות יהיה קטן ככל האפשר. אם יש כמה זוגות מיטביים $L,R$, יש למצוא את הזוג שבו $L$ הוא הקטן ביותר.

קלט

השורה הראשונה של קובץ הקלט מכילה את המספר $n$, מספר העובדים בחברה ($2\le n\le200\,000$). השורה השנייה מכילה $n-1$ מספרים: $p_2,p_3,\ldots,p_n$ ($1\le p_i<i$), מספרי הממונים הישירים של העובדים.

השורה השלישית מכילה את המספר $m$, מספר בקשות העובדים.

כל אחת מ-$m$ השורות הבאות מתארת בקשה ומכילה שני מספרים שלמים $u_j,k_j$ ($1\le u_j<n$, $1\le k_j<n$; מובטח שלעובד $u_j$ יש לפחות כפוף אחד ברמה $k_j$).

פלט

יש להדפיס את שני המספרים המבוקשים: $L$ ו-$R$. אם יש כמה זוגות מיטביים $(L,R)$, יש להדפיס את הזוג שבו $L$ הוא הקטן ביותר.

דוגמאות

קלט 1

7
1 1 2 2 3 3
3
1 1
3 1
1 2

פלט 1

3 6

הסבר

העובדים שמספריהם $3,4,5,6$ יישלחו להשתלמות. עובד $3$ הוא כפוף ברמה $1$ של עובד $1$, עובד $4$ הוא כפוף ברמה $2$ של עובד $1$, ועובד $6$ הוא כפוף ברמה $1$ של עובד $3$.

תתי־משימות

הנקודות עבור כל תת־משימה מוענקות רק אם כל הבדיקות של אותה תת־משימה ושל תתי־המשימות הנדרשות עברו בהצלחה.

קבלת מידע על תוצאות הבדיקה הסופית

לפי בקשה, נמסר הניקוד עבור כל תת־משימה.