Just Long Neckties
시간 제한2초메모리 제한512 MB
N+1개의 넥타이 중 하나를 제거하고 남은 N개를 N명의 직원에게 짝지어 최대 초과량 max(a-b, 0)를 최소로 만드는 값을 각 제거 대상마다 구한다.
문제
Just Odd Inventions, Ltd.(이 문제에서는 JOI, Ltd.라고 부른다)는 "기묘한 발명품"으로 알려진 회사다. JOI, Ltd.가 새로 만든 제품이 "Just Long Neckties"이다. 넥타이는 1번부터 N + 1번까지 N + 1종류가 있고, i번째 넥타이(1 ≤ i ≤ N + 1)의 길이는 Ai이다.
회사는 직원들을 모아 넥타이 착용 파티를 열려고 한다. 파티에는 N명의 직원이 참가하며, j번째 직원(1 ≤ j ≤ N)은 처음에 길이 Bj인 넥타이를 매고 있다.
착용 파티는 다음 순서로 진행된다.
- JOI, Ltd.의 CEO가 파티에서 사용하지 않을 넥타이를 하나 고른다.
- 이어서 각 직원이 남은 넥타이 중 하나를 골라 착용해 본다. 두 직원이 같은 넥타이를 고를 수는 없다.
- 마지막으로 각 직원이 처음에 매고 있던 넥타이를 벗고 고른 넥타이를 맨다.
처음에 길이 b인 넥타이를 매고 있던 직원이 길이 a인 넥타이를 착용해 보면 max{a − b, 0}만큼의 이질감을 느낀다. 착용 파티의 기묘함은 직원들이 느낀 이질감 중 최댓값으로 정의한다.
또한 Ck를 JOI, Ltd.의 CEO가 k번째 넥타이를 골랐을 때 착용 파티의 기묘함의 최솟값으로 정의한다.
파티에서 사용하는 넥타이의 길이와 각 직원이 처음에 매고 있는 넥타이의 길이가 주어질 때, C1,C2, . . . ,CN+1을 계산하는 프로그램을 작성하라.
입력
표준 입력에서 다음 데이터를 읽는다. 주어지는 값은 모두 정수이다.
N
A1 . . . AN+1
B1 . . . BN
출력
표준 출력에 한 줄을 출력한다. C1,C2, . . . ,CN+1을 공백으로 구분하여 출력한다.
제한
- 1 ≤ N ≤ 200 000.
- 1 ≤ Ai ≤ 1 000 000 000 (1 ≤ i ≤ N + 1).
- 1 ≤ Bj ≤ 1 000 000 000 (1 ≤ j ≤ N).