A. Add Odd or Subtract Even

You are given two positive integers a and b.
In one move, you can change a in the following way:

  • Choose any positive odd integer x (x>0) and replace a with a+x;
  • choose any positive even integer y (y>0) and replace a with a−y.

You can perform as many such operations as you want. You can choose the same numbers x and y in different moves.
Your task is to find the minimum number of moves required to obtain b from a. It is guaranteed that you can always obtain b from a.
You have to answer t independent test cases.

Input

The first line of the input contains one integer t(1≤t≤104)t (1≤t≤10^4) — the number of test cases.
Then t test cases follow. Each test case is given as two space-separated integers a and b (1≤a,b≤109)(1≤a,b≤10^9).

Output

For each test case, print the answer — the minimum number of moves required to obtain b from a if you can perform any number of moves described in the problem statement. It is guaranteed that you can always obtain bb from aa.

Example

input

5
2 3
10 10
2 4
7 4
9 3

output

1
0
2
2
1

Note

In the first test case, you can just add 1.
In the second test case, you don’t need to do anything.
In the third test case, you can add 1 two times.
In the fourth test case, you can subtract 4 and add 1.
In the fifth test case, you can just subtract 6.

Translation

给两个数a,ba,b，可以作如下两种操作：

  • 给aa加上奇数x(x>0)x(x>0)；
  • 给aa减去偶数y(y>0)y(y>0)。

问从aa变化到bb至少需要几次操作。

Idea

要知道，一个数加上或减去偶数奇偶性不变，加上或减去奇数，奇偶性改变。
因此，若a,ba,b同奇偶且a>ba>b，我们只需a−ya-y；若a,ba,b奇偶性不同且a<ba<b，我们只需a+xa+x。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
using namespace std;
void solve()
{
	ll a,b;
	cin>>a>>b;
	if(a==b) cout<<0<<endl;
	else if(a<b&&(a&1)!=(b&1)) cout<<1<<endl;
	else if(a>b&&(a&1)==(b&1)) cout<<1<<endl;
	else cout<<2<<endl;
}
int main()
{
	ios::sync_with_stdio(false);
	int t;
	cin>>t;
	while(t--) solve();
	return 0;
}

B. WeirdSort

You are given an array aa of length nn.
You are also given a set of distinct positions$ p_1,p_2,…,p_m$, where 1≤pi<n1≤p_i<n. The position pi means that you can swap elements a[pi]a[pi] and$ a[p_i+1]$. You can apply this operation any number of times for each of the given positions.
Your task is to determine if it is possible to sort the initial array in non-decreasing order $(a_1≤a_2≤⋯≤a_n) $using only allowed swaps.
For example, if a=[3,2,1]a=[3,2,1] and p=[1,2]p=[1,2], then we can first swap elements a[2]a[2] and a[3]a[3] (because position 22 is contained in the given set$ p$). We get the array a=[3,1,2]a=[3,1,2]. Then we swap a[1]a[1]and a[2]a[2] (position 11 is also contained in pp). We get the array a=[1,3,2]a=[1,3,2]. Finally, we swap$ a[2]$ and a[3]a[3] again and get the array a=[1,2,3]a=[1,2,3], sorted in non-decreasing order.
You can see that if a=[4,1,2,3]a=[4,1,2,3] and$ p=[3,2]$ then you cannot sort the array.
You have to answer tt independent test cases.

Input

The first line of the input contains one integer t(1≤t≤100)t (1≤t≤100) — the number of test cases.
Then t test cases follow. The first line of each test case contains two integers$ n$ and m(1≤m<n≤100)m (1≤m<n≤100) — the number of elements in a and the number of elements in$ p$. The second line of the test case contains n integers a1,a2,…,an(1≤ai≤100)a1,a2,…,a_n (1≤a_i≤100). The third line of the test case contains m integers p1,p2,…,pmp_1,p_2,…,p_m (1≤pi<n1≤p_i<n, all $ p_i$ are distinct) — the set of positions described in the problem statement.

