Building 4
시간 제한1.5초메모리 제한512 MB
2N개 건물 중 정확히 N개에는 A를, 나머지에는 B를 골라 럭셔리 수준이 비감소하도록 만들고, 불가능하면 -1을 출력한다.
문제
The Olympic Games will be held in JOI Kingdom soon. In order to welcome participants from all over the world, the buildings on the way from the airport to the accommodation will be decorated. There are 2N buildings, numbered from 1 to 2N from the airport.
President K is in charge of the decoration project. He asked the public to make decoration plans. After examining them, he finally chose two plans, the plan A and the plan B. In the plan A, the luxury level of the building i (1 ≤ i ≤ 2N) is Ai. In the plan B, the luxury level of the building i (1 ≤ i ≤ 2N) is Bi.
Both plans are very good, and it is difficult to choose one of them. He decided to decorate the buildings in the following way: for each building, one of the plan A or B will be chosen. In order to decorate the buildings in a fair way, the plan A will be chosen for N buildings, and the plan B will be chosen for the remaining N buildings. Moreover, since the participants will be excited if the luxury levels are increasing on the way from the airport to the accommodation, the following condition should be satisfied: Ci ≤ Ci+1 for every i with 1 ≤ i ≤ 2N − 1, where Ci is the luxury level of the building i (1 ≤ i ≤ 2N).
Write a program which, given the number of buildings and the luxury levels of the buildings for each plan, decides whether it is possible to choose decoration plans satisfying the above condition, and output one way to decorate the buildings if it is possible.
입력
Read the following data from the standard input. All the values in the input are integers.
N
A1 · · · A2N
B1 · · · B2N
출력
If it is impossible to choose decoration plans satisfying the condition, output -1 to the standard output.
Otherwise, output a string S of length 2N describing a way to decorate the buildings to the standard output. Here the i-th character of S (1 ≤ i ≤ 2N) is A if the plan A is chosen for the building i, and is B if the plan B is chosen for the building i. If there are multiples ways satisfying the condition, output any of them.
제한
- 1 ≤ N ≤ 500 000．
- 1 ≤ Ai ≤ 1 000 000 000 (1 ≤ i ≤ 2N).
- 1 ≤ Bi ≤ 1 000 000 000 (1 ≤ i ≤ 2N).