import sys
import time
import random

# PeSTO material values [mg, eg]
MG_VAL = {'p': 82, 'n': 337, 'b': 365, 'r': 477, 'q': 1025, 'k': 0}
EG_VAL = {'p': 94, 'n': 281, 'b': 297, 'r': 512, 'q': 936, 'k': 0}
PHASE_INC = {'p': 0, 'n': 1, 'b': 1, 'r': 2, 'q': 4, 'k': 0}

# PeSTO piece-square tables (from white's view, rank8=index0..rank1=index56)
MG_PST = {
'p':[ 0, 0, 0, 0, 0, 0, 0, 0, 98,134, 61, 95, 68,126, 34,-11, -6, 7, 26, 31, 65, 56, 25,-20,-14, 13, 6, 21, 23, 12, 17,-23,-27, -2, -5, 12, 17, 6, 10,-25,-26, -4, -4,-10, 3, 3, 33,-12,-35, -1,-20,-23,-15, 24, 38,-22, 0, 0, 0, 0, 0, 0, 0, 0],
'n':[-29,-51,-23,-15,-22,-18,-50,-64,-20,-22,-15,-15,-14,-14,-12,-14,-17, -7, -6, 1, 0,-14, 2,-21, -9, -5, 11, 16, 22, 17, 14, -3,-13, 4, 16, 13, 28, 19, 21, -8,-23, -9, 12, 10, 19, 17, 25,-16,-29,-53,-12, -3, -1, 18,-14,-19,-105,-21,-58,-33,-17,-28,-19,-23],
'b':[-29, 4,-82,-37, -4,-14,-17,-24,-26, 16,-18,-13, 30, 59, 18,-47,-16, 37, 43, 40, 35, 50, 37, -2, -4, 5, 19, 50, 37, 37, 7, -2, -6, 13, 13, 26, 34, 12, 10, 4, 0, 15, 15, 15, 14, 27, 18, 10, 4, 15, 16, 0, 7, 21, 33, 1,-33, -3,-14,-21,-13,-12,-39,-21],
'r':[ 32, 42, 32, 51, 63, 9, 31, 43, 27, 32, 58, 62, 80, 67, 26, 44, -5, 19, 26, 36, 17, 45, 61, 16,-24,-11, 7, 26, 24, 35, -8,-20,-36,-26,-12, -1, 9, -7, 6,-23,-45,-25,-16,-17, 3, 0, -5,-33,-44,-16,-20, -9, -1, 11, -6,-71,-19,-13, 1, 17, 16, 7,-37,-26],
'q':[-28, 0, 29, 12, 59, 44, 43, 45,-24,-39, -5, 1,-16, 57, 28, 54,-13,-17, 7, 8, 29, 56, 47, 57,-27,-27,-16,-16, -1, 17, -2, 1, -9,-26, -9,-10, -2, -4, 3, -3,-14, 2,-11, -2, -5, 2, 14, 5,-35, -8, 11, 2, 8, 15, -3, 1, -1,-18, -9, 10,-15,-25,-31,-50],
'k':[-74,-35,-18,-18,-11, 15, 4,-17,-53, -5, -8,-23,-23, -8, 1,-15,-11, 4, 13, 1, 5, 0, -5,-17,-17,-20,-12,-27,-30,-25,-14,-36,-49, -1,-27,-39,-46,-44,-33,-51,-14,-14,-22,-46,-44,-30,-15,-27, 1, 7, -8,-64,-43,-16, 9, 8,-15, 36, 12,-54, 8,-28, 24, 14],
}
EG_PST = {
'p':[ 0, 0, 0, 0, 0, 0, 0, 0,178,173,158,134,147,132,165,187, 94,100, 85, 67, 56, 53, 82, 84, 32, 24, 13, 5, -2, 4, 17, 17, 13, 9, -3, -7, -7, -8, 3, -1, 4, 7, -6, 1, 0, -5, -1, -8, 13, 8, 8, 10, 13, 0, 2, -7, 0, 0, 0, 0, 0, 0, 0, 0],
'n':[-53,-34,-21,-11,-28,-14,-24,-43,-44,-16,-13,-10, -5,-15,-17,-46,-20, -6, 9, 13, 11, 5, -2,-23,-17, -4, 18, 29, 25, 15, 8,-16,-18, -6, 16, 25, 16, 17, 4,-18,-23, -3, -1, 15, 10, -3,-20,-22,-42,-20,-10, -5, -2,-20,-23,-44,-29,-51,-23,-15,-22,-18,-50,-64],
'b':[-14,-21,-11, -8, -7, -9,-17,-24, -8, -4, 7,-12, -3,-13, -4,-14, 2, 12, 6, 2, 0, 1, 6, 2, -3, 9, 12, 9, 14, 10, 3, 2, -6, 3, 13, 19, 7, 10, -3, -9,-12, -3, 8, 10, 13, 3, -7,-15,-14,-18, -7, -1, 4, -9,-15,-27,-23, -9,-23, -5, -9,-16, -5,-17],
'r':[ 3, 0, 0, 3, 0, -1, 3, 0, -3, 5, 5, 5, 8, 8, -4, -8, -5, 8, 10, 7, -1, 4, -4, -8, -7, -2, -1, 3, 8, 1, -5,-10, 1, -1, 0, 7, 6, 2, 2, -3, -6, -8, -3, -3, -2, 3, 2, 7,-12, -9, -1, 0, 6, 3, 4, 9, -9,-13,-10, -9, -8, -3, 0, 3],
'q':[ 8, 0, 0, -2, 0, 0, -1, 2, 6, 5, 8, 8, 8, 8, 2, 0, 0, 10, 10, 13, 7, 10, 7, 4, 3, -5, -5, 3, 5, 6, 1, -1, -4,-14,-15,-12, -9, -8, -7,-12,-11,-28,-14,-24, -5, -1, -8,-19,-22,-23,-30,-16,-16,-23,-36,-32,-33,-28,-18,-16,-29, -2, 0,-14],
'k':[-74,-35,-18,-18,-11, 15, 4,-17,-12, 17, 14, 17, 17, 38, 23, 11, 10, 17, 23, 15, 20, 45, 44, 13, -8, 22, 24, 27, 26, 33, 26, 3,-18, -4, 21, 24, 27, 23, 9,-11,-19, -3, 11, 21, 23, 16, 7, -9,-27,-11, 4, 13, 14, 4, -5,-17,-53,-34,-21,-11,-28,-14,-24,-43],
}

