Problem Statement

At an internal developer summit, two engineers — Alex and Charlie — compete in a coding duel. They are given a string S made of lowercase English letters. Game rules Alex and Charlie take turns removing exactly one character from the current string, with Alex going first . The game continues until only one character is left in the string. Removal strategy Alex removes the character that makes the resulting string the lexicographically smallest possible. Charlie removes the character that makes the resulting string the lexicographically largest possible. Both players always follow their own strategy on their own turn. Report the single character that remains at the end. Note. Lexicographic order compares two strings of the same length character by character from left to right; the string whose first differing character is earlier in the alphabet is the smaller one (for example "abc" < "abd" because 'c' comes before 'd' ). Input Format S A single line containing the string