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

<p>A <strong>palindrome</strong> is a number that reads the same backwards and forwards. Palindromes cannot have leading zeros.</p>

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

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

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

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

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

<ul>
	<li><code>1 &lt;= queries.length &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>1 &lt;= queries[i] &lt;= 10<sup>9</sup></code></li>
	<li><code>1 &lt;= intLength&nbsp;&lt;= 15</code></li>
</ul>

class Solution {
public:
 

    long long int pow(int a,long long int n){
        if(n==0){
            return 1;
        }
        return (a*pow(a,n-1));
    }
    long long fun(long long int c,long long int n){
      
      long long int ans;
     long long  int f=(n-1)/2;
      if(c> (9* pow(10,f)) ){
          return -1;
      }
    long long   int d=c%10;
      c=c/10;
      long long int count=1;
     long long  int flag=0;
      if(d!=0){
          ans=d-1;
      }
      else if(d==0){
          ans=9;
          flag=1;
      }
      if(n%2==0){
          int e=ans*10+ans;
          ans=e;
          
          count++;
      }
      if(n==1){
         return (ans+1);        
      }
      if(n==2){
          return (ans+11);
      }
   
      while(count<n){
          if(c==0){
              d=0;
          }
          else if(c!=0){
             d=c%10;
             
          }
        
         
          if(c==0){
              int left=(n-count);
              left=left/2;
             
              ans=ans*pow(10,left)+1;
              
              count=count+left;
              
              d=pow(10,count+left-1)+ans;
              ans=d;
              return ans;
          }
        
          if(count==n-2){
              
            d=d+1;
            
          }
          
            if(flag==0){
                
           count++;
            
           ans=ans*10+d;
          
           count++;
           d=d*pow(10,count-1)+ans;
           ans=d;
           
            }
            else if(flag!=0){
               if(d==0){
                 d=9;
                  count++;
               ans=ans*10+d;
               count++;
              d=d*pow(10,count-1)+ans;
              ans=d;
                 
               }
               else if(d!=0){
                   
                   d=d-1;
                   flag=0;
                   count++;
               ans=ans*10+d;
               count++;
              d=d*pow(10,count-1)+ans;
              ans=d;
               }

            }
          c=c/10;
           
      }


    return ans;
        
    }

    vector<long long> kthPalindrome(vector<int>& queries, int intLength) {
        
     vector<long long> v;

     long long int ans;
    
    long long  int n=intLength;
     
    long long  int i;
     for(i=0;i<queries.size();i++){
          
          v.push_back(fun(queries[i],intLength));
        
     }

      return v;
    }
};
58800