단백질 식별

단백질은 아미노산의 연결체이다. 단백질은 이중 질량 분석기 (MS2)를 이용해서 단백질의 서열을 알아낼 수 있다.

문제를 풀기 위해 다음과 같은 상황을 가정한다.

• 단백질은 최대 400개 아미노산이 연결된 형태이다.
• 아미노산은 두 종류 P와 Q만 있다.
• P의 질량은 97.05276돌턴, Q의 질량은 128.05858돌턴이다.

MS2의 결과는 실수의 집합이며, 각각의 실수는 피크라고 부른다. 집합은 단백질의 모든 prefix와 suffix의 질량이 포함(전체 단백질의 질량 포함)되어 있으며, 다른 숫자는 포함되어 있지 않다.

알 수 없는 단백질을 MS2로 실험한 결과가 주어진다. 실험은 오차가 발생할 수 있기 때문에, 결과는 아래 조건을 만족한다.

• 일부 prefix와 suffix의 결과는 집합에 포함되어 있지 않다.
• 단백질의 prefix/suffix 질량에 해당하지 않는 피크가 집합에 포함되어 있을 수도 있다. 이러한 피크를 노이즈 피크라고 한다.
• 모든 피크는 양수이다.
• 가장 큰 피크는 단백질 전체 질량이다.
• prefix/suffix 질량에 해당하는 피크는 정확한 값이다.

실험 결과가 주어졌을 때, 최대 피크가 단백질의 질량이면서, 노이즈 피크의 수가 최소인 단백질을 만드는 프로그램을 작성하시오.

첫째 줄에 MS2의 실험 결과인 피크의 수 n이 주어진다. (1 ≤ n ≤ 100,000)

다음 n개 줄에는 i번째 피크 pi가 주어진다.

항상 문제의 모든 조건을 만족시키며, 모든 피크는 다르다. 각 피크는 소수점 최대 5째자리까지 주어진다.

길이가 최대 400인 P와 Q로 이루어진 문자열(단백질)을 출력한다. 노이즈 피크의 수를 최소로하는 답이 여러 가지인 경우에는 아무거나 출력한다.

가능한 단백질은 PQQ와 QQP이다. 두 단백질 모두 291.15828, 353.16991 결과를 제외하면 얻을 수 있다.