注意

yukicoder contest 279 (Zelkova and Cherry) の問題は 難易度順に並んではいない. よって, 問題文や難易度を表すの星の数, 正解者数等といった公開されている情報から問題を取捨選択することを強く推奨する.

問題文

春の国, 夏の国, 秋の国, 冬の国からそれぞれ $N$ 人ずつ合計 $4N$ 人が集まって大会が催された. この大会の予選を戦うグループとして, 春, 夏, 秋, 冬の国それぞれ1人ずつからなる $N$ 個のグループ $G_1,\dots ,G_N$ を作る. また,この大会の各参加者にはレーティングが設定されており, この値を利用し以下の値を定義する.

• グループ $G_k$ の4人のレーティングの最大値,最小値をそれぞれ $X_k,Y_k$ としたとき, グループ $G_k$ の不公平さ $D_k$ を $D_k:=X_k-Y_k$ と定義する.
• 予選の不公平さを ${\displaystyle \sum _{k=1}^N{D}_k^K}$ で定義する.

予選の不公平さの最小値 $F$ を求めよ. ただし, $F$ は非常に大きくなる可能性があるので, $F$ を $M$ で割った余りを出力せよ. 予選の不公平さを $M$ で割った余りの最小値を求めるのではないことに注意せよ.
ただし, 春, 夏, 秋, 冬の国の $i$ 番目の参加者のレーティングをそれぞれ $P_i,E_i,A_i,H_i$ とする.

制約

• $1\le N\le 2\times {10}^5$
• $1\le K\le {10}^9$
• $1\le M\le {10}^9$
• $0\le P_i,E_i,A_i,H_i\le {10}^9(i=1,2,\dots ,N)$
• 入力は全て整数である.

入力

$NKM$
$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$

出力

考えうる全てのグループ分けを考えたときに可能な, 予選の不公平さの最小値を $M$ で割った余りを出力せよ. 改行を忘れないこと.

サンプル

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