一个 网格的每个格子中都有一个苹果。行从上到下、列从左到右均编号为 到 。
你可以按任意顺序逐个吃掉这 个苹果。初始时,每个苹果的美味值均为100。吃掉一个苹果时,获得等于它当时美味值的分数。随后,所有尚未吃掉且与刚吃掉的苹果的曼哈顿距离不超过2的苹果,其美味值各乘以0.9。
两个格子 、 的曼哈顿距离为 。更新美味值时不进行四舍五入或截断。
你希望使总得分尽可能大。如果输出的顺序恰好包含每个格子一次,吃苹果的总得分将直接作为评测分数。标称满分为 分,但得分不设上限,超过 分的部分也会保留。得分达到 分或更高时判定为 AC。评测使用准确的总得分,而不是显示时四舍五入后的数值。无效顺序得 分。
实际评测数据均为 。 仅用于样例,样例给出总得分最大的顺序。 分的 AC 门槛适用于实际评测数据。
第一行给出一个整数 。
输出 行,表示吃苹果的顺序。第 行输出第 个要吃的苹果的行号 和列号 ,用空格分隔。
该顺序得分为 ,是 网格的最大值。实际评测数据仅使用 。
每个格子必须恰好出现一次。请寻找一个总得分尽可能高的顺序。不要输出分数本身。