Background

不知道题目要取什么名字，随便编一个。
有一个工程师、一个物理学家和一个数学家分别粉刷一面墙，但是每人的油漆都是不够的。
工程师刷了一半发现不够，物理学家估计了油漆不够就不刷了。
只有数学家，把整面墙都刷满了，但是油漆一点都没少。
为什么呢？因为他把墙上所有的有理数点都涂上了油漆。
这个故事告诉我们，有理数是非常稀少的，甚至于它相比无理数的数量可以忽略不计。
那么下面这题或许可以全部输出0？这样能骗到多少分？

Description

给出n个数，第i个数的值为ai，从左至右排列。
每个数一开始属于不同的集合，每个集合内的元素就是这个数本身。
请支持如下两种操作：
1.合并左起第u个数和第v个数所在的集合，如果这两个数在同一个集合中，那么你无需进行操作。
2.查询：在左起第x个数所在的集合内随机选出两个数b,c，那么关于x的一元二次方程x^2+bx+c=0解为有理数的概率是多少。
b,c的生成方式为：先随机选取集合内一个数为b，再重复此过程选出c。

Format

Input

第一行两个正整数n,Q，Q表示操作总数。
第二行n个正整数ai。
接下来Q行，每行为如下两种形式：
1 u v 表示操作1，这种情况下你不需要输出任何内容。
2 x 表示操作2，你需要输出该询问的答案。

Output

对于每个操作2，按顺序输出该询问的答案，保留6位小数。

Sample 1

Input

3 2
1 2 3
1 1 2
2 1

Output

0.250000

Limitation

5s, 512MB for each test case.

Hint

对于全部数据，1<=n,Q<=10^5,1<=ai<=10^9,1<=u,v,x<=n。
本题共有10个测试数据点，每个测试数据点还满足如下特殊性质：
测试点1,2：n,Q<=1000。
测试点3：没有操作2。
测试点4：没有操作1。
测试点5,6：先进行所有的操作1，再进行所有的操作2。
测试点7,8：所有操作1中的u,v在数据范围内均匀随机生成。
测试点9,10：不保证任何特殊性。

Source

wbs