Fortuna

伟大的凯撒想要得到一个在 0..M-1 上严格均匀的随机整数。

每天，神谕会给出一个真正均匀随机的整数 R，满足 0 <= R < N。你不能直接观察未来的随机数，只能根据当前“卷轴状态”和当天抽到的 R 决定：

• 直接结束，并输出一个答案 T；
• 或者把卷轴改写成另一个状态，留到下一天继续。

原题要求你实现两个函数：

void setup(int N, int M)
std::pair<bool, int> proc(int X, int R)

为了适配 Hydro，这里把题目改写为标准输入输出题：

你需要输出一个有限状态自动机策略，等价地描述你的 proc 行为。

输入格式

输入仅一行两个整数：

N M

含义与原题相同。

输出格式

第一行输出一个整数 K，表示你设计的自动机状态数。

要求：

• 1 <= K <= 500
• 状态编号为 0..K-1
• 初始状态固定为 0

接下来输出 K 行。第 i 行描述状态 i 在所有随机结果下的动作。

对于每个 r = 0..N-1，你需要输出一对整数：

• 0 Y：表示不结束，并把状态改为 Y
• 1 T：表示结束，并输出答案 T

因此每行一共需要输出 2N 个整数，按 r=0,1,2,...,N-1 的顺序给出。

其中：

• 若输出 0 Y，则必须满足 0 <= Y < K
• 若输出 1 T，则必须满足 0 <= T < M

正确性要求

你的输出会被判定程序检查：

1. 从初始状态 0 出发，最终输出的结果必须在 0..M-1 上完全等概率；
2. 过程必须保证最终停止；
3. 平均天数 C 尽量小；若 C > 100，该测试点得分为 0。

评分方式

每个测试点独立评分。

设：

• C* 为该测试点的理论最优平均天数；
• C 为你的策略的平均天数。

定义：

该测试点得分比例为：

数据范围

• 2 <= N, M <= 30
• 1 <= K <= 500

样例

输入

2 3

一组合法输出

3
0 1 0 2
0 0 1 0
1 1 1 2

解释

• 初始状态为 0
• 若第一天抽到 0，转到状态 1
• 若第一天抽到 1，转到状态 2
• 后续按照表中策略继续

这只是某个合法策略；本题答案不唯一。