It is natural to think of sorting the queries first, according to their timestamps.

Now let’s look at the operations. Suppose we have \((x,y)\):

• Operation I changes it to \((y,-x)\)
• Operation II changes it to \((-y, x)\)
• Operation III changes it to \((2p-x,y)\)
• Operation IV changes it to \((x,2p-y)\)

Since the operations are applied to all points at the same time, we will not calculate the position of each point, instead, we want to know the final transform.

Operation I & II swaps \(x\) and \(y\), while changing the sign of one axis. Operation III & IV flips one axis and then adds \(2p\) to it. To handle all the operations, we will use five variables, \(swap\) denoting if \(x\) and \(y\) are swapped, \(s_x\) denoting the sign of the current \(x\) axis, \(s_y\) denoting the sign of the current \(y\) axis, \(c_x\) denoting the extra value for \(x\) and \(c_y\) denoting the extra value for \(y\).

Now we have:

• Operation I: \(swap\) is flipped, \(c_x\) and \(c_y\) is swapped, \(s_x\) and \(s_y\) is swapped, then \(s_y\) and \(c_y\) are flipped.
• Operation II: \(swap\) is flipped, \(c_x\) and \(c_y\) is swapped, \(s_x\) and \(s_y\) is swapped, then \(s_x\) and \(c_x\) are flipped.
• Operation III: \(s_x\) is flipped, and \(c_x\) is flipped then added \(2p\).
• Operation IV: \(s_y\) is flipped, and \(c_y\) is flipped then added \(2p\).

For each query, after applying enough operations, we can answer the query according to the five variables:

• If \(swap\) is false, the answer will be \((s_xx_0+c_x,s_yy_0+c_y)\)

• If \(swap\) is true, the answer will be \((s_xy_0+c_x,s_yx_0+c_y)\)

• Time complexity is \(\mathcal{O}(Q\log Q)\).

• Space complexity is \(\mathcal{O}(Q)\).

Source code:

use proconio::input;
use proconio::marker::Usize1;
use std::cmp::Ordering;

fn main() {
    input! {
        n: usize,
        points: [(i64, i64); n],
        m: usize,
    }

    let mut ops: Vec<(usize, i64)> = vec![];
    for _i in 0..m {
        input! {
            t: usize,
        }
        if t <= 2 {
            ops.push((t, 0));
        } else {
            input! {
                p: i64,
            }
            ops.push((t, p));
        }
    }

    input! {
        q: usize,
        queries: [(usize, Usize1); q],
    }

    let mut ans = vec![(0i64, 0i64); q];
    let mut order: Vec<usize> = (0..q).collect();
    order.sort_by(|a, b| if queries[*a].0 <= queries[*b].0 {
        Ordering::Less
    } else {
        Ordering::Greater
    });

    let mut swap = false;
    let mut sx = 1i64;
    let mut sy = 1i64;
    let mut cx = 0i64;
    let mut cy = 0i64;
    let mut op = 0usize;
    for i in order {
        let (a, b) = queries[i];
        while op < a {
            let (t, p) = ops[op];
            match t {
                1 => {
                    swap = !swap;
                    std::mem::swap(&mut cx, &mut cy);
                    std::mem::swap(&mut sx, &mut sy);
                    sy = -sy;
                    cy = -cy;
                },
                2 => {
                    swap = !swap;
                    std::mem::swap(&mut cx, &mut cy);
                    std::mem::swap(&mut sx, &mut sy);
                    sx = -sx;
                    cx = -cx;
                },
                3 => {
                    sx = -sx;
                    cx = p * 2 - cx;
                },
                4 => {
                    sy = -sy;
                    cy = p * 2 - cy;
                },
                _ => {

                }
            }
            op += 1;
        }
        if swap {
            ans[i] = (points[b].1 * sx + cx, points[b].0 * sy + cy);
        } else {
            ans[i] = (points[b].0 * sx + cx, points[b].1 * sy + cy);
        }
    }

    for i in 0..q {
        println!("{} {}", ans[i].0, ans[i].1);
    }
}