{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"We can number binary trees using the following scheme: \r\u003cbr\u003eThe empty tree is numbered 0.\r\u003cbr\u003eThe single-node tree is numbered 1.\r\u003cbr\u003eAll binary trees having m nodes have numbers less than all those having m+1 nodes.\r\u003cbr\u003eAny binary tree having m nodes with left and right subtrees L and R is numbered n such that all trees having m nodes numbered \u0026gt; n have either Left subtrees numbered higher than L, or A left subtree \u003d L and a right subtree numbered higher than R.\r\u003cbr\u003e\r\u003cbr\u003eThe first 10 binary trees and tree number 20 in this sequence are shown below:\r\u003cbr\u003e\u003ccenter\u003e\u003cimg src\u003d\"CDN_BASE_URL/862ab7d4c5583093781b5715502a9ec3?v\u003d1724057066\"\u003e\u003c/center\u003e\r\u003cbr\u003eYour job for this problem is to output a binary tree when given its order number.\r\u003cbr\u003e"}},{"title":"Input","value":{"format":"HTML","content":"Input consists of multiple problem instances. Each instance consists of a single integer n, where 1 \u0026lt;\u003d n \u0026lt;\u003d 500,000,000. A value of n \u003d 0 terminates input. (Note that this means you will never have to output the empty tree.)"}},{"title":"Output","value":{"format":"HTML","content":"For each problem instance, you should output one line containing the tree corresponding to the order number for that instance. To print out the tree, use the following scheme:\r\u003cbr\u003e\r\u003cbr\u003eA tree with no children should be output as X.\r\u003cbr\u003eA tree with left and right subtrees L and R should be output as (L\u0027)X(R\u0027), where L\u0027 and R\u0027 are the representations of L and R.\r\u003cbr\u003e If L is empty, just output X(R\u0027).\r\u003cbr\u003e If R is empty, just output (L\u0027)X.\r\u003cbr\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n20\r\n31117532\r\n0\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eX\r\n((X)X(X))X\r\n(X(X(((X(X))X(X))X(X))))X(((X((X)X((X)X)))X)X)\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}