#P12012. 复活

复活

题目背景

多日的文化课过后,不知道是什么时候传来一些风声,大家将会出去北极几天。

一开始大家也并不在意这些意外的风声,直到那天真的来临。

省选翻盘,看似无望,却何尝没有想过这种可能?

无论如何,这是上天又给了一次机会。

题目描述

你得到了一个 n×mn\times m 的网格图。从学校前往北极沿途每个位置是否有城市已经标注在地图里了,其中北极在 (1,1)(1,1)。每座城市都有一座机场,可以前往周围四个相邻的城市。保证任意两座城市都可达。

你作为航线的规划者希望不会出现浪费人力物力的航线,但是不能让两个城市之间无法联系,即任意两个城市有且仅有一种不经过重复的城市互相到达的方法。所以你需要禁航某些航线。

北极是高贵的,所以距离北极越近的城市就越高贵。我们认为规划航线后除北极外,无法在一步之内走到一个到北极的飞行距离比当前点更远的点的点是乡下。将新图划分为二分图,则要求北极与乡下属于不同的部分,可以证明规划航线后的图一定是二分图。

形式化题意:给定一个四连通网格图。你需要构造出原图的生成树,使得除根外,每个叶子到根的深度为奇数(根深度为 00)。

输入格式

第一行两个正整数 n,mn,m,表示地图的大小。

接下来 nn 行,每行 mm 个字符,表示地图。其中,* 表示这里有一个城市,# 表示没有。

输出格式

第一行为 "win" 或 "hope",其中 "win" 表示你能够完成任务,"hope" 表示不能。

如果你能完成任务,则接下来是任意多行,每行有四个整数 x1,y1,x2,y2x1,y1,x2,y2,表示你没有禁用 (x1,y1)(x1,y1)(x2,y2)(x2,y2) 的航线。你需要保证 x1x2+y1y2=1|x1-x2|+|y1-y2|=11x1,x2n1\le x1,x2\le n1y1,y2m1\le y1,y2\le m

输入输出样例 1

revive1.in revive1.out
4 4
****
#*##
#***
####
win
1 1 1 2
1 3 1 4
2 2 3 2
3 3 3 4
1 2 2 2
1 2 1 3
3 2 3 3

输入输出样例 2

revive2.in revive2.out
3 3
***
#*#
**#
hope

输入输出样例 3

见 revive3.in/out

输入输出样例 4

见 revive4.in/out

说明/提示

数据范围:

子任务编号 分值 特殊性质
subtask 1\texttt{subtask 1} 11 图中除北极外没有城市
subtask 2\texttt{subtask 2} 1717 n,m4n,m\le 4
subtask 3\texttt{subtask 3} 3232 n,m20n,m\le20
subtask 4\texttt{subtask 4} 2424 n,m100n,m\le 100
subtask 5\texttt{subtask 5} 2626

对于所有数据,1n,m3001\le n,m\le 300,地图中的字符只包含 *#,保证 (1,1)(1,1) 一定是 *