# Simple piece values for move ordering
PIECE_VALUES = {'P':100,'N':320,'B':330,'R':500,'Q':900,'K':20000,
                'p':-100,'n':-320,'b':-330,'r':-500,'q':-900,'k':-20000}

# Zobrist hashing
_zrng = random.Random(42)
ZOBRIST_PIECES = {}
for _pc in 'PNBRQKpnbrqk':
    ZOBRIST_PIECES[_pc] = [_zrng.getrandbits(64) for _ in range(64)]
ZOBRIST_EP = [_zrng.getrandbits(64) for _ in range(8)]
ZOBRIST_CASTLE = [_zrng.getrandbits(64) for _ in range(16)]
ZOBRIST_SIDE = _zrng.getrandbits(64)

# Transposition table
TT_EXACT, TT_ALPHA, TT_BETA = 0, 1, 2
TT_SIZE = 1 << 20
TT = {}
TT_AGE = 0
DRAW_CONTEMPT = 12

class Board:
    def __init__(self, fen=None):
        if fen:
            self.parse_fen(fen)
        else:
            self.parse_fen("rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1")

    def parse_fen(self, fen):
        parts = fen.split()
        rows = parts[0].split('/')
        self.board = []
        for row in rows:
            board_row = []
            for char in row:
                if char.isdigit():
                    board_row.extend(['.'] * int(char))
                else:
                    board_row.append(char)
            self.board.append(board_row)
        
        self.turn = parts[1]
        self.castling = parts[2]
        self.en_passant = parts[3]
        self.halfmove_clock = int(parts[4])
        self.fullmove_number = int(parts[5])

    def get_piece(self, r, c):
        if 0 <= r < 8 and 0 <= c < 8:
            return self.board[r][c]
        return None

    def is_empty(self, r, c):
        return self.get_piece(r, c) == '.'

    def get_moves(self):
        moves = []
        for r in range(8):
            for c in range(8):
                piece = self.board[r][c]
                if piece == '.':
                    continue
                if (self.turn == 'w' and piece.isupper()) or (self.turn == 'b' and piece.islower()):
                    moves.extend(self.get_piece_moves(r, c))
        
        legal_moves = []
        for move in moves:
            if not self.leaves_king_in_check(move):
                legal_moves.append(move)
        return legal_moves

    def get_capture_moves(self):
        """Generate only capture moves (for quiescence search)."""
        moves = []
        for r in range(8):
            for c in range(8):
                piece = self.board[r][c]
                if piece == '.': continue
                if (self.turn == 'w' and piece.isupper()) or (self.turn == 'b' and piece.islower()):
                    for m in self.get_piece_moves(r, c):
                        target = self.board[m[1][0]][m[1][1]]
                        is_ep = (piece.lower() == 'p' and self.en_passant != '-' and
                                 m[1][0] == 8 - int(self.en_passant[1]) and
                                 m[1][1] == ord(self.en_passant[0]) - ord('a'))
                        if target != '.' or m[2] is not None or is_ep:
                            if not self.leaves_king_in_check(m):
                                moves.append(m)
        return moves

    def has_non_pawn_material(self):
        """Check if side to move has non-pawn material (for null move safety)."""
        for r in range(8):
            for c in range(8):
                p = self.board[r][c]
                if p == '.': continue
                if self.turn == 'w' and p in 'NBRQ': return True
                if self.turn == 'b' and p in 'nbrq': return True
        return False

    def get_piece_moves(self, r, c):
        piece = self.board[r][c].lower()
        moves = []
        color = 'w' if self.board[r][c].isupper() else 'b'
        
        if piece == 'p':
            direction = -1 if color == 'w' else 1
            if self.is_empty(r + direction, c):
                if (color == 'w' and r + direction == 0) or (color == 'b' and r + direction == 7):
                    for p in 'qrbn':
                        moves.append(((r, c), (r + direction, c), p))
                else:
                    moves.append(((r, c), (r + direction, c), None))
                    if (color == 'w' and r == 6) or (color == 'b' and r == 1):
                        if self.is_empty(r + 2 * direction, c):
                            moves.append(((r, c), (r + 2 * direction, c), None))
            for dc in [-1, 1]:
                target_r, target_c = r + direction, c + dc
                target_piece = self.get_piece(target_r, target_c)
                if target_piece and target_piece != '.' and ((color == 'w' and target_piece.islower()) or (color == 'b' and target_piece.isupper())):
                    if (color == 'w' and target_r == 0) or (color == 'b' and target_r == 7):
                        for p in 'qrbn':
                            moves.append(((r, c), (target_r, target_c), p))
                    else:
                        moves.append(((r, c), (target_r, target_c), None))
                ep_square = self.en_passant
                if ep_square != '-':
                    ep_c = ord(ep_square[0]) - ord('a')
                    ep_r = 8 - int(ep_square[1])
                    if target_r == ep_r and target_c == ep_c:
                        moves.append(((r, c), (target_r, target_c), None))

        elif piece == 'n':
            for dr, dc in [(2, 1), (2, -1), (-2, 1), (-2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2)]:
                nr, nc = r + dr, c + dc
                target = self.get_piece(nr, nc)
                if target and (target == '.' or (color == 'w' and target.islower()) or (color == 'b' and target.isupper())):
                    moves.append(((r, c), (nr, nc), None))
        
        elif piece in 'brq':
            directions = []
            if piece in 'rq': directions.extend([(0, 1), (0, -1), (1, 0), (-1, 0)])
            if piece in 'bq': directions.extend([(1, 1), (1, -1), (-1, 1), (-1, -1)])
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                while True:
                    target = self.get_piece(nr, nc)
                    if not target: break
                    if target == '.':
                        moves.append(((r, c), (nr, nc), None))
                    else:
                        if (color == 'w' and target.islower()) or (color == 'b' and target.isupper()):
                            moves.append(((r, c), (nr, nc), None))
                        break
                    nr += dr
                    nc += dc

        elif piece == 'k':
            for dr in [-1, 0, 1]:
                for dc in [-1, 0, 1]:
                    if dr == 0 and dc == 0: continue
                    nr, nc = r + dr, c + dc
                    target = self.get_piece(nr, nc)
                    if target and (target == '.' or (color == 'w' and target.islower()) or (color == 'b' and target.isupper())):
                        moves.append(((r, c), (nr, nc), None))
            if color == 'w' and r == 7 and c == 4:
                if ('K' in self.castling and self.board[7][7] == 'R' and
                    self.board[7][5] == '.' and self.board[7][6] == '.' and
                    not self.is_attacked(7, 4, 'b') and not self.is_attacked(7, 5, 'b')):
                    moves.append(((7, 4), (7, 6), None))
                if ('Q' in self.castling and self.board[7][0] == 'R' and
                    self.board[7][1] == '.' and self.board[7][2] == '.' and self.board[7][3] == '.' and
                    not self.is_attacked(7, 4, 'b') and not self.is_attacked(7, 3, 'b')):
                    moves.append(((7, 4), (7, 2), None))
            elif color == 'b' and r == 0 and c == 4:
                if ('k' in self.castling and self.board[0][7] == 'r' and
                    self.board[0][5] == '.' and self.board[0][6] == '.' and
                    not self.is_attacked(0, 4, 'w') and not self.is_attacked(0, 5, 'w')):
                    moves.append(((0, 4), (0, 6), None))
                if ('q' in self.castling and self.board[0][0] == 'r' and
                    self.board[0][1] == '.' and self.board[0][2] == '.' and self.board[0][3] == '.' and
                    not self.is_attacked(0, 4, 'w') and not self.is_attacked(0, 3, 'w')):
                    moves.append(((0, 4), (0, 2), None))
                    
        return moves

    def is_attacked(self, r, c, by_color):
        """Fast ray-cast attack detection from target square outward."""
        b = self.board
        if by_color == 'w':
            pawn, knight, bishop, rook, queen, king = 'P','N','B','R','Q','K'
        else:
            pawn, knight, bishop, rook, queen, king = 'p','n','b','r','q','k'
        # Pawn attacks
        pd = -1 if by_color == 'w' else 1
        for dc in (-1, 1):
            pr, pc2 = r + pd, c + dc
            if 0 <= pr < 8 and 0 <= pc2 < 8 and b[pr][pc2] == pawn:
                return True
        # Knight attacks
        for dr, dc in ((2,1),(2,-1),(-2,1),(-2,-1),(1,2),(1,-2),(-1,2),(-1,-2)):
            nr, nc = r+dr, c+dc
            if 0 <= nr < 8 and 0 <= nc < 8 and b[nr][nc] == knight:
                return True
        # King attacks
        for dr in (-1,0,1):
            for dc in (-1,0,1):
                if dr == 0 and dc == 0: continue
                nr, nc = r+dr, c+dc
                if 0 <= nr < 8 and 0 <= nc < 8 and b[nr][nc] == king:
                    return True
        # Rook/Queen (straight)
        for dr, dc in ((0,1),(0,-1),(1,0),(-1,0)):
            nr, nc = r+dr, c+dc
            while 0 <= nr < 8 and 0 <= nc < 8:
                p = b[nr][nc]
                if p != '.':
                    if p == rook or p == queen: return True
                    break
                nr += dr; nc += dc
        # Bishop/Queen (diagonal)
        for dr, dc in ((1,1),(1,-1),(-1,1),(-1,-1)):
            nr, nc = r+dr, c+dc
            while 0 <= nr < 8 and 0 <= nc < 8:
                p = b[nr][nc]
                if p != '.':
                    if p == bishop or p == queen: return True
                    break
                nr += dr; nc += dc
        return False

    def leaves_king_in_check(self, move):
        start, end, promo = move
        sr, sc = start
        er, ec = end
        original_piece = self.board[er][ec]
        moving_piece = self.board[sr][sc]
        # Handle en passant: remove captured pawn
        ep_captured = None
        if moving_piece.lower() == 'p' and self.en_passant != '-':
            ep_c = ord(self.en_passant[0]) - ord('a')
            ep_r = 8 - int(self.en_passant[1])
            if er == ep_r and ec == ep_c:
                ep_captured = self.board[sr][ec]
                self.board[sr][ec] = '.'
        self.board[er][ec] = moving_piece if not promo else (promo.upper() if moving_piece.isupper() else promo.lower())
        self.board[sr][sc] = '.'
        king_piece = 'K' if self.turn == 'w' else 'k'
        opponent_color = 'b' if self.turn == 'w' else 'w'
        if moving_piece.lower() == 'k':
            kr, kc = er, ec
        else:
            kr, kc = -1, -1
            for r in range(8):
                for c in range(8):
                    if self.board[r][c] == king_piece:
                        kr, kc = r, c
                        break
        in_check = self.is_attacked(kr, kc, opponent_color)
        self.board[sr][sc] = moving_piece
        self.board[er][ec] = original_piece
        if ep_captured is not None:
            self.board[sr][ec] = ep_captured
        return in_check

    def make_move(self, move):
        start, end, promo = move
        sr, sc = start
        er, ec = end
        piece = self.board[sr][sc]
        captured = self.board[er][ec]
        # Update castling rights when a rook is captured on its home square.
        if captured == 'R':
            if er == 7 and ec == 0: self.castling = self.castling.replace('Q', '')
            if er == 7 and ec == 7: self.castling = self.castling.replace('K', '')
        elif captured == 'r':
            if er == 0 and ec == 0: self.castling = self.castling.replace('q', '')
            if er == 0 and ec == 7: self.castling = self.castling.replace('k', '')
        if piece.lower() == 'k':
            if self.turn == 'w':
                self.castling = self.castling.replace('K', '').replace('Q', '')
                if sc == 4 and ec == 6:
                    self.board[7][5] = 'R'; self.board[7][7] = '.'
                elif sc == 4 and ec == 2:
                    self.board[7][3] = 'R'; self.board[7][0] = '.'
            else:
                self.castling = self.castling.replace('k', '').replace('q', '')
                if sc == 4 and ec == 6:
                    self.board[0][5] = 'r'; self.board[0][7] = '.'
                elif sc == 4 and ec == 2:
                    self.board[0][3] = 'r'; self.board[0][0] = '.'
        if piece == 'R':
            if sr == 7 and sc == 0: self.castling = self.castling.replace('Q', '')
            if sr == 7 and sc == 7: self.castling = self.castling.replace('K', '')
        elif piece == 'r':
            if sr == 0 and sc == 0: self.castling = self.castling.replace('q', '')
            if sr == 0 and sc == 7: self.castling = self.castling.replace('k', '')
        if piece.lower() == 'p' and self.en_passant != '-':
            ep_c = ord(self.en_passant[0]) - ord('a')
            ep_r = 8 - int(self.en_passant[1])
            if er == ep_r and ec == ep_c:
                self.board[sr][ec] = '.'
        if piece.lower() == 'p' and abs(er - sr) == 2:
            self.en_passant = chr(ord('a') + sc) + str(8 - (sr + er) // 2)
        else:
            self.en_passant = '-'
        self.board[er][ec] = piece if not promo else (promo.upper() if piece.isupper() else promo.lower())
        self.board[sr][sc] = '.'
        self.turn = 'b' if self.turn == 'w' else 'w'

    def compute_hash(self):
        h = 0
        for r in range(8):
            for c in range(8):
                p = self.board[r][c]
                if p != '.':
                    h ^= ZOBRIST_PIECES[p][r * 8 + c]
        ci = 0
        for i, ch in enumerate('KQkq'):
            if ch in self.castling: ci |= (1 << i)
        h ^= ZOBRIST_CASTLE[ci]
        if self.en_passant != '-':
            h ^= ZOBRIST_EP[ord(self.en_passant[0]) - ord('a')]
        if self.turn == 'b':
            h ^= ZOBRIST_SIDE
        return h

    def evaluate(self):
        mg, eg, phase = [0, 0], [0, 0], 0
        wb, bb = 0, 0
        wp_files = [0] * 8
        bp_files = [0] * 8
        wpawns = []
        bpawns = []
        for r in range(8):
            for c in range(8):
                piece = self.board[r][c]
                if piece == '.': continue
                pt = piece.lower()
                is_white = piece.isupper()
                idx = 0 if is_white else 1
                sq = r * 8 + c if is_white else (7 - r) * 8 + c
                mg[idx] += MG_VAL[pt] + MG_PST[pt][sq]
                eg[idx] += EG_VAL[pt] + EG_PST[pt][sq]
                if pt == 'b':
                    if is_white:
                        wb += 1
                    else:
                        bb += 1
                elif pt == 'p':
                    if is_white:
                        wp_files[c] += 1
                        wpawns.append((r, c))
                    else:
                        bp_files[c] += 1
                        bpawns.append((r, c))
                phase += PHASE_INC[pt]
        if wb >= 2:
            mg[0] += 30
            eg[0] += 30
        if bb >= 2:
            mg[1] += 30
            eg[1] += 30
        # Pawn structure: doubled/isolated and passed pawns.
        for f in range(8):
            if wp_files[f] > 1:
                mg[0] -= 14 * (wp_files[f] - 1)
                eg[0] -= 18 * (wp_files[f] - 1)
            if bp_files[f] > 1:
                mg[1] -= 14 * (bp_files[f] - 1)
                eg[1] -= 18 * (bp_files[f] - 1)
            if wp_files[f] and (f == 0 or wp_files[f - 1] == 0) and (f == 7 or wp_files[f + 1] == 0):
                mg[0] -= 10
                eg[0] -= 14
            if bp_files[f] and (f == 0 or bp_files[f - 1] == 0) and (f == 7 or bp_files[f + 1] == 0):
                mg[1] -= 10
                eg[1] -= 14
        for r, c in wpawns:
            blocked = False
            for rr in range(r - 1, -1, -1):
                for cc in (c - 1, c, c + 1):
                    if 0 <= cc < 8 and self.board[rr][cc] == 'p':
                        blocked = True
                        break
                if blocked:
                    break
            if not blocked:
                adv = 6 - r
                mg[0] += 12 + adv * 6
                eg[0] += 18 + adv * 10
        for r, c in bpawns:
            blocked = False
            for rr in range(r + 1, 8):
                for cc in (c - 1, c, c + 1):
                    if 0 <= cc < 8 and self.board[rr][cc] == 'P':
                        blocked = True
                        break
                if blocked:
                    break
            if not blocked:
                adv = r - 1
                mg[1] += 12 + adv * 6
                eg[1] += 18 + adv * 10
        # Rook on open/semi-open files.
        for r in range(8):
            for c in range(8):
                p = self.board[r][c]
                if p == 'R':
                    if wp_files[c] == 0 and bp_files[c] == 0:
                        mg[0] += 20; eg[0] += 12
                    elif wp_files[c] == 0:
                        mg[0] += 10; eg[0] += 6
                elif p == 'r':
                    if wp_files[c] == 0 and bp_files[c] == 0:
                        mg[1] += 20; eg[1] += 12
                    elif bp_files[c] == 0:
                        mg[1] += 10; eg[1] += 6
        phase = min(phase, 24)
        wt = 0 if self.turn == 'w' else 1
        mg_score = mg[wt] - mg[wt ^ 1]
        eg_score = eg[wt] - eg[wt ^ 1]
        return (mg_score * phase + eg_score * (24 - phase)) // 24

def move_to_uci(move):
    start, end, promo = move
    s = chr(ord('a') + start[1]) + str(8 - start[0])
    e = chr(ord('a') + end[1]) + str(8 - end[0])
    return s + e + (promo if promo else "")

# Killer moves: 2 slots per ply, up to depth 64
killers = [[None, None] for _ in range(64)]

# History heuristic: indexed by (piece, to_square) for quiet move ordering
history = {}

# Global search control
stopped = False
nodes = 0

def tt_store(h, depth, flag, score, best_move):
    """Depth/age-aware TT replacement with partial eviction."""
    global TT
    old = TT.get(h)
    if old:
        od, _, _, _, oage = old
        if od > depth and oage == TT_AGE:
            return
    TT[h] = (depth, flag, score, best_move, TT_AGE)
    if len(TT) <= TT_SIZE:
        return
    # Evict a small sample of older/shallower entries instead of clearing all.
    excess = len(TT) - TT_SIZE
    to_remove = min(max(1024, excess * 2), 8192)
    candidates = []
    for k, v in TT.items():
        d, _, _, _, age = v
        candidates.append((age, d, k))
        if len(candidates) >= to_remove * 4:
            break
    candidates.sort(key=lambda x: (x[0], x[1]))
    for _, _, k in candidates[:to_remove]:
        TT.pop(k, None)

def decay_history():
    if not history:
        return
    kill = []
    for k, v in history.items():
        nv = v // 2
        if nv:
            history[k] = nv
        else:
            kill.append(k)
    for k in kill:
        history.pop(k, None)

def quiesce(board, alpha, beta, start_time, time_limit):
    global stopped, nodes
    nodes += 1
    if nodes & 2047 == 0 and time.time() - start_time > time_limit:
        stopped = True
    if stopped:
        return 0
    stand_pat = board.evaluate()
    if stand_pat >= beta:
        return beta
    # Delta pruning: if even capturing a queen can't raise alpha, skip
    if stand_pat + 1025 < alpha:
        return alpha
    if stand_pat > alpha:
        alpha = stand_pat
    captures = board.get_capture_moves()
    def cap_sort_key(m):
        target = board.board[m[1][0]][m[1][1]]
        val = abs(PIECE_VALUES.get(target, 0)) if target != '.' else 100
        attacker = board.board[m[0][0]][m[0][1]]
        return val * 10 - abs(PIECE_VALUES.get(attacker, 0))
    captures.sort(key=cap_sort_key, reverse=True)
    for move in captures:
        # Delta pruning per capture
        target = board.board[move[1][0]][move[1][1]]
        cap_val = abs(PIECE_VALUES.get(target, 0)) if target != '.' else 100
        if stand_pat + cap_val + 200 < alpha and move[2] is None:
            continue
        ob = [row[:] for row in board.board]
        ot, oc, oe = board.turn, board.castling, board.en_passant
        board.make_move(move)
        score = -quiesce(board, -beta, -alpha, start_time, time_limit)
        board.board, board.turn, board.castling, board.en_passant = ob, ot, oc, oe
        if stopped: return 0
        if score >= beta:
            return beta
        if score > alpha:
            alpha = score
    return alpha

def negamax(board, depth, alpha, beta, start_time, time_limit, ply=0, do_null=True):
    global stopped, nodes
    nodes += 1
    if nodes & 2047 == 0 and time.time() - start_time > time_limit:
        stopped = True
    if stopped:
        return 0

    is_pv = beta - alpha > 1
    # Mate distance pruning.
    alpha = max(alpha, -90000 + ply)
    beta = min(beta, 90000 - ply - 1)
    if alpha >= beta:
        return alpha

    # TT probe
    h = board.compute_hash()
    tt_entry = TT.get(h)
    if tt_entry and tt_entry[0] >= depth:
        td, tf, ts, tm, tage = tt_entry
        if not is_pv:
            if tf == TT_EXACT: return ts
            if tf == TT_ALPHA and ts <= alpha: return alpha
            if tf == TT_BETA and ts >= beta: return beta

    if depth <= 0:
        return quiesce(board, alpha, beta, start_time, time_limit)

    # Find king and check status
    king = 'K' if board.turn == 'w' else 'k'
    kr, kc = -1, -1
    for r in range(8):
        for c in range(8):
            if board.board[r][c] == king:
                kr, kc = r, c
                break
    opp = 'b' if board.turn == 'w' else 'w'
    in_check = board.is_attacked(kr, kc, opp)

    if in_check and ply < 30:
        depth += 1

    # Static eval for pruning decisions
    static_eval = board.evaluate()

    # Reverse futility pruning (static null move pruning)
    if not is_pv and not in_check and depth <= 2 and ply > 0:
        margin = 90 * depth + 60
        if static_eval - margin >= beta:
            return static_eval - margin

    # Null move pruning
    null_failed = False
    if do_null and not in_check and depth >= 3 and ply > 0 and board.has_non_pawn_material():
        ob = [row[:] for row in board.board]
        ot, oc, oe = board.turn, board.castling, board.en_passant
        board.turn = 'b' if board.turn == 'w' else 'w'
        board.en_passant = '-'
        R = 3 if depth >= 6 else 2
        score = -negamax(board, depth - 1 - R, -beta, -beta + 1, start_time, time_limit, ply + 1, False)
        board.board, board.turn, board.castling, board.en_passant = ob, ot, oc, oe
        if stopped: return 0
        if score >= beta:
            return beta
        null_failed = True

    # Razoring: at low depth, if eval is far below alpha, drop to qsearch
    if not is_pv and not in_check and depth <= 2 and ply > 0:
        razor_margin = 300 + 200 * depth
        if static_eval + razor_margin < alpha:
            score = quiesce(board, alpha, beta, start_time, time_limit)
            if score < alpha:
                return score

    moves = board.get_moves()
    if not moves:
        if in_check:
            return -90000 + ply
        return DRAW_CONTEMPT

    # Move ordering
    tt_move = tt_entry[3] if tt_entry else None
    # Internal iterative deepening to seed tt_move in PV nodes.
    if not tt_move and is_pv and depth >= 5:
        _ = negamax(board, depth - 2, alpha, beta, start_time, time_limit, ply, do_null)
        if stopped:
            return 0
        te = TT.get(h)
        if te:
            tt_move = te[3]
    k1 = killers[ply][0] if ply < 64 else None
    k2 = killers[ply][1] if ply < 64 else None
    def move_sort_key(m):
        if tt_move and m == tt_move: return 10000000
        target = board.board[m[1][0]][m[1][1]]
        if target != '.' or m[2] is not None:
            return 1000000 + (abs(PIECE_VALUES.get(target, 0)) if target != '.' else 100)
        if k1 and m[0] == k1[0] and m[1] == k1[1]: return 500000
        if k2 and m[0] == k2[0] and m[1] == k2[1]: return 400000
        piece = board.board[m[0][0]][m[0][1]]
        return history.get((piece, m[1][0], m[1][1]), 0)
    moves.sort(key=move_sort_key, reverse=True)

    best_score = -99999
    best_move = moves[0]
    flag = TT_ALPHA
    moves_searched = 0

    for move in moves:
        ob = [row[:] for row in board.board]
        ot, oc, oe = board.turn, board.castling, board.en_passant
        target = board.board[move[1][0]][move[1][1]]
        is_quiet = (target == '.' and move[2] is None)

        # Futility pruning: at low depth, skip quiet moves unlikely to raise alpha
        if not is_pv and is_quiet and not in_check and depth <= 2 and ply > 0 and moves_searched > 0:
            futility_margin = 150 * depth
            if static_eval + futility_margin <= alpha:
                moves_searched += 1
                continue
        # Late move pruning: skip very late quiets in non-PV nodes.
        if (not is_pv and is_quiet and not in_check and ply > 0 and depth <= 3 and
            moves_searched >= (4 + depth * 2)):
            moves_searched += 1
            continue

        # Singular extension on likely-best TT move (lightweight verification).
        singular_ext = 0
        if tt_move and move == tt_move and depth >= 7 and not in_check:
            singular_beta = alpha - 35
            score_probe = -99999
            for om in moves:
                if om == move:
                    continue
                ob2 = [row[:] for row in board.board]
                ot2, oc2, oe2 = board.turn, board.castling, board.en_passant
                board.make_move(om)
                score_probe = max(score_probe, -negamax(board, depth - 3, -singular_beta, -singular_beta + 1, start_time, time_limit, ply + 1, False))
                board.board, board.turn, board.castling, board.en_passant = ob2, ot2, oc2, oe2
                if stopped:
                    return 0
                if score_probe >= singular_beta:
                    break
            if score_probe < singular_beta:
                singular_ext = 1

        board.make_move(move)

        # PVS + LMR
        child_do_null = not null_failed
        if moves_searched == 0:
            score = -negamax(board, depth - 1 + singular_ext, -beta, -alpha, start_time, time_limit, ply + 1, child_do_null)
        else:
            # LMR for late quiet moves
            if moves_searched >= 3 and depth >= 3 and is_quiet and not in_check:
                R = 1 + (moves_searched >= 6) + (depth >= 5)
                score = -negamax(board, depth - 1 - R + singular_ext, -alpha - 1, -alpha, start_time, time_limit, ply + 1, child_do_null)
            else:
                score = alpha + 1  # force full search
            # PVS re-search if reduced/zero-window found improvement
            if score > alpha:
                score = -negamax(board, depth - 1 + singular_ext, -beta, -alpha, start_time, time_limit, ply + 1, child_do_null)

        board.board, board.turn, board.castling, board.en_passant = ob, ot, oc, oe
        moves_searched += 1
        if stopped: return 0

        if score > best_score:
            best_score = score
            best_move = move
        if score > alpha:
            alpha = score
            flag = TT_EXACT
        if alpha >= beta:
            flag = TT_BETA
            if is_quiet and ply < 64:
                if killers[ply][0] != move:
                    killers[ply][1] = killers[ply][0]
                    killers[ply][0] = move
                piece = board.board[move[0][0]][move[0][1]]
                hkey = (piece, move[1][0], move[1][1])
                history[hkey] = history.get(hkey, 0) + depth * depth
            break

    tt_store(h, depth, flag, best_score, best_move)
    return best_score

def get_best_move(fen):
    global killers, history, stopped, nodes, TT_AGE
    TT_AGE = (TT_AGE + 1) & 0xFFFF
    board = Board(fen)
    moves = board.get_moves()
    if not moves: return None
    if len(moves) == 1:
        return move_to_uci(moves[0])
    best_move = moves[0]
    start_time = time.time()
    # Adaptive budget under a 5s cap: spend more in complex/tactical positions.
    complexity = min(1.0, len(moves) / 35.0)
    soft_limit = 2.2 + 1.6 * complexity
    hard_limit = 4.85
    time_limit = min(hard_limit, soft_limit + 0.15)
    killers = [[None, None] for _ in range(64)]
    history = {}
    stopped = False
    nodes = 0
    prev_score = 0
    for depth in range(1, 60):
        # History decay to avoid stale ordering pollution.
        if depth % 4 == 0:
            decay_history()
        # Aspiration windows with proper fail-low/high recovery.
        window = 50 if depth >= 4 else 99999
        if depth >= 4:
            a0, b0 = prev_score - window, prev_score + window
        else:
            a0, b0 = -99999, 99999
        current_best = None
        best_score = -99999
        while True:
            stopped = False
            a, b = a0, b0
            best_score = -99999
            current_best = None
            for i, move in enumerate(moves):
                ob = [row[:] for row in board.board]
                ot, oc, oe = board.turn, board.castling, board.en_passant
                target = board.board[move[1][0]][move[1][1]]
                is_quiet = (target == '.' and move[2] is None)
                # Root pruning for late quiet moves at shallow depth.
                if i > 5 and depth <= 2 and is_quiet and board.evaluate() + 110 * depth <= a:
                    continue
                board.make_move(move)
                if current_best is None:
                    score = -negamax(board, depth - 1, -b, -a, start_time, time_limit, 1, True)
                else:
                    score = -negamax(board, depth - 1, -a - 1, -a, start_time, time_limit, 1, True)
                    if score > a and score < b and not stopped:
                        score = -negamax(board, depth - 1, -b, -a, start_time, time_limit, 1, True)
                board.board, board.turn, board.castling, board.en_passant = ob, ot, oc, oe
                if stopped:
                    break
                if score > best_score:
                    best_score = score
                    current_best = move
                    if score > a:
                        a = score
            if stopped:
                break
            if depth < 4 or (best_score > a0 and best_score < b0):
                break
            # Recover from aspiration failure by widening and re-searching same depth.
            window *= 2
            if best_score <= a0:
                a0 = max(-99999, best_score - window)
            else:
                b0 = min(99999, best_score + window)
            if time.time() - start_time > time_limit * 0.92:
                break
        if current_best:
            best_move = current_best
            prev_score = best_score
            moves.remove(current_best)
            moves.insert(0, current_best)
        if stopped or time.time() - start_time > time_limit:
            break
        if abs(best_score) >= 89000:
            break
    return move_to_uci(best_move)

def main():
    while True:
        line = sys.stdin.readline()
        if not line: break
        fen = line.strip()
        if not fen: continue
        try:
            move = get_best_move(fen)
            if move:
                # Final legality guard before output.
                board = Board(fen)
                legal_uci = {move_to_uci(m) for m in board.get_moves()}
                out = move if move in legal_uci else (random.choice(list(legal_uci)) if legal_uci else None)
                if out:
                    sys.stdout.write(out + "\n")
                    sys.stdout.flush()
        except:
            try:
                board = Board(fen)
                moves = board.get_moves()
                if moves:
                    sys.stdout.write(move_to_uci(random.choice(moves)) + "\n")
                    sys.stdout.flush()
            except: pass

if __name__ == "__main__":
    main()