407301: GYM102757 F Maze Design

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

F. Maze Designtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Alice has traveled back in time to Ancient Greece to meet one of her greatest idols, the famous inventor Daedulus. When Alice visits, Daedulus is analyzing a few maze passageways that he is considering including in his latest creation, the soon-to-be famous Labyrinth. Alice jumps at the opportunity to help Daedulus and needs to build a solver that determines if a given maze passageway is solvable or not.

A maze passageway consists of $$$3$$$ rows that each have $$$n$$$ positions. Each position can either be blocked, which means that Alice cannot move through that position, or open, which means that Alice can move through that position. To solve a particular maze passageway, a person can move in any of the cardinal directions, as long as they don't move into a blocked position or go out of bounds of the passageway. Alice can start in any of the $$$3$$$ rows at the first position and can successfully solve the maze if she can reach the final position at any of the $$$3$$$ rows.

Given a particular maze passageway that meets these criteria, you must output Solvable! if Alice can solve the maze passageway and Unsolvable! otherwise.

Input

The first line will consist of a single integer $$$n$$$ ($$$2 \leq n \leq 10^4$$$), which gives the number of positions per row. The next $$$3$$$ lines consist of a string, $$$s$$$, with $$$n$$$ characters that are either 0 or 1, representing a row of the maze passage way. If $$$s_i = $$$ 0, then the $$$i$$$th position in that row is open, and if $$$s_i = $$$ 1, then the $$$i$$$th position in that row is blocked.

Output

Output Solvable! if the maze passageway is solvable and Unsolvable! otherwise.

ExamplesInput
2
00
10
00
Output
Solvable!
Input
2
01
10
10
Output
Unsolvable!

加入题单

上一题 下一题 算法标签: