<p>You are given two <strong>positive</strong> integers <code>n</code> and <code>k</code>.</p>

<p>An integer <code>x</code> is called <strong>k-palindromic</strong> if:</p>

<ul>
	<li><code>x</code> is a <span data-keyword="palindrome-integer">palindrome</span>.</li>
	<li><code>x</code> is divisible by <code>k</code>.</li>
</ul>

<p>Return the<strong> largest</strong> integer having <code>n</code> digits (as a string) that is <strong>k-palindromic</strong>.</p>

<p><strong>Note</strong> that the integer must <strong>not</strong> have leading zeros.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">n = 3, k = 5</span></p>

<p><strong>Output:</strong> <span class="example-io">&quot;595&quot;</span></p>

<p><strong>Explanation:</strong></p>

<p>595 is the largest k-palindromic integer with 3 digits.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">n = 1, k = 4</span></p>

<p><strong>Output:</strong> <span class="example-io">&quot;8&quot;</span></p>

<p><strong>Explanation:</strong></p>

<p>4 and 8 are the only k-palindromic integers with 1 digit.</p>
</div>

<p><strong class="example">Example 3:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">n = 5, k = 6</span></p>

<p><strong>Output:</strong> <span class="example-io">&quot;89898&quot;</span></p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= k &lt;= 9</code></li>
</ul>

sys.set_int_max_str_digits(100010)
class Solution:
    def largestPalindrome(self, n: int, k: int) -> str:
        def build(tail, n):
            tail = str(tail)
            if n == 1:
                return tail
            if n == 2:
                return tail + tail
            return tail + ("9" * (n-2)) + tail

        if k == 1:
            return "9" * n
        if k == 2:
            return build(8, n)
        if k == 5:
            return build(5, n)    

        
        def build2(tail, n):
            suffix = str(tail)
            prefix = suffix[::-1]
            m = len(suffix)
            if n == 1:
                return prefix[0]
            if n == 2:
                return prefix[0] * 2
            if n == 3:
                return prefix[:2] + suffix[-1]
            if n == 4:
                return prefix[:2] + suffix[-2:]        
            if n >= 7:
                cut = 3
            else:
                cut = 2        
            nines = ("9" * ((n - 2 * m - 1) // 2))
            if n % 2 == 1:
                for i in range(9, -1, -1):
                    t = prefix[:cut] + nines + str(i) + nines + suffix[-cut:]
                    if int(t) % k == 0:
                        return t
                return ""
            for i in range(9, -1, -1):
                t = prefix[:cut] + nines + str(i) + str(i) + nines + suffix[-cut:]
                if int(t) % k == 0:
                    return t
            return ""



        
        for lead in range(999, 0, -1):
            tail = int(str(lead)[::-1])
            if k % 2 == 0 and tail % 2 != 0:
                continue

            t = build2(tail, n)
            if t == "":
                continue
            if int(t) % k == 0:
                return t
         
            
19363