11305 - Array Row Swapping   

Status  |  Limits Submit

Description

This problem might be the most challenging one in this contest. Challenge this one when you are ready.

In this problem, an NxN array is given. After applying several tiems of "Row Swappings", you have to print the final value at specified coordinate.

The array is composed of N rows, and each row has N values.

Row 0:    a0,0     a0,1     a0,2     a0,3     a0,4    ...    a0,N-1  
Row 1:    a1,0     a1,1     a1,2     a1,3     a1,4    ...    a1,N-1  
Row 2:    a2,0     a2,1     a2,2     a2,3     a2,4    ...    a2,N-1  
Row 3:    a3,0     a3,1     a3,2     a3,3     a3,4    ...    a3,N-1  
​Row 4:    a4,0     a4,1     a4,2     a4,3     a4,4    ...    a4,N-1  
                 .          .          .          .          .      ...       .    
Row N-1:   aN-1,0  aN-1,1  aN-1,2  aN-1,3  aN-1,4  ...  aN-1,N-1  

A "Row Swapping" in this problem is to "swap all the values in the K rows following row S and row T". For example, if we "swap all the values in the 2 rows following row 3 and row 0", the result will be:

(new) Row 0:    a3,0     a3,1     a3,2     a3,3     a3,4    ...    a3,N-1  
​(new) Row 1:    a4,0     a4,1     a4,2     a4,3     a4,4    ...    a4,N-1  
           Row 2:    a2,0     a2,1     a2,2     a2,3     a2,4    ...    a2,N-1  
(new) Row 3:    a0,0     a0,1     a0,2     a0,3     a0,4    ...    a0,N-1  
(new) Row 4:    a1,0     a1,1     a1,2     a1,3     a1,4    ...    a1,N-1  
                            .          .          .          .          .      ...       .    
          Row N-1:   aN-1,0  aN-1,1  aN-1,2  aN-1,3  aN-1,4  ...  aN-1,N-1  

The initial values of the array are generated by a simple rule. The first row is filled by the sequence 1 to N, the second row is the right-rotation (shift 1) of the first row, and the following rows are the right-rotation of their previous rows. Taking N=7 as our example, the initial values of the array are:
 1  2  3  4  5  6  7 
 7  1  2  3  4  5  6 
 6  7  1  2  3  4  5 
 5  6  7  1  2  3  4 
 4  5  6  7  1  2  3 
 3  4  5  6  7  1  2 
 2  3  4  5  6  7  1 

Suppose 2 row swapings {K, S, T}, which are {2, 3, 0} and {3, 1, 4}, are applied to this array. After the row swapping {2, 0, 3} is applied, the array becomes:

 5  6  7  1  2  3  4 
 4  5  6  7  1  2  3 
 6  7  1  2  3  4  5 
 1  2  3  4  5  6  7 
 7  1  2  3  4  5  6 
 3  4  5  6  7  1  2 
 2  3  4  5  6  7  1 
 
After the row swapping {3, 1, 4} is applied, the fnal result is:
 5  6  7  1  2  3  4 
 7  1  2  3  4  5  6 
 3  4  5  6  7  1  2 
 2  3  4  5  6  7  1 
 4  5  6  7  1  2  3 
 6  7  1  2  3  4  5 
 1  2  3  4  5  6  7 

Suppose the specified coordinate is [2][3], the final values at the coordinate will be printed, which is the value 6:

 5  6  7  1  2  3  4 
 7  1  2  3  4  5  6 
 3  4  5  6  7  1  2 
 2  3  4  5  6  7  1 
 4  5  6  7  1  2  3 
 6  7  1  2  3  4  5 
 1  2  3  4  5  6  7 

Input

The first line is an integer X, 1 ≤ X ≤ 10. There will be X independent cases in the input.

In each case, the first line contains 2 integers N and M, 2 ≤ N ≤ 1000 and 0 ≤ M ≤ 1000, which denote the array size and the number of swappings. Each of the following M lines contains 3 integers K, S and T, which means to "swap all the values in the K rows following row S and row T". After these swappings, the final line in the case contains 2 integers R and C, which is the specified coordinate that we have to report its final value.

In each row swapping, there is no overlapping between the 2 ranges to be swapped. And these ranges will never excceed the array size.

Output

For each case, there is one line contains only one integer, which is the final value at the specified coordinate. There will be X values with X newline symbols in the output.

Sample Input  Download

Sample Output  Download

Tags




Discuss