يوجد $N$ روبوتًا على دائرة. تُرقّم أقصى نقطة شمالًا بالموضع $0$. نُقسم الدائرة إلى $M$ أجزاء متساوية ($M \ge N$)، ونُرقّم نقاط التقسيم المتبقية من $1$ إلى $M-1$ باتجاه عقارب الساعة. بذلك تتحدد المواضع من $0$ إلى $M-1$ على الدائرة (الشكل 1). في البداية، تشغل الروبوتات $N$ مواضع مختلفة.

تُعرّف المسافة بين موضعين $x,y$ على الدائرة بأنها $y-x$ ($y \ge x$). يستطيع الروبوت $R_i$ الموجود في الموضع $x_i$ مراقبة النقاط ضمن مدى ثابت $R>0$ في كلا الاتجاهين. أي إذا كان $a$ هو الموضع على مسافة $R$ عكس اتجاه عقارب الساعة من $x_i$، و$b$ هو الموضع على مسافة $R$ باتجاه عقارب الساعة، فإن $R_i$ يراقب الجزء من الدائرة الممتد من $a$ إلى $b$ باتجاه عقارب الساعة.

نريد مراقبة الدائرة بأكملها. قد تترك المواضع الأولية أجزاء غير مراقبة، لذلك نريد حينها تحريك الروبوتات لتغطية الدائرة كلها. نفترض $M \le 2RN$، مما يضمن وجود تحريك يحقق ذلك دائمًا.

لا يجوز للروبوتات الانتقال إلا إلى مواضع الدائرة المعرّفة أعلاه، ويمكن تحريك كل روبوت مرة واحدة على الأكثر. نريد تصغير أكبر مسافة يتحركها أي روبوت.

مثلًا، في الشكل 1، توجد الروبوتات الثلاثة $R_1,R_2,R_3$ في المواضع $1,2,5$ على الترتيب، ومدى المراقبة $R=2$. لمراقبة الدائرة كلها، ينتقل $R_1$ إلى الموضع $0$، وينتقل $R_3$ إلى الموضع $6$. هذا التحريك يجعل أكبر مسافة حركة أصغر ما يمكن.

الشكل 1

عند إعطاء مواضع $N$ روبوتًا والمدى $R$ والعدد الصحيح $M$، أوجد واطبع أصغر قيمة ممكنة لأكبر مسافة حركة عند تحريك الروبوتات لمراقبة الدائرة بأكملها.

الإدخال

تُعطى المعلومات التالية عبر الإدخال القياسي. يحتوي السطر الأول على عدد الروبوتات $N$ ($1 \le N \le 1,000,000$). يحتوي السطر الثاني على عددين صحيحين $R,M$ يحددان مدى المراقبة ومواضع الدائرة ($1 \le R,M \le 10^9$، $N \le M \le 2RN$). يحتوي السطر التالي على $N$ أعداد صحيحة مختلفة $x_i$ ($0 \le x_i \le M-1$، $i=1,\ldots,N$)، مفصولة بمسافات، تمثل المواضع الأولية للروبوتات.

المهام الفرعية

• المهمة الفرعية 1: 10 نقاط من أصل 100؛ $M \le 10$.

• المهمة الفرعية 2: 30 نقطة من أصل 100؛ $N \le 7,000$.

• المهمة الفرعية 3: 60 نقطة من أصل 100؛ لا توجد قيود غير القيود الأصلية.

الإخراج

اطبع عبر الإخراج القياسي أصغر قيمة ممكنة لأكبر مسافة حركة للروبوتات تتيح مراقبة الدائرة بأكملها.

أمثلة

الإدخال 1

3
2 10
1 2 5

الإخراج 1

1

الإدخال 2

6
1 11
0 1 2 3 4 5

الإخراج 2

2