#45 PS

Statement

다다스는 PS를 너무 사랑한 나머지, 어떤 문자열을 보아도 채점 결과가 눈에 들어온다. AC 가 보이면 기분이 좋아지고, WA, TLE, MLE, RE, CE 가 보이면 기분이 나빠진다고 한다.

문자열 $S$ 에 대하여 $f(T)$ 를 $S$ 의 부분수열 중 $T$ 와 일치하는 것의 수라 할 때, 문자열 $S$ 를 보았을 때 다다스의 만족도는 다음과 같이 정의된다.

f(\text{AC})-f(\text{WA})-f(\text{TLE})-f(\text{MLE})-f(\text{RE})-f(\text{CE})

부분수열의 정의

문자열 $S$ 의 부분수열이란, $S$ 에서 $0$ 개 이상의 문자를 제거하여 얻을 수 있는 문자열이다. 예를 들어 $S = \text{``HELLOWORLD''}$ 일 때, 문자열 $\text{``HELL''}$ , $\text{``WORD''}$ 는 모두 $S$ 의 부분수열이다.

엄밀하게는, 길이 $k$ 인 문자열 $T$ 가 길이 $n$ 인 문자열 $S$ 의 부분수열이라 함은, 다음을 만족하는 인덱스 열 $1 \le i_1 < i_2 < \cdots < i_k \le n$ 이 존재함을 의미한다.

S[i_1] = T[1],\; S[i_2] = T[2],\; \ldots,\; S[i_k] = T[k]

$f(T)$ 는 이러한 인덱스 열의 수, 즉 $S$ 에서 $T$ 를 부분수열로 선택하는 방법의 수이다.

예를 들어, $S = \text{``MARKETPLACE''}$ 인 경우, 만족도는 $2 - 0 - 1 - 1 - 2 - 1 = -3$ 이다.

다다스를 최대한 행복하게 해 주고 싶은 모그는, 길이가 $N$ 인 문자열 $S$ 를 적절히 선택하여 만족도를 최대화하고자 한다. 만족도의 최댓값 $M$ 과 그 최댓값을 달성하는 문자열 $S$ 를 구하여라. 단, $S$ 는 알파벳 대문자로만 이루어진 문자열이어야 한다.

$S$ 를 정확하게 구하지 못하더라도 $M$ 의 값을 올바르게 구하면 $50\%$ 의 점수를 받을 수 있다. 자세한 내용은 Scoring 섹션을 참고하라.

Input

입력은 다음과 같은 형식으로 주어진다.

$N$

Output

다음과 같은 형식으로 출력하라.

$M$ $S$

가능한 $S$ 가 여러 개 존재하면, 아무거나 출력한다.

Constraints

$2 \leq N \leq 200 \ 000$ .

Subtasks

#	점수	제한
1	23	$N \leq 4$ .
2	29	$N$ 은 짝수이다.
3	31	$N$ 은 홀수이다.
4	17	추가적인 제약조건이 없다.

Scoring

각 테스트케이스의 점수는 다음과 같이 부여된다.

$M$ 이 올바르지 않으면 $0$ 점.
$M$ 은 올바르지만 $S$ 가 올바르지 않으면 해당 서브태스크 배점의 $50\%$ ( $S$ 를 출력하지 않아도 된다.)
$M$ 과 $S$ 가 모두 올바르면 해당 서브태스크 배점의 $100\%$ .

각 서브태스크의 점수는 해당 서브태스크에 속한 모든 테스트케이스의 점수 중 최솟값이다.

Samples

예제 1

입력

4

출력

4
AACC

이 예제는 서브태스크 1, 2, 4의 조건을 만족한다.

예제 2

입력

5

출력

6
AACCC

이 예제는 서브태스크 3, 4의 조건을 만족한다.

Miscellaneous

AC, WA, TLE, MLE, RE, CE 의 의미

DOJ에서 코드를 제출하면 다음과 같은 채점 결과를 받을 수 있다.

AC (Accepted): 모든 테스트케이스를 통과한 경우.
WA (Wrong Answer): 출력이 정답과 다른 경우.
TLE (Time Limit Exceeded): 제한 시간을 초과한 경우.
MLE (Memory Limit Exceeded): 메모리 제한을 초과한 경우.
RE (Runtime Error): 실행 중 오류가 발생한 경우.
CE (Compile Error): 컴파일에 실패한 경우.

PS