//WARNSDORFF'S ALGORITHM

import java.util.Scanner;

class Main {
    public static final int N = 8;
    public static final int cx[] = { 1, 1, 2, 2, -1, -1, -2, -2 };
    public static final int cy[] = { 2, -2, 1, -1, 2, -2, 1, -1 };

    boolean limits(int x, int y) {
        return ((x >= 0 && y >= 0) && (x < N && y < N));
    }

    boolean isEmpty(int a[], int x, int y) {
        return (limits(x, y)) && (a[y * N + x] < 0);
    }

    int getDegree(int a[], int x, int y) {
        int count = 0;
        for (int i = 0; i < N; ++i)
            if (isEmpty(a, (x + cx[i]), (y + cy[i])))
                count++;
        return count;
    }

    Cell nextMove(int a[], Cell cell) {
        int min_deg_idx = -1, c, min_deg = (N + 1), nx, ny;
        int start = (int) (Math.random() * N); // Generate random start index within 0 to N-1

        for (int count = 0; count < N; ++count) {
            int i = (start + count) % N;
            nx = cell.x + cx[i];
            ny = cell.y + cy[i];
            if ((isEmpty(a, nx, ny)) && (c = getDegree(a, nx, ny)) < min_deg) {
                min_deg_idx = i;
                min_deg = c;
            }
        }

        if (min_deg_idx == -1)
            return null;

        nx = cell.x + cx[min_deg_idx];
        ny = cell.y + cy[min_deg_idx];

        a[ny * N + nx] = a[cell.y * N + cell.x] + 1;

        cell.x = nx;
        cell.y = ny;

        return cell;
    }

    void print(int a[]) {
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j)
                System.out.printf("%d\t", a[j * N + i]);
            System.out.printf("\n");
        }
    }

    boolean neighbour(int x, int y, int xx, int yy) {
        for (int i = 0; i < N; ++i)
            if (((x + cx[i]) == xx) && ((y + cy[i]) == yy))
                return true;
        return false;
    }

    boolean findClosedTour(int sx, int sy) {
        // Filling up the chessboard matrix with -1's
        int a[] = new int[N * N];

        for (int i = 0; i < N * N; ++i)
            a[i] = -1;

        Cell cell = new Cell(sx, sy);
        a[cell.y * N + cell.x] = 1; // Mark first move.

        Cell ret = null;
        for (int i = 0; i < N * N - 1; ++i) {
            ret = nextMove(a, cell);
            if (ret == null)
                return false;
        }

        if (!neighbour(ret.x, ret.y, sx, sy))
            return false;

        print(a);
        return true;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        while (true) {
            System.out.println("Enter the starting x-coordinate (0 to 7): ");
            int startX = scanner.nextInt();
            System.out.println("Enter the starting y-coordinate (0 to 7): ");
            int startY = scanner.nextInt();

            if (startX >= 0 && startX < N && startY >= 0 && startY < N) {
                Main knightTour = new Main();
                if (knightTour.findClosedTour(startX, startY)) {
                    System.out.println("Knight's tour found!");
                } else {
                    System.out.println("Knight's tour not found for the given starting position.");
                }
                break;
            } else {
                System.out.println("Invalid starting position. Please enter valid coordinates.");
            }
        }
        scanner.close();
    }
}

class Cell {
    int x;
    int y;

    public Cell(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

//HAMILTONIAN CYCLE

public class Main
{
	final int V = 5;
	int path[];
	boolean isSafe(int v, int graph[][], int path[], int pos)
	{
		if (graph[path[pos - 1]][v] == 0)
			return false;
		for (int i = 0; i < pos; i++)
			if (path[i] == v)
				return false;

		return true;
	}
	boolean hamCycleUtil(int graph[][], int path[], int pos)
	{
		if (pos == V)
		{
			if (graph[path[pos - 1]][path[0]] == 1)
				return true;
			else
				return false;
		}
		for (int v = 1; v < V; v++)
		{
			if (isSafe(v, graph, path, pos))
			{
				path[pos] = v;
				if (hamCycleUtil(graph, path, pos + 1) == true)
					return true;
				path[pos] = -1;
			}
		}
		return false;
	}
	int hamCycle(int graph[][])
	{
		path = new int[V];
		for (int i = 0; i < V; i++)
			path[i] = -1;

		path[0] = 0;
		if (hamCycleUtil(graph, path, 1) == false)
		{
			System.out.println("\nSolution does not exist");
			return 0;
		}

		printSolution(path);
		return 1;
	}
	void printSolution(int path[])
	{
		System.out.println("Solution Exists: Following" +
						" is one Hamiltonian Cycle");
		for (int i = 0; i < V; i++)
			System.out.print(" " + path[i] + " ");

		System.out.println(" " + path[0] + " ");
	}

	public static void main(String args[])
	{
		Main hamiltonian = new Main();
		int graph1[][] = {{0, 1, 0, 1, 0},
			{1, 0, 1, 1, 1},
			{0, 1, 0, 0, 1},
			{1, 1, 0, 0, 1},
			{0, 1, 1, 1, 0},
		};

		hamiltonian.hamCycle(graph1);

		int graph2[][] = {{0, 1, 0, 1, 0},
			{1, 0, 1, 1, 1},
			{0, 1, 0, 0, 1},
			{1, 1, 0, 0, 0},
			{0, 1, 1, 0, 0},
		};

		hamiltonian.hamCycle(graph2);
	}
}

//lexographically


class Main{
 
    static char MAX_CHAR = 26;
    static void countFreq(String str, int freq[], int len){
        for (int i = 0; i < len; i++){
            freq[str.charAt(i) - 'a']++;
        }
    }
 
    static boolean canMakePalindrome(int freq[], int len){
        
        int count_odd = 0;
        for (int i = 0; i < MAX_CHAR; i++){
            if (freq[i] % 2 != 0){
                count_odd++;
            }
        }
 
        if (len % 2 == 0){
            if (count_odd > 0){
                return false;
            }
            else{
                return true;
            }
        }
    
        if (count_odd != 1){
            return false;
        }
        return true;
    }

    static String findOddAndRemoveItsFreq(int freq[]){
        String odd_str = "";
        for (int i = 0; i < MAX_CHAR; i++){
            if (freq[i] % 2 != 0){
                freq[i]--;
                odd_str = odd_str + (char) (i + 'a');
                return odd_str;
            }
        }
        return odd_str;
    }
 
    static String findPalindromicString(String str){
        int len = str.length();
        int freq[] = new int[MAX_CHAR];
        countFreq(str, freq, len);
 
        if (!canMakePalindrome(freq, len)){
            return "No Palindromic String";
        }
 
        String odd_str = findOddAndRemoveItsFreq(freq);
 
        String front_str = "", rear_str = " ";
 
        for (int i = 0; i < MAX_CHAR; i++){
            String temp = "";
            if (freq[i] != 0){
                char ch = (char) (i + 'a');
                for (int j = 1; j <= freq[i] / 2; j++){
                    temp = temp + ch;
                }
                front_str = front_str + temp;
 
                rear_str = temp + rear_str;
            }
        }
 
        return (front_str + odd_str + rear_str);
    }
    public static void main(String[] args){
        String str = "banan";
        System.out.println(findPalindromicString(str));
    }
}