Meaning:

Give a n\times mn × The initial value of each position of the matrix is its number. It is required to support the following operations:

For each given point (x,y)(x,y), output the value of the position, and cycle the number at the following positions in the following matrix to the left by one bit:

(x,y),(x,y+1),(x,y+2),\cdots(x,m),(x+1,m),(x+2,m),\cdots(n,m)(x,y),(x,y+1),(x,y+2),⋯(x,m),(x+1,m),(x+2,m),⋯(n,m).

Practice:

First of all, start with the part.

We note that when ， n=1n=1 ， what we need to maintain is that each time we move the sequence cycle to the left, this can obviously balance the tree.

Then, let's consider the case where ， nn ， and ， mm ， are both large.

It doesn't seem to be possible to cycle left on a two-dimensional graph, but we can divide the operation into the following parts:

For the operations whose starting point is (x,y)(x,y), we find that it is equivalent to the splicing of the following operations:

1. In the − xx − row of the matrix, delete the − yy − number, and move all the − y+1y+1 − to the − m-1m − 1 − number of this column to the left by one bit;
2. Put a number at the end of the # xx # row of the matrix, and the value is the # xx # number in the last column of the original matrix;
3. In the last column of the matrix, delete the {xx} number, and move all the {x+1x+1} to {nn} numbers of the column to the left by one bit;
4. Put a number in the last column of the matrix, and the value is the number of {yy} in the {xx} row of the original matrix.

We were surprised to find that the first two operations are essentially equivalent to the last two operations, but on different columns / rows.

Inspired by this observation, we may be able to maintain {n+1n+1} sequences, each representing a row / column;

Then, for each sequence, we only need to maintain the following two operations:

1. Query the value of a location;
2. Delete a position and move all the numbers on the right one bit to the left, and then put a given new number on the last empty bit.

We found that deleting a certain number is easy to maintain. You can directly assign ， 00 ， and the difficulty lies in the left shift of other numbers.

At this time, there is a routine: we don't really need to maintain the move left operation,

For a sequence, we only need to maintain one 0101 sequence,

A position value of  11  represents the number of positions in the original sequence, and a value of  00  represents the number of positions in the original sequence.

In this case, the left shift operation is transformed into finding the left number kk ＾ 11 on the ＾ 0101 ＾ sequence,

Because every time we move left, we don't care. We query the value of position {xx},

It is equivalent to querying the value of the original sequence corresponding to the position of the xx ＾ 11th ＾ on the left of the ＾ 0101 ＾ sequence.

So, how can we quickly get the value of the original sequence corresponding to the position ＾ pp ＾ of each ＾ 11 ＾ in the sequence?

Obviously, when pp is less than the initial length of the original sequence, according to the meaning of the question, the value of this position is its number in the matrix,

We can calculate this directly; When pp is greater than the initial length of the original sequence, this number must be inserted later,

The sum of the numbers inserted later is equal to the operand multiplied by ＾ 22, so we can open a ＾ vector for each sequence,

In order to maintain the number inserted later, such spatial complexity is guaranteed.

To maintain the above {0101} sequence, we only need to dynamically open the point segment tree, because the initial sequence is all} 11.

As for the details, you can see the code. The code part refers to a problem solution in Luogu.

code:

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define LL long long
#define pii pair < int , int >
#define ckmax(a, b) ((a) = max((a), (b)))
#define ckmin(a, b) ((a) = min((a), (b)))
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
#define edg(i, v, u) for (int i = head[u], v = e[i].to; i; i = e[i].nxt, v = e[i].to)

using namespace std;

inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') f = ch == '-' ? -1 : 1, ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
    return x * f;
}

const int N (6e5 + 10);
const int M (2e7 + 10);

int tot;
int q, c;
int n, m;
int rt[N];
vector < LL > a[N];

struct Tree {
    int sum;
    int ch[2];
} t[M];

#define ls(p) t[p].ch[0]
#define rs(p) t[p].ch[1]
#define mid ((l + r) >> 1)
#define lsn ls(p), l, mid
#define rsn rs(p), mid + 1, r

void ins (int &p, int l, int r, int x) {
    if (!p) p = ++tot; t[p].sum++; if (l == r) return;
    if (x <= mid) ins (lsn, x); else ins (rsn, x);
}

int kth (int p, int l, int r, int k) {
    if (l == r) return l;
    int sl = mid - l + 1 - t[ls(p)].sum;
    if (k <= sl) return kth (lsn, k);
    return kth (rsn, k - sl);
}

LL shu (int x, LL val) {
    int k = kth (rt[n + 1], 1, c, x);
    ins (rt[n + 1], 1, c, k);
    LL res = (k <= n) ? (1ll * m * k) : a[n + 1][k - n - 1];
    return a[n + 1].pb (val ? val : res), res;
}

LL heng (int x, int y) {
    int k = kth (rt[x], 1, c, y);
    ins (rt[x], 1, c, k);
    LL res = (k < m) ? (1ll * (x - 1ll) * m + 1ll * k) : a[x][k - m];
    LL ttt = shu (x, res);
    return a[x].pb (ttt), res;
}

int main() {
    n = read(), m = read(), q = read();
    c = max (n, m) + q;
    rep (i, 1, q) {
        int x = read(), y = read();
        LL ans = (y ^ m) ? heng (x, y) : shu (x, 0);
        printf ("%lld\n", ans);
    }
    return 0;
}