package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
)

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Buffer(make([]byte, 1024*1024), 10*1024*1024)
	scanner.Split(bufio.ScanWords)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	readInt := func() int {
		scanner.Scan()
		res := 0
		for _, b := range scanner.Bytes() {
			res = res*10 + int(b-'0')
		}
		return res
	}

	n := readInt()
	q := readInt()
	k := readInt()

	a := make([]int, n+2)
	for i := 1; i <= n; i++ {
		a[i] = readInt()
	}
	a[n+1] = 0

	stack := make([]int, 0, n+1)
	R := make([]int, n+2)
	for i := 1; i <= n; i++ {
		for len(stack) > 0 && a[stack[len(stack)-1]] >= a[i] {
			R[stack[len(stack)-1]] = i
			stack = stack[:len(stack)-1]
		}
		stack = append(stack, i)
	}
	for _, i := range stack {
		R[i] = n + 1
	}
	R[n+1] = n + 1

	children := make([][]int, n+2)
	for i := 1; i <= n; i++ {
		children[R[i]] = append(children[R[i]], i)
	}

	up := make([][]int, n+2)
	for i := 0; i <= n+1; i++ {
		up[i] = make([]int, 20)
	}
	for i := 1; i <= n+1; i++ {
		up[i][0] = R[i]
	}
	for j := 1; j < 20; j++ {
		for i := 1; i <= n+1; i++ {
			up[i][j] = up[up[i][j-1]][j-1]
		}
	}

	Q := make([]int, n+2)
	V := make([]int, n+2)
	Delta := make([]int64, n+2)
	for i := 1; i <= n; i++ {
		Q[i] = (R[i] - 1) / k
		V[i] = (R[i] - 1) % k
		Delta[i] = int64(a[i]) - int64(a[R[i]])
	}

	P1 := make([]int64, n+2)
	in := make([]int, n+2)
	outTime := make([]int, n+2)
	timer := 0

	var dfs func(int)
	dfs = func(node int) {
		timer++
		in[node] = timer
		for _, child := range children[node] {
			P1[child] = P1[node] + int64(Q[child])*Delta[child]
			dfs(child)
		}
		outTime[node] = timer
	}
	dfs(n + 1)

	bit := make([]int64, timer+2)
	add := func(idx int, val int64) {
		for i := idx; i <= timer; i += i & -i {
			bit[i] += val
		}
	}
	queryBIT := func(idx int) int64 {
		var sum int64
		for i := idx; i > 0; i -= i & -i {
			sum += bit[i]
		}
		return sum
	}

	nodesByV := make([][]int, k)
	for i := 1; i <= n; i++ {
		nodesByV[V[i]] = append(nodesByV[V[i]], i)
	}

	type Query struct {
		l, r, id int
	}
	queries := make([]Query, q)
	for i := 0; i < q; i++ {
		queries[i] = Query{l: readInt(), r: readInt(), id: i}
	}
	sort.Slice(queries, func(i, j int) bool {
		return queries[i].l%k < queries[j].l%k
	})

	ans := make([]int64, q)
	currentM := 0

	for _, qry := range queries {
		m := qry.l % k
		for currentM < m {
			for _, node := range nodesByV[currentM] {
				add(in[node], Delta[node])
				add(outTime[node]+1, -Delta[node])
			}
			currentM++
		}

		u := qry.l
		for j := 19; j >= 0; j-- {
			if up[u][j] != 0 && up[u][j] <= qry.r {
				u = up[u][j]
			}
		}

		term1 := -int64(a[qry.l]) * floorDiv(qry.l-1-m, k)
		term2 := int64(a[u]) * floorDiv(qry.r-m, k)
		sum1 := P1[qry.l] - P1[u]
		sum2 := queryBIT(in[qry.l]) - queryBIT(in[u])

		ans[qry.id] = term1 + term2 + sum1 - sum2
	}

	for i := 0; i < q; i++ {
		fmt.Fprintln(out, ans[i])
	}
}

func floorDiv(a, b int) int64 {
	if a >= 0 {
		return int64(a / b)
	}
	return int64((a - b + 1) / b)
}