2022 Collegiate Programming Contest of Xiangtan University
A. 社团招新
time limit per test
30 с
memory limit per test
128 megabytes
input
standard input
output
standard output

计网院里面有n个学生。

他们中任意一些人都可以成立一个社团。

如果社团满足3男有1女，就可以一对情侣一对基。

但是院里要求这些社团有如下要求：

  • 为方便社团决议（少数服从多数），每个社团里面只有奇数个成员；
  • 为方便社团联谊，每两个社团的共同成员是偶数。

现在，计网院的海王哥哥想要知道最多可以成立几个社团。

Input

第一行是一个整数T (1 ≤ T ≤ 200000)，表示样例的个数。 以后每行一个样例，为一个整数n (3 ≤ n ≤ 1000000)。

Output

每行输出一个样例的结果。

Example
Input
1
3
Output
3

B. 字符串
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

lililalala和kukyo在玩一个字符串游戏，具体规则为： 给定一个只含小写字母的字符串S，lililalala和kukyo轮流在S上选择两个相同且相邻的字母删除，删除完之后再将两端连接起来。比如"funny""fuy"，"aab""b")。如果某一方不能执行删除操作则判负，另一方获胜。 现在lililalala先进行操作，假设双方都以最优策略进行游戏，谁会获胜？

Input

第一行一个整数T (1 ≤ T ≤ 1000)，表示测试样例个数。 然后的每一行表示一个测试样例，包含一个字符串S，字符串只含小写英文字母，长度不超过105。 保证输入中所有字符串的长度之和。

Output

对每个样例输出一行，如果lililalala能获胜输出"Yes"，否则输出"No"。

Example
Input
4
xtu
funny
abcdcba
abccba
Output
No
Yes
No
Yes

C. 排球
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

正规的排球赛规则为5局3胜，前4局每局25分,决胜局15分。

为了简化本题，假定规则为一场排球赛为3局2胜，每局都为25分。即：

  1. 一局中，如果双方小比分没有打成过24比24，则先得到25分者获胜。
  2. 一局中，如果双方小比分打成24比24，获胜一方需超过对手2分(且得分超过25分)才算取胜。(比如一局结束时26:24，25:10这种小比分是可能的，27:24，25:24则是不可能出现的)
  3. 任何一方一局获胜则大比分得1分，败方不得分，当任何一方大比分达到2时，整场比赛结束。

现在，有A、B两只排球队按上述规则打完了一场排球赛，且已知这场比赛所有局中两队分别的小比分之和(即两队分别赢了多少个球)，请问两队的大比分应该是多少？

Input

第一行一个整数T(T ≤ 105)–样例个数。

接下来的T行每行代表一个样例，包含两个整数0 ≤ x, y ≤ 109，分别表示A、B队分别的小比分之和。

Output

对于每个样例输出一行两个整数S1, S2，用英文冒号":"分隔，表示A、B两队的大比分。

如果有多个可能的结果，请输出A队净胜局数最大，即使得S1 - S2最大的结果。

如果没有任何符合条件得结果，请输出"Impossible"

Example
Input
16
50 46
50 47
51 41
51 49
51 72
51 75
53 48
53 50
88 85
0 50
10 60
20 60
30 60
996 1007
1000000000 999999995
1000000000 1000000000
Output
2:0
2:1
2:0
2:1
2:1
1:2
2:0
2:1
2:1
0:2
Impossible
Impossible
1:2
2:1
2:0
2:1

D. 香蕉
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

你有n根香蕉，要分给m只猴子，每只猴子都要有香蕉。无论怎么分配，请问至少多少只猴子分得的香蕉数是一样的？

比如有5根香蕉，分给3只猴子，我们只能按(1, 1, 3)或者(1, 2, 2)分配，这样无论怎么分配，至少都有2只猴子获得的香蕉是一样的。如果有6根香蕉，分给3只猴子，那么我们可以按(1, 2, 3)分配，这样的话，至少1只猴子分得的香蕉数是一样的。

Input

第一行输入一个整数T'(1 ≤ T ≤ 1000)，表示样例的个数。

每行一个样例，为两个整数n (1 ≤ n ≤ 1018), m (1 ≤ m ≤ 109, m ≤ n)。

Output

依次每行输出一个样例的结果，为一个整数。

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

E. 孤独的小Z
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

