問題文

STPC(Science Tokyo Programming Contest) は東京科学大学の学生が開催するコンテストです。初回は 2025 年 11 月 8 日に行われました。早速、次回の STPC の日程を決めることにしましょう！

正整数 N,L,W と N 個の正整数 D_1,D_2,\dots, D_N が与えられます。

あなたは STPC というイベントの開催日程を決めようとしています。具体的には、正整数 X を決めて、STPC を今日から X 日後に開催しようとしています。

さて、現在予定されている重大なイベントが N 個あります。 i 個目のイベントは今日から D_i 日後に開催されることが分かっています。

あなたはこれらのイベントと日程が被るのを避けて STPC の開催日程を決めることにしました。すなわち、任意の i に対して D_i\neq X である必要があります。また、準備には時間がかかるため、X\ge L である必要があります。さらに、開催会場の都合上、X は W の倍数である必要があります。

これらの条件をすべて満たすように STPC の開催日程を決めるとき、最も早い開催日程は今日から何日後であるかを求めてください。すなわち、すべての条件を満たす最小の正整数 X を求めてください。

ただし、このような X が存在することは証明できます。

制約

• 入力はすべて整数
• 1\le N\le 2\times 10^5
• 1\le L,W\le 10^9
• 1 \le D_1 \lt D_2 \lt \dots \lt D_N \le 10^9

入力例 1

5 3 2
1 3 4 7 9

出力例 1

6

この入力例では L = 3, W = 2 です。

• X = 1 は X \ge L を満たしません。
• X = 2 は X \ge L を満たしません。
• X = 3 は W の倍数ではありません。
• X = 4 は 3 個目のイベントと被ってしまいます。
• X = 5 は W の倍数ではありません。
• X = 6 はすべての条件を満たします。

よって、最も早い開催日程は 6 日後です。

入力例 2

10 1 1
1 2 3 4 5 6 7 8 9 10

出力例 2

11