Given a palindromic number N in the form of string. The task is to find the smallest palindromic number greater than N using the same set of digits as in N.
Example 1:
Input: 
N = "35453"
Output: 
53435
Explanation: Next higher palindromic 
number is 53435.
Example 2:
Input: N = "33"
Output: -1
Explanation: Next higher palindromic number 
does not exist.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function nextPalin() which takes the string N as input parameters and returns the answer, else if no such number exists returns "-1".
Expected Time Complexity: O(|N|log|N|)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ |N| ≤ 10^{5}

Difficulty: MEDIUM
Tags: String algorithms

Data structures

Mathematics
Skill types: Data structures
Expected Time Complexity: O(|N|log|N|)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3



class Solution:

    def nextPalin(self,N):

        #code here

Solutions:
class Solution:

	def nextPalin(self, N):
		n = len(N) // 2
		ns = [int(N[n - 1])]
		i = n - 2
		while i >= 0:
			nn = int(N[i])
			mns = max(ns)
			if nn < mns:
				rn = min(nn + 1, mns)
				while rn not in ns:
					rn += 1
				if rn > mns:
					rn = mns
				ns.remove(rn)
				ns.append(nn)
				ns.sort()
				rs = str(rn) + ''.join([str(nm) for nm in ns])
				N = N[0:i] + rs + N[i + len(rs):len(N) - i - len(ns) - 1] + rs[::-1] + N[len(N) - i:]
				return N
			else:
				ns.append(nn)
				i -= 1
		return -1


class Solution:

	def nextPalin(self, S):
		n = len(S)
		N = list(S)
		mid = n // 2 - 1
		pos = -1
		for i in range(mid, 0, -1):
			if N[i - 1] < N[i]:
				pos = i - 1
				break
		if pos == -1:
			return '-1'
		numPos = -1
		for i in range(pos + 1, mid + 1):
			if N[i] > N[pos]:
				if numPos == -1:
					numPos = i
				elif N[i] < N[numPos]:
					numPos = i
		temp = N[pos]
		N[pos] = N[numPos]
		N[numPos] = temp
		N[pos + 1:mid + 1] = sorted(N[pos + 1:mid + 1])
		i = 0
		j = n - 1
		while i <= mid:
			N[j] = N[i]
			i += 1
			j -= 1
		return ''.join(N)


class Solution:

	def nextPalin(self, N):
		nums = len(N) // 2
		numSet = [int(N[nums - 1])]
		i = nums - 2
		while i >= 0:
			nowNum = int(N[i])
			maxNumSet = max(numSet)
			if nowNum < maxNumSet:
				replaceNum = min(nowNum + 1, maxNumSet)
				while replaceNum not in numSet:
					replaceNum += 1
				if replaceNum > maxNumSet:
					replaceNum = maxNumSet
				numSet.remove(replaceNum)
				numSet.append(nowNum)
				numSet = sorted(numSet)
				replaceStr = str(replaceNum) + ''.join([str(num) for num in numSet])
				N = N[0:i] + replaceStr + N[i + len(replaceStr):len(N) - i - len(numSet) - 1] + replaceStr[::-1] + N[len(N) - i:]
				return N
			else:
				numSet.append(nowNum)
				i -= 1
		return -1


class Solution:

	def nextPalin(self, N):
		if len(N) <= 3:
			return -1
		arr1 = list(N)
		n = len(N)
		mid = n // 2 - 1
		pos = -1
		for i in range(mid, 0, -1):
			if arr1[i - 1] < arr1[i]:
				pos = i - 1
				break
		if pos == -1:
			return -1
		numpos = -1
		for j in range(pos + 1, mid + 1):
			if arr1[j] > arr1[pos]:
				if numpos == -1:
					numpos = j
				elif arr1[j] < arr1[numpos]:
					numpos = j
		temp = arr1[pos]
		arr1[pos] = arr1[numpos]
		arr1[numpos] = temp
		arr1[pos + 1:mid + 1] = sorted(arr1[pos + 1:mid + 1])
		a = 0
		b = n - 1
		while a <= b:
			arr1[b] = arr1[a]
			a += 1
			b -= 1
		return ''.join(arr1)


def nextPalin(S):
	S = list(S)
	n = len(S)
	if n <= 3:
		return -1
	mid = n // 2 - 1
	for i in range(mid - 1, -1, -1):
		if S[i] < S[i + 1]:
			break
	if i == 0 and S[i] >= S[i + 1]:
		return -1
	smal = i + 1
	for j in range(i + 2, mid + 1):
		if S[j] > S[i] and S[j] < S[smal]:
			smal = j
	(S[i], S[smal]) = (S[smal], S[i])
	(S[n - i - 1], S[n - smal - 1]) = (S[n - smal - 1], S[n - i - 1])
	S[i + 1:mid + 1] = sorted(S[i + 1:mid + 1])
	if n % 2 == 1:
		S[mid + 2:n - i - 1] = sorted(S[mid + 2:n - i - 1], reverse=True)
	else:
		S[mid + 1:n - i - 1] = sorted(S[mid + 1:n - i - 1], reverse=True)
	return ''.join(S)

class Solution:

	def nextPalin(self, N):
		N = list(N)
		return nextPalin(N)


