Dragica 是当地一支半职业保龄球队的队长，她是一位热情的厨师，也可能是克罗地亚最好的填字游戏玩家之一。一个填字游戏由 $N \times M$ 个方格组成，排列成 $N$ 行 $M$ 列。其中一些方格是空的（需要通过回答问题来填入字母），另一些方格是已填充的。已填充的方格最多包含两个问题，分别需要向右水平回答或向下垂直回答。问题的答案会写在空方格中，直到遇到填字游戏的边界或另一个初始已填充的方格为止。如果一个初始已填充的方格右侧存在方格且该方格为空，则它包含一个水平问题。类似地，如果一个初始已填充的方格下方存在方格且该方格为空，则它包含一个垂直问题。
Dragica 通常知道填字游戏所有问题的答案，但她希望阅读并回答尽可能少的问题，同时仍能解决整个填字游戏（即每个空方格都必须被至少一个回答了的问题覆盖）。请帮助她实现这一目标。
输入格式
第一行包含整数 $N$ 和 $M$（$2 \le N, M \le 500$），含义如题面所述。
接下来的 $N$ 行，每行包含 $M$ 个字符 0 或 1。其中 0 表示需要通过回答问题来填充的空方格，1 表示初始已填充的方格（如题面所述，它最多可包含两个问题）。第一行和第一列将全部由字符 1 填充。
保证输入中至少包含一个字符 0。
输出格式
第一行输出为了解决整个填字游戏所需回答的最少问题数。我们将该数量记为 $X$。
接下来的 $X$ 行，每行描述一个需要回答的问题。问题的描述格式应为 R C direction，其中 $R$ 是该问题所在方格的行号，$C$ 是列号，direction 为 DESNO（克罗地亚语中的“向右”，代表水平问题）或 DOLJE（克罗地亚语中的“向下”，代表垂直问题）。
如果存在多个解，输出其中任意一个。
子任务
| 子任务 | 分值 | 限制 |
|---|---|---|
| 1 | 18 | 字符为 1 的方格最多有 9 个 |
| 2 | 32 | $N \le 500$ 且 $M \le 10$ |
| 3 | 60 | 无附加限制 |
如果你的程序在某个子任务的所有测试点中，第一行（最少问题数 $X$）输出正确，但某些测试点的后续行输出不正确，你将获得该子任务 50% 的分数。
样例
输入样例 1
4 5 11111 10000 10000 10000
输出样例 1
3 2 1 DESNO 3 1 DESNO 4 1 DESNO
输入样例 2
6 4 1111 1011 1000 1011 1010 1000
输出样例 2
4 1 2 DOLJE 4 4 DOLJE 5 3 DOLJE 3 1 DESNO
输入样例 3
9 8 11111111 10000000 10001000 10010001 11100001 10100110 10001000 10100001 10010001
输出样例 3
14 5 2 DOLJE 5 8 DOLJE 8 3 DOLJE 2 1 DESNO 3 1 DESNO 3 5 DESNO 4 1 DESNO 4 4 DESNO 5 3 DESNO 6 3 DESNO 7 1 DESNO 7 5 DESNO 8 3 DESNO 9 4 DESNO
说明
第三个样例解释：
与该样例等价的真实填字游戏示例如下图所示。初始已填充的方格被染成黑色，包含至少一个问题的方格被编号。在谜题下方，你可以看到需要向右解决的问题（“Across”列）和需要向下解决的问题（“Down”列）。请注意，某些初始已填充的方格不包含任何问题，某些包含单个问题（例如 8 和 13），而某些包含两个问题（例如 10 和 12）。为了解决这个填字游戏，你至少需要知道输出中列出的 14 个问题的答案。你能解决它吗？
第三个样例对应的填字游戏示例