use proconio::input;

#[derive(Debug, Clone, Copy, Eq, PartialEq)]
enum Dir {
    Upward,
    Downward,
}

#[derive(Debug, Clone, Copy, Eq, PartialEq)]
enum State {
    Point(i32),
    Interval(i32, i32, i32),
}

impl State {
    pub fn shift(self, dr: i32, ex: i32, dir: Dir) -> Self {
        match self {
            State::Point(x) => match dir {
                Dir::Upward => State::Point(ex.min(x + dr)),
                Dir::Downward => State::Point(0.max(x - dr)),
            },
            State::Interval(x, y, d) => match dir {
                Dir::Upward => {
                    let y = y + dr;
                    if ex <= y {
                        State::Point(ex)
                    } else if ex <= y + d {
                        State::Interval(x, y, d - ((y + d) - ex))
                    } else {
                        State::Interval(x, y, d)
                    }
                }
                Dir::Downward => {
                    let y = y - dr;
                    if y + d <= 0 {
                        State::Point(0)
                    } else if y <= 0 {
                        State::Interval(x - y, 0, d + y)
                    } else {
                        State::Interval(x, y, d)
                    }
                }
            },
        }
    }

    pub fn get(&self, z: i32, ex: i32) -> i32 {
        assert!(0 <= z && z <= ex);
        match self {
            State::Point(x) => *x,
            State::Interval(x, y, d) => y + (z - x).max(0).min(*d),
        }
    }
}

fn main() {
    input!(
        ex: i32,
        n: usize,
        r: [usize; n],
        q: usize,
        ta: [(usize, usize); q]
    );
    let mut states = vec![(0, State::Interval(0, 0, ex)); n + 1];
    for i in 0..n {
        let prv = states[i].0;
        let state = states[i].1.shift(
            (r[i] - prv) as i32,
            ex,
            if i % 2 == 0 {
                Dir::Downward
            } else {
                Dir::Upward
            },
        );
        states[i + 1] = (r[i], state);
    }

    for (t, a) in ta {
        let mut l = 0;
        let mut r = n + 1;
        while 1 < r - l {
            let c = l + (r - l) / 2;
            if states[c].0 <= t {
                l = c;
            } else {
                r = c;
            }
        }
        let dt = t - states[l].0;
        let state = states[l].1.shift(
            dt as i32,
            ex,
            if l % 2 == 0 {
                Dir::Downward
            } else {
                Dir::Upward
            },
        );
        println!("{}", state.get(a as i32, ex));
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_shift() {
        // Upward
        assert_eq!(
            State::Interval(5, 10, 20).shift(5, 40, Dir::Upward),
            State::Interval(5, 15, 20)
        );
        assert_eq!(
            State::Interval(5, 10, 20).shift(10, 40, Dir::Upward),
            State::Interval(5, 20, 20)
        );
        assert_eq!(
            State::Interval(5, 10, 20).shift(15, 40, Dir::Upward),
            State::Interval(5, 25, 15)
        );
        assert_eq!(
            State::Interval(5, 10, 20).shift(25, 40, Dir::Upward),
            State::Interval(5, 35, 5)
        );
        assert_eq!(
            State::Interval(5, 10, 20).shift(30, 40, Dir::Upward),
            State::Point(40)
        );
        // Downward
        assert_eq!(
            State::Interval(5, 10, 20).shift(5, 40, Dir::Downward),
            State::Interval(5, 5, 20)
        );
        assert_eq!(
            State::Interval(5, 10, 20).shift(10, 40, Dir::Downward),
            State::Interval(5, 0, 20)
        );
        assert_eq!(
            State::Interval(5, 10, 20).shift(15, 40, Dir::Downward),
            State::Interval(10, 0, 15)
        );
        assert_eq!(
            State::Interval(5, 10, 20).shift(25, 40, Dir::Downward),
            State::Interval(20, 0, 5)
        );
        assert_eq!(
            State::Interval(5, 10, 20).shift(30, 40, Dir::Downward),
            State::Point(0)
        );
    }

    #[test]
    fn test_get() {
        assert_eq!(State::Interval(5, 10, 20).get(0, 40), 10);
        assert_eq!(State::Interval(5, 10, 20).get(5, 40), 10);
        assert_eq!(State::Interval(5, 10, 20).get(10, 40), 15);
        assert_eq!(State::Interval(5, 10, 20).get(20, 40), 25);
        assert_eq!(State::Interval(5, 10, 20).get(25, 40), 30);
        assert_eq!(State::Interval(5, 10, 20).get(35, 40), 30);
        assert_eq!(State::Interval(5, 10, 20).get(40, 40), 30);
    }
}


Measured memory_bytes: 9484