Zhang3's favorite toy, Steve, has been hit and his head was broken. Zhang3 wants to make a cube as a new head for him.
Zhang3 got a piece of grid paper as material, satisfying the conditions below:
- The grid paper consists of $n \times m$ square units, forming $n$ rows by $m$ columns.
- Some units of the grid paper are broken, the others are usable.
- All of the usable units are 4-connected (two units are directly connected by sharing an edge).
By using some tools, she can do the following things for arbitrary times:
- Cut along an edge on the grid paper. After doing this, the paper mustn't be split into two pieces, i.e., all the usable units are still 4-connected.
- Fold along an edge, so that the two adjacent units form a right angle.
A cube has six faces. Every unit should overlap with one of the six faces. The paper is so thin that it's possible to overlap more than one units at the same face. But it's not allowed to leave a face without any units.
Help Zhang3 determine whether it is possible to make a cube with the grid paper.