에일리언을 알아보자

우리 세계는 사람을 납치하고 그들의 신분을 훔치는 변신 에일리언의 침공을 받았다. 당신은 이들을 색출하고 체포하는 전담 태스크 포스의 감시관이다. 그래서 에일리언을 탐지하고 진짜 인간과 구별할 수 있는 특수 장비를 받았다. 이번 임무는 침공이 의심되는 도시를 방문해, 그곳의 모든 사람을 몰래 조사해 누가 에일리언이고 누가 아닌지 알아낸 뒤 본부에 보고하는 것이다. 그러면 본부는 병력을 도시에 기습적으로 보내 모든 에일리언을 한 번에 체포할 수 있다.

에일리언은 당신 같은 감시관의 활동을 알고 있으며, 그런 보고의 전송을 탐지하려고 모든 무선 채널을 감시한다. 그래서 보고를 암호화하려는 여러 시도가 있었고, 가장 최근의 방법은 다항식을 사용한다.

당신이 방문할 도시에는 N명의 시민이 있고, 각 시민은 2부터 2N까지의 서로 다른 짝수 정수로 식별된다. 당신은 모든 시민 i에 대해, 시민 i가 인간이면 P(i) > 0이고 그렇지 않으면 P(i) < 0인 다항식 P를 찾아야 한다. 이 다항식이 본부로 전송된다. 대역폭을 최소화하기 위해 다항식에는 몇 가지 추가 조건이 붙는다. 모든 근과 계수는 정수여야 하고, 최고차항의 계수는 1 또는 −1이어야 하며, 차수는 가능한 한 낮아야 한다.

각 시민이 인간인지 아닌지는 알고 있다. 이 정보가 주어졌을 때, 위 조건을 만족하는 다항식을 찾아야 한다.

입력은 길이 N(1 ≤ N ≤ 104)인 문자열 S 한 줄로 이루어진다. 여기서 N은 도시의 인구이다. i = 1, 2, . . . , N에 대해 S의 i번째 문자는 대문자 “H” 또는 대문자 “A”이며, 각각 시민 2i가 인간인지 에일리언인지를 나타낸다.

첫째 줄에는 위 조건을 만족하는 다항식의 차수 D를 나타내는 정수를 출력한다. 둘째 줄에는 다항식의 계수 D + 1개를 해당 항의 차수가 큰 순서대로 출력한다. 각 계수의 절댓값이 263보다 작은 해가 적어도 하나 존재함이 보장된다.