微型代数自然继电器(Miniature Algebraic Natural Relay,也称为 MALNAR)是微型可编程设备蓬勃发展领域的最新技术突破。你可以使用 MalnarScript 为该设备编写自己的程序,这是一种具有以下特性的奇特(esoteric)编程语言:
- 程序的输入是一个严格小于 $2^N$ 的非负整数。
- 程序的输出是一个严格小于 $2^N$ 的非负整数。
- 在 MalnarScript 中编程时,你只能使用一个 $N$ 位无符号整数变量 $A$。在程序开始时,该变量保存输入值,程序结束时其值被视为程序的输出。
MalnarScript 的源代码必须由最多 $K$ 条形如
A=<expr>的命令组成,这些命令按顺序执行,且每条命令必须由最多 $1000$ 个字符组成。符号<expr>递归定义如下:<expr> = A | <num> | (<expr><operator><expr>)
换句话说,符号 <expr> 既可以是一个变量 $A$,也可以符合符号 <num> 的定义,或者可以(在括号内)表示一个双目表达式,其中每个操作数都符合相同的 <expr> 定义。
上述定义中的符号 <num> 表示一个严格小于 $2^N$ 的非负十进制整数,而符号 <operator> 可以是 +、-、|、&、<< 或 >>,它们(按顺序)分别表示加法、减法、按位或、按位与、左移和右移操作。
此外,字符 $A$ 在 <expr> 符号中最多只能出现 $5$ 次。
在进行加法和减法操作时,如果发生上溢(overflow)或下溢(underflow),MalnarScript 将对这些操作进行模 $2^N$ 的运算。例如,当 $N = 3$ 时,表达式 (7 + 3) 的计算结果为 $2$,而表达式 (2 - 5) 的计算结果在 MalnarScript 中为 $5$。
每条命令中等号右侧的表达式会计算出一个单一的数值,然后将其存储到 $A$ 中。为了计算右侧表达式的值,MalnarScript 首先将所有出现的 $A$ 替换为其当前值。然后,表达式的计算过程与任何数学表达式相同,即括号具有最高优先级。注意,运算符的优先级(就运算顺序而言)是无关紧要的,因为最终结果完全由括号的嵌套位置决定。
你的任务是编写一个程序,输出一个 MalnarScript 程序,该程序能够计算输入值二进制表示中 $1$ 的个数。
输入格式
第一行包含两个整数 $N$ 和 $K$,含义如题目描述所示。
输出格式
第一行应输出生成的 MalnarScript 程序的命令条数。
在接下来的各行中,你应该输出所求程序的命令。每条命令必须打印在单独的一行中,并且必须满足题目描述中 MalnarScript 的语法。
输出中不能有不必要的空行或多余的空格字符。每行(包括最后一行)必须以换行符('\n')结束。
子任务
| 子任务 | 分值 | 数据范围 |
|---|---|---|
| 1 | 15 | $2 \le N \le 100$, $K = N - 1$ |
| 2 | 15 | $N = 500$, $K = 128$ |
| 3 | 35 | $1 \le N \le 40$, $K = 7$ |
| 4 | 45 | $100 \le N \le 500$, $K = 10$ |
样例
输入样例 1
2 2
输出样例 1
1 A=(A-((A&2)>>1))
输入样例 2
3 5
输出样例 2
2 A=((A&4)|((A&3)-((A&2)>>1))) A=((A&3)+((A&4)>>2))
说明
样例 1 说明
- $\text{input} = 0 \Rightarrow \text{output} = (0 - ((0 \& 2) \gg 1)) = (0 - (0 \gg 1)) = (0 - 0) = 0$
- $\text{input} = 1 \Rightarrow \text{output} = (1 - ((1 \& 2) \gg 1)) = (1 - (0 \gg 1)) = (1 - 0) = 1$
- $\text{input} = 2 \Rightarrow \text{output} = (2 - ((2 \& 2) \gg 1)) = (2 - (2 \gg 1)) = (2 - 1) = 1$
- $\text{input} = 3 \Rightarrow \text{output} = (3 - ((3 \& 2) \gg 1)) = (3 - (2 \gg 1)) = (3 - 1) = 2$