Футбол

У футбольній команді $n$ гравців, пронумерованих цілими числами від $1$ до $n$. Рівень гри гравця з номером $i$ описується цілим числом $c_i$.

Гравці вишикувались по колу в такому порядку, що наступним з правого боку для гравця з номером $i$ є гравець з номером $i+1$ (для $1\le i<n$), а для гравця з номером $n$ наступним є гравець з номером $1$.

Визначимо силу ігрової комбінації, яка характеризується масивом цілих чисел $k=[k_0,k_1,k_2,\dots ,k_{m-1}]$, наступним чином:

• початково м'яч знаходиться у гравця з номером $1$;

• гравці по черзі передають м'яч нескінченно довго: виконуючи передачу з номером $i$, гравець, який наразі контролює м'яч, передає його гравцю, що знаходиться на $x$ позицій правіше по колу, де $x=k_{((i-1)\mathrm{mod}m)}$;

• силою ігрової комбінації вважається мінімальна сила гри серед сил всіх гравців, що володіли м'ячем в деякий момент описаного процесу.

Задано масив цілих чисел $a_0,a_1,\dots ,a_{q-1}$. Для кожного $i$ від $0$ до $(q-1)$ знайдіть силу ігрової комбінації, яка характеризується масивом $[a_0,a_1,\dots ,a_i]$.

Вхідні дані

У першому рядку задано два цілі числа $n$ та $q$ $(1\le n,q\le 3\cdot {10}^5)$ — кількість гравців та довжина масиву $a$.

У другому рядку задано $n$ цілих чисел $c_1,c_2,\dots ,c_n$ $(1\le c_i\le n)$ — рівні гри гравців.

У третьому рядку задано $q$ цілих чисел $a_0,a_1,\dots ,a_{q-1}$ $(1\le a_i\le n-1)$ — елементи масиву $a$.

Вихідні дані

Виведіть $q$ цілих чисел — шукані значення сил ігрових комбінацій.

Приклади

Примітка

У прикладі передачі м'яча для ігрових комбінацій виглядають наступним чином:

$k=[3]$

$k=[3,1]$

$k=[3,1,2]$

Оцінювання

1. ($10$ балів): $n,q\le 100$;

2. ($4$ бали): усі значення $a_i$ однакові;

3. ($11$ балів): $n$ — просте число;

4. ($12$ балів): $n,q\le 1000$;

5. ($16$ балів): $n,q\le 1.5\cdot {10}^5$, $n=2^k$ для деякого цілого $k$;

6. ($25$ балів): $n,q\le {10}^5$;

7. ($22$ бали): без додаткових обмежень.