Se dau numerele $P$, $m$, $n$, $k$, și două șiruri: $b_1, b_2, \dots b_m$ și $a_0, a_1, \dots a_{n-1}$ de numere naturale. Se formează șirul $v_0, v_1, \dots , v_{n-1}$ parcurgând elementele lui $a$ din $k$ în $k \pmod{n}$, începând de la poziția 0.

Fiecare număr din $v$ se înlocuiește cu cea mai apropiată putere cu exponent natural a unui element din $b$. Dacă un număr se află la aceeași distanță de două puteri, se alege valoarea mai mică. De exemplu dacă $b = [2, 3]$, puterile elementelor din șirul $b$ sunt: $1, 2, 4, 8, 16, \dots, 1, 3, 9, 27, 81, \dots$.

Cerință

1. Dacă $P = 1$, aflați suma valorilor din șirul $v$ după ce s-au făcut înlocuirile.
2. Dacă $P = 2$, când numărul este mai mic ca puterea aleasă, se va înlocui cu opusul puterii alese (De exemplu, în loc de 5 ar fi -5). Apoi se calculeaza $S$, parcurgând elementele lui $v$ în ordine ($0, 1, 2, \dots n-1$) și aplicându-se formula S=((S*k+v[i])%n+n)%n. Initial, $S$=0.

Date de intrare

Pe prima linie a fișierului abmnk.in se află $P$. Pe a doua linie se află numerele $m$, $n$ și $k$, în această ordine, separate prin câte un spațiu. Pe a treia linie se află șirul $b_1, b_2, \dots b_m$ de numere naturale mai mari sau egale cu 2, separate prin câte un spațiu. Pe a patra linie se află șirul $a_0, a_1, \dots a_{n-1}$ de numere naturale separate prin câte un spațiu.

Date de ieșire

Pe prima linie a fișierului de ieșire abmnk.out se va găsi un singur număr întreg, răspunsul cerinței $P$.

Restricții și precizări

• Se garantează $cmmdc$ $(n, k) = 1$.
• $1 \le m \le 1 \ 000$
• $1 \le k < n \le 1 \ 000 \ 000$
• Numerele din fișierul de intrare sunt mai mici sau egale cu $10^9$

Subtaskuri

Exemplul 1

abmnk.in

1
5 15 4
2 32 10000 17 3
5 16 289 57 32 27 70 1 10000000 100000000 4 90 81 1024 531441

abmnk.out

108921736

Explicație

Parcurgem din 4 in 4 și obținem $V = \texttt{\{5}$ , $\texttt{32}$ , $\texttt{10000000}$ , $\texttt{81}$ , $\texttt{16}$ , $\texttt{27}$ , $\texttt{100000000}$ , $\texttt{1024}$ , $\texttt{289}$ , $\texttt{70}$ , $\texttt{4}$ , $\texttt{531441}$, $\texttt{57}$ , $\texttt{1}$ , $\texttt{90\}}$

Exemplul 2

abmnk.in

2
5 15 4
2 32 10000 17 3
5 16 289 57 32 27 70 1 10000000 100000000 4 90 81 1024 531441

abmnk.out

8

Explicație

La final, $V = \texttt{\{4}$ , $\texttt{32}$ , $\texttt{8388608}$ , $\texttt{81}$ , $\texttt{16}$ , $\texttt{27}$ , $\texttt{100000000}$ , $\texttt{1024}$ , $\texttt{289}$ , $\texttt{64}$ , $\texttt{4}$ , $\texttt{531441}$ , $\texttt{-64}$ , $\texttt{1}$ , $\texttt{81\}}$