Color Sandwich

Problem Statement

Color Sandwich Sam is a cook. He has coloured slices of bread and some stuffing, and he has made a stack of sandwiches. A single sandwich is a slice of bread, then zero or more pieces of stuffing, then a second slice of bread of the same colour as the first. For example, qabcq is one sandwich: the bread colour is q and the stuffing is abc . A sandwich with no stuffing, such as uu , is also allowed. The sandwiches are placed one on top of the other, and the whole stack is written as a string S , from the first sandwich to the last. Every character of S is either a slice of bread or a piece of stuffing, and every character belongs to exactly one sandwich. Return a string made of the bread colour of every sandwich, in the order the sandwiches appear in S . Input Format A single line containing the string S . Output Format Print a single line: the bread colours of all the sandwiches, one character per sandwich, in order. Constraints 2 <= |S| <= 20000 (inferred -- the source gives no