A. Bad Ugly Numbers

You are given a integer nn (n>0)(n>0). Find any integer ss which satisfies these conditions, or report that there are no such numbers:
In the decimal representation of ss:

  • s>0s>0,
  • ss consists of nn digits,
  • no digit in ss equals 00,
  • ss is not divisible by any of it’s digits.

Input

The input consists of multiple test cases. The first line of the input contains a single integer tt (1⩽t⩽400)(1\leqslant t\leqslant 400), the number of test cases. The next tt lines each describe a test case.
Each test case contains one positive integer nn (1⩽n⩽105)(1\leqslant n\leqslant 10^5).
It is guaranteed that the sum of nn for all test cases does not exceed 10510^5.

Output

For each test case, print an integer ss which satisfies the conditions described above, or “-1” (without quotes), if no such number exists. If there are multiple possible solutions for ss, print any solution.

Example

input

4
1
2
3
4

output

-1
57
239
6789

Note

In the first test case, there are no possible solutions for s consisting of one digit, because any such solution is divisible by itself.
For the second test case, the possible solutions are: 2323, 2727, 2929, 3434, 3737, 3838, 4343, 4646, 4747, 4949, 5353, 5454, 5656, 5757, 5858, 5959, 6767, 6868, 6969, 7373, 7474, 7676, 7878, 7979, 8383, 8686, 8787, 8989, 9494, 9797, and 9898.
For the third test case, one possible solution is 239239 because 239239 is not divisible by 2,32, 3 or 99 and has three digits (none of which equals zero).

Translation

给一个整数nn，要求输出一个由nn个数字组成的正整数，要求该整数不包含00，且不能被组成该整数的nn个数中的任意一个数整除。

Idea

显然，23333333333333333333333333…23333333333333333333333333\dots符合题意。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<cstdio>
using namespace std;
void solve()
{
	int n;
	cin>>n;
	if(n==1) puts("-1");//特判
	else
	{
		cout<<2;
		n--;
		while(n--) cout<<3;
		cout<<endl;
	}
}
int main()
{
	int t;
	cin>>t;
	while(t--) solve();
	return 0;
}

B. Maximums

Alicia has an array, a1,a2,…,ana_1,a_2,\dots ,a_n, of non-negative integers. For each 1⩽i⩽n1\leqslant i\leqslant n, she has found a non-negative integer $x_i=\max \{0,a_1,\dots,a_{i−1}\}$. Note that for i=1i=1,xi=0x_i=0.
For example, if Alicia had the array $a=\{0,1,2,0,3\}$, then $x=\{0,0,1,2,2\}$.
Then, she calculated ana_n array, b1,b2,…,bn:bi=ai−xib_1,b_2,…,b_n: b_i=a_i−x_i.
For example, if Alicia had the array $a=\{0,1,2,0,3\}, b=\{0−0,1−0,2−1,0−2,3−2\}=\{0,1,1,−2,1\}$.
Alicia gives you the values b1,b2,…,bnb_1,b_2,…,b_n and asks you to restore the values a1,a2,…,ana_1,a_2,\dots ,a_n. Can you help her solve the problem?

Input

The first line contains one integer nn (3⩽n⩽200000)(3\leqslant n\leqslant 200000) – the number of elements in Alicia’s array.
The next line contains nn integers, b1,b2,…,bnb_1,b_2,…,b_n (−109⩽bi⩽109)(−10^9\leqslant b_i\leqslant 10^9).
It is guaranteed that for the given array bb there is a solution a1,a2,…,ana_1,a_2,\dots ,a_n, for all elements of which the following is true: 0≤ai≤1090≤a_i≤10^9.

Output

Print n integers, a1,a2,…,ana_1,a_2,\dots ,a_n (0⩽ai⩽109)(0\leqslant a_i\leqslant 10^9), such that if you calculate xx according to the statement, b1b_1 will be equal to a1−x1a_1−x_1, b2b_2 will be equal to a2−x2a_2−x_2, …, and bnb_n will be equal to an−xna_n−x_n.
It is guaranteed that there exists at least one solution for the given tests. It can be shown that the solution is unique.

