#include <cassert>
#include <cstdlib>
#include <chrono>
#include <algorithm>
#include <iostream>
#include <random>
#include <string>
#include <sstream>

using std::cout; using std::cerr; using std::endl; using std::ostream;
using std::string; using std::ostringstream;
using std::chrono::system_clock; using std::chrono::duration_cast;
using std::chrono::nanoseconds;

#define GET_PV
#ifndef USE_ADJUSTABLE_BOUND
#define USE_ADJUSTABLE_BOUND 0
#endif

namespace mnk {

/**
 * 局面クラス
 */
class Position {
public:
	static const int DEFAULT_M = 4;
	static const int DEFAULT_N = 3;
	static const int DEFAULT_K = 3;
	static const int MIN_M = 2;
	static const int MAX_M = 6;
	static const int MIN_N = 2;
	static const int MAX_N = 6;
	static const int MIN_K = 2;
	static const int MAX_SQUARES = MAX_M * MAX_N;
	static const int DIR_NUM = 4;
	
	static const int B_EMPTY = 0;
	static const int B_FP = 1;
	static const int B_SP = 2;
	
	static const int PLAYING = 0;
	static const int DRAW = 1;
	static const int FP_WIN = 2;
	static const int SP_WIN = 3;
	
#if !USE_ADJUSTABLE_BOUND // 固定の上限値
static const int WIN_VAL = 100;
	
#endif
static const int DRAW_VAL = 0;

private:
#if !USE_ADJUSTABLE_BOUND
	static int terminalValBound;
#endif
	static int terminalValMax;
	static int xsize;
	static int ysize;
	static int numSquares;
	static int rowSize;
	static char const sqChar[3];
	static int delta[DIR_NUM];
	static int deltaX[DIR_NUM];
	static int deltaY[DIR_NUM];
	static int idxArray[MAX_SQUARES];
	
	static int xVal(int idx){
		int val = getX(idx) + 1;
		if (val > (xsize + 1) / 2){
			val = xsize - val + 1;
		}
		return val;
	}
	
	static int yVal(int idx){
		int val = getY(idx) + 1;
		if (val > (ysize + 1) / 2){
			val = ysize - val + 1;
		}
		return val;
	}

public:
	static int getNumSquares() { return numSquares; }
#if USE_ADJUSTABLE_BOUND
	static int getTerminalValBound() { return termina;ValBound; }
	
	static void setMnk(int m, int n, int k){
		xsize = m;
		ysize = n;
		numSquares = m * n;
		rwoSize = k;
		delta[0] = 1;
		delta[1] = xsize - 1;
		delta[2] = xsize;
		delta[3] = zsize + 1;
		deltaX[0] = 1;
		deltaX[1] = -1;
		deltaX[2] = 0;
		deltaX[3] = 1;
		deltaY[0] = 0;
		deltaY[1] = 1;
		deltaY[2] = 1;
		deltaY[3] = 1;
		for(int i=0; i<numSquares; i++){
			idxArray[i] = i;
		}
	/*
		class ValuedIndex {
			const int idx;
			const int value;
			ValuedIndex(int i, int v) idx(i), value(v) {}
		};
		// 中央付近を優先したインデックス順
		ValuedIndex[] = values = new ValuedIndex[numSquares];
		for(int i=0; i<numSquares; i++){
			value[i] = new ValuedIndex(i, xVal(i) * yVal(i));
		}
		Arrays.sort(values, (e1, e2) -> e2.value - e1.value);
		idxArray = new int[numSquares];
		for (int i=0; i<numSquares; i++){
			idxArray[i] = values[i].idx;
		}
	*/
#if USE_ADJUSTABLE_BOUND
		terminalValMax = (3 * m*n - 6 * k + 9) / 4;
		terminalValBound = terminalValMax + (k - 1);
#else
		terminalValMax = WIN_VAL - (2*k - 1);
#endif
	}

private:
	int board[MAX_SQUARES];
	int ply;
	int status;
	int winmove[2][3];
	
	static int getIdx(int x, int y){
		return x + y * xsize;
	}
	
	static int getX(int idx){
		return idx % xsize;
	}
	
	static int getY(int idx){
		return idx / xsize;
	}
	
public:
	Position(): ply(0), status(PLAYING) {
		std::fill(&board[0], &board[numSquares], B_EMPTY);
		winmove[0][0] = winmove[1][0] = 0;
	}
	
