Given an integer array queries and a positive integer intLength, return an array answer where answer[i] is either the queries[i]th smallest positive palindrome of length intLength or -1 if no such palindrome exists.

A palindrome is a number that reads the same backwards and forwards. Palindromes cannot have leading zeros.

&nbsp;
Example 1:

Input: queries = [1,2,3,4,5,90], intLength = 3
Output: [101,111,121,131,141,999]
Explanation:
The first few palindromes of length 3 are:
101, 111, 121, 131, 141, 151, 161, 171, 181, 191, 202, ...
The 90th palindrome of length 3 is 999.


Example 2:

Input: queries = [2,4,6], intLength = 4
Output: [1111,1331,1551]
Explanation:
The first six palindromes of length 4 are:
1001, 1111, 1221, 1331, 1441, and 1551.


&nbsp;
Constraints:


	1 &lt;= queries.length &lt;= 5 * 104
	1 &lt;= queries[i] &lt;= 109
	1 &lt;= intLength&nbsp;&lt;= 15


class Solution:
    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:
        ogLength = intLength
        isOdd = intLength & 1
        if isOdd:
            intLength += 1
        k = intLength // 2
        k = 10 ** (k - 1)
        op = []
        for q in queries:
            pal = str(k + q - 1)
            if isOdd:
                pal += pal[::-1][1:]
            else:
                pal += pal[::-1]
            if len(pal) == ogLength:
                op.append(int(pal))
            else:
                op.append(-1)
        return op
class Solution {
    public long[] kthPalindrome(int[] queries, int intLength) {
        long[] res= new long[queries.length];
        for(int i=0;i<queries.length;i++){
            res[i]=nthPalindrome(queries[i],intLength);
        }
        return res;
    }
    public long nthPalindrome(int nth, int kdigit)
    {
    long temp = (kdigit & 1)!=0 ? (kdigit / 2) : (kdigit/2 - 1);
    long palindrome = (long)Math.pow(10, temp);
    palindrome += nth - 1;
    long res1=palindrome;
    if ((kdigit & 1)>0)
        palindrome /= 10;
    while (palindrome>0)
    {
        res1=res1*10+(palindrome % 10);
        palindrome /= 10;
    }
    String g="";
    g+=res1;
    if(g.length()!=kdigit)
        return -1;
    return res1;
}
}
#define ll long long
class Solution {
public:
    vector<long long> kthPalindrome(vector<int>& queries, int intLength) {
        vector<ll> result;
        ll start = intLength % 2 == 0 ? pow(10, intLength/2 - 1) : pow(10, intLength/2);
        for(int q: queries) { 
            string s = to_string(start + q - 1);
            string palindrome = s;
            reverse(s.begin(), s.end());
            if(intLength % 2 == 0) {
                palindrome += s;
            } else {
                palindrome += s.substr(1, s.size() - 1);
            }
			
			// len of palindrome should be intLength, otherwise -1
            if (palindrome.size() == intLength)
                result.push_back(stoll(palindrome));
            else
                result.push_back(-1);
        }
        
        return result;
    }
};
var kthPalindrome = function(queries, intLength) {
    let output=[];
    // 1. We use FIRST 2 digits to create palindromes: Math.floor((3+1)/2)=2
    let digit=Math.floor((intLength+1)/2);

    for(let i=0; i<queries.length; i++){
        // 2A. Get Nth 2-digits numbers: 10*(2-1)-1+[5,98]=[14,107]
        let helper=10**(digit-1)-1+queries[i];
        // 2B. Digits checking: 107>=100, which is INVALID
        if(helper>=10**digit){output.push(-1)}
        else{
            let m=intLength-digit;
            // 3A. We still need m digits for REFLECTION: 14=>["1","4"]=>"41"
            let add=helper.toString().substr(0, m).split("").reverse().join("");
            // 3B. Multiply 10**m for reversed digits: 14=>1400=>1441
            helper=helper*10**m+add*1;
            output.push(helper);
        }
    }
    return output; // [1441,-1]
};
Find Palindrome With Fixed Length