1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.util.Scanner;
import java.util.Arrays;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        char[] s = scan.next().toCharArray();
        Arrays.sort(s);
        int p1 = 0;
        int p2 = next(s, p1);
        char[] res = new char[s.length];
        for (int i = 0; i < s.length; i++) {
            if (i == 0 || s[p1] != res[i - 1]) {
                res[i] = s[p1++];
                if (p1 < s.length && s[p1] != s[p1 - 1]) {
                    p1 = p2;
                    p2 = next(s, p1);
                }
            } else {
                if (p2 >= s.length) {
                    System.out.println("INVALID");
                    return;
                } else {
                    res[i] = s[p2++];
                }
            }
        }
        System.out.println(new String(res));
    }
    static int next(char[] s, int p1) {
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX