Creative Number Construction and Query

In the beginning, the universe was nothing but darkness. Then, the Creator made light and separated day from night. On the second day, He created the number 0. On the third day, dissatisfied with only 0, He created new numbers by forming ordered pairs of numbers that were already created. That is, for any two numbers x and y, the new number is defined as

$$x = (x_L, x_R)$$

Examples include: $$ (0,0),\; (0,(0,0)),\; ((0,0),0),\; ((0,0),(0,0)),\; \ldots $$

The Creator then defined equality and a total order on these recursively defined numbers as follows:

• Equality:
  1. $$0=0.$$
  2. For any numbers $$x_L,x_R,y_L,y_R$$, if $$x_L=y_L$$ and $$x_R=y_R$$ then $$(x_L,x_R)=(y_L,y_R)$$.
  3. No other equalities hold.
• Order:
  1. For any number $$x\neq0$$, $$0<x.$$
  2. For any numbers $$x_L,x_R,y_L,y_R$$, if $$x_L<y_L$$ then $$(x_L,x_R)<(y_L,y_R).$$
  3. For any numbers $$x_L,x_R,y_L,y_R$$, if $$x_L=y_L$$ and $$x_R<y_R$$ then $$(x_L,x_R)<(y_L,y_R).$$
  4. No other cases yield $$x<y$$.

  Moreover, we define $$x\le y\iff x<y \text{ or } x=y.$$ Hence, any two numbers are comparable.

Inspired by this creation, a clever flea plays with these numbers every day. The flea starts with an array a[1..n] of length n, initially all set to 0 (the base number). Then, the flea performs a sequence of operations. There are two kinds of operations:

1. Assignment Operation: The flea chooses three positive integers l, r, k (with $$1\le l,r,k\le n$$). It then assigns $$a[k] = (a[l],a[r]).$$ Note that even if k equals l or r, the operation is valid (the flea first computes the pair then assigns it).
2. Query Operation: The flea chooses two positive integers l and r (with $$1\le l \le r \le n$$) and requests the maximum value among $$a[l],a[l+1],\ldots,a[r].$$ The maximum is determined using the order defined above.

Your task is to simulate the flea's operations. For each query operation, output the maximum element in the queried range in its canonical string representation. The representation is defined recursively as follows:

• If the number is 0, print 0.
• If the number is a pair (x,y), print it as (S(x),S(y)) where S(x) is the string representation of x.

For example, if a[2]=(0,0) then its representation is (0,0), and if a[5]=((0,0),(0,0)) then its representation is ((0,0),(0,0)).

Input Format: The first line contains two integers n and q — the length of the array and the number of operations. The following q lines each describe an operation. An operation with two integers represents a query operation, and an operation with three integers represents an assignment operation.

Output Format: For each query operation, print the maximum number in the specified range on a separate line using the canonical string representation described above.

inputFormat

The first line contains two integers n and q ($$1\le n\le 10^5$$, the number of operations is reasonable for simulation).
Each of the next q lines contains either:

• Two integers l and r ($$1\le l\le r\le n$$) representing a query operation.
• Three integers l, r, and k ($$1\le l,r,k\le n$$) representing an assignment operation, meaning set $$a[k]=(a[l],a[r]).$$

It is guaranteed that all indices are valid.

outputFormat

For each query operation, output a single line containing the string representation of the maximum number in the queried segment.

The string representation is defined recursively as:

• If the number is 0, output 0.
• If the number is a pair (x, y), output (S(x),S(y)) where S(x) and S(y) are the string representations of x and y respectively.

sample

5 7
1 5
1 1 2
1 3
2 2 5
2 5
3 5 4
1 5

0
(0,0)
((0,0),(0,0))
((0,0),(0,0))

</p>