小Z很孤独，他的朋友很少。某天，他做了一个梦，梦到了他有好多朋友，分布在各个城市，他依稀记得梦中各个城市间朋友数量的关系。现在，梦醒了，小Z想要知道这个梦是否有可能是真的。

有n个城市，编号为1 - n，他还依稀记得m条信息，每条信息是下面其中一种：

  • 城市a中的朋友数量比城市b中的朋友数量至少多c个。
  • 城市a中的朋友数量比城市b中的朋友数量至多多c个。
  • 城市a中的朋友数量等于城市b中的朋友数量。
现在，请你判断，他的梦是否可能是真的，如果有可能，则输出他最少有多少个朋友，否则，输出 - 1。
Input

第一行是一个整数T(1 ≤ T ≤ 50)，表示样例的个数。

每个样例第一行有两个整数n, m，表示城市数量和信息数量。

之后m行：

如果该行第一个数字是1，则接下来有三个整数a, b, c，表示城市a中的朋友数量比城市b中的朋友数量至少多c个。

如果该行第一个数字是2，则接下来有三个整数a, b, c，表示城市a中的朋友数量比城市b中的朋友数量至多多c个。

如果该行第一个数字是3，则接下来有三个整数a, b，表示城市a中的朋友数量等于城市b中的朋友数量。

同类型下信息两个城市不会重复同时出现，比如已经出现了有了信息1 2 3 100，不会再出现信息1 2 3 200，但可能出现1 3 2 200。

另外，不会出现重复的信息。

1 ≤ n, m, a, b, c ≤ 1000，a ≠ b

Output

每个样例输出一个整数，如果梦可能为真，则输出小Z最少有多少个朋友。如果梦为假，则输出 - 1。

Example
Input
2
3 3
3 1 2
1 1 3 1
2 2 3 2
2 2
1 1 2 1
1 2 1 1
Output
2
-1

F. 摘橘子
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

lililalala路过了一片橘子园，他准备从橘子园里摘橘子回去给队友们分享。这片橘子园有n棵橘子树，其中第i棵橘子树上有ai个橘子，对于每棵橘子树i，lililalala都可以选择从上面摘[0, ai]中任意整数数量的橘子(即0, 1, 2...ai)。lililalala总共有m个队友，因此他希望他摘到的橘子能平均分给这些队友，也就是说摘到橘子的总数能整除m。

请问lililalala有多少种不同的摘橘子的方案？

注意，当两个方案中存在任意一棵橘子树摘下的橘子数量不同时，这两个方案就称为不同的方案。

Input

第一行一个整数T–表示测试样例个数。

然后每个样例包含两行，第一行包含两个整数1 ≤ n ≤ 104, 1 ≤ m ≤ 50–表示橘子树的数量和队友的数量。

第二行包含n个整数1 ≤ a0, a1...an ≤ 105，表示这些橘子树上的橘子数量。

保证样例数量T ≤ 103，所有样例中

Output

对于每个样例，输出一个整数，表示方案的数量。由于方案数可能很大，答案请对998244353取模。

Example
Input
4
3 1
1 1 1
3 2
1 1 1
3 2
1 1 2
2 2
1000000000 1000000000
Output
8
4
6
359791097

G. 排列
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

给定两个整数N, M，求是否存在一个关于[1, N]的排列A = {a1, a2...aN}和一个关于[M + 1, M + N]的排列B = {b1, b2...bN}，使得对于任意位置满足条件：bi - ai是一个完全平方数或bi + ai是一个完全平方数。

Input

第一行一个整数T–表示测试样例个数。 然后的每一行表示一个测试样例，包含两个整数N, M。 数据范围1 ≤ T ≤ 1000, 1 ≤ N ≤ 100000, 0 ≤ M ≤ 400。

Output

对每个样例输出一行，如果存在输出"Yes"，否则输出"No"。

Example
Input
5
2 2
3 3
13 2
13 49
13 51
Output
No
Yes
Yes
Yes
No
Note

样例1与样例5没有满足条件的排列。

关于样例2，一个满足条件的情况为A = {1, 2, 3}, B = {5, 6, 4}。

关于样例3，一个满足条件的情况为A = {13, 3, 4, 5, 7, 1, 8, 10, 11, 12, 9, 2, 6}，

B = {3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}。

关于样例4，一个满足条件的情况为A = {12, 13, 1, 2, 3, 11, 10, 9, 8, 7, 6, 5, 4}，

B = {48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60}。

当答案为Yes时，满足条件的情况不一定唯一。