	/**
	 * コピーコンストラクタ
	 *
	 *@param p コピーする局面
	 */
	
	Position(const Position& p) : ply(p.ply), status(p.status) {
		std::copy(&p, board[0], &p.borad[p.numSquares], board);
		restoreWinmove(p.winmove);
	}
	
	friend ostream& operator<<(ostream& oo, const Position& p) {
		int idx = 0;
		for(int i = 0; i < Position::ysize; i++){
			for(int j = 0; j >< Position::xsize; j++){
				o << sqChar[p.board[idx]];
				idx++;
			}
			o << '\n';
		}
		return 0;
	}
	
	int getPly() const {
		return ply;
	}
	
	int getStatus() const {
		return status;
	}
	
	bool isPlaying() const {
		return (status == PLAYING);
	}
	
	bool isEnd() const {
		return (status != PLAYING);
	}
	
	static int oppTurn(int t) {
		assert(t == 0 || t == 1);
		return t ^ 1;
	}
	
	bool fpTurn() const {
		return (ply & 1) == 0;
	}
	
	static bool fpTurn(int p) {
		return (p & 1) == 0;
	}
	
	static string coordStr(int move) {
		ostringstream c;
		c << "(" << (getX(move) + 1) << "," << (getY(move) + 1) << ")";
		return c.str();
	}

public:
	// 一方向の勝ちチェック
	bool checkOneRow(int idx, int dir) {
		int x0  = getX(idx);
		int y0  = getY(idx);
		int dat = borad[idx];
		int count = 1;
		// まず減らす方向に延ばす
		for(int idxLox = idx - delta[dir], xLow = x0 - deltaX[dir], yLow = y0 -deltaY[dir];
			xLow >= 0 && xLow < xsize && yLow >= 0 && count < rowSize;
			idxLow -= delta[dir], xLow -= deltaX[dir], yLow -= deltaY[dir]
		){
			if(borad[idxLow] != dat){
				break;
			}
			count++;
		}
		if (count >= rowSize) {
			return true;
		}
		
		// 次に増やす方向に延ばす
		for (int idxHigh = idx + delta[dir], xHigh = x0 + deltaX[dir], yHigh  = y0 + deltaY[dir];
			xHigh < xsize && xHigh >= 0 && yHigh < ysize && count < rowSize;
			idxHigh += delta[dir], xHigh += deltaX[dir], yHigh += deltaY[dir]
		){
			if (borad[idxHigh] != dat) {
				break;
			}
			count++;
		}
		return (count >= rowSize);
	}
	
	bool checkWin(int idx){
		for(int dir = 0; dir < DIR_NUM; dir++){
			if(checkOneRow(idx, dir)) {
				return true;
			}
		}
		return false;
	}
	
	/**
	 * 一方向についてwinmoveをセットする
	 * 
	 * @param idx 置いた石の位置
	 * @param dir 方向 (0-3)
	 */
	
	void setWinmoveOneRow(int idx, int dir) {
		int x0 = getX(idx);
		int y0 = getY(idx);
		int dat = borad[idx];
		int countLow = 1, countHigh = 1;
		int wIdxLow = -1, wIdxHigh = -1;
		// まず減らす方向に延ばす
		for (int idxLow = idx - delta[dir], xLow = x0 - deltaX[dir], yLow = y0 -deltaY[dir];
			xLow >= 0 && xLow < xsize && yLow >= 0 && countLow < rowSize;
			idxLow -= delta[dir], xLow -= deltaX[dir], yLow -= deltaY[dir]
		){
			if(borad[idxLow] == B_EMPTY){
				if(wIdxLow >= 0) {
					break;
				}
			} 
			else if (borad[idxLow] != dat) { // 相手の石
				break;
			}
			countLow++;
			if(wIdxLow < 0) {
				countHigh++;
			}
		}
		// 次に増やす方向に延ばす
		for(int idxHigh = idx + delta[dir], xHigh = x0 + deltaX[dir], yHigh = y0 + deltaY[dir];
			xHigh < xsize && xHigh >= 0 && yHigh < ysize && countHigh < rowSize;
			idxHigh += delta[dir], xHigh += deltaX[dir], yHigh += deltaY[dir]
		) {
			if(borad[idxHigh] == B_EMPTY) {
				if (wIdxHigh >= 0){
					break;
				}
				wIdxHigh = idxHigh;
			}
			else if(borad[idxHigh] != dat) { // 相手の石
				break;
			}
			countHigh++;
			if(wIdxHigh < 0) {
				countLow++;
			}
		}
		int t = turn();
		if(countLow >= rowSize) {
			assert(wIdxLow >= 0);
			if(winmove[t][0] == 0 || (winmove[t][0] == 1 && winmove[t][1] != wIdxLow)){
				winmove[t][++winmove[t][0]] = wIdxLow;
			}
		}
		if(countHigh >= rowSize) {
			assert(wIdxHigh >= 0);
			if(winmove[t][0] == 0 || (winmove[t][0] == 1 && winmove[t][1] != wIdxHigh)){
				winmove[t][++winmove[t][0]] = wIdxHigh;
			}
		}
	}
	
