+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- یکی از سرورهای گوگولا در هر روز $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$ دارد.