Malnar 先生在 2018 年 3 月末从当地的家庭农场带回了一堆辣椒。他轻松地用绳子将它们以最优的方式连接起来,并无私地分给了朋友们。第一个品尝的是 Dominik,他甚至没感觉到辣味,接着是 Josip,以此类推。然而,Malnar 先生的一些朋友被辣得够呛。其中值得一提的是 Krešimir,他发誓要报复 Malnar 先生。
如今,Malnar 先生不再购买辣椒,而是自己种植。今年,他决定在坐标系中种植 $(N + 1) \cdot (M + 1)$ 株幼苗,使它们位于集合 $\{0, 1, 2, \dots, N\} \times \{0, 1, 2, \dots, M\}$ 的整点上。此外,他决定使用 $(N + 1)(M + 1) - 1$ 段单位长度的绳子将幼苗连接起来,即如果两株幼苗的欧几里得距离为 1,则可以用一段绳子直接连接。此外,幼苗必须连接成一个连通块(即“花环”)。我们称两株幼苗属于同一个花环,如果一只微小的蚂蚁仅通过幼苗和绳子就能在它们之间爬行。
当 $N = 1$ 且 $M = 2$ 时,幼苗连接方式的示例。
Malnar 先生知道 Krešimir 想破坏他的计划。他预感到 Krešimir 会在夜幕掩护下潜入,并进行恰好一次水平或垂直的切割,切断路径上遇到的每一段绳子。已知 Krešimir 不会伤害幼苗本身,但他的切割方式会使初始的花环尽可能多地分裂成多个花环。
因此,Malnar 先生希望以一种方式连接幼苗,使得在 Krešimir 切割后,剩余花环的数量尽可能少。
你能确定一种 Malnar 先生连接幼苗的方式吗?
输入格式
第一行包含自然数 $N$ 和 $M$。
输出格式
输出 $2N + 1$ 行,每行 $3M + 1$ 个字符,表示幼苗通过绳子连接的方式。
幼苗用字符 'o' (ASCII 111) 表示,连接同一列中两株幼苗的绳子用字符 '|' (ASCII 124) 表示,连接同一行中两株幼苗的绳子用字符 '--' (ASCII 45) 表示。
相邻但未被绳子连接的幼苗之间用空格隔开,同一行中相邻幼苗间有两个空格 (ASCII 32),同一列中相邻幼苗间有一个空格 (ASCII 32)。
子任务
对于未能达到最优解的方案,得分计算公式如下:
$$0.75 \cdot \max \left( \left( \frac{A - 1}{B - 1} \right)^4, 1 - \left( 1 - \frac{1}{(B - A)^2} \right)^6 \right) \cdot X$$
其中 $A$ 表示最优解中 Krešimir 切割后的花环数量,$B$ 表示你的方案中对应的数量,$X$ 为该测试点预设的分数。
子任务得分等于该子任务中所有测试点得分的最小值。
| 子任务 | 分数 | 数据范围 |
|---|---|---|
| 1 | 15 | $1 \le N = M \le 1000$ |
| 2 | 15 | $2 \le 2N = M \le 1000$ |
| 3 | 5 | $1 \le N \le M \le 3$ |
| 4 | 10 | $1 \le N \le M \le 10$ |
| 5 | 20 | $1 \le N \le M \le 100$ |
| 6 | 35 | $1 \le N \le M \le 1000$ |
样例
输入 1
2 2
输出 1
o--o o | | o o--o | | o--o--o
输入 2
2 2
输出 2
o--o--o | o o--o | | o--o--o
说明
第一个样例的输出代表了一种最优的连接方式。Krešimir 的切割会将这个花环拆分成三个较小的花环。
第二个样例的输出代表了一种 Malnar 先生最初想到的次优连接方式(注意字母 G 的形状)。Krešimir 的切割会将这个花环拆分成四个较小的花环。对于这种输出,你将获得该测试点总分的 75%。