小w的矩阵前k大元素
题号：NC25109
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

小w现在有两个长度为n的数组a[ ]和长度为m的数组b[ ]，现在小w用它们两个构造了一个二维数组c[ ][ ]。

c中的每个元素c[i][j]被定义为c[i][j]=a[i]+b[j]。其中i表示行，j表示列，数组的下标均从0开始计算。

现在小w把这个数组画到了一张纸上面。例如当a[ ]={1,2,3,4,5,7}，b[ ]={1,2,3,4,5}时。画在纸上的数组如图所示

现在小w在这个数组(0,0)的位置放置了一个棋子。小w准备进行q次操作。

1、将棋子向右移动dy步，如果移动dy步之后越出了棋盘，只需将棋子移动到棋盘的最边缘即可。即(x,y)->(x,min(m-1,y+dy))。

2、将棋子向下移动dx步，如果移动dx步之后越出了棋盘，只需将棋子移动到棋盘的最边缘即可。即(x,y)->(min(n-1,x+dx),y)。

3、查询从(0,0)到(x,y)的这个子矩形中，升序排列的前k个元素是什么，请你输出升序k个整数。输入数据保证k不多于当前子矩形中的元素个数，同时保证所有查询k的总和不多于。

输入描述:

第一行输入三个整数n,m,q,，分别表示a数组的长度，b数组的长度，操作的总次数。
接下来一行n个整数a[i]表示a数组的第i个元素。
接下来一行m个整数b[i]表示b数组的第i个元素。

接下来q行，每行一个字符及一个操作参数。

当输入的字符为'R'时，表示棋子向右移动，输入的参数dy表示向右移动的步数。
当输入的字符为'D'时，表示棋子向下移动，输入的参数dx表示向下移动的步数。
当输入的字符为'Q'时，查询从(0,0)到(x,y)的这个子矩形中，升序排列的前k个元素是什么，请你升序输出k个整数。输入数据保证k不多于当前子矩形中的元素个数，同时保证所有查询k的总和不多于。
输入数据保证至少进行了1次查询操作。

输出描述:

对于每个Q，按照升序顺序输出k个整数。输出的整数之间用空格隔开，行末不允许有多余空格。
示例1

输入

复制 
6 5 10
1 2 3 4 5 7
1 2 3 4 5
Q 1
R 1
D 1
Q 4
R 1
D 1
Q 7
R 100
D 100
Q 30

输出

复制 
2
2 3 3 4
2 3 3 4 4 4 5
2 3 3 4 4 4 5 5 5 5 6 6 6 6 6 7 7 7 7 8 8 8 8 9 9 9 10 10 11 12

说明

第一次查询时，棋子在(0,0)，子矩阵升序排列的前1个是2
第二次查询时，棋子在(1,1)，子矩阵升序排列的前4个是2,3,3,4
第三次查询时，棋子在(2,2)，子矩阵升序排列的前7个是2,3,3,4,4,4,5
第四次查询时，棋子在(5,4)，子矩阵升序排列的前30个是2,3,3,4,4,4,5,5,5,5,6,6,6,6,6,7,7,7,7,8,8,8,8,9,9,9,10,10,11,12