HNNU Freshman Competition Round 2
A. 琪露诺的算法课堂
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

琪露诺的算法课堂要开始了哟！

第一步要干什么呢？输出"hello world"吗？

不！我们应该输出"ciallo world"（不包括引号）。

Input

无

Output

无

Example
Input
ciallo world
Output
ciallo world

B. 琪露诺数 Ciallo
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

一天琪露诺在路上捡到了 $$$x_C$$$ 个字母 C，$$$x_i$$$ 个 字母 i，$$$x_a$$$ 个 字母 a，$$$x_l$$$ 个 字母 l，$$$x_o$$$ 个字母 o。

她想把这些字母组成若干个 Ciallo，她最多能组成多少个？

Input

每个测试点包含多个测试用例。第一行包含一个整数 $$$t\ (1 \le t \le 10^5)$$$，表示测试用例的数量。

对于每个测试用例，第一行包含 5 个整数 $$$x_C,x_i,x_a,x_l,x_o\ (0 \le x_C,x_i,x_a,x_l,x_o \le 10^9)$$$，含义如题。

Output

对于每个测试用例，输出最多能够组成 Ciallo 的数量。

Example
Input
3
1 1 1 2 1
1 2 3 4 5
6 7 8 9 10
Output
1
1
4
Note

对于第 1 个测试点：恰好可以组成一个 Ciallo。

对于第 2 个测试点：组成 1 个 Ciallo 后，只剩下 0 个字母 C 了，无法组成更多。

对于第 3 个测试点：组成 4 个 Ciallo 后，只剩下 1 个字母 l 了，无法组成更多。

C. 琪露诺放冰块
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

琪露诺有一个长为 $$$n$$$，宽为 $$$m$$$ 的长方体$$$^*$$$冰箱和若干个长为 $$$a$$$，宽为 $$$b$$$ 的长方体冰块，冰箱与冰块高度一样，她想知道在不能旋转的情况下她最多能把多少冰块放入冰箱。由于琪露诺是一个 baka，所以她把这个问题交给了你。

$$$^*$$$长方体的边和水平同方向的叫做"长"，和前后同方向的叫做"宽"，和竖直同方向的叫做"高"。

Input

每个测试点包含多个测试用例。第一行包含一个整数 $$$t\ (1 \le t \le 100)$$$，表示测试用例的数量。

对于每个测试用例，第一行包含 4 个整数 $$$n,m,a,b\ (1 \le a \le n \le 10^4,1 \le b \le m \le 10^4)$$$，含义如题。

Output

对于每个测试用例，输出一行一个整数，表示答案。

Example
Input
3
3 3 2 1
3 3 2 2
10000 10000 1 1
Output
3
1
100000000
Note
第二个测试点的一种可行放法。

D. 琪露诺的无限循环小数
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

在东方Project的幻想乡，琪露诺是雾之湖的冰之妖精。有一天，她在湖边练习魔法时，发现了一个有趣的数学问题：

$$$\quad$$$ 对于给定的正整数 $$$n\ \left(n \in N_+\ 且\ n \in [2,10^9] \right)$$$ ，分数 $$$\frac{1}{n}$$$ 是否是一个无限循环小数$$$^*$$$？

琪露诺虽然自信满满，但这个问题涉及数学知识，让她感到困惑。为了解开这个谜题，她决定寻求你的帮助。

$$$^*$$$无限循环小数是指小数部分有无限个数字，且从小数点后某一位开始，一个或几个数字依次不断重复出现的小数。

Input

每个测试点包含多个测试用例。第一行包含一个整数 $$$t\ (1 \le t \le 10^5)$$$，表示测试用例的数量。

对于每个测试用例，第一行包含一个整数 $$$n\ (2 \le n \le 10^{9})$$$，含义如题。

Output

对于每个测试用例，如果是无限循环小数，输出"YES"（不包括引号），否则输出"NO"（不包括引号）。

Example
Input
5
2
3
5
7
10
Output
NO
YES
NO
YES
NO
Note

对于第 1 个测试点：$$$\frac{1}{2} = 0.5$$$ 不是无限循环小数。

对于第 2 个测试点：$$$\frac{1}{3} = 0.\dot{3}$$$ 是无限循环小数。

对于第 3 个测试点：$$$\frac{1}{5} = 0.2$$$ 不是无限循环小数。

对于第 4 个测试点：$$$\frac{1}{7} = 0.\dot{1}4285\dot{7}$$$ 是无限循环小数。

对于第 5 个测试点：$$$\frac{1}{10} = 0.1$$$ 不是无限循环小数。

E. 琪露诺的最大方差子序列
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

琪露诺是东方project中著名的冰之妖精，她最近在雾雨魔法店学习统计学。有一天，她在湖面上发现了一串由冰晶组成的数字序列。为了施展最强的冰魔法，她需要从这个序列中选出一个非空子序列，使得该子序列的方差最大。方差能够反映数据的离散程度，琪露诺相信方差最大的子序列能凝聚最大的冰之能量。作为最聪明的妖精，她决定挑战这个问题，但需要你的帮助来找到最优解。

给一个长度为 $$$n$$$ 的整数数组 $$$a$$$，从中选出一个非空 子序列$$$^*$$$ $$$b$$$，使得 $$$b$$$ 中所有元素的 方差$$$^†$$$ 最大。

$$$^*$$$子序列是指从一个原始序列中通过去除某些元素而不改变剩余元素的相对顺序所形成的新序列。

$$$^†$$$方差是长度为 $$$n$$$ 的数组 $$$a$$$ 方差 $$$\sigma^2(a) = \frac{1}{n} \sum_{i=1}^{n} \left( a_i - \frac{1}{n} \sum_{j=1}^{n}a_j \right)^2 $$$。

