AT_abc429_d [ABC429D] On AtCoder Conference

$ 1 $ 周の長さが $ M $ である池があり、その周上に $ 1 $ つの小屋と $ N $ 人の人が立っています。 実数 $ x $ $ (0\leq x

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ C $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

$ i=0,1,\ldots,M-1 $ にわたる $ X_i $ の総和を一行に出力せよ。

### Sample Explanation 1 $ i=0 $ のとき、高橋君は地点 $ 0.5 $ からスタートして時計回りに動きます。その後、次のようになります。 - 地点 $ 1 $ で $ 1,3,5 $ 番目の $ 3 $ 人と出会い、今まで出会った人数の合計は $ 3 $ となる。これは $ C=2 $ 以上であるため、高橋くんはそこで止まる。よって、 $ X_0=3 $ である。 $ i=1 $ のとき、高橋君は地点 $ 1.5 $ からスタートして時計回りに動きます。その後、次のようになります。 - 地点 $ 2 $ で $ 2 $ 番目の人と出会う。今まで出会った人数の合計は $ 1 $ であるため、動き続ける。 - 地点 $ 0 $ で $ 4 $ 番目の人と出会い、今まで出会った人数の合計は $ 2 $ となる。これは $ C=2 $ 以上であるため、高橋くんはそこで止まる。よって、 $ X_1=2 $ である。 $ i=2 $ のとき、高橋君は地点 $ 2.5 $ からスタートして時計回りに動きます。その後、次のようになります。 - 地点 $ 0 $ で $ 4 $ 番目の人と会う。今まで出会った人数の合計は $ 1 $ であるため、動き続ける。 - 地点 $ 1 $ で $ 1,3,5 $ 番目の $ 3 $ 人と会い、今まで出会った人数の合計は $ 4 $ となる。これは $ C=2 $ 以上であるため、高橋くんはそこで止まる。よって、 $ X_2=4 $ である。 よって、答えは $ X_0+X_1+X_2=3+2+4=9 $ となります。 ### Sample Explanation 2 高橋君はスタートする位置によらず、池の周りに立っている唯一の人である、地点 $ 1 $ にいる人に出会った時に止まります。 よって、 $ i $ によらず $ X_i=1 $ であり、答えは $ 10^{12} $ となります。 ### Constraints - $ 1\leq N\leq 5\times 10^5 $ - $ 1\leq M\leq 10^{12} $ - $ 0\leq A_i\leq M-1 $ - $ 1\leq C\leq N $ - 入力はすべて整数