class Solution:

	def nextPalin(self, s):
		n = len(s)
		odd = [s[n // 2]] if n % 2 == 1 else []
		s = [i for i in s[:n // 2]]
		size = len(s)
		if size > 1:
			i = size - 2
			while i >= 0 and s[i] >= s[i + 1]:
				i -= 1
			if i == -1:
				return -1
			j = size - 1
			while j >= 0 and s[i] >= s[j]:
				j -= 1
			(s[i], s[j]) = (s[j], s[i])
			s = s[:i + 1] + s[i + 1:][::-1]
			s = s + odd + s[::-1]
			return ''.join(s)
		else:
			return -1


class Solution:

	def nextPermutation(self, a, n):
		a = list(map(int, a))
		for i in range(n - 1, 0, -1):
			if a[i] > a[i - 1]:
				idx = i - 1
				break
		else:
			return '-1'
		mine = idx + 1
		for i in range(idx + 1, n):
			if a[i] > a[idx] and a[i] <= a[mine]:
				mine = i
		(a[idx], a[mine]) = (a[mine], a[idx])
		a[idx + 1:] = a[:idx:-1]
		s = [str(i) for i in a]
		res = ''.join(s)
		return res

	def nextPalin(self, n):
		l = len(n)
		mid = l // 2
		x = self.nextPermutation(n[:mid], len(n[:mid]))
		if x == '-1':
			return x
		if l % 2 != 0:
			return x + n[mid] + x[::-1]
		else:
			return x + x[::-1]


class Solution:

	def nextPalin(self, N):
		arr = []
		for i in range(len(N) // 2):
			arr.append(N[i])
		i = len(arr) - 1
		while i >= 1 and arr[i] <= arr[i - 1]:
			i -= 1
		if i <= 0:
			return -1
		j = len(arr) - 1
		while j >= i and arr[j] <= arr[i - 1]:
			j -= 1
		(arr[i - 1], arr[j]) = (arr[j], arr[i - 1])
		sortlist = arr[i:]
		sortlist.sort()
		ans = arr[:i] + sortlist
		if len(N) % 2 == 0:
			res = ''.join(ans)
			return res + res[::-1]
		else:
			res = ''.join(ans)
			return res + N[len(N) // 2] + res[::-1]


class Solution:

	def reverse(self, arr, left, right):
		while left < right:
			(arr[left], arr[right]) = (arr[right], arr[left])
			left += 1
			right -= 1

	def nextPalin(self, N):
		if len(N) <= 3:
			return -1
		n = len(N)
		N = list(N)
		mid = n // 2
		i = mid - 2
		while i >= 0 and N[i] >= N[i + 1]:
			i -= 1
		if i < 0:
			return -1
		j = mid - 1
		while j > i:
			if N[j] > N[i]:
				break
			j -= 1
		(N[i], N[j]) = (N[j], N[i])
		(N[n - i - 1], N[n - j - 1]) = (N[n - j - 1], N[n - i - 1])
		self.reverse(N, i + 1, mid - 1)
		if n & 1 == 1:
			self.reverse(N, mid + 1, n - i - 2)
		else:
			self.reverse(N, mid, n - i - 2)
		N = ''.join(N)
		return N


from collections import OrderedDict

class Solution:

	def nextPalin(self, N):
		n = len(N)
		odd = [N[n // 2]] if n % 2 == 1 else []
		N = [i for i in N[:n // 2]]
		if len(N) > 1:
			i = len(N) - 2
			while i >= 0 and N[i] >= N[i + 1]:
				i -= 1
			if i == -1:
				return '-1'
			j = len(N) - 1
			while j >= 0 and N[i] >= N[j]:
				j -= 1
			(N[i], N[j]) = (N[j], N[i])
			N = N[:i + 1] + N[i + 1:][::-1]
			N = N + odd + N[::-1]
			return ''.join(N)
		else:
			return '-1'


class Solution:

	def nextPalin(self, N):
		n = len(N)
		if n >= 1 and n <= 3:
			return -1
		if n % 2 == 1:
			mid = N[n // 2]
		else:
			mid = ''
		arr = [N[i] for i in range(n // 2)]
		ch = self.nextper(arr)
		if ch == False:
			return -1
		s = self.con(arr)
		arr.reverse()
		return s + mid + self.con(arr)

	def nextper(self, arr):
		i = len(arr) - 2
		while i >= 0 and arr[i] >= arr[i + 1]:
			i -= 1
		if i == -1:
			return False
		j = len(arr) - 1
		while arr[j] <= arr[i]:
			j -= 1
		self.swap(arr, i, j)
		i = i + 1
		j = len(arr) - 1
		while i < j:
			self.swap(arr, i, j)
			i += 1
			j -= 1

	def swap(self, arr, i, j):
		(arr[i], arr[j]) = (arr[j], arr[i])

	def con(self, arr):
		s = ''
		for i in arr:
			s += str(i)
		return s


class Solution:

	def nextPalin(self, N):
		dic = {str(i): i for i in range(0, 10)}
		length = len(N)
		if length <= 3:
			return -1
		fir = N[:length // 2]
		fi = -1
		las = length // 2 - 1
		for i in range(las - 1, -1, -1):
			if dic[fir[i]] < dic[fir[i + 1]]:
				fi = i
				break
		if fi == -1:
			return -1
		for i in range(las, -1, -1):
			if dic[fir[fi]] < dic[fir[i]]:
				tic = fir[:fi] + fir[i] + fir[fi + 1:i] + fir[fi] + fir[i + 1:]
				tic = tic[:fi + 1] + tic[fi + 1:][::-1]
				break
		if length % 2 == 0:
			return tic + tic[::-1]
		else:
			return tic + N[length // 2] + tic[::-1]


class Solution:

	def nextPalin(self, N):
		myStr = N
		n = len(myStr)
		if n <= 3:
			return -1
		else:
			mid = n // 2 - 1
			i = mid
			odd = myStr[mid + 1]
			while i >= 0:
				if myStr[i - 1] < myStr[i]:
					break
				i -= 1
			i -= 1
			if i < 0:
				return -1
			j = i
			maxPos = -1
			while j <= mid:
				if myStr[i] < myStr[j]:
					maxDigit = myStr[j]
					maxPos = j
				j += 1
			first = myStr[0:i]
			second = myStr[i]
			third = myStr[i + 1:maxPos]
			forth = myStr[maxPos]
			fifth = myStr[maxPos + 1:mid + 1]
			myStr = first + forth + third + second + fifth
			myStr = myStr[0:i + 1] + ''.join(sorted(myStr[i + 1:mid + 1]))
			if n % 2 == 0:
				myStr = myStr + myStr[::-1]
			else:
				myStr = myStr[0:mid + 1] + odd + myStr[::-1]
			return myStr


class Solution:

	def nextPalin(self, st):
		n = len(st)
		if n <= 2:
			return -1
		extra = ''
		if n % 2 == 1:
			extra = st[n // 2]
		number = list(st[:n // 2])
		n = n // 2
		if n == 1:
			return -1
		i = n - 1
		while i > 0:
			if number[i - 1] < number[i]:
				break
			i -= 1
		else:
			i += 1
		if i == 1 and number[i] <= number[i - 1]:
			return -1
		x = number[i - 1]
		small = i
		for j in range(i + 1, n):
			if x < number[j] and number[j] < number[small]:
				small = j
		(number[i - 1], number[small]) = (number[small], number[i - 1])
		x = ''.join(number[:i] + sorted(number[i:]))
		return x + extra + x[::-1]


class Solution:

	def nextPalin(self, num):
		n = list(num)

		def reverse(n, i, j):
			while i < j:
				temp = n[i]
				n[i] = n[j]
				n[j] = temp
				i = i + 1
				j = j - 1
		if len(n) <= 3:
			return -1
		mid = len(n) // 2 - 1
		i = mid - 1
		while i >= 0:
			if int(n[i]) < int(n[i + 1]):
				break
			i -= 1
		if i < 0:
			return -1
		smallest = i + 1
		j = i + 2
		while j <= mid:
			if int(n[j]) > int(n[i]) and int(n[j]) <= int(n[smallest]):
				smallest = j
			j += 1
		(n[i], n[smallest]) = (n[smallest], n[i])
		(n[len(n) - i - 1], n[len(n) - smallest - 1]) = (n[len(n) - smallest - 1], n[len(n) - i - 1])
		reverse(n, i + 1, mid)
		if len(n) % 2 == 0:
			reverse(n, mid + 1, len(n) - i - 2)
		else:
			reverse(n, mid + 2, len(n) - i - 2)
		return ''.join(n)


class Solution:

	def nextp(self, N, arr):
		p = 0
		for i in range(N - 1, 0, -1):
			if arr[i - 1] < arr[i]:
				p = i
				break
		if p == 0:
			return '-1'
		k = N - 1
		while arr[p - 1] >= arr[k]:
			k = k - 1
		(arr[p - 1], arr[k]) = (arr[k], arr[p - 1])
		i = p
		k = N - 1
		while i < k:
			(arr[i], arr[k]) = (arr[k], arr[i])
			i += 1
			k -= 1
		return arr

	def nextPalin(self, N):
		n = len(N)
		k = n // 2
		l = []
		for i in range(k):
			l.append(N[i])
		d = self.nextp(k, l)
		if d == '-1':
			return '-1'
		e = ''.join(d)
		if n % 2 == 1:
			return e + N[k] + e[::-1]
		return e + e[::-1]


class Solution:

	def nextPalin(self, N):
		num = list(N)
		N = len(num)
		if N <= 3:
			return -1
		mid = (N >> 1) - 1
		leftpos = -1
		for i in range(mid, 0, -1):
			if num[i - 1] < num[i]:
				leftpos = i - 1
				break
		if leftpos == -1:
			return -1
		rightpos = -1
		for i in range(leftpos + 1, mid + 1):
			if num[i] > num[leftpos]:
				if rightpos == -1:
					rightpos = i
				elif num[i] < num[rightpos]:
					rightpos = i
		(num[leftpos], num[rightpos]) = (num[rightpos], num[leftpos])
		num[leftpos + 1:mid + 1] = sorted(num[leftpos + 1:mid + 1])
		i = 0
		j = N - 1
		while i <= mid:
			num[j] = num[i]
			i += 1
			j -= 1
		return ''.join(num)


class Solution:

	def nextPalin(self, number):
		mid = len(number) // 2
		arr = [int(number[i]) for i in range(mid)]
		idx1 = -1
		for i in range(len(arr) - 1, 0, -1):
			if arr[i] > arr[i - 1]:
				idx1 = i - 1
				break
		if idx1 == -1:
			return -1
		idx2 = 0
		for i in range(len(arr) - 1, -1, -1):
			if arr[i] > arr[idx1]:
				idx2 = i
				break
		(arr[idx1], arr[idx2]) = (arr[idx2], arr[idx1])
		arr[idx1 + 1:] = sorted(arr[idx1 + 1:])
		if len(number) % 2 == 0:
			arr = arr + arr[::-1]
		else:
			arr = arr + [number[mid]] + arr[::-1]
		arr = [str(i) for i in arr]
		return ''.join(arr)


class Solution:

	def nextHigher(self, s, slen):
		(changeidx, nextidx) = (-1, -1)
		for i in range(slen - 2, -1, -1):
			if s[i] < s[i + 1]:
				changeidx = i
				break
		if changeidx < 0:
			return '-1'
		for i in range(slen - 1, changeidx, -1):
			if s[i] > s[changeidx]:
				nextidx = i
				break
		(s[changeidx], s[nextidx]) = (s[nextidx], s[changeidx])
		return ''.join(s[:changeidx + 1] + s[changeidx + 1:][::-1])

	def nextPalin(self, N):
		(i, nlen) = (0, len(N))
		if nlen <= 3:
			return -1
		mid = nlen // 2
		firstHalf = N[:mid]
		middle = N[mid] if nlen % 2 == 1 else ''
		ans = self.nextHigher(list(firstHalf), mid)
		if ans != '-1':
			return ans + middle + ans[::-1]
		return '-1'


def nextPerm(string):
	n = len(string)
	string = list(string)
	pos = -1
	for i in range(n - 2, -1, -1):
		if int(string[i]) < int(string[i + 1]):
			pos = i
			val = int(string[i])
			break
	if pos == -1:
		return ''.join(string)
	for i in range(n - 1, -1, -1):
		if int(string[i]) > val:
			pos1 = i
			break
	(string[pos], string[pos1]) = (string[pos1], string[pos])
	string = string[:pos + 1] + string[n - 1:pos:-1]
	string = ''.join(string)
	return string

class Solution:

	def nextPalin(self, N):
		string = N
		n = len(string)
		middle_val = -1
		if n % 2 != 0:
			middle_val = string[n // 2]
		new_string = nextPerm(string[:n // 2])
		if middle_val != -1:
			next_string = new_string + middle_val + new_string[::-1]
		else:
			next_string = new_string + new_string[::-1]
		if string == next_string:
			return -1
		return next_string
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		s = input()
		solObj = Solution()
		print(solObj.nextPalin(s))


class Solution:

	def nextPalin(self, number):
		mid = len(number) // 2
		arr = [int(number[i]) for i in range(mid)]
		idx1 = -1
		for i in range(mid - 1, 0, -1):
			if arr[i] > arr[i - 1]:
				idx1 = i - 1
				break
		if idx1 == -1:
			return -1
		idx2 = 0
		for i in range(mid - 1, 0, -1):
			if arr[i] > arr[idx1]:
				idx2 = i
				break
		(arr[idx1], arr[idx2]) = (arr[idx2], arr[idx1])
		arr[idx1 + 1:] = sorted(arr[idx1 + 1:])
		if len(number) % 2 == 0:
			arr = arr + arr[::-1]
		else:
			arr = arr + [number[mid]] + arr[::-1]
		arr = [str(i) for i in arr]
		return ''.join(arr)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		s = input()
		solObj = Solution()
		print(solObj.nextPalin(s))


class Solution:

	def nextPalin(self, N):
		nums = len(N) // 2
		numSet = [int(N[nums - 1])]
		i = nums - 2
		while i >= 0:
			nowNum = int(N[i])
			maxNumSet = max(numSet)
			if nowNum < maxNumSet:
				replaceNum = min(nowNum + 1, maxNumSet)
				while replaceNum not in numSet:
					replaceNum += 1
				if replaceNum > maxNumSet:
					replaceNum = maxNumSet
				numSet.remove(replaceNum)
				numSet.append(nowNum)
				numSet = sorted(numSet)
				replaceStr = str(replaceNum) + ''.join([str(num) for num in numSet])
				N = N[0:i] + replaceStr + N[i + len(replaceStr):len(N) - i - len(numSet) - 1] + replaceStr[::-1] + N[len(N) - i:]
				return N
			else:
				numSet.append(nowNum)
				i -= 1
		return -1
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		s = input()
		solObj = Solution()
		print(solObj.nextPalin(s))


class Solution:

	def nextPermutation(self, s, slen):
		(changeidx, nextidx) = (-1, -1)
		for i in range(slen - 2, -1, -1):
			if s[i] < s[i + 1]:
				changeidx = i
				break
		if changeidx < 0:
			return '-1'
		for i in range(slen - 1, changeidx, -1):
			if s[i] > s[changeidx]:
				nextidx = i
				break
		(s[changeidx], s[nextidx]) = (s[nextidx], s[changeidx])
		return ''.join(s[:changeidx + 1] + s[changeidx + 1:][::-1])

	def nextPalin(self, N):
		(i, nlen) = (0, len(N))
		if nlen <= 3:
			return -1
		mid = nlen // 2
		firstHalf = N[:mid]
		if nlen % 2 == 0:
			middle = ''
			secondHalf = N[mid:]
		else:
			middle = N[mid]
			secondHalf = N[mid + 1:]
		ans = self.nextPermutation(list(firstHalf), mid)
		if ans != '-1':
			return ans + middle + ans[::-1]
		return '-1'
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		s = input()
		solObj = Solution()
		print(solObj.nextPalin(s))


class Solution:

	def nextPalin(self, N):
		N = list(N)
		n = len(N)
		mid = n // 2 if not n & 1 else n // 2 + 1
		for i in range(mid + 1, n):
			if N[i] < N[i - 1]:
				rep = i - 1
				j = i - 2
				while j >= mid:
					if N[j] > N[i] and N[j] < N[rep]:
						rep = j
					j -= 1
				(N[i], N[rep]) = (N[rep], N[i])
				N = N[:mid] + sorted(N[mid:i])[::-1] + N[i:]
				i = n - 1 - i
				rep = n - 1 - rep
				(N[i], N[rep]) = (N[rep], N[i])
				mid = n - 1 - mid
				N = N[:i + 1] + sorted(N[i + 1:mid + 1]) + N[mid + 1:]
				return ''.join(N)
		return -1
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		s = input()
		solObj = Solution()
		print(solObj.nextPalin(s))


class Solution:

	def nextPalin(self, N):
		x = len(N) // 2
		l = []
		if len(N) % 2 == 1:
			x -= 1
		l.append(N[x])
		if len(N) % 2 == 0:
			x -= 1
		dec = 0
		flag = True
		idx = 0
		for i in range(x - 1, -1, -1):
			if l[x - i - 1] <= N[i]:
				l.append(N[i])
			else:
				dec = N[i]
				idx = i
				flag = False
				break
		if flag:
			return -1
		idx2 = 0
		swap = 0
		for j in range(len(l)):
			if l[j] > dec:
				idx2 = x - j - 1
				swap = l[j]
				l[j] = dec
				break
		temp = []
		for k in range(idx):
			temp.append(N[k])
		temp.append(swap)
		for m in range(len(l)):
			temp.append(l[m])
		ans = ''
		for y in temp:
			ans += y
		if len(N) % 2 == 1:
			ans += N[x + 1]
		for z in range(len(temp) - 1, -1, -1):
			ans += temp[z]
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		s = input()
		solObj = Solution()
		print(solObj.nextPalin(s))


class Solution:

	def nextPalin(self, N):
		n = len(N)
		st = N[:n // 2]
		lt = n // 2 - 1
		st = list(st)
		(st1, st2) = (-1, 0)
		while lt > 0:
			x = lt - 1
			while x > st1:
				if st[x] < st[lt]:
					if st1 == -1 or (st1 != -1 and x > st1):
						(st1, st2) = (x, lt)
					break
				x -= 1
			lt -= 1
		if st1 == -1 and st2 == 0:
			return -1
		(st[st1], st[st2]) = (st[st2], st[st1])
		st = st[:st1 + 1] + sorted(st[st1 + 1:])
		y = ''.join(st)
		if len(N) % 2 == 1:
			return ''.join(st) + N[n // 2] + y[::-1]
		return ''.join(st) + ''.join(st)[::-1]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		s = input()
		solObj = Solution()
		print(solObj.nextPalin(s))


class Solution:

	def nextPalin(self, N):

		def func(arr):
			k = -99999
			arr = list(arr)
			for i in range(len(arr)):
				arr[i] = int(arr[i])
			for i in range(len(arr) - 1, 0, -1):
				if arr[i] > arr[i - 1]:
					k = i - 1
					break
			if k < 0:
				return arr
			else:
				for i in range(len(arr) - 1, k, -1):
					if arr[i] > arr[k]:
						break
				(arr[i], arr[k]) = (arr[k], arr[i])
				arr[k + 1:] = sorted(arr[k + 1:])
				return arr
		a = len(N) // 2
		b = N[:a]
		d = func(b)
		for i in range(len(d)):
			d[i] = str(d[i])
		d = ''.join(d)
		if b == d:
			return -1
		elif len(N) % 2 == 0:
			d = d + d[::-1]
			return d
		else:
			d = d + N[a] + d[::-1]
			return d


def reverse(string, i, j):
	temp = string[i:j + 1]
	rev = temp[::-1]
	string[i:j + 1] = rev

class Solution:

	def nextPalin(self, string: str):
		string = list(string)
		N = len(string)
		if N <= 3:
			return -1
		mid = N // 2 - 1
		i = mid - 1
		while i >= 0:
			if string[i] < string[i + 1]:
				break
			i -= 1
		if i < 0:
			return -1
		smallest = i + 1
		j = i + 2
		while j <= mid:
			if string[j] > string[i] and string[j] <= string[smallest]:
				smallest = j
			j += 1
		temp = string[i]
		string[i] = string[smallest]
		string[smallest] = temp
		temp = string[N - 1 - i]
		string[N - 1 - i] = string[N - 1 - smallest]
		string[N - 1 - smallest] = temp
		reverse(string, i + 1, mid)
		if N % 2 == 0:
			reverse(string, mid + 1, N - i - 2)
		else:
			reverse(string, mid + 2, N - i - 2)
		return ''.join(string)


class Solution:

	def nextPalin(self, N):
		new_str = N[:len(N) // 2]
		arr = list(new_str)
		id1 = -1
		for i in range(len(arr) - 2, -1, -1):
			if arr[i] < arr[i + 1]:
				id1 = i
				break
		if id1 == -1:
			return -1
		for i in range(len(arr) - 1, -1, -1):
			if arr[id1] < arr[i]:
				id2 = i
				break
		(arr[id1], arr[id2]) = (arr[id2], arr[id1])
		arr[id1 + 1:] = arr[-1:id1 - len(arr):-1]
		if len(N) % 2:
			pali = arr + [N[len(N) // 2]] + arr[::-1]
		else:
			pali = arr + arr[::-1]
		return ''.join(pali)


class Solution:

	def nextPalin(self, N):
		a = []
		ans = ''
		f = 0
		for i in range(int(len(N) / 2) - 1, -1, -1):
			a.append(int(N[i]))
			if N[i] > N[i - 1]:
				f = 1
				break
		if f == 0:
			return -1
		i -= 1
		a.sort()
		for j in range(len(a)):
			ans += str(a[j])
		ans = N[i] + ans
		for j in range(1, len(ans)):
			if int(ans[0]) < int(ans[j]):
				ans = ans[j] + ans[1:j] + ans[0] + ans[j + 1:]
				break
		ans = N[:i] + ans
		if len(N) % 2 == 0:
			ans += ans[::-1]
		else:
			ans += N[int(len(N) / 2)] + ans[::-1]
		return ans


class Solution:

	def nextPalin(self, N):
		n = len(N)
		end = n // 2 - 1
		digit_count = [0] * 10
		j = end
		h_res = ''
		r_res = ''
		while j > -1:
			digit = int(N[j])
			high = -1
			for i in range(digit + 1, 10):
				if digit_count[i] > 0:
					high = i
					break
			digit_count[digit] += 1
			if high == -1:
				j -= 1
			else:
				h_res = str(high)
				r_res = str(high)
				digit_count[high] -= 1
				for i in range(10):
					for k in range(digit_count[i]):
						h_res += str(i)
						r_res = str(i) + r_res
				break
		if h_res:
			for k in range(j - 1, -1, -1):
				h_res = N[k] + h_res
				r_res += N[k]
			if n % 2 != 0:
				return h_res + N[n // 2] + r_res
			return h_res + r_res
		return -1


class Solution:

	def nextPalin(self, N):
		if len(N) <= 3:
			return -1
		hs = int(len(N) / 2)
		s = N[:hs]
		idx = None
		for i in range(hs - 2, -1, -1):
			if s[i] < s[i + 1]:
				idx = i
				break
		if idx is None:
			return -1
		(min_val, min_idx) = (None, None)
		for i in range(idx + 1, hs):
			if N[i] > s[idx] and (min_val is None or N[i] < min_val):
				min_val = N[i]
				min_idx = i
		seq = s[:idx] + s[min_idx] + ''.join(sorted(list(s[idx:min_idx] + s[min_idx + 1:hs])))
		if len(N) % 2 == 1:
			return seq + N[hs] + seq[::-1]
		return seq + seq[::-1]


from collections import Counter

class Solution:

	def next_permutation(self, N, arr):
		start = -1
		for i in range(N - 1, 0, -1):
			if arr[i] > arr[i - 1]:
				start = i
				break
		if start == -1:
			return -1
		a = sorted(arr[start:])
		for i in a:
			if arr[start - 1] < i:
				ind = arr.index(i, start, N)
				(arr[start - 1], arr[ind]) = (arr[ind], arr[start - 1])
				break
		a = sorted(arr[start:])
		del arr[start:]
		arr += a
		return ''.join(arr)

	def nextPalin(self, N):
		if len(N) < 3:
			return -1
		dic = Counter(N)
		count = 0
		for i in dic.values():
			if i % 2 != 0:
				count += 1
		if len(N) % 2 == 0 and count > 0 or count > 1:
			return -1
		k = []
		for i in N[:len(N) // 2]:
			k.append(i)
		ans = self.next_permutation(len(k), k)
		if ans == -1:
			return ans
		if len(N) % 2 == 0:
			return ans + ans[::-1]
		else:
			return ans + N[len(N) // 2] + ans[::-1]
		return -1


class Solution:

	def nextPalin(self, a):
		middle_num = a[len(a) // 2]
		n = len(a)
		a = a[:len(a) // 2]
		a = [v for v in a]
		first_dip_index = -1
		for i in reversed(range(1, len(a))):
			if a[i] > a[i - 1]:
				d = i - 1
				first_dip_index = i - 1
				break
		if first_dip_index == -1:
			return '-1'
		just_greater_index = -1
		for i in range(first_dip_index + 1, len(a)):
			if a[i] > a[first_dip_index]:
				just_greater_index = i
			else:
				break
		(a[first_dip_index], a[just_greater_index]) = (a[just_greater_index], a[first_dip_index])
		res = a[:first_dip_index + 1] + a[:first_dip_index:-1]
		second_half = res[::-1]
		if n % 2 == 1:
			res.append(middle_num)
		res.extend(second_half)
		return ''.join(res)


class Solution:

	def getNextHigher(self, arr, value):
		n = len(arr)
		smallest_idx = 0
		for i in range(1, n):
			if arr[i] > value and arr[i] < arr[smallest_idx]:
				smallest_idx = i
		return smallest_idx

	def getNextGretearValue(self, num_arr):
		n = len(num_arr)
		if n == 2:
			if num_arr[0] < num_arr[1]:
				(num_arr[0], num_arr[1]) = (num_arr[1], num_arr[0])
				return num_arr
			else:
				return -1
		swap_pointer = n - 2
		while swap_pointer >= 0:
			if num_arr[swap_pointer] < num_arr[swap_pointer + 1]:
				right_arr = num_arr[swap_pointer + 1:]
				swap_val_idx = swap_pointer + self.getNextHigher(right_arr, num_arr[swap_pointer]) + 1
				(num_arr[swap_pointer], num_arr[swap_val_idx]) = (num_arr[swap_val_idx], num_arr[swap_pointer])
				right_arr = num_arr[swap_pointer + 1:]
				right_arr.sort()
				left_arr = num_arr[:swap_pointer + 1]
				return left_arr + right_arr
			swap_pointer -= 1
		return -1

	def nextPalin(self, N):
		n = len(N)
		mid = n // 2
		midValue = -1
		if n % 2 == 1:
			midValue = int(N[mid])
		left_str = []
		for i in range(mid):
			left_str.append(int(N[i]))
		if len(left_str) == 1:
			return -1
		next_res = self.getNextGretearValue(left_str)
		if next_res == -1:
			return -1
		else:
			res_str = ''
			res_str += ''.join(map(str, next_res))
			if midValue > -1:
				res_str += str(midValue)
			next_res.reverse()
			res_str += ''.join(map(str, next_res))
			return res_str


class Solution:

	def nextPalin(self, N):
		if len(N) <= 3:
			return '-1'
		mid = len(N) // 2
		odd = N[mid] if len(N) % 2 == 1 else ''
		s = N[:mid]
		nums = list(s)
		n = len(nums)
		i = n - 2
		while i >= 0 and nums[i] >= nums[i + 1]:
			i -= 1
		if i < 0:
			return '-1'
		else:
			(l, r) = (i + 1, n - 1)
			while l < r:
				mid = (l + r) // 2 + 1
				if nums[mid] <= nums[i]:
					r = mid - 1
				else:
					l = mid
			(nums[i], nums[l]) = (nums[l], nums[i])
			(l, r) = (i + 1, n - 1)
			while l < r:
				(nums[l], nums[r]) = (nums[r], nums[l])
				l += 1
				r -= 1
			new = ''.join(nums)
			return new + odd + new[::-1]


import sys

class Solution:

	def reverse(self, num, i, j):
		while i < j:
			temp = num[i]
			num[i] = num[j]
			num[j] = temp
			i = i + 1
			j = j - 1

	def nextPalin(self, N):
		maxval = sys.maxsize
		n = len(N)
		smaller = maxval
		smallest = maxval
		if n <= 3:
			return -1
		mid = n // 2 - 1
		a = list(N)
		for i in range(mid, 0, -1):
			if a[i - 1] < a[i]:
				smallest = i - 1
				break
		if smallest == maxval:
			return -1
		smaller = smallest + 1
		for i in range(smallest + 2, mid + 1):
			if a[i] > a[smallest] and a[i] <= a[smaller]:
				smaller = i
		(a[smaller], a[smallest]) = (a[smallest], a[smaller])
		(a[n - 1 - smaller], a[n - 1 - smallest]) = (a[n - 1 - smallest], a[n - 1 - smaller])
		self.reverse(a, smallest + 1, mid)
		if n % 2 == 0:
			self.reverse(a, mid + 1, n - 2 - smallest)
		else:
			self.reverse(a, mid + 2, n - 2 - smallest)
		return ''.join(a)


class Solution:

	def nextgreatestnumber(self, n):
		if len(n) == 1:
			return n
		for i in range(len(n) - 1, 0, -1):
			if n[i] > n[i - 1]:
				break
		if i == 1 and n[i - 1] >= n[i]:
			return n
		m = i - 1
		min1 = i
		for j in range(i + 1, len(n)):
			if n[j] > n[m] and n[j] < n[min1]:
				min1 = j
		(n[m], n[min1]) = (n[min1], n[m])
		i = m + 1
		n = n[:i] + sorted(n[i:])
		return n

	def nextPalin(self, N):
		if len(N) == 1:
			return '-1'
		ls = list(N)
		mid = len(N) // 2
		ls1 = self.nextgreatestnumber(ls[:mid])
		if len(N) % 2 == 0:
			ls = ls1 + ls1[::-1]
		else:
			ls = ls1 + list(ls[mid]) + ls1[::-1]
		s = ''.join(ls)
		if s != N:
			return s
		return '-1'


class Solution:

	def nextPalin(self, N):
		l = len(N)
		if l <= 3:
			return -1
		cntr = l // 2 - 2
		li = list(N)
		s = ''
		flag = 0
		x = li
		z = 0
		mx = -1
		while cntr >= 0:
			mn = int(N[cntr])
			for i in range(cntr + 1, l // 2):
				if flag == 0 and mn < int(N[i]):
					mn = int(N[i])
					z = i
					flag = 1
				elif flag == 1 and mn >= int(N[i]) and (int(N[cntr]) < int(N[i])):
					mn = int(N[i])
					z = i
			if flag == 1:
				(li[cntr], li[z]) = (li[z], li[cntr])
				x = li.copy()
				li = li[:cntr + 1] + sorted(li[cntr + 1:l // 2])
				break
			cntr -= 1
		if flag == 0:
			return -1
		if l % 2 == 0:
			x = li.copy()
			li += reversed(x)
		else:
			x = li.copy()
			li.append(N[l // 2])
			li += reversed(x)
		return ''.join(li)


class Solution:

	def nextPalin(self, N):
		l = []
		strLen = len(N)
		for i in range(strLen // 2):
			l.append(s[i])
		i = len(l) - 2
		while i >= 0:
			if int(l[i]) < int(l[i + 1]):
				break
			i -= 1
		if i < 0:
			return -1
		low = i + 1
		high = len(l) - 1
		while low < high:
			mid = low + (high - low) // 2
			if int(l[mid]) <= int(l[i]):
				high = mid - 1
			elif low == high - 1:
				if int(l[high]) > int(l[i]):
					low += 1
				break
			else:
				low = mid
		(l[i], l[low]) = (l[low], l[i])
		j = len(l) - 1
		i += 1
		while i < j:
			(l[i], l[j]) = (l[j], l[i])
			i += 1
			j -= 1
		if strLen % 2 != 0:
			l.append(N[strLen // 2])
		l = l + l[:strLen // 2][::-1]
		return ''.join(l)


class Solution:

	def nextPalin(self, N):
		N = list(N)
		if len(N) == 1 or len(N) == 2 or len(N) == 3:
			return -1
		floor = len(N) // 2 - 1
		arr = N[:floor + 1]
		for i in range(len(arr) - 1, 0, -1):
			if arr[i - 1] < arr[i]:
				swap = arr[i - 1]
				pos = i - 1
				break
		else:
			return -1
		for i in range(len(arr) - 1, pos, -1):
			if int(swap) < int(arr[i]):
				(arr[pos], arr[i]) = (arr[i], arr[pos])
				break
		arr[pos + 1:] = sorted(arr[pos + 1:])
		if len(N) % 2 == 1:
			res = arr + [N[floor + 1]] + arr[::-1]
		else:
			res = arr + arr[::-1]
		return ''.join(res)


class Solution:

	def nextPalin(self, N):
		final_str = ''
		if len(N) <= 3:
			return -1
		list_ = []
		curr_str = N[:len(N) // 2]
		for i in curr_str:
			list_.append(int(i))

		def find_next(list_):
			val = len(list_)
			k = val - 2
			while k >= 0:
				if list_[k] < list_[k + 1]:
					break
				k -= 1
			if k < 0:
				list_ = list_[::-1]
			else:
				for j in range(val - 1, k, -1):
					if list_[j] > list_[k]:
						(list_[j], list_[k]) = (list_[k], list_[j])
						break
				pm = list_[k + 1:]
				list_[k + 1:] = pm[::-1]
		find_next(list_)
		for i in list_:
			final_str += str(i)
		if N == final_str:
			return -1
		if len(N) % 2 == 1:
			final_str = final_str + N[len(N) // 2] + final_str[::-1]
		else:
			final_str += final_str[::-1]
		if N == final_str:
			return -1
		return final_str


class Solution:

	def reverse(self, num, i, j):
		while i < j:
			temp = num[i]
			num[j] = num[i]
			i = i + 1
			j = j - 1

	def nextPalin(self, N):
		n = len(N)
		num = list(N)
		if len(num) <= 3:
			return -1
		mid = n // 2 - 1
		i = mid - 1
		while i >= 0:
			if num[i] < num[i + 1]:
				break
			i -= 1
		if i < 0:
			return -1
		smallest = i + 1
		j = i + 2
		while j <= mid:
			if num[j] > num[i] and num[j] < num[smallest]:
				smallest = j
			j = j + 1
		temp = num[i]
		num[i] = num[smallest]
		num[smallest] = temp
		temp = num[n - i - 1]
		num[n - i - 1] = num[n - smallest - 1]
		num[n - smallest - 1] = temp
		num[i + 1:mid + 1] = sorted(num[i + 1:mid + 1])
		self.reverse(num, 0, n - 1)
		result = ''.join(num)
		return result


class Solution:

	def nextPalin(self, s):
		r = s
		res = ''
		n = int(len(s) / 2)
		s = r[:n]
		i = n - 1
		while i > 0:
			if int(s[i]) > int(s[i - 1]):
				target = i - 1
				res = s[:i - 1]
				for j in range(n - 1, i - 1, -1):
					if int(s[j]) > int(s[i - 1]):
						res += s[j] + s[n - 1:j:-1] + s[i - 1] + s[j - 1:i - 1:-1]
						break
				break
			i -= 1
		if not res:
			return -1
		res_ = res
		if len(r) & 1:
			res_ += r[n]
		res_ += res[::-1]
		return res_


from collections import deque

class Solution:

	def nextPalin(self, N):
		n = len(N)
		i = n // 2 - 1
		N = list(map(int, list(N)))
		dp = [0] * 10
		m = []
		while i >= 0:
			dp[N[i]] += 1
			for j in range(N[i] + 1, 10):
				if dp[j] > 0:
					dp[j] -= 1
					m = N[:i] + [j]
					for k in range(0, 10):
						for _ in range(dp[k]):
							m.append(k)
					m = m + ([N[n // 2]] if n % 2 else []) + m[::-1]
					m = map(str, m)
					return ''.join(m)
			i -= 1
		return -1


class Solution:

	def nextPalin(self, s):
		n = len(s)
		digits = list(s[:n // 2])
		if len(digits) <= 1:
			return -1
		t = ''
		if n % 2:
			t = s[n // 2]
		i = len(digits) - 1
		j = len(digits) - 1
		while i and digits[i] <= digits[i - 1]:
			i -= 1
		if i == 0:
			return -1
		while digits[j] <= digits[i - 1]:
			j -= 1
		(digits[j], digits[i - 1]) = (digits[i - 1], digits[j])
		digits[i:] = digits[i:][::-1]
		res = ''.join(digits)
		ans = res + t + res[::-1]
		return ans


def find(N):
	list = []
	a = []
	for i in N:
		list.append(int(i))
	if sorted(list)[::-1] == list:
		return -1
	else:
		for i in range(len(N) - 1, 0, -1):
			if list[i - 1] >= list[i]:
				continue
			else:
				for j in range(len(N) - 1, i - 1, -1):
					if list[j] > list[i - 1]:
						temp = list[j]
						list[j] = list[i - 1]
						list[i - 1] = temp
						break
				a = list[:i] + sorted(list[i:])
				break
	s = ''
	for i in a:
		s = s + str(i)
	if len(s) > 0:
		return s
	else:
		return -1

class Solution:

	def nextPalin(self, N):
		if len(str(N)) == 1 or len(str(N)) == 2 or len(str(N)) == 3:
			return -1
		elif len(str(N)) == 4:
			a = str(N)[0]
			b = str(N)[1]
			c = str(N)[2]
			d = str(N)[3]
			if int(b + a + d + c) > int(N):
				return int(b + a + d + c)
			else:
				return -1
		elif len(str(N)) == 5:
			a = str(N)[0]
			b = str(N)[1]
			c = str(N)[2]
			d = str(N)[3]
			e = str(N)[4]
			if int(b + a + c + e + d) > int(N):
				return int(b + a + c + e + d)
			else:
				return -1
		elif len(N) % 2 == 0:
			x = find(N[:len(N) // 2])
			if x == -1:
				return -1
			else:
				return x + x[::-1]
		else:
			x = find(N[:len(N) // 2])
			if x == -1:
				return -1
			else:
				return x + N[len(N) // 2] + x[::-1]


class Solution:

	def nextPalin(self, N):
		(st, n) = (str(N), len(str(N)))
		if n <= 3:
			return '-1'
		half = st[:n // 2]
		half = list(half)
		if self.next_permutation(half):
			half = ''.join(half)
			ans = half
			if n & 1:
				ans += s[n // 2]
			half = half[::-1]
			ans += half
			return ans
		return '-1'

	def next_permutation(self, a):
		for i in reversed(range(len(a) - 1)):
			if a[i] < a[i + 1]:
				break
		else:
			return False
		j = next((j for j in reversed(range(i + 1, len(a))) if a[i] < a[j]))
		(a[i], a[j]) = (a[j], a[i])
		a[i + 1:] = reversed(a[i + 1:])
		return True


class Solution:

	def nextPalin(self, N):

		def swap(string, ind1, ind2):
			list_of_chars = list(string)
			(list_of_chars[ind1], list_of_chars[ind2]) = (list_of_chars[ind2], list_of_chars[ind1])
			orig_string = ''.join(list_of_chars)
			return orig_string
		n = len(N)
		if len(set(N)) == 1:
			return -1
		if n <= 3:
			return -1
		mid = n // 2
		N_orig = N
		N = N_orig[:mid]
		j = mid - 1
		while j - 1 >= 0:
			if int(N[j]) > int(N[j - 1]):
				j -= 1
				break
			j -= 1
		ind1 = j
		if ind1 == 0 and int(N[ind1]) >= int(N[ind1 + 1]):
			return -1
		i = mid - 1
		while i >= 0:
			if int(N[i]) > int(N[ind1]):
				break
			i -= 1
		ind2 = i
		res = swap(N, ind1, ind2)
		res = res[:ind1 + 1] + ''.join(sorted(res[ind1 + 1:]))
		return res + N_orig[mid] + res[::-1] if n & 1 else res + res[::-1]


from collections import Counter

class Solution:

	def nextPalin(self, N):
		arr = list(map(int, N.strip()))
		if len(arr) == 1:
			return -1
		n = len(arr)
		extra = -1
		if n % 2 != 0:
			extra = arr[n // 2]
		temp = arr[:n // 2]
		temp2 = []
		flag = False
		for i in range(n // 2 - 1, -1, -1):
			if temp2:
				temp2.sort()
				for j in range(len(temp2)):
					if temp2[j][0] > temp[i]:
						(temp[i], temp[temp2[j][1]]) = (temp[temp2[j][1]], temp[i])
						flag = True
						break
				if flag:
					break
			temp2.append([arr[i], i])
		if not flag:
			return -1
		temp = temp[:i + 1] + sorted(temp[i + 1:])
		temp2 = temp[:]
		if extra != -1:
			temp.append(extra)
		temp.extend(temp2[::-1])
		return ''.join(map(str, temp))


class Solution:

	def nextPalin(self, n):

		def rev(nums, l, r):
			while l < r:
				(nums[l], nums[r]) = (nums[r], nums[l])
				l += 1
				r -= 1

		def nextGreatestPermutation(nums, l, r):
			i = r - 1
			while i >= 0 and nums[i] >= nums[i + 1]:
				i -= 1
			if i == -1:
				return -1
			j = r
			while j >= 0 and nums[i] >= nums[j]:
				j -= 1
			(nums[i], nums[j]) = (nums[j], nums[i])
			rev(nums, i + 1, r)
		nums = list(n)
		n = len(nums)
		if n == 1 or n == 0 or n == 2 or (n == 3):
			return -1
		mid = n // 2 - 1
		res = nextGreatestPermutation(nums, 0, mid)
		if res == -1:
			return res
		ans = ''
		for i in range(mid + 1):
			ans += nums[i]
		if n % 2 != 0:
			ans += nums[mid + 1]
		for i in range(mid, -1, -1):
			ans += nums[i]
		return ans


class Solution:

	def nextPalin(self, string):

		def check_per(arr, length):
			index = -1
			for k in range(length - 2, -1, -1):
				if arr[k] < arr[k + 1]:
					index = k
					break
			if index == -1:
				return False
			change = -1
			for k in range(length - 1, -1, -1):
				if arr[k] > arr[index]:
					change = k
					break
			(arr[change], arr[index]) = (arr[index], arr[change])
			low = index + 1
			high = length - 1
			while low < high:
				(arr[low], arr[high]) = (arr[high], arr[low])
				low += 1
				high -= 1
			return True
		arr = list(string)
		size = len(arr)
		flag = check_per(arr, size // 2)
		if flag == False:
			return -1
		ans = ''.join(arr[:(size + 1) // 2])
		for idx in range(size // 2 - 1, -1, -1):
			ans += arr[idx]
		return ans


class Solution:

	def nextPalin(self, N):
		arr = list(N)
		n = len(arr)
		mid = n // 2 - 1
		i = mid - 1
		while i >= 0:
			if arr[i] < arr[i + 1]:
				break
			i -= 1
		if i < 0:
			return -1
		j = i + 2
		smallest = i + 1
		while j <= mid:
			if arr[i] < arr[j] and arr[j] < arr[smallest]:
				smallest = j
			j += 1
		(arr[i], arr[smallest]) = (arr[smallest], arr[i])
		(arr[n - 1 - i], arr[n - 1 - smallest]) = (arr[n - 1 - smallest], arr[n - 1 - i])
		arr = arr[:i + 1] + sorted(arr[i + 1:mid + 1])
		if n % 2 != 0:
			arr.append(N[mid + 1])
			arr.extend(arr[:-1][::-1])
		else:
			arr.extend(arr[::-1])
		return ''.join(arr)


class Solution:

	def nextPalin(self, N):
		mid = len(N) // 2
		mid = mid - 1
		ma = {}
		c = 0
		f = ''
		for i in range(mid, -1, -1):
			if len(f) != 0:
				break
			c += 1
			ko = int(N[i])
			if ko in ma:
				ma[ko] += 1
			else:
				ma[ko] = 1
			if c == 1:
				continue
			for j in range(ko + 1, 10, 1):
				if j in ma:
					ma[j] -= 1
					for w in range(i):
						f += N[w]
					f += str(j)
					for uw in range(0, 10):
						if uw in ma and ma[uw] != 0:
							for i in range(ma[uw]):
								f += str(uw)
					break
		if len(f) == 0:
			return -1
		if len(N) % 2 != 0:
			f = f + N[mid + 1] + f[::-1]
		else:
			f = f + f[::-1]
		return f


class Solution:

	def nextPalin(self, N):
		N = [int(c) for c in N]
		if len(N) <= 3:
			return -1
		val = self.NextHigher(N[:len(N) // 2])
		if val == -1:
			return -1
		else:
			ans = ''
			for i in val:
				ans += str(i)
			if len(N) % 2:
				return ans + str(N[len(N) // 2]) + ans[::-1]
			else:
				return ans + ans[::-1]

	def NextHigher(self, N):
		k = len(N) - 2
		while k >= 0:
			if int(N[k]) < int(N[k + 1]):
				break
			k -= 1
		if k >= 0:
			for i in range(len(N) - 1, k, -1):
				if int(N[i]) > int(N[k]):
					(N[k], N[i]) = (N[i], N[k])
					break
			N[k + 1:] = reversed(N[k + 1:])
			return N
		else:
			return -1


class Solution:

	def nextPalin(self, N):
		n = len(N)
		if n <= 3:
			return -1
		s = list(N[:n // 2])
		f = 0
		maxx = s[-1]
		ind = -1
		for i in range(n // 2 - 2, -1, -1):
			if maxx > s[i]:
				ind = i + 1
				break
			maxx = s[i]
		s = s[:ind] + sorted(s[ind:])
		for i in range(ind, n // 2):
			if s[ind - 1] < s[i]:
				(s[ind - 1], s[i]) = (s[i], s[ind - 1])
				break
		ans = ''.join(s)
		if n % 2 != 0:
			ans += N[n // 2]
		ans += ''.join(s[::-1])
		if ans <= N:
			return -1
		return ans