H. 紧急补给
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

谭雅·提古雷查夫少校是一位身经百战却十分遗憾的军人,她现在莱茵战线打堑壕战,但是她十分缺少补给,于是她在脑中随机选择了一个补给点( 她知道有哪几个补给,但是没记住在哪里 ),并临时查阅地图,准备前往该补给点补给(不要问我为什么不找最近一个,你要是会这个,就无敌了)。现在,少校有了一个有趣的想法,如果脑中选取补给点的概率对各个补给点而言是均匀的且其当前在地图上的位置的概率也是均匀的,那么她需要前往的补给点的距离的期望值是多少？

地图是一个边长为N的(共计(N + 1) × (N + 1)个点)的正方形,且因为莱茵战线到处都是枪林弹雨的影响,谭雅不得不通过堑壕行动,而堑壕横平竖直地连接着地图上的各个整数点,即点(x1, y1)到(x2, y2)的距离是abs({x1 - x2}) + abs({y1 - y2}),且谭雅的当前位置和补给点的坐标也全都是整数.

Input

一行给出一个正整数N和一个正整数M分别表示地图的尺寸和补给点的数量.

接下来的M行依次给出xi,yi,即第i个补给点的坐标.

数据范围:1 ≤ N ≤ 2·106 1 ≤ M ≤ 2·106 0 ≤ xi, yi ≤ N

输入保证每一个补给点的坐标都是独一无二的,即同一个点不会同时存在两个补给点

Output

对于每一个答案 x / y ,请输出最小的一个正整数 k 使得 y·k ≡ x(mod 998244353)

Examples
Input
2 1
0 0
Output
2
Input
6 3
0 0
5 3
0 3
Output
760567131
Note

第一个样例中距离补给点(0, 0)为0的点有(0, 0)；

距离为1的点有(0, 1), (1, 0)；

距离为2的点有(0, 2), (1, 1), (2, 0)；

距离为3的点有(1, 2), (2, 1)；

距离为4的点为(2, 2)。

所以距离的期望为

I. 线段与平面
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

在一个无边的平面上有n条线段，问这个平面被这些线段分成了多少个面？

样例图
Input

输入包含多组样例。

每组样例的第一行是整数n (1 ≤ n ≤ 1000)，表示线段的数量。 接下里的n行，每行四个整数x1, y1, x2, y2,  ( - 1000 ≤ x1, y1, x2, y2 ≤ 1000)，表示一条线段的两个端点的坐标。

输入保证任意两条线段最多只有1个交点。

Output

依次每行输出一个样例的结果，为一个整数。

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

J. 在一起
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

ACMer分布在全国的n个不同的城市，编号为。任意两个城市都连通，且只有唯一的一条通路。

你们决定来一次全体聚会，请选出一个城市作为聚会地，使得所有人的距离和最小。

Input

第一行是一个整数T (1 ≤ T ≤ 10)，表示样例的个数，所有测试数据样例总数不超过100。

每个样例的第一行是一个整数n (1 ≤ n ≤ 10000)。

第二行是n个整数，表示第i个城市里的ACMer的人数ai (1 ≤ ai ≤ 100)。

从第三行起的n - 1行，每行三个整数u, v, w,  (1 ≤ u < v ≤ n), 1 ≤ w ≤ 100，表示城市u和v之间有一条路，距离为w。

Output

依次输出每个样例的结果，为两个整数，第一个为聚会城市的编号，第二个为所有人的距离和，两者之间用一个空格隔开。

如果存在多个符合条件的城市，取编号最小的。

Example
Input
1
6
1 2 3 4 5 6
1 2 1
1 3 1
2 4 1
2 5 1
3 6 1
Output
2 34
Note

选1号城市作为聚会地，距离和为(2 + 3)·1 + (4 + 5 + 6)·2 = 35。

选2号城市作为聚会地，距离和为(1 + 4 + 5)·1 + 3·2 + 6·3 = 34。

选3号城市作为聚会地，距离和为(1 + 7)·1 + 2·2 + (4 + 5)·3 = 39。

选4号城市作为聚会地，距离和为2·1 + (1 + 5)·2 + 3·3 + 6·4 = 47。

选5号城市作为聚会地，距离和为2·1 + (1 + 4)·2 + 3·3 + 6·4 = 45。

选6号城市作为聚会地，距离和为3·1 + 1·2 + 2·3 + (4 + 5)·4 = 47。