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

---

ابواسحاق پس از خواندن تمام نامه‌ها، به یک دعوت‌نامه بَر خورد. او که بسیار کنجکاو شده بود به آدرس داخل دعوت‌نامه رفت و سَر از جزیرهٔ آدم‌خوارها درآورد! آن‌ها ابواسحاق را تهدید کردند که اگر می‌خواهد او را نخورند، باید جای خرگوش‌های جزیره را برایشان پیدا کند. او هم که خیلی ترسیده بود، از شما کمک خواست تا جای خرگوش‌ها را پیدا کنید. سوال آدم خوارها به صورت زیر است:

تعدادی خرگوش روی محور $x$ ها ایستاده‌اند. خرگوش‌ها با اعداد ۱ تا $n$ شماره‌گذاری شده‌اند و خرگوش شماره $i$ ابتدا در موقعیت مکانی $a_i$ قرار دارد. یک عملیات قرینه‌سازی روی خرگوش شماره $i$ به صورت زیر انجام می شود:

• با احتمال برابر، یکی از خرگوش‌های $i+1$ یا $i-1$ انتخاب می‌شود (اندیس‌ها دایره ای هستند؛ به عبارت دیگر اگر عملیات روی خرگوش شماره ۱ انجام شود، یکی از خرگوش‌های $2$ یا $n$ انتخاب می‌شوند).

• موقعیت خرگوش شماره $i$ نسبت به خرگوش انتخاب شده قرینه می‌شود.

آدم‌خوارها به ما یک ترتیب از عملیات‌های قرینه‌سازی را می‌دهند و ما $k$ بار پشت سر هم و به همین ترتیب، این عملیات‌ها را انجام می‌دهیم. حال شما باید به ازای هر خرگوش باقیمانده امیدریاضی مکانش را نسبت به $10^9 + 7$ به دست آورید.

ورودی

در خط اول ورودی، تعداد خرگوش‌ها، $n$ می‌آید. سپس در خط دوم، دنباله $a_1 , a_2 , ... , a_n $ موقعیت مکانی اولیه خرگوش‌ها می آیند. در خط بعد، دو عدد $m$ و $k$ ورودی داده می‌شوند. در خط آخر، دنباله عملیات‌ها، $b_1 , b_2 , ... , b_m $ ورودی داده می‌شود.

$$ 3 \le n \le 200\ 000 $$ $$ 0 \le a_i \le 10^9 + 6 $$ $$ 1 \le m \le 200\ 000 $$ $$ 1 \le k \le 10^{18} $$

خروجی

در خروجی یک دنباله به طول $n$، شامل امید ریاضی مکان نهایی خرگوش‌ها باقیمانده بر $10^9 + 7$ را چاپ کنید.

مثال

ورودی نمونه ۱

3
1 2 3
3 2
2 1 3

خروجی نمونه ۱

4
5
6

ورودی نمونه ۲

4
1 0 1 0
2 3
2 3

خروجی نمونه ۲

1
0
1
0