Output

For each test case, print the answer — “YES” (without quotes) if you can sort the initial array in non-decreasing order$ (a_1≤a_2≤⋯≤a_n)$ using only allowed swaps. Otherwise, print “NO”.

Example

input

6
3 2
3 2 1
1 2
4 2
4 1 2 3
3 2
5 1
1 2 3 4 5
1
4 2
2 1 4 3
1 3
4 2
4 3 2 1
1 3
5 2
2 1 2 3 3
1 4

output

YES
NO
YES
YES
NO
YES

Translation

给一个数列a1,a2,...,ana_1,a_2,...,a_n，一个序列p1,p2,...,pmp_1,p_2,...,p_m。交换是合法的，问能否靠合法交换，得到不下降序列aa。

Idea

数据规模非常小，考虑暴力。遍历pp，如果发现a[p[i]]>a[p[i]+1]a[p[i]]>a[p[i]+1]，则交换，将上述操作进行TT次（将TT取非常大），应该就能得到下降序列了，如果还没有得到，那就是不行。
这是不禁好奇，T最多取多大能保证不TLE，于是做了个测试（我手算二分哪！），把TT逼近到T=193999T=193999,T=194000T=194000时有大概率会TLE。实际上T不需要取这么大。

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
#include<iostream>
#include<algorithm>
using namespace std;
void solve()
{
	const int N=110;
	int a[N],p[N];
	int n,m;
	cin>>n>>m;
	int i;
	for(i=1;i<=n;i++) cin>>a[i];
	for(i=1;i<=m;i++) cin>>p[i];
	int T=193999;
	while(T--)
	{
		for(i=1;i<=m;i++)
		{
			if(p[i]+1<=n&&a[p[i]]>a[p[i]+1]) swap(a[p[i]],a[p[i]+1]);
		}
	}
	bool ok=1;
	for(i=1;i<n;i++)
	{
		if(a[i]>a[i+1])
		{
			ok=0;
			break;
		}
	}
	if(ok) cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	while(t--) solve();
	return 0;
}

C. Perform the Combo

You want to perform the combo on your opponent in one popular fighting game. The combo is the string s consisting of n lowercase Latin letters. To perform the combo, you have to press all buttons in the order they appear in s. I.e. if s=“abca” then you have to press ‘a’, then ‘b’, ‘c’ and ‘a’ again.
You know that you will spend m wrong tries to perform the combo and during the ii-th try you will make a mistake right after pip_i-th button (1≤pi<n1≤p_i<n) (i.e. you will press first pi buttons right and start performing the combo from the beginning). It is guaranteed that during the m+1m+1-th try you press all buttons right and finally perform the combo.
I.e. if s=“abca”, m=2 and p=[1,3] then the sequence of pressed buttons will be ‘a’ (here you’re making a mistake and start performing the combo from the beginning), ‘a’, ‘b’, ‘c’, (here you’re making a mistake and start performing the combo from the beginning), ‘a’ (note that at this point you will not perform the combo because of the mistake), ‘b’, ‘c’, ‘a’.
Your task is to calculate for each button (letter) the number of times you’ll press it.
You have to answer tt independent test cases.

Input

The first line of the input contains one integer t(1≤t≤104)t (1≤t≤10^4) — the number of test cases.
Then t test cases follow.
The first line of each test case contains two integers n and m$ (2≤n≤2⋅10^5, 1≤m≤2⋅10^5)$ — the length of s and the number of tries correspondingly.
The second line of each test case contains the string s consisting of n lowercase Latin letters.
The third line of each test case contains m integers p1,p2,…,pm(1≤pi<n)p_1,p_2,…,p_m (1≤p_i<n) — the number of characters pressed right during the ii-th try.
It is guaranteed that the sum of n and the sum of m both does not exceed$ 2⋅10^5 (∑n≤2⋅10^5, ∑m≤2⋅10^5)$.
It is guaranteed that the answer for each letter does not exceed $ 2⋅10^9$.

