Redistribution of Digits

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

요약

문자열 s의 모든 자릿수를 정확히 한 번씩 사용해 n개의 수를 만들되, 각 수가 a_i 이하가 되도록 배분한다.

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

문제

You are required to form numbers based on a given set of digits. Each number is also provided with an upper bound. Each digit from the given set must be used exactly once. If the set does not contain a digit, you are not allowed to use it.

입력

First line contains an integer $t$ --- the number of tests.

Each of the next $t$ lines contains a string $s$ --- a given set of digits, integer $n$ --- quantity of numbers which should be formed and $n$ integers $a\_i$ --- upper bounds for numbers. The digits for all numbers $a\_i$ are given in a non-increasing order starting from the most significant digit. The set of digits and the numbers $a\_i$ do not contain a digit $0$ .

출력

You are required to output $t$ lines containing the given quantity of numbers corresponding the conditions above. If a solution does not exist you should print "-1". If there are multiple solutions, you may output any of them.

제한

$1 \le t \le 1000$
$1 \le |s| \le 500$
$1 \le n \le 50$
$1 \le a\_i \le 10^9$

예제1

예제 1

입력

3
1234 2 21 43
12534 2 21 43
42 1 42

예상 출력

14 23
-1
42