B'Recently, Kolya found out that a new movie theatre is going to be opened in his city soon, which will show a new movie every day for n days. So, on the day with the number 1 <= i <= n , the movie theatre will show the premiere of the i -th movie. Also, Kolya found out the schedule of the movies and assigned the entertainment value to each movie, denoted by a_i . However, the longer Kolya stays without visiting a movie theatre, the larger the decrease in entertainment value of the next movie. That decrease is equivalent to d cdot cnt , where d is a predetermined value and cnt is the number of days since the last visit to the movie theatre. It is also known that Kolya managed to visit another movie theatre a day before the new one opened -- the day with the number 0 . So if we visit the movie theatre the first time on the day with the number i , then cnt -- the number of days since the last visit to the movie theatre will be equal to i . For example, if d = 2 and a = [3, 2, 5, 4, 6] , then by visiting movies with indices 1 and 3 , cnt value for the day 1 will be equal to 1 - 0 = 1 and cnt value for the day 3 will be 3 - 1 = 2 , so the total entertainment value of the movies will be a_1 - d cdot 1 + a_3 - d cdot 2 = 3 - 2 cdot 1 + 5 - 2 cdot 2 = 2 . Unfortunately, Kolya only has time to visit at most m movies. Help him create a plan to visit the cinema in such a way that the total entertainment value of all the movies he visits is maximized. Each test consists of multiple test cases. The first line contains a single integer t ( 1 <= t <= 10^4 ) -- the number of test cases. The description of the test cases follows. The first line of each test case contains three integers n , m , and d ( 1 <= n <= 2 cdot 10^5 , 1 <= m <= n , 1 <= d <= 10^9 ). The second line of each set of i'...