Alchemy (from Arabic: الكيمياء, al-kīmiyā) was an ancient branch of natural philosophy: a philosophical and protoscientific tradition practised throughout Europe, Africa, and Asia, that originated in Greco-Roman Egypt in the first few centuries.

Alchemists attempted to purify, mature, and perfect certain materials. Common aims were chrysopoeia¹ — the transmutation of "base metals" (e.g., lead) into "noble metals" (particularly gold) —, the creation of an elixir of immortality, the creation of panaceas² able to cure any disease, and the development of an alkahest³ — a universal solvent. The perfection of the human body and soul was thought to permit or result from the alchemical magnum opus and — in the Hellenistic and Western mystery tradition — the achievement of gnosis⁴. In Europe, the creation of a Philosopher's Stone⁵ was variously connected with all of these projects.

In English, the term is often limited to descriptions of European alchemy, but similar practices existed in the Far East, the Indian subcontinent, and the Muslim world. In Europe, following the 12th-century Renaissance produced by the translation of Medieval Islamic works on science and the rediscovery of Aristotelian philosophy, alchemists played a significant role in early modern science (particularly chemistry and medicine). Islamic and European alchemists developed a structure of basic laboratory techniques, theory, terminology, and experimental method, some of which are still in use today. However, they continued antiquity's belief in four elements and guarded their work in secrecy including ciphers and cryptic symbolism. Their work was guided by Hermetic principles⁶ related to magic, mythology, and religion.

Current insights into the elements show that it is impossible to convert other metals into gold through chemical processes. However, American chemist Glenn Seaborg transmuted several thousand atoms of bismuth into gold at the Lawrence Berkeley Laboratory in 1980. His experimental technique, using nuclear physics, was able to remove protons and neutrons from the bismuth atoms. Seaborg's technique would have been far too expensive to enable routine manufacturing of gold, but his work was close to the mythical Philosopher's Stone⁷.

Assignment

A polymer is formed by smaller units which — when activated — react with each other such that two adjacent units of the same type and opposite polarity destroy each other. This is called the alchemical reduction of the polymer.

Unit's types are represented by letters, with the unit's polarity represented by capitalization. For instance, r and R are units with the same type but opposite polarity, whereas r and s are entirely different types that do not react with each other.

Some examples of alchemical reductions:

• in polymer aA units a and A react with each other, leaving nothing behind

• in polymer abBA units b and B first destroy each other, leaving polymer aA; as above, this then destroys itself, leaving nothing behind

• in polymer abAB no two adjacent units are of the same type, so nothing happens

• nothing happens with polymer aabAAB: even though aa and AA are of the same type, their polarities match

Now consider the alchemical reduction of polymer dabAcCaCBAcCcaDA as a somewhat larger example:

After all possible reactions, the resulting polymer contains 10 units.

Input

A polymer, represented as a sequence of uppercase and lowercase letters.

Output

The alchemical reduction of the given polymer, followed by the number of units in the reduced polymer in between round brackets.

Example

Input:

dabAcCaCBAcCcaDA

Output:

dabCBAcaDA(10)