The 5th FanRuan Cup Southeast University Programming Contest （Winter）
A. rain（easy version）
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

简单版和困难版的唯一区别在于对 $$$k$$$ 的约束不同。

下雨了！

上帝管理了 $$$10^9$$$ 个城市，这些城市的编号从 $$$1$$$ 到 $$$10^9$$$，并按从左到右的顺序分布在一条直线上。一共有 $$$n$$$ 个降雨安排，每个安排表示为 $$$l,r$$$，代表编号在 $$$l$$$ 到 $$$r$$$ 之间的所有城市发生了一次降雨。

如果一个城市在短时间内降雨次数超过 $$$k$$$ 次，就会引发洪水。作为上帝，并不希望发生洪水，因此上帝想知道在任何一个城市的降雨次数都不超过 $$$k$$$ 次的情况下，所有城市的降雨次数之和的最大值是多少。

Input

第一行，一个整数 $$$t(1\le t \le 200)$$$，代表数据组数。

对于每组数据： 第一行，两个整数 $$$n,k(1\le n\le 200;1\le k \le \min(n,2))$$$，代表降雨安排的个数和一个城市降雨次数上限。 接下来连续的 $$$n$$$ 行，每行两个整数 $$$l,r(1\le l\le r\le 10^9)$$$，代表一次降雨安排。

保证在同一测试点内的 $$$n$$$ 的总和不超过 $$$200$$$。

Output

对于每组数据，输出一行整数代表所有城市的降雨次数和的最大值是多少。

Example
Input
3
5 2
1 3
2 6
1 9
4 5
5 10
5 1
1 10
1 9
3 6
2 7
5 7
1 1
1 1000000000
Output
18
10
1000000000

B. rain（hard version）
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

简单版和困难版的唯一区别在于对 $$$k$$$ 的约束不同。

下雨了！

上帝管理了 $$$10^9$$$ 个城市，这些城市的编号从 $$$1$$$ 到 $$$10^9$$$，并按从左到右的顺序分布在一条直线上。一共有 $$$n$$$ 个降雨安排，每个安排表示为 $$$l,r$$$，代表编号在 $$$l$$$ 到 $$$r$$$ 之间的所有城市发生了一次降雨。

如果一个城市在短时间内降雨次数超过 $$$k$$$ 次，就会引发洪水。作为上帝，并不希望发生洪水，因此上帝想知道在任何一个城市的降雨次数都不超过 $$$k$$$ 次的情况下，所有城市的降雨次数之和的最大值是多少。

Input

第一行，一个整数 $$$t(1\le t \le 200)$$$，代表数据组数。

对于每组数据：

第一行，两个整数 $$$n,k(1\le k\le n\le 200)$$$，代表降雨安排的个数和一个城市降雨次数上限。 接下来连续的 $$$n$$$ 行，每行两个整数 $$$l,r(1\le l\le r\le 10^9)$$$，代表一次降雨安排。

保证在同一测试点内的 $$$n$$$ 的总和不超过 $$$200$$$。

Output

对于每组数据，输出一行整数代表所有城市的降雨次数和的最大值是多少。

Example
Input
5
5 2
1 3
2 6
1 9
4 5
5 10
5 1
1 10
1 9
3 6
2 7
5 7
1 1
1 1000000000
7 5
1 8
2 15
3 4
2 3
6 10
2 6
8 11
7 3
1 8
2 15
3 4
2 3
6 10
2 6
8 11
Output
18
10
1000000000
40
31

C. There are many books and books
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

志愿时长 400h！

你在图书馆担任图书管理员，在书架上有一些书，它们的编号为 $$$1$$$ 或 $$$2$$$，你需要改变书的顺序，使得编号相同的书被放在一起。 在你的每次操作中，你可以把一本书移动到书架的开头或者把一本书移动到书架的末尾，其它书的相对位置不会发生改变。 请问为了使得书架上编号相同的书被放在一起，你需要进行最少的移动次数为多少。

Input

第一行，一个整数 $$$t(1\le t\le 10^4)$$$，代表数据组数。

对于每组数据： 第一行，一个整数 $$$n(1\le n \le 2·10^5)$$$，代表书的数量。 第二行，$$$n$$$ 个整数 $$$a(1\le a\le2)$$$，代表每本书的编号。