Output

For each test case, print the answer — 26 integers: the number of times you press the button ‘a’, the number of times you press the button ‘b’, …, the number of times you press the button ‘z’.

Example

input

3
4 2
abca
1 3
10 5
codeforces
2 8 3 2 9
26 10
qwertyuioplkjhgfdsazxcvbnm
20 10 1 2 3 5 10 5 9 4

output

4 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 9 4 5 3 0 0 0 0 0 0 0 0 9 0 0 3 1 0 0 0 0 0 0 0
2 1 1 2 9 2 2 2 5 2 2 2 1 1 5 4 11 8 2 7 5 1 10 1 5 2

Note

The first test case is described in the problem statement. Wrong tries are “a”, “abc” and the final try is “abca”. The number of times you press ‘a’ is 4, ‘b’ is 2 and ‘c’ is 2.
In the second test case, there are five wrong tries: “co”, “codeforc”, “cod”, “co”, “codeforce” and the final try is “codeforces”. The number of times you press ‘c’ is 9, ‘d’ is 4, ‘e’ is 5, ‘f’ is 3, ‘o’ is 9, ‘r’ is 3 and ‘s’ is 1.

Translation

这题不太好读，看Note对样例的解释就好理解一些。简单来说就是给一个长度为nn的字符串，字符位置从1开始，给一堆位置p1,p2,…,pm(1≤pi<n)p_1,p_2,…,p_m (1≤p_i<n)，每一次都从11出发，走到pip_i，mm次这样的操作26个字母出现了几次。

Idea

这很明显是一个前缀和问题，因为每一次都从11出发，出现了重叠的区间。
对每一个位置ii，维护从11开始到ii出现的2626个字母个数prefix[i][26]prefix[i][26]。
获取prefixprefix的方法很简单，我们只需要先遍历字符串，把第ii位出现的字母作标记，即prefix[i][s[i]−a]++prefix[i][s[i]-a]++，再将前i−1i-1位出现字母的个数向ii位累加即可，即作一次前缀和操作。
然后只要将mm次操作出现的字母个数累加即可。当然，最后一次经过整个字符串的操作不算在这mm次里，需要单独再算一次。
！注意！：慎用memsetmemset初始化，因为有很多testtest $ cases，用，用memset$进行了多余的初始化，容易TLE。我在此受到血的教训！

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
#include<cstring>
#include<iostream>
using namespace std;
const int N=200007;
int ans[26],prefix[N][26];
char s[N];
void solve()
{	
	memset(ans,0,sizeof(ans));
	int i,j;
	int n,m;
	cin>>n>>m;
	for(i=1;i<=n;i++) memset(prefix[i],0,sizeof(prefix[i]));
	cin>>(s+1);		
	for(i=1;i<=n;i++) prefix[i][s[i]-'a']++;
	for(i=2;i<=n;i++) //前缀和操作
	{
		for(j=0;j<26;j++) 
		{
			prefix[i][j]+=prefix[i-1][j];
		}
	}
	for(i=1;i<=m;i++)
	{
		int opt;
		cin>>opt;
		for(j=0;j<26;j++) 
		{
			ans[j]+=prefix[opt][j];
		}
	}
	for(i=1;i<=n;i++) ans[s[i]-'a']++;//算上最后的一次
	for(i=0;i<26;i++) 
	{
		cout<<ans[i];
		if(i==25) cout<<endl;
		else cout<<' ';
	}  
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	while(t--) solve();
	return 0;
}

