Given a number, in the form of an array Num[] of size N containing digits from 1 to 9(inclusive). The task is to find the next smallest palindrome strictly larger than the given number.
Example 1:
Input:
N = 11
Num[] = {9, 4, 1, 8, 7, 9, 7, 8, 3, 2, 2}
Output: 9 4 1 8 8 0 8 8 1 4 9
Explanation: Next smallest palindrome is
94188088149.
Example 2:
Input:
N = 5
Num[] = {2, 3, 5, 4, 5}
Output: 2 3 6 3 2
Explanation: Next smallest palindrome is
23632.
Your Task:
Complete the function generateNextPalindrome() which takes an array num, and an single integer n, as input parameters and returns an array of integers denoting the answer. You don't to print answer or take inputs.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 <= N <= 10^{5}
1 <= Num[i] <= 9

Difficulty: MEDIUM_HARD
Tags: Data structures
Skill types: Data structures
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3
class Solution:


	def generateNextPalindrome(self,num, n ) :
	    # code here

Solutions:
class Solution:

	def generateNextPalindrome(self, num, n):
		if num.count(9) == len(num):
			return [1] + [0 for i in range(n - 1)] + [1]
		x = num[:]
		mid = n // 2
		if mid == n / 2:
			num[mid:] = num[:mid][::-1]
		else:
			num[mid + 1:] = num[:mid][::-1]
		if num <= x:
			if mid == n / 2:
				if num[mid] == 9:
					mid1 = mid - 1
					mid2 = mid
					while num[mid1] == 9 and num[mid2] == 9:
						num[mid1] = 0
						num[mid2] = 0
						mid1 -= 1
						mid2 += 1
					num[mid1] += 1
					num[mid2] += 1
				else:
					num[mid] += 1
					num[mid - 1] += 1
			elif num[mid] == 9:
				num[mid] = 0
				mid1 = mid - 1
				mid2 = mid + 1
				while num[mid1] == 9 and num[mid2] == 9:
					num[mid1] = 0
					num[mid2] = 0
					mid1 -= 1
					mid2 += 1
				num[mid1] += 1
				num[mid2] += 1
			else:
				num[mid] += 1
		return num


