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

در کوهستان $m$ اسکی‌باز مشغول اسکی هستند. آن‌ها همه خوشحال هستند غافل از اینکه خطری مرگبار آن‌ها را تهدید می‌کند. شما به عنوان محافظ کوهستان، می‌خواهید به آن‌ها قبل از آنکه دیر شود هشدار دهید که بهمنی بزرگ در راه هست.

هر اسکی‌باز یک سرعت ثابت دارد که به سوی بالا یا پایین در حرکت است. شما می‌دانید که در زمان‌های $t_1, t_2, t_3, ...,t_n$ بهمن سراریز خواهد شد به همین دلیل شما می‌خواهید بدانید در هر یک از این زمان‌ها بالاترین اسکی‌باز در چه ارتفاعی قرار دارد.

ورودی

سطر نخست ورودی شامل دو عدد صحیح $m$ و $n$ به ترتیب است. در سطر دوم $m$ جفت $v_i, s_i$ آمده است که $s_i$ نشان‌دهنده‌ی ارتفاع اولیه‌ی اسکی‌باز $i$ ام و $v_i$ نشان‌دهنده‌ی سرعت آن است. در سطر بعد $n$ عدد $t_1, t_2, t_3, ..., t_n$ به ترتیب آمده است.

$$1 \leq n, m \leq 100000$$

قدر مطلق سرعت و ارتفاع اولیه‌ی اسکی‌بازها از ۱۰۰۰۰ بیشتر نیست.

خروجی

در تنها سطر خروجی $n$ عدد که نشانگر ارتفاع بالاترین اسکی‌باز در زمان $t_i$ است را بنویسید. اعداد را با فاصله از هم جدا کنید.

مثال

ورودی نمونه ۱

2 3
0 1 2 -1
0 2 4

خروجی نمونه ۱

2 2 4