如果想避免初始化操作，建议参考下面骚代码

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
#include<cstdio>
using namespace std;
const int N=200007;
int ans[26],prefix[N][26];
char s[N];
void solve()
{
	int n,m;
	scanf("%d%d%s",&n,&m,s+1);
	int i,j;
	//前缀处理 
	for(i=1;i<=n;i++) 
	{
		for(j=0;j<26;j++) 
		{
			//第一步循环进来prefix[0][j]=0，于是所有的值都往后覆盖了。
			prefix[i][j]=prefix[i-1][j];
		}
		prefix[i][s[i]-'a']++;
	}
	for(i=0;i<26;i++) ans[i]=prefix[n][i];//ans也被覆盖
	for(i=1;i<=m;i++)
	{
		int opt;
		scanf("%d",&opt);
		for(j=0;j<26;j++) 
		{
			ans[j]+=prefix[opt][j];
		}
	}
	for(i=0;i<26;i++) 
	{
		printf("%d",ans[i]);
		if(i<25) putchar(' ');
		else putchar('\n');
	}  
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--) solve();
	return 0;
}

D. Three Integers

You are given three integers a≤b≤ca≤b≤c.
In one move, you can add +1 or −1 to any of these integers (i.e. increase or decrease any number by one). You can perform such operation any (possibly, zero) number of times, you can even perform this operation several times with one number. Note that you cannot make non-positive numbers using such operations.
You have to perform the minimum number of such operations in order to obtain three integers A≤B≤CA≤B≤C such that BB is divisible by AA and CC is divisible by BB.
You have to answer t independent test cases.

Input

The first line of the input contains one integer t(1≤t≤100)t (1≤t≤100) — the number of test cases.
The next t lines describe test cases. Each test case is given on a separate line as three space-separated integers a,ba,b and c(1≤a≤b≤c≤104)c (1≤a≤b≤c≤10^4).

Output

For each test case, print the answer. In the first line print res — the minimum number of operations you have to perform to obtain three integers$ A≤B≤C$ such that B is divisible by$ A$ and$ C$ is divisible by BB. On the second line print any suitable triple $A,B $and CC.

Example

input

8
1 2 3
123 321 456
5 10 15
15 18 21
100 100 101
1 22 29
3 19 38
6 30 46

output

1
1 1 3
102
114 228 456
4
4 8 16
6
18 18 18
1
100 100 100
7
1 22 22
2
1 19 38
8
6 24 48

Translation

给三个数a,b,ca,b,c，每一次操作，可以从三个数中选一个数，进行+1+1或−1-1两种操作，问至少几次操作使得bb能被aa整除，cc能被bb整除。输出最小次数和修改后的a,b,ca,b,c。

Idea

a,b,ca,b,c不是很大，可以考虑暴力构造一下。枚举的上界不能过小，否则就被hack了。

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
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#define ll long long
#define prefix pre
using namespace std;
void solve()
{
	int aa,bb,cc;
	int a,b,c;
	cin>>a>>b>>c;
	int ans=1000000000;
	const int n=20000;
	int i,j,k;
	for(i=1;i<=n;i++)
	{
		for(j=1;i*j<=n;j++)
		{
			for(k=1;k*j*i<=n;k++)
			{
				if(abs(i*j*k-c)+abs(a-i)+abs(i*j-b)<ans)
				{
					ans=abs(i*j*k-c)+abs(a-i)+abs(i*j-b);
					aa=i;
					bb=i*j;
					cc=i*j*k;
				}
			}
		}
	}
	cout<<ans<<endl<<aa<<' '<<bb<<' '<<cc<<endl;
}
int main()
{
	ios::sync_with_stdio(false);
	int t;
	cin>>t;
	while(t--) solve();
	return 0;
}

F. Moving Points

There are n points on a coordinate axis OX. The i-th point is located at the integer point xix_i and has a speed vi. It is guaranteed that no two points occupy the same coordinate. All nn points move with the constant speed, the coordinate of the i-th point at the moment t (t can be non-integer) is calculated as xi+t⋅vix_i+t⋅v_i.
Consider two points$ i$ and jj. Let d(i,j)d(i,j) be the minimum possible distance between these two points over any possible moments of time (even non-integer). It means that if two points i and j coincide at some moment, the value d(i,j)d(i,j) will be 0.
Your task is to calculate the value$\sum\limits_{{\text{1}} \leqslant i < j \leqslant n} {d(i,j)} $ (the sum of minimum distances over all pairs of points).

