题目描述

作者有一个 N 行 M 列的二维表 A。你的任务是构造一台机器，用来计算并保存每个位置 (x, y) 的前缀和，其中 1 <= x <= N，1 <= y <= M。位置 (x, y) 的前缀和定义为：

sum_{i=1..x} sum_{j=1..y} A_{i,j}。

这台机器由若干个节点组成。每个节点有：

• 一个值；
• 一种设置（+ 或 -）；
• 两个孩子（左孩子和右孩子）。

节点的值按如下方式计算：

• 如果该节点设置为 +，则它的值等于两个孩子值之和；
• 如果该节点设置为 -，则它的值等于左孩子的值减去右孩子的值。

此外，你还需要指出 N * M 个节点，分别存储每个位置的一个前缀和。一个节点既可以作为某个前缀和的存储位置，也可以同时承担计算功能。

为了方便，你已经拥有前 N * M 个节点，这些节点中存放了表格 A 的原始值。具体地，单元格 A_{i,j} 存放在编号为 (i - 1) * M + j 的节点中。

请编写程序 machine，输入表格 A 的大小，输出所需机器的构造方案，使得：

• 使用的节点数尽可能少；
• 机器高度尽可能低。

补充说明：

• 节点总数必须始终小于 3 * 10^5，否则该测试点得 0 分；
• “高度”定义为：你添加的某个节点到前 N * M 个原始节点中的某个节点的最大距离。

输入格式

第一行输入两个整数 N 和 M，表示这台机器需要处理的表格大小。

输出格式

第一行输出机器总共使用了多少个节点。注意，这个数量包含前 N * M 个原始节点。

接下来输出一个 N * M 的表格，表示每个前缀和对应存放在哪个节点中。更准确地说，若记该表为 nodes，则 nodes[x][y] 应为某个节点编号，其值等于：

sum_{i=1..x} sum_{j=1..y} A_{i,j}。

随后每行描述一个新节点，格式为：

c = a ⊕ b

其中：

• a、b 分别表示新节点 c 的左孩子与右孩子；
• ⊕ 为 + 或 -；
• 若 ⊕ = -，则节点 c 的值为 a 的值减去 b 的值；
• 若 ⊕ = +，则节点 c 的值为 a 的值加上 b 的值。

数据范围

• 1 <= N, M <= 64

评分方式

测试分为两个子任务。

子任务	分值	额外限制
1	30	N, M <= 16
2	70	无

一项子任务只有在该子任务下所有测试全部通过时，才能获得该子任务的分数。

对于每个测试，会计算两个量：height_mult 和 nodes_mult。

height_mult =
    0                      , 如果 height > 400
    -0.001x + 0.51         , 如果 100 < height <= 400
    -0.003625x + 0.7725    , 如果 20 < height <= 100
    -0.0375x + 1.45        , 如果 12 < height <= 20
    1                      , 如果 height <= 12

其中上式中的 x 表示当前机器的高度 height。

nodes_mult =
    0                      , 如果 nodes > 3 * 10^5
    sqrt((3 * 10^4) / nodes), 如果 3 * 10^4 < nodes <= 3 * 10^5
    1                      , 如果 nodes <= 3 * 10^4

这里的 nodes 为机器使用的节点总数（同样包含前 N * M 个原始节点）。

对每个测试，记

p = height_mult * nodes_mult

若某个子任务满分为 x，并且该子任务中共有 n 个测试点，选手在这些测试上的得分系数分别为 p_1, p_2, ..., p_n，则该子任务最终得分为：

x * min(p_i)   (1 <= i <= n)

原题还特别说明：

• 当 height = 12 时，height_mult = 1；
• 当 height = 20 时，height_mult = 0.7；
• 当 height = 100 时，height_mult = 0.41；
• 当 height = 400 时，height_mult = 0.11；
• 当 height > 400 时，height_mult = 0。

样例

输入

2 2

输出

9
1 5
6 9
5 = 1 + 2
6 = 1 + 3
7 = 5 + 6
8 = 7 + 4
9 = 8 - 1

样例解释

原题此处带有一个 2 × 2 编号示意图，其含义可写成：

1	2
3	4

也就是说，编号 1 到 4 的节点按上面的顺序存放表格中的值。

• 节点 5 将节点 1 与 2 的值相加，因此得到位置 (1,2) 的前缀和；
• 节点 6 与节点 1、3 做了类似的操作，因此得到另一个前缀和。注意：原题原文此处写的是位置 (1,3)，但按题意与样例上下文应为 (2,1)。
• 为了得到位置 (2,2) 的前缀和，先把节点 5 与节点 6 的值相加，再加上节点 4 的值。此时结果保存在节点 8 中；
• 最后再减去节点 1 的值，结果保存在节点 9 中。