A. Kuroni and the Gifts

Kuroni has n daughters. As gifts for them, he bought nn necklaces and nn bracelets:

  • the ii-th necklace has a brightness aia_i, where all the aia_i are pairwise distinct (i.e. all aia_i are different),
  • the ii-th bracelet has a brightness bib_i, where all the bi are pairwise distinct (i.e. all bib_i are different).

Kuroni wants to give exactly one necklace and exactly one bracelet to each of his daughters. To make sure that all of them look unique, the total brightnesses of the gifts given to each daughter should be pairwise distinct. Formally, if the ii-th daughter receives a necklace with brightness xix_i and a bracelet with brightness yiy_i, then the sums xi+yix_i+y_i should be pairwise distinct. Help Kuroni to distribute the gifts.
For example, if the brightnesses are a=[1,7,5]a=[1,7,5] and b=[6,1,2]b=[6,1,2], then we may distribute the gifts as follows:
Give the third necklace and the first bracelet to the first daughter, for a total brightness of a3+b1=11a_3+b_1=11.
Give the first necklace and the third bracelet to the second daughter, for a total brightness of a1+b3=3a_1+b_3=3.
Give the second necklace and the second bracelet to the third daughter, for a total brightness of a2+b2=8a_2+b_2=8.
Here is an example of an invalid distribution:
Give the first necklace and the first bracelet to the first daughter, for a total brightness of a1+b1=7a_1+b_1=7.
Give the second necklace and the second bracelet to the second daughter, for a total brightness of a2+b2=8a_2+b_2=8.
Give the third necklace and the third bracelet to the third daughter, for a total brightness of a3+b3=7a_3+b_3=7.
This distribution is invalid, as the total brightnesses of the gifts received by the first and the third daughter are the same. Don’t make them this upset!

Input

The input consists of multiple test cases. The first line contains an integer t(1≤t≤100)t (1≤t≤100) — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer n(1≤n≤100)n (1≤n≤100) — the number of daughters, necklaces and bracelets.
The second line of each test case contains nn distinct integers a1,a2,…,an(1≤ai≤1000)a_1,a_2,…,a_n (1≤a_i≤1000) — the brightnesses of the necklaces.
The third line of each test case contains n distinct integers b1,b2,…,bn(1≤bi≤1000)b_1,b_2,…,b_n (1≤b_i≤1000) — the brightnesses of the bracelets.

Output

For each test case, print a line containing nn integers x1,x2,…,xnx_1,x_2,…,x_n, representing that the ii-th daughter receives a necklace with brightness xix_i. In the next line print nn integers y1,y2,…,yny_1,y_2,…,y_n, representing that the ii-th daughter receives a bracelet with brightness yiy_i.
The sums x1+y1,x2+y2,…,xn+ynx_1+y_1,x_2+y_2,…,x_n+y_n should all be distinct. The numbers x1,…,xnx_1,…,x_n should be equal to the numbers a1,…,ana_1,…,a_n in some order, and the numbers y1,…,yny_1,…,y_n should be equal to the numbers b1,…,bnb_1,…,b_n in some order.
It can be shown that an answer always exists. If there are multiple possible answers, you may print any of them.

Example

input

2
3
1 8 5
8 4 5
3
1 7 5
6 1 2

output

1 8 5
8 4 5
5 1 7
6 2 1

Note

In the first test case, it is enough to give the ii-th necklace and the ii-th bracelet to the ii-th daughter. The corresponding sums are 1+8=91+8=9,$ 8+4=12$, and 5+5=105+5=10.
The second test case is described in the statement.

Translation

给两个数组a,ba,b，它们都有nn个元素，输出x1,x2,...,xn∈a,y1,y2,...,yn∈bx_1,x_2,...,x_n\in a,y_1,y_2,...,y_n\in b，使得每一个xi+yix_i+y_i是唯一的，保证这样的解存在。

Idea

最小的和最小的配对，最大的和最大的配对。

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
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1003;
int a[N],b[N];
void solve()
{
	int n;
	cin>>n;
	int i;
	for(i=1;i<=n;i++) cin>>a[i];
	for(i=1;i<=n;i++) cin>>b[i];
	sort(a+1,a+1+n);
	sort(b+1,b+1+n);
	for(i=1;i<=n;i++) cout<<a[i]<<' ';
	cout<<endl;
	for(i=1;i<=n;i++) cout<<b[i]<<' ';
	cout<<endl;
}
int main()
{
	int t;
	cin>>t;
	while(t--) solve();
	return 0;
}

