222B.md (2788B)
1 Source: https://codeforces.com/problemset/problem/222/B 2 3 B. Cosmic Tables 4 5 time limit per test 6 7 3 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 The 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. 22 23 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: 24 25 * The query to swap two table rows; 26 * The query to swap two table columns; 27 * The query to obtain a secret number in a particular table cell. 28 29 As the main UCDHP module is critical, writing the functional of working with the table has been commissioned to you. 30 31 Input 32 33 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. 34 35 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* ≤ 106. 36 37 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. 38 39 * 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*); 40 * 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*); 41 * 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*). 42 43 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*. 44 45 Output 46 47 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. 48 49 Examples 50 51 Input 52 53 ``` 54 3 3 5 55 1 2 3 56 4 5 6 57 7 8 9 58 g 3 2 59 r 3 2 60 c 2 3 61 g 2 2 62 g 3 2 63 ``` 64 65 Output 66 67 ``` 68 8 69 9 70 6 71 ``` 72 73 Input 74 75 ``` 76 2 3 3 77 1 2 4 78 3 1 5 79 c 2 1 80 r 1 2 81 g 1 3 82 ``` 83 84 Output 85 86 ``` 87 5 88 ``` 89 90 Note 91 92 Let's see how the table changes in the second test case. 93 94 After the first operation is fulfilled, the table looks like that: 95 96 2 1 4 97 98 1 3 5 99 100 After the second operation is fulfilled, the table looks like that: 101 102 1 3 5 103 104 2 1 4 105 106 So the answer to the third query (the number located in the first row and in the third column) will be 5.