题目描述

有两支队伍 $A$、$B$，最终都恰好有 $n$ 名选手。比赛会随机生成一个一一配对：每名 $A$ 队选手恰好与一名 $B$ 队选手交手，所有 $n!$ 种配对等概率出现。

若两名选手强度分别为 $X$ 和 $Y$：

• 若 $X>Y$，$A$ 队得到 $(X-Y)^2$ 分；
• 若 $X<Y$，$B$ 队得到 $(X-Y)^2$ 分；
• 若 $X=Y$，双方均不得分。

定义最终分差为“A 队总分减去 B 队总分”。求这个分差的期望值。

为了缩小输入，只给出两组种子数组。对任意种子数组 $X$，按照下面过程生成长度为 $n$ 的真正强度数组 $R$：

j = 0
m = |X|
for i = 0 .. n-1:
    R[i] = X[j]
    s = (j + 1) % m
    X[j] = ((X[j] XOR X[s]) + 13) % 49999
    j = s

其中 XOR 表示按位异或。两支队伍分别独立执行该生成过程。

输入格式

由于原始测试数据转换时针对“两个种子数组长度是否相同”使用了两种等价编码，因此每个测试点会采用下面两种格式之一。

格式 A：两个种子数组长度相同

第一行两个整数 $m,n$。

接下来 $m$ 行，每行两个整数 $A_i,B_i$，分别给出两个种子数组的第 $i$ 个元素。

格式 B：两个种子数组长度不同

第一行一个整数 $n$。

第二行一个整数 $p=|A|$。

第三行 $p$ 个整数，表示种子数组 $A$。

第四行一个整数 $q=|B|$。

第五行 $q$ 个整数，表示种子数组 $B$。

输出格式

输出 A 队最终分差的期望值。绝对误差或相对误差不超过 $10^{-9}$ 即视为正确。

数据范围

• $1\le |A|,|B|\le 50$；
• 种子数组元素均在 $0$ 到 $49998$ 之间；
• $1\le n\le 50000$。

样例 1

1 1
6 4

4.0

样例 2

2 2
1 3
7 5

0.0

样例 3

2 2
3 1
7 5

20.0