This is an old revision of the document!
# 二哥的逃离
## Description
二哥突然学会了Blink（闪烁）魔法，但他也因此被伊利丹追杀。在慌乱之间，二哥冲入了迷宫的入口，被传送进入了远古之迷宫。
“你将一分为三，两个分身，一个本体。分身不能走动只能使用魔法，而本体则会被束缚而完全无法动弹，他们会被传送至不同的地方。但是作为补偿，你可以在开始行动之前，决定自己的本体是三者中的哪一个。当三者重新汇聚，束缚将被打破，你也自然脱离了迷宫。”二哥在恍惚之间听到了这样一番话。
迷宫是一个矩形，被划分成了\\( N \\)行\\( M \\)列共\\(N \times M\\)个小格。迷宫左上角小格的坐标定义为\\((1,1)\\)，右上角小格的坐标定义为\\((1,M)\\)，右下角小格的坐标定义为\\((N,M)\\)。两小格\\((a,b)\\)，\\((c,d)\\)之间的距离定义为\\(|a-c|+|b-d|\\)（即曼哈顿距离）。
二哥唯一能做的事就是使用闪烁魔法，来使得自己的两个分身尽快与本体会合。不过正如同之前听到的那句话，只有分身能够使用闪烁魔法进行移动。
由于二哥的魔法水平有限，他每次使用魔法只能让分身移动到一定距离以内的任意一个小格并且在进行移动之前需要一段时间进行准备（吟唱魔法）。而在这个神秘的迷宫里，二哥发现他的分身在每个小格所能移动的距离和吟唱时间是不同的。
在 \\( \(i,j\) \\)小格上能移动的最大距离为: \\( A_{i,j} \\)
需要的准备时间为: \\( B_{i,j} \\)
更加悲剧的是，二哥每次只能让一个分身进行吟唱魔法并移动，移动完毕之后才能进行下一次吟唱。
现在，二哥想知道，自己至少要花多少时间才能逃脱出迷宫。
注意：迷宫的外部是虚无，二哥不会通过闪烁移动到迷宫之外。
## Input Format
第一行两个整数\\( N,M \\)
接下来两个\\( N \times M \\) 的自然数矩阵: \\( A_{i,j} \\) , \\( B_{i,j} \\)
接下来六个数\\(Xx,Xy,Yx,Yy,Zx,Zy\\)，表示本体和两个分身的坐标。
## Output Format
输出两行第一行一个字符\\( X,Y\\)或\\( Z \\)，表示以哪一个为本体。
第二行一个整数，表示最短时间。
若无法逃出迷宫，则只输出一行“NO”（不带引号）。
## Sample Input
4 4 0 0 0 0 1 2 2 0 0 2 2 1 0 0 0 0 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 2 1 3 4 2 2
## Sample Output
Z 15
## About Test Data
对于20%的数据：\\( 1 \leq n,m \leq 10 \\)。
对于50%的数据：\\( 1 \leq n,m \leq 100 \\) \\( 1 \leq B_{i,j} \leq 30 \\)。
对于100%的数据：\\( 1 \leq n,m \leq 100 \\)
\\( 1 \leq B_{i,j} \leq 100 \\)
\\( 1 \leq A_{i,j} \leq 10^9 \\)
# 体育节之战
## Description
这次体育节多了一个新项目，神还没有确定它的名字，不过他在人间的代言人已经知道了一些关于这个项目的内容：
\\(n\\)个人，每个人有个强度值\\(a_i\\)(编号从1开始)，最开始的时候大家都不认识。然后有\\(m\\)次冲突发生，每次冲突发生在2个不认识的人之间(如果两个人本来就认识，则不发生冲突)，这时双方各自会找自己所认识的人中最强的人出来决斗，经过决斗之后他们就互相认识了（并且他们原本认识的人现在都互相认识了）。决斗后，参加决斗的胜者的强度值会减半（向下取整）。
神想知道对于每次决斗，参与决斗的人所认识的所有人中最大的强度值。希望你能写一个程序帮他解决这个问题。
## Input Format
输入共有\\(n + m + 2\\)行。
第\\(1\\)行有\\(1\\)个整数\\(n\\)，表示参与这个项目的人数
第\\(2\\)到\\(n + 1\\)行每行有\\(1\\)个整数，分别表示每个人的强度值。
第\\(n + 2\\)行是一个整数\\(m\\)。
第\\(n + 3\\)到\\(m + n + 2\\)行描述\\(m\\)组询问，即冲突双方的编号
## Output Format
输出\\(m\\)行，每行是对于询问的回答(参与决斗的人所认识的所有人中最大的强度值)。
如果询问的两个人本来就认识，那么输出-1
## Sample Input
5 20 16 10 10 4 5 2 3 3 4 3 5 4 5 1 5
## Sample Output
8 5 5 -1 10
## About Test Data
对于30%的数据，\\(1 \leq m, n \leq 1000\\)。
对于70%的数据，\\(1 \leq n \leq 100000, 1 \leq m \leq 1000\\)。
对于100%的数据，\\(1 \leq n \leq 100000, 1 \leq m \leq 100000\\)。
# 配对 I
## Description
DS接到一个任务，这个任务有很多部分，每一个部分需要两个人完成，自然就要进行配对。
本次配对的具体要求教务处已经下发：
1) 一共\\( 2 \times N \\)个人，分为两个队伍，每队\\( N \\)人，每个人都有一个工作能力评估值（可以相同）。总共需要配出\\( N \\)对，每对两个人。
2) 每个人可以被配对多次，每一对中的两个人分别来自不同队伍。
3) 要求中提到，需要得到工作能力评估值之和最小的\\( N \\)对。
请你帮忙进行配对。
## Input Format
输入共有三行。
第一行一个整数\\( N \\)，意义如上。
第二行有\\( N \\)个整数，分别表示第一个队伍中每个人的工作能力评估值。
第三行有\\( N \\)个整数，分别表示第二个队伍中每个人的工作能力评估值。
## Output Format
共\\( N \\)行，每行一个整数，表示每一对的工作能力评估值之和。
按照升序输出。
## Sample Input
4 2 7 4 5 8 3 1 4
## Sample Output
3 5 5 6
## About Test Data
对于30%数据 \\(1 \leq N \leq 800\\)。
对于100%数据 \\(1 \leq N \leq 200,000\\)。
所有工作能力评估值\\(\leq 100,000,000\\)。
样例解释：
2+1, 2+3, 4+1, 2+4