保证同一测试点内的 $$$\sum n \le 2·10^5$$$

Output

对于每组数据，输出一个整数代表为了使得书架上编号相同的书被放在一起，你需要进行最少的移动次数的数量。

Example
Input
5
4
1 1 2 2
4
2 1 1 2
5
1 2 1 2 2
7
1 2 1 1 1 2 1
1
2
Output
0
1
1
2
0

D. We need more and more OR numbers
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

给定一个长度为 $$$n$$$ 的序列 $$$a$$$，序列中的数字都是正整数，你需要完成一段代码，完成以下两种操作：

$$$1$$$ $$$l$$$ $$$r$$$：将序列中所有下标范围为 $$$[l,r](1\le l \le r\le n)$$$ 的数字变成它的或数。

$$$2$$$ $$$pos$$$：询问当前下标为 $$$pos$$$ 的数字是多少。

一个数字的或数是指将一个正整数的的十进制的表示形式每个数位按位或操作之后的结果，例如，数字 $$$25_{10}$$$ 的或数就是 $$$7_{10}$$$，因为 $$$2_{10}\ OR\ 5_{10}=7_{10}$$$。

举个例子，令 $$$fOR(x)$$$ 代表 $$$x$$$ 的或数，那么 $$$fOR(11)=1,fOR(45)=5,fOR(14)=5,fOR(520)=7$$$。

Input

第一行，一个整数 $$$t(1\le t \le 10^5)$$$，代表数据组数。

对于每组数据：

第一行，一个整数 $$$n(1\le n \le 5·10^5)$$$，代表序列中数字的数量。

第二行，$$$n$$$ 个整数 $$$a(1\le a \le 10^9)$$$，代表这个序列。 第三行，一个整数 $$$q(1\le q \le 5·10^5)$$$，代表操作次数。

接下来的 $$$q$$$ 行，每行为一个题目中给出的操作。

保证在同一测试点内的 $$$\sum n \le 10^6;\sum q \le 10^6$$$。

Output

对于每个第 $$$2$$$ 种询问，输出一行整数表示答案。

Example
Input
2
6
11 45 14 520 1314 12345678
11
1 1 3
2 4
2 2
1 3 6
2 6
2 2
2 1
1 4 4
2 3
2 4
2 5
3
2 4 6
4
1 1 3
2 1
2 2
2 3
Output
520
5
15
5
1
5
7
7
2
4
6

E. 不减的数组
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

DingDing 给了你一个长度为 $$$n$$$ 的数组 $$$a$$$ 和一个大于 $$$1$$$ 的正整数 $$$k$$$，你可以对数组 $$$a$$$ 中任何一个元素进行任意次如下操作:

$$$$$$ a_i:=\lfloor \frac{a_i}{k}\rfloor $$$$$$

其中 $$$\lfloor b\rfloor$$$ 的意思是对于 $$$b$$$ 向 $$$0$$$ 取整，例如 $$$\lfloor \frac{7}{3}\rfloor=2$$$，$$$\lfloor -\frac{4}{3}\rfloor=-1$$$。

他想问你，要使得数组单调不减，你最少需要使用多少次操作。

Input

第一行，一个整数 $$$t(1\le t \le 10^4)$$$ ，代表数据组数。

对于每组数据：

第一行，两个整数 $$$n,k(1\le n \le 2·10^5;2\le k \le 10^9)$$$，代表数组 $$$a$$$ 的长度。

第二行，一个长度为 $$$n$$$ 的数组 $$$a$$$，数组中每个数字 $$$a_i$$$ 满足 $$$-10^9\le a_i\le 10^9$$$。

保证在同一测试点内的 $$$\sum n\le 2·10^5$$$。

Output

对于每组数据，输出一行整数代表你使得数组单调不减的最少操作次数。

事实上，可以证明，在有限的操作次数内，一定存在一种方式，使得数组最后单调不减。

Example
Input
4
5 2
-7 0 1 3 4
4 3
1 7 3 2
5 100
99 -98 101 0 -100
6 6
1 1 -4 -5 1 4
Output
0
4
6
4

F. 乘法与加法
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

给你两个长度为 $$$n$$$ 的数组 $$$a,b$$$。

