Given a grid of characters grid with dimensions m x n and a list of strings, words, find all the words present on 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.

The result can be returned in any order.

Input

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

Input: grid = [["e","e","d","f","a","e"],["b","f","f","b","a","a"],["c","e","f","e","e","d"],["d","d","c","f","c","d"],["a","e","f","e","d","d"],["f","f","e","b","d","c"]], words = ["acd","cbbc","fb","efdc"]
Output: ["fb"]
Explanation: The word 'fb' can be formed from adjacent cells on the grid, while others cannot.

Input: grid = [["a","b","c"],["s","f","c"],["d","a","f"]], words = ["abc","bcd","cfa","sfa"]
Output: ["abc","cfa","sfa"]
Explanation: The words 'abc' and 'cfa' can be formed from adjacent cells on the grid.

Input: grid = [["x","y","z"],["a","b","c"],["d","e","f"]], words = ["xyz","abc","def","xzy"]
Output: ["xyz","abc","def"]
Explanation: The words 'xyz', 'abc', and 'def' can be formed from adjacent cells on the grid.

Constraints

• m == grid.length
• n = grid[i].length
• 1 <= m, n <= 12
• 1 <= words.length <= 1000
• 1 <= words[i].length <= 10
• Both grid and words[i] consist only of lowercase English letters
• Each word in the words list is unique