Input

每个测试点包含多个测试用例。第一行包含一个整数 $$$t\ (1 \le t \le 10^5)$$$，表示测试用例的数量。

对于每个测试用例，第一行包含一个整数 $$$n\ (1 \le n \le 5 \times 10^5)$$$，表示数组的长度。

第二行包含 $$$n$$$ 个整数 $$$a_1, a_2, \dots , a_n\ (1 \le a_i \le 10^9)$$$, 表示数组 $$$a$$$。

保证所有测试用例的 $$$n$$$ 之和不超过 $$$5 \times 10^5$$$。

Output

对于每个测试用例，输出该数组的非空子序列的最大方差。

你的答案被认为是正确的当且仅当它与标准答案的绝对或相对误差不超过 $$$10^{-6}$$$。

更准确地来说，假设你的答案是 $$$x$$$、标准答案为 $$$y$$$，那么你的答案将被认为是正确的当且仅当 $$$\frac{|x−y|}{max(1,|y|)} \le 10^{-6} $$$。

Example
Input
3
2
2 1
3
9 9 9
6
1 1 4 5 1 4
Output
0.25
0.0
4.0
Note

对于 c/c++ 选手且使用浮点数运算建议使用精度更高的 long double。

对于第 1 个测试点：选择子序列 $$$b = [2, 1]$$$，此时方差为 $$$\sigma^2(b) = \frac{1}{2}\left( (1 -\frac{1+2}{2})^2+(2 -\frac{1+2}{2})^2 \right) = \frac{1}{4}$$$。

对于第 2 个测试点：选择子序列 $$$b = [9, 9, 9]$$$，此时方差为 $$$\sigma^2(b) = \frac{1}{3}\left( (9-\frac{9+9+9}{3})^2+(9-\frac{9+9+9}{3})^2+(9-\frac{9+9+9}{3})^2 \right) = 0$$$。

F. 琪露诺的冰晶数学挑战
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

在幻想乡，琪露诺是雾之湖的冰之妖精。今天，她在湖边发现了一组闪闪发光的数字冰晶，每个冰晶上都刻有一个数字。好奇的琪露诺想从中选出两个不同的冰晶，通过加法、减法或乘法操作，找出能得到的最大数值。作为最聪明的妖精（自认），她决定接受这个挑战，但需要你的帮助来验证她的想法。

形式化地说：给 $$$n$$$ 个整数 $$$a_1,a_2,\cdots,a_n$$$，求出 $$$\max_{1 \le i,j \le n,i \not = j,op \in \left\{+,-,\times\right\}} a_i\ op\ a_j$$$。

Input

每个测试点包含多个测试用例。第一行包含一个整数 $$$t\ (1 \le t \le 10^5)$$$，表示测试用例的数量。

对于每个测试用例，第一行包含一个整数 $$$n\ (1 \le n \le 2 \times 10^5)$$$，表示数组的长度。

第二行包含 $$$n$$$ 个整数 $$$a_1, a_2, \dots , a_n\ (-10^9 \le a_i \le 10^9)$$$, 表示数组 $$$a$$$。

保证所有测试用例的 $$$n$$$ 之和不超过 $$$2 \times 10^5$$$。

Output

对于每个测试用例，输出一行一个整数，表示答案。

Example
Input
2
3
2 -3 1
6
1 1 4 5 1 4
Output
5
20
Note

对于第 1 个测试点：选择 $$$a_1 - a_2 = 5$$$，可以证明没有更大的答案了。

对于第 2 个测试点：选择 $$$a_4 \times a_6 = 20$$$，可以证明没有更大的答案了。

G. 琪露诺寻找锐角
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

二维平面内有 $$$n$$$ 个不同的点 $$$P_1(x_1,y_1),P_2(x_2,y_2),\cdots,P_n(x_n,y_n)\ (\forall i \in [1,n],x_i,y_i \in Z)$$$。你需要找到三个整数 $$$i,j,k\ (1 \le i,j,k \le n)$$$ 使得 $$$i \not = j, i \not = k, j \not = k$$$ 且 $$$\angle P_iP_jP_k$$$ 是锐角$$$^*$$$，或报告无解。

*锐角是指严格大于0°而严格小于90°的角。

Input

每个测试点包含多个测试用例。第一行包含一个整数 $$$t\ (1 \le t \le 10^5)$$$，表示测试用例的数量。

对于每个测试用例，第一行包含一个整数 $$$n\ (3 \le n \le 10^{5})$$$，表示点的数量。

接下来的 $$$n$$$ 行中，第 $$$i$$$ 行包含两个整数 $$$x_i,y_i\ (-10^9 \le x_i,y_i \le 10^9)$$$，表示第 $$$i$$$ 个点的坐标。保证 $$$n$$$ 个点坐标两两不同。

保证所有测试数据 $$$n$$$ 之和不超过 $$$10^5$$$。

Output

对于每个测试用例，如果不存在解，输出一行一个整数 -1；否则输出一行 3 个整数 $$$i,j,k$$$ 满足题意。

如果有多种合法答案，你可以输出任意一种。

Example
Input
2
3
1 1
0 0
2 2
3
0 0
1 0
0 1
Output
-1
1 2 3
Note

对于第 1 个测试点：

$$$\angle P_1P_2P_3 = 0°,\angle P_2P_1P_3 = 180°,\angle P_1P_3P_2 = 0°$$$。

所以无解。

对于第 2 个测试点：

$$$\angle P_1P_2P_3 = 45°$$$。