#include <iostream>
#include <vector>
#include <string>
#include <tuple>
#include <algorithm>

//小文字大文字は判別する。
//処理速度度返し！！Orz

typedef std::vector<std::tuple<int, int, std::string>> RType;


RType FindRight(const std::vector<std::string>& Vec, const std::string& Word, bool IsRev = false){
	std::size_t Cur = 0;
	std::size_t x = 0, y = 0;
	RType Ret;

	for (std::size_t i = 0; i < Vec.size(); i++){
		for (std::size_t j = 0; j < Vec[i].size(); j++){
			if (Vec[i][j] == Word[Cur]){
				if (Cur == 0){
					x = j;
					y = i;
				}
				Cur++;
			}
			else{
				if (Cur != 0) j--;
				Cur = 0;
			}
			if (Cur == Word.size()){
				if (IsRev == false){
					Ret.push_back(std::make_tuple(y, x, "R"));
				}
				else{
					Ret.push_back(std::make_tuple(i, j, "L"));
				}
				//return Ret;//一個見つけたらやめる
			}
		}
		Cur = 0;
	}
	
	return Ret;
}
RType FindBottom(const std::vector<std::string>& Vec,const std::string& Word,bool IsRev =false){
	std::size_t Cur = 0;
	std::size_t x = 0, y = 0;
	std::size_t j = 0;
	RType Ret;
	std::size_t M = 0;
	while (true){
		for (std::size_t i = 0; i < Vec.size(); i++){
			if (Vec[i].size() < j) continue;
			M = std::max(M, Vec[i].size());
			if (Vec[i][j] == Word[Cur]){
				if (Cur == 0){
					x = j;
					y = i;
				}
				Cur++;
			}
			else{
				if (Cur != 0) i--;
				Cur = 0;
			}
			if (Cur == Word.size()){
				if (IsRev == false){
					Ret.push_back(std::make_tuple(y, x, "D"));
				}
				else{
					Ret.push_back(std::make_tuple(i, j, "U"));
				}
				//return Ret;//一個見つけたらやめる
			}

		}
		Cur = 0;
		j++;
		if (j >= M) break;
	}
	
	return Ret;
}
RType FindNanameMae(std::vector<std::string>& Vec, std::string Word,bool IsRev = false){
	std::size_t vs = Vec.size();
	std::size_t ss = Word.size();
	std::size_t Cur = 0;
	std::size_t x = 0, y = 0;
	bool F = false;
	RType Ret;
	std::vector < std::pair<int, int>> T;
	int A = 0, B = 0;

	for (std::size_t i = 0; i < Vec.size(); i++){
		for (std::size_t j = 0; j < Vec[i].size(); j++){
			for (std::size_t k = 0; k + i < Vec.size() && k + j < Vec[i + k].size(); k++){
				if (Vec[i + k][j + k] == Word[Cur]){
					if (Cur == 0){
						x = j+k;
						y = i+k;
					}
					Cur++;
				}
				else{
					Cur = 0;
				}
				if (Cur == Word.size()){

					if (IsRev == false){
						A = y;
						B = x;
					}
					else{
						A = i+k;
						B = j+k;
					}
					auto P = std::make_pair(A, B);
					for (auto& o : T){
						F = o == P;
						if (F == true) break;
					}
					if (F == true)continue;

					if (IsRev == false){
						T.push_back(std::make_pair(y, x));
						Ret.push_back(std::make_tuple(y, x, "NM"));
					}
					else{
						T.push_back(std::make_pair(i+k, j+k));
						Ret.push_back(std::make_tuple(i+k, j+k, "NMR"));
					}
					//return Ret;//一個見つけたらやめる
				}
			}
			Cur = 0;
		}
	}
	return Ret;
}
RType FindNanameUsiro(std::vector<std::string>& Vec, std::string Word,bool IsRev = false){
	std::size_t vs = Vec.size();
	std::size_t ss = Word.size();
	std::size_t Cur = 0;
	std::size_t x = 0, y = 0;
	bool F = false;
	RType Ret;
	std::vector < std::pair<int, int>> T;
	int A = 0, B = 0;

	for (std::size_t i = 0; i < Vec.size(); i++){
		for (int j = 0; j < Vec[i].size(); j++){
			for (int k = 0; k + i < Vec.size() && j-k >= 0; k++){
				if (Vec[i + k][j - k] == Word[Cur]){
					if (Cur == 0){
						x = j+k;
						y = i+k;
					}
					Cur++;
				}
				else{
					Cur = 0;
				}
				if (Cur == Word.size()){

					if (IsRev == false){
						A = y;
						B = x;
					}
					else{
						A = i+k;
						B = j-k;
					}
					auto P = std::make_pair(A, B);
					for (auto& o : T){
						F = o == P;
						if (F == true) break;
					}
					if (F == true)continue;

					if (IsRev == false){
						T.push_back(std::make_pair(y, x));
						Ret.push_back(std::make_tuple(y, x, "NU"));
					}
					else{
						T.push_back(std::make_pair(i+k, j-k));
						Ret.push_back(std::make_tuple(i+k, j-k, "NUR"));
					}
					//return Ret;//一個見つけたらやめる
				}
			}
			Cur = 0;
		}
	}
	return Ret;
}

RType FindWord(std::vector<std::string>& Vec,const std::string& Word){
	RType Ret;
	auto bs = std::back_inserter(Ret);


	/* */
	auto FR = FindRight(Vec, Word);
	for (auto& o : FR)bs = o;
	/* */
	auto FB = FindBottom(Vec, Word);
	for (auto& o : FB)bs = o;
	/* */
	auto FNM = FindNanameMae(Vec, Word);
	for (auto& o : FNM)bs = o;
	/* */
	auto FNU = FindNanameUsiro(Vec, Word);
	for (auto& o : FNU)bs = o;
	/* */
	std::string T(Word.rbegin(),Word.rend());
	
	/* */
	auto FRR = FindRight(Vec, T, true);
	for (auto& o : FRR)bs = o;
	/* */
	auto FBR = FindBottom(Vec, T,true);
	for (auto& o : FBR)bs = o;
	/* */
	auto FNMR = FindNanameMae(Vec, T,true);
	for (auto& o : FNMR)bs = o;
	/* */
	auto FNUR = FindNanameUsiro(Vec, T,true);
	for (auto& o : FNUR)bs = o;
	/* */
	return Ret;

}


int main(){
	std::vector<std::string> vec = {
		"WVERTICALL",
		"ROOAFFLSAB",
		"ACRILIATOA",
		"NDODKONWDC",
		"DRKESOODDK",
		"OEEPZEGLIW",
		"MSIIHOAERA",
		"ALRKRRIRER",
		"KODIDEDRCD",
		"HELWSLEUTH",
	};
	std::vector<std::string> Words = {
		"WEEK",
		"FIND",
		"RANDOM",
		"SLEUTH",
		"BACKWARD",
		"VERTICAL",
		"DIAGONAL",
		"WIKIPEDIA",
		"HORIZONTAL",
		"WORDSEARCH",
	};
	std::vector<std::string> vec2 = {
		"MAMEMAM",
		"AAoMoAA",
		"MoMAMoM",
		"EMAEAME",
		"MoMAMoM",
		"AAoMoAA",
		"MAMEMAM",
	};

	std::string MAME = "MAME";

	for (std::size_t i = 0; i < Words.size(); i++){
		auto R = FindWord(vec, Words[i]);

		if (R.size() == 0){
			std::cout << Words[i] << " is NotFound!" << std::endl;
			continue;
		}
		std::cout << Words[i] << " is ";
		for (auto& o : R) std::cout << std::get<0>(o)+1 << ',' << std::get<1>(o)+1 << "@" << std::get<2>(o) << ' ';
		std::cout << std::endl;
	}
	auto R = FindWord(vec2, MAME);

	if (R.size() == 0){
		std::cout << MAME << " is NotFound!" << std::endl;
	}
	std::cout << MAME << " is ";
	for (auto& o : R) std::cout << std::get<0>(o)+1 << ',' << std::get<1>(o)+1 << "@" << std::get<2>(o) << ' ';
	std::cout << std::endl;

	return 0;
}