How Many Times?
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

Mars-man (MM) has n (1 <= n <= 100,000) piles of numbers (We will call them H). At first, Hi has only one number i.

Now he will perform m (1 <= m <= 300,000) operations. There are 3 kinds of operators and he will choose one of them each time.

  • OP = 1 : MM will merge heap Px and heap Py (Pi is the heap which contains integer i).
  • OP = 2 : MM will delete the largest number in heap Px if it exists.
  • OP = 3 : MM want to know the value of max(Sx, Sy) / min(Sx, Sy). We define Sx = 1 * a1 * a2 * ... * asi (ai is the ith number in Px and si is the size of Px).

For each OP 3, you should print a number. Certainly, MM hates big numbers, so you should print 10,000,000,000,000,000 if your answer is greater than 10,000,000,000,000,000.

输入描述:

* Line 1 : Two space-separated integers n and m.  
* Line 2...m+1 : Two or three space-separated integers, OP (1 <= OP <= 3), x (1 <= x <= n), and y (1 <= y <= n) if OP != 2.  

输出描述:

For each OP 3, each line print a number.  
Your answer will be accepted if your answers to all queries have absolute or relative error of at most 106.
示例1

输入

复制 
6 5
3 3 1
1 2 3
3 3 6
2 3
3 6 4

输出

复制 
3.000000
1.000000
1.500000