abmnk

You are given the numbers $P$, $m$, $n$, $k$, and two sequences: $b_1, b_2, \dots b_m$ and $a_0, a_1, \dots a_{n-1}$ of natural numbers. The sequence $v_0, v_1, \dots , v_{n-1}$ is formed by traversing the elements of $a$ from $k$ to $k \pmod{n}$, starting from position 0.

Each number in $v$ is replaced with the closest natural power of an element from $b$. If a number is equidistant from two powers, the smaller value is chosen. For example, if $b = [2, 3]$, the powers of the elements in sequence $b$ are: $1, 2, 4, 8, 16, \dots, 1, 3, 9, 27, 81, \dots$.

Task

1. If $P = 1$, find the sum of the values in the sequence $v$ after the replacements.
2. If $P = 2$, when a number is less than the chosen power, it will be replaced with the negative of the chosen power (For example, instead of 5, it would be -5). Then calculate $S$ by traversing the elements of $v$ in order ($0, 1, 2, \dots n-1$) and applying the formula S=((S*k+v[i])%n+n)%n. Initially, $S$=0.

Input data

The first line of the input file abmnk.in contains $P$. The second line contains the numbers $m$, $n$, and $k$, in this order, separated by spaces. The third line contains the sequence $b_1, b_2, \dots b_m$ of natural numbers greater than or equal to 2, separated by spaces. The fourth line contains the sequence $a_0, a_1, \dots a_{n-1}$ of natural numbers separated by spaces.

Output data

The first line of the output file abmnk.out will contain a single integer, the answer to requirement $P$.

Constraints and clarifications

• It is guaranteed that gcd $(n, k) = 1$.
• $1 \le m \le 1\ 000$
• $1 \le k < n \le 1\ 000\ 000$
• The numbers in the input file are less than or equal to $10^9$

Subtasks

Example 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

Explanation

We traverse from 4 to 4 and obtain $V = \{5, 32, 10000000, 81, 16, 27, 100000000, 1024, 289, 70, 4, 531441, 57, 1, 90\}$.

Example 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

Explanation

In the end, $V = \{4, 32, 8388608, 81, 16, 27, 100000000, 1024, 289, 64, 4, 531441, -64, 1, 81\}$.