令 $$$f(x,y,k)$$$ 表示在最多进行 $$$k$$$ 次赋值操作 $$$a_i:=b_i(1\le i\le n)$$$ 的情况下 $$$\sum_{i=x}^y\sum_{j=x}^y a_i\times a_j-\sum_{i=x}^y\sum_{j=x}^y (a_i+a_j)$$$ 的最大值。

你需要对于 $$$q$$$ 个独立的提问的 $$$x,y,k$$$ 分别求出 $$$f(x,y,k)$$$ 的最大值。

独立的提问的含义为，数组 $$$a,b$$$ 是不变的，这就意味着对于每个提问你只是假定操作去回答，而不会实际改变数组 $$$a,b$$$。

Input

第一行，两个整数 $$$n,q(1\le n,q \le 2·10^5)$$$，代表数组长度和询问次数。

第二行，$$$n$$$ 个整数 $$$a_i(-10^9\le a_i \le 10^9)$$$，代表数组 $$$a$$$。

第三行，$$$n$$$ 个整数 $$$b_i(-10^9\le b_i \le 10^9)$$$，代表数组 $$$b$$$。

接下来连续的 $$$q$$$ 行，每行三个整数 $$$x,y,k(1\le x \le y\le n,0\le k \le 10^9)$$$，代表你需要求的 $$$f(x,y,k)$$$ 的最大值。

Output

对于每次提问，输出一行整数代表当前询问下的 $$$f(x,y,k)$$$ 的最大值。

Examples
Input
5 5
1 2 3 4 5
1 3 5 7 9
1 1 3
1 2 1
1 3 7
1 4 3
1 5 5
Output
-1
0
27
128
375
Input
5 6
-3 2 8 -4 0
1 2 1 2 1
1 5 0
2 5 1
3 5 2
4 5 3
5 5 4
1 5 5
Output
-21
48
55
32
0
56
Input
10 10
10 7 5 -7 10 -1 2 7 9 -3
-2 0 -4 7 1 -8 -1 -9 6 -5
2 3 9
4 4 8
9 10 5
3 10 4
6 7 6
3 8 4
6 10 8
5 9 9
1 1 8
6 6 4
Output
96
63
12
720
117
925
459
459
80
80

G. 除法与取模
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

给定 $$$x,a,b$$$ ，求出对于所有的 $$$y$$$ 为整数且 $$$y\in[1,10^9]$$$ 的 $$$a\times (x\%y)+b\times\lfloor \frac{x}{y}\rfloor$$$ 的最大值。

其中 $$$\lfloor b\rfloor$$$ 的意思是对于 $$$b$$$ 向下取整，例如 $$$\lfloor \frac{7}{3}\rfloor=2$$$。

其中 $$$a\%b$$$ 的意思是 $$$a$$$ 对 $$$b$$$ 取余数，例如 $$$7\%3=1$$$。

Input

第一行，一个整数 $$$t(1\le t \le 10^5)$$$ 代表数据组数。

对于每组数据，仅有一行 $$$3$$$ 个整数 $$$x,a,b(0\le x,a,b \le 10^6)$$$，含义如题目所示。

保证同一测试点内的 $$$x$$$、$$$a$$$、$$$b$$$ 的和均不会超过 $$$10^6$$$。

Output

对于每组数据，输出一行整数代表对于所有的 $$$y$$$ 为整数且 $$$y\in[1,10^9]$$$ 的 $$$a\times (x\%y)+b\times\lfloor \frac{x}{y}\rfloor$$$ 的最大值。

Example
Input
5
0 0 0
1 0 0
1 0 1
2 3 0
3 1 2
Output
0
0
1
6
6

H. 打饭
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

再晚一秒就饿4了。

小A来到桃园餐厅就餐。桃园食堂的窗口可以视为在一条直线上，第 $$$i$$$ 个窗口的位置距出发点距离为 $$$i$$$ 个单位。小A从位置 $$$0$$$ 出发去打饭。小A可以在不超出窗口范围的前提下任意左右移动。在第 $$$i$$$ 个窗口，如果他没在这个窗口打过饭，则他可以向餐盘加入 $$$a_i$$$ 克食物（不可少打）。当他移动一个单位时，需要消耗 $$$w+1$$$ 单位能量，其中 $$$w$$$ 为他的餐盘上当前的食物重量总和。

