题目描述

给定一个长度为 $n$ 的数列 $a_1,a_2,...,a_n$。
和一个长度为 $m$ 的数列 $b_1,b_2,...,b_m$。
再给定一个正整数 $p$，需要生成一个长度为 $n\times m$ 的数列 $c_1,c_2,...,c_{n\times m}$。
其中满足 $c_{(i-1)\times m+j}=(a_i+b_j)\space mod\space p$。
现在问你数列 $c$ 中有多少个数对 $(i,j)$ 满足 $i\lt j$ 且 $c_i\gt c_j$

输入格式

从文件 pair.in 中读取数据。

第一行三个整数 $n,m,p$。

第二行 $n$ 个整数，表示 $a_1\sim a_n$。

第三行 $m$ 个整数，表示 $b_1\sim b_m$。

输出格式

输出到文件 pair.out 中。

一行一个整数，表示答案。

6 7 10
1 1 4 5 1 4
1 9 1 9 8 1 0

294

样例输入输出 2

见 2.in 与 2.ans

数据规模与约定

• 对于测试点 $1\sim 4$：$1\le n,m\le 100,1\le p\le 10,0\le a_i,b_i\lt p$。
• 对于测试点 $5\sim 6$：$1\le n,m\le 1000,1\le p\le 10,0\le a_i,b_i\lt p$。
• 对于测试点 $7\sim 8$：$1\le n,m\le 1000000,p=2,0\le a_i,b_i\lt p$。
• 对于测试点 $9\sim 20$：$1\le n,m\le 1000000,1\le p\le 10,0\le a_i,b_i\lt p$。