لديك القدرة على صنع روبوتات يقع ارتفاعها في المجال $[0, d]$. ولاختبارها، قمت ببناء مسار بطول $n$ يحتوي على بعض العوائق. يُعطى وصف العوائق على شكل مصفوفة $a$. إذا كان $a_i = 0$، فلا يوجد عائق في الموضع $i$، وإلا فإنه يوجد عائق بارتفاع $a_i > 0$.
لاختبار الروبوت الخاص بك، تختار مجالاً $[l, r]$ وتجعله يمر عبر جميع العوائق الموجودة في هذا المجال. عندما يصادف الروبوت عائقاً بقيمة $a_i > 0$، يحدث أحد احتمالين:
- إذا كان الارتفاع الحالي للروبوت $h$ أصغر من $a_i$، فلا يحدث شيء لأن الروبوت أقصر من أن يصل إلى العائق.
- إذا كان الارتفاع الحالي للروبوت $h$ على الأقل $a_i$، فإن الارتفاع الجديد يتغير إلى $h' = h - a_i$.
الآن عليك الإجابة عن $q$ استعلامات. لكل مجال من المجالات $q$ المعطاة $[l_i, r_i]$، عليك تحديد أقصى ارتفاع ممكن يمكن أن ينتهي به الروبوت بعد المرور عبر العوائق في المجال إذا تم اختيار ارتفاعه الابتدائي من المجال $[0, d]$.
الإدخال
يحتوي السطر الأول على الأعداد الصحيحة $n, q, d$ ($1 \le n, q \le 3 \cdot 10^5, 1 \le d \le 10^9$) — طول المصفوفة وعدد الاستعلامات.
يحتوي السطر الثاني على $n$ أعداد صحيحة $a_i$ ($0 \le a_i \le 10^9$) — وصف المصفوفة.
تحتوي الأسطر الـ $q$ التالية على زوج من الأعداد الصحيحة $[l_i, r_i]$ ($1 \le l_i \le r_i \le n$) — وصف الاستعلامات.
الإخراج
اطبع $q$ أعداد صحيحة — الإجابات عن الاستعلامات.
أمثلة
الإدخال 1
5 3 5 0 2 6 1 3 5 5 1 5 1 3
الإخراج 1
2 2 3
الإدخال 2
7 5 10 7 6 2 5 0 1 4 1 3 1 7 4 7 2 5 4 6
الإخراج 2
3 2 3 3 4