UOJ Logo

NOI.AC

1S 512MB

#2467. 寻宝

统计

题目描述

你站在一个 $n\times m$ 的棋盘上,其中第 $x$ 行第 $y$ 列的格子坐标为 $(x,y)$。

每一个格子里面有一个宝箱,其中 $(1,1)$ 这个格子中的宝箱中藏着宝物,而其余的每一个宝箱都藏着一把开启另一个宝箱的钥匙。你在拿到钥匙后就已经知道了这个钥匙可以开启哪一个宝箱。

你现在站在 $(1,1)$,手里拿着一把钥匙。为了拿到宝物,你必须顺次开启若干个宝箱,最后回到 $(1,1)$ 这个格子拿到宝物。

如果你现在站在 $(x_1,y_1)$,而你想到达 $(x_2,y_2)$ 这个点,那么你走过的距离就是 $|x_1-x_2|+|y_1-y_2|$,也就是曼哈顿距离。

现在你想知道,你最多需要走多远的距离才能拿到宝物。构造一组方案。

输入格式

一行两个用空格隔开的正整数 $n,m$。

输出格式

第一行输出一个整数 $l$,表示最远距离。

接下来一行输出一个整数 $k$,表示最远情况下需要经过多少个点。

接下来 $k+1$ 行,每一行输出 $1$ 个坐标,其中第 $i$ 个坐标为 $(x_i,y_i)$,描述一条路径。你需要保证 $x_1=y_1=x_{k+1}=y_{k+1}=1$。

样例1

Input

3 3

Output

24
8
1 1
2 3
3 1
1 2
3 3
2 1
1 3
3 2
1 1

数据范围

对于所有的数据,保证 $1\le n,m\le 1000$。

子任务1:(20分)$n,m\le 3$。

子任务2:(25分)保证 $n,m$ 是偶数。

子任务3:(25分)保证 $n,m$ 是奇数。

子任务4:(30分)无特殊限制。