- 16

## Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

## Statement

## Goal

If you have 4 bells (say**Plain Bob Minimus**is such an algorithm. Here is its beginning:

1 2 3 4 →2 1 4 3 →2 4 1 3 →4 2 3 1 →4 3 2 1 →3 4 1 2

A permutation of a set is a bijection (a one-to-one function) from the set onto itself, like a shuffle of the elements of the set.

We can describe

**Plain Bob Minimus**’ permutations as

`(1 2)(3 4)`→

`(1 4)`→

`(2 4)(1 3)`→

`(2 3)`→

`(4 3)(2 1)`.

First,

`(1 2)(3 4)`exchanges the bells

Then

`(1 4)`exchanges the bells

Then

`(2 4)(1 3)`exchanges the bells

In blue, it’s a list of bells, a melody with four bells. In yellow, it’s the permutation that rearranges the bells from a melody to the next melody.

A permutation can move more than two bells.

`(1 4 5)`is the permutation that sends

Beware, because permutations are functions,

**you must compute them from right to left**.

You have to

**print the resulting permutation**from a succession of permutations, that is a product of disjoint cycles (no number may appear in more than one cycle).

Note that

`(1 4)(2 3)`=

`(4 1)(2 3)`=

`(3 2)(4 1)`and so on. Write down the first in the lexicographic order where

`(1 4)(2 3)`<

`(3 2)(4 1)`<

`(4 1)(2 3)`.

Don’t print the 1-cycle permutations like

`(1)`or

`(3)`that move nothing in the decomposition even if they might be present as input. There might be only one permutation and the result might be the original. If the permutation moves nothing, print

`()`(two parentheses).

Look at the examples below.

Example,

`(1 3)(1 2 3)(1 3)`:

Conclusion,

`(1 3)(1 2 3)(1 3)`=

`(1 3 2)`(a 3-cycle).

The last example,

`(1 2 3)(1 4 3)`:

Conclusion,

`(1 2 3)(1 4 3)`=

`(1 4)(2 3)`(two disjoint 2-cycle).

Input

**Single line**The succession of permutations.

Output

**Single line**The result of their product.

Constraints

The input is properly formatted (no unpaired parentheses, etc.)

1≤

1≤

`input`≤5Example

Input

(1 2)(2 3)

Output

(1 2 3)

A higher resolution is required to access the IDE