L. Linked Letters
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Lua is from Vitória da Conquista, a small city in the countryside of Bahia, or so she claims. Ryei has never bought this story: the city spans over three thousand square kilometers, roughly seventeen times the area of Recife. "Small" and "countryside" are not exactly the words that come to mind.

During a particularly slow afternoon in the lab, Lua came up with a linguistic theory: two words are connected if you can transform one into the other through a chain of mutations, where each mutation swaps a word for another that shares at least one common letter with it. She was convinced this could settle the debate: if she could show that "CONQUISTA" reaches "INTERIOR" through a chain of mutations over a given dictionary, the link between her city and the countryside would be mathematically proven.

Ryei, naturally, wants to disprove every connection she finds. The argument quickly escalated; now the entire lab is involved, and everyone keeps submitting new queries to test.

Given a dictionary of $$$N$$$ words and $$$Q$$$ queries, determine for each query whether word $$$a$$$ can reach word $$$b$$$ through one or more mutations.

Input

The first line contains two integers $$$N$$$ and $$$Q$$$ ($$$2 \le N \le 2 \cdot 10^5$$$, $$$1 \le Q \le 2 \cdot 10^5$$$): the size of the dictionary and the number of queries.

Each of the next $$$N$$$ lines contains a single string $$$s_i$$$ ($$$1 \le |s_i| \le 50$$$) consisting of lowercase English letters. All words are distinct.

Each of the next $$$Q$$$ lines contains two strings $$$a$$$ and $$$b$$$, separated by a space: a query asking whether word $$$a$$$ can reach word $$$b$$$ through one or more mutations. It is guaranteed that both $$$a$$$ and $$$b$$$ appear in the dictionary and that $$$a \neq b$$$.

Output

For each query, print one line containing "LUA" (without quotes) if word $$$a$$$ can be transformed into word $$$b$$$ through a chain of one or more mutations, or "RYEI" (without quotes) otherwise.

Examples
Input
6 4
conquista
interior
recife
capital
lua
ryei
conquista interior
recife capital
conquista recife
lua ryei
Output
LUA
LUA
LUA
LUA
Input
5 5
lua
palao
ryei
grisi
recife
lua palao
ryei grisi
lua ryei
palao recife
grisi palao
Output
LUA
LUA
RYEI
RYEI
RYEI
Input
5 4
ab
bc
cd
da
xyz
ab cd
ab xyz
da xyz
ab da
Output
LUA
RYEI
RYEI
LUA
Note

Note that two words share a common letter if they both contain that letter anywhere in the word, regardless of position. For example, "ab" and "bc" share the letter b, so they are connected.