Regatta Seed Bracket Draw

A regatta committee is drawing up a single-elimination knockout series for a fleet of n sailboats, seeded by strength from 1 (strongest) to n (weakest); n is guaranteed to be a power of two. In the first round the committee lines the boats up in seed order and pairs the boat at the front of the line with the boat at the back, then the new front with the new back, and so on working inward, so seed 1 races seed n, seed 2 races seed n-1, and so forth. Each of those pairings is then treated as a single unit and lined up in the same left-to-right order in which the pairs were formed; the committee applies the exact same front-with-back rule to this new, shorter line, and keeps repeating the process -- always pairing the current front unit with the current back unit and working inward -- until only one unit remains, which describes the entire bracket.

Formally, let the current round be a list of groups g_1, g_2, ..., g_k written left to right (initially the k = n boats themselves, in seed order). The next round's list is formed by combining g_i and g_{k+1-i} into a single group "(g_i,g_{k+1-i})" for i = 1, 2, ..., k/2, keeping the results in that same left-to-right order. Repeat this halving process until exactly one group remains, and print it.

Input format

A single line containing one integer n.

Output format

A single line containing the fully nested bracket string built by the process above, using only digits, commas, and parentheses -- no spaces anywhere. If n = 1 there is nothing to pair, so the output is simply "1".

Constraints

• 1 <= n <= 4096
• n is a power of two (n = 2^k for some integer k >= 0).

4

((1,4),(2,3))

8

(((1,8),(4,5)),((2,7),(3,6)))