罗兰喜欢养花。他最近在笛卡尔坐标系的 (0, 0) 点种植了一朵美丽的玫瑰。这朵玫瑰花如此美丽,罗兰担心邪恶势力会试图偷走它。
为了保护玫瑰,罗兰想要建造n座瞭望塔。我们假设塔是平面上距离玫瑰最多 r 的点。此外,罗兰还假设塔楼应该建在坐标为整数的点上,并且所有对塔楼之间的距离平方和必须尽可能大。请注意,罗兰可能会在同一点建造多个塔,也可能会在点 (0, 0) 建造其中一些塔。
帮助罗兰在整数点建造塔,使所有塔之间的距离平方和尽可能最大。请注意,此问题中的距离定义为点之间的欧几里得距离。
输入
第一行包含两个整数 n 和 r (2 ≤ n ≤ 8; 1 ≤ r ≤ 30)。
输出
在第一行中打印一个整数 - 最大可能的平方距离之和。在接下来的 n 行的第 i 行中,打印两个整数 xi、yi — 第 i 个塔的坐标。每个塔必须位于半径为 r 的圆的内部或边界上。请注意,可能有多个塔位于平面的同一点,也可能有一些塔位于点 (0, 0)。
如果有多个有效的最优安排,请选择其中任何一个。
示例
输入 #1
4 1
输出 #1
16 0 1 0 1 0 -1 0 -1
输入 #2
3 6
输出 #2
312 0 6 5 -3 -5 -3