#include<bits/stdc++.h>
#define ll unsigned long long
using namespace std;
inline int read(){
	char ch=getchar();
	int f=1,x=0;
	while(ch<'0'||ch>'9'){
		if(ch=='-')
			f=-f;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return f*x;
}
inline void work(ll k){
	if(k<0){
		putchar('-');
		k=-k;
	}
	if(k>9)
		work(k/10);
	putchar(k%10+'0');
}
/*
如果不考虑第一个1<=k<=(i-1)/2的限制,对于一个固定的k,满足条件的i一定是一个前缀,考虑二分这个前缀
那么加上这个限制之后满足条件的就是一个区间
判定可以用字符串Hash,如果满足h(1,i-2*k)+h(2*k+1,i)=2*h(k+1,l-k)就是满足条件的
这个单Hash不会被卡吧
O(nlogn)不太行
从小到大跑i,双指针维护k
*/
const ll p=1e9+9843,mod=1e9+7;
int n,ans[2000005];
ll h[2000005],pn[2000005],p1[2000005];
long long pn1[2000005],h1[2000005];
ll Hash(int l,int r){
	return h[r]-h[l-1]*pn[r-l+1];
}
long long Hash1(int l,int r){
	return (h1[r]-h1[l-1]*pn1[r-l+1]%mod+mod)%mod;
}
char s[25];
int main(){
	n=read();
	pn[0]=p1[0]=pn1[0]=1;
	for(int i=1;i<=15;i++){
		p1[i]=p1[i-1]*62;
	}
	for(int i=1;i<=n;i++){
		ll val=0;
		scanf("%s",s+1);
		int len=strlen(s+1);
		for(int j=len,now=0;j;j--,now++){
			ll id=s[j];
			if(id>='a'&&id<='z')
				id=id-'a'+1+9;
			else if(id>='A'&&id<='Z')
				id=id-'A'+1+35;
			else
				id=id-'0';
			val=val+p1[now]*id;
		}
		pn[i]=pn[i-1]*p;
		pn1[i]=pn1[i-1]*p%mod;
		h[i]=h[i-1]*p+val;
		h1[i]=(h1[i-1]*p%mod+val)%mod;
	}
	int l=1,r=1;
	work(0);
	work(0);
	for(int i=3;i<=n;i++){
		if(Hash(1,i-2*r)+Hash(2*r+1,i)!=2*Hash(r+1,i-r)||(Hash(1,i-2*r)+Hash(2*r+1,i))%mod!=2*Hash(r+1,i-r)%mod){
			l=r+1;
			r++;
			work(0);
			continue;
		}
		while(Hash(1,i-2*l)+Hash(2*l+1,i)!=2*Hash(l+1,i-l)||(Hash(1,i-2*l)+Hash(2*l+1,i))%mod!=2*Hash(l+1,i-l)%mod){
			l++;
		}
		work(1);
	}
	
	return 0;
}