Input

The first line of the input contains one integer$ n (2≤n≤2⋅10^5)$ — the number of points.
The second line of the input contains n integers$ x_1,x_2,…,x_n (1≤x_i≤10^8)$, where xi is the initial coordinate of the i-th point. It is guaranteed that all xi are distinct.
The third line of the input contains n integers v1,v2,…,vn(−108≤vi≤108)v_1,v_2,…,v_n (−10^8≤vi≤10^8), where vi is the speed of the i-th point.

Output

Print one integer — the value$\sum\limits_{{\text{1}} \leqslant i < j \leqslant n} {d(i,j)} $ (the sum of minimum distances over all pairs of points).

Examples

input

3
1 3 2
-100 2 3

output

3

input

5
2 1 4 3 5
2 2 2 3 4

output

19

input

2
2 1
-3 0

output

0

Translation

有nn个动点在一维坐标轴上匀速移动，每个动点给出初始坐标和移动速度。令d（i,j）d（i,j）是在任何可能的时刻（甚至是非整数），这两点之间的最小可能距离。任务是计算$\sum\limits_{{\text{1}} \leqslant i < j \leqslant n} {d(i,j)} $。

Idea

对于所有xi<xjx_i<x_j，最小距离有两种情况：

  • 若vi>vjv_i>v_j，两点会在一开始相互靠近，最小距离为0；
  • 若vi≤vjv_i≤v_j，两点互相远离，最小距离即为初态。

为了能够进行上述的讨论，我们要将xx进行升序排序。然后另开一个数组存所有的速度，排序并去重。利用二分查找速度数组得出小于当前点速度的点个数。开两个树状数组，一个cntcnt维护速度小于vv的个数，一个sumsum维护速度小于vv的xx之和。从左向右扫描一遍所有的点，每次加上x×cnt−sumx×cnt-sum，并将状态加入树状数组中维护即可。
这属于树状数组的单点更新和区间查询，假设当前第ii个点的point[i].vpoint[i].v在所有vv中排在idxidx位；我们需要查询1−>idx1->idx小于vv的个数cntcnt，和1−>idx1->idx小于vv的xx之和sumsum；每次更新时cnt+1cnt+1，sum+point[i].xsum+point[i].x。

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
#include<algorithm>
#include<iostream>
#define ll long long
using namespace std;
const int N=200007;
ll v[N],cnt[N],sum[N],ans;
int len;
int n;
inline int lowbit(int x)
{
	return x&(-x);
}
struct node
{
	int x,v;
	bool operator<(node &a)const
	{
		return x<a.x;
	}
}point[N];
void update(int x,int val)
{
	while(x<=n)
	{
		cnt[x]++;
		sum[x]+=val;
		x+=lowbit(x);
	}
}
ll query(int x,ll a[])
{
	ll res=0;
	while(x)
	{
		res+=a[x];
		x-=lowbit(x);
	}
	return res;
}
void solve()
{	
	cin>>n;
	int i;
	for(i=1;i<=n;i++) cin>>point[i].x;
	for(i=1;i<=n;i++)
	{
		cin>>point[i].v;
		v[i]=point[i].v;
	}
	sort(point+1,point+1+n);
	sort(v+1,v+1+n);
	len=unique(v+1,v+1+n)-(v+1);//去重是为了算排位
	for(i=1;i<=n;i++)
	{
		int idx=lower_bound(v+1,v+1+len,point[i].v)-v;
		ans+=point[i].x*query(idx,cnt)-query(idx,sum);
		//已经加入树状数组的元素的x都会比当前的x[i]小
		update(idx,point[i].x);
	}
	cout<<ans;
}
int main()
{
	ios::sync_with_stdio(false);
	solve();
	return 0;
}