| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 69 | 36 | 22 | 81.481% |
Боузер --- злодей, который часто похищает принцесс, и даже имеет для их заточения целое подземелье.
В подземелье расположено $n$ тюремных камер. Камеры пронумерованы натуральными числами от $1$ до $n$ и расположены в этом порядке вдоль длинного коридора на одинаковом расстоянии друг от друга. Камера с номером $i$ рассчитана на заточение $a_i$ принцесс. Вход в подземелье расположен между камерами $k$ и $k + 1$, при этом, если $k = 0$, это означает, что вход находится перед первой камерой. Если $k = n$, вход расположен после последней камеры.
Боузер собирается сделать $m$ вылазок с целью похищения принцесс. В $j$-ю вылазку он планирует похитить $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$.
3 3 0 5 3 1 1 1 1
3 1 2
4 5 2 1 3 2 2 1 1 3 2 1
1 2 -1 3 4
6 6 3 1 2 3 3 2 1 1 1 1 1 1 1
1 6 3 4 2 5