Given an m×n board of characters and a list of words, return all words on the board. Each word must be constructed from letters of sequentially adjacent cells (horizontally or vertically neighbouring). The same cell may not be used more than once in a word.

Example:

Input:
4 4
o a a n
e t a e
i h k r
i f l v
oath pea eat rain

Output:
eat
oath

Constraints:

• m == board.length, n == board[i].length
• 1 ≤ m, n ≤ 12
• board[i][j] is a lowercase English letter.
• 1 ≤ words.length ≤ 3 × 10⁴
• 1 ≤ words[i].length ≤ 10
• All words[i] are unique.

Input format: First line: m n. Next m lines: n space-separated characters. Then one word per line.

Output format: Found words, one per line, sorted lexicographically.