Examples

input

5
0 1 1 -2 1

output

0 1 2 0 3

input

3
1000 999999000 -1000000000

output

1000 1000000000 0

input

5
2 1 2 2 3

output

2 3 5 7 10

Note

The first test was described in the problem statement.
In the second test, if Alicia had an array $a=\{1000,1000000000,0\}$, then $x=\{0,1000,1000000000\}$ and $b=\{1000−0,1000000000−1000,0−1000000000\}=\{1000,999999000,−1000000000\}$.

Translation

给一个数列$\{a_n\}$，计算数列$\{x_n\}$，$x_i=\max\{0,a_1,\dots,a_{i-1}\}$。接着，我们可以计算数列$\{b_n\}$，bi=ai−xib_i=a_i-x_i。
现在给出数列$\{b_n\}$，要求输出一组符合条件的$\{a_n\}$，保证$\{a_n\}$有唯一解。

Idea

$ \begin{cases} x_{i-1}=\max\{0,a_1,\dots,a_{i-2}\},i>1 \\ x_i=\max\{0,a_1,\dots,a_{i-2},a_{i-1}\} \\ \end{cases} $$\Rightarrow x_i=\begin{cases} 0,i=1\\ \max\{x_{i-1},a_{i-1}\},i>1\\ \end{cases}$

∵ai=bi+xi,\because a_i=b_i+x_i,

$\therefore x_i=\begin{cases} 0,i=1\\ \max\{x_{i-1},b_{i-1}+x_{i-1}\},i>1\\ \end{cases}$

可以通过迭代计算出xix_i，相应的aia_i就变得非常好求。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<algorithm>
using namespace std;
const int N=200005;
long long b[N],x[N];
void solve()
{
	int n;
	cin>>n;
	int i;
	for(i=1;i<=n;i++) cin>>b[i];
	x[1]=0;
	//迭代出x
	for(i=2;i<=n;i++) x[i]=max(x[i-1],x[i-1]+b[i-1]);
	for(i=1;i<=n;i++) cout<<b[i]+x[i]<<' ';
}
int main()
{
	solve();
	return 0;
}

C. Permutation Partitions

You are given a permutation p1,p2,…,pnp_1,p_2,\dots,p_n of integers from 11 to nn and an integer kk, such that 1⩽k⩽n1\leqslant k\leqslant n. A permutation means that every number from 11 to nn is contained in pp exactly once.
Let’s consider all partitions of this permutation into kk disjoint segments. Formally, a partition is a set of segments $\{[l_1,r_1],[l_2,r_2],\dots,[l_k,r_k]\}$, such that:
1⩽li⩽ri⩽n1\leqslant l_i\leqslant r_i\leqslant n for all 1⩽i⩽k1\leqslant i\leqslant k;
For all 1⩽j⩽n1\leqslant j\leqslant n there exists exactly one segment [li,ri][l_i,r_i], such that li⩽j⩽ril_i\leqslant j\leqslant r_i.
Two partitions are different if there exists a segment that lies in one partition but not the other.
Let’s calculate the partition value, defined as ∑i=1kmax⁡li⩽j⩽ripj\displaystyle \sum_{i=1}^k \max\limits_{l_i\leqslant j\leqslant r_i}p_j, for all possible partitions of the permutation into kk disjoint segments. Find the maximum possible partition value over all such partitions, and the number of partitions with this value. As the second value can be very large, you should find its remainder when divided by 998244353998244353.

Input

The first line contains two integers, nn and kk (1⩽k⩽n⩽200000)(1 \leqslant k\leqslant n\leqslant 200000) — the size of the given permutation and the number of segments in a partition.
The second line contains nn different integers p1,p2,…,pnp_1,p_2,\dots,p_n$ (1\leqslant p_i\leqslant n)$ — the given permutation.

Output

Print two integers — the maximum possible partition value over all partitions of the permutation into kk disjoint segments and the number of such partitions for which the partition value is equal to the maximum possible value, modulo 998244353998244353.
Please note that you should only find the second value modulo 998244353998244353.

Examples

input

3 2
2 1 3

output

5 2

input

5 5
2 1 5 3 4

