你有一个 4x4 的网格。您玩一个游戏 - 有一系列图块,每个图块都是 2x1 或 1x2。您的任务是将给定序列中的所有图块放置在网格中。放置图块时,位于完全占据的行或列中的每个单元格都会被删除(同时独立地删除单元格)。您可以将图块放置在网格中的任何位置,唯一的条件是图块(和图块部分)不应重叠。您的目标是完成所有给定的数字并避免随时交叉。
输入
唯一的行包含一个由零和一组成的字符串 $$$s$$$ ($$$1 \le |s| \le 1000$$$)。零描述垂直平铺,一描述水平平铺。
输出
输出 $$$|s|$$$ 行 - 对于每个图块,您应该输出两个正整数 $$$r,c$$$,不超过 $$$4$$$,表示与其相交的最小行和列的数量。
如果存在多个解决方案,则打印其中任何一个。
示例
输入 #1
010
输出 #1
1 1 1 2 1 4
注意
下图展示了放置所有三个图块后的示例: