Problem: Example

Input

2 2
..
..


Output

Second

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (int)(k); i < (int)(n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
#define D10 fixed<<setprecision(10)
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
const int MOD = 1000000007;
const int INF = MOD + 1;
const ld EPS = 1e-12;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }

/*--------------------template--------------------*/
const int dx[] = { -1, 0, 0, 1 }, dy[] = { 0, -1, 1, 0 };
//[const int dx[] = { -1, -1, -1, 0, 0, 1, 1, 1 }, dy[] = { 0, -1, 1, -1, 1, 0, -1, 1 };
bool valid(int x, int y, int h, int w) { return (x >= 0 && y >= 0 && x < h&&y < w); }
int place(int x, int y, int w) { return w*x + y; }

int w, h;
vs fld;
int dp[22][22][22][22];

int grundy(int top, int left, int bottom, int right)
{
	if (dp[top][left][bottom][right] >=0) return dp[top][left][bottom][right];
	set<int> st;
	FOR(i, top, bottom)FOR(j, left, right) 
	{
		if (fld[i][j] == 'X') continue;
		st.insert(grundy(top, left, i, j) ^ grundy(i + 1, left, bottom, j) ^ grundy(top, j + 1, i, right) ^ grundy(i + 1, j + 1, bottom, right));
	}
	int res = 0;
	while (st.count(res)) res++;
	return dp[top][left][bottom][right] = res;
}

int main()
{
	cin.sync_with_stdio(false);
	MS(dp, -1);
	cin >> h >> w;
	fld.resize(h);
	REP(i, h) cin >> fld[i];
	if (grundy(0, 0, h, w)) puts("First");
	else puts("Second");
	return 0;
}