现在他打算从起点出发，尽可能多的多打饭并回到起点。已知他的初始能量为 $$$x$$$,请问他最多能打多少克食物(没出发过也算一种方案)。因为每一天小A的初始能量不一样，所以他会对你进行多次询问。

Input

第一行两个整数 $$$n,q(1\le n \le 10^5;1\le q \le 10^5)$$$，代表窗口数和询问的次数。

第二行 $$$n$$$ 个整数 $$$a_1,a_2...a_n(1\le a_i \le 10^6)$$$，代表第 $$$i$$$ 个窗口可以打的食物量。

接下来连续的 $$$q$$$ 行，每行一个整数 $$$x(1\le x \le 10^6)$$$，第 $$$i$$$ 行代表小A第 $$$i$$$ 天的初始能量。

Output

共 $$$q$$$ 行，每行一个整数，代表第 $$$i$$$ 天小A最多能打多少克的食物。

Example
Input
5 4
2 1 3 4 1
100
17
5
3
Output
11
5
2
0

I. 大力出奇迹
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

现在有两棵深度为 $$$n$$$ 的满二叉树，树上节点编号依次为 $$$1$$$ 到 $$$2^n-1$$$ ，定义根节点的深度为 $$$1$$$ ，则深度为 $$$k$$$ 的节点编号依次为 $$$2^{k-1}$$$ 到 $$$2^k-1$$$ 。

现在我们把第一棵树的所有叶子节点(深度为 $$$n$$$ 的节点)分别向第二棵树上的某个节点连一条边，准确来说，第一棵树上编号为 $$$2^{n-1}+i$$$ 的叶子节点将会向第二棵树上编号为 $$$a_i$$$ 的节点连一条特殊的无向边。

在这两棵树和新加的边构成的无向图里，我们定义一个简单环为不重复经过同一节点且刚好经过两次特殊边的环，一个简单环的长度定义为环内的节点数。

现在请你回答最长简单环的长度，如果不存在简单环，输出 $$$0$$$。

Input

第一行输入一个整数 $$$n(1\leq n\leq 18)$$$ ，代表满二叉树的深度。

第二行输入 $$$2^{n-1}$$$ 个整数 $$$a_1,a_2,...,a_{2^{n-1}}(1\leq a_i\leq 2^n-1)$$$ ，代表第一棵树的叶子节点连到第二棵树的节点编号。

Output

输出最长简单环的长度。

Examples
Input
1
1
Output
0
Input
3
2 1 4 3
Output
8
Input
4
5 15 6 10 15 13 15 8
Output
14

J. 大兴土木
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

DDL战神小G闪耀登场。

DDL战神小G接了一个项目，需要设计一条商业街上大楼的高度，设这一条街上大楼的高度依次为 $$$h_1,h_2,...,h_n$$$ ，要求满足这是一个 $$$1,...,n$$$ 的排列。

既然是项目，甲方必然会有一些奇奇怪怪的要求，总之，甲方一共提出了 $$$m$$$ 个要求，每个要求给出了两个数 $$$l$$$ 和 $$$r$$$ ，表示一个区间，甲方要求对于在这个区间里的所有楼的高度都要小于等于两边大楼中的最高楼的高度，即对于 $$$\forall i\in[l,r]$$$， $$$h_i\leq\max\{h_l,h_r\}$$$ 。

由于DDL将近的原因，小G需要你帮他计算出满足甲方所有要求的方案数，这样他才好分配时间。

但拖DDL不是一个好习惯，为了给小G一个教训，你只需要回答他方案数对 $$$998244353$$$ 取模的结果。

Input

第一行，一个整数 $$$t(1\le t\le 10)$$$ ，代表数据组数。

对于每组数据：

第一行输入两个整数 $$$n,m(1\le n \le 500;0\le m \le n^2)$$$ ，代表大楼个数和要求个数。

第 $$$2$$$ 到 $$$m+1$$$ 行分别输入两个整数 $$$l,r(1\le l\le r\le n)$$$ ，代表对应要求的区间。

保证同一测试点内 $$$n$$$ 的总和不超过 $$$500$$$。

Output

输出满足所有要求的方案数，答案对 $$$998244353$$$ 取模。

Example
Input
3
3 1
1 3
6 3
1 3
2 4
1 5
5 4
1 1
4 5
1 4
1 5
Output
4
144
36

