题目描述

现代科技博物馆安装了两扇自动门。每扇门有一个整数参数 $t$，安装时可以设置为 $1\sim10^9$。

如果有人在时刻 $p$ 通过一扇门，那么这扇门会在 $p-t$ 时刻打开，并在 $p+t$ 时刻关闭。若有若干人连续通过，且任意相邻两人的通过时间间隔都不超过 $2t$，那么门只会在这一段人的第一人到达前 $t$ 秒打开一次，并在最后一人通过后 $t$ 秒关闭一次。

现在给出两扇门过去的通行记录：

• 第一扇门有人在 $p_1<p_2<\cdots<p_n$ 时通过；
• 第二扇门有人在 $q_1<q_2<\cdots<q_m$ 时通过。

需要分别选择参数 $t_1,t_2$，满足：

1. 两扇门的总打开次数尽可能少；
2. 不存在一个长度严格大于 $d$ 的连续时间区间，使得在整个区间中两扇门都同时处于打开状态。

若有多个最优方案，输出任意一个。

输入格式

第一行三个整数 $n,m,d$，其中 $1\le n,m\le5000$，$1\le d\le10^9$。

第二行 $n$ 个严格递增的整数 $p_1,p_2,\ldots,p_n$。

第三行 $m$ 个严格递增的整数 $q_1,q_2,\ldots,q_m$。

所有通行时刻均满足 $1\le p_i,q_i\le10^9$。

输出格式

若存在方案，输出两个整数 $t_1,t_2$，满足 $1\le t_1,t_2\le10^9$，且总打开次数最少。

若不存在任何可行方案，输出：

No solution

样例

3 2 4
1 6 13
7 11

3 2

难度评定

约 CF2700。

关键在于发现每扇门的打开次数只会在相邻时间差对应的 $\lceil\Delta/2\rceil$ 处变化，再利用可行性关于 $t_1,t_2$ 的单调性做双指针，将原本的候选二重枚举降到线性次数的区间交判定。