基础排序算法练习题
时间限制：12s 空间限制：512MB
题目描述
OI小园丁ZZX最近在XJOI上夜以继日地学习编程基础知识，刷初级训练题库。在无压力AC了“圆的周长与面积”、“二位数加法口算训练程序”等题之后，他遇到了这样一道难题：
“输入n个数a[1], a[2], ..., a[n]，请将它们升序排序后输出。”
ZZX苦思冥想，不知所措，便去请教德高望重的OI老司机JRY。
JRY贴给他一段超自然的神秘代码，说：
“你把这段东西塞进程序里，然后每次调用magic(left, right)这个函数，它就会用O(1)时间将a[left], a[left+1], ..., a[right]原地升序排序。”
“劲啊”
“但是啊由于一些奇怪的原因，你不能直接调用magic(1,n)，否则程序会RE”
“wori?”
不过这难不倒聪明伶俐的ZZX。经过一番思索，他写出了这样一段程序：
input(a[1], a[2], ..., a[n]);
magic(left_1, right_1);
magic(left_2, right_2);
...
magic(left_m, right_m);
output(a[1], a[2], ..., a[n]);
JRY看了这段代码，批判道：“Native! 看我用遗传算法造个数据分分钟把你卡掉”
然而ZZX并不信服，他打算把程序交到XJOI上，用评测结果来打JRY的脸。
由于XJOI管理员Ginger最近忙于打Geometry Dash，没有工夫来修理狗带了的评测姬。因此评测任务落到了你的头上。
这道题共有q个测试点。你需要对于每一个测试点，判断ZZX的程序是否输出了正确的排序结果。
输入格式
第一行三个整数n, m, q。
接下来m行按顺序给出了ZZX的程序中每条指令的参数left_i, right_i。
接下来q行，每行表示一个测试点，包含空格隔开的n个非负整数a[1], a[2], ..., a[n]。
1 ≤ n ≤ 1500 , 1 ≤ m ≤ 1000000 , 1 ≤ q ≤ 1500;
1 ≤ left_i ≤ right_i ≤ n, right_i - left_i + 1 < n; 0 ≤ a[i] ≤ 1500。
输出格式
对于每个测试点输出一行，如果ZZX的程序能将这个数列正确排序，输出"AC"，否则输出"WA"。
样例输入
6 3 2 1 3 3 6 1 3 4 2 2 3 0 7 5 3 8 2 1 9
样例输出
AC WA 样例说明 对于第一个测试点： 4 2 2 3 0 7 -> [2 2 4] 3 0 7 -> 2 2 [0 3 4 7] -> [0 2 2] 3 4 7，正确。 对于第二个测试点： 5 3 8 2 1 9 -> [3 5 8] 2 1 9 -> 3 5 [1 2 8 9] -> [1 3 5] 2 8 9，错误。
提示
没有写明提示
题目来源
By Jcvb