B"Students of one unknown college don't have PE courses. That's why q of them decided to visit a gym nearby by themselves. The gym is open for n days and has a ticket system. At the i -th day, the cost of one ticket is equal to a_i . You are free to buy more than one ticket per day. You can activate a ticket purchased at day i either at day i or any day later. Each activated ticket is valid only for k days. In other words, if you activate ticket at day t , it will be valid only at days t, t + 1, ... , t + k - 1 . You know that the j -th student wants to visit the gym at each day from l_j to r_j inclusive. Each student will use the following strategy of visiting the gym at any day i ( l_j <= i <= r_j ): Note that each student will visit gym only starting l_j , so each student has to buy at least one ticket at day l_j . Help students to calculate the minimum amount of money they have to spend in order to go to the gym. The first line contains three integers n , q and k ( 1 <= n, q <= 300 ,000 ; 1 <= k <= n ) -- the number of days, the number of students and the number of days each ticket is still valid. The second line contains n integers a_1, a_2, ... , a_n ( 1 <= a_i <= 10^9 ) -- the cost of one ticket at the corresponding day. Each of the next q lines contains two integers l_i and r_i ( 1 <= l_i <= r_i <= n ) -- the segment of days the corresponding student want to visit the gym. For each student, print the minimum possible amount of money they have to spend in order to go to the gym at desired days. Let's see how each student have to spend their money: "...