Worms

دوستان کرم‌ ما پس از باران دیشب از زیر خاک بیرون آمده‌اند و قامت سهی خود را به منصه‌ی ظهور رسانده‌اند. در این اوقات این دوستان المپیادی به طور کامل از روی زمین بلند می شوند و سیخ می‌ایستند تا زمین خشک شود. ما هم فرصت را غنیمت شمردیم و می‌خواهیم مقدار متنابهی از آن‌ها را به ملکوت اعلاء بپیوندانیم.

برای این کار باید از بیل مخصوصی استفاده کنیم و آن را در ارتفاعی ثابت به صورت افقی حرکت دهیم. یک کرم در صورتی کشته می‌شود که قسمتی از بیل به سرآن اصابت کند.

برای این که بتوانیم با تلاش کم تعداد زیادی از دوستان را از بین ببریم، احتیاج به اطلاعاتی داریم که قرار است شما آن را در اختیار ما قرار دهید. اطلاعات مورد نیاز ما به این صورت است که در ارتفاعات بازه‌ی [$a$, $b$] چه تعداد سر کرم وجود دارد.

برنامه‌ای بنویسید که با گرفتن ارتفاع سر کرم‌ها و بازه‌های مورد نظر اطلاعات مورد نیاز را تأمین کند.

• در سطر اول به ترتیب دو عدد $n$ (تعداد کرم‌ها) و $k$ (تعداد بازه‌ها) با یک فاصله آمده اند.
• ‎$1 \leq n,k \leq 10^5$
• در هر یک از $n$ سطر بعد، یک عدد صحیح نامنفی آمده است که ارتفاع سر یکی از کرم‌ها است (در محدوده‌ی integer).
• سپس در $k$ سطر بعد، در هر سطر دو عدد صحیح آمده‌اند که نشان‌دهنده‌ی یکی از بازه‌های مورد سؤال است.

• در هر یک از $k$ سطر، پاسخ به یکی از پرسش‌ها باید داده شوند.
• در سطر $i$ام عددی صحیح بنویسید که پاسخ به پرسش $i$ام از ورودی است.

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

• سوال بعد
• سوال قبل