A ball is placed in a maze filled with open cells and walls. The ball can roll up, down, left, or right, but it continues moving in a chosen direction until it encounters a wall. The ball can only change direction after coming to a stop at a wall. Your task is to determine if the ball can eventually stop at a given target location in the maze.

The maze is represented by a string list where each row is a space separated list of integers, where 1 indicates a wall and 0 indicates an open cell. The maze is surrounded by walls. The starting and goal positions are given as row and column indices.

Examples

Example 1:

Input 1: maze =
[
  "0 0 1 0 0",
  "0 0 0 0 0",
  "0 0 0 1 0",
  "1 1 0 1 1",
  "0 0 0 0 0"
]
Input 2: int[] start = {0, 3}
Input 3: int[] goal = {4, 2}

Output: true

Explanation: One valid path is: down → right → down → left.

Example 2:

Input 1: maze =
[
  "0 0 1 0 0",
  "0 0 0 0 0",
  "0 1 0 1 0",
  "1 1 0 1 1",
  "0 0 0 0 0"
]
Input 2: int[] start = {0, 1}
Input 3: int[] goal = {3, 2}

Output: false

Explanation: There is no sequence of moves that lets the ball stop at the goal position.

Constraints

• There is exactly one ball and one goal in the maze.
• Both the ball and the goal start on open cells, and their initial positions are different.
• The maze is surrounded by walls (you may assume all borders are walls).
• The maze dimensions are at least 2x2 and at most 80x80.
• There are at least two open cells in the maze.