output

15 1

input

7 3
2 7 3 1 5 4 6

output

18 6

Note

In the first test, for k=2k=2, there exists only two valid partitions: $\{[1,1],[2,3]\}$ and $\{[1,2],[3,3]\}$. For each partition, the partition value is equal to 2+3=52+3=5. So, the maximum possible value is 55 and the number of partitions is 22.
In the third test, for k=3k=3, the partitions with the maximum possible partition value are $\{[1,2],[3,5],[6,7]\}$,$\{[1, 3], [4, 5], [6, 7]\}$,$\{[1, 4], [5, 5], [6, 7]\}$,$\{[1, 4], [5, 5], [6, 7]\}$,$\{[1, 2], [3, 6], [7, 7]\}$,$\{[1, 3], [4, 6], [7, 7]\}$,$\{[1, 4], [5, 6], [7, 7]\}$. For all of them, the partition value is equal to 7+5+6=187+5+6=18.
The partition $\{[1,2],[3,4],[5,7]\}$, however, has the partition value 7+3+6=167+3+6=16. This is not the maximum possible value, so we don’t count it.

Translation

将一个全排列$\{p_n\}$，分成kk个区间，定义一个和为∑i=1kmax⁡li⩽j⩽ripj\displaystyle \sum_{i=1}^k \max\limits_{l_i\leqslant j\leqslant r_i}p_j，求这个和的最大值，并输出能够取到这个最大值的分割方式的数量。

Idea

∑i=1kmax⁡li⩽j⩽ripj\displaystyle \sum_{i=1}^k \max\limits_{l_i\leqslant j\leqslant r_i}p_j的最大值必定是$\{p_n\}$中前kk个最大数字的和。因此，前kk个最大数字要均匀分布在kk个区间中。我们选中前kk个最大的数，只需要记录每一个被选中数字的位置，然后得到相邻两个数字的间隔，按照乘法原理计算即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<iostream>
#include<algorithm>
#include<vector>
#define ll long long
using namespace std;
const int N=200005;
const ll mod=998244353;
vector<ll>pos;
struct node
{
	ll val;
	ll id;
}p[N];
bool cmp(node a,node b)
{
	return a.val>b.val;
}
void solve()
{
	ll n,k;
	ll i;
	cin>>n>>k;
	for(i=1;i<=n;i++) 
	{
		cin>>p[i].val;
		p[i].id=i;//记录位置
	}
	sort(p+1,p+1+n,cmp);//从大到小排序
	ll res=0;
	for(i=1;i<=k;i++)
	{
		pos.push_back(p[i].id);//记录前k大的数的所有位置
		res=res+p[i].val;//前k大的数字的和
	}
	ll ans=1;
	sort(pos.begin(),pos.end());//将位置排序
	//求出间隔，利用乘法原理得到答案
	for(i=1;i<k;i++) ans=ans*(pos[i]-pos[i-1])%mod;
	cout<<res<<' '<<ans; 
}
int main()
{
	solve();
	return 0;
}

D1. Prefix-Suffix Palindrome (Easy version)

This is the easy version of the problem. The difference is the constraint on the sum of lengths of strings and the number of test cases. You can make hacks only if you solve all versions of this task.
You are given a string ss, consisting of lowercase English letters. Find the longest string tt, which satisfies the following conditions:

  • The length of tt does not exceed the length of ss.
  • tt is a palindrome.
  • There exists two strings aa and bb (possibly empty), such that t=a+bt=a+b ( “+” represents concatenation), and aa is prefix of ss while bb is suffix of ss.

Input

The input consists of multiple test cases. The first line contains a single integer tt (1⩽t⩽1000)(1\leqslant t\leqslant 1000), the number of test cases. The next tt lines each describe a test case.
Each test case is a non-empty string ss, consisting of lowercase English letters.
It is guaranteed that the sum of lengths of strings over all test cases does not exceed 50005000.

Output

For each test case, print the longest string which satisfies the conditions described above. If there exists multiple possible solutions, print any of them.

Example

input

5
a
abcdfdcecba
abbaxyzyx
codeforces
acbba

output

