public class OnlySanta {
	boolean containsSubsequence(String a, String b) {
		int i = 0;
		for(int j = 0; j < b.length(); ++j)
			while(i < a.length() && a.charAt(i) != b.charAt(j))
				++i;
		return i < a.length();
	}
	public String solve(String S) {
		if(!containsSubsequence(S, "S"))
			return S + "SANTA";
		if(containsSubsequence(S, "SAN")) return S + "TA";
		// find first S
		int i = 0;
		while(S.charAt(i) != 'S') ++i;
		return S.substring(0, i + 1) + "AN" + S.substring(i + 1) + "TA";
	}
}

cHVibGljIGNsYXNzIE9ubHlTYW50YSB7Cglib29sZWFuIGNvbnRhaW5zU3Vic2VxdWVuY2UoU3RyaW5nIGEsIFN0cmluZyBiKSB7CgkJaW50IGkgPSAwOwoJCWZvcihpbnQgaiA9IDA7IGogPCBiLmxlbmd0aCgpOyArK2opCgkJCXdoaWxlKGkgPCBhLmxlbmd0aCgpICYmIGEuY2hhckF0KGkpICE9IGIuY2hhckF0KGopKQoJCQkJKytpOwoJCXJldHVybiBpIDwgYS5sZW5ndGgoKTsKCX0KCXB1YmxpYyBTdHJpbmcgc29sdmUoU3RyaW5nIFMpIHsKCQlpZighY29udGFpbnNTdWJzZXF1ZW5jZShTLCAiUyIpKQoJCQlyZXR1cm4gUyArICJTQU5UQSI7CgkJaWYoY29udGFpbnNTdWJzZXF1ZW5jZShTLCAiU0FOIikpIHJldHVybiBTICsgIlRBIjsKCQkvLyBmaW5kIGZpcnN0IFMKCQlpbnQgaSA9IDA7CgkJd2hpbGUoUy5jaGFyQXQoaSkgIT0gJ1MnKSArK2k7CgkJcmV0dXJuIFMuc3Vic3RyaW5nKDAsIGkgKyAxKSArICJBTiIgKyBTLnN1YnN0cmluZyhpICsgMSkgKyAiVEEiOwoJfQp9