Дивні запити

Масив цілих чисел $p_1,p_2,\dots ,p_n$ називається перестановкою, якщо послідовність містить кожне ціле число від $1$ до $n$ рівно один раз. Наприклад, $[1,5,3,4,2]$ є перестановкою. Однак $[1,3,4]$ не є перестановкою (вона не містить $2$ та містить $4$) і $[1,2,2,3]$ також не є перестановкою (вона містить $2$ двічі та не містить $4$).

Вам дана перестановка $p_1,p_2,\dots ,p_n$.

Нехай $p_i^k=\underset{\text{k разів}}{\underbrace{p[p[\dots [i]\dots ]]}}$. Наприклад: $p_i^1=p[i]$ та $p_i^2=p[p[i]]$.

Ваше завдання — відповісти на $q$ запитів. Для певного числа $k$ визначте $\underset{1\le i\le n}{\max }(p_i^k+i)$. Іншими словами, визначте максимальне значення $p_i^k+i$, де $1\le i\le n$.

Вхідні дані

Перший рядок містить два цілих числа $n$ та $q$ $(1\le n\le 1000;1\le q\le 10^6)$ — довжина $p$ та кількість запитів, відповідно.

Наступний рядок містить $n$ цілих чисел $p_1,p_2,\dots ,p_n$ ($1\le p_i\le n$) — елементи перестановки $p$. Гарантується, що послідовність $p$ є перестановкою.

Кожен з наступних $q$ рядків містить одне ціле число $k$ $(1\le k\le 10^9)$.

Вихідні дані

Для кожного запиту виведіть бажане максимальне значення.

Приклади

Примітка

У першому прикладі у нас є перестановка $p=[4,1,5,2,3]$.

Перший запит — $k=1$, отже нам потрібно знайти

Другий запит — $k=2$. Відповідь —

Оцінювання

1. ($3$ бали): $p=[1,2,\dots ,n]$;

2. ($5$ балів): $q\le 10$ та $k\le 100$;

3. ($7$ балів): $k\le 100$;

4. ($5$ балів): для кожної пари $1\le i,j\le n$ існує таке $k$ що $p_i^k=j$;

5. ($16$ балів): $n\le 20$;

6. ($31$ бал): $q\le 10^4$;

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