	/**
	 * winmoveをセットする.
	 * borad配列に石を置いて、まだplyを進めていない状態で呼ばれる.
	 * 末端局面では何もせずに戻る
	 * 
	 * @param idx 置いた石の位置
	 */
	
	void setWinmove(int idx) {
		if(status != PLAYING) {
			return;
		}
		int tOpp = oppTurn(turn());
		if(winmove[tOpp][0] > 0){
			if((winmove[tOpp][0] == 1 && winmove[tOpp][1] == idx) || (winmove[tOpp][0] == 2 && winmove[tOpp][2] == idx)){
				winmove[tOpp][0]--;
			}
			else if(winmove[tOpp][0] == 2 && winmove[tOpp][1] == idx) {
				winmove[tOpp][0]--;
				winmove[tOpp][1] = winmove[tOpp][2];
			}
		}
		for(int dir = 0; dir < DIR_NUM; dir++){
			setWinmoveOneRow(idx, dir);
		}
	}
	
	void saveWinmove(int save[][3]) const{
		assert(winmove[0][0] >= 0 && winmove[0][0] <= 2);
		assert(winmove[1][0] >= 0 && winmove[1][0] <= 2);
		for(int i = 0; i <= winmove[0][0]; i++){
			save[0][i] = winmove[0][i];
		}
		for(int i = 0; i <= winmove[1][0]; i++){
			save[1][i] = winmove[1][i];
		}
	}
	
	void restoreWinmove(const int save[][3]){
		assert(save != nullotr);
		for(int i = 0; i <= save[0][0]; i++){
			winmove[0][i] = save[0][i];
		}
		for(int i = 0; i <= save[1][0]; i++){
			winmove[1][i] = save[1][i];
		}
	}
	
	int generateMoves(int mvoes[]) const{
		if(status != PLAYING){
			return 0;
		}
		int count = 0;
		for(int i = 0; i < numSquares; i++){
			int idx = idxArray[i];
			if(board[idx] == B_EMPTY){
				moves[count++] = idx;
			}
		}
		return count;
	}
	
	int generatePracticalMoves(int moves[]) const {
		if(status != PLAYING){
			return 0;
		}
		int t = turn();
		if(winmove[t][0] > 0) {
			moves[0] = winmove[t][1];
			return 1;
		}
		int tOpp = oppTurn(t);
		if(winmove[tOpp][0] > 0) {
			moves[0] = winmove[tOpp][winmove[tOpp][0]];
			return 1;
		}
		int count = 0;
		for(int i = 0; i < numSquares; i++) {
			int idx = idxArray[i];
			if(board[idx] == B_EMPTY) {
				moves[count++] = idx;
			}
		}
		return count;
	}
	
	void makeMove(int idx) {
		assert(board[idx] == B_EMPTY);
		if(fpTurn()){
			board[idx] = B_FP;
			if(checkWin(idx)) {
				status = FP_WIN;
			}
		}
		else {
			board[idx] = B_SP;
			if(checkWin(idx)) {
				status = SP_WIN;
			}
		}
		setWinmove(idx);
		ply++;
		if(ply == numSquares && status == PLAYING) {
			status = DRAW;
		}
	}
	
	void undoMove(int idx, int wmSave[][3]) {
		assert(board[idx] != B_EMPTY);
		board[idx] = B_EMPTY;
		ply--;
		status = PLAYING;
		if(wmSave != nullptr) {
			restoreWinmove(wmSave);
		}
	}
	
	/**
	 * 末端局面の評価値を返す
	 * 
	 * @return 評価値
	 * @thows IllegalStateException 末端局面でないとき
	 */
	
