您想要在大小为 $$$n \times n$$$ 的方形草坪上种植树木,其角点具有笛卡尔坐标 $$$(0, 0)$$$、$$$(n, 0)$$$、$$$(0, n)$$$ 和 $$$(n, n)$$$。树木只能种植在具有整数坐标的位置。每棵树都会在以树种植位置为中心、半径为 $$$r$$$ 的圆盘内生长根;这些圆盘必须完全包含在草坪中(可能接触草坪的边界)并且只能在其边界上彼此相交。
找到最大化树数量的配置。
输入
第一行也是唯一一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 20$$$) 和一个实数 $$$r$$$ ($$$0 < r \leq n/2$$$) — 草坪边的长度,以及每棵树将生长根部的圆盘的半径。实数 $$$r$$$ 以十进制表示,小数点后最少为 $$$1$$$,最多为 $$$3$$$ 位。
输出
在第一行中,打印可以种植的最大树木数$$$m$$$。
在接下来的 $$$m$$$ 行中,打印最大化树数量的配置。具体来说,在第 $$$(i+1)$$$ 行中,打印两个整数 $$$x$$$ 和 $$$y$$$ — 应种植第 $$$i$$$ 树的位置的坐标。您可以按任何顺序打印树木。
如果有多个解决方案,请打印其中任何一个。
示例
输入 #1
6 1.241
输出 #1
2 4 2 2 4
输入 #2
9 2.0
输出 #2
4 2 2 7 2 2 6 6 6
注意
对于第一个示例,示例输出如下图所示。请注意,这不是最大化树数量的唯一配置。
对于第二个示例,示例输出如下图所示。请注意,这不是最大化树数量的唯一配置。