A. Even Subset Sum Problem

You are given an array $a$ consisting of $n$ positive integers. Find a non-empty subset of its elements such that their sum is even (i.e. divisible by $2$ ) or determine that there is no such subset.
Both the given array and required subset may contain equal values.

Input

The first line contains a single integer $t (1≤t≤100)$ , number of test cases to solve. Descriptions of t test cases follow.
A description of each test case consists of two lines. The first line contains a single integer $n (1≤n≤100)$ , length of array $a$ .
The second line contains $n$ integers $a_1,a_2,…,a_n (1≤a_i≤100)$ , elements of $a$ . The given array a can contain equal values (duplicates).

Output

For each test case output $−1$ if there is no such subset of elements. Otherwise output positive integer $k$ , number of elements in the required subset. Then output $k$ distinct integers $(1≤p_i≤n)$ , indexes of the chosen elements. If there are multiple solutions output any of them.

Example

input

3
3
1 4 3
1
15
2
3 5

output

1
2
-1
2
1 2

Note

There are three test cases in the example.
In the first test case, you can choose the subset consisting of only the second element. Its sum is $4$ and it is even.
In the second test case, there is only one non-empty subset of elements consisting of the first element, however sum in it is odd, so there is no solution.
In the third test case, the subset consisting of all array’s elements has even sum.

Translation

给一个数集，要求找到任意一个非空子集，使得子集内的所有元素和为偶数。

Idea

如果给定数集中有一个偶数，可以把这个偶数单独拿出来作为子集；如果集合中没有偶数，那就拿两个奇数出来，如果连两个奇数都没有，那就不存在这样的子集。

Code

#include<iostream>
#include<vector>
using namespace std;
const int N=105;
void solve()
{
	int i;
	int a[N];
	vector<int>pos;
	int n;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	for(i=1;i<=n;i++)
	{
		if((a[i]&1)==0)
		{
			cout<<1<<endl;
			cout<<i<<endl;
			return;//找到偶数
		}
		else pos.push_back(i);
	}
	if (pos.size()<=1) cout<<-1<<endl;//只有不到2个奇数
	else cout<<2<<endl<<pos[0]<<' '<<pos[1]<<endl;
}
int main()
{
	int t;
	cin>>t;
	while(t--) solve();
	return 0;
}

B. Count Subrectangles

You are given an array a of length n and array b of length m both consisting of only integers 0 and 1. Consider a matrix c of size n×m formed by following rule: $c_{ij}=a_ib_j$ (i.e. $a_i$ multiplied by $b_j$ ). It’s easy to see that c consists of only zeroes and ones too.
How many subrectangles of size (area) $k$ consisting only of ones are there in $c$ ?
A subrectangle is an intersection of a consecutive (subsequent) segment of rows and a consecutive (subsequent) segment of columns. I.e. consider four integers $x_1,x_2,y_1,y_2 (1≤x_1≤x_2≤n, 1≤y_1≤y_2≤m)$ a subrectangle $c[x1…x2][y1…y2]$ is an intersection of the rows $x_1,x_1+1,x_1+2,…,x_2$ and the columns $y_1,y_1+1,y_1+2,…,y_2$ .
The size (area) of a subrectangle is the total number of cells in it.

Input

The first line contains three integers $n, m$ and $k (1≤n,m≤40000,1≤k≤nm)$ , length of array $a$ , length of array $b$ and required size of subrectangles.
The second line contains n integers $a_1,a_2,…,a_n (0≤a_i≤1)$ , elements of $a$ .
The third line contains m integers $b_1,b_2,…,b_m (0≤b_i≤1)$ , elements of $b$ .

Output

Output single integer — the number of subrectangles of $c$ with size (area) $k$ consisting only of ones.

Examples

input

3 3 2
1 0 1
1 1 1

output

input

3 5 4
1 1 1
1 1 1 1 1

output

Note

In first example matrix $c$ is:

There are $4$ subrectangles of size $2$ consisting of only ones in it:

In second example matrix $c$ is:

Translation

给一个长度为 $n$ 的数组 $a$ ，一个长度为 $m$ 的数组 $b$ ，连个数组都只有 $0$ 或者 $1$ 。 $c$ 数组是二维数组 $c[i][j]=a[i]\times b[j]$ ， $c$ 中连续的一片 $1$ 组成一块面积，问面积为k的矩形有几个。

Idea

$a$ 中一段连续的长度为 $l_a$ 的 $1$ ，和 $b$ 中一段连续的长度为 $l_b$ 的 $1$ ，得到 $c$ 中一块 $l_a\times l_b$ 的面积。
特殊的，在 $a$ 中找一段连续的长度为 $i$ 的 $1$ ，然后在 $b$ 中一段连续的长度为 $\frac{k}{i}$ 的 $1$ ，能得到一块 $k$ 的面积。
只要找出 $k$ 的所有因子 $i$ ，对于每个因子，统计在 $a$ 中长度为 $i$ 个 $1$ 的子列个数，然后在 $b$ 中统计长度为 $\frac{k}{i}$ 个 $1$ 的子列个数。

