Notice

The problems of yukicoder contest 279 (Zelkova and Cherry) are not sorted in order of difficulty. Therefore, it is strongly recommended that you choose which problems to work on based on publicly available information such as the problem statements, the number of stars indicating difficulty, and the number of solvers.

Problem Statement

A tournament was held with $N$ people each from the Spring Country, the Summer Country, the Autumn Country, and the Winter Country, for a total of $4N$ people. As the groups that will compete in the preliminary round of this tournament, we form $N$ groups $G_1,\dots,G_N$, each consisting of one person from each of the Spring, Summer, Autumn, and Winter Countries. In addition, each participant of this tournament has a rating, and using these values, the following are defined.

• Let $X_k,Y_k$ be the maximum and the minimum, respectively, of the ratings of the four people in group $G_k$. The unfairness $D_k$ of group $G_k$ is defined as $D_k:=X_k-Y_k$.
• The unfairness of the preliminary round is defined as $\displaystyle \sum_{k=1}^N D_k^K$.

Find the minimum value $F$ of the unfairness of the preliminary round. Since $F$ can be very large, output $F$ modulo $M$. Note that you are not asked to find the minimum value of the unfairness of the preliminary round modulo $M$.
Here, the ratings of the $i$-th participants of the Spring, Summer, Autumn, and Winter Countries are $P_i,E_i,A_i,H_i$, respectively.

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq K \leq 10^9$
• $1 \leq M \leq 10^9$
• $0 \leq P_i,E_i,A_i,H_i \leq 10^9~(i=1,2,\dots,N)$
• All inputs are integers.

Input

$N\ K\ M$
$P_1\ P_2\ \dots \ P_N$
$E_1\ E_2\ \dots \ E_N$
$A_1\ A_2\ \dots \ A_N$
$H_1\ H_2\ \dots \ H_N$

Output

Output the minimum value of the unfairness of the preliminary round achievable over all possible groupings, modulo $M$. Do not forget the newline.

Sample

2 2 100
1 1000
1002 2
3 1004
1006 4

45

1 4 10000
5
10
15
20

625

9 20210122 123456789
14 14 21 35 62 37 30 95 4
88 1 68 87 24 20 96 98 7
85 69 67 18 75 37 69 48 7
31 76 67 97 37 99 7 32 47

39598529