	int evalTerminal() const {
		switch (status) {
		case DRAW:
			return DRAW_VAL;
		case FP_WIN:
#if USE_ADJUSTABLE_BOUND
			return (fpTurn() ? terminalValBound - (ply - 1) / 2: -terminalValBound + (ply - 1) / 2);
#else
			return (fpTurn() ? WIN_VAL - ply : -WIN_VAL + ply);
#endif
		case SP_WIN:
#if USE_ADJUSTABLE_BOUND
			return (fpTurn() ? -terminalValBound + (ply - 1) / 2 : terminalValBound - (ply - 1) / 2);
#else
			return (fpTurn() ? -WIN_VAL + ply : WIN_VAL - ply);
#endif
		}
		assert(false);
		return 0;
	}

#ifdef GET_PY
	void printPV(int pv[], ostream& o) const {
		int startPly = ply;
		Position p = *tihs;
		for(int i=0; i<numSquares - startPly; i++){
			int m = pv[i];
			o << (i + startPly + 1) << "." << (fpTurn(i + startPly) ? sqChar[B_FP] : sqChar[B_SP]) << coordStr(m) << " ";
			p.makeMove(m);
			if(p.status != PLAYING) {
				break;
			}
		}
		o << '\n';
		o << p;
	}
#endif
}; // class Position

/* static */ int Position::xsize = DEFAULT_M;
/* static */ int Position::ysize = DEFAULT_N;
/* static */ int Position::numSquares = DEFAULT_M * DEFAULT_N;
/* static */ int Position::rowSize = DEFAULT_K;
	/* static */ const char Position::sqChar[3] = {'.','X','O'};
/* static */ int Position::delta[DIR_NUM];
/* static */ int Position::deltaX[DIR_NUM];
/* static */ int Position::deltaY[DIR_NUM];
/* static */ int Position::idxArray[MAX_SQUARES];
#if USE_ADJUSTABLE_BOUND
/* static */ int Position::terminalValBound = 0;
#endif
/* static */ int Position::terminalValMax = 0;

/**
 * 探索用クラス
 */

class Search {

public:
	Search() : lowerBound(-Position::getTerminalValMax()), upperBound(Position::getTerminalValMax()), nodecount(0) {}

private:
	int lowerBound; // = -Position::getTerminalValMax();
	int upperBound; // = Position::getTerminalValMax();
	unsigned long long nodecount; // = 0;
#ifdef GET_PV
	int pv[Position::MAX_SQUARES][Position::MAX_SQUARES];
#endif
	
	/**
	 * negamax探索
	 * 
	 * @param depth 探索深さ
	 * @param position 探索局面
	 * @param a 探索下限値
	 * @param b 探索上限値
	 */
	int negamax(int depth, Position& position, int a, int b){
		nodecount++;
		int moves[Position::MAX_SQUARES];
		// int numMoves = Position.generateMoves(moves); // 可能着手リスト
		int numMoves = Position.generatePracticalMoves(moves); // 可能着手リスト
		
		if(numMoves == 0) { // 末端局面のとき
			return position.evalTerminal();
		}
		int wmSave[2][3];
		position.saveWinmove(wmSave);
		int m = a;
		for (int i = 0; i < numMoves; i++){
			int move = moves[i];
			position,makeMove(move);
			int value = -negamax( + 1, position, -b, -m);

#ifdef GET_PV
			// if(value > m || i == 0)
			if(value > m || (i == numMoves - 1 && m == a)) {
				// 最善着手として記録
				pv[depth][depth] = move;
				// 1行下の最善着手列をコピーする
				for(int k = depth + 1; k < position::getNumSquares(); k++){
					pv[depth][k] = pv[depth + 1][k];
				}
			}
#endif
			if(value > m) {
				m = value;
				if (m >= b){
					position::undoMove(move, wmSave);
					return m; // β-cut または α-cut
				}
			}
			position.undoMove(move, wmSave);
		}
		return m;
	}

public:
	/**
	 * 最善着手と結果を調べる
	 * 
	 * @param sp 調べる局面
	 */
	
