You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

工厂建造（$\texttt{cover}$）

【题目描述】

小 D 有很多机器人，还有一块无限大的土地。

这块土地可以被看成一个二维坐标系，他的机器人可以放在任意的整点 $(x,y)$ 上。

但他的机器人对放置的坐标有一些要求，当且仅当 $(x,y)$ 满足一定的要求时，这些机器人才可能工作。

• 小 D 有 $n$ 个 A 类机器人，第 $i$ 个机器人有参数 $p_i,q_i$，当且仅当 $x\equiv p_i\pmod k$ 和 $y\equiv q_i\pmod k$ 两个条件都满足，这个机器人才会工作。
• 小 D 有 $m$ 个 B 类机器人，第 $j$ 个机器人有参数 $s_j,t_j$，当且仅当 $x\equiv s_j\pmod k$ 和 $y\equiv t_j\pmod k$ 两个条件中至少满足一个，这个机器人才会工作。

小 D 想在这片土地中选定一块矩形作为工厂，要求每个机器人都能放在工厂中的某个位置（一个位置可以放多个机器人），使得 $n+m$ 个机器人都能工作，为了方便管理，他想最小化这块土地的面积。

准确来说，小 D 可以选择 $l_x,r_x,l_y,r_y$，那么他的机器人可以放在 $l_x\le x\le r_x,l_y\le y\le r_y$ 的任意整点 $(x,y)$ 上，他想最小化 $(r_x-l_x+1)\times (r_y-l_y+1)$ 的值。

【输入格式】

从 $\texttt{build.in}$ 中读入数据。

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

接下来 $n$ 行，每行两个整数表示 $p_i,q_i$。

接下来 $m$ 行，每行两个整数表示 $s_j,t_j$。

【输出格式】

输出到 $\texttt{build.out}$ 中。

一行一个整数表示答案。

【样例 1 输入】

2 1 5
1 4
2 2
0 0

【样例 1 输出】

8

【样例 1 解释】

选择 $l_x=1,r_x=2,l_y=2,r_y=5$，三个机器人分别放在 $(1,4),(2,2),(1,5)$。

【样例 2】

见下发文件中的 $\texttt{build2.in}$ 与 $\texttt{build2.ans}$。

该样例满足子任务 $2$ 的限制。

【样例 3】

见下发文件中的 $\texttt{build3.in}$ 与 $\texttt{build3.ans}$。

该样例满足子任务 $4$ 的限制。

【样例 4】

见下发文件中的 $\texttt{build4.in}$ 与 $\texttt{build4.ans}$。

该样例满足子任务 $6$ 的限制。

【数据范围】

对于所有的测试数据有：$n,m\ge 1,n+m\le 5\times 10^5,k\le 5000,0\le p_i,q_i,s_j,t_j<k$。