V1

use crate::algo_lib::collections::array_2d::Array2D;

use crate::algo_lib::io::input::Input;
use crate::algo_lib::io::output::Output;
fn solve(input: &mut Input, out: &mut Output) {
    let n = input.usize();
    let k = input.usize();
    let q = input.usize();
    let mut a = input.vec::<i32>(n);
    a.extend_from_slice(&a.clone());
    let mut queries = vec![];
    for _ in 0..q {
        let l = input.usize() - 1;
        let mut r = input.usize();
        if l >= r {
            r += n;
        }
        queries.push(l..r);
    }
    let mut res = vec![i32::MIN; q];
    let mut answered = vec![false; q];
    loop {
        let mut min_r = usize::MAX;
        for i in 0..q {
            if res[i] == i32::MIN {
                min_r = min_r.min(queries[i].end);
            }
        }
        if min_r == usize::MAX {
            break;
        }
        let mid = min_r;
        let mut max_r = mid;
        let mut min_l = usize::MAX;
        for i in 0..q {
            if res[i] == i32::MIN && queries[i].start < mid {
                max_r = max_r.max(queries[i].end);
                min_l = min_l.min(queries[i].start);
            }
        }
        for use_center in 0..2 {
            let dp_right = {
                let len = max_r - mid;
                let mut dp = vec![Array2D::new(i32::MIN / 2, 2, k + 1); len + 1];
                dp[0][use_center][0] = 0;
                for i in 0..len {
                    let cur_val = a[mid + i];
                    for segm_open in 0..2 {
                        for j in 0..=k {
                            dp[i + 1][segm_open][j] = dp[i][segm_open][j];
                        }
                    }
                    for j in 0..k {
                        dp[i + 1][1][j] = dp[i + 1][1][j].max(dp[i][0][j] - cur_val);
                    }
                    for j in 0..k {
                        dp[i + 1][0][j + 1] = dp[i + 1][0][j + 1]
                            .max(dp[i][1][j] + cur_val);
                    }
                }
                dp
            };
            let dp_left = {
                let len = mid - min_l;
                let mut dp = vec![Array2D::new(i32::MIN / 2, 2, k + 1); len + 1];
                dp[0][use_center][0] = 0;
                for i in 0..len {
                    let cur_val = a[mid - 1 - i];
                    for segm_open in 0..2 {
                        for j in 0..=k {
                            dp[i + 1][segm_open][j] = dp[i][segm_open][j];
                        }
                    }
                    for j in 0..k {
                        dp[i + 1][1][j + 1] = dp[i + 1][1][j + 1]
                            .max(dp[i][0][j] + cur_val);
                    }
                    for j in 0..=k {
                        dp[i + 1][0][j] = dp[i + 1][0][j].max(dp[i][1][j] - cur_val);
                    }
                }
                dp
            };
            for i in 0..q {
                if answered[i] || queries[i].start >= mid {
                    continue;
                }
                let left_len = mid - queries[i].start;
                let right_len = queries[i].end - mid;
                let mut best = i32::MIN;
                let mut right_cnt_iter = k;
                for left_cnt in 0..=k {
                    while right_cnt_iter > 0
                        && (right_cnt_iter + left_cnt > k
                            || dp_right[right_len][0][right_cnt_iter] == i32::MIN / 2)
                    {
                        right_cnt_iter -= 1;
                    }
                    best = best
                        .max(
                            dp_left[left_len][0][left_cnt]
                                + dp_right[right_len][0][right_cnt_iter],
                        );
                }
                res[i] = res[i].max(best);
                if use_center == 1 {
                    answered[i] = true;
                }
            }
        }
    }
    for &x in res.iter() {
        out.println(x);
    }
}
pub(crate) fn run(mut input: Input, mut output: Output) -> bool {
    solve(&mut input, &mut output);
    output.flush();
    true
}

fn main() {
    let input = crate::algo_lib::io::input::Input::new_stdin();
    let mut output = crate::algo_lib::io::output::Output::new_stdout();
    run(input, output);
}