题目背景

雪蚱在青花动物园做着收发邮件的工作，每天会有很多邮件需要寄到不同的地点去，比如录取通知书。雪蚱当然不用把每一封邮件送到收件人手中，他只需要把邮件放在正确的邮箱里，然后等着快递员来收走就好了。如果没有放到正确的邮箱里，那就不能送达正确地点了。但是雪蚱始终是雪蚱，是一只不认字的雪蚱，他并不知道每封邮件上写的收件地址是什么意思，只好随机乱放了。放错的邮件太多，他就可能会被裁退，并被丢给雪芬鸡。

今天一大早，雪蚱来到工作室，发现堆了许多许多的邮件，于是他开始发愁了。

题目描述

一共有 $N$ 封邮件，第 $i$ 封邮件需要邮寄到省份 $a_i$。同样，一共有 $N$ 个邮箱，第 $i$ 个邮箱里的所有邮件将会被送往省份 $b_i$。邮件与邮箱都从$1\sim N$进行编号，每个邮箱里最多只能放一封邮件，每个邮件也只能放入一个邮箱。

假定初始状态下，所有的邮箱都是空的，所有邮件都尚未投入邮箱。现在，他需要将编号在区间 $[c,d]$ 中的邮件逐个投出。对于每封邮件，他等概率地从编号在区间 $[e,f]$ 中的空邮箱选择一个，并把这封邮件放到这个邮箱中。在这种情况下，他投对邮件数目的期望是多少？

雪蚱也是一只爱多想的雪蚱，所以一共会有 $Q$ 次询问。每次询问之间互不影响，即对于每次询问，都从初始状态开始，且保证 $d - c +1 \leq f - e + 1$。

输入格式

输入数据的第一行包含三个正整数 $task,N,Q$，表示子任务编号、邮件及邮箱的个数以及询问个数。

接下来一行一共 $N$ 个正整数，第 $i$ 个数 $a_i$ 表示第 $i$ 封邮件需要邮寄到的省份编号。

接下来一行一共 $N$ 个正整数，第 $i$ 个数 $b_i$ 表示第 $i$ 个邮箱对应的省份编号。

接下来一共 $Q$ 行，每行 $4$ 个正整数 $c,d,e,f$，表示第 $c$ 到第 $d$ 封邮件和第 $e$ 到第 $f$ 个邮箱。

对于所有测试点，保证$1\leq a_i,b_i,c,d,e,f\leq N$, $d-c+1\leq f-e+1$

输出格式

输出 $Q$ 行，每行一个最简分数表示对应询问的答案，也就是期望放对的邮件份数。

最简分数输出格式为——输出空格隔开的两个整数，分别表示分子和分母。答案为整数的时候，分母视为 $1$。

例如答案为 0 时，应当输出 0 1。

5 3 1
2 3 3
3 2 1
1 3 1 3

1 1

令 $(a_1,a_2,a_3)$ 表示第一封邮件放入了邮箱 $a_1$，第二份邮件放入了邮箱 $a_2$，第三份邮件放入了邮箱 $a_3$ 的方案。

那么所有可能的邮件放置方式有 $(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)$，一共正确放入了 $0+0+2+2+1+1=6$ 封邮件。所以期望正确放入 $1$ 封邮件。

子任务

对于每一个子任务，如果通过子任务下所有测试点即可获得该子任务得分，否则不得分。

- args: [20, 1, "N"]
  cases: [10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
  score: 12
- args: [100000, 100000, "2"]
  cases: [20, 21, 22, 23, 24, 25, 26, 27, 28, 29]
  score: 20
- args: [100000, 100000, "3"]
  cases: [30, 31, 32, 33, 34, 35, 36, 37, 38, 39]
  score: 6
- args: [50000, 50000, "N"]
  cases: [40, 41, 42, 43, 44, 45, 46, 47, 48, 49]
  score: 25
- args: [100000, 100000, "N"]
  cases: [50, 51, 52, 53, 54, 55, 56, 57, 58, 59]
  score: 17
- args: [50000, 1000000, "N"]
  cases: [60, 61, 62, 63, 64, 65, 66, 67, 68, 69]
  score: 20