시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB69362281.481%

문제

Боузер --- злодей, который часто похищает принцесс, и даже имеет для их заточения целое подземелье.

В подземелье расположено $n$ тюремных камер. Камеры пронумерованы натуральными числами от $1$ до $n$ и расположены в этом порядке вдоль длинного коридора на одинаковом расстоянии друг от друга. Камера с номером $i$ рассчитана на заточение $a_i$ принцесс. Вход в подземелье расположен между камерами $k$ и $k + 1$, при этом, если $k = 0$, это означает, что вход находится перед первой камерой. Если $k = n$, вход расположен после последней камеры.

Боузер собирается сделать $m$ вылазок с целью похищения принцесс. В $j$-ю вылазку он планирует похитить $b_j$ принцесс. Приведя их в подземелье, Боузер выбирает камеру для новых принцесс по следующему принципу:

  • Если есть свободная камера с вместимостью $a_i = b_j$, то он обязательно выбирает такую камеру. Иначе он выбирает свободную камеру с вместимостью $a_i > b_j$.
  • Из подходящих камер он выбирает ту, которая расположена как можно ближе ко входу. Если камер с одинаковым расстоянием до входа несколько, он выбирает ту, у которой номер меньше. Расстояние от входа до камеры Боузер считает равным количеству камер между ними.
  • Если свободной камеры, подходящей по вместимости, нет, то ему остается лишь расстроиться и отпустить принцесс.

Чтобы не допустить побега принцесс, после того как Боузер заточил их в камеру, он закрывает камеру на ключ и выбрасывает его. Таким образом открыть камеру и добавить туда принцесс похищенных в другой вылазке, невозможно. Также Боузер никогда не пытается разместить принцесс, похищенных в одной вылазке, более чем в одной камере.

Марио и Луиджи нашли планы подземелья и владеют информацией о вылазках Боузера. Для каждой вылазки, они хотят определить камеру, в которую будут заточены принцессы.

입력

В первой строке даны три целых числа $n$, $m$ и $k$ --- число тюремных камер, число вылазок Боузера и номер камеры, после которой расположен вход в подземелье ($1 \le n, m \le 1000$, $0 \le k \le n$). Если $k = 0$, то вход находится перед первой камерой.

Во второй строке даны $n$ целых чисел $a_i$ --- вместительности камер ($1 \le a_i \le 1000$).

Во третьей строке даны $m$ целых чисел $b_j$ --- число похищенных в $j$-ю вылазку принцесс ($1 \le b_j \le 1000$).

출력

Выведите $m$ чисел $c_j$ --- номера тюремных камер, выбранных для принцесс, похищенных в $j$-ю вылазку. Если Боузер отпустил принцесс, так как не нашел для них подходящую камеру, будем считать, что $c_j = -1$.

예제 입력 1

3 3 0
5 3 1
1 1 1

예제 출력 1

3 1 2

예제 입력 2

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

예제 출력 2

1 2 -1 3 4

예제 입력 3

6 6 3
1 2 3 3 2 1
1 1 1 1 1 1

예제 출력 3

1 6 3 4 2 5