K. 美丽角对
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

一对不同的角为**美丽角对**当且仅当：$$$gcd(\theta_{i},\theta_{j})=1$$$ ，其中 $$$\theta$$$ 是角的角度值向下取整的值，例如 $$$60.4°=60$$$。

规定 $$$gcd(0,\theta)=\theta$$$，且 $$$180°$$$ 的角的顶点不能算作凸包的顶点。

给定 $$$n$$$ 个点的坐标 $$$(x,y)$$$ ，问最大凸包的美丽角对一共有多少对，重复的角对无需计算（即假如角对 $$$i,j$$$ 已经被计算，那么无需再计算角对 $$$j,i$$$）。

最大凸包即含所有的点，并且所有的点都在凸多边形的边界上或内部的凸多边形。

Input

第一行输入整数 $$$n$$$ $$$(3 \le n \le 10^5)$$$ ，表示点的数量；

后面 $$$n$$$ 行中，每行输入两个整数 $$$x,y(0 \le x,y \le 10^9)$$$，表示点的坐标，保证所有给出的点的坐标互不相同。

保证给出的所有的点一定可以构成至少一个凸包。

Output

输出美丽角对的数量。

Examples
Input
9
1 2
3 1
1 5
2 9
3 2
3 7
4 2
6 3
2 1
Output
8
Input
4
0 0
0 1
1 1
1 0
Output
0

L. 生活在树上
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

生活在树上——始终热爱大地——升上天空。

给你一棵有 $$$n$$$ 个节点的树，树上的每一个节点处都有一个字符 $$$c$$$，为 "(" 或 ")" 。一共有 $$$q$$$ 次询问，每次询问树上从 $$$u$$$ 到 $$$v$$$ 有向的简单路径中所有节点构成的字符串 $$$s$$$ 是否是好的。

树上的一条从 $$$u$$$ 到 $$$v$$$ 有向的简单路径是指由一条由树上许多条连续的边组成的路径，第一条边从 $$$u$$$ 出发，最后一条边到达 $$$v$$$，并且该路径只经过树上每个点最多一次。

定义这样的一个只由字符 "(" 和 ")" 组成字符串 $$$s$$$ 是好的: 开始时，你在 $$$s$$$ 的第一个字符上，结束时，你必须站在 $$$s$$$ 的最后一个字符上。在每一个时刻你可以向左移动一个空格（如果你没有站在第一个字符上），或向右移动一个空格（如果你没有站在最后一个字符上）。你不能停留在同一个地方，但可以访问任何字符，包括第一个和最后一个字符，访问次数不限。在每个时间点，你都要写下当前所站的字符。如果存在某种移动序列，能让你从第一个字符走到最后一个字符，从而使你写下的字符串是一个匹配的括号序列，那么我们就说这个字符串 $$$s$$$ 是好的。

所谓匹配的括号序列，是指可以通过在序列的原始字符之间插入字符 "1" 和 "+"，将其转换为正确算术表达式的括号序列。例如，括号序列 "()()"、"(())" 就是匹配的括号序列（得到的表达式为"(1)+(1)"、"((1+1)+1)"），而 ")(" 和 "(" 则不是。

例如，字符串 "()(())))" 是好的，因为在每个时刻，你可以按照 $$$[1,2,3,4,3,4,5,6,7,8]$$$，这样的顺序在字符串上移动，最终的序列为 "()(((())))"，是一个匹配的括号序列。 而字符串 "())(()()(())" 就不是好的，可以确定的是，在每个时刻不论你如何再这个字符串上移动，都不可能得到一个匹配的括号序列。

Input

第一行，一个整数 $$$n(1\le n \le 2·10^5)$$$，代表树的结点数。

接下来的 $$$n-1$$$ 行，每行两个数字 $$$u,v(1\le u,v \le n;u\neq v)$$$，代表树上的一条边，保证最终构成一棵树。 接下来的一行，为一个长度为 $$$n$$$ 只由字符 "(" 和 ")" 组成字符串 $$$s$$$，$$$s_i$$$ 代表树上第 $$$i$$$ 个节点上的字符 $$$c$$$。

下一行，一个整数 $$$q(1\le q \le 2·10^5)$$$，代表询问的次数。

