题目描述

Gosho 在英国学习信息学，假期将回到保加利亚。和大多数学生一样，他想顺路去见一些在欧洲各地学习的朋友，但又负担不起昂贵的旅行。因此，他计划向着亲爱的祖国方向，也就是一路向南和向东，通过跑步和游泳横穿大陆。

如果把欧洲地图划分成正方形区域，那么旅程必须从坐标为 $(1,1)$ 的区域开始，并在坐标为 $(N,N)$ 的区域结束。Gosho 知道如何计算坐标为 $(x,y)$ 的区域中有多少朋友在学习，这个数记为 $F(x,y,B,P)$：

inline int F(long long x, long long y, int B, int P) {
    return ((x * B) ^ ((y + 1) * B)) % P;
}

这个贫穷的一年级学生希望找到一条路线，使得能遇到的朋友总数尽可能多。每一步只能向南或向东移动到相邻区域，不能走出地图。也就是说，从区域 $(x,y)$ 可以移动到 $(x+1,y)$ 或 $(x,y+1)$，前提是新的两个坐标都不超过 $N$。

注意！突然间，Gosho 变成了你，而你已经出发了！你只能在口袋里偶然留下的一张小公交车票背面做计算。

请编写程序 maxpath，求出所需的路线。

输入格式

输入仅一行，包含三个整数 $N,B,P$，用单个空格分隔。

输出格式

第一行输出一个整数，表示你能遇到的朋友数量最大值。

接下来输出 $2N-1$ 行，每行输出两个自然数，用空格分隔，表示找到的路径上第 $i$ 个区域的坐标 $x_i,y_i$。

如果存在多个最优解，输出任意一个即可。

数据范围

• $2 \le N \le 10000$；
• $2 \le B,P \le 2 \cdot 10^8$；
• $P$ 与 $B$ 互质，且 $B>P$；
• 在 $20\%$ 的测试中，$N<1500$；
• 每个测试的内存限制为 $2$ MB。

样例

输入

3 57 13

输出

30
1 1
1 2
2 2
2 3
3 3

样例解释

样例输入对应的矩阵为：

10 3 0
 0 9 7
 9 0 1