B. Kuroni and Simple Strings

Now that Kuroni has reached 10 years old, he is a big boy and doesn’t like arrays of integers as presents anymore. This year he wants a Bracket sequence as a Birthday present. More specifically, he wants a bracket sequence so complex that no matter how hard he tries, he will not be able to remove a simple subsequence!
We say that a string formed by n characters ‘(’ or ‘)’ is simple if its length nn is even and positive, its first n2\frac {n}{2} characters are ‘(’, and its last n2\frac {n}{2} characters are ‘)’. For example, the strings “()” and “(())” are simple, while the strings “)(” and “()()” are not simple.
Kuroni will be given a string formed by characters ‘(’ and ‘)’ (the given string is not necessarily simple). An operation consists of choosing a subsequence of the characters of the string that forms a simple string and removing all the characters of this subsequence from the string. Note that this subsequence doesn’t have to be continuous. For example, he can apply the operation to the string “)()(()))”, to choose a subsequence of bold characters, as it forms a simple string “(())”, delete these bold characters from the string and to get “))()”.
Kuroni has to perform the minimum possible number of operations on the string, in such a way that no more operations can be performed on the remaining string. The resulting string does not have to be empty.
Since the given string is too large, Kuroni is unable to figure out how to minimize the number of operations. Can you help him do it instead?
A sequence of characters a is a subsequence of a string b if a can be obtained from b by deletion of several (possibly, zero or all) characters.

Input

The only line of input contains a string s(1≤∣s∣≤1000)s (1≤|s|≤1000) formed by characters ‘(’ and ‘)’, where ∣s∣|s| is the length of ss.

Output

In the first line, print an integer kk — the minimum number of operations you have to apply. Then, print 2k2k lines describing the operations in the following format:
For each operation, print a line containing an integer mm — the number of characters in the subsequence you will remove.
Then, print a line containing m integers 1≤a1<a2<⋯<am1≤a_1<a_2<⋯<a_m — the indices of the characters you will remove. All integers must be less than or equal to the length of the current string, and the corresponding subsequence must form a simple string.
If there are multiple valid sequences of operations with the smallest kk, you may print any of them.

Examples

input

