시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB396342612.621%

문제

혜아는 $N$개의 신발을 신고 있다. $i$번째 신발의 능력치를 $A_i$라고 하자. 혜아는 현재 위치에서 $A_1 + A_2 + \cdots + A_N$ km 떨어진 보물이 숨겨진 곳으로 가려고 한다. 걷기 귀찮은 혜아는, 신발의 추진력(!)을 사용해서 점프를 하려고 한다. 

혜아가 점프를 할 때, $i$번째 신발을 사용 하면, 현재 위치에서 $A_i$ km 떨어진 곳으로 점프 할 수 있다. 점프를 하면, 신발은 닳아 없어진다. 모든 신발을 보물이 있는 방향으로 한번씩 사용하면, 혜아는 보물이 있는 곳에 도달하여 건물주가 될 수 있을것이다.

혜아가 건물주가 된다는 말을 들은 카흐는, 건물에만 틀어박힐 혜아를 걱정해서, $M$개의 이불을 놓았다. 이불은, 시작좌표로 부터 보물이 숨겨진 곳을 일직선으로 있는 직선 위에 놓여 있으며, 점프를 해서 착지한 위치가 이불 위라면, 혜아는 이불에서 나오지 않아서 보물을 찾지 못할 것이다. 그는 보물보다, 이불이 더 유혹적이기 때문에, 보물이 있는 곳에 이불이 있으면, 보물을 찾지 않고 바로 이불에 누워버릴 것이다.

혜아를 위해, 이불이 있는 곳을 피해서 보물이 있는 곳에 도착하기 위한 방법을 계산 해 주자.

입력

첫째 줄에는, $N$과 $M$이 공백으로 구분되어 들어온다. ($1 \le M < N \le 100000$)

둘째 줄에는, $N$개의 수가 공백으로 구분되어 들어온다. 이 중 $i$번째 수는 $A_i$를 의미한다. 추진력은 1 이상 $10^9$ 이하의 서로 다른 수이다.

셋째 줄에는, $M$개의 수가 공백으로 구분되어 들어온다. 이는 이불이 위치한 곳을 의미한다. 수가 $x$라는 것은, 이불이 현재 위치로 부터 보물이 숨겨진 방향으로 $x$ km 떨어져 있다는 것을 의미한다. 이불이 숨겨진 위치는 1 이상 $10^{14}$ 이하의 서로 다른 수이다.

출력

보물이 있는 곳에 도착 할 수 없으면, 첫째 줄에 -1을 출력한다.

보물이 있는 곳에 도착 할 수 있으면, 첫째 줄에 $N$개의 수를 공백으로 구분하여 출력한다. $i$번째 수가 $j$라는 것은, $i$번째 점프를 신발 $j$를 이용한 다는 것을 의미한다. 답이 여러개 인 경우, 아무거나 출력하여도 좋다.

예제 입력 1

2 1
4 5
4

예제 출력 1

2 1

예제 입력 2

2 1
4 5
9

예제 출력 2

-1

예제 입력 3

3 2
4 5 9
4 14

예제 출력 3

2 1 3

출처

University > KAIST > 2017 KAIST RUN Spring Contest (HYEA Cup) H번