ישנן $n$ חבילות, הממוספרות מ-$1$ עד $n$, שהגיעו זה עתה למחסן. הן הגיעו בסדר $a_1, \dots, a_n$, ואנו רוצים למיין אותן כך שיהיו בסדר $1, 2, \dots, n$.

מכונת המיון במחסן עובדת בשלבים. כל שלב מקבל שורה $a_1, \dots, a_n$ של חבילות ופועל באופן הבא: ראשית, החבילה הראשונה $a_1$ מוכנסת לשורה חדשה. לאחר מכן, עבור כל חבילה $a_i$ עבור $i = 2, \dots, n$, אם $a_i$ גדולה מהחבילה האחרונה (הימנית ביותר) בשורה החדשה, המכונה מציבה אותה בסוף השורה. אחרת, היא מציבה אותה בתחילת השורה.

אם השורה החדשה אינה ממוינת, היא משמשת כקלט לשלב הבא של מכונת המיון.

כתבו תוכנית המסייעת לבדוק האם המכונה פועלת כמתוכנן על ידי מענה על שאילתות מהצורה "איזו חבילה נמצאת במקום ה-$b$ לאחר $t$ שלבים".

קלט

השורה הראשונה של הקלט מכילה שני מספרים שלמים $n$ ו-$q$ ($1 \le n, q \le 5 \cdot 10^5$), המציינים את מספר החבילות ואת מספר השאילתות, בהתאמה.

השורה השנייה מכילה סדרה של $n$ מספרים שלמים $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$, $a_i \ne a_j$) המייצגים את הסידור ההתחלתי של החבילות.

$q$ השורות הבאות מכילות שאילתות; השורה ה-$i$ מכילה שני מספרים שלמים $t_i$ ו-$b_i$ ($0 \le t_i \le 10^9$, $1 \le b_i \le n$), המציינים את השאילתה ה-$i$.

פלט

פלטו בדיוק $q$ שורות. השורה ה-$i$ צריכה להכיל את התשובה לשאילתה ה-$i$.

אם המכונה ביצעה פחות מ-$t_i$ שלבים, כתבו $-1$. אחרת, כתבו איזו חבילה נמצאת במיקום $b_i$ משמאל, לאחר שבוצעו $t_i$ שלבים.

דוגמאות

קלט 1

5 4
2 1 3 5 4
1 1
3 2
4 1
0 4

פלט 1

4
2
-1
5

הערה 1

המכונה תבצע שלושה שלבים:

$$2\ 1\ 3\ 5\ 4 \to 4\ 1\ 2\ 3\ 5 \to 3\ 2\ 1\ 4\ 5 \to 1\ 2\ 3\ 4\ 5$$

קלט 2

1 1
1
1 1

פלט 2

-1