Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Cosmic Tables

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThe Free Meteor Association (FMA) has got a problem: as meteors are moving, the Universal Cosmic Descriptive Humorous Program (UCDHP) needs to add a special module that would analyze this movement.

UCDHP stores some secret information about meteors as an *n* × *m* table with integers in its cells. The order of meteors in the Universe is changing. That's why the main UCDHP module receives the following queries:

- The query to swap two table rows;
- The query to swap two table columns;
- The query to obtain a secret number in a particular table cell.

As the main UCDHP module is critical, writing the functional of working with the table has been commissioned to you.

Input

The first line contains three space-separated integers *n*, *m* and *k* (1 ≤ *n*, *m* ≤ 1000, 1 ≤ *k* ≤ 500000) — the number of table columns and rows and the number of queries, correspondingly.

Next *n* lines contain *m* space-separated numbers each — the initial state of the table. Each number *p* in the table is an integer and satisfies the inequality 0 ≤ *p* ≤ 10^{6}.

Next *k* lines contain queries in the format "*s*_{i} *x*_{i} *y*_{i}", where *s*_{i} is one of the characters "с", "r" or "g", and *x*_{i}, *y*_{i} are two integers.

- If
*s*_{i}= "c", then the current query is the query to swap columns with indexes*x*_{i}and*y*_{i}(1 ≤*x*,*y*≤*m*,*x*≠*y*); - If
*s*_{i}= "r", then the current query is the query to swap rows with indexes*x*_{i}and*y*_{i}(1 ≤*x*,*y*≤*n*,*x*≠*y*); - If
*s*_{i}= "g", then the current query is the query to obtain the number that located in the*x*_{i}-th row and in the*y*_{i}-th column (1 ≤*x*≤*n*, 1 ≤*y*≤*m*).

The table rows are considered to be indexed from top to bottom from 1 to *n*, and the table columns — from left to right from 1 to *m*.

Output

For each query to obtain a number (*s*_{i} = "g") print the required number. Print the answers to the queries in the order of the queries in the input.

Examples

Input

3 3 5

1 2 3

4 5 6

7 8 9

g 3 2

r 3 2

c 2 3

g 2 2

g 3 2

Output

8

9

6

Input

2 3 3

1 2 4

3 1 5

c 2 1

r 1 2

g 1 3

Output

5

Note

Let's see how the table changes in the second test case.

After the first operation is fulfilled, the table looks like that:

2 1 4

1 3 5

After the second operation is fulfilled, the table looks like that:

1 3 5

2 1 4

So the answer to the third query (the number located in the first row and in the third column) will be 5.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/20/2021 19:01:00 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|