• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

یکی از سرورهای گوگولا در هر روز \(n\) وظیفه برنامه‌ریزی شده را انجام می‌دهد. وظیفه \(i\)ام در زمان \(s_i\) انجام می‌شود. اجرای هر وظیفه به اندازه \(k\) میلی‌ثانیه زمان می‌برد پس هر وظیفه از ابتدای ثانیه \(s_i\) تا انتهای ثانیه \(s_i + k - 1\) در حال انجام است. انجام نشدن وظیفه \(i\)ام هزینه \(w_i\)تایی برای شرکت گوگولا به ارمغان می‌آورد.

اداره برق برای \(q\) روز بعدی جدول زمان‌بندی قطعی برق را اعلام کرده است. در روز \(i\)ام برق سرور از ابتدای ثانیه \(l_i\) تا انتهای ثانیه \(r_i\) در همان روز قطع می‌شود. هر وظیفه‌ای که زمان اجرای آن با زمان قطعی برق تلاقی داشته باشد، متوقف می‌شود. هزینه‌ای که گوگولا در روز \(i\)ام به خاطر قطعی برق می‌دهد، به اندازه مجموع هزینه وظایف متوقف شده می‌باشد. به ازای هر روز هزینه قطعی برق برای سرور گوگولا را محاسبه و چاپ کنید.

ورودی

در خط اول عدد طبیعی ‍‍\(n\) می‌آید. در خط دوم عدد طبیعی \(k\) می‌آید. در خط سوم اعداد طبیعی \(s_1, s_2, \cdots, s_n\,\) به‌ترتیب می‌آیند. در خط چهارم اعداد طبیعی \(w_1, w_2, \cdots, w_n\,\) به‌ترتیب می‌آیند. در خط پنجم عدد طبیعی \(q\) می‌آید. در \(i\)امین خط از \(q\) خط بعدی، دو عدد \(l_i\) و \(r_i\) به‌ترتیب می‌آیند.

\[1 \leq n, q \leq 200 \, 000 \] \[1 \leq k, s_i, w_i \leq 10^{9}\] \[1 \leq l_i \leq r_i \leq 10^{9}\]

خروجی

در \(q\) خط هزینه قطعی برق را به ازای هر روز به‌ترتیب چاپ کنید.

مثال‌ها

ورودی نمونه ۱

4
2
5 6 1 3
400 800 100 200
5
1 2
1 4
2 2
3 6
5 10

خروجی نمونه ۱

100
300
100
1400
1200

در این نمونه \(k = 2\) است و یعنی کارها از

• ابتدای ثانیه‌ی پنجم تا انتهای ثانیه‌ی ششم
• ابتدای ثانیه‌ی ششم تا انتهای ثانیه‌ی هفتم
• ابتدای ثانیه‌ی یکم تا انتهای ثانیه‌ی دوم
• و از ابتدای ثانیه‌ی سوم تا انتهای ثانیه‌ی چهارم

انجام می‌شوند و هزینه‌ی آن‌ها به ترتیب \(400\)، \(800\)، \(100\) و \(200\) است.

در قطعی‌های برق مختلف اگر:

• برق از ابتدای ثانیه‌ی اول تا انتهای ثانیه‌ی دوم برود، کار سوم متوقف می‌شود و هزینه‌ی \(100\) دارد.
• برق از ابتدای ثانیه‌ی اول تا انتهای ثانیه‌ی چهارم برود، کار سوم و چهارم متوقف می‌شوند و هزینه‌ی \(100 + 200\) دارد.
• برق از ابتدای ثانیه‌ی دوم تا انتهای ثانیه‌ی دوم برود، کار سوم متوقف می‌شود و هزینه‌ی \(100\) دارد.
• برق از ابتدای ثانیه‌ی سوم تا انتهای ثانیه‌ی ششم برود، کارهای به جز کار سوم متوقف می‌شوند و هزینه‌ی \(800 + 400 + 200\) دارد.
• برق از ابتدای ثانیه‌ی پنجم تا انتهای ثانیه‌ی دهم برود، کارهای اول و دوم متوقف می‌شوند و هزینه‌ی \(400 + 800\) دارد.