Дано множину цілих чисел. Для кожного запиту виду \(PREV\: x\) знайдіть найбільший елемент множини, який строго менший за \(x\). Якщо такого елемента не існує, виведіть \(-1\).

Input Specification

Перший рядок містить два числа \(n\) та \(q\), де \(n\) --- кількість елементів; \(q\) --- кількість запитів. Другий рядок містить \(n\) цілих чисел \(a_1, a_2, \ldots, a_n\), де \(a_i\) --- елементи. Другий рядок містить \(q\) запитів \(b_1, b_2, \ldots, b_n\), де \(b_i\) --- запити вигляду \(PREV\: x\)(\(x\) --- ціле число). \(\\1 \leq n \leq 2 \cdot 10^5\\\) \(1 \leq q \leq 2 \cdot 10^5\\\) \(-10^9 \leq a_i \leq 10^9\\\) \(-10^9 \leq x \leq 10^9\\\)

Output Specification

Для кожного запиту виведіть: \begin{itemize} \item найбільший елемент \(< x\); \item або \(-1\), якщо такого немає. \end{itemize}

Sample Input 1

5 5
1 3 5 7 9
PREV 4
PREV 5
PREV 8
PREV 1
PREV 0

Sample Output 1

3
3
7
-1
-1

Sample Input 2

7 4
1 0 121 45 32 89 -12
PREV -1
PREV 325
PREV -100
PREV 3

Sample Output 2

-12
121
-1
1