题目描述

你负责规划一座新城市。城市由一个矩形网格表示，每个格子要么是公园，要么是建筑区域。

居民自然会希望在城市的公园中散步。我们定义一个矩形步道：它由网格中的一个矩形区域组成，并且满足：

• 横向和纵向长度都至少为 $2$ 个格子；
• 该矩形边界上的所有格子都是公园；
• 矩形内部的格子可以任意，不要求是公园。

下面给出了一个矩形步道的示例，深色背景的格子构成该步道的边界。

矩形步道示例

你最喜欢的数字是 $k$。为了在城市中留下长久的印记，你希望设计一个恰好包含 $k$ 个矩形步道的城市。

输入格式

输入仅包含一个整数 $k$：

输出格式

第一行输出两个整数 $h,w$，分别表示网格的高度和宽度：

接下来输出 $h$ 行，每行包含一个长度为 $w$ 的字符串：

• # 表示公园；
• . 表示建筑区域。

保证对于所有满足约束的 $k$，都存在高度和宽度不超过 $2025$ 的合法方案。

只要输出的网格满足尺寸限制，并且恰好包含 $k$ 个矩形步道，就会被接受。

样例 1

输入

5

输出

3 4
####
#.##
####

样例说明

样例网格中共有下面五个矩形步道：

样例中的五个矩形步道