接下来连续的 $$$q$$$ 行，每行两个整数 $$$u,v$$$，代表一次询问树上从 $$$u$$$ 到 $$$v$$$ 有向的简单路径中所有节点构成的字符串 $$$s$$$ 是否是好的。

Output

共 $$$q$$$ 行，如果上从 $$$u$$$ 到 $$$v$$$ 有向的简单路径中所有节点构成的字符串 $$$s$$$ 是好的，那么输出一行 "YES" ,否则，输出一行 "NO"。

你可以输出 "YES "和 "NO" 的任何大小写形式（例如，字符串 "yES"、"yes "和 "Yes" 都将被当作肯定的答案）。

Examples
Input
8
1 2
3 1
4 1
2 5
8 4
5 6
7 5
)()((())
7
5 7
7 5
5 3
6 7
4 8
2 8
2 3
Output
Yes
No
Yes
No
Yes
Yes
No
Input
20
12 5
17 18
18 2
8 19
19 1
14 9
8 15
3 12
18 7
8 14
18 4
14 6
14 10
7 11
8 3
14 13
13 16
8 17
8 20
)((()()())(((((())))
20
15 19
16 5
13 20
8 17
13 20
11 5
11 5
13 19
3 5
14 5
15 7
6 5
3 18
11 20
11 19
14 17
6 17
8 19
11 20
15 18
Output
No
No
No
Yes
No
No
No
No
No
No
No
No
Yes
No
No
No
No
Yes
No
Yes

M. 染色游戏（easy version）
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

简单版和困难版的唯一区别是需要解决的问题不同。

在一个叫做"异彩"的神秘世界里，颜色是一切的源泉。人们饮食、居住、学习、工作，乃至于情感表达与社交互动，都与颜色有着紧密的联系。每个人生而就有自己的颜色，这个颜色会在他们成长中得以延伸和深化，勾绘出这个人的性格、情感与经历。

在"异彩"世界中，人们将颜色与特定的情感或性格相联结，因此颜色也成为了判断或揣摩他人意图的一种方式。

在这个世界里，还有一种被称为"染色"的神秘力量。它能够改变事物原有的颜色，赋予新的含义，甚至能够改变整个世界的色彩。这种力量被一部分有能力掌握的人所独占和使用，被称为"染色师"。

"染色游戏"，就是在这样的背景下，由一群染色师发起的一个游戏。游戏的目标是通过操控颜色，完成各种复杂的任务，以最终决定谁能够掌握更高级的染色技巧。最终胜出者，会获得染色师之间的最高荣誉。

有一个 $$$n\times n$$$ 的网格，初始时网格中的所有的方格都是无色的。染色师每次会选择第 $$$i$$$ 行，第 $$$j$$$ 列的一个方格，并且把与这个方格同一行或同一列的所有方格都染成同一种颜色 $$$c$$$，且每次新的染色会覆盖掉原先的颜色。可莉就是一名染色师，现在有人交个了她一个染色任务，她希望你能够告诉她在最后一次染色时，可能选择什么颜色。

Input

第一行，一个整数 $$$t(1\le t\le 10)$$$，代表数据组数。

对于每组数据：

第一行，一个整数 $$$n(1\le n \le 500)$$$，代表网格的大小。

接下来，一个 $$$n\times n$$$ 的方阵，其中第 $$$i$$$ 行第 $$$j$$$ 列的数字为 $$$c_{i,j}(0\le c_{i,j}\le n\times n)$$$，代表这个格子的颜色，如果 $$$c_{i,j}=0$$$，则代表这个格子没有染过色。

保证给出的方阵一定存在某种染色方式可以染成该种形式。

Output

对于每组数据，第一行，先输出一个整数 $$$num$$$，代表最后一次染色选择染色颜色的方案数量。

第二行，按照从小到大输出 $$$num$$$ 个不同的整数 $$$c$$$ 代表方阵最后一次可能被染色的颜色。

Example
Input
3
2
0 1
1 1
3
1 1 1
0 2 0
3 3 3
2
0 0
0 0
Output
1
1 
2
1 3 
0

N. 染色游戏（hard version）
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

简单版和困难版的唯一区别是需要解决的问题不同。

在一个叫做"异彩"的神秘世界里，颜色是一切的源泉。人们饮食、居住、学习、工作，乃至于情感表达与社交互动，都与颜色有着紧密的联系。每个人生而就有自己的颜色，这个颜色会在他们成长中得以延伸和深化，勾绘出这个人的性格、情感与经历。

在"异彩"世界中，人们将颜色与特定的情感或性格相联结，因此颜色也成为了判断或揣摩他人意图的一种方式。

在这个世界里，还有一种被称为"染色"的神秘力量。它能够改变事物原有的颜色，赋予新的含义，甚至能够改变整个世界的色彩。这种力量被一部分有能力掌握的人所独占和使用，被称为"染色师"。

"染色游戏"，就是在这样的背景下，由一群染色师发起的一个游戏。游戏的目标是通过操控颜色，完成各种复杂的任务，以最终决定谁能够掌握更高级的染色技巧。最终胜出者，会获得染色师之间的最高荣誉。

有一个 $$$n\times n$$$ 的网格，初始时网格中的所有的方格都是无色的。染色师每次会选择第 $$$i$$$ 行，第 $$$j$$$ 列的一个方格，并且把与这个方格同一行或同一列的所有方格都染成同一种颜色 $$$c$$$，且每次新的染色会覆盖掉原先的颜色。可莉就是一名染色师，现在有人交个了她一个染色任务，她希望你能够告诉她按照什么顺序对网格进行染色，才能顺利完成染色任务。

Input

第一行，一个整数 $$$t(1\le t\le 10)$$$，代表数据组数。

对于每组数据：

第一行，一个整数 $$$n(1\le n \le 500)$$$，代表网格的大小。 接下来，一个 $$$n\times n$$$ 的方阵，其中第 $$$i$$$ 行第 $$$j$$$ 列的数字为 $$$c_{i,j}(0\le c_{i,j}\le n\times n)$$$，代表这个格子的颜色，如果 $$$c_{i,j}=0$$$，则代表这个格子没有染过色。

Output

对于每组数据，如果存在某种染色方式使得方阵网格可以被染成给出的染色任务形式，先输出一行 "YES"，然后输出一行正整数 $$$m(0\le m \le 2n)$$$，代表你给出的染色方案操作次数。最后输出连续的 $$$m$$$ 行，每行四个整数 $$$op,i,j,c(0\le op \le 1;1\le i,j \le n;1\le c \le n\times n)$$$ ,代表你当前染色的是行 ($$$op=0$$$) 还是列 ($$$op=1$$$) 与你选择的方格位置 $$$(i,j)$$$ 和你本次所染的颜色。

你不需要最小化 $$$m$$$。

如果不存在任何染色方案，输出一行 "NO"。

任何满足题目要求的答案都会被判做正确的。

Example
Input
4
2
0 1
1 1
3
2 2 2
0 2 3
3 2 3
2
0 0
0 0
2
1 2
3 4
Output
YES
2
1 1 2 1
0 2 1 1
YES
4
1 1 3 3
0 3 1 3
1 1 2 2
0 1 1 2
YES
0
NO

O. 至少一半要相等
time limit per test
0.75 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

现在有一个长度为 $$$n$$$($$$n$$$为偶数) 的序列，该序列中数字互不相同，你需要选择一个正整数 $$$k$$$，然后对序列中任意一个数字 $$$a_i$$$ 执行任意次如下操作：

$$$$$$ a_i=a_i-k $$$$$$

在一定次数的该操作后，你需要使序列中至少一半的数字相等，请问 $$$k$$$ 的最大值是多少，如果 $$$k$$$ 可以无限大，则输出 $$$0$$$。

Input

第一行，一个整数 $$$t(1\le t \le 100)$$$。

对于每组数据：

第一行，一个整数 $$$n(2\le n \le 5000)$$$，$$$n$$$ 是一个偶数，代表序列长度。 接下来一行，一个长度为 $$$n$$$ 的序列 $$$a$$$，该序列中数字互不相同，其中的每个数字 $$$1\le a_i \le 10^6$$$。

保证在同一测试点内的 $$$\sum n \le 5000$$$。

Output

对于每组数据，输出一行代表可行的 $$$k$$$ 的最大值，如果 $$$k$$$ 可以无限大，则输出 $$$0$$$。

Example
Input
3
6
1 2 3 4 5 6
2
1 10
8
1 5 4 9 8 13 12 11
Output
2
0
4