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

یکی از سرورهای گوگولا در هر روز $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$ دارد.