AT_abc429_d [ABC429D] On AtCoder Conference

There is a pond with a circumference of $ M $ , and on its shore stand one hut and $ N $ people. For a real number $ x $ $ (0\leq x

The input is given from Standard Input in the following format: > $ N $ $ M $ $ C $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

Print the sum of $ X_i $ over $ i=0,1,\ldots,M-1 $ on a single line.

### Sample Explanation 1 When $ i=0 $ , Takahashi starts at point $ 0.5 $ and moves clockwise. Then, the following happens: - At point $ 1 $ , he meets the $ 1 $ st, $ 3 $ rd, and $ 5 $ th people, a total of three people, and the total number of people met so far is $ 3 $ . This is not less than $ C=2 $ , so Takahashi stops there. Therefore, $ X_0=3 $ . When $ i=1 $ , Takahashi starts at point $ 1.5 $ and moves clockwise. Then, the following happens: - At point $ 2 $ , he meets the $ 2 $ nd person. The total number of people met so far is $ 1 $ , so he continues moving. - At point $ 0 $ , he meets the $ 4 $ th person, and the total number of people met so far is $ 2 $ . This is not less than $ C=2 $ , so Takahashi stops there. Therefore, $ X_1=2 $ . When $ i=2 $ , Takahashi starts at point $ 2.5 $ and moves clockwise. Then, the following happens: - At point $ 0 $ , he meets the $ 4 $ th person. The total number of people met so far is $ 1 $ , so he continues moving. - At point $ 1 $ , he meets the $ 1 $ st, $ 3 $ rd, and $ 5 $ th people, a total of three people, and the total number of people met so far is $ 4 $ . This is not less than $ C=2 $ , so Takahashi stops there. Therefore, $ X_2=4 $ . Therefore, the answer is $ X_0+X_1+X_2=3+2+4=9 $ . ### Sample Explanation 2 Regardless of the starting position, Takahashi stops when he meets the only person standing around the pond, who is at point $ 1 $ . Therefore, $ X_i=1 $ regardless of $ i $ , and the answer is $ 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 $ - All input values are integers.