喵喵很喜歡玩 Minecraft。Minecraft 因為能創造屬於自己的世界，一直令他很著迷，所以喵喵很喜歡找他的朋友，汪汪跟他一起玩。但是汪汪有點怕水，他每次都會不小心在挖礦的時候挖到水然後被沖走。為了更了解 Minecraft 水流的流動，他今天想要透過程式來計算水流的流動。

今天 Minecraft 是 2D 版本，有一個地圖從 $(1, 1)$ 到 $(M, N)$
開始每次水流會在座標 $(\lfloor \frac{M + 1}{2} \rfloor, N)$ 的地方開始重力往下流動。為了簡化，如果水流撞到底部，他會往所有沒有方塊的那個方向流動至多 $K$ 格。若過程中水流底部沒有方塊，則水流會往下。若碰到方塊或移動 $K$ 格後會停下。
如果水流撞到底部且兩邊都有方塊，則該水流會停下。此外，地圖外的方格均視為方塊。

注意在這樣的條件下，兩道水流也有可能合併成一道水流。