a
abcdfdcba
xyzyx
c
abba

Note

In the first test, the string s=“a"s=\text{“a"} satisfies all conditions.
In the second test, the string "abcdfdcba"\text{"abcdfdcba"} satisfies all conditions, because:
Its length is 99, which does not exceed the length of the string ss, which equals 1111.
It is a palindrome.
“abcdfdcba"=“abcdfdc"+“ba"\text{“abcdfdcba"} = \text{“abcdfdc"} + \text{“ba"}, and “abcdfdc"\text{“abcdfdc"} is a prefix of s while “ba"\text{“ba"} is a suffix of ss.
It can be proven that there does not exist a longer string which satisfies the conditions.
In the fourth test, the string “c"\text{“c"} is correct, because “c"=“c"+“”\text{“c"} = \text{“c"} + \text{“”} and a or b can be empty. The other possible solution for this test is “s"\text{“s"}.

Translation

给一个字符串ss，取ss的前缀aa，ss的后缀bb，得到新的字符串t=a+bt=a+b，要求tt的长度不大于ss的长度，且tt是回文串。输出满足条件的长度最长的字符串tt。
a,ba,b可为空串。

Idea

Easy  versionEasy\ \ version允许算法时间复杂度为O(n2)O(n^2)。
先去头尾，将字符串中对称的前后缀删除并保存，在剩下的字符串中找到最长的回文前后缀，选取两者之间最长的，左右各拼接上原来的头和尾。
举例：字符串“abcdfdcecba”\text{“abcdfdcecba”}，去掉对称的前后缀后为“dfdce”\text{“dfdce”}；剩下的字符串中，最长回文前缀是“dfd”\text{“dfd”}，最长回文后缀是“e”\text{“e”}，因此选择“dfd”\text{“dfd”}；最终答案为“abcdfdcba”\text{“abcdfdcba”} 。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
void solve()
{
	string s;
	cin>>s;
	string ansl="",ansr="";
	int i;
	int l=0,r=s.length()-1;
	while(l<r)//去掉对称的前后缀 
	{
		if(s[l]==s[r])
		{
			l++;
			r--;
		}
		else break;
	}
	//在剩下的字符串中找最长回文前后缀  
	for(i=l;i<=r;i++)
	{
		string prefix=s.substr(l,i-l+1);
		string temp=prefix;
		//直接用算法库中的reverse判断是否回文 
		reverse(temp.begin(),temp.end());
		if(prefix==temp) ansl=prefix;
	}
	for(i=r;i>=l;i--)
	{
		string suffix=s.substr(i,r-i+1);
		string temp=suffix;
		reverse(temp.begin(),temp.end());
		if(suffix==temp) ansr=suffix;
	}
	string ans;
	//取两者中最长的 
	if(ansl.length()>ansr.length()) ans=ansl;
	else ans=ansr;
	//拼接上头和尾 
	ans=s.substr(0,l)+ans+s.substr(r+1,s.length()-r);
	cout<<ans<<endl;
}
int main()
{
	int t;
	cin>>t;
	while(t--) solve();
	return 0; 
}

D2. Prefix-Suffix Palindrome (Hard version)

This is the hard version of the problem. The difference is the constraint on the sum of lengths of strings and the number of test cases. You can make hacks only if you solve all versions of this task.
You are given a string ss, consisting of lowercase English letters. Find the longest string tt, which satisfies the following conditions:

  • The length of tt does not exceed the length of ss.
  • tt is a palindrome.
  • There exists two strings aa and bb (possibly empty), such that t=a+bt=a+b ( “+” represents concatenation), and aa is prefix of ss while bb is suffix of ss.

Input

The input consists of multiple test cases. The first line contains a single integer tt (1⩽t⩽105)(1\leqslant t\leqslant 10^5), the number of test cases. The next tt lines each describe a test case.
Each test case is a non-empty string ss, consisting of lowercase English letters.
It is guaranteed that the sum of lengths of strings over all test cases does not exceed 10610^6.

Output

For each test case, print the longest string which satisfies the conditions described above. If there exists multiple possible solutions, print any of them.

Example

input

