# bad62_simpler.py
# เวอร์ชันง่าย ๆ อ่านตรงไปตรงมา (เหมาะกับมือใหม่)
# ไอเดีย: ข้อความถูกเข้ารหัส base62 แล้ว .lower() ทำให้ตัวพิมพ์ใหญ่หาย
# ถ้าเดาว่าตัวไหนควรเป็นพิมพ์ใหญ่จริง ๆ ต้อง "ลบค่า" 26*62^(ตำแหน่ง) ออกจากค่าจำนวนเต็ม
# เราจะค่อย ๆ เดาจาก "หัวข้อความ" (MSB ก่อน) แล้วเก็บสถานะที่ดูมีแนวโน้มว่าจะเป็น ASCII ไว้จำนวนหนึ่ง

ALPH = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
VAL = {c: i for i, c in enumerate(ALPH)}
BASE = 62

def base62_decode(s: str) -> int:
    """แปลงสตริง base62 เป็นจำนวนเต็ม (ตีความตาม ALPH มาตรฐาน)"""
    v = 0
    for ch in s:
        v = v * BASE + VAL[ch]
    return v

def to_bytes_be(n: int, L: int) -> bytes:
    """แปลงจำนวนเต็มเป็นไบต์แบบ big-endian ความยาว L ไบต์ (ตัด/เสริมศูนย์ตาม L)"""
    b = bytearray(L)
    for i in range(L - 1, -1, -1):
        b[i] = n & 0xFF
        n >>= 8
    return bytes(b)

def is_printable_ascii(bs: bytes) -> int:
    """ให้คะแนนจำนวนไบต์ที่เป็น ASCII พิมพ์ได้ (32..126)"""
    score = 0
    for b in bs:
        if 32 <= b <= 126:
            score += 1
    return score

def prefix_bonus(bs: bytes, tgt=b"flag{") -> int:
    """ให้โบนัสถ้าไบต์ต้น ๆ ตรงกับ 'flag{' """
    m = min(len(bs), len(tgt))
    bonus = 0
    for i in range(m):
        if bs[i] == tgt[i]:
            bonus += 5
    return bonus

def try_decode_ascii(M: int, L_guess: int):
    """ลองแปลงจำนวนเต็มเป็น ASCII ด้วยความยาวไบต์ L_guess หลาย ๆ แบบ
       แล้วคืน flag{...} ถ้าเจอ"""
    import re
    for dL in (-2, -1, 0, 1, 2, 3):
        L = max(1, L_guess + dL)
        bs = to_bytes_be(M, L)
        try:
            s = bs.decode('ascii')
        except:
            continue
        # รูปแบบเข้มงวดที่ผู้ตั้งโจทย์ชอบใช้ (เช่น flag{....._##########})
        if re.fullmatch(r"^flag\{.*_[0-9]{10}\}$", s):
            return s
        # เผื่อกรณีเป็น flag{...} อย่างอื่น
        m = re.search(r"flag\{[^}]+\}", s)
        if m:
            return m.group(0)
    return None

