CF1598A Computer Game

Monocarp is playing a computer game. Now he wants to complete the first level of this game. A level is a rectangular grid of $ 2 $ rows and $ n $ columns. Monocarp controls a character, which starts in cell $ (1, 1) $ — at the intersection of the $ 1 $ -st row and the $ 1 $ -st column. Monocarp's character can move from one cell to another in one step if the cells are adjacent by side and/or corner. Formally, it is possible to move from cell $ (x_1, y_1) $ to cell $ (x_2, y_2) $ in one step if $ |x_1 - x_2| \le 1 $ and $ |y_1 - y_2| \le 1 $ . Obviously, it is prohibited to go outside the grid. There are traps in some cells. If Monocarp's character finds himself in such a cell, he dies, and the game ends. To complete a level, Monocarp's character should reach cell $ (2, n) $ — at the intersection of row $ 2 $ and column $ n $ . Help Monocarp determine if it is possible to complete the level.

N/A

N/A

Consider the example from the statement. In the first test case, one of the possible paths is $ (1, 1) \rightarrow (2, 2) \rightarrow (2, 3) $ . In the second test case, one of the possible paths is $ (1, 1) \rightarrow (1, 2) \rightarrow (2, 3) \rightarrow (2, 4) $ . In the fourth test case, one of the possible paths is $ (1, 1) \rightarrow (2, 2) \rightarrow (1, 3) \rightarrow (2, 4) \rightarrow (1, 5) \rightarrow (2, 6) $ .