5
a
abcdfdcecba
abbaxyzyx
codeforces
acbba

output

a
abcdfdcba
xyzyx
c
abba

Note

In the first test, the string s=“a"s=\text{“a"} satisfies all conditions.
In the second test, the string "abcdfdcba"\text{"abcdfdcba"} satisfies all conditions, because:
Its length is 99, which does not exceed the length of the string ss, which equals 1111.
It is a palindrome.
“abcdfdcba"=“abcdfdc"+“ba"\text{“abcdfdcba"} = \text{“abcdfdc"} + \text{“ba"}, and “abcdfdc"\text{“abcdfdc"} is a prefix of s while “ba"\text{“ba"} is a suffix of ss.
It can be proven that there does not exist a longer string which satisfies the conditions.
In the fourth test, the string “c"\text{“c"} is correct, because “c"=“c"+“”\text{“c"} = \text{“c"} + \text{“”} and a or b can be empty. The other possible solution for this test is “s"\text{“s"}.

Translation

给一个字符串ss，取ss的前缀aa，ss的后缀bb，得到新的字符串t=a+bt=a+b，要求tt的长度不大于ss的长度，且tt是回文串。输出满足条件的长度最长的字符串tt。
a,ba,b可为空串。

Idea

测试样例个数达到10510^5,每个样例的字符串总长度达到10610^6,考虑时间复杂度为O(n)O(n)的Manacher′s  algorithmManacher's \ \ algorithm。
还是采用贪心操作，将字符串头尾截取，在剩下的字符串中找到最长的回文前后缀，选取两者之间最长的，左右各拼接上原来的头和尾。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include<cctype>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1000010;
int p[N<<1];
char initial[N],s[N<<1],temp[N];
int len,n;
void manacher()
{
	int cnt=0;
	int i;
	s[++cnt]='?';//防止越界
	s[++cnt]='#';
	//插入'#'，只计算奇回文。
	for(i=1;i<=n;i++)
	{
		s[++cnt]=temp[i];
		s[++cnt]='#';
	}
	int max_len=0,l=0,r=0;
	int max_right=0;
	int mid=0;
	for(i=2;i<=cnt;i++)
	{
		//如果i在最大半径之内 
		if(i<=max_right) p[i]=min(p[(mid<<1)-i],max_right-i+1);
		//否则p[i]置为1 
		else p[i]=1;
		while(s[i-p[i]]==s[i+p[i]]) 
		{
			if(i+p[i]<=cnt&&i-p[i]>=2)
			{
				p[i]++;
			}
			else break;
		}
		//最大边界和回文中心更新 
		if(i+p[i]>max_right) 
		{
			max_right=i+p[i]-1;
			mid=i;
		}
		//找到一个回文前后缀 
		if(i+p[i]-1==cnt||i-p[i]==1)
		{
			if(max_len<p[i])//更新 
			{
				max_len=p[i];
				l=i-p[i]+1;
				r=i+p[i]-1;
			}
		}
	}
	for(i=l;i<=r;i++) 
	{
		//字符串中间插入了'#'
		if(isalpha(s[i]))
		{
			cout<<s[i];
		}
	} 
	//归零，慎用memset
	fill(p,p+cnt+3,0);
}
void solve()
{
	int i;
	cin>>(initial+1);
	len=n=strlen(initial+1);
	int l=1,r=n;
	//贪心
	while(l<r)
	{
		if(initial[l]==initial[r])
		{
			l++;
			r--;
		}
		else break;
	}
	n=0;
	//读取剩下部分的字符串
	for(i=l;i<=r;i++)
	{
		temp[i-l+1]=initial[i];
		n++;//统计剩下的字符串长度
	}
	for(i=1;i<=l-1;i++) cout<<initial[i];//输出前缀
	manacher();//执行Manacher's algorithm
	for(i=r+1;i<=len;i++) cout<<initial[i];//输出后缀
	cout<<endl;
}
int main()
{
	int t;
	cin>>t;
	while(t--) solve();
	return 0; 
}

Postscript

扩展回文半径时，要加上条件if(i+p[i]<=cnt&&i-p[i]>=2) p[i]++。