Code

#include<iostream>
#include<vector>
#define ll long long 
using namespace std;
const int N=40002;
int a[N],b[N];
ll n,m,k;
vector<ll>Kfactor;
void divide(ll x)
{
	ll i;
	for(i=1;i*i<=x;i++)//统计k的因子
	{
		if(x%i==0)
		{
			Kfactor.push_back(i);
			if(i*i!=x) Kfactor.push_back(x/i);
			else continue;
		}
	}
}
void solve()
{
	cin>>n>>m>>k;
	divide(k);
	int i;
	for(i=1;i<=n;i++) cin>>a[i];
	for(i=1;i<=m;i++) cin>>b[i];
	ll ans=0;
	for(auto factor:Kfactor)
	{
		ll cnt=0;
		ll x=0,y=0;
		for(i=1;i<=n;i++)
		{
			if(a[i]) cnt++;//是1长度增加
			else cnt=0;//遇到0，断开
			if(cnt==factor) 找到长度为factor的连续1
			{
				cnt--;//将最前面的1舍弃
				x++;//子列个数加1
			}
		}
		cnt=0;
		for(i=1;i<=m;i++)
		{
			if(b[i]) cnt++;
			else cnt=0;
			if(cnt==k/factor)
			{
				cnt--;
				y++;
			}
		}
		ans=ans+x*y;
	}
	cout<<ans;
}
int main()
{
	solve();
	return 0;
}

C. Unusual Competitions

A bracketed sequence is called correct (regular) if by inserting “+” and “1” you can get a well-formed mathematical expression from it. For example, sequences “(())()”, “()” and “(()(()))” are correct, while “)(”, “(()” and “(()))(” are not.
The teacher gave Dmitry’s class a very strange task — she asked every student to come up with a sequence of arbitrary length, consisting only of opening and closing brackets. After that all the students took turns naming the sequences they had invented. When Dima’s turn came, he suddenly realized that all his classmates got the correct bracketed sequence, and whether he got the correct bracketed sequence, he did not know.
Dima suspects now that he simply missed the word “correct” in the task statement, so now he wants to save the situation by modifying his sequence slightly. More precisely, he can the arbitrary number of times (possibly zero) perform the reorder operation.
The reorder operation consists of choosing an arbitrary consecutive subsegment (substring) of the sequence and then reordering all the characters in it in an arbitrary way. Such operation takes l nanoseconds, where l is the length of the subsegment being reordered. It’s easy to see that reorder operation doesn’t change the number of opening and closing brackets. For example for “))((” he can choose the substring “)(” and do reorder “)()(” (this operation will take 2 nanoseconds).
Since Dima will soon have to answer, he wants to make his sequence correct as fast as possible. Help him to do this, or determine that it’s impossible.

Input

The first line contains a single integer $n (1≤n≤10^6)$ — the length of Dima’s sequence.
The second line contains string of length $n$ , consisting of characters “(” and “)” only.

Output

Print a single integer — the minimum number of nanoseconds to make the sequence correct or “-1” if it is impossible to do so.

Examples

input

8
))((())(

output

input

3
(()

output

-1

Note

In the first example we can firstly reorder the segment from first to the fourth character, replacing it with “()()”, the whole sequence will be “()()())(”. And then reorder the segment from the seventh to eighth character, replacing it with “()”. In the end the sequence will be “()()()()”, while the total time spent is $4+2=6$ nanoseconds.

Translation

给一个括号序列，每次可以选择一个长度为 $l$ 的子列，任意调整其中括号的位置，花费的时间是 $l$ ，问至少需要花费多少时间，得到一个合法序列。

Idea

如果整个括号序列’(‘和’)‘的个数不相同，那么肯定不能得到合法的括号序列，否则一定能（比如直接调整整个序列）。
贪心得选择一段’(‘和’)‘个数相同的不合法子列（以’(‘结尾，’(‘和’)'个数相同），将其调整，然后寻找下一段没有调整的子列。此处运用单指针 $pos$ 对位置 $i$ 进行迭代。

Code

#include<iostream>
#include<string>
using namespace std;
void solve()
{
	int n;
	cin>>n;
	string s;
	cin>>s;
	int c=0;
	int i;
	for(i=0;i<n;i++)
	{
		if(s[i]==')') c++;
		else c--;
	}
	if(c) cout<<-1;
	else
	{
		int pos=-1;//pos初始化必须为-1
		int ans=0;
		int c1=0,c2=0;
		for(i=0;i<n;i++)
		{
			if(s[i]=='(')
			{
				c1++;
				if(c1==c2)
				{
					ans=ans+i-pos;
					pos=i;
				}
			}
			else
			{
				c2++;
				if(c1==c2)//前i个处理完毕
				{
					pos=i;
				}
			}
		}
		cout<<ans;
	}
}
int main()
{
	solve();
	return 0;
}