public String encode(String s)
	{
		String t = "";
		while (s.length() > 1) {
			int mid = s.length() / 2;
			if (s.length() % 2 == 1) {
				t += s.charAt(mid);
				s = s.substring(0, mid) + s.substring(mid + 1);
			} else {
				if (s.charAt(mid - 1) < s.charAt(mid)) {
					t += s.charAt(mid - 1);
					s = s.substring(0, mid - 1) + s.substring(mid);
				} else {
					t += s.charAt(mid);
					s = s.substring(0, mid) + s.substring(mid + 1);
				}
			}
		}
		return t + s;
	}