Word Search

Problem Statement

You are playing word search!

The rules of the game is simple: You are given an $n \times m$ grid of letters. You want to find if a given word, $w$ , exists on a straight line in the grid of letters.

For example, if the grid you are playing on is as follows:

Code 1

WGTNPOTSFXQQ
OVOEWPCNRRLX
BDZVNXWLCXJM
NBEZPRLGXHVU
OTTPDIMJSYPJ
XNEKTUFLSFVF
JKPYJHJCYVPR
FLAUQHFWKVVA
RIKDMPJFNUJG
VTDVCECFCPXK

and if you're asked to find the word DEPTH from it, you would be able to find it with the starting letter D starting from $2$ nd column, $3$ rd row:

Code 2

............
............
.D..........
..E.........
...P........
....T.......
.....H......
............
............
............

The word can go in any direction as long as it is in a straight line: East, North, South, West, North-East, North-West, South-East, or South-West.

As a smart kid like you are who even attends MAPS workshops, you have decided to write yourself a little algorithm that could solve word searches for you.

Input

Your first line will contain $n$ and $m$ as space-separated integers. $n$ and $m$ represents the size of the letter grid.

Your next line will contain $w$ , a string of the word you are trying to search for.

Your next $m$ lines will contain $n$ letters each, representing a single row of the letter grid.

Output

The string FOUND if the word $w$ is present in the letter grid, nope otherwise.

Constraints

For all test cases:

$1 \le n,m \le 10^4$
$1 \le |w| \le \text{max}\left(n, m\right)$ ; that is, the word $w$ will always be able to fit on the grid.

Example 1

Input 1

12 10
DEPTH
WGTNPOTSFXQQ
OVOEWPCNRRLX
BDZVNXWLCXJM
NBEZPRLGXHVU
OTTPDIMJSYPJ
XNEKTUFLSFVF
JKPYJHJCYVPR
FLAUQHFWKVVA
RIKDMPJFNUJG
VTDVCECFCPXK

Output 1

FOUND

Example 2

Input 2

4 7
MONASH
QKNP
PAOA
SNMA
UHAJ
UNHS
MBSY
AOAE

Output 2

nope

Example 3

Input 3

40 36
SUPERCALIFRAGILISTICEXPIALIDOCIOUS
OOTFOBAIZIWIUDEKMUYTWIAAZLQEPQQYVFILJEVX
DNRRGLJRHJDFILAWZXCPJGGOFDKAXDLIDFDLLZUK
WXGCCMCWJIBTTDDTQSBFNFWRNQZCNAXUVKAHNNUO
MWAHYIAWGAFCEPFKLUJNKZKIRZMZXVKZRTJNNADR
BXNOKPUNCAECBZEAKOGRCTAUYLMZDRGQKFOLDBJZ
QITUYHPONZRHCBBCFIWYNQORTGOXEDAVHZTNIZND
ETGOBLKTMLAZJGTUACRJRRANJYTHCRJTHLJYYXIJ
MBPVRUOKWGVPJHOUZOUUIFWZBNAEJQBJMCIYNQRZ
OENVWIOOCAMXIXBAMDFNKHFNBAAPLCGUJGMHEKDO
HTQEOJJIGMJQVIIFGIEERMYODPCAXPYXFZMPNATC
BHGHWLAEFXKFLONNELRJHJWBURAQQJIOOFKXBHXC
HHHKENXWFVLFFRPAXADFZIBHOTQJZFWJJKYGXCDO
WJRMEWXPTZQOHAMQUIEAQYEPJZBZLCNRQXLOBQRU
PMRWAKNVDGRHDGQFGPOMTJPFOFFWHYBRXATHPHLD
OVIFBNPYUCFJIKWNNXOYYNAEQGAQDKKNRCZOTGAX
IKBULMKXLYWQWWINKELBBWVFPTQYEPHKKKULADLT
CYRFRHIDQWPPMXARZCGDEMHTTJCURIXVGGRIFFCG
OGBBJKFKBFFXWABJEIEKPJGVWVLIQFVXRQOQDOOU
KRKQRBNADPECOAEKJTEAXAHVIYUKNCNVEZDFHJEE
QMNRNRARCYFGNLYXCSXYEZVGRYCXRILUKYINDMGE
GEDBIBZQRJBJMXKMRIXCEWVLLROVEPCRKWUVVELG
MXHPMJMDOZAFYCUUTLYLCXXFBFKPXGAEBQCYPZRV
WRMVPNIHYPFZXBDDOIXBHVPVKAJCCKVIBVAQMRPV
HBNYGBKFVCWTPZREPGGDRBHQDIAXIRFMKNTDPOLQ
TJRVIYOAREOZQDEJOAYIQVXWYMPNJTWUTKGRKBBK
DVCDIEMRAATXLOJIERTGKYARTLLHITDRPRMVGBUB
CMXILELKURQKBDHVTFHQLCKNJAMGNRFPALGRVAIJ
GKLEKYJPIEFDWNIKCICFIQMZACWALKYDAXOUPRWN
RGRZBHCWHTORTXVZNLYTFWEAXBBUWHRVJPYWHARP
PVTHFGGKFJWVADPVGAOONDNWJWLAZMFXVXJMAZFK
LPLYIFXIJJKLBMVJRCCJUJMPVFQTQXMOBQWVEFYX
LDHRJBZKCAEJVVPZGRIZZETCNZIYCQACBMWGCAEJ
MKJTIQKZJGGKKNNAHEPTGKAZJWNVFNKMRPMOBFJN
OCIWIMHTGJZIXPULNPWYIGNQYRONTAUIPXXUXAVP
EFREVDIOYVIKYXQTBUJGWDTNIIHHERDXVODYWYRI
RINBUWOQZXBKFRVVKSYXFBJLHFIIAHHMVJRGLTCO

Output 3

FOUND

Python Template

Code 3

n, m = map(int, input().split())
word = input()
board = [list(input()) for _ in range(m)]

# print(...)