ایلیچ $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$ام است.

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

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

• زیرمسئله 1 (6 نمره): در تمام روزها، شماره‌ی شهر محل سکونت تمام پسرها کمتر مساوی شماره‌ی شهر محل سکونت تمام دخترهاست.
• زیرمسئله 2 (15 نمره): $n, q \le 1000$
• زیرمسئله 3 (17 نمره): $a_i, b_j, x_d \le 1000$
• زیرمسئله 4 (62 نمره): بدون محدودیت اضافی