本文共 14785 字，大约阅读时间需要 49 分钟。

Two distinct points CodeForces - 1108A

You are given two segments [l1;r1] and [l2;r2] on the x-axis. It is guaranteed that l1<r1 and l2<r2. Segments may intersect, overlap or even coincide with each other. The example of two segments on the x-axis. Your problem is to find two integers a and b such that l1≤a≤r1, l2≤b≤r2 and a≠b. In other words, you have to choose two distinct integer points in such a way that the first point belongs to the segment [l1;r1] and the second one belongs to the segment [l2;r2].

It is guaranteed that the answer exists. If there are multiple answers, you can print any of them.

You have to answer q independent queries.

Input

The first line of the input contains one integer q (1≤q≤500) — the number of queries.

Each of the next q lines contains four integers l1i,r1i,l2i and r2i (1≤l1i,r1i,l2i,r2i≤109,l1i<r1i,l2i<r2i) — the ends of the segments in the i-th query.

Output

Print 2q integers. For the i-th query print two integers ai and bi — such numbers that l1i≤ai≤r1i, l2i≤bi≤r2i and ai≠bi. Queries are numbered in order of the input.

It is guaranteed that the answer exists. If there are multiple answers, you can print any.

Example

Input 5 1 2 1 2 2 6 3 4 2 4 1 3 1 2 1 3 1 4 5 8 Output 2 1 3 4 3 2 1 2 3 7 水题，只要输出的两个不同就好。 代码如下：

#include
   
    #define ll long longusing namespace std;ll a1,b1,a2,b2;int main(){	int t;	scanf("%d",&t);	while(t--)	{		cin>>a1>>b1>>a2>>b2;		if(a1==a2) cout<
    
     <<" "<
     
      <
     
    
   

Divisors of Two Integers CodeForces - 1108B

Recently you have received two positive integer numbers x and y. You forgot them, but you remembered a shuffled list containing all divisors of x (including 1 and x) and all divisors of y (including 1 and y). If d is a divisor of both numbers x and y at the same time, there are two occurrences of d in the list.

For example, if x=4 and y=6 then the given list can be any permutation of the list [1,2,4,1,2,3,6]. Some of the possible lists are: [1,1,2,4,6,3,2], [4,6,1,1,2,3,2] or [1,6,3,2,4,1,2].

Your problem is to restore suitable positive integer numbers x and y that would yield the same list of divisors (possibly in different order).

It is guaranteed that the answer exists, i.e. the given list of divisors corresponds to some positive integers x and y.

Input

The first line contains one integer n (2≤n≤128) — the number of divisors of x and y.

The second line of the input contains n integers d1,d2,…,dn (1≤di≤104), where di is either divisor of x or divisor of y. If a number is divisor of both numbers x and y then there are two copies of this number in the list.

Output

Print two positive integer numbers x and y — such numbers that merged list of their divisors is the permutation of the given list of integers. It is guaranteed that the answer exists.

Example

Input 10 10 2 8 1 2 4 1 20 4 5 Output 20 8 给出两个数所有的因子，让你去求这两个数。 我们把这n个数拍一下序，最大的肯定是其中一个数字。这样我们就能求出这个数所有的因子，然后通过剩余的数去求另一个数。 代码如下：

