Find the Largest Palindrome Divisible by K

Find the largest n-digit palindrome (no leading zeros) divisible by k and return it as a string; with n up to 1e5 and k ≤ 9, the core challenge is to construct the lexicographically largest palindrome by selecting the first half and using modular arithmetic to adjust digits so the full palindrome is divisible by k while operating on very long strings.