Limits 1s, 256 MB

In the heart of ICPC's code-filled realm, you encountered a cryptic two-dimensional character array consisting of lowercase latin letters. But, here's the twist: vowels (a,e,i,o,u)(a, e, i, o, u) were ignored to create a labyrinth of consonants. As you navigate through this labyrinth using the directions (left, right, up, and down) provided, you'll collect characters to create a secret message. After decoding this message, you'll face a set of thrilling word challenges.

There are two key steps to your quest:

  1. ArrayNavigationArray Navigation: Your journey starts at the top-left cell (0,0)(0,0), where you'll follow the given directions (lleft,rright,uup,ddown)(l-left, r-right, u-up, d-down) in sequence. During your journey, you must record the characters you collect while ignoring Vowels. Your objective is to display the string after navigating the array.

  2. QueryHandlingQuery Handling: After you've collected a sequence of characters using ArrayNavigationArray Navigation, you'll receive a series of word queries. Your mission is to determine if each query word can be formed using the collected characters while preserving their order. That means if you pick a character from ithi^{th} index of the navigated string to form a query word, you can not pick a character from the lower index anymore.

Input

First line of the test case contains four integers: n,m,ln, m, l and qq representing the array dimensions, length of the string of valid direction and the number of queries separated by spaces.

Each of the next nn lines contains a string of mm characters consist of lowercase latin letters.

The next line contains the string SdS_d of valid directions for ArrayNavigationArray Navigation.

Finally, each of the next qq lines contains a query string SqS_q consist of lowercase latin letters.

1n,m,l,q1031 ≤ n, m, l, q ≤ 10^3

SdS_d== {l,r,u,dl, r, u, d}

1Sq1031≤ S_q ≤ 10^3

Output

First line of the output contains a single string formed by ArrayNavigationArray Navigation.

For each of the next qq lines, print "YES" if the query string can be formed using QueryHandlingQuery Handling and "NO" otherwise without quotations.

Samples

InputOutput
3 3 6 2
aei
ouk
btc
rrdldl
bk
kb
ktb
NO
YES

Word bkbk can not be formed because, after picking character bb you can not pick kk as it is situated in lower index.

Word kbkb can be formed because, first you can pick kk and then you can pick bb from higher index.

InputOutput
4 4 11 3
rnst
xiue
aorp
bzei
dudrurrddlu
p
noise
str
rxrxnstpr
YES
NO
YES

Submit

Login to submit.

Statistics

67% Solution Ratio
murshed336Earliest, 5M ago
Tanvir_580Fastest, 0.0s
Tanvir_580Lightest, 5.2 MB
Shahriar.888Shortest, 1663B
Toph uses cookies. By continuing you agree to our Cookie Policy.