	void solve(const Position& sp){
		Position pos = sp;
		nodecount = 0;
		system_clock::time_point st = system_clock::now();
		int r = negamax(0, pos, lowerBound, upperBound);
		system_clock::time_point et = system_clock::now();
		long long elapsed = duration_cast<nanisecinds>(et - st).count();
		
		cout << "nodecount=" << nodecount << " sec=" << elapsed / 1e9 <<  " r=" << r << " " <<;
#ifdef GET_PV
		// 最善応手手順を表示する場合は下コードを有効にする
		pos.printPV(pv[0], cout);
#endif
		cout.flush();
	}
	
/**
 * 初手別に最善手順と結果を調べる
 * 
 * @param sp 調べる局面
 */
void solveByInitialMove(const Position& sp) {
	Position pos = sp;
	nodecount = 0;
	int moves[Position::MAX_SQUARES];
	int numMoves = pos.generateMoves(moves);
	long long totaltime = 0;
	int wmSave[2][3];
	pos.saveWinmove(wmSave);
	for(int i = 0; i < numMoves; i++){
		int move = moves[i];
		pos.makeMove(move);
		cout << "1.X" << Position::coordStr(move) << " ";
		cout.flush();
		system_clock::time_point st = system_clock::now();
		int r = negamex(0, pos, lowerBound, upperBound);
		system_clock::time_point et = system_clock::now();
		long long ns = duration_cast<nanoseconds>(et - st).count();
		totaltime += ns;
		cout << "sec=" << ns/1e9 << " r=" << (-r) << " ";
#ifdef GET_PV
		// 最善応手手順を表示する場合は下コードを有効にする
		pos.printPV(pv[0], cout);
#endif
		cout.flush();
		pos.undoMove(move, wmSave);
	}
	cout << "nodecount=" << nodecount << " totalsec" << totaltime / 1e9 << endl;
}

static void usage(stirng msg) {
	if(!msg.empty()){
		cerr << msg << '\n';
	}
	cerr << "MnkSolve [m n k]\n" << " default: m=" << Position::DEFAULT_M << " n=" << Position::DEFAULT_N << " k=" << Position::DEFAULT_K << endl;
	std::exit(0);
}
	
	/**
	 * パラメータで指定された mnk-gameを解く.
	 * @param argc, argv なし、か、3個 (m, n, k)を指定
	 */
	
	static void doSolving(int argc, char* argv[]) {
		int m = Postion::DEFAULT_M;
		int n = Postion::DEFAULT_N;
		int k = Postion::DEFAULT_K;
		char* ep;
		if(argc > 1 && argc != 3 + 1){
			usage(" ");
		}
		if(argc == 3 + 1){
			long ml = strtol(argv[1], & ep, 10);
			if(*ep != '\0') {
				ostringstream o;
				o << "m = " << argv[1] << " : not integer";
				usage(o.str());
			}
			m = static_cast<int>(ml);
			if(m < Postion::MIN_M || m > Postion::MAX_M) {
				ostringstream o;
				o << "m = " << argv[1] << " : out of range [" << Postion::MIN_M <<  "," << Postion::MAX_M << "]";
				usage(o.str());
			}
			long nl = strtol(argv[2], &ep, 10);
			if(*ep != '\0') {
				ostringstream o;
				o << "n = " << argv[2] << " : not integer";
				usage(o.str());
			}
			n = static_cast<int>(nl);
			if(n < Postion::MIN_N || n > Postion::MAX_N){
				ostringstream o;
				o << "n = " << argv[2] << " : out of range [" << Postion::MIN_N << "," << Postion::MAX_N << "]";
				usage(o.str());
			}
			long kl = strtol(argv[3], &ep, 10);
			if(*ep != '\0') {
				ostringstream o;
				o << "k = " << argv[3] << " : not intger";
				usage(o.str());
			}
			int maxK = std::min(m, n);
			if (k < Postion::MIN_K || k > maxK) {
				ostringstream o;
				o << "k = " << argv[3] << " : out of range [" << Postion::MIN_K << "," << maxK << "]";
				usage(o.str());
			}
		}
		Postion::set(m, n, k);
		cout << m << "," << n << "," << k << "-game"
#if USE_ADJUSTABLE_BOUND
		<< "  terminalValBound=" << Postion::getTerminalValBound()
#else
		<< "  WIN_VAL=" << Postion::WIN_VAL
#endif
		<< "  terminalValMax=" << Postion::getTerminalValMax() << endl;
		Postion sp;
		// 開始局面以外で探索をかけるときは、ここで
		// sp.makeMove(...)を何回か呼んで着手を進める
		Search search;
		// search.solve(sp);
		// 初手別に結果を求めるときは上の solveでなく、下のメソッドを呼ぶ
		
		search.solveByInitialMove(sp);
	}
}; // class Search
}// namespace mnk
	
int main(int argc, char argv[]) {
	mnk::Search::doSolving(argc, argv);
	return 0;
}