나무 징검다리

시간 제한1초메모리 제한512 MB

요약

나무 밑둥 n개의 높이가 k까지 강한 증가 후 강한 감소가 되고, 반지름은 증가와 감소가 번갈아 일어나도록 나열하거나 불가능하면 -1을 출력한다.

난이도: 보통10점 중 7점
유형: 그리디, 정렬, 구현
정답자: 아직 제출이 없습니다

문제

Albert는 다양한 크기의 나무 밑둥 (stump) 모양의 장난감으로 징검다리를 만들고 싶어한다.

각 장난감은 1부터 n까지 번호가 붙어있고, i번째 장난감의 높이는 H[i] 이고 반지름은 R[i] 이다.

Albert는 n개의 나무 밑둥 장난감을 왼쪽에서 오른쪽으로 임의의 순서로 나열하되, 아래의 조건을 만족하도록 하고 싶다.

조건 1: 장난감의 높이는 1번째 밑둥부터 k번째 밑둥까지 강한 단조 증가 (strictly increasing) 수열을 이루며 k번째부터 n번째 까지는 강한 단조 감소 (strictly decreasing) 수열을 이룬다. 단, 이 때 k는 1 < k < n를 만족해야 한다.
조건 2: 장난감의 반지름은 왼쪽에서 오른쪽으로 감소, 증가, 감소, 증가, ..., 혹은 증가, 감소, 증가, 감소 해야한다. 즉, 인접한 두 장난감의 반지름이 반드시 달라야 하고, 반지름 차이는 감소와 증가가 번갈아 일어나야 한다.

예를 들어 n = 3, H = [10, 20, 30], 그리고 R = [2, 3, 4]라 하자.

장난감을 1번, 2번, 3번 순서로 나열하는 경우:
- 조건 1: 주어진 조건을 만족하는 k가 존재하지 않는다 (k = 3은 k < n 을 어김에 유의하자)
- 조건 2: 장난감의 반지름이 증가 (2에서 3), 증가 (3에서 4) 하므로 조건 2를 만족하지 않는다.
장난감을 1번, 3번, 2번 순서로 나열하는 경우:
- 조건 1: 처음 두 장난감의 높이는 단조 증가하고 마지막 두 장난감의 높이는 단조 감소 하므로 k = 2 일 때 조건 1을 만족한다.
- 조건 2: 장난감의 반지름이 2 -> 4 -> 3 으로 증가, 감소 하므로 조건 2를 만족한다.
장난감을 2번, 1번, 3번 순서로 나열하는 경우:
- 조건 1: 높이가 [20, 10, 30] 으로 강한 단조 감소 후 강한 단조 증가하는데 주어진 조건은 강한 단조 증가 후 강한 단조 감소이다 (따라서 조건1을 어긴다).
- 조건 2: 장난감의 반지름이 3 -> 2 -> 4로 감소, 증가 하므로 조건 2를 만족한다.

이 예제의 경우 상기한 (1번, 3번, 2번) 순서로 나열하는 경우 외에 (2번, 3번, 1번) 순서로 나열하는 경우도 두 조건을 만족한다.

다른 예로, n = 3, H = [10, 20, 30], 그리고 R = [2, 5, 2]라 하자.

이 경우, 세 장난감을 나열하는 6가지 방법 중 상기한 두 조건을 모두 만족하는 경우는 없다.

마지막으로, n = 5, H = [10, 20, 30, 40, 50], R = [2, 7, 3, 4, 6] 이라 하자.

이 경우, 총 4가지 다른 방법으로 장난감을 나열하여 상기한 두 조건을 만족시킬 수 있다.

장난감을 1번 2번 3번 5번 4번 순서로 나열한 경우:
- 조건 1: 높이가 [10, 20, 30, 50, 40] 으로 k = 4 일 때 조건을 만족한다.
- 조건 2: 반지름이 [2, 7, 3, 6, 4]로 증가, 감소, 증가, 감소 하므로 조건을 만족한다. 본문의 그림은 이 예제에서 장난감을 1-2-3-5-4번 순서로 나열한 경우를 나타낸다.
장난감을 1번 2번 4번 5번 3번 순서로 나열한 경우:
- 조건 1: 높이가 [10, 20, 40, 50, 30] 으로 k = 4 일 때 조건을 만족한다.
- 조건 2: 반지름이 [2, 7, 4, 6, 3]로 증가, 감소, 증가, 감소 하므로 조건을 만족한다.
그 외에 장난감을 3번 5번 4번 2번 1번 순서로 나열한 경우와 4번 5번 3번 2번 1번 순으로 나열한 경우가 가능하다.

입력으로 n과 각 장난감의 높이/반지름이 주어졌을 때, 위의 두 조건을 만족하며 장난감을 나열할 수 있는 방법이 있는지 알아보자.

입력

첫 줄에는 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스는 세 줄에 나누어 주어진다.

첫 줄에는 n이 주어진다.

둘째 줄에는 장난감의 높이 (H[i])를 나타내는 n개의 정수가 공백으로 구분되어 주어진다.

셋째 줄에는 장난감의 반지름 (R[i])을 나타내는 n개의 정수가 공백으로 구분되어 주어진다.

출력

각 테스트 케이스에 대하여 답을 한 줄에 출력한다.

조건을 만족하는 장난감 나열법이 있을 경우, n개의 장난감 번호를 공백으로 구분하여 출력한다. 본문의 예제 처럼 다양한 답이 존재하는 경우, 아무 것이나 한 가지 방법을 출력하면 된다. 조건을 만족하는 방법이 없을 경우 -1을 출력한다.

제한

1 ≤ T ≤ 20
1 < n ≤ 400
1 ≤ H[i], R[i] ≤ 1,000,000,000

예제1

예제 1

입력

8
3
10 20 30
2 5 2
3
10 20 30
2 3 4
5
10 20 30 40 50
2 7 3 4 6
3
2 4 5
6 1 4
3
1 2 3
2 6 2
5
1 1 2 6 7
4 6 4 2 8
5
2 6 4 4 8
6 4 2 5 1
5
1 2 3 4 5
2 7 6 4 3

예상 출력