class Solution:

	def makePalindrome(self, in_str: str) -> str:
		(a, b) = (0, len(in_str) - 1)
		in_list = list(in_str)
		while a < b:
			in_list[b] = in_list[a]
			a += 1
			b -= 1
		return ''.join(in_list)

	def solve(self, A: str) -> str:
		n = len(A)
		temp = self.makePalindrome(A)
		if temp > A:
			return temp
		carry = 1
		A_list = list(A)
		for a in range((n - 1) // 2, -1, -1):
			t = int(A_list[a]) + carry
			if t == 10:
				t = 0
				carry = 1
			else:
				carry = 0
			A_list[a] = str(t)
		if carry == 1:
			A_list.insert(0, '1')
		return self.makePalindrome(''.join(A_list))

	def generateNextPalindrome(self, num, n):
		A = ''.join((str(x) for x in num))
		res = self.solve(A)
		ans = [int(i) for i in res]
		return ans


class Solution:

	def generateNextPalindrome(self, num, n):
		num2 = num[:]
		for i in range(n // 2):
			num[n - 1 - i] = num[i]
		if num2 < num:
			return num
		curr = n // 2
		while curr >= 0 and num[curr] == 9:
			num[curr] = 0
			num[n - 1 - curr] = 0
			curr -= 1
		if curr < 0:
			ans = [0] * (n + 1)
			ans[0] = ans[-1] = 1
		else:
			num[curr] += 1
			num[n - 1 - curr] = num[curr]
			ans = num
		return ans


class Solution:

	def generateNextPalindrome(self, num, l):

		def reverse(num):
			return num[::-1]

		def add_one_to_str(list_str):
			return list(map(int, list(str(int(''.join(map(str, list_str))) + 1))))
		if l == 1:
			res = add_one_to_str(num)
			if len(res) > 1:
				return self.generateNextPalindrome(res, len(res))
		elif l % 2 == 0:
			left = num[:l // 2]
			right = num[l // 2:]
			if reverse(left) < right:
				left = add_one_to_str(left)
			elif reverse(left) == right:
				num = add_one_to_str(num)
				return self.generateNextPalindrome(num, len(num))
			res = left + reverse(left)
		else:
			left = num[:l // 2]
			mid = num[l // 2]
			right = num[l // 2 + 1:]
			if reverse(left) < right:
				mid += 1
				if mid == 10:
					mid = 0
					left = add_one_to_str(left)
			elif reverse(left) == right:
				num = add_one_to_str(num)
				return self.generateNextPalindrome(num, len(num))
			res = left + [mid] + reverse(left)
		return ''.join(map(str, res))


class Solution:

	def generateNextPalindrome(self, num, n):
		if n % 2 == 0:
			i = n // 2 - 1
			j = i + 1
		else:
			i = n // 2
			j = i
		f = 0
		x = i
		y = j
		palinx = x
		paliny = y
		while i >= 0:
			if num[i] > num[j]:
				f = 1
				num[j] = num[i]
				break
			elif num[i] < num[j]:
				f = 1
				if num[x] == 9:
					while num[x] == 9:
						num[x] = 0
						num[y] = 0
						x -= 1
						y += 1
					num[x] += 1
					num[y] = num[x]
					num[j] = num[i]
					break
				else:
					num[x] += 1
					num[y] = num[x]
					num[j] = num[i]
					break
			i -= 1
			j += 1
		while i >= 0:
			num[j] = num[i]
			i -= 1
			j += 1
		if f == 0:
			chk = 0
			for i in range(n):
				if num[i] != 9:
					chk = 1
					break
			if chk == 0:
				num[0] = 1
				for i in range(1, n):
					num[i] = 0
				num.append(1)
			elif num[palinx] == 9:
				while num[palinx] == 9:
					num[palinx] = 0
					num[paliny] = 0
					palinx -= 1
					paliny += 1
				num[palinx] += 1
				num[paliny] = num[palinx]
			else:
				num[palinx] += 1
				num[paliny] = num[palinx]
		return num


class Solution:

	def generateNextPalindromeUtil(self, num, n):
		mid = int(n // 2)
		leftsmaller = False
		i = mid - 1
		j = mid + 1 if n % 2 else mid
		while i >= 0 and num[i] == num[j]:
			i -= 1
			j += 1
		if i < 0 or num[i] < num[j]:
			leftsmaller = True
		while i >= 0:
			num[j] = num[i]
			j += 1
			i -= 1
		if leftsmaller == True:
			carry = 1
			i = mid - 1
			if n % 2 == 1:
				num[mid] += carry
				carry = int(num[mid] // 10)
				num[mid] %= 10
				j = mid + 1
			else:
				j = mid
			while i >= 0:
				num[i] += carry
				carry = num[i] // 10
				num[i] %= 10
				num[j] = num[i]
				j += 1
				i -= 1

	def generateNextPalindrome(self, num, n):
		ans = []
		if self.AreAll9s(num, n) == True:
			ans.append(1)
			for i in range(1, n):
				ans.append(0)
			ans.append(1)
		else:
			self.generateNextPalindromeUtil(num, n)
			ans = num
		return ans

	def AreAll9s(self, num, n):
		for i in range(0, n):
			if num[i] != 9:
				return 0
		return 1


class Solution:

	def generateNextPalindrome(self, num, n):
		res = ''

		def convert(arr):
			res = ''
			for i in arr:
				res += str(i)
			return res
		num = convert(num)
		if num == num[::-1]:
			num = int(num) + 1
			num = str(num)
			if int(num) <= 9:
				return num
		if len(num) % 2 == 0:
			mid = len(num) // 2
			first_half = num[:mid]
			second_half = num[mid:]
			if int(convert(first_half[::-1])) >= int(convert(second_half)):
				second_half = first_half[::-1]
				res += convert(first_half) + convert(second_half)
			else:
				temp = str(int(convert(first_half)) + 1)
				res += temp + temp[::-1]
		else:
			mid = len(num) // 2
			first_half = num[:mid]
			second_half = num[mid + 1:]
			if int(convert(first_half[::-1])) >= int(convert(second_half)):
				second_half = first_half[::-1]
				res += convert(first_half) + str(num[mid]) + convert(second_half)
			else:
				temp = str(int(convert(first_half)) * 10 + int(num[mid]) + 1)
				res += temp + temp[::-1][1:]
		return res


class Solution:

	def generateNextPalindrome(self, num, n):
		if n == 1:
			if num[0] == 9:
				num[0] = 1
				num.append(1)
				return num
			else:
				num[0] += 1
				return num
		nu = ''
		for j in num:
			nu += str(j)
		ans = ''
		if n % 2 == 0:
			if nu[n // 2 - 1::-1] > nu[n // 2:]:
				ans += nu[:n // 2] + nu[n // 2 - 1::-1]
				l = list(map(int, list(ans)))
				return l
			else:
				for j in range(n // 2 - 1, -1, -1):
					if num[j] == 9:
						num[j] = 0
					else:
						num[j] += 1
						break
				nu = ''
				for j in num:
					nu += str(j)
				ans += nu[:n // 2] + nu[n // 2 - 1::-1]
				l = list(map(int, list(ans)))
				return l
		elif nu[n // 2 - 1::-1] > nu[n // 2 + 1:]:
			ans += nu[:n // 2 + 1] + nu[n // 2 - 1::-1]
			l = list(map(int, list(ans)))
			return l
		else:
			for j in range(n // 2, -1, -1):
				if num[j] == 9:
					num[j] = 0
				else:
					num[j] += 1
					break
			nu = ''
			for j in num:
				nu += str(j)
			ans += nu[:n // 2 + 1] + nu[n // 2 - 1::-1]
			l = list(map(int, list(ans)))
			return l


class Solution:

	def is_palindrome(self, a):
		return a == a[::-1]

	def add_1(self, x):
		ns = ''
		carry = 1
		for c in reversed(x):
			d = (int(c) + carry) // 10
			r = (int(c) + carry) % 10
			ns += str(r)
			carry = d
		if carry:
			ns += str(carry)
		return ns[::-1]

	def handle_odd(self, a):
		n = len(a)
		mid = n // 2
		left = a[:mid]
		right = a[mid + 1:]
		revleft = left[::-1]
		if revleft > right:
			return left + a[mid] + revleft
		else:
			left = left + a[mid]
			left = self.add_1(left)
			return left + left[::-1][1:]

	def handle_even(self, a):
		n = len(a)
		mid = n // 2
		left = a[:mid]
		right = a[mid:]
		revleft = left[::-1]
		if revleft <= right:
			left = self.add_1(left)
			return left + left[::-1]
		else:
			return left + revleft

	def solve(self, a):
		if self.is_palindrome(a):
			a = self.add_1(a)
		if self.is_palindrome(a):
			return a
		n = len(a)
		if n & 1:
			return self.handle_odd(a)
		else:
			return self.handle_even(a)

	def generateNextPalindrome(self, num, n):
		a = map(str, num)
		a = ''.join(a)
		return self.solve(a)


class Solution:

	def is_palindrome(self, a):
		return a == a[::-1]

	def compare(self, left, right):
		for (l, r) in zip(left, right):
			if l > r:
				return 1
			elif l < r:
				return -1
			else:
				continue
		return 0

	def add_1(self, x):
		ns = ''
		carry = 1
		for c in reversed(x):
			(d, r) = divmod(int(c) + carry, 10)
			ns += str(r)
			carry = d
		if carry:
			ns += str(carry)
		return ns[::-1]

	def handle_odd(self, a):
		n = len(a)
		mid = n // 2
		left = a[:mid]
		right = a[mid + 1:]
		if self.compare(left[::-1], right) == 1:
			return left + a[mid] + left[::-1]
		else:
			left = left + a[mid]
			left = self.add_1(left)
			return left + left[::-1][1:]

	def handle_even(self, a):
		n = len(a)
		mid = n // 2
		left = a[:mid]
		right = a[mid:]
		if self.compare(left[::-1], right) == -1:
			left = self.add_1(left)
			return left + left[::-1]
		else:
			return left + left[::-1]

	def solve(self, a):
		if self.is_palindrome(a):
			a = self.add_1(a)
		if self.is_palindrome(a):
			return a
		n = len(a)
		if n & 1:
			return self.handle_odd(a)
		else:
			return self.handle_even(a)

	def generateNextPalindrome(self, num, n):
		a = map(str, num)
		a = ''.join(a)
		return self.solve(a)


class Solution:

	def generateNextPalindrome(self, num, n):
		number = ''
		for integer in num:
			number += str(integer)
		middle = ''
		if len(number) % 2 != 0:
			middle = number[len(number) // 2]
		first = number[:len(number) // 2]
		if first + middle + first[::-1] > number:
			pass
		elif middle == '9':
			middle = '0'
			if first == '':
				first = '0'
			first = str(int(first) + 1)
			if len(first) != len(number) // 2:
				middle = ''
		elif middle != '':
			middle = str(int(middle) + 1)
		else:
			if first == '':
				first = '0'
			first = str(int(first) + 1)
			if len(first) != len(number) // 2:
				middle = first[-1]
				first = first[:-1]
		nextNumber = first + middle + first[::-1]
		num = [0] * len(nextNumber)
		for i in range(len(nextNumber)):
			num[i] = int(nextNumber[i])
		return num


def palindrome(num):
	return num == num[::-1]

def add_1(num):
	return str(int(num) + 1)

class Solution:

	def generateNextPalindrome(self, num, n):
		a = ''.join((str(x) for x in num))
		if palindrome(a):
			a = add_1(a)
		n = len(a)
		if n == 1:
			return list(a)
		if n % 2 == 1:
			left = a[:n // 2]
			mid = a[n // 2]
			right = a[n // 2 + 1:]
			if int(left[::-1]) > int(right):
				return list(left + mid + left[::-1])
			else:
				left += mid
				left = add_1(left)
				return list(left + left[::-1][1:])
		else:
			left = a[:n // 2]
			right = a[n // 2:]
			if int(left[::-1]) > int(right):
				return list(left + left[::-1])
			else:
				left = add_1(left)
				return list(left + left[::-1])
		a = ''.join((str(x) for x in num))
		if palindrome(a):
			a = add_1(a)
		n = len(a)
		if n == 1:
			num[0] += 1
			return num
		if n % 2 == 1:
			left = a[:n // 2]
			mid = a[n // 2]
			right = a[n // 2 + 1:]
			if int(left[::-1]) > int(right):
				return list(left + mid + left[::-1])
			else:
				left += mid
				left = add_1(left)
				return list(left + left[::-1][1:])
		else:
			left = a[:n // 2]
			right = a[n // 2:]
			if int(left[::-1]) > int(right):
				return list(left + left[::-1])
			else:
				left = add_1(left)
				return list(left + left[::-1])


class Solution:

	def generateNextPalindrome(self, num, n):

		def isAll9(number):
			for num in number:
				if num != 9:
					return False
			return True
		if n == 1 and num[0] != 9:
			return [num[0] + 1]
		if isAll9(num):
			result = [1] + [0] * (n - 1)
			return result + [1]
		(i, j) = (n // 2 - 1, n // 2 + 1)
		if n % 2 == 0:
			j = n // 2
		while i >= 0 and num[i] == num[j]:
			i -= 1
			j += 1
		midIncrement = False
		if i < 0 or num[i] < num[j]:
			midIncrement = True
		mid = n // 2
		(i, j) = (mid - 1, mid + 1)
		if n % 2 == 0:
			j = mid
		carry = 0
		if midIncrement:
			if n % 2 == 0:
				mid -= 1
			num[mid] += 1
			carry = num[mid] // 10
			num[mid] = num[mid] % 10
			if n % 2 == 0:
				num[j] = num[mid]
				j += 1
				i -= 1
		while i >= 0 and j < n:
			num[i] += carry
			carry = num[i] // 10
			num[i] %= 10
			num[j] = num[i]
			i -= 1
			j += 1
		return num


class Solution:

	def isPalindrome(self, s):
		return s == s[::-1]

	def addOne(self, s):
		return str(int(s) + 1)

	def compareStrings(self, x, y):
		for (i, j) in zip(x, y):
			if int(i) > int(j):
				return 1
			elif int(i) < int(j):
				return -1
			else:
				continue
		return 0

	def handle_odd(self, s):
		n = len(s)
		left = s[:n // 2]
		mid = s[n // 2]
		right = s[n // 2 + 1:]
		if self.compareStrings(left[::-1], right) == 1:
			return left + mid + left[::-1]
		else:
			left = left + mid
			left = self.addOne(left)
			return left + left[::-1][1:]

	def handle_even(self, s):
		n = len(s)
		left = s[:n // 2]
		right = s[n // 2:]
		if self.compareStrings(left[::-1], right) == 1:
			return left + left[::-1]
		else:
			left = self.addOne(left)
			return left + left[::-1]

	def generateNextPalindrome(self, num, n):
		s = ''
		for i in num:
			s += chr(48 + i)
		if s == '9':
			return '11'
		if len(s) == 1:
			return str(int(s) + 1)
		if self.isPalindrome(s) == True:
			s = self.addOne(s)
		if len(s) & 1:
			return self.handle_odd(s)
		else:
			return self.handle_even(s)
		return num


class Solution:

	def generateNextPalindrome(self, num, n):
		new_num = num[:n // 2] + (num[n // 2:n // 2 + 1] if n % 2 else []) + num[:n // 2][::-1]
		if new_num > num:
			return new_num

		def str_sum(nn=num[:(n + 1) // 2]):
			carry = 1
			ans = []
			for i in range(len(nn) - 1, -1, -1):
				(carry, new_num) = ((nn[i] + carry) // 10, (nn[i] + carry) % 10)
				ans.append(new_num)
			if carry:
				ans.append(carry)
			return ans[::-1]
		if num == [9] * n:
			num = str_sum(num)
			num = str_sum(num)
			return num[::-1]
		num = str_sum()
		new_num = num[:n // 2] + (num[n // 2:n // 2 + 1] if n % 2 else []) + num[:n // 2][::-1]
		return new_num


class Solution:

	def makePalindrome(self, num, n):
		ans = [0 for _ in range(n)]
		for i in range(0, (n - 1) // 2 + 1):
			ans[i] = num[i]
			ans[n - i - 1] = num[i]
		return ans

	def compare(self, a, b, n):
		for i in range(0, n):
			if a[i] > b[i]:
				return True
			if a[i] < b[i]:
				return False
		return False

	def all9(self, num, n):
		for i in range(0, n):
			if num[i] != 9:
				return False
		return True

	def generateNextPalindrome(self, num, n):
		ans = []
		if self.all9(num, n):
			ans.append(1)
			for _ in range(1, n):
				ans.append(0)
			ans.append(1)
			return ans
		palindromeNum = self.makePalindrome(num, n)
		if self.compare(palindromeNum, num, n):
			return palindromeNum
		carry = 1
		for i in range((n - 1) // 2, -1, -1):
			value = palindromeNum[i] + carry
			palindromeNum[i] = value % 10
			carry = value // 10
		return self.makePalindrome(palindromeNum, n)


class Solution:

	def generateNextPalindrome(self, num, n):
		ans = []
		All9 = True
		for i in range(n):
			if num[i] != 9:
				All9 = False
				break
		if All9:
			ans.append(1)
			for i in range(1, n):
				ans.append(0)
			ans.append(1)
			return ans
		mid = n // 2
		i = mid - 1
		j = mid + 1 if n % 2 else mid
		while i >= 0 and num[i] == num[j]:
			i -= 1
			j += 1
		if i >= 0 and num[i] > num[j]:
			while i >= 0:
				num[j] = num[i]
				i -= 1
				j += 1
		elif i < 0 or num[i] < num[j]:
			carry = 1
			i = mid - 1
			if n % 2:
				num[mid] += carry
				carry = num[mid] // 10
				num[mid] = num[mid] % 10
				j = mid + 1
			else:
				j = mid
			while i >= 0:
				num[i] += carry
				carry = num[mid] // 10
				num[mid] = num[mid] % 10
				num[j] = num[i]
				i -= 1
				j += 1
		return num


class Solution:

	def generateNextPalindrome(self, num, n):

		def add_middle(num):
			if n & 1 == 1:
				l = n // 2 - 1
				r = n // 2 + 1
				carry = 1
				num[n // 2] += carry
				carry = num[n // 2] // 10
				num[n // 2] = num[n // 2] % 10
				while l >= 0:
					num[l] += carry
					carry = num[l] // 10
					num[l] = num[l] % 10
					num[r] = num[l]
					l -= 1
					r += 1
			else:
				l = n // 2 - 1
				r = n // 2
				carry = 1
				while l >= 0:
					num[l] += carry
					carry = num[l] // 10
					num[l] = num[l] % 10
					num[r] = num[l]
					l -= 1
					r += 1
			return num
		if num == [9] * n:
			return [1] + [0] * (n - 1) + [1]
		elif n & 1 == 1:
			i = n // 2 - 1
			j = n // 2 + 1
			left = num[:n // 2]
			right = num[n // 2 + 1:]
			if left == right[::-1]:
				return add_middle(num)
			while num[i] == num[j]:
				i -= 1
				j += 1
			if num[i] > num[j]:
				return num[:i + 1] + num[i + 1:j] + num[:i + 1][::-1]
			else:
				return add_middle(num)
		else:
			i = n // 2 - 1
			j = n // 2
			left = num[:n // 2]
			right = num[n // 2:]
			if left == right[::-1]:
				return add_middle(num)
			while num[i] == num[j]:
				i -= 1
				j += 1
			if num[i] > num[j]:
				return num[:i + 1] + num[i + 1:j] + num[:i + 1][::-1]
			else:
				return add_middle(num)


class Solution:

	def generateNextPalindrome(self, num, n):
		if sum(num) == 9 * n:
			ans = [0] * (n + 1)
			ans[0] = 1
			ans[-1] = 1
			num[:] = ans
			return num
		mid = int(n / 2)
		l = mid - 1
		r = mid + 1 if n % 2 != 0 else mid
		leftsmall = False
		while l >= 0 and num[l] == num[r]:
			l -= 1
			r += 1
		if l < 0 or num[l] < num[r]:
			leftsmall = True
		while l >= 0:
			num[r] = num[l]
			l -= 1
			r += 1
		if leftsmall:
			l = mid - 1
			carry = 1
			if n % 2 == 1:
				num[mid] += carry
				carry = num[mid] // 10
				num[mid] %= 10
				r = mid + 1
			else:
				r = mid
			while l >= 0:
				num[l] += carry
				carry = num[l] // 10
				num[l] %= 10
				num[r] = num[l]
				l -= 1
				r += 1
			if carry:
				num = [1] + num + [1]
		return num


class Solution:

	def generateNextPalindrome(self, num, n):
		if n == 1 and num[0] < 9:
			a = sum(num) + 1
			return [a]
		elif n == 1 and num[0] == 9:
			return [1, 1]
		mid = n // 2
		c = int(''.join(list(map(str, reversed(num[:mid])))))
		if n % 2 == 1:
			d = int(''.join(list(map(str, num[mid + 1:]))))
			if c > d:
				num[mid + 1:] = reversed(num[:mid])
				return num
			else:
				a = int(''.join(list(map(str, num[:mid + 1])))) + 1
				a = list(str(a))
				a = list(map(int, a))
				num[:mid + 1] = a
				num[mid + 1:] = reversed(num[:mid])
		else:
			e = int(''.join(list(map(str, num[mid:]))))
			if c > e:
				num[mid:] = reversed(num[:mid])
				return num
			else:
				a = int(''.join(list(map(str, num[:mid])))) + 1
				a = list(str(a))
				a = list(map(int, a))
				num[:mid] = a
				num[mid:] = reversed(num[:mid])
		return num


class Solution:

	def generateNextPalindrome(self, num, n):
		check = False
		i = n // 2
		while i < n:
			if num[i] < num[-(i + 1)]:
				check = True
				break
			elif num[i] == num[-(i + 1)]:
				i += 1
			else:
				break
		if check:
			j = n // 2
			while j < n:
				num[j] = num[-(j + 1)]
				j += 1
			return num
		if n % 2 == 0:
			i = n // 2 - 1
		else:
			i = n // 2
		while i >= 0:
			num[i] += 1
			if num[i] == 10:
				num[i] = 0
				i -= 1
			else:
				break
		if i == -1:
			num = [1] + num
		j = len(num) // 2
		while j < len(num):
			num[j] = num[-(j + 1)]
			j += 1
		return num


class Solution:

	def generateNextPalindrome(self, num, n):
		if n == 1:
			if num[0] < 9:
				num[0] += 1
				return num
			else:
				return [1, 1]
		mid = n // 2
		if n & 1 == 0:
			p = left = mid - 1
			q = right = mid
		else:
			p = left = mid - 1
			q = right = mid + 1
		flag = 1
		while left > -1:
			if num[left] < num[right]:
				flag = 1
				break
			elif num[left] > num[right]:
				flag = 0
				break
			left -= 1
			right += 1
		if flag == 1:
			mid = (n + 1) // 2 - 1
			carry = (num[mid] + 1) // 10
			num[mid] = (num[mid] + 1) % 10
			for i in range(mid - 1, -1, -1):
				if carry == 0:
					break
				t = (num[i] + carry) // 10
				num[i] = (num[i] + carry) % 10
				carry = t
			for i in range(mid + 1):
				num[n - i - 1] = num[i]
			if carry == 1:
				return [1] + num[:-1] + [1]
		else:
			while p > -1:
				num[q] = num[p]
				p -= 1
				q += 1
		return num


class Solution:

	def generateNextPalindrome(self, num, n):
		snum = ''.join([str(x) for x in num])
		if self.isPalindrome(snum, n):
			snum = str(int(snum) + 1)
			if int(snum) >= 0 and int(snum) <= 9:
				return snum
		if n % 2 == 0:
			snum = self.evenCase(snum, n)
		else:
			snum = self.oddCase(snum, n)
		return snum

	def isPalindrome(self, num, n):
		(i, j) = (0, n - 1)
		while i <= j:
			if num[i] != num[j]:
				return False
			i += 1
			j -= 1
		return True

	def oddCase(self, snum, n):
		mid = (n - 1) // 2
		rev_left = snum[mid - 1::-1]
		right = snum[mid + 1:]
		res = ''
		if int(rev_left) < int(right):
			if snum[mid] == '9':
				res = str(int(snum[0:mid + 1]) + 1)
			else:
				res = snum[0:mid] + str(int(snum[mid]) + 1)
		else:
			res = snum[0:mid + 1]
		res += res[mid - 1::-1]
		return res

	def evenCase(self, snum, n):
		mid = (n - 1) // 2
		rev_left = snum[mid::-1]
		right = snum[mid + 1:]
		res = ''
		if int(rev_left) < int(right):
			res = str(int(snum[0:mid + 1]) + 1)
		else:
			res = snum[0:mid + 1]
		res += res[mid::-1]
		return res


class Solution:

	def generateNextPalindrome(self, num, n):
		if n == 1 and num[0] == 9:
			return [1, 1]
		if n == 1:
			return [num[0] + 1]
		strnum = ''.join([str(n) for n in num])
		if strnum == strnum[::-1]:
			strnum = str(int(strnum) + 1)
		numstr = strnum
		if len(numstr) % 2 != 0:
			mid_ind = len(numstr) // 2
			front = numstr[:mid_ind]
			if front[::-1] > numstr[mid_ind + 1:]:
				res = numstr[:mid_ind + 1] + front[::-1]
			else:
				mid = numstr[mid_ind]
				if numstr[mid_ind] == '9':
					front = int(front)
					front += 1
					front = str(front)
					mid = '0'
				else:
					mid = str(int(mid) + 1)
				res = front + mid + front[::-1]
		else:
			mid_ind = len(numstr) // 2
			front = numstr[:mid_ind]
			if front[::-1] > numstr[mid_ind:]:
				res = numstr[:mid_ind] + front[::-1]
			else:
				front = str(int(front) + 1)
				res = front + front[::-1]
		return res


class Solution:

	def all(self, l):
		for i in l:
			if i != 9:
				return False
		return True

	def generateNextPalindrome(self, num, n):
		if self.all(num):
			for i in range(n):
				num[i] = 0
			num.append(1)
			num[0] = 1
		else:
			mid = n // 2
			left = mid - 1
			right = mid + 1 if n % 2 else mid
			while left >= 0:
				if num[left] != num[right]:
					break
				left -= 1
				right += 1
			left_smaller = False
			if left < 0 or num[left] < num[right]:
				left_smaller = True
			while left >= 0:
				num[right] = num[left]
				right += 1
				left -= 1
			if left_smaller:
				carry = 1
				left = mid - 1
				if n % 2 == 0:
					right = mid
				else:
					num[mid] += 1
					carry = num[mid] // 10
					num[mid] %= 10
					right = mid + 1
				while left >= 0 and carry:
					num[left] += 1
					carry = num[left] // 10
					num[left] %= 10
					num[right] = num[left]
					left -= 1
					right += 1
		return num


class Solution:

	def isallnine(self, num):
		co = 0
		for el in num:
			if el == 9:
				co += 1
		return True if co == len(num) else False

	def getnext(self, num, n):
		res = []
		if n & 1:
			mid = n // 2
			(i, j) = (mid - 1, mid + 1)
			while i >= 0 and j < n:
				if num[i] == num[j]:
					i -= 1
					j += 1
				else:
					break
			if i < 0 and j > n - 1 or num[i] < num[j]:
				carry = 1
				for k in range(mid, -1, -1):
					num[k] += carry
					carry = num[k] // 10
					num[k] %= 10
				for k in range(mid + 1, n):
					num[k] = num[mid - (k - mid)]
				if carry != 0:
					res = [1] + num + [1]
				else:
					res = num
			else:
				res = num[0:mid] + [num[mid]] + num[0:mid][::-1]
		else:
			mid = n // 2
			(i, j) = (mid - 1, mid)
			while i >= 0 and j < n:
				if num[i] == num[j]:
					i -= 1
					j += 1
				else:
					break
			if i < 0 and j > n - 1 or num[i] < num[j]:
				carry = 1
				for k in range(mid - 1, -1, -1):
					num[k] += carry
					carry = num[k] // 10
					num[k] %= 10
				if carry == 0:
					res = num[0:mid] + num[0:mid][::-1]
				else:
					res = [1] + num[0:mid] + num[0:mid][::-1] + [1]
			else:
				res = num[0:mid] + num[0:mid][::-1]
		return res

	def generateNextPalindrome(self, num, n):
		res = []
		if self.isallnine(num):
			res.append(1)
			for i in range(n - 1):
				res.append(0)
			res.append(1)
			return res
		else:
			res = self.getnext(num, n)
			return res


class Solution:

	def generateNextPalindrome(self, num, n):
		if n == 1 and num[0] == 9:
			return self.generateNextPalindrome([1, 0], 2)
		if n == 1:
			return [num[0] + 1]
		string_n = ''.join((str(_) for _ in num))
		if string_n == string_n[::-1]:
			string_n = str(int(string_n) + 1)
		mid = len(string_n) // 2
		res_string = ''
		if len(string_n) % 2 == 0:
			left_side = string_n[:mid]
			right_side = string_n[mid:]
			reversed_left_side = left_side[::-1]
			if reversed_left_side > right_side:
				res_string = left_side + reversed_left_side
			else:
				left_side = str(int(left_side) + 1)
				res_string = left_side + left_side[::-1]
		else:
			left_side = string_n[:mid]
			m = string_n[mid]
			right_side = string_n[mid + 1:]
			reversed_left_side = left_side[::-1]
			if reversed_left_side > right_side:
				res_string = left_side + m + reversed_left_side
			elif m != '9':
				m = str(int(m) + 1)
				res_string = left_side + m + reversed_left_side
			else:
				new_left = str(int(left_side + m) + 1)
				string_n = new_left + right_side
				res_string = new_left + new_left[:-1][::-1]
		return [int(x) for x in res_string]


class Solution:

	def generateNextPalindrome(self, arr, n):
		if max(arr) == 9 and min(arr) == 9:
			for i in range(n):
				arr[i] = 0
			arr = [1] + arr
			arr[-1] = 1
			return arr
		mid = (n - 1) // 2
		l = mid
		r = mid
		if n % 2 == 0:
			r = mid + 1
		while l >= 0:
			if arr[l] > arr[r]:
				break
			if arr[r] > arr[l]:
				m = mid
				while m >= 0 and arr[m] == 9:
					arr[m] = 0
					m -= 1
				arr[m] = arr[m] + 1
				break
			l -= 1
			r += 1
		else:
			m = mid
			while m >= 0 and arr[m] == 9:
				arr[m] = 0
				m -= 1
			arr[m] = max(arr[m] + 1, arr[n - 1 - m])
		for i in range(mid + 1):
			arr[n - 1 - i] = arr[i]
		return arr


class Solution:

	def generateNextPalindrome(self, num, n):
		if n == 1 and num[0] == 9:
			return self.generateNextPalindrome([1, 0], 2)
		if n == 1:
			return [num[0] + 1]
		string_n = ''.join((str(_) for _ in num))
		if string_n == string_n[::-1]:
			string_n = str(int(string_n) + 1)
		mid = len(string_n) // 2
		res_string = ''
		if len(string_n) % 2 == 0:
			left_side = string_n[:mid]
			right_side = string_n[mid:]
			reversed_left_side = left_side[::-1]
			if reversed_left_side > right_side:
				res_string = left_side + reversed_left_side
			else:
				left_side = str(int(left_side) + 1)
				res_string = left_side + left_side[::-1]
		else:
			left_side = string_n[:mid]
			m = string_n[mid]
			right_side = string_n[mid + 1:]
			reversed_left_side = left_side[::-1]
			if reversed_left_side > right_side:
				res_string = left_side + m + reversed_left_side
			elif m != '9':
				m = str(int(m) + 1)
				res_string = left_side + m + reversed_left_side
			else:
				new_left = str(int(left_side + m) + 1)
				string_n = new_left + right_side
				res_string = new_left + new_left[:-1][::-1]
		return [int(x) for x in res_string]
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		num = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.generateNextPalindrome(num, n)
		for x in ans:
			print(x, end=' ')
		print()
		tc = tc - 1


class Solution:

	def generateNextPalindrome(self, num, n):

		def util(mid, i, j):
			if n % 2 == 0:
				if num[mid - 1] < 9:
					num[mid - 1] += 1
					num[mid] += 1
					return num
				else:
					while i >= 0 and num[i] == 9 and (num[j] == 9):
						num[i] = 0
						num[j] = 0
						i = i - 1
						j = j + 1
					if i < 0:
						num.append(1)
						num.insert(0, 1)
					else:
						num[i] = num[i] + 1
						num[j] = num[j] + 1
					return num
			elif num[mid] < 9:
				num[mid] += 1
				return num
			else:
				num[mid] = 0
				while i >= 0 and num[i] == 9 and (num[j] == 9):
					num[i] = 0
					num[j] = 0
					i = i - 1
					j = j + 1
				if i < 0:
					num.append(1)
					num.insert(0, 1)
				else:
					num[i] = num[i] + 1
					num[j] = num[j] + 1
				return num
		if n == 1:
			num[0] = num[0] + 1
			if num[0] == 10:
				num = [1, 1]
			return num
		temp = num[0:]
		mid = n // 2
		i = mid - 1
		if n % 2 == 0:
			j = mid
		else:
			j = mid + 1
		num[j:] = num[:mid][::-1]
		if num == temp:
			return util(mid, i, j)
		for t in range(j, n):
			if temp[t] > num[t]:
				return util(mid, i, j)
			if temp[t] < num[t]:
				return num
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		num = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.generateNextPalindrome(num, n)
		for x in ans:
			print(x, end=' ')
		print()
		tc = tc - 1


class Solution:

	def mid(self, num, i, j):
		if i + 1 == j:
			if num[j] < num[i]:
				num[j] = num[i]
			elif num[j] > num[i]:
				num[i] += 1
				num[j] = num[i]
			else:
				num[i] += 1
				num[j] += 1
			return [i, j, num]
		elif i == j:
			if num[i] < 9:
				num[i] += 1
				return [i, j, num]
			else:
				k = i - 1
				l = i + 1
				num[i] = 0
				while k > 0 and l < n:
					if num[k] != 9:
						num[k] += 1
						num[l] += 1
						break
					num[k] = 0
					num[l] = 0
					k -= 1
					l += 1
			return [i, j, num]
		if num[i] > num[j]:
			num[j] = num[i]
			return [i, j, num]
		else:
			num[j] = num[i]
			return self.mid(num, i + 1, j - 1)
		pass

	def generateNextPalindrome(self, num, n):
		if n == 1:
			if num[0] != 9:
				num[0] += 1
				return num
			else:
				return [1, 1]
		i = 0
		j = n - 1
		c = 0
		while i <= j:
			if num[i] > num[j]:
				num[j] = num[i]
				j -= 1
				i += 1
				c = 1
			elif num[i] < num[j]:
				if i + 1 == j:
					if num[j] < num[i]:
						num[j] = num[i]
					elif num[j] > num[i]:
						num[i] += 1
						num[j] = num[i]
					else:
						num[i] += 1
						num[j] += 1
					return num
				num[j] = num[i]
				x = self.mid(num, i + 1, j - 1)
				i = x[0] + 1
				j = x[1] - 1
				num = x[2]
				c = 1
			else:
				j -= 1
				i += 1
		if num[0] == 0:
			num[0] = 1
			num.append(1)
		if c == 0:
			if num[0] == 9:
				num = [0] * n
				num[0] = 1
				num.append(1)
			elif n % 2 == 0:
				num[n // 2] += 1
				num[n // 2 + 1] += 1
			else:
				num[n // 2] += 1
		return num
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		num = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.generateNextPalindrome(num, n)
		for x in ans:
			print(x, end=' ')
		print()
		tc = tc - 1


def palindrome(num):
	return num == num[::-1]

def add_1(num):
	return str(int(num) + 1)

class Solution:

	def generateNextPalindrome(self, num, n):
		a = ''.join((str(x) for x in num))
		if palindrome(a):
			a = add_1(a)
		n = len(a)
		if n == 1:
			num[0] += 1
			return num
		if n % 2 == 1:
			left = a[:n // 2]
			mid = a[n // 2]
			right = a[n // 2 + 1:]
			if int(left[::-1]) > int(right):
				return list(left + mid + left[::-1])
			else:
				left += mid
				left = add_1(left)
				return list(left + left[::-1][1:])
		else:
			left = a[:n // 2]
			right = a[n // 2:]
			if int(left[::-1]) > int(right):
				return list(left + left[::-1])
			else:
				left = add_1(left)
				return list(left + left[::-1])
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		num = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.generateNextPalindrome(num, n)
		for x in ans:
			print(x, end=' ')
		print()
		tc = tc - 1


class Solution:

	def generateNextPalindrome(self, num, n):
		ans = num.copy()
		if n % 2 == 0 and n > 1:
			i = (n - 1) // 2
			m = i
			while i >= 0:
				if num[i] == num[n - 1 - i]:
					i -= 1
				elif num[i] < num[n - 1 - i]:
					num[m] += 1
					break
				else:
					num[n - 1 - i] = num[i]
					break
			for i in range(n // 2, n):
				num[i] = num[n - 1 - i]
		elif n % 2 != 0 and n > 1:
			flag = 0
			for e in num:
				if e != 9:
					flag = 1
					break
			if flag == 1:
				i = (n - 2) // 2
				m = (n - 1) // 2
				while i >= 0:
					if num[i] == num[n - 1 - i]:
						i -= 1
					elif num[i] < num[n - 1 - i]:
						num[m] += 1
						while num[m] == 10:
							num[m] = 0
							num[m - 1] += 1
							m -= 1
						break
					else:
						num[n - 1 - i] = num[i]
						break
				for i in range(m + 1, n):
					num[i] = num[n - 1 - i]
			else:
				lst = [1]
				for i in range(n - 1):
					lst.append(0)
				lst.append(1)
				num = lst
		else:
			num[0] += 1
			if num[0] == 10:
				num = [1, 1]
		if num == ans:
			m = n // 2
			num[m] += 1
			while num[m] == 10:
				num[m] = 0
				num[m - 1] += 1
				num[n - 2 - m] += 1
				m -= 1
		return num


class Solution:

	def generateNextPalindrome(self, arr, n):
		if n == 1:
			if arr[0] == 9:
				return [1, 1]
			arr[0] += 1
			return arr
		num = []
		for i in range(n):
			num.append(arr[i])
		mid = n // 2
		leftSmaller = False
		i = mid - 1
		j = mid + 1 if n % 2 else mid
		while i >= 0 and num[i] == num[j]:
			i -= 1
			j += 1
		if i < 0 or num[i] < num[j]:
			leftSmaller = True
		while i >= 0:
			num[j] = num[i]
			j += 1
			i -= 1
		if leftSmaller:
			carry = 1
			i = mid - 1
			if n % 2 == 1:
				num[mid] += carry
				carry = num[mid] // 10
				num[mid] %= 10
				j = mid + 1
			else:
				j = mid
			while i >= 0:
				num[i] += carry
				carry = num[i] // 10
				num[i] %= 10
				num[j] = num[i]
				j += 1
				i -= 1
		return num


class Solution:

	def generateNextPalindrome(self, l, n):
		if n == 1:
			if l[0] < 9:
				l[0] += 1
				return l
			else:
				return [1, 1]
		if n % 2 == 0:
			t = l[:]
			i = n // 2
			j = i - 1
			while i < n:
				t[i] = t[j]
				j -= 1
				i += 1
			f = 0
			i = n // 2
			if t > l:
				return t
			i = n // 2 - 1
			while i >= 0 and t[i] == 9:
				i -= 1
			if i < 0:
				t = [1]
				for _ in range(n - 1):
					t.append(0)
				t.append(1)
				return t
			else:
				t[i] += 1
				for j in range(i + 1, n // 2):
					t[j] = 0
				i = n // 2
				j = i - 1
				while i < n:
					t[i] = t[j]
					i += 1
					j -= 1
				return t
		else:
			t = l[:]
			i = n // 2
			j = i - 1
			i += 1
			while i < n:
				t[i] = t[j]
				j -= 1
				i += 1
			f = 0
			i = n // 2 + 1
			if t > l:
				return t
			i = n // 2
			while i >= 0 and t[i] == 9:
				i -= 1
			if i < 0:
				t = [1]
				for _ in range(n - 1):
					t.append(0)
				t.append(1)
				return t
			else:
				t[i] += 1
				for j in range(i + 1, n // 2 + 1):
					t[j] = 0
				i = n // 2
				j = i - 1
				i += 1
				while i < n:
					t[i] = t[j]
					i += 1
					j -= 1
				return t


class Solution:

	def my(self, N):
		le = len(N)
		if le % 2 == 0:
			i = le // 2 - 1
			j = le // 2
			carry = 1
			while i >= 0 and j < le:
				x = N[i]
				N[i] = N[j] = (x + carry) % 10
				carry = (x + carry) // 10
				i -= 1
				j += 1
		else:
			i = le // 2
			j = le // 2
			carry = 1
			while i >= 0 and j < le:
				x = N[i]
				N[i] = N[j] = (x + carry) % 10
				carry = (x + carry) // 10
				i -= 1
				j += 1
		return N

	def myl(self, N):
		le = len(N)
		x = N[:]
		if le % 2 == 0:
			i = le // 2 - 1
			j = le // 2
			while i >= 0 and j < le:
				x[j] = x[i]
				i -= 1
				j += 1
		else:
			i = le // 2
			j = le // 2
			carry = 1
			while i >= 0 and j < le:
				x[j] = x[i]
				i -= 1
				j += 1
		return x

	def solve(self, N):
		le = len(N)
		if le == 1:
			if N != '9':
				return str(int(N) + 1)
		if N == '9' * le:
			return '1' + '0' * (le - 1) + '1'
		res = list(N)
		if res == res[::-1]:
			return self.my(res)
		else:
			x = self.myl(res)
			if x > ''.join(res):
				return x
			return self.my(res)

	def generateNextPalindrome(self, N, le):
		if le == 1:
			if num != [9]:
				return [num[0] + 1]
		if N == [9] * le:
			return [1] + [0] * (le - 1) + [1]
		if N == N[::-1]:
			return self.my(N)
		else:
			x = self.myl(N)
			if x > N:
				return x
			return self.my(x)


class Solution:

	def generateNextPalindrome(self, num, n):
		if n % 2 == 0:
			left = n // 2 - 1
			right = n // 2
		else:
			left = n // 2 - 1
			right = n // 2 + 1
		flag = 0
		c = 0
		while left >= 0 and right < n:
			if num[left] == num[right]:
				left -= 1
				right += 1
			elif num[left] > num[right]:
				c += 1
				num[right] = num[left]
				if c == 1:
					flag = 1
				left -= 1
				right += 1
			else:
				c += 1
				num[right] = num[left]
				left -= 1
				right += 1
		if flag == 1:
			return num
		else:
			if n % 2 == 0:
				if num[n // 2] != 9:
					num[n // 2] += 1
					num[n // 2 - 1] += 1
				else:
					l = n // 2 - 1
					r = n // 2
					while l >= 0 and r < n:
						if num[l] != 9:
							num[l] += 1
							num[r] += 1
							break
						num[l] = 0
						num[r] = 0
						l -= 1
						r += 1
					if l < 0:
						num[0] = 1
						num.append(1)
			elif num[n // 2] != 9:
				num[n // 2] += 1
			else:
				num[n // 2] = 0
				l = n // 2 - 1
				r = n // 2 + 1
				while l >= 0 and r < n:
					if num[l] != 9:
						num[l] += 1
						num[r] += 1
						break
					num[l] = 0
					num[r] = 0
					l -= 1
					r += 1
				if l < 0:
					num[0] = 1
					num.append(1)
			return num


class Solution:

	def AreAll9s(self, num, n):
		for i in range(0, n):
			if num[i] != 9:
				return 0
		return 1

	def ispal(self, num, n):
		i = 0
		while i <= n // 2:
			if num[i] != num[n - i - 1]:
				return 0
			i = i + 1
		return 1

	def generateNextPalindrome(self, num, n):
		lst = []
		if self.AreAll9s(num, n) == 1:
			lst.append(1)
			for i in range(1, n):
				lst.append(0)
			lst.append(1)
		elif self.ispal(num, n) == 1:
			m = n // 2
			j = m
			c = 1
			while j >= 0:
				num[j] = num[j] + c
				c = num[j] // 10
				num[j] = num[j] % 10
				j = j - 1
			i = n // 2
			while i >= 0:
				num[n - i - 1] = num[i]
				i = i - 1
			for i in range(n):
				lst.append(num[i])
		else:
			m = n // 2
			if n % 2 == 0:
				m = m - 1
			else:
				m = m
			c = 0
			i = m
			while i >= 0:
				if num[i] > num[n - i - 1]:
					i = m
					while i >= 0:
						num[n - i - 1] = num[i]
						i = i - 1
					for i in range(n):
						lst.append(num[i])
					return lst
				elif num[i] < num[n - i - 1]:
					j = m
					c = 1
					while j >= i:
						num[j] = num[j] + c
						c = num[j] // 10
						num[j] = num[j] % 10
						j = j - 1
					break
				i = i - 1
			i = m
			while i >= 0:
				num[n - i - 1] = num[i]
				i = i - 1
			for i in range(n):
				lst.append(num[i])
		return lst


class Solution:

	def generateNextPalindrome(self, array, n):
		string = ''.join([str(i) for i in array])
		if int(string) < 9:
			return str(int(string) + 1)
		if self.isPalindrome(string):
			string = self.add_(string)
		if len(string) & 1:
			return self.handleOdd(string)
		else:
			return self.handleEven(string)

	def isPalindrome(self, string):
		return string == string[::-1]

	def add_(self, string):
		return str(int(string) + 1)

	def compare(self, x, y):
		for (i, j) in zip(x, y):
			if int(i) > int(j):
				return 1
			elif int(i) < int(j):
				return -1
			else:
				continue
		return 0

	def handleOdd(self, string):
		nHalf = len(string) // 2
		left = string[:nHalf]
		mid = string[nHalf]
		right = string[nHalf + 1:]
		if self.compare(left[::-1], right) == 1:
			return left + mid + left[::-1]
		else:
			left += mid
			left = self.add_(left)
			return left + left[::-1][1:]

	def handleEven(self, string):
		nHalf = len(string) // 2
		left = string[:nHalf]
		right = string[nHalf:]
		if self.compare(left[::-1], right) == 1:
			return left + left[::-1]
		else:
			left = self.add_(left)
			return left + left[::-1]


class Solution:

	def generateNextPalindrome(self, num, n):
		if n == 1:
			if num[0] == 9:
				return str(11)
			return str(num[0] + 1)

		def is_palindrome(a):
			return a == a[::-1]

		def add_1(a):
			return str(int(a) + 1)

		def compare(x, y):
			if int(x) > int(y):
				return 1
			elif int(x) < int(y):
				return -1
			else:
				return 0

		def odd_case(a):
			n = len(a)
			left = a[:n // 2]
			mid = a[n // 2]
			right = a[n // 2 + 1:]
			if compare(left[::-1], right) == 1:
				return left + mid + left[::-1]
			else:
				left = left + mid
				left = add_1(left)
				return left + left[::-1][1:]

		def even_case(a):
			n = len(a)
			left = a[:n // 2]
			right = a[n // 2:]
			if compare(left[::-1], right) == 1:
				return left + left[::-1]
			else:
				left = add_1(left)
				return left + left[::-1]

		def solve(a):
			if is_palindrome(a):
				a = add_1(a)
			if len(a) & 1:
				return odd_case(a)
			else:
				return even_case(a)
		s = ''
		for i in num:
			s += str(i)
		ans = solve(s)
		return ans


class Solution:

	def generateNextPalindrome(self, num, n):
		if n % 2 == 0:
			x = n // 2 - 1
			y = x + 1
			if num[x] == num[y]:
				while x > 0 and y < n - 1:
					if num[x] != num[y]:
						break
					x -= 1
					y += 1
			if x >= 0 and y < n:
				if num[x] > num[y]:
					x = n // 2 - 1
					y = x + 1
					for i in range(0, n // 2):
						num[y + i] = num[x - i]
				else:
					x = n // 2 - 1
					y = x + 1
					j = 0
					while j <= x:
						k = (num[x - j] + 1) % 10
						num[x - j] = k
						if k != 0:
							break
						j += 1
					for i in range(0, n // 2):
						num[y + i] = num[x - i]
		elif n >= 3:
			z = n // 2
			x = z - 1
			y = z + 1
			if num[x] == num[y]:
				while x > 0 and y < n - 1:
					if num[x] != num[y]:
						break
					x -= 1
					y += 1
			if x >= 0 and y < n:
				if num[x] > num[y]:
					for i in range(1, n // 2 + 1):
						num[z + i] = num[z - i]
				else:
					j = 0
					while j <= z:
						k = (num[z - j] + 1) % 10
						num[z - j] = k
						if k != 0:
							break
						j += 1
					for i in range(1, n // 2 + 1):
						num[z + i] = num[z - i]
		elif (num[0] + 1) % 10 != 0:
			num[0] = num[0] + 1
		else:
			num[0] = 1
			num.append(1)
		return num


class Solution:

	def generateNextPalindrome(self, num, n):

		def makepalindromic(nums, n):
			nums = nums[:]
			ed = n - 1
			i = 0
			while i < n // 2:
				nums[ed - i] = nums[i]
				i += 1
			return nums
		if n == 1 and num[0] == 9:
			return (1, 1)
		st2 = makepalindromic(num, n)
		if st2 > num:
			return st2
		if n & 1:
			middle = n // 2
			while middle > 0 and num[middle] + 1 == 10:
				num[middle] = 0
				middle -= 1
			if middle >= 0 and num[middle] + 1 < 10:
				num[middle] += 1
			else:
				num[0] = 0
				num = [1] + num
				n += 1
			return makepalindromic(num, n)
		else:
			middle = n // 2 - 1
			while middle > 0 and num[middle] + 1 == 10:
				num[middle] = 0
				middle -= 1
			if middle >= 0 and num[middle] + 1 < 10:
				num[middle] += 1
			else:
				num[0] = 0
				num = [1] + num
				n += 1
			return makepalindromic(num, n)


class Solution:

	def generateNextPalindrome(self, num, n):
		i = 0
		j = n - 1
		all_9 = True
		while i <= j:
			if num[i] == num[j] and num[i] == 9:
				i += 1
				j -= 1
			else:
				all_9 = False
				break
		if all_9:
			new_num = [0] * (n + 1)
			new_num[0] = 1
			new_num[-1] = 1
			return new_num
		carry = 1
		i = 0
		j = n - 1
		new_num = [0] * n
		while i <= j:
			(new_num[i], new_num[j]) = (num[i], num[i])
			if new_num[j] > num[j]:
				carry = 0
			elif new_num[j] < num[j]:
				carry = 1
			i += 1
			j -= 1
		if n % 2 == 0:
			(i, j) = (n // 2 - 1, n // 2)
		else:
			(i, j) = (n // 2, n // 2)
		while i > -1 and carry == 1:
			new_digit = new_num[i] + 1
			new_num[i] = new_digit % 10
			new_num[j] = new_digit % 10
			carry = new_digit // 10
			i -= 1
			j += 1
		return new_num


class Solution:

	def generateNextPalindrome(self, num, n):
		b = False
		if len(num) % 2 == 0:
			b = True
			num.insert(len(num) // 2, 9)
		start = 0
		end = len(num) - 1
		b1 = False
		while start < end:
			if num[end] < num[start] or (num[end] == num[start] and b1):
				b1 = True
			else:
				b1 = False
			num[end] = num[start]
			start += 1
			end -= 1
		carry = 0
		if not b1:
			num[start] += 1
			if num[start] <= 9:
				if b:
					num.pop(len(num) // 2)
				return num
			carry = num[start] // 10
			num[start] %= 10
			start -= 1
			end += 1
			while start >= 0:
				num[start] += carry
				carry = num[start] // 10
				num[start] %= 10
				num[end] = num[start]
				end += 1
				start -= 1
		if b:
			num.pop(len(num) // 2)
		if carry == 1:
			num.append(1)
			num[0] = 1
		return num


class Solution:

	def generateNextPalindrome(self, num, n):
		for i in range(n):
			num[i] = str(num[i])
		input_str = ''.join(num)
		output_str = ''
		if n % 2 == 0:
			new = input_str[:n // 2] + input_str[:n // 2][::-1]
			if new > input_str:
				output_str = new
			else:
				left = str(int(input_str[:n // 2]) + 1)
				if len(left) == len(input_str[:n // 2]):
					output_str = left + left[::-1]
				else:
					output_str = '1' + '0' * (len(new) - 1) + '1'
		else:
			new = input_str[:n // 2 + 1] + input_str[:n // 2][::-1]
			if new > input_str:
				output_str = new
			else:
				left = str(int(input_str[:n // 2 + 1]) + 1)
				if len(left) == len(input_str[:n // 2 + 1]):
					output_str = left + left[:-1][::-1]
				else:
					output_str = '1' + '0' * (len(new) - 1) + '1'
		output = []
		for j in output_str:
			output.append(int(j))
		return output


class Solution:

	def generateNextPalindrome(self, num, n):
		if n == 1:
			if num[0] < 9:
				return [num[0] + 1]
			elif num[0] < 11:
				return [1, 1]
		if 10 ** n - 1 == n:
			return [n + 2]

		def solve():
			s = ''
			for i in num:
				s += str(i)
			if n % 2 == 0:
				left = s[:n // 2]
				right = s[n // 2:]
				if int(left[::-1]) > int(right):
					return left + left[::-1]
				else:
					left = str(int(left) + 1)
					return left + left[::-1]
			else:
				left = s[:n // 2]
				right = s[n // 2 + 1:]
				mid = s[n // 2]
				if int(left[::-1]) > int(right):
					return left + mid + left[::-1]
				elif mid == '9':
					left = str(int(left) + 1)
					mid = '0'
					return left + mid + left[::-1]
				else:
					mid = str(int(mid) + 1)
					return left + mid + left[::-1]
		x = solve()
		res = []
		for i in x:
			res.append(int(i))
		return res


class Solution:

	def generateNextPalindrome(self, num, n):
		if num.count(9) == n:
			res = [0] * (n - 1)
			res.append(1)
			res.insert(0, 1)
			return res
		l1 = []
		for i in range(len(num)):
			l1.append(num[i])
		i = 0
		j = n - 1
		c = 0
		a = 0
		while i < j:
			if num[i] < num[j]:
				c = 1
				num[j] = num[i]
			elif num[i] > num[j]:
				c = 0
				num[j] = num[i]
			else:
				a += 1
			i += 1
			j -= 1
		if n % 2 == 0:
			if a == n // 2 + 1:
				a = n
		elif a == n // 2:
			a = n
		if c or a == n:
			if n % 2 == 0:
				m = n // 2 - 1
			else:
				m = n // 2
			if num[m] + 1 > 9:
				while num[m] + 1 > 9:
					num[m] = 0
					m = m - 1
				num[m] = num[m] + 1
			else:
				num[m] = num[m] + 1
			i = 0
			j = n - 1
			while i < j:
				num[j] = num[i]
				i += 1
				j -= 1
			return num
		else:
			return num


class Solution:

	def generateNextPalindrome(self, num, n):
		if num.count(9) == n:
			p = []
			p.append(1)
			for i in range(n - 1):
				p.append(0)
			p.append(1)
			return p
		elif n % 2 != 0:
			p = [0 for i in range(n)]
			for i in range(n // 2):
				p[i] = num[i]
				p[-(i + 1)] = num[i]
			p[n // 2] = num[n // 2]
			chang = 0
			unchang = 0
			for i in range(n // 2, n):
				if num[i] == p[i]:
					continue
				elif num[i] > p[i]:
					unchang = 1
					break
				else:
					chang = 1
					break
			if chang > unchang:
				return p
			elif num[n // 2] != 9:
				p[n // 2] = num[n // 2] + 1
				return p
			else:
				i = n // 2
				j = n // 2
				p[i] = 0
				while p[i - 1] + 1 == 10:
					p[i - 1] = 0
					p[j + 1] = 0
					i -= 1
					j += 1
				p[i - 1] += 1
				p[j + 1] += 1
				return p
		else:
			p = [0 for i in range(n)]
			for i in range(n // 2):
				p[i] = num[i]
				p[-(i + 1)] = num[i]
			chang = 0
			unchang = 0
			for i in range(n // 2, n):
				if num[i] == p[i]:
					continue
				elif num[i] > p[i]:
					unchang = 1
					break
				else:
					chang = 1
					break
			if chang > unchang:
				return p
			elif num[n // 2 - 1] != 9:
				p[n // 2] = num[n // 2 - 1] + 1
				p[n // 2 - 1] = num[n // 2 - 1] + 1
				return p
			else:
				i = n // 2 - 1
				j = n // 2
				p[i] = 0
				p[j] = 0
				while p[i - 1] + 1 == 10:
					p[i - 1] = 0
					p[j + 1] = 0
					i -= 1
					j += 1
				p[i - 1] += 1
				p[j + 1] += 1
				return p


class Solution:

	def solve(self, num, n):
		if n % 2 != 0 and num[n // 2] != 9:
			num[n // 2] += 1
			return num
		elif n % 2 == 0 and num[n // 2] != 9:
			num[n // 2] += 1
			num[n // 2 - 1] += 1
			return num
		elif num[n // 2] == 9:
			if n % 2 != 0:
				num[n // 2] = 0
				i = n // 2 - 1
				j = n // 2 + 1
				car = 1
			else:
				i = n // 2 - 1
				j = n // 2
				car = 1
			while i >= 0 and j < n and (car == 1):
				if num[i] != 9:
					num[i] += 1
					num[j] += 1
					i = i - 1
					j = j + 1
					car = 0
				else:
					num[i] = 0
					num[j] = 0
					i = i - 1
					j += 1
			return num

	def generateNextPalindrome(self, num, n):
		if num == num[::-1]:
			if num.count(9) == n:
				ans = [1]
				for i in range(n - 1):
					ans.append(0)
				ans.append(1)
				return ans
			else:
				return self.solve(num, n)
		else:
			i = 0
			j = n - 1
			small = False
			while i < j:
				if num[j] > num[i]:
					small = True
				elif num[j] < num[i]:
					small = False
				num[j] = num[i]
				i = i + 1
				j = j - 1
			if small == False:
				return num
			else:
				return self.solve(num, n)


class Solution:

	def generateNextPalindrome(self, num, n):
		if n == 1:
			if num[0] < 9:
				return [num[0] + 1]
			elif num[0] == 9:
				return [1, 1]
		val = ''
		for i in range(n):
			val += str(num[i])
		v = val[:len(val) // 2]
		rv = v[::-1]
		if n % 2 == 0:
			ans = v + rv
		else:
			ans = v + val[len(val) // 2] + rv
		if val >= ans:
			v = 10 ** (n // 2)
			val = str(int(val) // v + 1)
			if n % 2 == 0:
				ans = val + val[::-1]
			else:
				v = val[:-1]
				ans = v + val[-1] + v[::-1]
		return [i for i in ans]


class Solution:

	def isp1GreaterThanp2(self, p1, p2, n):
		count = 0
		for i in range(n):
			if p1[i] < p2[i]:
				return False
			elif p1[i] > p2[i]:
				return True
		return False

	def addOne(self, num, n):
		x = num[n - 1] + 1
		num[n - 1] = x % 10
		carry = x // 10
		for i in range(n - 2, -1, -1):
			x = num[i] + carry
			num[i] = x % 10
			carry = x // 10

	def generateNextPalindrome(self, num, n):
		if num == [9] * n:
			return [1] + [0] * (n - 1) + [1]
		a = num[:n // 2]
		ans = a + a[::-1]
		if n % 2 == 1:
			a = num[:n // 2 + 1]
			ans = a + a[::-1][1:]
		if not self.isp1GreaterThanp2(ans, num, n):
			if n % 2 == 1:
				self.addOne(a, n // 2 + 1)
			else:
				self.addOne(a, n // 2)
			ans = a + a[::-1]
			if n % 2 == 1:
				ans = a + a[::-1][1:]
		return ans


class Solution:

	def generateNextPalindrome(self, a, n):
		if n == 1:
			if a[0] < 9:
				a[0] += 1
				return a
		if a.count(9) == n:
			return [1] + [0] * (n - 1) + [1]
		mid = n // 2
		left = mid - 1
		right = mid + 1
		even = False
		if n % 2 == 0:
			even = True
			a.insert(mid, 9)
		if a == a[::-1]:
			v = mid
			k = mid
			a[v] += 1
			while a[v] == 10:
				a[v] = 0
				a[k + 1] = a[v - 1] = a[v - 1] + 1
				v -= 1
				k += 1
			if even:
				a.pop(mid)
			return a
		change = False
		while left >= 0:
			if a[left] == a[right]:
				left -= 1
				right += 1
				continue
			elif a[left] < a[right]:
				if not change:
					v = mid
					k = mid
					a[v] += 1
					while a[v] == 10:
						a[v] = 0
						a[k + 1] = a[v - 1] = a[v - 1] + 1
						v -= 1
						k += 1
					a[right] = a[left]
					change = True
				else:
					a[right] = a[left]
			else:
				change = True
				a[right] = a[left]
			left -= 1
			right += 1
		if even:
			a.pop(mid)
		return a


class Solution:

	def convert(self, s):
		num = list()
		for i in s:
			num.append(int(i))
		return num

	def checkPalindrome(self, s):
		i = 0
		j = len(s) - 1
		while i < j:
			if s[i] != s[j]:
				return False
			i += 1
			j -= 1
		return True

	def add1(self, s):
		return str(int(s) + 1)

	def compare(self, l, r):
		for (i, j) in zip(l, r):
			if l > r:
				return 1
			elif l < r:
				return -1
			else:
				continue
		return 0

	def odd(self, s):
		n = len(s)
		m = n // 2
		l = s[:m]
		r = s[m + 1:]
		if self.compare(l[::-1], r) == 1:
			st = list(l + s[m] + l[::-1])
		else:
			l += s[m]
			l = self.add1(l)
			st = list(l + l[::-1][1:])
		return self.convert(st)

	def even(self, s):
		n = len(s)
		m = n // 2
		l = s[:m]
		r = s[m:]
		if self.compare(l[::-1], r) == -1:
			l = self.add1(l)
			st = list(l + l[::-1])
		else:
			st = list(l + l[::-1])
		return self.convert(st)

	def generateNextPalindrome(self, num, n):
		A = ''
		for i in range(n):
			A += str(num[i])
		if self.checkPalindrome(A):
			A = self.add1(A)
		if self.checkPalindrome(A):
			return A
		n = len(A)
		if n & 1:
			return self.odd(A)
		else:
			return self.even(A)


class Solution:

	def generateNextPalindrome(self, num, n):
		if n == 1:
			if int(num[0]) < 9:
				return [int(num[0]) + 1]
			else:
				return [1, 1]
		if num == num[::-1]:
			if num[-1] == 9:
				num[-1] = 0
				num.append(0)
			else:
				num[-1] += 1
			return self.generateNextPalindrome(num, len(num))
		ans = []
		temp = []
		odd = True
		if n % 2 == 0:
			odd = False
		else:
			odd_value = num[n // 2]
		for i in range(n // 2):
			ans.append(str(num[i]))
		if odd:
			ans.append(str(num[n // 2]))
			num = num[n // 2 + 1:]
		else:
			num = num[n // 2:]
		flg = False
		xx = len(ans) - 1
		if odd:
			xx -= 1
		for i in range(len(num)):
			if flg or int(ans[xx - i]) > int(num[i]):
				flg = True
				temp.append(ans[xx - i])
			elif int(ans[xx - i]) < int(num[i]):
				x = int(''.join(ans)) + 1
				if odd:
					return str(x) + str(x)[::-1][1:]
				return str(x) + str(x)[::-1]
			else:
				temp.append(ans[xx - i])
		if odd:
			return ans + temp
		return ans + temp


class Solution:

	def generateNextPalindrome(self, num, n):
		if num[0] == 9 and n == 1:
			return [1, 1]
		if n == 1:
			return [num[0] + 1]
		if num.count(num[0]) == n:
			l = []
			for i in range(n - 1):
				l.append(0)
			l.insert(1, 0)
			l.append(0)
		(i, j) = (0, n - 1)
		x = 0
		s1 = False
		while i <= j:
			if num[i] > num[j]:
				s1 = False
				num[j] = num[i]
			elif num[i] < num[j]:
				s1 = True
				num[j] = num[i]
			else:
				x = x + 1
			i += 1
			j -= 1
		if n % 2 != 0:
			if x == n // 2 + 1:
				x = n
		elif x == n // 2:
			x = n
		if s1 or x == n:
			if n % 2 != 0:
				i = n // 2
			else:
				i = n // 2 - 1
			while True:
				if num[i] + 1 == 10:
					num[i] = 0
				else:
					num[i] += 1
					break
				i = i - 1
			i = n // 2
			if n % 2 != 0:
				num[i + 1:] = num[:i][::-1]
			else:
				num[i:] = num[:i][::-1]
		return num


import math

def is_smaller(num, n):
	mid = n // 2
	if n % 2:
		(lptr, rptr) = (mid - 1, mid + 1)
	else:
		(lptr, rptr) = (mid - 1, mid)
	while lptr >= 0:
		if num[lptr] == num[rptr]:
			lptr -= 1
			rptr += 1
		elif num[lptr] < num[rptr]:
			return False
		else:
			return True

class Solution:

	def generateNextPalindrome(self, num, n):
		hn = math.ceil(n / 2) - 1
		carry = False
		if n == 1 and num[0] != 9:
			return [num[0] + 1]
		elif n == 1 and num[0] == 9:
			return [1, 1]
		if is_smaller(num, n):
			if n % 2:
				return num[:hn] + num[-hn - 1::-1]
			else:
				return num[:hn + 1] + num[-hn - 2::-1]
		for i in range(hn, -1, -1):
			if num[i] == 9:
				num[i] = 0
				carry = True
			else:
				num[i] += 1
				carry = False
			if not carry:
				break
		if carry:
			return [1] + [0 for _ in range(n - 1)] + [1]
		if n % 2:
			return num[:hn] + num[-hn - 1::-1]
		else:
			return num[:hn + 1] + num[-hn - 2::-1]


class Solution:

	def split_num(self, num, n):
		left = num[:n // 2]
		if n % 2 != 0:
			mid = [num[n // 2]]
		else:
			mid = []
		if n % 2 != 0:
			right = num[n // 2 + 1:n]
		else:
			right = num[n // 2:n]
		left = ''.join(map(str, left))
		mid = ''.join(map(str, mid))
		right = ''.join(map(str, right))
		return (left, mid, right)

	def generateNextPalindrome(self, num, n):
		(left, mid, right) = self.split_num(num, n)
		if 10 * n - 1 == num[0]:
			output_arr = []
			for i in str(num[0] + 2):
				output_arr.append(int(i))
			return output_arr
		elif n == 1:
			num_str = ''.join(map(str, num))
			return [int(num_str) + 1]
		elif mid == '':
			if not int(left[::-1]) > int(right):
				left = str(int(left) + 1)
			right = left[::-1]
		elif mid != '':
			if not int(left[::-1]) > int(right):
				left_mid = str(int(left + mid) + 1)
				(left, mid) = (left_mid[:-1], left_mid[-1])
			right = left[::-1]
		output_arr = []
		for i in left:
			output_arr.append(int(i))
		for i in mid:
			output_arr.append(int(i))
		for i in right:
			output_arr.append(int(i))
		return output_arr


class Solution:

	def generateNextPalindrome(self, num, n):
		nums = [i for i in num]
		st = list(set(nums))
		if len(st) == 1 and st[0] == 9:
			return [1] + [0] * (len(nums) - 1) + [1]
		(left, right) = (0, len(nums) - 1)
		flag = True
		while left < right:
			if nums[left] < nums[right]:
				nums[right] = nums[left]
				flag = True
			elif nums[left] > nums[right]:
				nums[right] = nums[left]
				flag = False
			left += 1
			right -= 1
		if flag:
			if n % 2:
				mid = n // 2
				if nums[mid] != 9:
					nums[mid] += 1
				else:
					(left, right) = (mid - 1, mid + 1)
					nums[mid] = 0
					while left >= 1 and right < n - 1 and (nums[left] == 9) and (nums[right] == 9):
						nums[left] = nums[right] = 0
						left -= 1
						right += 1
					nums[left] = nums[right] = nums[left] + 1
			else:
				mid = n // 2
				(left, right) = (mid - 1, mid)
				if nums[left] == nums[right] and nums[left] != 9:
					nums[left] = nums[right] = nums[right] + 1
				else:
					while left > 0 and right < n - 1 and (nums[left] == nums[right] == 9):
						nums[left] = nums[right] = 0
						left -= 1
						right += 1
					nums[left] = nums[right] = nums[left] + 1
		return nums


class Solution:

	def generateNextPalindrome(self, num, n):
		if all([digit == 9 for digit in num]):
			return list(map(int, str(10 ** n + 1)))
		middle = n // 2
		left = middle - 1
		right = middle if n % 2 == 0 else middle + 1
		while left >= 0:
			if num[left] != num[right]:
				break
			left -= 1
			right += 1
		if left == -1 or num[left] < num[right]:
			left = middle - 1 if n % 2 == 0 else middle
			while True:
				num[left] += 1
				carry = num[left] // 10
				num[left] %= 10
				if carry == 0:
					break
				left -= 1
		left = middle - 1
		right = middle if n % 2 == 0 else middle + 1
		while left >= 0:
			num[right] = num[left]
			left -= 1
			right += 1
		return num


def generateNextPalindromeUtil(num, n):
	mid = int(n / 2)
	leftsmaller = False
	i = mid - 1
	j = mid + 1 if n % 2 else mid
	while i >= 0 and num[i] == num[j]:
		i -= 1
		j += 1
	if i < 0 or num[i] < num[j]:
		leftsmaller = True
	while i >= 0:
		num[j] = num[i]
		j += 1
		i -= 1
	if leftsmaller == True:
		carry = 1
		i = mid - 1
		if n % 2 == 1:
			num[mid] += carry
			carry = int(num[mid] / 10)
			num[mid] %= 10
			j = mid + 1
		else:
			j = mid
		while i >= 0:
			num[i] += carry
			carry = int(num[i] / 10)
			num[i] %= 10
			num[j] = num[i]
			j += 1
			i -= 1

def AreAll9s(num, n):
	for i in range(1, n):
		if num[i] != 9:
			return 0
	return 1

def printArray(arr, n):
	for i in range(0, n):
		print(int(arr[i]), end=' ')
	print()

class Solution:

	def generateNextPalindrome(self, num, n):
		if n == 1:
			if num[0] == 9:
				return '11'
			else:
				num[0] = num[0] + 1
		elif n == 2:
			if num[0] < num[1]:
				num[0] = num[0] + 1
				num[1] = num[0]
			else:
				num[1] = num[0]
		elif AreAll9s(num, n) == True:
			num.append('1')
			for i in range(1, n):
				num.append('0')
			num.append('1')
		else:
			generateNextPalindromeUtil(num, n)
		return num


def addOne(s):
	return str(int(s) + 1)

class Solution:

	def generateNextPalindrome(self, num, n):
		(s, length) = ('', n)
		for i in range(n):
			s += str(num[i])
		if s.count('9') == length:
			return '1' + (length - 1) * '0' + '1'
		if length == 1:
			return addOne(s)
		elif length & 1:
			if int(s[length // 2 - 1::-1]) > int(s[length // 2 + 1:]):
				return s[:length // 2 + 1] + s[length // 2 - 1::-1]
			elif s[length // 2] == '9':
				a = addOne(s[:length // 2])
				return a + '0' + a[::-1]
			else:
				return s[:length // 2] + addOne(s[length // 2]) + s[length // 2 - 1::-1]
		elif int(s[length // 2 - 1::-1]) > int(s[length // 2:]):
			return s[:length // 2] + s[length // 2 - 1::-1]
		else:
			a = addOne(s[:length // 2])
			return a + a[::-1]


class Solution:

	def generateNextPalindrome(self, num, n):
		if n == 1:
			if num[0] > 8:
				return [1, 1]
			else:
				num[0] += 1
			return num
		all9s = False
		for i in range(n):
			if num[i] == 9:
				all9s = True
			else:
				all9s = False
				break
		if all9s:
			num[0] = 1
			num[n - 1] = 1
			for i in range(1, n - 1):
				num[i] = 0
			return num
		mid = n // 2
		i = mid - 1
		j = mid + 1 if n % 2 else mid
		leftSmaller = False
		while i >= 0 and num[i] == num[j]:
			i -= 1
			j += 1
		if i < 0 or num[i] < num[j]:
			leftSmaller = True
		while i >= 0:
			num[j] = num[i]
			j += 1
			i -= 1
		if leftSmaller == True:
			i = mid - 1
			carry = 1
			if n % 2 == 1:
				num[mid] += carry
				carry = int(num[mid] // 10)
				num[mid] %= 10
				j = mid + 1
			else:
				j = mid
			while i >= 0:
				num[i] += carry
				carry = int(num[i] // 10)
				num[i] %= 10
				num[j] = num[i]
				j += 1
				i -= 1
		return num


import math

class Solution:

	def generateNextPalindrome(self, num, n):
		i = 0
		j = n - 1
		numm = num.copy()
		while i < j:
			numm[j] = numm[i]
			i += 1
			j -= 1
		num = ''.join([str(i) for i in num])
		numm = ''.join([str(i) for i in numm])
		if numm > num:
			return numm
		else:
			num = num[0:math.ceil(n / 2)]
			numm = str(int(num) + 1)
			if len(numm) > len(num):
				lst = [0] * (n + 1)
				j = n
			else:
				lst = [0] * n
				j = n - 1
			i = 0
			while i <= j:
				lst[i] = numm[i]
				lst[j] = lst[i]
				i += 1
				j -= 1
		return lst


class Solution:

	def checkall9(self, arr):
		for i in range(len(arr)):
			if arr[i] != 9:
				return False
		return True

	def generateNextPalindrome(self, num, n):
		if self.checkall9(num):
			ans = [0] * (n + 1)
			ans[0] = 1
			ans[-1] = 1
			return ans
		mid = int(n / 2)
		leftsmaller = False
		i = mid - 1
		j = mid + 1 if n % 2 else mid
		while i >= 0 and num[i] == num[j]:
			i -= 1
			j += 1
		if i < 0 or num[i] < num[j]:
			leftsmaller = True
		while i >= 0:
			num[j] = num[i]
			j += 1
			i -= 1
		if leftsmaller == True:
			carry = 1
			i = mid - 1
			if n % 2 == 1:
				num[mid] += carry
				carry = int(num[mid] / 10)
				num[mid] %= 10
				j = mid + 1
			else:
				j = mid
			while i >= 0:
				num[i] += carry
				carry = int(num[i] / 10)
				num[i] %= 10
				num[j] = num[i]
				j += 1
				i -= 1
		return num


class Solution:

	def generateNextPalindrome(self, nums, n):
		if len(nums) == 1:
			if nums[0] == 9:
				return [1, 1]
			return [nums[0] + 1]
		s = ''
		for i in nums:
			s = s + str(i)
		if len(s) % 2 != 0:
			x = len(s) // 2
			if s[x] == '9':
				s1 = s[0:x]
				r = s1 + '9' + s1[::-1]
				if r > s:
					return r
				y = int(s1)
				y = y + 1
				y = str(y)
				if len(y) == len(s1):
					return y + '0' + y[::-1]
				return y + y[::-1]
			s1 = s[0:x]
			if s1 + s[x] + s1[::-1] > s:
				return s1 + s[x] + s1[::-1]
			y = int(s[x]) + 1
			y = str(y)
			return s1 + y + s1[::-1]
		if len(s) % 2 == 0:
			x = len(s) // 2
			y = s[:x]
			r = y + y[::-1]
			if r > s:
				return r
			y = int(y)
			y = y + 1
			y = str(y)
			return y + y[::-1]


class Solution:

	def checkAllNines(self, num, n):
		for i in range(n):
			if num[i] != 9:
				return False
		return True

	def generateNextPalindrome(self, num, n):
		if self.checkAllNines(num, n):
			return [1] + [0] * (n - 1) + [1]
		if n % 2:
			i = n // 2 - 1
			j = n // 2 + 1
		else:
			i = n // 2 - 1
			j = n // 2
		while i >= 0 and j < n and (num[i] == num[j]):
			i -= 1
			j += 1
		if i != -1:
			if num[i] > num[j]:
				while i >= 0 and j < n:
					num[j] = num[i]
					i -= 1
					j += 1
				return num
		if n % 2:
			t = num[n // 2] + 1
			ti = n // 2 - 1
		else:
			t = num[n // 2 - 1] + 1
			ti = n // 2 - 2
		car = t // 10
		num[ti + 1] = t % 10
		while car > 0 and ti >= 0:
			t = num[ti] + 1
			car = t // 10
			num[ti] = t % 10
		if n % 2:
			i = n // 2 - 1
			j = n // 2 + 1
		else:
			i = n // 2 - 1
			j = n // 2
		while i >= 0 and j < n:
			num[j] = num[i]
			i -= 1
			j += 1
		return num


class Solution:

	def generateNextPalindrome(self, num, n):
		mid = (n + 1) // 2
		new_num = num[:mid]
		new_num = new_num + new_num[::-1][n % 2:]
		flag = False
		for (i, j) in zip(num, new_num):
			if i > j:
				flag = True
				break
			elif j > i:
				break
		else:
			flag = True
		if flag:
			new_num = num[:mid]
			for i in range(mid - 1, -1, -1):
				new_num[i] = new_num[i] + 1
				if new_num[i] < 10:
					break
				elif i == 0:
					new_num[i] = 1
					n = 2
				else:
					new_num[i] = 0
			new_num = new_num + new_num[::-1][n % 2:]
		return new_num