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

---

ایلیچ $n$ دختر دارد و همچنین سلطان $n$ پسر دارد که می خواهند ازدواج کنند. ولی سلطان در این شرایط وخیم اقتصادی پول زیادی ندارد که خرج رفت و آمد و مهریه پسرهایش کند. لذا به بچه‌هایش گفته که حتما باید به خواستگاری دختران ایلیچ بروند (چون خانواده ایلیچ اعتقادی به مهریه ندارند). خوش‌بختانه پسران سلطان به خوبی تربیت شده‌اند و علاوه بر گوش دادن به حرف پدر، در تلاش هستند تا با کمترین هزینه ممکن به خواستگاری دختران ایلیچ بروند اما آن‌ها توانایی لازم برای محاسبه‌ی این مقدار هزینه را ندارند. لذا از شما کمک خواسته‌اند.

می‌دانیم که خانه پسر $i$ ام در شهر $a_i$ و خانه دختر $j$ام در شهر $b_j$ است؛ هزینه رفتن از شهر $x$ به شهر $y$ برابر $|x - y|$ است. همچنین در صبح هر یک از روزهای $1$ تا $q$ یکی از پسران یا دختران به دلیل وضعیت بد مالی خانه‌ی خود را تغییر می‌دهد و به خانه جدیدی می‌رود (ممکن است خانه جدید در هر شهری باشد).

بر طبق آداب و رسوم ما ایرانی‌ها بدیهی است که مراسم خواستگاری در شب صورت می‌گیرد و همچنین هیچ دو نفری در یک شب خواستگاری یک نفر نمی‌روند و همچنین پول برگشت پسر به خانه را پدر دختر تقبل می‌کند. حال شما به ازای هر یک از روزهای $1$ تا $q$ بگویید که اگر پسرها بخواهند در شب این روز به خواستگاری بروند کمترین هزینه‌ای که مجموعا سلطان برای آن‌ها باید پرداخت کند چه‌قدر خواهد بود؟

از آن‌جایی که بچه‌های سلطان مانند پدرشان اهل تسلیم شدن نیستند، ممکن است به خواستگاری دختر تکراری نیز بروند.

ورودی

در سطر اول ورودی عدد $n$ آمده است که نشان‌دهنده تعداد پسرها و همچنین تعداد دخترها است.
سپس در سطر بعدی $n$ عدد آمده است که عدد $i$ام همان $a_i$ است.
در سطر بعدی نیز $n$ عدد آمده است که عدد $j$ ام نمایانگر $b_j$ است.
در سطر چهارم ورودی عدد $q$ آمده است که نشان‌دهنده‌ی تعداد روزهایی است که پسرهای سلطان عزم خواستگاری می‌کنند.
در $q$ سطر بعدی نیز در هر سطر دو عدد $v_d$ و سپس $x_d$ آمده است که نشان‌دهنده‌ی مهاجرت نفر $v_d$در ابتدای روز فعلی به خانه‌ای در شهر $x_d$ می‌باشد.
اگر $v_d$ بزرگتر از $n$ باشد، منظور دختر $v_d - n$ ام و در غیر این صورت منظور پسر $v_d$ام است.

• $1 \le n, q \le 10^{5}$
• $1 \le a_i, b_j, x_d \le 10^{5}$
• $1 \le v_d \le 2 \times n$

خروجی

در خروجی $q$ عدد چاپ کنید که عدد $d$ام نشان‌دهنده کمترین مجموع هزینه رفتن پسرهای سلطان به خواستگاری در شب روز $d$ام است.

زیر مسئله ها

زیرمسئله	نمره	محدودیت ها
۱	۶	در طول تمامی روز ها شماره شهر محل سکونت تمام پسر ها کمتر مساوی شماره شهر محل سکونت تمام دختر هاست.
۲	۱۵	$n, q \le 1000$
۳	۱۷	$a_i, b_j, x_d \le 1000$
۴	۶۲	بدون محدودیت اضافی

مثال

ورودی نمونه ۱

2
2 100
1 101
2
1 1
4 100

خروجی نمونه ۱

1
0

ورودی نمونه ۲

5
10 2 20 3 30
5 17 4 9 23
6
4 9
9 7
8 15
1 47
5 21
2 8

خروجی نمونه ۲

17
19
20
47
38
38