Popcount

Miniature Algebraic Natural Relay (MALNAR)는 소형 프로그램 가능 장치 분야의 최신 기술이다. 이 장치를 위해 MalnarScript라는 난해한 프로그래밍 언어로 직접 프로그램을 작성할 수 있다. 이 언어의 기능은 다음과 같다.

• 프로그램의 입력은 2N보다 작은 음이 아닌 정수 하나이다.
• 프로그램의 출력은 2N보다 작은 음이 아닌 정수 하나이다.
• MalnarScript로 프로그래밍할 때 N비트 부호 없는 정수 변수 A 하나만 사용할 수 있다. 프로그램 시작 시 이 변수에는 입력이 들어 있고, 프로그램 종료 시 이 변수의 값이 프로그램의 출력이 된다.
• MalnarScript 소스 코드는 A=<expr> 형태의 명령 K개 이하로 구성되며, 명령은 순서대로 실행된다. 각 명령은 최대 1000자이다. 기호 <expr>은 다음과 같이 재귀적으로 정의된다.

<expr> = A | <num> | (<expr><operator><expr>)

다시 말해 기호 <expr>은 변수 A이거나, 기호 <num>의 정의를 따르거나, 괄호 안에서 두 개의 피연산자가 각각 같은 <expr> 정의를 따르는 이항 식을 나타낼 수 있다.

위 정의에서 기호 <num>은 2N보다 작은 음이 아닌 십진 정수를 나타내고, 기호 <operator>는 +, -, |, &, <<, >> 중 하나이며 각각 덧셈, 뺄셈, 비트 OR, 비트 AND, 왼쪽 시프트, 오른쪽 시프트를 뜻한다.

또한 <expr> 안에 문자 A는 최대 5번 나타날 수 있다.

덧셈과 뺄셈에서 오버플로나 언더플로가 발생하면 MalnarScript는 그 연산을 2N에 대한 나머지로 수행한다. 예를 들어 N = 3일 때 식 (7 + 3)은 MalnarScript에서 2로, 식 (2 - 5)는 5로 계산된다.

각 명령의 등호 오른쪽은 하나의 수로 계산되어 A에 저장된다. 오른쪽 식을 계산할 때 MalnarScript는 먼저 A가 나타날 때마다 현재 값으로 바꾼다. 그다음 식을 일반적인 수학 식처럼 계산하며, 괄호가 우선한다. 최종 결과는 괄호 배치로 완전히 결정되므로 연산자 우선순위는 상관없다.

여러분의 임무는 입력값의 이진 표현에 있는 1의 개수를 계산하는 MalnarScript 프로그램을 출력하는 프로그램을 작성하는 것이다.

첫째 줄에 문제 설명에 나온 두 정수 N과 K가 주어진다.

첫째 줄에 여러분이 만든 MalnarScript 프로그램의 명령 개수를 출력한다.

나머지 줄에 그 프로그램의 명령을 출력한다. 각 명령은 한 줄에 하나씩 출력해야 하며 문제 설명에 나온 MalnarScript 문법을 만족해야 한다.

출력에 불필요한 빈 줄이나 여분의 공백 문자가 있어서는 안 된다. 각 줄은 마지막 줄까지 줄 바꿈 문자('\n')로 끝나야 한다.