def solve_bad62_head(encoded: str, group_size=6, keep_top=2000):
    """
    กลยุทธ์ง่าย ๆ:
    1) ถอด base62 ทั้งสตริงให้ได้จำนวนเต็ม M0
    2) หา index ของตัวอักษร (ที่อาจเคยเป็นพิมพ์ใหญ่)
    3) เดินจากหัว -> ท้าย ทีละกลุ่มเล็ก ๆ (group_size ตำแหน่ง)
       ภายในแต่ละกลุ่มลอง "เลือก/ไม่เลือก" ลบ 26*62^(pos) สำหรับแต่ละตำแหน่ง
       แล้วให้คะแนนด้วยจำนวน ASCII พิมพ์ได้ + โบนัส prefix 'flag{'
       เก็บเฉพาะสถานะคะแนนสูงสุดไว้ไม่เกิน keep_top อันดับ (ใช้ลิสต์ + sort)
    4) หลังจบทุกกลุ่ม ลองถอด ASCII หา 'flag{...}'
    """
    N = len(encoded)

    # ตำแหน่งที่เป็นตัวอักษร (a..z) ในสตริงที่ถูก lower มาแล้ว
    letter_positions = []
    for i, c in enumerate(encoded):
        if c.isalpha():
            letter_positions.append(i)

    # เตรียม 62^k ล่วงหน้า
    pow62 = [1] * (N + 1)
    for k in range(1, N + 1):
        pow62[k] = pow62[k - 1] * BASE

    # ถ้าตัวนั้น "ควรจะเป็นพิมพ์ใหญ่" จริง ๆ ค่า base62 เดิมจะต่างจากตอนเป็นตัวเล็กอยู่ 26
    # เมื่ออยู่ที่ตำแหน่ง i (นับจากซ้าย) น้ำหนักคือ 62^(N-1-i)
    diffs = {}
    for i in letter_positions:
        diffs[i] = 26 * pow62[N - 1 - i]

    # ค่าจำนวนเต็มตอนทุกตัวเป็น lower (ตามอินพุตที่ได้มา)
    M0 = base62_decode(encoded)

    # เดาความยาว byte จาก bit_length
    L_guess = (M0.bit_length() + 7) // 8
    if L_guess < 1:
        L_guess = 1

    # แบ่งกลุ่มตำแหน่ง (ง่าย ๆ: ก้อนละ group_size)
    groups = []
    pos_sorted = sorted(letter_positions)
    for i in range(0, len(pos_sorted), group_size):
        groups.append(pos_sorted[i:i + group_size])

    # เริ่มด้วย "ยังไม่ลบอะไรเลย"
    # เก็บเป็นลิสต์ของสถานะ: (score, total_subtracted_diff)
    states = [(0, 0)]  # score=0, ยังไม่ลบอะไร

    # เดินทีละกลุ่ม
    for g_index, grp in enumerate(groups):
        # เตรียม "รายการผลรวมที่จะลบ" จากการเลือก/ไม่เลือกในกลุ่มนี้ (แบบง่าย ๆ)
        # adds = {0, d[p1], d[p2], d[p1]+d[p2], ...}
        adds = [0]
        for p in grp:
            d = diffs[p]
            new_adds = []
            for a in adds:
                new_adds.append(a)      # ไม่เลือกตำแหน่ง p
                new_adds.append(a + d)  # เลือกตำแหน่ง p (แปลว่าจริง ๆ มันเป็นพิมพ์ใหญ่)
            adds = new_adds

        # กะว่า "พาร์ทหัว" ที่น่าจะมี character อ่านออกเพิ่มขึ้นตามกลุ่มที่เดินมา
        head_need = min(L_guess, (g_index + 1) * group_size)

        new_states = []
        for (old_score, total_sub) in states:
            base_val = M0 - total_sub
            if base_val <= 0:
                continue
            for add in adds:
                M = base_val - add
                if M <= 0:
                    continue
                # ตัดหัวมาดูความ "พิมพ์ได้"
                bs = to_bytes_be(M, L_guess)
                head = bs[:head_need]
                s = is_printable_ascii(head) + prefix_bonus(head)
                new_states.append((s, total_sub + add))

        # เก็บแค่ตัวท็อป ๆ (เรียงคะแนนแบบง่าย ๆ แล้วหั่น)
        new_states.sort(key=lambda x: x[0], reverse=True)
        states = new_states[:keep_top]

    # หลังจบทุกกลุ่ม ลองถอดจริงหา flag
    for (score, total_sub) in states:
        M = M0 - total_sub
        flag = try_decode_ascii(M, L_guess)
        if flag:
            return flag

    return None

if __name__ == "__main__":
    enc = "cbm6okchgcvxtifbvfd68lmyh38nqxnjxmdtbathtougtkxdmwux9tcmo6rs0j7uuf"
    ans = solve_bad62_head(enc, group_size=6, keep_top=2000)
    print(ans)