집합론

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

요약
집합 A의 원소 n개가 주어질 때, 모든 n^2개의 합 a_i + b_j가 서로 다르도록 [1, 10^6] 범위의 서로 다른 정수 n개로 이루어진 집합 B를 찾거나 불가능함을 판정한다.
난이도

보통10점 중 6점

유형
수학, 조합론, 그리디, 구현
정답자
아직 제출이 없습니다

문제

마샤와 그리샤는 양의 정수로 이루어진 집합을 공부하는 것을 좋아한다.

어느 날 그리샤는 칠판에 서로 다른 nn개의 정수 aia_i를 원소로 하는 집합 AA를 적었다. 이제 그는 마샤에게 서로 다른 nn개의 정수 bjb_j를 원소로 하는 집합 BB를 만들어 달라고 부탁한다. 이때 가능한 모든 ii와 jj의 쌍에 대해 ai+bja_i + b_j로 얻을 수 있는 n2n^2개의 정수가 모두 서로 달라야 한다.

마샤와 그리샤는 큰 수를 좋아하지 않으므로, AA의 모든 수는 11부터 10610^6까지이고, BB의 모든 수도 같은 범위에 있어야 한다.

마샤가 그리샤의 요구를 만족하는 집합 BB를 만들도록 도와주자.

입력

입력은 여러 개의 테스트 케이스로 이루어진다. 첫째 줄에는 정수 tt가 주어진다. 이는 테스트 케이스의 수이다 (1≤t≤1001 \le t \le 100).

각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에는 정수 nn이 주어진다. 이는 AA의 원소 수이다 (1≤n≤1001 \le n \le 100).

둘째 줄에는 nn개의 정수 aia_i가 주어진다. 이는 AA의 원소이다 (1≤ai≤1061 \le a_i \le 10^6).

출력

각 테스트 케이스마다 답을 출력한다.

  • 마샤의 과제를 풀 수 없어서 필요한 집합 BB를 만들 방법이 없으면 NO를 출력한다.
  • 필요한 집합을 만들 방법이 있으면 YES를 출력한다. 이 경우 둘째 줄에 서로 다른 nn개의 양의 정수 bjb_j를 출력한다. 이는 BB의 원소이다 (1≤bj≤1061 \le b_j \le 10^6). 가능한 집합이 여러 개라면 그중 아무거나 출력한다.

예제1

  1. 예제 1

    입력
    3
    3
    1 10 100
    1
    1
    2
    2 4
    
    예상 출력
    YES
    1 2 3 
    YES
    1 
    YES
    1 2