Given a grid of characters with dimensions m x n, determine if a specified word can be formed by connecting adjacent characters in the grid.

The word can be formed by traveling through adjacent cells, where adjacent cells are those directly next to each other either horizontally or vertically. Each cell in the grid can only be used once for forming the word.

Input

• grid: string[][]: A 2D array of size m x n, where each element is a lowercase English letter
• target: string: A string to be searched for in the grid

Input: grid = [["a","b","c","e"],["s","f","c","t"],["a","d","e","e"]], target = "tee"
Output: true
Explanation: The word 'tee' can be formed starting from the cell (1, 3).

Input: grid = [["a","b"],["c","d"]], target = "abcd"
Output: false
Explanation: The word 'abcd' cannot be formed. There's no way to move from 'b' to 'c' as required by the word.

Input: grid = [["h","e","l","l","o"],["w","o","r","l","d"]], target = "hello"
Output: true
Explanation: The word 'hello' is found in the first row of the grid.

Constraints

• 1 <= grid.length, grid[i].length <= 6
• 1 <= target.length <= 15
• Both grid and target consist only of lowercase English letters