#include <iostream>
#include <vector>
#include <cassert>
using namespace std;
int dx[9][10] = {
{-1,-1,-1,0,1,1,1,0},
{},
{-1,-1,0,0,1,1,0},
{-1,-1,0,0,1,1,0},
{-1,1,0,1,-1},
{-1,-1,0,1,1},
{-1,0,1,-1,1},
{0},
{-1,1}
};
int dy[9][10] = {
{1,0,-1,-1,-1,0,1,1},
{},
{1,0,-1,1,1,0},
{1,0,-1,1,1,0},
{-1,1,1,-1,1},
{-1,0,1,-1,0},
{-1,-1,-1,1,1},
{1},
{1,1}
};
string KOMA[9] = {"王", "飛", "金", "金", "銀", "特", "銅", "歩", "平"};
struct Move{
int type;
int px,py,fx,fy;
int get; // -1
};
enum{OU,HI,KI,KI2,GI,TO,DO,HU,HR};
struct Board {
bool turn[9];
int x[9],y[9]; // x[i] = -1 then 持駒
int get_pos(int x,int y){
for(int i = 0; i<9;i++){
if(this->x[i]==x&&this->y[i] == y){
return i;
}
}
return -1;
}
vector<Move> generate_moves(int cur_turn){
vector<Move> result;
for(int j = 0; j < 2; j++){
int kk=j == 0 ? HI : HR;
if(turn[kk] == cur_turn && x[kk] != -1) {
// 飛
int ddx[4]={1,-1,0,0},ddy[4]={0,0,1,-1};
int max = kk==HI?4:2;
for(int k = 0; k < max; k++) {
int xx = x[kk],yy = y[kk];
while(true) {
xx += ddx[k];
yy += ddy[k];
if(0 <= xx && xx < 6 && 0 <= yy && yy < 6) {
if(get_pos(xx,yy) == -1) {
result.push_back((Move){kk, x[kk], y[kk], xx, yy, -1});
}else if(turn[get_pos(xx,yy)] != cur_turn){
result.push_back((Move){kk, x[kk], y[kk], xx, yy, get_pos(xx,yy)});
break;
}else{
break;
}
}else break;
}
}
}
}
for(int K = 0; K < 9; K++) {
if(turn[K] == cur_turn) {
int rev = cur_turn ? -1 : 1;
if(x[K] != -1) {
for(int t = 0; dx[K][t] || dy[K][t]; t++ ){
int ddx = -dx[K][t];
int ddy = -dy[K][t];
int nx = x[K]+rev*ddx,ny=y[K]+rev*ddy;
if(nx >= 0 && nx < 6 && ny >= 0 && ny < 6){
if(get_pos(nx,ny) == -1){
result.push_back((Move){K, x[K], y[K], nx, ny, -1});
}else if (turn[get_pos(nx,ny)] != cur_turn){
result.push_back((Move){K, x[K], y[K], nx, ny, get_pos(nx,ny)});
}
}
}
}else{
for(int nx = 0; nx < 6; nx++) {
for(int ny = 0; ny < 6; ny++) {
if(get_pos(nx,ny) == -1) {
result.push_back((Move){K, x[K], y[K], nx, ny, -1});
}
}
}
}
}
}
return result;
}
void show() {
string s[6][6];
string moti[2];
for(int i = 0; i < 9; i++) {
string type = "▽";
if(turn[i] == 0) {
type="△";
}
if(x[i] != -1) {
s[x[i]][y[i]] = type + KOMA[i];
}else{
moti[turn[i]] += type + KOMA[i];
}
}
cout << "持駒:" << moti[1] << endl;
cout << "+";
for(int t = 0; t < 6; t++ ) {
cout <<"----+";
}
cout<<endl;
for(int y = 0; y < 6; y++) {
cout << "|";
for(int x = 0; x < 6; x++) {
if(s[x][y] == "")cout<<" ";
else cout <<s[x][y];
cout << "|";
}
cout<<endl;
cout << "+";
for(int t = 0; t < 6; t++ ) {
cout <<"----+";
}
cout<<endl;
}
cout << "持駒:" << moti[0] << endl;
}
};
void move(Board &board, Move move, int turn) {
assert(board.turn[move.type] == turn);
assert(board.x[move.type] == move.px);
assert(board.y[move.type] == move.py);
board.x[move.type] = move.fx;
board.y[move.type] = move.fy;
if(move.get >= 0) {
assert(board.turn[move.get] == !turn);
assert(board.x[move.get] == move.fx);
assert(board.y[move.get] == move.fy);
board.turn[move.get] = turn;
board.x[move.get] = -1;
board.y[move.get] = -1;
}
}
void unmove(Board &board, Move move, int turn) {
assert(board.turn[move.type] == turn);
assert(board.x[move.type] == move.fx);
assert(board.y[move.type] == move.fy);
board.x[move.type] = move.px;
board.y[move.type] = move.py;
if(move.get >= 0) {
assert(board.turn[move.get] == turn);
assert(board.x[move.get] == -1);
assert(board.y[move.get] == -1);
board.turn[move.get] = !turn;
board.x[move.get] = move.fx;
board.y[move.get] = move.fy;
}
}
vector<Move> check_move(Board &board, const vector<Move> &moves, int turn) {
vector<Move> result;
for(Move mv: moves) {
bool ok = false;
if(turn == 0) {
// 王手であるかどうかの判定
move(board, mv, turn);
vector<Move> mvs = board.generate_moves(turn);
for(int i = 0; i < mvs.size(); i++) {
if(mvs[i].get == OU) {
ok =true;
break;
}
}
unmove(board, mv, turn);
}else {
// 王を取れないかの判定
ok = true;
move(board, mv, turn);
vector<Move> mvs = board.generate_moves(!turn);
for(int i = 0; i < mvs.size(); i++) {
if(mvs[i].get == OU) {
ok =false; // 王が取られる
break;
}
}
unmove(board, mv, turn);
}
if(ok)result.push_back(mv);
}
return result;
}
#define AND (1)
#define OR (0)
const int INF = 9999999;
struct SNode {
int pf,dp;
int terminateNode;
int turn;
int nodeType;
Move lastMove;
SNode* children;
int childrenSize = 0;
SNode(){}
SNode(Board board, int turn, int nodeType){
pf=dp=1;
terminateNode = true;
this->turn = turn;
this->nodeType = nodeType;
vector<Move> moves = check_move(board, board.generate_moves(turn), turn);
if(moves.size() == 0) {
if(nodeType == OR) {
dp = 0;
pf = INF;
}else{
dp = INF;
pf = 0;
}
}
}
void update() {
if(nodeType == OR) {
pf = INF;
dp = 0;
for(int i = 0; i < childrenSize;i++){
pf = min(pf, children[i].pf);
dp = min(dp + children[i].dp , INF);
}
}else{
dp = INF;
pf = 0;
for(int i = 0; i < childrenSize;i++){
dp = min(dp, children[i].dp);
pf = min(pf + children[i].pf , INF);
}
}
}
void expand(Board &board) {
terminateNode = false;
vector<Move> moves = check_move(board, board.generate_moves(turn), turn);
children = new SNode[moves.size()]();
childrenSize = moves.size();
for(int i = 0; i < moves.size();i++){
move(board, moves[i], turn);
children[i] = SNode(board, 1 - turn, 1 - nodeType);
children[i].lastMove = moves[i];
unmove(board, moves[i], turn);
}
update();
}
SNode *getMinProofChild() {
int proof = INF;
for(int i = 0; i < childrenSize;i++){
proof = min(proof, children[i].pf);
}
for(int i = 0; i < childrenSize;i++){
if(children[i].pf == proof)
return children + i;
}
}
SNode *getMinDisProofChild() {
int proof = INF;
for(int i = 0; i < childrenSize;i++){
proof = min(proof, children[i].dp);
}
for(int i = 0; i < childrenSize;i++){
if(children[i].dp == proof)
return children + i;
}
}
static void bestFirstSearch(SNode *node, Board &board) {
if(node->terminateNode) {
node->expand(board);
}else{
if(node->nodeType == OR) {
SNode *best = node->getMinProofChild();
move(board, best->lastMove, node->turn);
bestFirstSearch(best, board);
unmove(board, best->lastMove, node->turn);
}else{
SNode *best = node->getMinDisProofChild();
move(board, best->lastMove, node->turn);
bestFirstSearch(best, board);
unmove(board, best->lastMove, node->turn);
}
node->update();
}
}
static void dfs(Board &board, SNode &n, int turn, int depth) {
cout << depth << endl;
board.show();
if(turn == 0) {
for(int i = 0; i < n.childrenSize; i++) {
if(n.children[i].pf == 0){
SNode &child = n.children[i];
move(board, child.lastMove, turn);
dfs(board, child, !turn, 1 + depth);
unmove(board, child.lastMove, turn);
}
}
}else{
for(int i = 0; i < n.childrenSize; i++) {
if(n.children[i].pf == 0){
SNode &child = n.children[i];
move(board, child.lastMove, turn);
dfs(board, child, !turn, 1 + depth);
unmove(board, child.lastMove, turn);
}
}
}
}
static void chessProblemSearch(Board &board, int turn) {
SNode root = SNode(board, OR, turn);
while(root.dp > 0 && root.pf > 0) {
bestFirstSearch(&root, board);
}
cout << root.dp <<"," << root.pf << endl;
dfs(board, root, 0, 0);
}
};
int search(int turn, int depth, Board &board) {
vector<Move> moves = check_move(board, board.generate_moves(turn), turn);
if(moves.size() == 0) {
if(depth == 13)
board.show();
return -1;
}
if(depth == 13)return 1;
cout << depth << "," << moves.size() << endl;
board.show();
int result = -1;
for(Move mv: moves) {
move(board, mv,turn);
result = max(result, -search(!turn, depth + 1, board));
unmove(board, mv, turn);
if(result > 0)break;
}
cout << result << endl;
return result;
}
int main() {
Board board;
board.x[0] = 4;
board.y[0] = 2;
board.turn[0] = 1;
board.x[1] = 5;
board.y[1] = 2;
board.turn[1] = 1;
board.x[2] = 2;
board.y[2] = 1;
board.turn[2] = 0;
board.x[3] = -1;
board.y[3] = -1;
board.turn[3] = 0;
board.x[4] = 4;
board.y[4] = 1;
board.turn[4] = 1;
board.x[5] = -1;
board.y[5] = -1;
board.turn[5] = 0;
board.x[6] = -1;
board.y[6] = -1;
board.turn[6] = 0;
board.x[7] = 3;
board.y[7] = 4;
board.turn[7] = 0;
board.x[8] = -1;
board.y[8] = -1;
board.turn[8] = 0;
board.show();
SNode::chessProblemSearch(board, 0);
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8Y2Fzc2VydD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmludCBkeFs5XVsxMF0gPSB7CiAgey0xLC0xLC0xLDAsMSwxLDEsMH0sCiAge30sCiAgey0xLC0xLDAsMCwxLDEsMH0sCiAgey0xLC0xLDAsMCwxLDEsMH0sCiAgey0xLDEsMCwxLC0xfSwKICB7LTEsLTEsMCwxLDF9LAogIHstMSwwLDEsLTEsMX0sCiAgezB9LAogIHstMSwxfQp9OwppbnQgZHlbOV1bMTBdID0gewogIHsxLDAsLTEsLTEsLTEsMCwxLDF9LAogIHt9LAogIHsxLDAsLTEsMSwxLDB9LAogIHsxLDAsLTEsMSwxLDB9LAogIHstMSwxLDEsLTEsMX0sCiAgey0xLDAsMSwtMSwwfSwKICB7LTEsLTEsLTEsMSwxfSwKICB7MX0sCiAgezEsMX0KfTsKc3RyaW5nIEtPTUFbOV0gPSB7IueOiyIsICLpo5siLCAi6YeRIiwgIumHkSIsICLpioAiLCAi54m5IiwgIumKhSIsICLmrakiLCAi5bmzIn07CnN0cnVjdCBNb3ZlewogIGludCB0eXBlOwogIGludCBweCxweSxmeCxmeTsKICBpbnQgZ2V0OyAvLyAtMQp9OwplbnVte09VLEhJLEtJLEtJMixHSSxUTyxETyxIVSxIUn07CnN0cnVjdCBCb2FyZCB7CiAgYm9vbCB0dXJuWzldOwogIGludCB4WzldLHlbOV07IC8vIHhbaV0gPSAtMSB0aGVuIOaMgemnkgogIGludCBnZXRfcG9zKGludCB4LGludCB5KXsKICAgIGZvcihpbnQgaSA9IDA7IGk8OTtpKyspewogICAgICBpZih0aGlzLT54W2ldPT14JiZ0aGlzLT55W2ldID09IHkpewogICAgICAgIHJldHVybiBpOwogICAgICB9CiAgICB9CiAgICByZXR1cm4gLTE7CiAgfQogIHZlY3RvcjxNb3ZlPiBnZW5lcmF0ZV9tb3ZlcyhpbnQgY3VyX3R1cm4peyAKICAgIHZlY3RvcjxNb3ZlPiByZXN1bHQ7CiAgICBmb3IoaW50IGogPSAwOyBqIDwgMjsgaisrKXsKICAgICAgaW50IGtrPWogPT0gMCA/IEhJIDogSFI7CiAgICAgIGlmKHR1cm5ba2tdID09IGN1cl90dXJuICYmIHhba2tdICE9IC0xKSB7CiAgICAgICAgLy8g6aObCiAgICAgICAgaW50IGRkeFs0XT17MSwtMSwwLDB9LGRkeVs0XT17MCwwLDEsLTF9OwogICAgICAgIGludCBtYXggPSBraz09SEk/NDoyOwogICAgICAgIGZvcihpbnQgayA9IDA7IGsgPCBtYXg7IGsrKykgewogICAgICAgICAgaW50IHh4ID0geFtra10seXkgPSB5W2trXTsKICAgICAgICAgIHdoaWxlKHRydWUpIHsKICAgICAgICAgICAgeHggKz0gZGR4W2tdOwogICAgICAgICAgICB5eSArPSBkZHlba107CiAgICAgICAgICAgIGlmKDAgPD0geHggJiYgeHggPCA2ICYmIDAgPD0geXkgJiYgeXkgPCA2KSB7CiAgICAgICAgICAgICAgaWYoZ2V0X3Bvcyh4eCx5eSkgPT0gLTEpIHsKICAgICAgICAgICAgICAgIHJlc3VsdC5wdXNoX2JhY2soKE1vdmUpe2trLCB4W2trXSwgeVtra10sIHh4LCB5eSwgLTF9KTsKICAgICAgICAgICAgICB9ZWxzZSBpZih0dXJuW2dldF9wb3MoeHgseXkpXSAhPSBjdXJfdHVybil7CiAgICAgICAgICAgICAgICByZXN1bHQucHVzaF9iYWNrKChNb3ZlKXtraywgeFtra10sIHlba2tdLCB4eCwgeXksIGdldF9wb3MoeHgseXkpfSk7CiAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgICB9ZWxzZXsKICAgICAgICAgICAgICAgIGJyZWFrOwogICAgICAgICAgICAgIH0KICAgICAgICAgICAgfWVsc2UgYnJlYWs7CiAgICAgICAgICB9CiAgICAgICAgICAKICAgICAgICB9CiAgICAgIH0KICAgIH0KICAgIGZvcihpbnQgSyA9IDA7IEsgPCA5OyBLKyspIHsKICAgICAgaWYodHVybltLXSA9PSBjdXJfdHVybikgewogICAgICAgIGludCByZXYgPSBjdXJfdHVybiA/IC0xIDogMTsKICAgICAgICBpZih4W0tdICE9IC0xKSB7CiAgICAgICAgICBmb3IoaW50IHQgPSAwOyBkeFtLXVt0XSB8fCBkeVtLXVt0XTsgdCsrICl7CiAgICAgICAgICAgIGludCBkZHggPSAtZHhbS11bdF07CiAgICAgICAgICAgIGludCBkZHkgPSAtZHlbS11bdF07CiAgICAgICAgICAgIGludCBueCA9IHhbS10rcmV2KmRkeCxueT15W0tdK3JldipkZHk7CiAgICAgICAgICAgIGlmKG54ID49IDAgJiYgbnggPCA2ICYmIG55ID49IDAgJiYgbnkgPCA2KXsgCiAgICAgICAgICAgICAgaWYoZ2V0X3BvcyhueCxueSkgPT0gLTEpewogICAgICAgICAgICAgICAgcmVzdWx0LnB1c2hfYmFjaygoTW92ZSl7SywgeFtLXSwgeVtLXSwgbngsIG55LCAtMX0pOwogICAgICAgICAgICAgIH1lbHNlIGlmICh0dXJuW2dldF9wb3MobngsbnkpXSAhPSBjdXJfdHVybil7CiAgICAgICAgICAgICAgICByZXN1bHQucHVzaF9iYWNrKChNb3ZlKXtLLCB4W0tdLCB5W0tdLCBueCwgbnksIGdldF9wb3MobngsbnkpfSk7CiAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgICB9CiAgICAgICAgfWVsc2V7CgogICAgICAgICAgZm9yKGludCBueCA9IDA7IG54IDwgNjsgbngrKykgewogICAgICAgICAgICBmb3IoaW50IG55ID0gMDsgbnkgPCA2OyBueSsrKSB7CiAgICAgICAgICAgICAgaWYoZ2V0X3BvcyhueCxueSkgPT0gLTEpIHsKICAgICAgICAgICAgICAgIHJlc3VsdC5wdXNoX2JhY2soKE1vdmUpe0ssIHhbS10sIHlbS10sIG54LCBueSwgLTF9KTsKICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICAgIH0KICAgICAgICB9CiAgICAgIH0KICAgIH0KICAgIHJldHVybiByZXN1bHQ7CiAgfQogIHZvaWQgc2hvdygpIHsKICAgIHN0cmluZyBzWzZdWzZdOwogICAgc3RyaW5nIG1vdGlbMl07CiAgICBmb3IoaW50IGkgPSAwOyBpIDwgOTsgaSsrKSB7CiAgICAgIHN0cmluZyB0eXBlID0gIuKWvSI7CiAgICAgIGlmKHR1cm5baV0gPT0gMCkgewogICAgICAgIHR5cGU9IuKWsyI7IAogICAgICB9CiAgICAgIGlmKHhbaV0gIT0gLTEpIHsKICAgICAgICBzW3hbaV1dW3lbaV1dID0gdHlwZSArIEtPTUFbaV07CiAgICAgIH1lbHNlewogICAgICAgIG1vdGlbdHVybltpXV0gKz0gdHlwZSArIEtPTUFbaV07CiAgICAgIH0KICAgIH0KICAgIGNvdXQgPDwgIuaMgemnkjoiIDw8IG1vdGlbMV0gPDwgZW5kbDsKICAgIGNvdXQgPDwgIisiOwogICAgZm9yKGludCB0ID0gMDsgdCA8IDY7IHQrKyApIHsKICAgICAgY291dCA8PCItLS0tKyI7CiAgICB9CiAgICBjb3V0PDxlbmRsOwogICAgZm9yKGludCB5ID0gMDsgeSA8IDY7IHkrKykgewogICAgICBjb3V0IDw8ICJ8IjsKICAgICAgZm9yKGludCB4ID0gMDsgeCA8IDY7IHgrKykgewogICAgICAgIGlmKHNbeF1beV0gPT0gIiIpY291dDw8IiAgICAiOwogICAgICAgIGVsc2UgY291dCA8PHNbeF1beV07CiAgICAgICAgY291dCA8PCAifCI7CiAgICAgIH0KICAgICAgY291dDw8ZW5kbDsKICAgICAgY291dCA8PCAiKyI7CiAgICAgIGZvcihpbnQgdCA9IDA7IHQgPCA2OyB0KysgKSB7CiAgICAgICAgY291dCA8PCItLS0tKyI7CiAgICAgIH0KICAgICAgY291dDw8ZW5kbDsKICAgIH0KICAgIGNvdXQgPDwgIuaMgemnkjoiIDw8IG1vdGlbMF0gPDwgZW5kbDsKICB9Cn07CgoKCnZvaWQgbW92ZShCb2FyZCAmYm9hcmQsIE1vdmUgbW92ZSwgaW50IHR1cm4pIHsKICBhc3NlcnQoYm9hcmQudHVyblttb3ZlLnR5cGVdID09IHR1cm4pOwogIGFzc2VydChib2FyZC54W21vdmUudHlwZV0gPT0gbW92ZS5weCk7CiAgYXNzZXJ0KGJvYXJkLnlbbW92ZS50eXBlXSA9PSBtb3ZlLnB5KTsKICBib2FyZC54W21vdmUudHlwZV0gPSBtb3ZlLmZ4OwogIGJvYXJkLnlbbW92ZS50eXBlXSA9IG1vdmUuZnk7CiAgaWYobW92ZS5nZXQgPj0gMCkgewogICAgYXNzZXJ0KGJvYXJkLnR1cm5bbW92ZS5nZXRdID09ICF0dXJuKTsKICAgIGFzc2VydChib2FyZC54W21vdmUuZ2V0XSA9PSBtb3ZlLmZ4KTsKICAgIGFzc2VydChib2FyZC55W21vdmUuZ2V0XSA9PSBtb3ZlLmZ5KTsKICAgIGJvYXJkLnR1cm5bbW92ZS5nZXRdID0gdHVybjsKICAgIGJvYXJkLnhbbW92ZS5nZXRdID0gLTE7CiAgICBib2FyZC55W21vdmUuZ2V0XSA9IC0xOwogIH0KfQoKdm9pZCB1bm1vdmUoQm9hcmQgJmJvYXJkLCBNb3ZlIG1vdmUsIGludCB0dXJuKSB7CiAgYXNzZXJ0KGJvYXJkLnR1cm5bbW92ZS50eXBlXSA9PSB0dXJuKTsKICBhc3NlcnQoYm9hcmQueFttb3ZlLnR5cGVdID09IG1vdmUuZngpOwogIGFzc2VydChib2FyZC55W21vdmUudHlwZV0gPT0gbW92ZS5meSk7CiAgYm9hcmQueFttb3ZlLnR5cGVdID0gbW92ZS5weDsKICBib2FyZC55W21vdmUudHlwZV0gPSBtb3ZlLnB5OwogIGlmKG1vdmUuZ2V0ID49IDApIHsKICAgIGFzc2VydChib2FyZC50dXJuW21vdmUuZ2V0XSA9PSB0dXJuKTsKICAgIGFzc2VydChib2FyZC54W21vdmUuZ2V0XSA9PSAtMSk7CiAgICBhc3NlcnQoYm9hcmQueVttb3ZlLmdldF0gPT0gLTEpOwogICAgYm9hcmQudHVyblttb3ZlLmdldF0gPSAhdHVybjsKICAgIGJvYXJkLnhbbW92ZS5nZXRdID0gbW92ZS5meDsKICAgIGJvYXJkLnlbbW92ZS5nZXRdID0gbW92ZS5meTsKICB9Cn0KCnZlY3RvcjxNb3ZlPiBjaGVja19tb3ZlKEJvYXJkICZib2FyZCwgY29uc3QgdmVjdG9yPE1vdmU+ICZtb3ZlcywgaW50IHR1cm4pIHsKICB2ZWN0b3I8TW92ZT4gcmVzdWx0OwogIGZvcihNb3ZlIG12OiBtb3ZlcykgewogICAgYm9vbCBvayA9IGZhbHNlOwogICAgaWYodHVybiA9PSAwKSB7CiAgICAgIC8vIOeOi+aJi+OBp+OBguOCi+OBi+OBqeOBhuOBi+OBruWIpOWumgogICAgICAKICAgICAgbW92ZShib2FyZCwgbXYsIHR1cm4pOwogICAgICB2ZWN0b3I8TW92ZT4gbXZzID0gYm9hcmQuZ2VuZXJhdGVfbW92ZXModHVybik7CiAgICAgIGZvcihpbnQgaSA9IDA7IGkgPCBtdnMuc2l6ZSgpOyBpKyspIHsKICAgICAgICBpZihtdnNbaV0uZ2V0ID09IE9VKSB7CiAgICAgICAgICBvayAgPXRydWU7CiAgICAgICAgICBicmVhazsKICAgICAgICB9CiAgICAgIH0KICAgICAgdW5tb3ZlKGJvYXJkLCBtdiwgdHVybik7CiAgICB9ZWxzZSB7CiAgICAgIC8vIOeOi+OCkuWPluOCjOOBquOBhOOBi+OBruWIpOWumgogICAgICBvayA9IHRydWU7CiAgICAgIG1vdmUoYm9hcmQsIG12LCB0dXJuKTsKICAgICAgdmVjdG9yPE1vdmU+IG12cyA9IGJvYXJkLmdlbmVyYXRlX21vdmVzKCF0dXJuKTsKICAgICAgZm9yKGludCBpID0gMDsgaSA8IG12cy5zaXplKCk7IGkrKykgewogICAgICAgIGlmKG12c1tpXS5nZXQgPT0gT1UpIHsKICAgICAgICAgIG9rICA9ZmFsc2U7IC8vIOeOi+OBjOWPluOCieOCjOOCiwogICAgICAgICAgYnJlYWs7CiAgICAgICAgfQogICAgICB9CiAgICAgIHVubW92ZShib2FyZCwgbXYsIHR1cm4pOwogICAgfQogICAgaWYob2spcmVzdWx0LnB1c2hfYmFjayhtdik7CiAgfQogIHJldHVybiByZXN1bHQ7Cn0KI2RlZmluZSBBTkQgKDEpCiNkZWZpbmUgT1IgKDApCmNvbnN0IGludCBJTkYgPSA5OTk5OTk5OwpzdHJ1Y3QgU05vZGUgewogIGludCBwZixkcDsKICBpbnQgdGVybWluYXRlTm9kZTsKICBpbnQgdHVybjsKICBpbnQgbm9kZVR5cGU7CiAgTW92ZSBsYXN0TW92ZTsKICBTTm9kZSogY2hpbGRyZW47CiAgaW50IGNoaWxkcmVuU2l6ZSA9IDA7CiAgU05vZGUoKXt9CiAgU05vZGUoQm9hcmQgYm9hcmQsIGludCB0dXJuLCBpbnQgbm9kZVR5cGUpewogICAgcGY9ZHA9MTsKICAgIHRlcm1pbmF0ZU5vZGUgPSB0cnVlOwogICAgdGhpcy0+dHVybiA9IHR1cm47CiAgICB0aGlzLT5ub2RlVHlwZSA9IG5vZGVUeXBlOwogICAgdmVjdG9yPE1vdmU+IG1vdmVzID0gY2hlY2tfbW92ZShib2FyZCwgYm9hcmQuZ2VuZXJhdGVfbW92ZXModHVybiksIHR1cm4pOwogICAgaWYobW92ZXMuc2l6ZSgpID09IDApIHsKICAgICAgaWYobm9kZVR5cGUgPT0gT1IpIHsKICAgICAgICBkcCA9IDA7CiAgICAgICAgcGYgPSBJTkY7CiAgICAgIH1lbHNlewogICAgICAgIGRwID0gSU5GOwogICAgICAgIHBmID0gMDsKICAgICAgfQogICAgfQogIH0KICB2b2lkIHVwZGF0ZSgpIHsKICAgIGlmKG5vZGVUeXBlID09IE9SKSB7CiAgICAgIHBmID0gSU5GOwogICAgICBkcCA9IDA7CiAgICAgIGZvcihpbnQgaSA9IDA7IGkgPCBjaGlsZHJlblNpemU7aSsrKXsKICAgICAgICBwZiA9IG1pbihwZiwgY2hpbGRyZW5baV0ucGYpOwogICAgICAgIGRwID0gbWluKGRwICsgY2hpbGRyZW5baV0uZHAgLCBJTkYpOwogICAgICB9CiAgICB9ZWxzZXsKICAgICAgZHAgPSBJTkY7CiAgICAgIHBmID0gMDsKICAgICAgZm9yKGludCBpID0gMDsgaSA8IGNoaWxkcmVuU2l6ZTtpKyspewogICAgICAgIGRwID0gbWluKGRwLCBjaGlsZHJlbltpXS5kcCk7CiAgICAgICAgcGYgPSBtaW4ocGYgKyBjaGlsZHJlbltpXS5wZiAsIElORik7CiAgICAgIH0KICAgIH0KICB9CiAgdm9pZCBleHBhbmQoQm9hcmQgJmJvYXJkKSB7CiAgICB0ZXJtaW5hdGVOb2RlID0gZmFsc2U7CiAgICB2ZWN0b3I8TW92ZT4gbW92ZXMgPSBjaGVja19tb3ZlKGJvYXJkLCBib2FyZC5nZW5lcmF0ZV9tb3Zlcyh0dXJuKSwgdHVybik7CiAgICBjaGlsZHJlbiA9IG5ldyBTTm9kZVttb3Zlcy5zaXplKCldKCk7CiAgICBjaGlsZHJlblNpemUgPSBtb3Zlcy5zaXplKCk7CiAgICBmb3IoaW50IGkgPSAwOyBpIDwgbW92ZXMuc2l6ZSgpO2krKyl7CiAgICAgIG1vdmUoYm9hcmQsIG1vdmVzW2ldLCB0dXJuKTsKICAgICAgY2hpbGRyZW5baV0gPSBTTm9kZShib2FyZCwgMSAtIHR1cm4sIDEgLSBub2RlVHlwZSk7CiAgICAgIGNoaWxkcmVuW2ldLmxhc3RNb3ZlID0gbW92ZXNbaV07CiAgICAgIHVubW92ZShib2FyZCwgbW92ZXNbaV0sIHR1cm4pOwogICAgfQogICAgdXBkYXRlKCk7CiAgfQoKICBTTm9kZSAqZ2V0TWluUHJvb2ZDaGlsZCgpIHsKICAgIGludCBwcm9vZiA9IElORjsKICAgIGZvcihpbnQgaSA9IDA7IGkgPCBjaGlsZHJlblNpemU7aSsrKXsKICAgICAgcHJvb2YgPSBtaW4ocHJvb2YsIGNoaWxkcmVuW2ldLnBmKTsKICAgIH0KICAgIGZvcihpbnQgaSA9IDA7IGkgPCBjaGlsZHJlblNpemU7aSsrKXsKICAgICAgaWYoY2hpbGRyZW5baV0ucGYgPT0gcHJvb2YpCiAgICAgICAgcmV0dXJuIGNoaWxkcmVuICsgaTsKICAgIH0KICB9CgogIFNOb2RlICpnZXRNaW5EaXNQcm9vZkNoaWxkKCkgewogICAgaW50IHByb29mID0gSU5GOwogICAgZm9yKGludCBpID0gMDsgaSA8IGNoaWxkcmVuU2l6ZTtpKyspewogICAgICBwcm9vZiA9IG1pbihwcm9vZiwgY2hpbGRyZW5baV0uZHApOwogICAgfQogICAgZm9yKGludCBpID0gMDsgaSA8IGNoaWxkcmVuU2l6ZTtpKyspewogICAgICBpZihjaGlsZHJlbltpXS5kcCA9PSBwcm9vZikKICAgICAgICByZXR1cm4gY2hpbGRyZW4gKyBpOwogICAgfQogIH0KCiAgc3RhdGljIHZvaWQgYmVzdEZpcnN0U2VhcmNoKFNOb2RlICpub2RlLCBCb2FyZCAmYm9hcmQpIHsKICAgIGlmKG5vZGUtPnRlcm1pbmF0ZU5vZGUpIHsKICAgICAgbm9kZS0+ZXhwYW5kKGJvYXJkKTsKICAgIH1lbHNlewogICAgICBpZihub2RlLT5ub2RlVHlwZSA9PSBPUikgewogICAgICAgIFNOb2RlICpiZXN0ID0gbm9kZS0+Z2V0TWluUHJvb2ZDaGlsZCgpOwogICAgICAgIG1vdmUoYm9hcmQsIGJlc3QtPmxhc3RNb3ZlLCBub2RlLT50dXJuKTsKICAgICAgICBiZXN0Rmlyc3RTZWFyY2goYmVzdCwgYm9hcmQpOwogICAgICAgIHVubW92ZShib2FyZCwgYmVzdC0+bGFzdE1vdmUsIG5vZGUtPnR1cm4pOwogICAgICB9ZWxzZXsKICAgICAgICBTTm9kZSAqYmVzdCA9IG5vZGUtPmdldE1pbkRpc1Byb29mQ2hpbGQoKTsKICAgICAgICBtb3ZlKGJvYXJkLCBiZXN0LT5sYXN0TW92ZSwgbm9kZS0+dHVybik7CiAgICAgICAgYmVzdEZpcnN0U2VhcmNoKGJlc3QsIGJvYXJkKTsKICAgICAgICB1bm1vdmUoYm9hcmQsIGJlc3QtPmxhc3RNb3ZlLCBub2RlLT50dXJuKTsKICAgICAgfQogICAgICBub2RlLT51cGRhdGUoKTsKICAgIH0KICB9CiAgc3RhdGljIHZvaWQgZGZzKEJvYXJkICZib2FyZCwgU05vZGUgJm4sIGludCB0dXJuLCBpbnQgZGVwdGgpIHsKICAgIGNvdXQgPDwgZGVwdGggPDwgZW5kbDsKICAgIGJvYXJkLnNob3coKTsKICAgIGlmKHR1cm4gPT0gMCkgewogICAgICBmb3IoaW50IGkgPSAwOyBpIDwgbi5jaGlsZHJlblNpemU7IGkrKykgewogICAgICAgIGlmKG4uY2hpbGRyZW5baV0ucGYgPT0gMCl7IAogICAgICAgICAgU05vZGUgJmNoaWxkID0gbi5jaGlsZHJlbltpXTsKICAgICAgICAgIG1vdmUoYm9hcmQsIGNoaWxkLmxhc3RNb3ZlLCB0dXJuKTsKICAgICAgICAgIGRmcyhib2FyZCwgY2hpbGQsICF0dXJuLCAxICsgZGVwdGgpOwogICAgICAgICAgdW5tb3ZlKGJvYXJkLCBjaGlsZC5sYXN0TW92ZSwgdHVybik7CiAgICAgICAgfQogICAgICB9CiAgICB9ZWxzZXsKICAgICAgZm9yKGludCBpID0gMDsgaSA8IG4uY2hpbGRyZW5TaXplOyBpKyspIHsKICAgICAgICBpZihuLmNoaWxkcmVuW2ldLnBmID09IDApeyAKICAgICAgICAgIFNOb2RlICZjaGlsZCA9IG4uY2hpbGRyZW5baV07CiAgICAgICAgICBtb3ZlKGJvYXJkLCBjaGlsZC5sYXN0TW92ZSwgdHVybik7CiAgICAgICAgICBkZnMoYm9hcmQsIGNoaWxkLCAhdHVybiwgMSArIGRlcHRoKTsKICAgICAgICAgIHVubW92ZShib2FyZCwgY2hpbGQubGFzdE1vdmUsIHR1cm4pOwogICAgICAgIH0KICAgICAgfQogICAgfQogIH0KICBzdGF0aWMgdm9pZCBjaGVzc1Byb2JsZW1TZWFyY2goQm9hcmQgJmJvYXJkLCBpbnQgdHVybikgewogICAgU05vZGUgcm9vdCA9IFNOb2RlKGJvYXJkLCBPUiwgdHVybik7CiAgICB3aGlsZShyb290LmRwID4gMCAmJiByb290LnBmID4gMCkgewogICAgICBiZXN0Rmlyc3RTZWFyY2goJnJvb3QsIGJvYXJkKTsKICAgIH0KICAgIGNvdXQgPDwgcm9vdC5kcCA8PCIsIiA8PCByb290LnBmIDw8IGVuZGw7CiAgICBkZnMoYm9hcmQsIHJvb3QsIDAsIDApOwogIH0KCn07CmludCBzZWFyY2goaW50IHR1cm4sIGludCBkZXB0aCwgQm9hcmQgJmJvYXJkKSB7CiAgdmVjdG9yPE1vdmU+IG1vdmVzID0gY2hlY2tfbW92ZShib2FyZCwgYm9hcmQuZ2VuZXJhdGVfbW92ZXModHVybiksIHR1cm4pOwogIGlmKG1vdmVzLnNpemUoKSA9PSAwKSB7CiAgICBpZihkZXB0aCA9PSAxMykKICAgICAgYm9hcmQuc2hvdygpOwogICAgcmV0dXJuIC0xOwogIH0KICBpZihkZXB0aCA9PSAxMylyZXR1cm4gMTsKICBjb3V0IDw8IGRlcHRoIDw8ICAiLCIgPDwgbW92ZXMuc2l6ZSgpIDw8IGVuZGw7CiAgYm9hcmQuc2hvdygpOwogIGludCByZXN1bHQgPSAtMTsKICBmb3IoTW92ZSBtdjogbW92ZXMpIHsKICAgIG1vdmUoYm9hcmQsIG12LHR1cm4pOwogICAgcmVzdWx0ID0gbWF4KHJlc3VsdCwgLXNlYXJjaCghdHVybiwgZGVwdGggKyAxLCBib2FyZCkpOwogICAgdW5tb3ZlKGJvYXJkLCBtdiwgdHVybik7CiAgICBpZihyZXN1bHQgPiAwKWJyZWFrOwogIH0KICBjb3V0IDw8IHJlc3VsdCA8PCBlbmRsOwogIHJldHVybiByZXN1bHQ7Cn0KaW50IG1haW4oKSB7CiAgQm9hcmQgYm9hcmQ7CiAgYm9hcmQueFswXSA9IDQ7CiAgYm9hcmQueVswXSA9IDI7CiAgYm9hcmQudHVyblswXSA9IDE7CgogIGJvYXJkLnhbMV0gPSA1OwogIGJvYXJkLnlbMV0gPSAyOwogIGJvYXJkLnR1cm5bMV0gPSAxOwoKICBib2FyZC54WzJdID0gMjsKICBib2FyZC55WzJdID0gMTsKICBib2FyZC50dXJuWzJdID0gMDsKCiAgYm9hcmQueFszXSA9IC0xOwogIGJvYXJkLnlbM10gPSAtMTsKICBib2FyZC50dXJuWzNdID0gMDsKCiAgYm9hcmQueFs0XSA9IDQ7CiAgYm9hcmQueVs0XSA9IDE7CiAgYm9hcmQudHVybls0XSA9IDE7CiAgCiAgYm9hcmQueFs1XSA9IC0xOwogIGJvYXJkLnlbNV0gPSAtMTsKICBib2FyZC50dXJuWzVdID0gMDsKCiAgYm9hcmQueFs2XSA9IC0xOwogIGJvYXJkLnlbNl0gPSAtMTsKICBib2FyZC50dXJuWzZdID0gMDsKCiAgYm9hcmQueFs3XSA9IDM7CiAgYm9hcmQueVs3XSA9IDQ7CiAgYm9hcmQudHVybls3XSA9IDA7CgogIGJvYXJkLnhbOF0gPSAtMTsKICBib2FyZC55WzhdID0gLTE7CiAgYm9hcmQudHVybls4XSA9IDA7CgogIGJvYXJkLnNob3coKTsKICBTTm9kZTo6Y2hlc3NQcm9ibGVtU2VhcmNoKGJvYXJkLCAwKTsKfQ==