(()((

output

1
2
1 3

input

)(

output

0

input

(()())

output

1
4
1 2 5 6

Note

In the first sample, the string is "(()((. The operation described corresponds to deleting the bolded subsequence. The resulting string is “(((”, and no more operations can be performed on it. Another valid answer is choosing indices 2 and 3, which results in the same final string.
In the second sample, it is already impossible to perform any operations.

Translation

要从一个括号序列中删除一个形如simplesimple $ string的子序列，直到不能删除为止，输出至少删除的次数，以及子序列中每一个元素在原序列中的位置。的子序列，直到不能删除为止，输出至少删除的次数，以及子序列中每一个元素在原序列中的位置。 simple$ $ string$ 前n2\frac {n}{2}个字符都为’(‘，后n2\frac {n}{2}个字符都为’)'。

Idea

若原字符串中含有simplesimple $ string$，那么我们一次把这个 simplesimple $ string$ 全部删除，最少的操作次数是11；如果根本没有simplesimple $ string$，那么最少操作次数就是00。
删除对称的括号时，为了不破坏对称性，用双指针 l,rl,r 从两边向中心逼近，对称地删除括号，这样得到的解是最优的。

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<cstring>
#include<algorithm>
#include<vector>
using namespace std;
void solve()
{
	char s[1009];
	cin>>(s+1);
	int len=strlen(s+1);
	int l=1,r=len;
	vector<int>pos;
	while(l<r)
	{
		while(true)
		{
			if(s[l]=='('||l>=r) break;//在左端找到'(' 
			else l++;
		}
		while(true)
		{
			if(s[r]==')'||r<=l) break;//在右端找到')' 
			else r--; 
		}
		//存储合法的位置 
		if(l<r) pos.push_back(l);
		if(r>l) pos.push_back(r);
		//继续逼近 
		l++;
		r--;
	}
	if(pos.size())
	{
		cout<<1<<endl;
		cout<<pos.size()<<endl;
		sort(pos.begin(),pos.end());//排序，按在原序列中的顺序输出 
		for(auto v:pos) cout<<v<<' ';
	}
	else cout<<0;
}
int main()
{
	solve();
	return 0;
}

C. Kuroni and Impossible Calculation

To become the king of Codeforces, Kuroni has to solve the following problem.
He is given nn numbers a1,a2,…,ana_1, a_2, \dots, a_n. Help Kuroni to calculate ∏1⩽i<j⩽n∣ai−aj∣\prod\limits_{1 \leqslant i < j \leqslant n} {\left| a_i-a_j\right|}. As result can be very big, output it modulo mm.

If you are not familiar with short notation, $\prod\limits_{1 \leqslant i < j \leqslant n} {\left| a_i - a_j \right|} $ is equal to ∣a1−a2∣⋅∣a1−a3∣⋅⋯⋅∣a1−an∣⋅∣a2−a3∣⋅∣a2−a4∣⋅…⋅∣a2−an∣⋅…⋅∣an−1−an∣|a_1−a_2|⋅|a_1−a_3|⋅ \dots ⋅|a_1−a_n|⋅|a_2−a_3|⋅|a_2−a_4|⋅ … ⋅|a_2−a_n|⋅ … ⋅|a_{n−1}−a_n|. In other words, this is the product of ∣ai−aj∣|a_i−a_j| for all 1≤i<j≤n1≤i<j≤n.

Input

The first line contains two integers n,m(2≤n≤2⋅105,1≤m≤1000)n, m (2≤n≤2⋅10^5, 1≤m≤1000) — number of numbers and modulo.
The second line contains nn integers a1,a2,…,an(0≤ai≤109)a_1,a_2,…,a_n (0≤a_i≤10^9).

Output

Output the single number — (∏1⩽i<j⩽n∣ai−aj∣) mod m\left( \prod\limits_{1 \leqslant i < j \leqslant n} {\left| a_i - a_j \right|} \right)\bmod m.

Examples

input

2 10
8 5

output

3

input

3 12
1 4 5

output

0

input

3 7
1 4 9

output

1

Note

In the first sample, ∣8−5∣=3≡3 mod 10|8−5|=3≡3 \bmod10.
In the second sample, ∣1−4∣⋅∣1−5∣⋅∣4−5∣=3⋅4⋅1=12≡0 mod 12|1−4|⋅|1−5|⋅|4−5|=3⋅4⋅1=12≡0\bmod 12.
In the third sample, ∣1−4∣⋅∣1−9∣⋅∣4−9∣=3⋅8⋅5=120≡1 mod 7|1−4|⋅|1−9|⋅|4−9|=3⋅8⋅5=120≡1\bmod 7.

Translation

给一个数组aa，计算(∏1⩽i<j⩽n∣ai−aj∣) mod m\left( \prod\limits_{1 \leqslant i < j \leqslant n} {\left| a_i - a_j \right|}\right)\bmod m。

Idea

直接暴力计算肯定不行，但是有意思的是，题目给了模数m(1≤m≤1000)m(1≤m≤1000)。
当n≤mn≤m时，我们可以直接O(n2)O(n^2)暴力算；但是当n>mn >m时（比如n=200000n=200000），显然会TLE，这时模数 mm 就很耐人寻味。
一个数xx，对mm取余的结果在区间[0,m−1][0,m-1]内，也就是说，nn个数中最对只能有mm个数对mm取余的结果不同，剩下的n−mn-m个数一定能在mm个数中找到余数相同的数，所以相乘答案为00。

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
#include<iostream>
#include<cmath>
#define ll long long
using namespace std;
ll a[200005];
ll n,m;
ll ans=1;
void solve()
{
	cin>>n>>m;
	int i;
	for(i=1;i<=n;i++) cin>>a[i];
	if(n>m) cout<<0;
	else 
	{
		int j;
		for(i=1;i<=n;i++)
		{
			for(j=i+1;j<=n;j++)
			{
				ans=ans*abs(a[i]-a[j])%m;
			}
		}
		cout<<ans;
	}
}
int main()
{
	solve();
	return 0;
}

D. Kuroni and the Celebration

This is an interactive problem.
After getting AC after 13 Time Limit Exceeded verdicts on a geometry problem, Kuroni went to an Italian restaurant to celebrate this holy achievement. Unfortunately, the excess sauce disoriented him, and he’s now lost!
The United States of America can be modeled as a tree (why though) with nn vertices. The tree is rooted at vertex rr, wherein lies Kuroni’s hotel.
Kuroni has a phone app designed to help him in such emergency cases. To use the app, he has to input two vertices uu and vv, and it’ll return a vertex ww, which is the lowest common ancestor of those two vertices.
However, since the phone’s battery has been almost drained out from live-streaming Kuroni’s celebration party, he could only use the app at most ⌊n2⌋⌊\frac {n}{2}⌋ times. After that, the phone would die and there will be nothing left to help our dear friend! :(
As the night is cold and dark, Kuroni needs to get back, so that he can reunite with his comfy bed and pillow(s). Can you help him figure out his hotel’s location?
Interaction
The interaction starts with reading a single integer n(2≤n≤1000)n (2≤n≤1000), the number of vertices of the tree.
Then you will read n−1n−1 lines, the i-th of them has two integers xix_i and yi(1≤xi,yi≤n,xi≠yi)y_i (1≤x_i,y_i≤n, x_i≠y_i), denoting there is an edge connecting vertices xix_i and yiy_i. It is guaranteed that the edges will form a tree.
Then you can make queries of type “? u v” $ (1≤u,v≤n)$ to find the lowest common ancestor of vertex uu and vv.
After the query, read the result w as an integer.
In case your query is invalid or you asked more than ⌊n2⌋⌊\frac {n}{2}⌋ queries, the program will print −1−1 and will finish interaction. You will receive a Wrong answer verdict. Make sure to exit immediately to avoid getting other verdicts.
When you find out the vertex r, print “! r” and quit after that. This query does not count towards the ⌊n2⌋⌊\frac {n}{2}⌋ limit.
Note that the tree is fixed beforehand and will not change during the queries, i.e. the interactor is not adaptive.
After printing any query do not forget to print end of line and flush the output. Otherwise, you might get Idleness limit exceeded. To do this, use:

  • fflush(stdout) or cout.flush() in C++;
  • System.out.flush() in Java;
  • flush(output) in Pascal;
  • stdout.flush() in Python;
    see the documentation for other languages.
    Hacks
    To hack, use the following format:
    The first line should contain two integers nn and r(2≤n≤1000,1≤r≤n)r (2≤n≤1000, 1≤r≤n), denoting the number of vertices and the vertex with Kuroni’s hotel.
    The ii-th of the next n−1n−1 lines should contain two integers xix_i and yi(1≤xi,yi≤n)y_i (1≤xi,yi≤n) — denoting there is an edge connecting vertex xix_i and yiy_i.
    The edges presented should form a tree.

Example

input

6
1 4
4 2
5 3
6 3
2 3

3
4
4

output

? 5 6
? 3 1
? 1 2
! 4

Note

Note that the example interaction contains extra empty lines so that it’s easier to read. The real interaction doesn’t contain any empty lines and you shouldn’t print any extra empty lines as well.
The image below demonstrates the tree in the sample test:

Translation

这是一道互动题，测评 机会给你一颗树，你可以向测评机询问一对节点(a,b)(a,b)的LCA，要求询问不超过$\left\lfloor {\frac{n}{2}} \right\rfloor $次，得到树的根节点。

Idea

应该说，树的根节点应该是相对的，每一个节点都可以作为根节点。通过询问，我们能找到测评机所选定的根节点。
我们将所有节点放入集合nodenode，并建成树形图GG；每次询问一对叶子节点（度数为11）的LCA，如果得到的LCA是这两个叶子节点的其中一个，那么我们就找到根节点了；如果还没有找到，我们就把叶子节点删掉（从节点集合中去掉，从树上删除节点），继续找。

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
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=1002;
vector<int>G[N];
vector<int>node;
int n;
void build()
{
	cin>>n;
	int i;
	for(i=1;i<=n;i++) node.push_back(i);
	for(i=1;i<=n-1;i++)
	{
		int u,v;
		cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
}
void solve()
{
	build();
	int i;
	while(true)
	{
		if(node.size()==1)//如果只剩下一个节点，也就找到了根节点 
		{
			printf("! %d\n",node[0]);
			break;
		}
		else
		{
			int l=-1,r=-1,lca;
			for(auto i:node)//遍历所有节点
			{
				if(G[i].size()==1)//找两个叶子节点
				{
					if(l==-1) l=i;
					else if(r==-1) r=i;
					else break;
				}
			}
			printf("? %d %d\n",l,r);
			fflush(stdout);
			cin>>lca;
			if(lca==l||lca==r)
			{
				printf("! %d\n",lca);
				break;
			}
			else
			{
				vector<int>::iterator it;
				for(it=node.begin();it!=node.end();)//从节点集合中删除
				{
					if(*it==l||*it==r) it=node.erase(it);
					else it++;
				}
				for(i=1;i<=n;i++)//从图中删除
				{
					for(it=G[i].begin();it!=G[i].end();)
					{
						if(*it==l||*it==r) it=G[i].erase(it);
						else it++;
					}
				}
			}
		}		
	}
}
int main()
{
	solve();
	return 0;
}

E. Kuroni and the Score Distribution

Kuroni is the coordinator of the next Mathforces round written by the “Proof by AC” team. All the preparation has been done, and he is discussing with the team about the score distribution for the round.
The round consists of n problems, numbered from 11 to nn. The problems are ordered in increasing order of difficulty, no two problems have the same difficulty. A score distribution for the round can be denoted by an array 1≤a1<a2<⋯<an≤1091 \leq a_1 < a_2 < \dots < a_n \leq 10^9, where aia_i is the score of ii-th problem.
Kuroni thinks that the score distribution should satisfy the following requirements:
The score of each problem should be a positive integer not exceeding 10910^9.
A harder problem should grant a strictly higher score than an easier problem. In other words, 1≤a1<a2<⋯<an≤1091≤a_1<a_2<⋯<a_n≤10^9.
The balance of the score distribution, defined as the number of triples (i,j,k)(i,j,k) such that 1≤i<j<k≤n1≤i<j<k≤n and ai+aj=aka_i+a_j=a_k, should be exactly mm.
Help the team find a score distribution that satisfies Kuroni’s requirement. In case such a score distribution does not exist, output −1−1.

Input

The first and single line contains two integers nn and m(1≤n≤5000,0≤m≤109)m (1≤n≤5000, 0≤m≤10^9) — the number of problems and the required balance.

Output

If there is no solution, print a single integer −1−1.
Otherwise, print a line containing n integers a1,a2,…,ana_1,a_2,…,a_n, representing a score distribution that satisfies all the requirements. If there are multiple answers, print any of them.

Examples

input

5 3

output

4 5 9 13 18

input

8 0

output

10 11 12 13 14 15 16 17

input

4 10

output

-1

Note

In the first example, there are 33 triples (i,j,k)(i,j,k) that contribute to the balance of the score distribution.

  • (1,2,3)(1,2,3)
  • (1,3,4)(1,3,4)
  • (2,4,5)(2,4,5)

Translation

构造一个长度为nn的数列，使得满足ai+aj=ak(1≤i<j<k≤n)a_i+a_j=a_k(1≤i<j<k≤n)的三元数对(i,j,k)(i,j,k)的个数恰好为mm个。

Idea

显然1,2,3,4,5,6,⋯ ,x1,2,3,4,5,6, \cdots ,x这样的数字能构成最多的满足条件的(i,j,k)(i,j,k)数对。对于1,2,3,4,5,6,⋯ ,x1,2,3,4,5,6, \cdots ,x,满足条件的数对个数有⌊02⌋+⌊12⌋+⋯+⌊x−12⌋=N\lfloor \frac{0}{2} \rfloor + \lfloor \frac{1}{2} \rfloor + \dots + \lfloor \frac{x-1}{2} \rfloor = N。若最多只给nn个数，但是NN仍然小于mm，那么就不能构造出要求的数列；否则一定能构造出来。
找规律得到，末尾的nn每增加22，满足条件的数对就减少一个，所以只要输出刚刚达到上限mm的xx，若还不足nn个数，以后每隔2000020000输出一个数作为补全。

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
#include<iostream>
#define ll long long
using namespace std;
void solve()
{
	ll n,m;
	cin>>n>>m;
	ll i,j;
	bool ok=0;
	ll temp=0;
	for(i=1;i<=n;i++)
	{
		temp+=(i-1)/2;
		if(temp>=m)
		{
			ok=1;
			for(j=1;j<i;j++) cout<<j<<' ';
            /*
            	若temp略微超过m，我们调整最后一位的大小。
            	x每增加2,合法的数对减少一个。
            */
			cout<<i+(temp-m)*2<<' ';
			ll num=i+2*(temp-m)+20000;
			for(j=i+1;j<=n;j++)
			{
				cout<<num<<' ';
				num+=20000;
			}
			break;
		}
	}
	if(!ok) cout<<-1;
}
int main()
{
	solve();
	return 0;
}