#include
   
    #define ll long longusing namespace std;const int maxx=150;ll a[maxx];int n;int main(){	while(cin>>n)	{		map
    
      mp;		for(int i=0;i
     
      >a[i],mp[a[i]]++;		sort(a,a+n);		ll x=a[n-1];		for(int i=1;i<=sqrt(x);i++)		{			if(x%i==0)			{				mp[i]--;				if(x/i!=i) mp[x/i]--;			} 		}		int pos1,pos2;		for(int i=0;i
      
       =0;i--)		{			if(mp[a[i]])			{				pos2=i;				break;			}		}		cout<
       
        <<" "<
        
         <
        
       
      
     
    
   

Nice Garland CodeForces - 1108C

You have a garland consisting of n lamps. Each lamp is colored red, green or blue. The color of the i-th lamp is si (‘R’, ‘G’ and ‘B’ — colors of lamps in the garland).

You have to recolor some lamps in this garland (recoloring a lamp means changing its initial color to another) in such a way that the obtained garland is nice.

A garland is called nice if any two lamps of the same color have distance divisible by three between them. I.e. if the obtained garland is t, then for each i,j such that ti=tj should be satisfied |i−j| mod 3=0. The value |x| means absolute value of x, the operation x mod y means remainder of x when divided by y.

For example, the following garlands are nice: “RGBRGBRG”, “GB”, “R”, “GRBGRBG”, “BRGBRGB”. The following garlands are not nice: “RR”, “RGBG”.

Among all ways to recolor the initial garland to make it nice you have to choose one with the minimum number of recolored lamps. If there are multiple optimal solutions, print any of them.

Input

The first line of the input contains one integer n (1≤n≤2⋅105) — the number of lamps.

The second line of the input contains the string s consisting of n characters ‘R’, ‘G’ and ‘B’ — colors of lamps in the garland.

Output

In the first line of the output print one integer r — the minimum number of recolors needed to obtain a nice garland from the given one.

In the second line of the output print one string t of length n — a nice garland obtained from the initial one with minimum number of recolors. If there are multiple optimal solutions, print any of them.

Examples

Input 3 BRB Output 1 GRB Input 7 RGBGRBB Output 3 RGBRGBR 给定一个字符串，要求其中任意两个相同的字母的位置差可以整除3. 一开始没啥思路。。但是自己画了画之后，发现字符串其实是可以确定的，因为前三个确定下来之后，剩下的也就确定了，这样我们只要枚举RDB组成的6个字符串来贪心找就行。 代码如下：

#include
   
    #define inf 0x3f3f3f3fusing namespace std;int n;string s;char a[7][4]={"RGB","RBG","BGR","BRG","GBR","GRB"};int solve(int x){	int sum=0;	for(int i=0;i
    
     >n)	{		cin>>s;		int ans=inf;		int pos;		for(int i=0;i<7;i++)		{			int sum=solve(i);			if(sum
    
   

Diverse Garland CodeForces - 1108D

You have a garland consisting of n lamps. Each lamp is colored red, green or blue. The color of the i-th lamp is si (‘R’, ‘G’ and ‘B’ — colors of lamps in the garland).

You have to recolor some lamps in this garland (recoloring a lamp means changing its initial color to another) in such a way that the obtained garland is diverse.

A garland is called diverse if any two adjacent (consecutive) lamps (i. e. such lamps that the distance between their positions is 1) have distinct colors.

In other words, if the obtained garland is t then for each i from 1 to n−1 the condition ti≠ti+1 should be satisfied.

Among all ways to recolor the initial garland to make it diverse you have to choose one with the minimum number of recolored lamps. If there are multiple optimal solutions, print any of them.

Input

The first line of the input contains one integer n (1≤n≤2⋅105) — the number of lamps.

The second line of the input contains the string s consisting of n characters ‘R’, ‘G’ and ‘B’ — colors of lamps in the garland.

Output

In the first line of the output print one integer r — the minimum number of recolors needed to obtain a diverse garland from the given one.

In the second line of the output print one string t of length n — a diverse garland obtained from the initial one with minimum number of recolors. If there are multiple optimal solutions, print any of them.

Examples

Input 9 RBGRRBRGG Output 2 RBGRGBRGR Input 8 BBBGBRRR Output 2 BRBGBRGR Input 13 BBRRRRGGGGGRR Output 6 BGRBRBGBGBGRG 这个题自认为比C 简单，就是需要考虑的地方多点。 其实就是按着字符串的顺序走一遍就行了，如果有两个字符相等，就改变后面那一个。。 代码如下：

#include
   
    #define ll long longusing namespace std;string s;int n;int main(){	while(cin>>n)	{		cin>>s;		int ans=0;		for(int i=1;i
   

Array and Segments (Easy version) CodeForces - 1108E1

The only difference between easy and hard versions is a number of elements in the array.

You are given an array a consisting of n integers. The value of the i-th element of the array is ai.

You are also given a set of m segments. The j-th segment is [lj;rj], where 1≤lj≤rj≤n.

You can choose some subset of the given set of segments and decrease values on each of the chosen segments by one (independently). For example, if the initial array a=[0,0,0,0,0] and the given segments are [1;3] and [2;4] then you can choose both of them and the array will become b=[−1,−2,−2,−1,0].

You have to choose some subset of the given segments (each segment can be chosen at most once) in such a way that if you apply this subset of segments to the array a and obtain the array b then the value maxi=1nbi−mini=1nbi will be maximum possible.

Note that you can choose the empty set.

If there are multiple answers, you can print any.

If you are Python programmer, consider using PyPy instead of Python when you submit your code.

Input

The first line of the input contains two integers n and m (1≤n≤300,0≤m≤300) — the length of the array a and the number of segments, respectively.

The second line of the input contains n integers a1,a2,…,an (−106≤ai≤106), where ai is the value of the i-th element of the array a.

The next m lines are contain two integers each. The j-th of them contains two integers lj and rj (1≤lj≤rj≤n), where lj and rj are the ends of the j-th segment.

Output

In the first line of the output print one integer d — the maximum possible value maxi=1nbi−mini=1nbi if b is the array obtained by applying some subset of the given segments to the array a.

In the second line of the output print one integer q (0≤q≤m) — the number of segments you apply.

In the third line print q distinct integers c1,c2,…,cq in any order (1≤ck≤m) — indices of segments you apply to the array a in such a way that the value maxi=1nbi−mini=1nbi of the obtained array b is maximum possible.

If there are multiple answers, you can print any.

Examples

Input 5 4 2 -2 3 1 2 1 3 4 5 2 5 1 3 Output 6 2 1 4 Input 5 4 2 -2 3 1 4 3 5 3 4 2 4 2 5 Output 7 2 3 2 Input 1 0 1000000 Output 0 0

Note

In the first example the obtained array b will be [0,−4,1,1,2] so the answer is 6.

In the second example the obtained array b will be [2,−3,1,−1,4] so the answer is 7.

In the third example you cannot do anything so the answer is 0.

给定一组序列，和m个区间，每次可以选择不同的区间，让序列对应区间减一，问最大值和最小值的最大差是多少。由于n和m都是三百，我们可以完全暴力去做。。 如果一个序列里有最大值和最小值，那么我们选这一个区间，是无所谓的。因为差值不会改变。如果这个区间里有最小值，而没有最大值，这样的话差值是增大的。通过这一点来看，我们可以把每个点当成最小值去枚举，不断的去更新差值最大化。n和m不大，这样直接暴力就行 代码如下：

#include
   
    #define ll long long#define inf 0x3f3f3f3fusing namespace std;const int maxx=3e2+100;vector
    
      x1,x2;int n,m;int a[maxx],b[maxx];struct node{	int l;	int r;}p[maxx];int main(){	while(scanf("%d%d",&n,&m)!=EOF)	{		for(int i=0;i
     
      >a[i];		for(int i=0;i
      
       >p[i].l>>p[i].r;		int ans=-inf;		x2.clear(); 		for(int pos=0;pos
       
        ans)			{				ans=_max-_min;				x2=x1;			}		}		cout<
        
         <
        
       
      
     
    
   

Array and Segments (Hard version) CodeForces - 1108E2

The only difference between easy and hard versions is a number of elements in the array.

You are given an array a consisting of n integers. The value of the i-th element of the array is ai.

You are also given a set of m segments. The j-th segment is [lj;rj], where 1≤lj≤rj≤n.

You can choose some subset of the given set of segments and decrease values on each of the chosen segments by one (independently). For example, if the initial array a=[0,0,0,0,0] and the given segments are [1;3] and [2;4] then you can choose both of them and the array will become b=[−1,−2,−2,−1,0].

You have to choose some subset of the given segments (each segment can be chosen at most once) in such a way that if you apply this subset of segments to the array a and obtain the array b then the value maxi=1nbi−mini=1nbi will be maximum possible.

Note that you can choose the empty set.

If there are multiple answers, you can print any.

If you are Python programmer, consider using PyPy instead of Python when you submit your code.

Input

The first line of the input contains two integers n and m (1≤n≤105,0≤m≤300) — the length of the array a and the number of segments, respectively.

The second line of the input contains n integers a1,a2,…,an (−106≤ai≤106), where ai is the value of the i-th element of the array a.

The next m lines are contain two integers each. The j-th of them contains two integers lj and rj (1≤lj≤rj≤n), where lj and rj are the ends of the j-th segment.

Output

In the first line of the output print one integer d — the maximum possible value maxi=1nbi−mini=1nbi if b is the array obtained by applying some subset of the given segments to the array a.

In the second line of the output print one integer q (0≤q≤m) — the number of segments you apply.

In the third line print q distinct integers c1,c2,…,cq in any order (1≤ck≤m) — indices of segments you apply to the array a in such a way that the value maxi=1nbi−mini=1nbi of the obtained array b is maximum possible.

If there are multiple answers, you can print any.

Examples

Input 5 4 2 -2 3 1 2 1 3 4 5 2 5 1 3 Output 6 2 4 1 Input 5 4 2 -2 3 1 4 3 5 3 4 2 4 2 5 Output 7 2 3 2 Input 1 0 1000000 Output 0 0

Note

In the first example the obtained array b will be [0,−4,1,1,2] so the answer is 6.

In the second example the obtained array b will be [2,−3,1,−1,4] so the answer is 7.

In the third example you cannot do anything so the answer is 0.

和上一个题一样，但是这个题n是1e5的，嘤嘤嘤这可咋整。 显然暴力是不行了。还是和上面的一样的想法，枚举每一位数，去找最大值和最小值的差值，但是肯定不能像之前一样随时更新。我们可以开一个数组来记录哪些线段用过还是没用过，如果枚举到一个点而且线段符合条件用过的话，就不用管了。如果没有用过，就将这个区间内的数减一。如果不符合条件而且用过，就把这个区间都加一。树状数组或者线段树都可以。（我的代码多组样例不对，不过这个题是单组输入的。。） 代码如下：

#include
   
    #define ll long long#define inf 0x3f3f3f3fusing namespace std;const int maxx=1e5+100;struct node{	int l;	int r;	int lazy;	int _min;	int _max;	int v;}p[maxx<<2];vector
    
      x1,x2;int n,m;int pl[maxx],pr[maxx],a[maxx],vis[maxx];inline void pushup(int cur){	p[cur]._max=max(p[cur<<1]._max,p[cur<<1|1]._max);	p[cur]._min=min(p[cur<<1]._min,p[cur<<1|1]._min);}inline void pushdown(int cur){	if(p[cur].lazy)	{		p[cur<<1].lazy+=p[cur].lazy;		p[cur<<1|1].lazy+=p[cur].lazy;		p[cur<<1]._min+=p[cur].lazy;		p[cur<<1|1]._min+=p[cur].lazy;		p[cur<<1]._max+=p[cur].lazy;		p[cur<<1|1]._max+=p[cur].lazy;		p[cur].lazy=0;	}}inline void build(int l,int r,int cur){	p[cur].l=l;	p[cur].r=r;	p[cur]._max=-inf;	p[cur]._min=inf;	if(l==r) 	{		p[cur]._max=p[cur]._min=a[l];		return ;	}	int mid=(l+r)/2;	build(l,mid,cur<<1);	build(mid+1,r,cur<<1|1);	pushup(cur);}inline void update(int l,int r,int cur,int add){	int L=p[cur].l;	int R=p[cur].r;	if(l<=L&&R<=r)	{		p[cur]._min+=add;		p[cur]._max+=add;		p[cur].lazy+=add;		return ;	}	pushdown(cur);	int mid=(L+R)/2;	if(r<=mid) update(l,r,cur<<1,add);	else if(l>mid) update(l,r,cur<<1|1,add);	else 	{		update(l,mid,cur<<1,add);		update(mid+1,r,cur<<1|1,add);	}	pushup(cur);}int main(){	while(scanf("%d%d",&n,&m)!=EOF)	{		memset(vis,0,sizeof(vis));		for(int i=1;i<=n;i++) scanf("%d",&a[i]);		build(1,n,1);		for(int i=1;i<=m;i++) cin>>pl[i]>>pr[i];		int ans=-inf;		for(int pos=1;pos<=n;pos++)		{			for(int i=1;i<=m;i++)			{				if(pl[i]<=pos&&pos<=pr[i])				{					if(!vis[i])					{						update(pl[i],pr[i],1,-1);						vis[i]=1;					}				}				else if(vis[i]) update(pl[i],pr[i],1,1),vis[i]=0; 			}			if(p[1]._max-p[1]._min>ans)			{				x1.clear();				ans=p[1]._max-p[1]._min;				for(int i=1;i<=m;i++) if(vis[i]) x1.push_back(i);			}		}		cout<
     
      <
     
    
   

努力加油a啊，(^o)/~

转载地址：http://ffxvi.baihongyu.com/