#include<bits/stdc++.h>
using namespace std;
const int N = 1e7+5;
char s[N];
int nxt[N];
int main(){
	int n,k;
	scanf("%d%d",&n,&k);
	scanf("%s",s+1);
	nxt[1] = 0;
	for(int i=2,j=0; i<=n; i++){
		while(j && s[j+1] != s[i])	j = nxt[j];
		if(s[j+1] == s[i])	j ++;
		nxt[i] = j; 
	}
	for(int i=1; i<=n; i++){
		int len = i - nxt[i];
		int tot = i / len; //出现次数
		printf("%d",(tot / k * len) >= (tot % k * len) + (i % len));
		//S 的长度大于等于 A 的长度 
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 2e6+5;
char s[N];
int z[N],sum[N];
int main(){
	int n,k;
	scanf("%d%d%s",&n,&k,s+1);
	int l=0,r = 0;
	z[0] = 0,z[1] = n;
	for(int i=2; i<=n; i++){
		if(i <= r)	z[i] = min(r-i,z[i - l + 1]);
		while(i + z[i] <= n && s[i + z[i]] == s[z[i] + 1])	z[i]++;
		if(i + z[i] - 1 > r)	r = i + z[i] - 1,l=i;
	}
	for(int len=1; len<=n/k; len++){
		bool flag = true;
		for(int i=1; i<k; i++){  //判断是否符合条件，SSSSS的条件 
			if(z[len * i + 1] < len){
				flag = false;
				break;
			}
		}
		if(flag){
			sum[len * k] ++;   //这一段区间都是合法的，因为他们的剩余的 A 的长度均不超过 S 
			sum[len * k + min(len,z[len * k + 1]) + 1] --;
		}
	}
	int ans = 0;
	for(int i=1; i<=n; i++){
		ans += sum[i];
		printf("%d",ans > 0);
	}
	return 0;
}

#include<bits/stdc++.h>
#define PII pair<int,int>
using namespace std;
const int N = 2e6+5;
char s[N],t[N];
int top = 0,nxt[N];
PII st[N];
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	scanf("%s%s",s+1,t+1);
	int n = strlen(s + 1);
	int m = strlen(t + 1);
	nxt[1] = 0;
	for(int i=2,j=0; i<=m; i++){
		while(j && t[j + 1] != t[i])	j = nxt[j];
		if(t[j + 1] == t[i])	j++;
		nxt[i] = j;
	}
	for(int i=1,j=0; i<=n; i++){
		while((j && t[j + 1] != s[i]) || j == m)	 j = nxt[j];
		if(t[j + 1] == s[i])	j++;
		st[++top] = {i,j};
		if(j == m){
			top = top - m;
			j = st[top].second;
		}
	}
	for(int i=1; i<=top; i++)	printf("%c",s[st[i].first]);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 2e6+5;
char s[N],t[N];
int nxt[N];
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int p;
	scanf("%d",&p);
	scanf("%s",s+1);
	int n = strlen(s+1);
	for(int q=1; q<p; q++){
		scanf("%s",t+1);
		int m = strlen(t+1);
		nxt[1] = 0;
		for(int i=2,j=0; i<=m; i++){
			while(j && t[j+1] != t[i])	j = nxt[j];
			if(t[j + 1] == t[i])	j++;
			nxt[i] = j;
		}
		int j = 0;
		for(int i = n - min(n,m) + 1; i<=n; i++){  //s 和 t 取匹配 
			while((j && t[j+1] != s[i]) || j == m)	j = nxt[j];
			if(t[j + 1] == s[i])	j++;
		}
		for(int i = j + 1; i<=m; i++)	s[++n] = t[i];
	}
	for(int i=1; i<=n; i++)	printf("%c",s[i]);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 2e6+5;
int cnt,tmp[27][N],z[N],tax[N],pre[N],suf[N],tot[N],rt[N];
char s[N];
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		scanf("%s",s+1);
		//预处理出来每一个后缀出现次数为奇数的字符个数
		int n = strlen(s+1);
		z[0] = 0,z[1] = n;
		int l = 0,r = 0;
		for(int i=2; i<=n; i++){  //求 z 函数，方便判断 SSSS 是否合法 
			if(i <= r)	z[i] = min(r - i,z[i - l + 1]);
			while(i + z[i] <= n && s[i + z[i]] == s[z[i] + 1])	z[i]++;
			if(i + z[i] - 1 > r)	r = i + z[i] - 1,l = i;
		}
		for(int i=n; i>=1; i--){
			suf[i] = suf[i + 1];
			tot[s[i] - 'a'] ^= 1;
			if(tot[s[i] - 'a'] & 1)	suf[i]++;
			else	suf[i]--; 
		}
		for(int i=0; i<=26; i++)	tot[i] = 0;
		for(int i=1; i<=n; i++){
			for(int j=0; j<=26; j++)	tmp[j][i] = tmp[j][i-1];
			pre[i] = pre[i-1];
			tot[s[i] - 'a'] ^= 1;
			if(tot[s[i] - 'a'] & 1)	pre[i]++;
				else	pre[i]--;	
			tmp[pre[i]][i]++;
		}
		for(int j=1; j<=26; j++)
			for(int i=1; i<=n; i++)
				tmp[j][i] += tmp[j-1][i];
		long long ans = 0;
		for(int i=2; i<n; i++){  //因为 AB 非空 
			for(int j=0; (j + 1) * i + 1 <= n; j++){
				if(z[j * i + 1] < i)
					break;
				//这个时候 C 的起始点就是 (j + 1) * i
				ans += tmp[suf[(j + 1) * i + 1]][i-1];
			}
		}
		printf("%lld\n",ans);
		for(int i=0; i<=n + 2; i++)	suf[i] = z[i] = 0;
		for(int i=0; i<=26; i++)	tot[i] = 0;
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
char s[N];
int tmp[N],nxt[N],f[N];
int main(){
	scanf("%s",s+1);
	int n = strlen(s+1);
	nxt[1] = 0;
	for(int i=2,j=0; i<=n; i++){
		while(j && s[j + 1] != s[i])	j = nxt[j];
		if(s[j + 1] == s[i])	j++;
		nxt[i] = j;
	}
	f[1] = 1,tmp[f[1]] = 1;
	for(int i=2; i<=n; i++){
		f[i] = i;
		if(tmp[f[nxt[i]]] >= i - nxt[i])	f[i] = f[nxt[i]];  
	//f[nxt[i]] 可以覆盖 [i - nxt[i] + 1,i]，而 f[j] 可以覆盖 [1,j]，所以当 j >= i - nxt[i] 时就可以完全覆盖了 
		tmp[f[i]] = i;   //tmp[i] 其实存的是最后一个 f[x] = i 的 x 的位置，显然 x 越大越好所以可以覆盖之前的位置 
	}
	printf("%d\n",f[n]);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
const int INF = 1e9+5;
vector<vector<int> > dp;
char s[N],t[N];
int nxt[N];
int main(){
	scanf("%s",s+1);
	scanf("%s",t+1);
	int n = strlen(s + 1);
	int m = strlen(t + 1);
	nxt[1] = 0;
	for(int i=0; i<=n+2; i++){
		vector<int> tmp;
		for(int j=0; j<=m+2; j++){
			tmp.push_back(-INF);
		}
		dp.push_back(tmp);
	}
	for(int i = 2,j = 0; i<=m; i++){
		while(j && t[j + 1] != t[i])	j = nxt[j];
		if(t[j+1] == t[i])	j++;
		nxt[i] = j;
	}
	dp[0][0] = 0;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			if(s[i] == t[j] || s[i] == '?')
				dp[i][j] = max(dp[i][j],dp[i-1][j-1]);
			if(j == m){
				dp[i][j]++;
				for(int p = nxt[m];p;p=nxt[p])
					dp[i][p] = max(dp[i][p],dp[i][j]);
			}
		}
		for(int j=0; j<=m; j++)
			dp[i][0] = max(dp[i][0],max(dp[i-1][j],dp[i][j]));
	}
	int ans = 0;
	for(int i=0; i<=m; i++)	ans = max(ans,dp[n][i]);
	printf("%d\n",ans);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 22;
const int M = 22;
struct matrix{
	int a[M][M];
	int n,m;
	matrix(){   //千万不要忘记初始化为 0 
		memset(a,0,sizeof(a));
		n = m = 0;
	}
}g,f;
char s[N];
int nxt[N],n,m,MOD;
matrix operator * (matrix a,matrix b){
	matrix c;
	c.n = a.n;c.m = b.m;
	memset(c.a,0,sizeof(c.a));
	for(int i=0; i<=a.n; i++)
		for(int j=0; j<=a.n; j++)
			for(int k=0; k<=a.n; k++)
				c.a[i][j] = (c.a[i][j] + a.a[i][k] * b.a[k][j])%MOD;
	return c;
}
matrix power(matrix a,int b){
	matrix res;
	res.n = res.m = a.n;
	memset(res.a,0,sizeof(res.a));
	for(int i=0; i<=res.n; i++)	res.a[i][i] = 1;
	while(b > 0){
		if(b & 1)	res = res * a;
		a = a * a;
		b >>= 1;
	}
	return res;
}
int main(){
	scanf("%d%d%d",&n,&m,&MOD);
	scanf("%s",s+1);
	//get_kmp && g
	nxt[1] = 0;
	for(int i=2,j=0; i<=m; i++){
		while(j && s[j+1] != s[i])	j = nxt[j];
		if(s[j+1] == s[i])	j++;
		nxt[i] = j;
	}
	for(int i=0; i<m; i++){   //这里保证了任意时刻都不会匹配完，因为我们只会匹配到 m-1 
		for(int j=0; j<=9; j++){
			int now = i;
			while(s[now + 1] != j + '0' && now)	now = nxt[now];
			if(s[now + 1] == j + '0')	now++;
			if(now < m)	g.a[i][now]++;
		}
	}
	g.n = g.m = m-1;
	//---------------------------------------------------
	g = power(g,n);     //因为 f 就是一个 1,0,0,0, 所以答案显然是第 0 行的和 
	int ans = 0;
	for(int i=0; i<m; i++)	ans = (ans + g.a[0][i])%MOD;
	printf("%d\n",ans);
	return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 4e4+5;
const int L = 350;
char s[N][L];
int n,len,ALP,h[N],hashl[N][L],hashr[N][L];
void init(int x){
	for(int i=1; i<=len; i++)	hashl[x][i] = hashl[x][i-1] * 139 + s[x][i];
	for(int i=len; i>=1; i--)	hashr[x][i] = hashr[x][i+1] * 137 + s[x][i];
}
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	scanf("%lld%lld%lld",&n,&len,&ALP);
	for(int i=1; i<=n; i++){
		scanf("%s",s[i]+1);
		init(i);
	}
	int ans = 0;
	for(int i=1; i<=len; i++){
		for(int j=1; j<=n; j++)	h[j] = hashl[j][i-1] * 709 + hashr[j][i+1] * 853;  //只要变化的规则保持不变，hash 判断相同就不会出现问题 
		sort(h+1,h+n+1);
		int tmp = 1;
		for(int j=1; j<n; j++){
			if(h[j] == h[j + 1])	ans += tmp,tmp++;
			else	tmp = 1;
		}
	}
	printf("%lld\n",ans);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 2e6+5;
int h[N],pw[N];
int mn[N],b[N],tot,prime[N];
bool flag[N];
char s[N];
int get_hash(int l,int r){
	return h[r] - h[l - 1] * pw[r - l + 1];
}
void pre_work(int n){
	h[0] = pw[0] = 1;
	for(int i=1; i<=n; i++)	h[i] = h[i-1] * 137 + s[i];
	for(int i=1; i<=n; i++)	pw[i] = pw[i-1] * 137;
	for(int i=2; i<=n; i++){
		if(!flag[i]){
			prime[++tot] = i;
			mn[i] = i;
		}
		for(int j=1; j <= tot && i * prime[j] <= n; j++){
			flag[i * prime[j]] = true;
			mn[i * prime[j]] = prime[j];
			if(i % prime[j] == 0)	break;
		}
	}
}
signed main(){
	int n;
	scanf("%d%s",&n,s+1);
	pre_work(n);
	int q;
	scanf("%d",&q);
	while(q--){
		int l,r;
		scanf("%d%d",&l,&r);
		int p = r - l + 1;
		int cnt = 0;
		while(p != 1){
			b[++cnt] = mn[p];
			p /= mn[p];
		}  
		p = r - l + 1;
		for(int i=1; i<=cnt; i++){
			int len = p / b[i];
			if(get_hash(l,r-len) == get_hash(l+len,r)){
				p /= b[i];
			}
		}
		printf("%d\n",p);
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 2e6+5;
int tot,rt,ch[N][2],val[N],sz[N],key[N];
unsigned int pw[N],h[N];
int x,y,z;
char s[N];
void pushup(int now){
	h[now] = h[ch[now][0]] * pw[1 + sz[ch[now][1]]] + val[now] * pw[sz[ch[now][1]]] + h[ch[now][1]];
	sz[now] = sz[ch[now][0]] + sz[ch[now][1]] + 1;
}
int merge(int x,int y){
	if(!x || !y)	return x + y;
	if(key[x] > key[y]){
		ch[x][1] = merge(ch[x][1],y);
		pushup(x);
		return x;
	}
	else{
		ch[y][0] = merge(x,ch[y][0]);
		pushup(y);
		return y;
	}
}
void split(int now,int k,int &x,int &y){
	if(!now){
		x = y = 0;
		return;
	}
	if(sz[ch[now][0]] < k){
		x = now;
		split(ch[now][1],k - sz[ch[now][0]] - 1,ch[x][1],y);
		pushup(x);
	}
	else{
		y = now;
		split(ch[now][0],k,x,ch[y][0]);
		pushup(y);
	}
}
int newnode(int v){
	++tot;
	val[tot] = v;key[tot] = rand();sz[tot] = 1;h[tot] = v;
	return tot;
}
void insert(int k,int v){
	split(rt,k,x,y);
	rt = merge(merge(x,newnode(v)),y);
}
void delet(int k){
	split(rt,k,x,y);
	split(x,k-1,x,z);
	rt = merge(x,y);
}
unsigned int get_hash(int l,int r){
	split(rt,r,x,y);
	split(x,l-1,x,z);
	unsigned int ans = h[z];
	rt = merge(merge(x,z),y);
	return ans;
}
signed main(){
	scanf("%s",s+1);
	int n = strlen(s+1);
	pw[0] = 1;
	for(int i=1; i<=100005; i++)	pw[i] = pw[i-1] * 131;
	for(int i=1; i<=n; i++)	insert(i-1,s[i] - 'a' + 1);
	int q;
	scanf("%d",&q);
	while(q--){
		char opt[5];
		scanf("%s",opt + 1);
		if(opt[1] == 'Q'){
			int l,r;
			scanf("%d%d",&l,&r);
			int ans = 0;
			int tl = 1,tr = min(sz[rt]-r+1,sz[rt]-l+1);
			while(tl <= tr){
				int mid = (tl + tr) >> 1;
				if(get_hash(l,l + mid - 1) == get_hash(r,r + mid - 1)){
					ans = max(ans,mid);
					tl = mid + 1;
				}
				else	tr = mid - 1;
			}
			printf("%d\n",ans);
		}
		else if(opt[1] == 'R'){
			int pos;
			char d;
			cin>>pos>>d;
			delet(pos);
			insert(pos-1,d - 'a' + 1);
		}
		else if(opt[1] == 'I'){
			int pos;
			char d;
			cin>>pos>>d;
			insert(pos,d - 'a' + 1);
		}
	}
	return 0;
}

#include<cstdio>
#include<cstring>
using namespace std;
const int N = 2e4+5;
int rt = 1,tot = 1;
char t[N][15];
int sz[N * 15],ch[N * 15][11];
void insert(char *s){
	int n = strlen(s+1);
	int now = rt;
	for(int i=1; i<=n; i++){
		sz[now]++;
		if(!ch[now][s[i] - '0'])	ch[now][s[i] - '0'] = ++tot;
		now = ch[now][s[i] - '0'];
	}
	sz[now]++;
}
int check(char *s){
	int n = strlen(s+1);
	int now = rt;
	for(int i=1; i<=n; i++)	now = ch[now][s[i] - '0'];
	return sz[now] >= 2;
}
int main(){
	int ti;
	scanf("%d",&ti);
	while(ti--){
		int n;
		scanf("%d",&n);
		for(int i=1; i<=n; i++)	scanf("%s",t[i] + 1);
		for(int i=1; i<=n; i++)	insert(t[i]);
		bool flag = false;
		for(int i=1; i<=n; i++){
			if(check(t[i]))
				flag = true;
		}
		if(flag)	printf("NO\n");
		else	printf("YES\n");
		for(int i=1; i<=tot; i++){
			sz[i] = 0;
			for(int j=0; j<=10; j++)
				ch[i][j] = 0;
		}
		rt = 1;tot=1;
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int MOD = 20071027;
const int N = 5e6+5;
const int ALP = 26;
int rt=1,tot=1;
char s[N],t[N];
bool flag[N];
int f[N],ch[N][ALP];
void insert(char *s){
	int n = strlen(s+1);
	int now = rt;
	for(int i=1; i<=n; i++){
		if(!ch[now][s[i] - 'a'])	ch[now][s[i] - 'a']	= ++tot;
		now = ch[now][s[i] - 'a'];
	}
	flag[now] = true;
}
bool check(string s){
	int n = s.size();
	int now = rt;
	for(int i=0; i<n; i++){
		now = ch[now][s[i] - 'a'];
		if(!now)	return;
	}
	return flag[now];
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int res = 0;
	while(~scanf("%s",s+1)){
		++res;
		printf("Case %d: ",res);
		int n;
		scanf("%d",&n);
		for(int i=1; i<=n; i++){
			scanf("%s",t + 1);
			insert(t);
		}
		int m = strlen(s+1);
		f[m+1] = 1;
		for(int i=m; i>=1; i--){
			int now = rt;
			for(int j=i; j<=m; j++){
				if(!ch[now][s[j] - 'a'])	break;
				now = ch[now][s[j] - 'a'];
				if(flag[now])	f[i] = (f[i] + f[j+1]) % MOD;
			}
		}
		printf("%d\n",f[1]);
		for(int i=1; i<=m+1; i++) f[i] = 0;
		for(int i=1; i<=tot; i++){
			flag[i] = false;
			for(int j=0; j<ALP; j++){
				ch[i][j] = 0;
			}
		}
		rt = 1,tot = 1;
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 5e6+5;
const int ALP = 64;
int sz[N],ch[N][ALP],flag[N],rt = 1,tot=1;
char t[4005][1005];
int get(char c){
	if(c >= 'a' && c <= 'z')	return c - 'a';
	if(c >= 'A' && c <= 'Z')	return c - 'A' + 26;
	return c - '0' + 52;
}
void insert(char *s){
	int n = strlen(s+1);
	int now = rt;
	for(int i=1; i<=n; i++){
		sz[now]++;
		if(!ch[now][get(s[i])])	ch[now][get(s[i])] = ++tot;
		now = ch[now][get(s[i])];
	}
	sz[now]++;flag[now]++;
}
long long calc(char *s){
	long long ans = 0;
	int n = strlen(s+1);
	int now = rt;
	for(int i = 1; i<=n; i++){
		ans += sz[now];
		if(!now)	break;
		now = ch[now][get(s[i])];
		ans += sz[now];
	}
	ans += flag[now] + sz[now];
	return ans;
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int n;
	int res = 1;
	while(~scanf("%d",&n)){
		if(n == 0)	break;
		printf("Case %d: ",res);
		res++;
		for(int i=1; i<=n; i++)	scanf("%s",t[i] + 1);
		long long ans = 0;
		for(int i=n; i>=1; i--){
			ans += calc(t[i]);
			insert(t[i]);
		}
		printf("%lld\n",ans);
		for(int i=1; i<=tot; i++){
			sz[i] = flag[i] = 0;
			for(int j=0; j<ALP; j++){
				ch[i][j] = 0;
			}
		}
		rt = 1,tot = 1;
	}
	return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e6+5;
const int ALP = 51971;
const int MOD = 2005091020050911;
int b[N];
char s[N],t[N];
signed main(){
	int n;
	scanf("%lld",&n);
	scanf("%s%s",s+1,t+1);
	int tot = 0;
	for(int i=1; i<=n; i++){
		int now = 1;int H = 0;
		for(int j=i; j<=n; j++){
			while(now <= n && s[now] != t[j])	now++;
			if(now > n)	break;
			H = (H * ALP + t[j] - 'a' + 1)%MOD;
			b[++tot] = H;
			now++;
		}
	}
	sort(b+1,b+tot+1);
	tot = unique(b+1,b+tot+1) - b - 1;
	printf("%lld\n",tot);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 5e6+5;
const int ALP = 26;
struct edge{
	int nxt,to;
	edge(){}
	edge(int _nxt,int _to){
		nxt = _nxt,to = _to;
	}
}e[N];
int rt = 1,tot = 1,cnt,head[N],ch[N][ALP],fail[N],val[N],pos[N];
char s[N];
void add_edge(int from,int to){
	e[++cnt] = edge(head[from],to);
	head[from] = cnt;
}
void insert(char *s,int p){
	int n = strlen(s + 1);
	int now = rt;
	for(int i=1; i<=n; i++){
		val[now]++;
		if(!ch[now][s[i] - 'a'])	ch[now][s[i] - 'a'] = ++tot;
		now = ch[now][s[i] - 'a'];
	}
	val[now]++;
	pos[p] = now;
}
void build(){
	queue<int> q;
	for(int i=0; i<ALP; i++){
		if(ch[rt][i]){
			q.push(ch[rt][i]);
			fail[ch[rt][i]] = rt;
		}
		else	ch[rt][i] = rt;
	}
	while(!q.empty()){
		int now = q.front();q.pop();
		for(int i=0; i<ALP; i++){
			if(ch[now][i]){
				fail[ch[now][i]] = ch[fail[now]][i];
				q.push(ch[now][i]);
			}
			else	ch[now][i] = ch[fail[now]][i];
		}
	}
}
void dfs(int now){
	for(int i = head[now]; i;i = e[i].nxt){
		int to = e[i].to;
		dfs(to);
		val[now] += val[to];
	}
}
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1; i<=n; i++){
		scanf("%s",s+1);
		insert(s,i);
	}
	build();
	for(int i=2; i<=tot; i++)	add_edge(fail[i],i);
	dfs(1);
	for(int i=1; i<=n; i++){
		printf("%d\n",val[pos[i]]);
	}
	return 0;
}

#include<bits/stdc++.h>
#define PII pair<int,int>
using namespace std;
const int N = 2e6+5;
const int ALP = 26;
PII st[N];
int rt=1,tot=1,top,sz[N],ch[N][ALP],fail[N];
bool flag[N];
char s[N],t[N];
void insert(char *s){
	int now = rt;
	int n = strlen(s+1);
	for(int i=1; i<=n; i++){
		if(!ch[now][s[i] - 'a'])	ch[now][s[i] - 'a'] = ++tot;
		now = ch[now][s[i] - 'a'];
	}
	flag[now] = true;sz[now] = n;
}
void build(){
	queue<int> q;
	for(int i=0; i<ALP; i++){
		if(ch[rt][i]){
			q.push(ch[rt][i]);
			fail[ch[rt][i]] = rt;
		}
		else	ch[rt][i] = rt;
	}
	while(!q.empty()){
		int now = q.front();q.pop();
		for(int i=0; i<ALP; i++){
			if(ch[now][i]){
				fail[ch[now][i]] = ch[fail[now]][i];
				q.push(ch[now][i]);
			}
			else	ch[now][i] = ch[fail[now]][i];
		}
	}
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	scanf("%s",s+1);
	int n;
	scanf("%d",&n);
	for(int i=1; i<=n; i++){
		scanf("%s",t+1);
		insert(t);
	}
	build();
	int now = rt;
	n = strlen(s+1);
	//记录第几个位置，匹配到了哪一个节点 
	for(int i=1; i<=n; i++){
		while(now && !ch[now][s[i] - 'a'])	now = fail[now];
		if(ch[now][s[i] - 'a'])		now = ch[now][s[i] - 'a'];
		st[++top] = {i,now};
		if(flag[now]){
			top -= sz[now];
			now = st[top].second;
			if(!top)	now = rt;
		}
	}
	for(int i=1; i<=top; i++){
		printf("%c",s[st[i].first]);
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 2e3+5;
const int ALP = 3;
const int INF = 1e9+5;
struct edge{
	int nxt,to;
	edge(){}
	edge(int _nxt,int _to){
		nxt = _nxt,to = _to;
	}
}e[2 * N];
int cnt,tot=1,rt=1,dp[N][N],ch[N][ALP],val[N],head[N],fail[N];
char s[N];
void insert(char *s){
	int n = strlen(s + 1);
	int now = rt;
	for(int i=1; i<=n; i++){
		if(!ch[now][s[i] - 'A'])	ch[now][s[i] - 'A'] = ++tot;
		now = ch[now][s[i] - 'A'];
	}
	val[now] ++;
}
void build(){
	queue<int> q;
	for(int i=0; i<ALP; i++){
		if(ch[rt][i]){
			fail[ch[rt][i]] = rt;
			q.push(ch[rt][i]);
		}
		else	ch[rt][i] = rt;
	}
	while(!q.empty()){
		int now = q.front();q.pop();
		for(int i=0; i<ALP; i++){
			if(ch[now][i]){
				fail[ch[now][i]] = ch[fail[now]][i];
				q.push(ch[now][i]);
			}
			else 	ch[now][i] = ch[fail[now]][i];
		}
	}
}
void add_edge(int from,int to){
	e[++cnt] = edge(head[from],to);
	head[from] = cnt;
}
void dfs(int now){
	for(int i=head[now]; i;i = e[i].nxt){
		int to = e[i].to;
		val[to] += val[now];
		dfs(to);
	}
}
int main(){
	memset(dp,-0x3f,sizeof(dp));
	int n,k;
	scanf("%d%d",&n,&k);
	for(int i=1; i<=n; i++){
		scanf("%s",s+1);
		insert(s);
	}
	build();
	for(int i=2; i<=tot; i++)	add_edge(fail[i],i);
	dfs(1);
	//设 dp[i][j] 表示填好了前 i 个字符，当前在状态 j 的最大得分数 
	dp[0][1] = 0;
	for(int i=0; i<=k; i++){
		for(int j=1; j<=tot; j++){
			//直接枚举当前填什么
			for(int k='A'; k<='C'; k++){
				int now = j;
				while(now && !ch[now][k - 'A'])	now = fail[now];
				if(ch[now][k - 'A'])	now = ch[now][k - 'A'];
				if(!now)	now = rt;
				dp[i+1][now] = max(dp[i+1][now],dp[i][j] + val[now]);
			} 
		}
	}
	int ans = -INF;
	for(int i=2; i<=tot; i++)	ans = max(ans,dp[k][i]);
	printf("%d\n",ans);
	return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6+5;
const int ALP = 26;
const int MOD = 1e4+7;
struct edge{
	int nxt,to;
	edge(){}
	edge(int _nxt,int _to){
		nxt = _nxt,to = _to;
	}
}e[N];
bool flag[N];
int cnt,tot=1,rt=1,ch[N][ALP],fail[N],head[N],dp[105][10005];
char s[N];
int power(int a,int b){
	int res = 1;
	while(b){
		if(b & 1)	res = (res * a)%MOD;
		a = (a * a)%MOD;
		b >>= 1;
	}
	return res;
}
void add_edge(int from,int to){
	e[++cnt] = edge(head[from],to);
	head[from] = cnt;
}
void insert(char *s){
	int n = strlen(s + 1);
	int now = rt;
	for(int i=1; i<=n; i++){
		if(!ch[now][s[i] - 'A'])	ch[now][s[i] - 'A'] = ++tot;
		now = ch[now][s[i] - 'A'];
	}
	flag[now] = true;
}
void build(){
	queue<int> q;
	for(int i=0; i<ALP; i++){
		if(ch[rt][i]){
			fail[ch[rt][i]] = rt;
			q.push(ch[rt][i]);
		}
		else	ch[rt][i] = rt;
	}
	while(!q.empty()){
		int now = q.front();q.pop();
		for(int i=0; i<ALP; i++){
			if(ch[now][i]){
				fail[ch[now][i]] = ch[fail[now]][i];
				q.push(ch[now][i]);
			}
			else	ch[now][i] = ch[fail[now]][i];
		}
	}
}
void dfs(int now){
	for(int i = head[now]; i;i = e[i].nxt){
		int to = e[i].to;
		flag[to] |= flag[now];
		dfs(to);
	}
}
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int n,m;
	scanf("%lld%lld",&n,&m);
	for(int i=1; i<=n; i++){
		scanf("%s",s + 1);
		insert(s);
	}
	build();
	for(int i=2; i<=tot; i++)	add_edge(fail[i],i);
	dfs(1);
	dp[0][1] = 1;
	for(int i=0; i<=m; i++){  //前 i 个字符确定当前匹配到了 j 且不存在可读文本的方案数 
		for(int j=1; j<=tot; j++){
			if(flag[j])	continue;
			for(int k=0; k<ALP; k++){
				int now = j;
				while(now && !ch[now][k])	now = fail[now];
				if(ch[now][k])	now = ch[now][k];
				if(!flag[now]){
					dp[i+1][now] = (dp[i+1][now] + dp[i][j])%MOD;
				}
			}
		}
	}
	int ans = power(26,m);
	for(int i=1; i<=tot; i++)	ans = ((ans - dp[m][i])%MOD+MOD)%MOD;
	printf("%lld\n",ans);
	return 0;
}

#include<bits/stdc++.h>
#define int long long
const int N = 2e6+5;
const int ALP = 10;
const int MOD = 1e9+7;
using namespace std;
struct edge{
	int nxt,to;
	edge(){}
	edge(int _nxt,int _to){
		nxt = _nxt,to = _to;
	}
}e[N];
int rt=1,tot=1,cnt,n,f[1500][2][2][2000],head[N],ch[N][ALP],fail[N];
char s[N],num[N],flag[N],vis[1500][2][2][2000];
void add_edge(int from,int to){
	e[++cnt] = edge(head[from],to);
	head[from] = cnt;
}
void insert(char *s){
	int n = strlen(s+1);
	int now = rt;
	for(int i=1; i<=n; i++){
		if(!ch[now][s[i] - '0'])	ch[now][s[i] - '0'] = ++tot;
		now = ch[now][s[i] - '0'];
	}
	flag[now] = true;
}
void build(){
	queue<int> q;
	for(int i=0; i<ALP; i++){
		if(ch[rt][i]){
			fail[ch[rt][i]] = rt;
			q.push(ch[rt][i]);
		}
		else	ch[rt][i] = rt;
	}
	while(!q.empty()){
		int now = q.front();q.pop();
		for(int i = 0; i<ALP; i++){
			if(ch[now][i]){
				fail[ch[now][i]] = ch[fail[now]][i];
				q.push(ch[now][i]);
			}
			else	ch[now][i] = ch[fail[now]][i];
		}
	}
}
void dfs(int now){
	for(int i=head[now]; i;i = e[i].nxt){
		int to = e[i].to;
		flag[to] |= flag[now];
		dfs(to);
	}
}
int dfs(int dig,bool limit,bool pre_0,int now){
	//当前要分配第 dig 位，之前有没有抵到上届，是否有前导零，在AC自动机上跑到了第now个节点
	if(flag[now])	return 0;
	if(vis[dig][limit][pre_0][now])	return f[dig][limit][pre_0][now];
	if(dig == n + 1){
		if(pre_0){
			return 0;
		}
		return !flag[now];
	}
	int p = num[dig] - '0';
	int lmt = limit ? p : 9;
	int ans = 0;
	for(int i=0; i<=lmt; i++){
		if(i == 0 && pre_0){
			ans = (ans + dfs(dig+1,i == p && limit,pre_0,now))%MOD;
		}
		else{
			int g = now;
			while(now && !ch[now][i])	now = fail[now];
			if(ch[now][i])	now = ch[now][i];
			if(!now)	now = rt;
			ans = (ans + dfs(dig+1,i == p && limit,false,now))%MOD;
			now = g;
		}
	}
	vis[dig][limit][pre_0][now] = true;
	return f[dig][limit][pre_0][now] = ans;
}
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	scanf("%s",num + 1);
	n = strlen(num + 1);
	int m;
	scanf("%lld",&m);
	for(int i=1; i<=m; i++){
		scanf("%s",s+1);
		insert(s);
	}
	build();
	for(int i=2; i<=tot; i++)	add_edge(fail[i],i);
	dfs(1);
	printf("%lld",dfs(1,1,1,1));
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 2e6+5;
const int ALP = 26;
struct edge{
	int nxt,to;
	edge(){}
	edge(int _nxt,int _to){
		nxt = _nxt,to = _to;
	}
}e[N];
int cnt,tot = 1,tmp,rt = 1,pos[N],sum[N],ans[N],dfn[N],sz[N],back[N],head[N],ch[N][ALP],fail[N];
char s[N],t[N];
vector<pair<int,int> > g[N];
void add_edge(int from,int to){
	e[++cnt] = edge(head[from],to);
	head[from] = cnt;
}
void build(){
	queue<int> q;
	for(int i=0; i<ALP; i++){
		if(ch[rt][i]){
			fail[ch[rt][i]] = rt;
			q.push(ch[rt][i]);
		}
		else	ch[rt][i] = rt;
	}
	while(!q.empty()){
		int now = q.front();q.pop();
		for(int i = 0; i<ALP; i++){
			if(ch[now][i]){
				fail[ch[now][i]] = ch[fail[now]][i];
				q.push(ch[now][i]);
			}
			else	ch[now][i] = ch[fail[now]][i];
		}
	}
}
void dfs(int now,int fath){
	dfn[now] = ++tmp;
	sz[now] = 1;
	for(int i = head[now]; i;i = e[i].nxt){
		int to = e[i].to;
		if(to == fath)	continue;
		dfs(to,now);
		sz[now] += sz[to];
	}
}
void modify(int x,int val){
	if(!x)	return;
	for(;x<=tmp;x+=x&(-x))	sum[x] += val;
}
int query(int x){
	if(x <= 0)	return 0;
	int ans = 0;
	for(;x;x-=x&(-x))	ans += sum[x];
	return ans;
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	scanf("%s",t+1);
	int h = strlen(t+1);
	int len = 0;
	int res = 0;
	int now = rt;
	for(int i=1; i<=h; i++){
		if(t[i] == 'P')	pos[++res] = now;
		else if(t[i] == 'B')	now = back[now];
		else{
			if(!ch[now][t[i] - 'a'])	ch[now][t[i] - 'a'] = ++tot;
			back[ch[now][t[i] - 'a']] = now;
			now = ch[now][t[i] - 'a'];
		}
	}
	build();
	for(int i=2; i<=tot; i++)	add_edge(fail[i],i);
	dfs(1,0);
	int q;
	scanf("%d",&q);
	for(int i=1; i<=q; i++){
		int x,y;
		scanf("%d%d",&x,&y);
		g[y].push_back({x,i});
	}
	now = rt;
	res = 0;
	for(int i=1; i<=h; i++){
		if(t[i] == 'P'){
			res++;
			for(auto p : g[res]){
				int x = pos[p.first];
				ans[p.second] = query(dfn[x] + sz[x] - 1) - query(dfn[x] - 1);
			}
		}
		else if(t[i] == 'B'){
			modify(dfn[now],-1);
			now = back[now];
		}
		else{
			now = ch[now][t[i] - 'a'];
			modify(dfn[now],1);
		}
	}
	for(int i=1; i<=q; i++){
		printf("%d\n",ans[i]);
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
const int ALP = 26;
struct edge{
	int nxt,to;
	edge(){}
	edge(int _nxt,int _to){
		nxt = _nxt,to = _to;
	}
}e[N];
char s[N],t[N];
int cnt,tot = 1,rt=1,res,pos[N],head[N],ch[N][ALP],fail[N],sum[N],dep[N],fa[N],sz[N],dfn[N];
bool flag[N];
void insert(char *s,int p){
	int n = strlen(s+1);
	int now = rt;
	for(int i=1; i<=n; i++){
		if(!ch[now][s[i] - 'a'])	ch[now][s[i] - 'a'] = ++tot;
		now = ch[now][s[i] - 'a'];
	}
	pos[p] = now;
}
void build(){
	queue<int> q;
	for(int i=0; i<ALP; i++){
		if(ch[rt][i]){
			fail[ch[rt][i]] = rt;
			q.push(ch[rt][i]);
		}
		else	ch[rt][i] = rt;
	}
	while(!q.empty()){
		int now = q.front();q.pop();
		for(int i = 0;i < ALP; i++){
			if(ch[now][i]){
				fail[ch[now][i]] = ch[fail[now]][i];
				q.push(ch[now][i]);
			}
			else	ch[now][i] = ch[fail[now]][i];
		}
	}
}
void add_edge(int from,int to){
	e[++cnt] = edge(head[from],to);
	head[from] = cnt;
}
void dfs1(int now,int fath){
	dep[now] = dep[fath] + 1;
	fa[now] = fath;
	sz[now] = 1;dfn[now] = ++res;
	for(int i = head[now]; i;i = e[i].nxt){
		int to = e[i].to;
		if(to == fath)	continue;
		dfs1(to,now);
		sz[now] += sz[to];
	}
}
void modify(int x,int val){
	for(;x<=res;x+=x&(-x))	
		sum[x] += val;
}
int query(int x){
	if(!x)	return 0;
	int ans = 0;
	for(;x;x-=x&(-x))	ans += sum[x];
	return ans;
}
void change(int l,int r,int val){
	modify(l,val);
	modify(r+1,-val);
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int n,k;
	scanf("%d%d",&n,&k);
	for(int i=1; i<=k; i++){
		scanf("%s",s + 1);
		insert(s,i);
	}
	build();
	for(int i=2; i<=tot; i++)	add_edge(fail[i],i);
	dfs1(1,0);
	for(int i=1; i<=k; i++)	
		change(dfn[pos[i]],dfn[pos[i]] + sz[pos[i]] - 1,1),flag[i] = true;
	for(int i=1; i<=n; i++){
		char opt;
		cin>>opt;
		if(opt == '+'){
			int h;scanf("%d",&h);
			if(!flag[h])
				change(dfn[pos[h]],dfn[pos[h]] + sz[pos[h]] - 1,1),flag[h] = true;
		}
		else if(opt == '-'){
			int h;scanf("%d",&h);
			if(flag[h])
				change(dfn[pos[h]],dfn[pos[h]] + sz[pos[h]] - 1,-1),flag[h] = false;
		}
		else if(opt == '?'){
			scanf("%s",t+1);
			int now = rt;
			int len = strlen(t+1);
			int ans = 0;
			for(int j=1; j<=len; j++){
				while(now && !ch[now][t[j] - 'a'])	now = fail[now];
				if(!now)	now = rt;
				if(ch[now][t[j] - 'a'])	now = ch[now][t[j] - 'a'];
				ans = ans + query(dfn[now]);
			}
			printf("%d\n",ans);
		}
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+5;
const int ALP = 26;
struct edge{
	int nxt,to;
	edge(){}
	edge(int _nxt,int _to){
		nxt = _nxt,to = _to;
	}
}e[N];
int tot=1,rt=1,res,cnt,head[N],ch[N][ALP],sz[N],fail[N],sum[N],dfn[N],pos[N],ans[N];
char s[N],add[N];
vector<int> Q[N],to[N];
void add_edge(int from,int to){
	e[++cnt] = edge(head[from],to);
	head[from] = cnt;
}
void insert(char *s,int id){
	int n = strlen(s+1);
	int now = rt;
	for(int i=1; i<=n; i++){
		if(!ch[now][s[i] - 'a'])	ch[now][s[i] - 'a'] = ++tot;
		now = ch[now][s[i] - 'a'];
	}
	pos[id] = now;
}
void build(){
	queue<int> q;
	for(int i=0; i<ALP; i++){
		if(ch[rt][i]){
			fail[ch[rt][i]] = rt;
			q.push(ch[rt][i]);
		}
		else	ch[rt][i] = rt;
	}
	while(!q.empty()){
		int now = q.front();q.pop();
		for(int i = 0; i<ALP; i++){
			if(ch[now][i]){
				fail[ch[now][i]] = ch[fail[now]][i];
				q.push(ch[now][i]);
			}
			else	ch[now][i] = ch[fail[now]][i];
		}
	}
}
void dfs(int now,int fath){
	dfn[now] = ++res;sz[now] = 1;
	for(int i = head[now]; i;i = e[i].nxt){
		int to = e[i].to;
		if(to == fath)	continue;
		dfs(to,now);
		sz[now] += sz[to];
	}
}
void modify(int x,int val){
	for(;x<=res;x+=x&(-x))	sum[x] += val;
}
int query(int x){
	int ans = 0;
	for(;x;x-=x&(-x))	ans += sum[x];
	return ans;	
}
int query(int l,int r){
	return query(r) - query(l-1);
}
void calc(int p,int now){
	if(p){
		while(now && !ch[now][add[p] - 'a'])	now = fail[now];
		if(ch[now][add[p] - 'a'])	now =  ch[now][add[p] - 'a'];
		if(!now) now = rt;
		modify(dfn[now],1);
	}
	for(auto i : Q[p])	
		ans[i] = query(dfn[pos[i]],dfn[pos[i]] + sz[pos[i]] - 1);
	for(auto i : to[p])	
		calc(i,now);
	modify(dfn[now],-1);
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int n;
	scanf("%d",&n);
	for(int i=1; i<=n; i++){
		int opt;
		scanf("%d",&opt);
		if(opt == 1){
			char c;cin>>c;
			to[0].push_back(i);
			add[i] = c;
		}
		else{
			int p;char c;
			scanf("%d",&p);cin>>c;
			to[p].push_back(i);
			add[i] = c;
		}
	}
	int m;
	scanf("%d",&m);
	for(int i=1; i<=m; i++){
		int h;
		scanf("%d%s",&h,s+1);
		insert(s,i);
		Q[h].push_back(i);
	}
	build();
	for(int i=2; i<=tot; i++)	add_edge(fail[i],i);
	dfs(1,0);
	calc(0,1);  //当前是在哪个版本的串，当前在哪个节点 
	for(int i=1; i<=m; i++)	printf("%d\n",ans[i]);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int ALP = 2;
const int N = 5e4+5;
int ans,tot=1,rt=1,ch[N][ALP],fail[N];
bool flag[N],use[N],vis[N];
char s[N];
void insert(char *s){
	int n = strlen(s+1);
	int now = rt;
	for(int i = 1; i<=n; i++){
		if(!ch[now][s[i] - '0'])	ch[now][s[i] - '0'] = ++tot;
		flag[ch[now][s[i] - '0']] |= flag[now];
		now = ch[now][s[i] - '0'];
	}
	flag[now] = true;
}
void build(){
	queue<int> q;
	for(int i=0; i<ALP; i++){
		if(ch[rt][i])	fail[ch[rt][i]] = rt,q.push(ch[rt][i]);
	}
	while(!q.empty()){
		int now = q.front();q.pop();
		for(int i = 0; i<ALP; i++){
			if(ch[now][i]){
				fail[ch[now][i]] = ch[fail[now]][i];
				if(flag[fail[ch[now][i]]])	flag[ch[now][i]] = true;
				q.push(ch[now][i]);
			}
			else	ch[now][i] = ch[fail[now]][i];
		}
	}
}
bool calc(int now){
	vis[now] = true;
	for(int i = 0; i < ALP; i++){
		int to = ch[now][i];
		if(vis[to])	return true;
		if(flag[to] || use[to])	continue;
		use[to] = true;
		if(calc(to))	return true;
	}
	vis[now] = false;
	return false;
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int n;
	scanf("%d",&n);
	for(int i=1; i<=n; i++){
		scanf("%s",s+1);
		insert(s);
	}
	build();
//	for(int i=1; i<=tot; i++){
//		for(int j=0; j<ALP; j++){
//			if(ch[i][j])	printf("%d %d\n",i,ch[i][j]);
//		}
//	}
	if(calc(1))	printf("TAK\n");
	else	printf("NIE\n");
	return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 4e5+5;
const int ALP = 26;
struct ACAM{
	int rt=1,tot=1,f[N],ch[N][ALP],fail[N],val[N];
	void insert(char *s){
		int n = strlen(s+1);
		int now = rt;
		for(int i=1; i<=n; i++){
			if(!ch[now][s[i] - 'a'])	ch[now][s[i] - 'a'] = ++tot;
			now = ch[now][s[i] - 'a'];
		}
		val[now]++;
	}
	void build(){
		queue<int> q;
		for(int i=0; i<ALP; i++){
			if(ch[rt][i]){
				fail[ch[rt][i]] = rt;
				val[ch[rt][i]] += val[rt];
				q.push(ch[rt][i]);
			}
			else	ch[rt][i] = rt;
		}
		while(!q.empty()){
			int now = q.front();q.pop();
			for(int i=0; i<ALP; i++){
				if(ch[now][i]){
					fail[ch[now][i]] = ch[fail[now]][i];
					val[ch[now][i]] += val[fail[ch[now][i]]];
					q.push(ch[now][i]);
				}
				else	ch[now][i] = ch[fail[now]][i];
			}
		}
	}
	void query(char *s){
		int n = strlen(s+1);
		int now = rt;
		for(int i=1; i<=n; i++){
			while(now && !ch[now][s[i] - 'a'])	now = fail[now];
			if(ch[now][s[i] - 'a'])	now = ch[now][s[i] - 'a'];
			if(!now)	now = rt;
			f[i] = val[now];	
		}
	}
}ac,ac2;
char s[N],t[N];
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	scanf("%s",s+1);
	int n;
	scanf("%lld",&n);
	for(int i=1; i<=n; i++){
		scanf("%s",t+1);
		int m = strlen(t+1);
		ac.insert(t);
		reverse(t+1,t+m+1);
		ac2.insert(t);
	}
	ac.build();ac2.build();
	ac.query(s);
	n = strlen(s+1);reverse(s+1,s+n+1);
	ac2.query(s);
	int ans = 0;
	for(int i=1; i<n; i++)	
		ans = ans + ac.f[i] * ac2.f[n - i];
	printf("%lld\n",ans);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 3e6+5;
const int ALP = 26;
int tot=1,rt=1,g[N],ch[N][ALP],fail[N],f[N];
char s[N];
void insert(char *s){
	int n = strlen(s+1);
	int now = rt;
	for(int i=1; i<=n; i++){
		if(!ch[now][s[i] - 'a'])	ch[now][s[i] - 'a'] = ++tot;
		now = ch[now][s[i] - 'a'];
	}
	g[now] |= 1<<(n-1);
}
void build(){
	queue<int> q;
	for(int i=0; i<ALP; i++){
		if(ch[rt][i]){
			fail[ch[rt][i]] = rt;
			g[ch[rt][i]] |= g[rt];
			q.push(ch[rt][i]);
		}
		else	ch[rt][i] = rt;
	}
	while(!q.empty()){
		int now = q.front();q.pop();
		for(int i=0; i<ALP; i++){
			if(ch[now][i]){
				fail[ch[now][i]] = ch[fail[now]][i];
				g[ch[now][i]] |= g[ch[fail[now]][i]];
				q.push(ch[now][i]); 
			}
			else	ch[now][i] = ch[fail[now]][i];
		}
	}
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1; i<=n; i++){
		scanf("%s",s+1);
		insert(s);
	}
	build();
	while(m--){
		int tmp = (1<<22)-1;
		scanf("%s",s+1);
		n = strlen(s+1);
		int now = rt;
		int x = 1;  //认为 f[0] = 1 
		for(int i=1; i<=n; i++){
			while(now && !ch[now][s[i] - 'a'])	now = fail[now];
			if(ch[now][s[i] - 'a'])	now = ch[now][s[i] - 'a'];
			if(!now)	now = rt;
			if(x & g[now])	f[i] = 1;
			else	f[i] = 0;
			x = (x<<1) | f[i];
			x = x & tmp;  //防止超了直接爆掉 
		}
		int ans = 0;
		for(int i=n; i>=1; i--){
			if(f[i]){
				ans = i;
				break;
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 2e6+5;
const int ALP = 26;
struct edge{
	int nxt,to;
	edge(){}
	edge(int _nxt,int _to){
		nxt = _nxt,to = _to;
	}
}e[N];
int tot=1,rt=1,res,cnt,a[N],pos[N],head[N],dfn[N],ch[N][ALP],fail[N],son[N],fa[N],top[N],sz[N],dep[N],sum[N];
char s[N];
void add_edge(int from,int to){
	e[++cnt] = edge(head[from],to);
	head[from] = cnt;
}
void insert(char *s,int id){
	int now = rt;
	int n = strlen(s+1);
	for(int i=1; i<=n; i++){
		if(!ch[now][s[i] - 'a'])	ch[now][s[i] - 'a'] = ++tot;
		now = ch[now][s[i] - 'a'];
	}
	pos[id] = now;
}
void build(){
	queue<int> q;
	for(int i=0; i<ALP; i++){
		if(ch[rt][i]){
			fail[ch[rt][i]] = rt;
			q.push(ch[rt][i]);
		}
		else	ch[rt][i] = rt;
	}
	while(!q.empty()){
		int now = q.front();q.pop();
		for(int i=0; i<ALP; i++){
			if(ch[now][i]){
				fail[ch[now][i]] = ch[fail[now]][i];
				q.push(ch[now][i]);
			}
			else	ch[now][i] = ch[fail[now]][i];
		}
	}
}
void dfs1(int now,int fath){
	fa[now] = fath;dep[now] = dep[fath] + 1;
	sz[now] = 1;son[now] = 0;
	for(int i = head[now]; i;i = e[i].nxt){
		int to = e[i].to;
		if(to == fath)	continue;
		dfs1(to,now);
		sz[now] += sz[to];
		if(sz[to] > sz[son[now]])	son[now] = to;
	}
}
void dfs2(int now,int topf){
	top[now] = topf;
	dfn[now] = ++res;
	if(son[now])	dfs2(son[now],topf);
	for(int i = head[now]; i;i = e[i].nxt){
		int to = e[i].to;
		if(to == fa[now] || to == son[now])	continue;
		dfs2(to,to);
	}
}
int lca(int x,int y){
	while(top[x] != top[y]){
		if(dep[top[x]] < dep[top[y]])	swap(x,y);
		x = fa[top[x]];
	}
	if(dep[x] > dep[y])	swap(x,y);
	return x;
}
bool cmp(int a,int b){
	return dfn[a] < dfn[b];
}
void modify(int x,int val){
	for(;x <= res;x += x & (-x))	sum[x] += val;
}
int query(int x){
	int ans = 0;
	for(;x;x -= x & (-x))	ans += sum[x];
	return ans;
}
int query(int l,int r){
	return query(r) - query(l-1);
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int n;
	scanf("%d",&n);
	for(int i=1; i<=n; i++){
		scanf("%s",s+1);
		insert(s,i);
	}
	build();
	for(int i=2; i<=tot; i++)	add_edge(fail[i],i);
	
	dfs1(1,0);
	dfs2(1,1);
	int q;
	scanf("%d",&q);
	for(int i=1; i<=q; i++){
		int opt;
		scanf("%d",&opt);
		if(opt == 1){
			scanf("%s",s+1);
			int now = rt;n = strlen(s+1);
			int tmp = 0;
			for(int j=1; j<=n; j++){
				now = ch[now][s[j] - 'a'];
				a[++tmp] = now;
			}
			sort(a+1,a+tmp+1,cmp);
			for(int j=1; j<=tmp; j++)	modify(dfn[a[j]],1);
			for(int j=1; j<tmp; j++)	modify(dfn[lca(a[j],a[j+1])],-1);
		}
		else{
			int x;
			scanf("%d",&x);x = pos[x];
			printf("%d\n",query(dfn[x],dfn[x] + sz[x] - 1));
		}
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 2e6+5;
int k,cnt,mu[N],prime[N],pre[N];
bool flag[N];
void pre_work(int mx){
	mu[1] = 1;
	for(int i=2; i<=mx; i++){
		if(!flag[i]){
			prime[++cnt] = i;
			mu[i] = -1;
		}
		for(int j=1; j<=cnt && i * prime[j] <= mx; j++){
			flag[i * prime[j]] = true;
			if(i % prime[j] == 0)	break;
			else	mu[i * prime[j]] = -mu[i];
		}
	}
	pre[0] = 0;
	for(int i=1; i<=mx; i++)	pre[i] = pre[i-1] + mu[i];
}
int calc(int n,int m){
	int ans = 0;
	int mx = min(n,m);
	for(int l=1,r;l<=mx;l = r + 1){
		r = min(n / (n / l),m / (m / l));
		ans = ans + (pre[r] - pre[l-1]) * (n / l) * (m / l); 
	}
	return ans;
}
int main(){
	pre_work(100000);
	int n;
	scanf("%d",&n);
	for(int i=1; i<=n; i++){
		int a,b,c,d;
		scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
		printf("%d\n",calc(b/k,d/k) - calc(b/k,(c-1)/k) - calc((a-1)/k,d/k) + calc((c-1)/k,(a-1)/k));
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 4e5+5;
int fa[N],ans[N];
vector<int> son[N];
int find(int x){
	if(fa[x] == x)	return x;
	return fa[x] = find(fa[x]);	
}
void merge(int u,int v,int val){
	if(find(u) == find(v))	return;
	u = find(u),v = find(v);
	if(son[u].size() < son[v].size())	swap(u,v);
	if(find(1) == find(u))	for(int i : son[v])	ans[i] = val;
	if(find(1) == find(v))	for(int i : son[u])	ans[i] = val;
	for(int i : son[v])	son[u].push_back(i);
	fa[v] = u;
	son[v].clear();
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int n;
	scanf("%d",&n);
	for(int i=1; i<=n; i++)	fa[i] = i,son[i].push_back(i);
	for(int i=1; i<=n; i++)	ans[i] = -1;
	ans[1] = 0;
	int m1,m2;
	scanf("%d%d",&m1,&m2);
	for(int i=1; i<=m1; i++){
		int u,v;
		scanf("%d%d",&u,&v);
		merge(u,v,0);
	}
	for(int i=1; i<=m2; i++){
		int u,v;
		scanf("%d%d",&u,&v);
		merge(u,v,i);
	}
	for(int i=1; i<=n; i++)
		printf("%d\n",ans[i]);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 200;
int f[N],b[N];
void dfs(int id,int pos){
	if(b[id] == pos)	return;
	for(int i=id-1; i>=1; i--)	dfs(i,3 - b[id] - pos);   //神奇的发现这个就是可以找到 b[id] 和 pos 之外的那一个
	b[id] = pos;printf("%d %c\n",id,pos + 'A'); 
}
int main(){
	int n;
	scanf("%d",&n);
	f[1] = 1,f[2] = 2;
	for(int i=3; i<=n; i++){
		f[i] = f[i-1] * 2 + (i % 3 != 2);
	}
	printf("%d\n",f[n]);
	if(n <= 20){
		for(int i=2; i<=n; i+=2)	b[i] = 2;
		for(int i=n; i>=1; i--)	dfs(i,1);
	}
	return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e7+5;
const int MOD = 1004535809;
int tot,a[N],phi[N],prime[N];
bool flag[N];
unsigned seed, mod; 
unsigned read() {
    seed ^= seed << 13; 
    seed ^= seed >> 5; 
    seed ^= seed << 7; 
    return seed % mod + 1; 
}
void pre_work(int mx){
	phi[1] = 1;
	for(int i=2; i<=mx; i++){
		if(!flag[i]){
			phi[i] = i-1;
			prime[++tot] = i;
		}
		for(int j=1; j<=tot && i * prime[j] <= mx; j++){
			flag[i * prime[j]] = true;
			if(i % prime[j] == 0){
				phi[i * prime[j]] = phi[i] * prime[j];
			}
			else	phi[i * prime[j]] = phi[i] * phi[prime[j]];
		}
	}
}
int calc(int i,int n){
	int mn = a[0];
	int tot = 0;
	for(int j = (i == n ? 0 : i); j != 0 ; j = (j + i)%n){
		mn = a[j] < mn ? a[j] : mn;
		tot++;
	}
	++tot;
	return (tot * mn)%MOD;
}
signed main(){
	pre_work(10000000);
	int n;
	scanf("%lld",&n);
	int p = n;
	cin>>seed>>mod;
	for(int i=1; i<=n; i++)	a[i] = read();
	int ans = 0;
	a[0] = a[n];
	for(int i=1; i<=n; i++){  //i 其实就是枚举的 gcd 
		if(n % i == 0){
			int h = n / i;
			ans = (ans + phi[n/i] * calc(i,n))%MOD;
		}
	}
	printf("%lld\n",ans);
	return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e7+5;
const int MOD = 20101009;
int tot,prime[N],mu[N],pre[N];
bool flag[N];
int mod(int x){
	return ((x % MOD)+MOD)%MOD;
}
void pre_work(int mx){
	mu[1] = 1;
	for(int i=2; i<=mx; i++){
		if(!flag[i]){
			prime[++tot] = i;
			mu[i] = -1;
		}
		for(int j=1; j<=tot && i * prime[j] <= mx; j++){
			flag[i * prime[j]] = true;
			if(i % prime[j] == 0) break;
			else	mu[i * prime[j]] = -mu[i];
		}
	}
	pre[0] = 0;
	for(int i=1; i<=mx; i++)	pre[i] = mod(pre[i-1] + mod(mod(mu[i] * i) * i));
}
int g(int n,int m){
	return mod(mod(n * (n + 1) / 2) * mod(m * (m + 1) / 2));
}
int sum(int n,int m){
	int ans = 0;
	for(int l=1,r; l <= min(n,m); l = r + 1){
		r = min(n/(n/l),m/(m/l));
		ans = mod(ans + (pre[r] - pre[l-1]) * g(n/l,m/l));
	}
	return ans;
}
int calc(int n,int m){
	int ans = 0;
	for(int l=1,r; l <= min(n,m); l = r + 1){
		r = min(n/(n/l),m/(m/l));
		ans = mod(ans + mod((r - l + 1) * (l + r) / 2)* sum(n/l,m/l));  
	}
	return ans;
}
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int n,m;
	scanf("%lld%lld",&n,&m);
	pre_work(max(n,m) + 5);
	printf("%lld\n",calc(n,m));
	return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5+5;
int tot,prime[N],mu[N],pre[N],g[N];
bool flag[N];
void pre_work(int mx){
	mu[1] = 1;
	for(int i=2; i<=mx; i++){
		if(!flag[i]){
			prime[++tot] = i;
			mu[i] = -1;
		}
		for(int j=1; j<=tot && i * prime[j] <= mx; j++){
			flag[i * prime[j]] = true;
			if(i % prime[j] == 0)	break;
			else	mu[i * prime[j]] = -mu[i];
		}
	}
	pre[0] = 0;
	for(int i=1; i<=mx; i++)	pre[i] = pre[i-1] + mu[i];
	for(int i=1; i<=mx; i++){  //预处理 T/i 的和的式子，方便后续计算 
		for(int l=1,r=0; l<=i; l = r + 1){
			r = i / (i / l);
			g[i] = g[i] + (r - l + 1) * (i / l);
		}
	}
}
int calc(int n,int m){
	int ans = 0;
	for(int l=1,r; l <= min(n,m); l = r + 1){
		r = min(n/(n/l),m/(m/l));
		ans = ans + (pre[r] - pre[l-1]) * g[n/l] * g[m/l];
	}
	return ans;
}
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	pre_work(50000);
	int t;
	scanf("%lld",&t);
	while(t--){
		int n,m;
		scanf("%lld%lld",&n,&m);
		printf("%lld\n",calc(n,m));
	}
	return 0;
}

#include<bits/stdc++.h>
#define int unsigned   //这个模数相当于自然溢出 
using namespace std;
const int N = 1e7+5;
int f[N << 1],F[N << 1];
vector<int> prime;
bitset< N<<1 > flag;
int power(int a,int b){
	int res = 1;
	while(b){
		if(b & 1)	res = res * a;
		a = a * a;
		b >>= 1;
	}
	return res;
}
void pre_work(int mx,int k){
	f[1] = F[1] = 1;
	for(int i=2; i<=mx; i++){
		if(!flag[i]){
			prime.push_back(i);
			f[i] = i-1;F[i] = power(i,k);
		}
		for(int j : prime){
			if(i * j > mx)	break;
			flag[i * j] = true;
			F[i * j] = F[i] * F[j];
			if(i % j == 0){
				int h = i / j;
				if(h % j)  //这样就说明只是二次方，没有更多了 
					f[i * j] = f[h] * (-j);
				break;
			}
			else	f[i * j] = f[i] * (j - 1);
		}
	}
	for(int i=1; i<=mx; i++)	f[i] = f[i-1] + f[i] * F[i];  //先乘上 T^k
	for(int i=1; i<=mx; i++)	F[i] = F[i] + F[i-1];
	for(int i=1; i<=mx; i++)	F[i] = F[i] + F[i-1];
}
int calc(int n){
	return F[2*n] - 2 * F[n];
}
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int T,N,K;
	cin>>T>>N>>K;
	pre_work(N<<1,K);
	while(T--){
		int n;
		cin>>n;
		int ans = 0;
		for(int l=1,r=0; l<=n; l = r + 1){
			r = n / (n / l);
			ans = ans + (f[r] - f[l-1]) * calc(n / l);
		}
		cout<<ans<<'\n';
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		int n,k;
		scanf("%d%d",&n,&k);
		int ans = 0;
		for(int i=1; i<=n; i++){
			int a;
			scanf("%d",&a);
			ans |= a;
		}
		if(ans)	printf("YES\n");
		else	printf("NO\n");
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int a[N],pre[N],suf[N];
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int t;
	scanf("%d",&t);
	while(t--){
		int n;
		scanf("%d",&n);
		for(int i=1; i<=n; i++)	scanf("%d",&a[i]);
		for(int i=1; i<=n; i++)	pre[i] = pre[i-1] + (a[i] == 1);
		for(int i=n; i>=1; i--)	suf[i] = suf[i+1] + (a[i] == 0);
		int ans = 10000000;
		for(int i=0; i<=n; i++){  //枚举分界点 
			//[1,i]   [i+1,n]
			if(pre[i] >= suf[i+1]){
				ans = min(ans,pre[i]);
			}
		}
		printf("%d\n",ans);
		for(int i=1; i<=n; i++)	pre[i] = suf[i] = 0;
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 2e6+5;
int a[N],pos[N];
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		int n;
		scanf("%d",&n);
		for(int i=1; i<=n; i++)	scanf("%d",&a[i]);
		for(int i=1; i<=n; i++)	pos[n - a[i] + 1] = i;
		for(int i=1; i<=n; i++){
			printf("%d ",pos[i]);
		}
		printf("\n");
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 2e6+5;
int a[N],pos[N];
pair<int,int> b[N];
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int t;
	scanf("%d",&t);
	while(t--){
		int n;
		scanf("%d",&n);
		for(int i=1; i<=n; i++)	a[i] = 0,b[i] = {0,0},pos[i] = 1;
		for(int i=1; i<=n; i++)	scanf("%d",&a[i]);
		for(int i=1; i<=n; i++)	b[i] = {a[i] - a[i-1],i};
		int r = n,l = 1;
		sort(b+1,b+n+1);
		for(int i=1; i<=n; i++){
			if(b[i].first < 0){
				b[i].first += r;
				r--;
				pos[r+1] = b[i].second;
				while(b[i].first < 0){
					b[i].first += l;
					l++;
					pos[l-1] = b[i].second;
				}
			}	
		}
		for(int i=1; i<=n; i++)	printf("%d ",pos[i]);
		printf("\n");
	}
	return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5+5;
struct edge{
	int nxt,to;
	edge(){}
	edge(int _nxt,int _to){
		nxt = _nxt,to = _to;
	}
}e[N];
int ans = 0,cnt,head[N],fa[N],val[N],son[N];
multiset<int> st[N];
void add_edge(int from,int to){
	e[++cnt] = edge(head[from],to);
	head[from] = cnt;
}
void dfs(int now,int k){
	if(!son[now])	st[now].insert(0);
	ans += k * val[now];
	for(int i = head[now]; i;i = e[i].nxt){
		int to = e[i].to;
		dfs(to,k/son[now]);
		if(!st[to].empty()){
			multiset<int>::iterator it = st[to].end();it--;
			st[now].insert(*it + val[to]);
		}
	}
	multiset<int>::iterator it = st[now].begin();
//	printf("%lld:",now);
//	while(it != st[now].end()){
//		printf("%lld ",*it);
//		it++;
//	}
//	printf("\n");
	if(son[now]){
		int p = k % son[now];
		for(int i=1; i<=p; i++){
			multiset<int>::iterator it = st[now].end();it--;
			ans = ans + *it;
			st[now].erase(it);
		}
	}
}
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int t;
	scanf("%lld",&t);
	while(t--){
		int n,k;
		scanf("%lld%lld",&n,&k);
		for(int i=2; i<=n; i++){
			scanf("%lld",&fa[i]);
			add_edge(fa[i],i);
			son[fa[i]]++;
		}
		for(int i=1; i<=n; i++)	scanf("%lld",&val[i]);
		dfs(1,k);
		printf("%lld\n",ans);
		for(int i=1; i<=n; i++)	st[i].clear();
		for(int i=1; i<=n; i++)	head[i] = 0,son[i] = 0;
		cnt = ans = 0;
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
bool query(vector<int> v){
	printf("? %d ",v.size());
	for(int i : v)	printf("%d ",i);
	printf("\n");
	string s;cin>>s;
	return s == "YES";
}
vector<int> insert(const vector<int> a,vector<int> b){
	vector<int> tmp;
	for(int i : a)	tmp.push_back(i);
	for(int i : b)	tmp.push_back(i);
	return tmp;
}
void solve(vector<int> v){
	if(v.size() <= 2){
		printf("! %d\n",v[0]);
		string s;cin>>s;
		if(s == ":)")	return;
		printf("! %d\n",v[1]);
		return;
	}
	else if(v.size() == 3){
		bool is[4];
		is[0] = query({v[0]});
		is[1] = query({v[1]});
		is[2] = query({v[1]});
		is[3] = query({v[0]});
		if(is[1] && is[2])	solve({v[1]});  //这个推导过程需要在纸上画一下自己感觉一下 
		else if(!is[1] && !is[2])	solve({v[0],v[2]});
		else if((is[0] && is[1]) || (is[2] && is[3]))	solve({v[0],v[1]});
		else if((!is[0] && is[1]) || (is[2] && !is[3]))	solve({v[1],v[2]});
		else	solve({v[0],v[2]});
	}
	else{
		vector<int> v1,v2;v1.clear();v2.clear();;
		for(int i=0; i<v.size(); i++){
			if(i & 1)	v1.push_back(v[i]);
			if(i & 2)	v2.push_back(v[i]);
		}
		bool is[2];is[0] = is[1] = false;
		vector<int> tmp;
		is[0] = query(v1);
		is[1] = query(v2);
		tmp.clear();
		for(int i = 0; i<v.size(); i++){
			if((!(i & 1) ^ is[0]) || (!(i&2) ^ is[1]))
				tmp.push_back(v[i]);
			//考虑 对+错：舍弃 v3
			//考虑 对+对：舍弃 v4
			//考虑 错+错：舍弃 v1
			//考虑 错+对：舍弃 v2 
			//推荐自己推一下，确实这样是可行的 
			//v1:x&1 && x&2 
			//v2:!x&1 && x&2
			//v3:x&1 && !x&1
			//v4:!x&1 && !x&2
		}
		solve(tmp);
	}
}
int main(){
	vector<int> tmp;
	int n;
	scanf("%d",&n);
	for(int i=1; i<=n; i++)	tmp.push_back(i);
	solve(tmp);
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e6+5;
const int MOD = 1e9+7;
vector<int> v[N];
int tot,phi[N],prime[N],fac[N],inv[N],cnt[N],ans;
bool flag[N];
int mod(int x){
	return ((x % MOD) + MOD)%MOD;
}
int power(int a,int b){
	int res = 1;
	while(b){
		if(b & 1)	res = mod(res * a);
		a = mod(a * a);
		b >>= 1;
	}
	return res;
}
void pre_work(int n){
	for(int i=1; i<=n; i++)
		for(int j=i; j<=n; j += i)
			v[j].push_back(i);
	phi[1] = 1;
	for(int i=2; i<=n; i++){
		if(!flag[i]){
			prime[++tot] = i;
			phi[i] = i-1;
		}
		for(int j=1; j<=tot && i * prime[j] <= n; j++){
			flag[i * prime[j]] = true;
			if(i % prime[j] == 0){
				phi[i * prime[j]] = phi[i] * prime[j];
				break;
			}
			else	phi[i * prime[j]] = phi[i] * (prime[j] - 1);
		}
	}
	fac[0] = 1;
	for(int i=1; i<=n; i++)	fac[i] = mod(fac[i-1] * i);
	inv[n] = power(fac[n],MOD-2);
	for(int i=n-1; i>=0; i--)	inv[i] = mod(inv[i+1] * (i + 1));
}
int C(int n,int m){
	if(n < m)	return 0;
	return mod(mod(fac[n] * inv[m]) * inv[n - m]);
}
void insert(int x,int k){
	for(int i : v[x]){
		int tmp = C(cnt[i],k);
		cnt[i]++;
		ans = mod(ans + phi[i] * mod(C(cnt[i],k) - tmp));
	}
}
signed main(){
	pre_work(1000000);
	int n,k,q;
	scanf("%lld%lld%lld",&n,&k,&q);
	for(int i=1; i<=n; i++){
		int x;
		scanf("%lld",&x);
		insert(x,k);
	}
	for(int i=1; i<=q; i++){
		int x;
		scanf("%lld",&x);
		insert(x,k);

		printf("%lld\n",ans);
	}
	return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e6+5;
const int MOD = 1e9+7;
int tot,fib[N],mu[N],g[N],prime[N],F[N],inv[N],pre[N];
bool flag[N];
int mod(int x){
	return ((x%MOD)+MOD)%MOD;
}
int power(int a,int b){
	int res = 1;
	while(b){
		if(b & 1)	res = mod(res * a);
		a = mod(a * a);
		b >>= 1;
	}
	return res;
}
void pre_work(int n){
	fib[0] = 0,fib[1] = 1;
	for(int i=2; i<=n; i++)	fib[i] = mod(fib[i-1] + fib[i-2]);
	mu[1] = 1;
	for(int i=2; i<=n; i++){
		if(!flag[i]){
			mu[i] = -1;
			prime[++tot] = i;
		}
		for(int j=1; j<=tot && i * prime[j] <= n; j++){
			flag[i * prime[j]] = true;
			if(i % prime[j]	== 0)	break;
			else	mu[i * prime[j]] = -mu[i];
		}
	}
	for(int i=1; i<=n; i++)	g[i] = power(fib[i],MOD-2);
	for(int i=1; i<=n; i++)	F[i] = 1;
	for(int d=1; d<=n; d++){
		for(int T=d; T<=n; T+=d){
			int t = T / d;
			if(mu[t] == 1)	F[T] = mod(F[T] * fib[d]);
			else if(mu[t] == -1)	F[T] = mod(F[T] * g[d]);
		}
	}
	pre[0] = 1;
	for(int i=1; i<=n; i++)	pre[i] = mod(pre[i-1] * F[i]);
	for(int i=0; i<=n; i++)	inv[i] = power(pre[i],MOD-2);
}
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	pre_work(1000000);
	int t;
	scanf("%lld",&t);
	while(t--){
		int n,m;
		scanf("%lld%lld",&n,&m);
		if(n > m)	swap(n,m);
		int ans = 1;
		for(int l=1,r; l<=n; l = r + 1){
			r = min(n/(n/l),m/(m/l));
			ans = mod(ans * power(mod(pre[r] * inv[l-1]),(n/l) * (m/l)));
		}
		printf("%lld\n",ans);
	}
	return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
	int n,k;
	scanf("%lld%lld",&n,&k);
	int ans = 0;
	for(int l=1,r; l <= n; l = r + 1){
		if(k / l != 0)	r = min(k / (k / l),n);
		else	r = n;
		ans = ans + (r - l + 1) * k - (k / l) * (l + r) * (r - l + 1) / 2;
	}
	printf("%lld\n",ans);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 1e8+5;
const int MOD = 1e8+7;
int prime[5761456],tot;
bitset<N> flag;
void pre_work(int mx){
	for(int i=2; i<=mx; i++){
		if(!flag[i]){
			prime[++tot] = i;
		}
		for(int j=1; j<=tot && 1ll * i * prime[j] <= 1ll * mx; j++){
			flag[i * prime[j]] = true;
			if(i % prime[j] == 0)	break;
		}
	}
}
int main(){
//	freopen("in.txt","r",stdin);
	int n;
	scanf("%d",&n);
	pre_work(n);
	long long ans = 1;
	for(int i=1; i<=tot; i++){
		long long now = 1;
		while(1ll * now * prime[i] <= 1ll * n)	now = 1ll * now * prime[i];
		ans = (ans * now)%MOD;
	}
	printf("%lld\n",ans);
	return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 4e6+5;
int t[N],MOD;
int solve(int n,int k){
	int ans = 0;
	for(int i = k; i <= n; i += k)	
		ans = (ans + t[i])%MOD;
	return ans;
}
signed main(){
	int n,m;
	scanf("%lld%lld%lld",&n,&m,&MOD);
	if(n > m)	swap(n,m);
	for(int i=1; i<=m; i++){
		for(int j=i; j<=m; j+=i){
			t[j]++;
		}
	}
	int ans = 0;
	for(int T=1; T<=n; T++){
		ans = (ans + (solve(n,T) * solve(m,T))%MOD)%MOD;
	}
	printf("%lld\n",ans);
	return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e6+5;
int pre[N],a[N],b[N],val[N],tot;
void modify(int x,int v){
	for(;x <= tot; x += x & (-x))	val[x] += v;
}
int query(int x){
	int ans = 0;
	for(;x;x -= x & (-x))	ans += val[x];
	return ans;
}
signed main(){
	int n;
	scanf("%lld",&n);
	for(int i=1; i<=n; i++)	scanf("%lld",&a[i]);
	for(int i=1; i<=n; i++)	pre[i] = pre[i-1] + a[i];
	bool flag = true;
	for(int i=1; i<n; i++){
		if(pre[i] < 0 || pre[i] > pre[n])
			flag = false;
	}
	if(!flag || pre[n] < 0){
		printf("-1\n");
		return 0;
	}
	for(int i=1; i<=n; i++)	b[++tot] = pre[i];
	sort(b+1,b+tot+1);
	tot = unique(b+1,b+tot+1) - b - 1;
	for(int i=1; i<=n; i++)	pre[i] = lower_bound(b+1,b+tot+1,pre[i]) - b;
	int ans = 0;
	for(int i=1; i<n; i++){
		ans += (i - 1) - query(pre[i]);
		modify(pre[i],1);
	}
	printf("%lld\n",ans);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 1e7+5;
int rt=1,tot=1,ch[N][2],mx[N][2][2],a[N],dp[N];
void insert(int x,int val){
	int now = rt;
	for(int i=30; i>=0; i--){
		int p = (((x-1) ^ a[x]) >> i) & 1;
		if(!ch[now][p])	ch[now][p] = ++tot;
		mx[now][(a[x]>>i)&1][((x-1)>>i)&1] = max(mx[now][(a[x]>>i)&1][((x-1)>>i)&1],val);
		now = ch[now][p];
	}
}
int query(int x){
	int now = rt;
	int ans = 0;
	for(int i=30; i>=0; i--){
		int p = (((x-1) ^ a[x]) >> i) & 1;
		ans = max(ans,mx[now][(((x-1)>>i)&1)][((a[x] >> i) & 1) ^ 1]);
		now = ch[now][p];
		if(!now)	break;
	}
	return ans;
}
signed main(){
	int t;
	scanf("%d",&t);
	while(t--){
		int n;
		scanf("%d",&n);
		for(int i=1; i<=n; i++)	scanf("%d",&a[i]);
		dp[1] = 1;
		insert(1,dp[1]);
		for(int i=2; i<=n; i++){
			dp[i] = query(i) + 1;
			insert(i,dp[i]);
		}
		int ans = 0;
		for(int i=1; i<=n; i++)	ans = max(ans,dp[i]);
		printf("%d\n",ans);
		for(int i=1; i<=tot; i++){
			for(int j=0; j<=1; j++){
				for(int k=0; k<=1; k++){
					mx[i][j][k] = 0;
				}
				ch[i][j] = 0;
			}
		}
		tot = 1;
	}
	return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5+5;
int a[N],f[10][N],d[10];
multiset<int> st;
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int t;
	scanf("%lld",&t);
	while(t--){
		int n,q;
		scanf("%lld%lld",&n,&q);
		for(int i=1; i<=n; i++)	scanf("%lld",&a[i]);
		int tmp = n,tot = 0;
		for(int i=2; i<=tmp; i++){
			if(tmp % i == 0){
				d[++tot] = n / i;    // n / (n / i) = i 是个质数
				while(tmp % i == 0)	tmp /= i; 
			}
		}
		for(int i=1; i<=tot; i++){
			for(int j=0; j<d[i]; j++)	f[i][j] = 0;
			for(int j=1; j<=n; j++)		f[i][j % d[i]] += a[j];
			for(int j=0; j<d[i]; j++)	st.insert(d[i] * f[i][j]);
		}
		printf("%lld\n",*(st.rbegin()));
		while(q--){
			int x,y;
			scanf("%lld%lld",&x,&y);
			for(int i=1; i<=tot; i++){
				st.erase(st.find(d[i] * f[i][x % d[i]]));
				f[i][x % d[i]] += y - a[x];
				st.insert(d[i] * f[i][x % d[i]]);
			}
			a[x] = y;
			printf("%lld\n",*(st.rbegin()));
		}
		st.clear();
	}
	return 0;
}

#include<bits/stdc++.h>
#define int long long
#define PII pair<int,int> 
using namespace std;
const int N = 1e5+5;
struct edge{
	int nxt,to,val;
	edge(){}
	edge(int _nxt,int _to,int _val){
		nxt = _nxt,to = _to,val = _val;
	}
}e[2 * N];
int cnt,n,m,k,head[N],dis[N],st[N],tmp[N];
bool vis[N];
int X(int i){return 2 * i;}
int Y(int i){return dis[i] + 1ll * i * i;}
void add_edge(int from,int to,int val){
	e[++cnt] = edge(head[from],to,val);
	head[from] = cnt;
}
void dij(){
	priority_queue<PII> q;
	for(int i=1; i<=n; i++)	q.push({-dis[i],i});
	for(int i=1; i<=n; i++)	vis[i] = false;
	while(!q.empty()){
		int now = q.top().second;q.pop();
		if(vis[now])	continue;
		vis[now] = true;
		for(int i = head[now]; i;i = e[i].nxt){
			int to = e[i].to;
			if(dis[to] > dis[now] + e[i].val){
				dis[to] = dis[now] + e[i].val;
				q.push({-dis[to],to});
			}
		}
	}
}
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	scanf("%lld%lld%lld",&n,&m,&k);
	for(int i=1; i<=n; i++)	dis[i] = 1000000000000;
	for(int i=1; i<=m; i++){
		int u,v,w;
		scanf("%lld%lld%lld",&u,&v,&w);
		add_edge(u,v,w);add_edge(v,u,w);
	}
	dis[1] = 0;
	dij();
//	for(int i=1; i<=n; i++)	printf("dis[%lld] = %lld\n",i,dis[i]);
	while(k--){
		//建凸包
		int top = 0;
		for(int i=1; i<=n; i++){  //这样的话就需要建下凸包
			while(top >= 2 && (double)(Y(i) - Y(st[top])) / (X(i) - X(st[top])) <= (double)(Y(st[top]) - Y(st[top - 1])) / (X(st[top]) - X(st[top-1])))	top--;
			st[++top] = i;
		} 
//		for(int i=1; i<=top; i++)	printf("%lld %lld\n",X(st[i]),Y(st[i]));
//		printf("\n\n");
		for(int i=1; i<=n; i++){
			int l = 1,r = top,ans = 0;  //凸包上二分找最优决策点 
			while(l <= r){
				int mid = (l + r)>>1;
				if((Y(st[mid+1]) - Y(st[mid])) < 1ll * i * (X(st[mid+1]) - X(st[mid])))	l = mid + 1;
				else	r = mid - 1;
			}
			ans = l;
//			printf("%lld(%lld,%lld) -> %lld\n",st[ans],X(st[ans]),Y(st[ans]),i);
			tmp[i] = i * i + Y(st[ans]) - i * X(st[ans]);
		}
		for(int i=1; i<=n; i++) dis[i] = tmp[i];
//		for(int i=1; i<=n; i++)	printf("dis[%lld] = %lld\n",i,dis[i]);
		dij();
	}
	for(int i=1; i<=n; i++){
		printf("%lld ",dis[i]);
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3+5;
int val[N],fa[N],a[N][N];
int find(int x){
	if(fa[x] == x)	return x;
	int to = find(fa[x]);
	val[x] ^= val[fa[x]];
	return fa[x] = to;
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int t;
	scanf("%d",&t);
	while(t--){
		int n;
		scanf("%d",&n);
		for(int i=1; i<=n; i++){
			for(int j=1; j<=n; j++){
				scanf("%d",&a[i][j]);
			}
		}
		for(int i=1; i<=n; i++)	fa[i] = i,val[i] = 0;
		for(int i=1; i<=n; i++){
			for(int j=i+1; j<=n; j++){
				if(a[i][j] != a[j][i]){
					int fx = find(i),fy = find(j);
					if(a[i][j] > a[j][i]){  //想换 
						if(fx != fy){
							fa[fx] = fy;val[fx] = val[i] ^ val[j] ^ 1;
							swap(a[i][j],a[j][i]);
						}
						else if(val[i] ^ val[j])	swap(a[i][j],a[j][i]);
					}
					else if(a[i][j] < a[j][i]){
						if(fx != fy){
							fa[fx] = fy;val[fx] = val[i] ^ val[j];
						}
						else if(val[i] ^ val[j])	swap(a[i][j],a[j][i]);
					}
				}
			}
		}
		for(int i=1; i<=n; i++){
			for(int j=1; j<=n; j++){
				printf("%d ",a[i][j]);
			}
			printf("\n");
		}
	}
	return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAX = 2e5;
const int N = 2e5 + 5;
struct Query{
	int l,r,opt;
}q[N];
int ans[N],sum[MAX + 5];
vector<int> v[MAX + 5];
void modify(int x,int v){
	for(;x <= MAX; x += x & (-x))	sum[x] += v;
}
int query(int x){
	int ans = 0;
	for(;x;x -= x & (-x))	ans += sum[x];
	return ans;
}
bool cmp(Query a,Query b){
	return a.r < b.r;
}
signed main(){
	int t;
	scanf("%lld",&t);
	for(int i=1; i<=t; i++){
		scanf("%lld%lld",&q[i].l,&q[i].r);
		int l= q[i].l,r = q[i].r;
		ans[i] -= max(0ll,r/6 - (l-1)/3);
		ans[i] -= max(0ll,r/15 - (l-1)/6);
		q[i].opt = i;
	}
	sort(q+1,q+t+1,cmp);
	for(int i=1; i<=MAX; i++){
		for(int j = 2*i; j<=MAX; j+=i){
			v[j].push_back(i);
		}
	}
	int now = 1;
	for(int i=1; i<=MAX; i++){
		for(int j =0; j<v[i].size(); j++)	modify(v[i][j],v[i].size() - j - 1);
		while(now <= t && q[now].r <= i)	ans[q[now].opt] -= query(q[now].r) - query(q[now].l - 1),now++;
	}
	for(int i=1; i<=t; i++){
		int l = q[i].l,r = q[i].r;
		ans[q[i].opt] += (r-l-1) * (r-l) * (r-l+1) / 6;
	}
	for(int i=1; i<=t; i++)		printf("%lld\n",ans[i]);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
struct edge{
	int nxt,to;
	edge(){}
	edge(int _nxt,int _to){
		nxt = _nxt,to = _to;
	}
}e[2 * N];
int cnt,head[N],dis[N],a[N],ans;
multiset<int> st[N];
void add_edge(int from,int to){
	e[++cnt] = edge(head[from],to);
	head[from] = cnt;
}
void dfs(int now,int fath){
	bool flag = false;
	dis[now] = dis[fath] ^ a[now];
	st[now].insert(dis[now]);
	for(int i = head[now]; i;i = e[i].nxt){
		int to = e[i].to;
		if(to == fath)	continue;
		dfs(to,now);
		if(st[now].size() < st[to].size())	swap(st[now],st[to]);
		for(int j : st[to])	if(st[now].find(j ^ a[now]) != st[now].end())	flag = true;
		for(int j : st[to])	st[now].insert(j);
	}
	if(flag){
		ans++;
		st[now].clear();
	}
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int n;
	scanf("%d",&n);
	for(int i=1; i<=n; i++)	scanf("%d",&a[i]);
	for(int i=1; i<n; i++){
		int u,v;
		scanf("%d%d",&u,&v);
		add_edge(u,v);add_edge(v,u);
	}
	dfs(1,0);
	printf("%d\n",ans);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 6e5+5;
struct edge{
	int nxt,to;
	edge(){}
	edge(int _nxt,int _to){
		nxt = _nxt,to = _to;
	}
}e[2 * N];
int cnt,n,m,head[N],val[N],fa[N][30],from[N],to[N],dep[N],f[N];
bool flag[N];
void add_edge(int from,int to){
	e[++cnt] = edge(head[from],to);
	head[from] = cnt;
}
void calc(int now,int fath){
	for(int i = head[now]; i;i = e[i].nxt){
		int to = e[i].to;
		if(to == fath)	continue;
		val[to] += val[now];
		calc(to,now);
	}
}
void dfs(int now,int fath){
	fa[now][0] = fath;dep[now] = dep[fath] + 1;
	for(int i = head[now]; i;i = e[i].nxt){
		int to = e[i].to;
		if(to == fath)	continue;
		dfs(to,now);	
	}
}
void pre_lca(){
	for(int i=1; i<=24; i++){
		for(int j=1; j<=n; j++){
			fa[j][i] = fa[fa[j][i-1]][i-1];
		}
	}
}
int find(int x){
	if(f[x] == x)	return x;
	return f[x] = find(f[x]);
}
int get_lca(int x,int y){
	if(dep[x] > dep[y])	swap(x,y);
	for(int i=24; i>=0; i--){
		if(dep[fa[y][i]] >= dep[x])
			y = fa[y][i];
	}	
	if(x == y)	return x;
	for(int i=24; i>=0 ;i--){
		if(fa[x][i] != fa[y][i]){
			x = fa[x][i];y = fa[y][i];
		}
	}
	return fa[x][0];
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout); 
	scanf("%d%d",&n,&m);
	for(int i=1; i<=m; i++)	scanf("%d%d",&from[i],&to[i]);	
	for(int i=1; i<=n; i++)	f[i] = i;
	for(int i=1; i<=m; i++){
		if(find(from[i]) != find(to[i])){
			f[find(from[i])] = find(to[i]);
			flag[i] = true;
			add_edge(from[i],to[i]);add_edge(to[i],from[i]);
//			printf("%d %d\n",from[i],to[i]);
		}
	}
//	for(int i=1; i<=m; i++){
//		printf("%d",flag[i]);
//	}
//	printf("\n");
	dep[1] = 1;
	dfs(1,0);
	pre_lca();
	for(int i=1; i<=m; i++){
		if(flag[i])	continue;
		int u = from[i],v = to[i];
		if(dep[u] > dep[v])	swap(u,v);
		int lca = get_lca(u,v);
//		printf("lca(%d,%d) = %d\n",u,v,lca);
		if(lca == u){
			val[1]++;val[v]++;
			for(int j=24; j>=0; j--){
				if(dep[fa[v][j]] > dep[lca])
					v = fa[v][j];
			}
			val[v]--;
		}
		else	val[from[i]]++,val[to[i]]++;
	}
//	for(int i=1; i<=n; i++){
//		printf("%d ",val[i]);
//	}
//	printf("\n");
	calc(1,0);
	for(int i=1; i<=n; i++){
		if(val[i] == m - (n - 1))	printf("1");
		else	printf("0");
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 4e5+5;
struct edge{
	int nxt,to;
	edge(){}
	edge(int _nxt,int _to){
		nxt = _nxt,to = _to;
	}
}e[N];
int cnt,head[N],f[N],fa[N][27],dep[N],st[N][27],val[N],from[N],to[N];
void add_edge(int from,int to){
	e[++cnt] = edge(head[from],to);
	head[from] = cnt;
}
void dfs(int now,int fath){
	fa[now][0] = fath;dep[now] = dep[fath] + 1;
	for(int i = head[now]; i;i = e[i].nxt){
		int to = e[i].to;
		if(to == fath)	continue;
		dfs(to,now);
	}
}
void pre_lca(int n){
	for(int i=1; i<=24; i++){
		for(int j=1; j<=n; j++){
			fa[j][i] = fa[fa[j][i-1]][i-1];
		}
	}
}
int lca(int x,int y){
	if(dep[x] > dep[y])	swap(x,y);
	for(int i=24; i>=0; i--){
		if(dep[fa[y][i]] >= dep[x])
			y = fa[y][i];
	}
	if(x == y)	return x;
	for(int i=24; i>=0; i--){
		if(fa[x][i] != fa[y][i]){
			x = fa[x][i];
			y = fa[y][i];
		}
	}
	return fa[x][0];
}
int get_mx(int l,int r){
	if(l > r)	return 0;
	int len = log2(r-l+1);
	return max(st[l][len],st[r-(1<<len)+1][len]);
}
int find(int x){
	if(f[x] == x)	return x;
	return f[x] = find(f[x]);
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int t;
	scanf("%d",&t);
	while(t--){
		int n,m,q;
		scanf("%d%d%d",&n,&m,&q);
		for(int i=1; i<=m; i++){
			scanf("%d%d",&from[i],&to[i]);
		}
		for(int i=1; i<=n * 2; i++)	f[i] = i;
		int tot = n;
		for(int i=1; i<=m; i++){
			if(find(from[i]) != find(to[i])){
				int u = find(from[i]),v = find(to[i]);
				f[u] = f[v] = ++tot;val[tot] = i;
				add_edge(tot,u);add_edge(tot,v);
			}
		}
		dep[tot] = 1;
		dfs(tot,0);
		pre_lca(tot);
		for(int i=1; i<n; i++)	st[i][0] = val[lca(i,i+1)];
		for(int i=1; i<=24; i++){
			for(int j=1; j + (1<<i) <= n; j++){
				st[j][i] = max(st[j][i-1],st[j + (1<<(i-1))][i-1]);
			}
		}
		for(int i=1; i<=q; i++){
			int l,r;
			scanf("%d%d",&l,&r);
			if(l == r)	printf("0 ");
			else	printf("%d ",get_mx(l,r-1));
		}
		printf("\n");
		for(int i=1; i<=24; i++){
			for(int j=1; j<=n; j++){
				st[j][i] = 0;
			}
		}
		cnt = 0;
		for(int i=1; i<=tot; i++)	head[i] = 0;
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 5e6+5;
const int INF = 1e9+6;
int a[N],ans[N]; 
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int t;
	scanf("%d",&t);
	while(t--){
		memset(ans,0,sizeof(ans));
		int n,k;
		scanf("%d%d",&n,&k);
		for(int i=1; i<=n; i++)	scanf("%d",&a[i]);
		for(int i=1; i<=n; i++){
			int pre = -1;
			for(int l=1,r; l<=min(a[i],k); l = r + 1){
				r = a[i] / (a[i] / l);
				int cur = a[i] / l;
				ans[cur + 1] = max(ans[cur + 1],pre);
				pre = cur;
			}
			ans[0] = max(ans[0],pre);
		}
		int mx = 0;
		int res = INF;
		for(int i=0; i<=a[1]; i++){
			mx = max(mx,ans[i]);
			res = min(res,mx - i);
		}
		printf("%d\n",res);
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int MAX = 2e5+50;
const int N = 4e5+5;
int a[N],cnt[MAX + 10],sum[4 * MAX][2],tag[4 * MAX],p[4 * MAX][2];
void pushdown(int now,int now_l,int now_r){
	if(tag[now] != -1){
		sum[now<<1][tag[now]^1] = sum[now<<1|1][tag[now]^1] = 0;
		int mid = (now_l + now_r)>>1;
		sum[now<<1][tag[now]] = (mid - now_l + 1);
		sum[now<<1|1][tag[now]] = (now_r - mid);
		tag[now<<1] = tag[now<<1|1] = tag[now];
		p[now<<1][tag[now]] = mid;p[now<<1|1][tag[now]] = now_r;
		p[now<<1][tag[now]^1] = -1;p[now<<1|1][tag[now]^1] = -1;
		tag[now] = -1;
	}
}
void pushup(int now){
	sum[now][1] = sum[now<<1][1] + sum[now<<1|1][1];
	sum[now][0] = sum[now<<1][0] + sum[now<<1|1][0];
	p[now][1] = max(p[now<<1][1],p[now<<1|1][1]);
	p[now][0] = max(p[now<<1][0],p[now<<1|1][0]);
}
int get_pos(int now,int now_l,int now_r,int pos,int v){
	if(now_l == now_r)	return now_l;
	pushdown(now,now_l,now_r);
	int mid = (now_l + now_r)>>1;
	int ans = 0;
	if(p[now<<1][v] >= pos)	ans = get_pos(now<<1,now_l,mid,pos,v);
	else	ans = get_pos(now<<1|1,mid+1,now_r,pos,v);
	pushup(now);
	return ans;
}
int get_ans(int now,int now_l,int now_r){
	if(now_l == now_r)	return now_l;
	pushdown(now,now_l,now_r);
	int mid = (now_l + now_r)>>1;
	int ans = 0;
	if(sum[now<<1|1][1])	ans = get_ans(now<<1|1,mid+1,now_r);
	else	ans = get_ans(now<<1,now_l,mid);
	pushup(now);
	return ans;	
}
void modify(int now,int now_l,int now_r,int l,int r,int val){
	if(l <= now_l && r >= now_r){
		tag[now] = val;
		sum[now][val^1] = 0;
		sum[now][val] = (now_r - now_l + 1);
		p[now][val] = now_r;p[now][val^1] = -1;
		return;
	}
	pushdown(now,now_l,now_r);
	int mid = (now_l + now_r)>>1;
	if(l <= mid)	modify(now<<1,now_l,mid,l,r,val);
	if(r > mid)		modify(now<<1|1,mid+1,now_r,l,r,val);
	pushup(now);
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	memset(tag,-1,sizeof(tag));memset(p,-1,sizeof(p));
	int n,q;
	scanf("%d%d",&n,&q);
	for(int i=1; i<=n; i++)	scanf("%d",&a[i]);
	for(int i=1; i<=n; i++)	cnt[a[i]]++;
	for(int i=1; i<=MAX; i++)	cnt[i+1] += cnt[i] / 2,cnt[i] %= 2;
	for(int i=1; i<=MAX; i++)	modify(1,1,MAX,i,i,cnt[i]);
	for(int i=1; i<=q; i++){
		int x,y;
		scanf("%d%d",&x,&y);
		//考虑删除
		int pos1 = get_pos(1,1,MAX,a[x],1);
		if(pos1 == a[x])	modify(1,1,MAX,a[x],a[x],0);
		else	modify(1,1,MAX,a[x],pos1-1,1),modify(1,1,MAX,pos1,pos1,0);
		
		//考虑加入 
		a[x] = y;
		int pos0 = get_pos(1,1,MAX,a[x],0);
		if(pos0 == a[x])	modify(1,1,MAX,a[x],a[x],1);
		else	modify(1,1,MAX,a[x],pos0 - 1,0),modify(1,1,MAX,pos0,pos0,1);
		
		//考虑答案；
		printf("%d\n",get_ans(1,1,MAX)); 
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+5;
const int INF = 1e9+5;
int a[N],b[N],cnt[N],f[N];
bool calc(int l,int r,int mx){
	if(l > r)	return true;
	int len = (r - l + 1);
	if(mx <= len / 2 && len % 2 == 0)	return true;
	return false;
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int t;
	scanf("%d",&t);
	while(t--){
		int n;
		scanf("%d",&n);
		int tot = 0;
		for(int i=1; i<=n; i++)	scanf("%d",&a[i]);
		for(int i=1; i<=n; i++)	b[++tot] = a[i];
		sort(b+1,b+tot+1);
		tot = unique(b+1,b+tot+1) - b - 1;
		for(int i=1; i<=n; i++)	a[i] = lower_bound(b+1,b+tot+1,a[i]) - b;
		for(int i=1; i<=n; i++){
			for(int k=1; k<=tot; k++)	cnt[k] = 0;
			f[i] = -INF;
			int mx = 0;
			for(int j=i-1; j>=0; j--){
				if(j != i-1)	cnt[a[j+1]] ++,mx = max(mx,cnt[a[j+1]]);
				if(calc(j+1,i-1,mx) && (a[j] == a[i] || j == 0))
					f[i] = max(f[i],f[j]+1);
			}
		}
//		for(int i=1; i<=n; i++)	printf("f[%d] = %d\n",i,f[i]);
		int ans = 0,mx = 0;
		for(int i=1; i<=tot; i++)	cnt[i] = 0;
		for(int i=n; i>=1; i--){
			if(i != n)	cnt[a[i+1]]++,mx = max(mx,cnt[a[i+1]]);
			if(calc(i+1,n,mx))	
				ans = max(ans,f[i]);
		}
		printf("%d\n",ans);
		for(int i=1; i<=n; i++)	f[i] = 0;
	}
	return 0;
}

#include<bits/stdc++.h>
#define int long long
#define PII pair<int,int> 
using namespace std;
const int N = 2e5+5;
const int MOD = 998244353;
PII a[N];
bool flag[N];
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int t;
	scanf("%lld",&t);
	while(t--){
		int n,s;
		scanf("%lld%lld",&n,&s);
		for(int i=0; i<=n+5; i++)	flag[i] = false;
		for(int i=1; i<=n; i++)	scanf("%lld",&a[i].second);
		int mx = 0;
		for(int i=1; i<=n; i++){
			scanf("%lld",&a[i].first);
			if(a[i].first != -1){
				flag[a[i].first] = true;
				mx = max(mx,a[i].second - a[i].first);   //可以化成 a[i] - b[i] <= s 
			}
		}
		if(mx > s){
			printf("0\n");
			continue;
		}
		vector<int> t,c;t.clear();c.clear();
		for(int i=1; i<=n; i++)	if(!flag[i])	t.push_back(i);
		for(int i=1; i<=n; i++){
			if(a[i].first == -1){
				c.push_back(t.end() - lower_bound(t.begin(),t.end(),a[i].second - s));
			}
		}
		sort(c.begin(),c.end());
		int ans = 1;
		for(int i=0; i<c.size(); i++)	ans = ((ans * (c[i] - i))%MOD + MOD)%MOD;
		printf("%lld\n",ans);
	}
	return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 105;
const int INF = 1e9+5;
const int MOD = 998244353;
struct node{
	int x,y;
}a[N];
int fac[N],inv[N],dis[N][N],g[N][10],cnt[N],mn[N],tot[10];
bool vis[N];
int mod(int x){
	return x % MOD;
}
int power(int a,int b){
	int res = 1;
	while(b){
		if(b & 1)	res = mod(res * a);
		a = mod(a * a);
		b >>= 1;
	}
	return res;
}
int C(int n,int m){
	return mod(mod(fac[n] * inv[m]) * inv[n - m]);
}
 main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int n;
	scanf("%lld",&n);
	for(int i=1; i<=n; i++){
		scanf("%lld%lld",&a[i].x,&a[i].y);
	}
	//预处理需要用到的东西
	fac[0] = 1;
	for(int i=1; i<=n; i++)	fac[i] = mod(fac[i-1] * i);
	inv[n] = power(fac[n],MOD-2);
	for(int i=n-1; i>=0; i--)	inv[i] = mod(inv[i+1] * (i+1)); 
	//获取两点之间的距离 
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			dis[i][j] = abs(a[i].x - a[j].x) + abs(a[i].y - a[j].y);
		}
	}
	//对于每个点求他的最小距离
	for(int i=1; i<=n; i++){
		mn[i] = INF;
		for(int j=1; j<=n; j++){
			if(i == j)	continue;
			mn[i] = min(mn[i],dis[i][j]);
		}
	} 
	//对于每一个点求最小距离点的点集
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			if(i == j) continue;
			if(dis[i][j] == mn[i]){
				++cnt[i];if(cnt[i] >= 4)	continue;
				g[i][cnt[i]] = j;
			}
		}
	} 
	//求解有多少个大小为 2,3,4 的点集
	for(int i=1; i<=n; i++){
		if(cnt[i] >= 4 || vis[i])	continue;
		//cnt 不计算 i，所以如果超过 4 个显然不合法的
		bool flag = true;
		for(int j=1; j<=cnt[i]; j++){
			int to1 = g[i][j];
			if(mn[to1] != mn[i] || cnt[to1] != cnt[i])	flag = false;
			for(int k=1; k<=cnt[to1]; k++){
				int to2 = g[to1][k];
				if(to2 != i && dis[i][to2] != mn[i])	flag = false;
			}
		}
		if(flag){
			tot[cnt[i] + 1]++;
			vis[i] = true;
			for(int j=1; j<=cnt[i]; j++)	vis[g[i][j]] = true;
		}
	} 
	//暴力枚举 2,3,4 的个数并统计答案
	int ans = 0;
	for(int a2 = 0; a2<=tot[2]; a2++){
		for(int a3=0; a3<=tot[3]; a3++){
			for(int a4=0; a4<=tot[4]; a4++){
				int a1 = n - a2 * 2 - a3 * 3 - a4 * 4;  //点集大小为 1 的点集个数
				ans = mod(ans + mod(mod(mod(mod(C(tot[2],a2) * C(tot[3],a3)) * C(tot[4],a4)) * C(n,a1 + a2 + a3 + a4)) * fac[a1 + a2 + a3 + a4]));
			}
		}
	} 
	printf("%lld\n",ans);
	return 0;
}

#include<bits/stdc++.h>
#define PII pair<int,int>
using namespace std;
const int N = 5e5+5;
int a[N];
bool flag[N];
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int t;
	scanf("%d",&t);
	while(t--){
		int n;
		scanf("%d",&n);
		for(int i=1; i<=n + 5; i++)	flag[i] = false;
		flag[0] = true;
		for(int i=1; i<=n; i++)	scanf("%d",&a[i]);
		int sum = 0;
		for(int i=1; i<=n; i++)	sum += a[i];	
		if(sum > 0){  //正的取负 
			for(int i=1; i<=n; i++){
				if(sum == 0)	break;
				if(a[i] > 0 && !flag[i-1])	flag[i] = 1,sum -= 2;
			}
		}
		else if(sum < 0){  //负的取正 
			for(int i=1; i<=n; i++){
				if(sum == 0)	break;
				if(a[i] < 0 && !flag[i-1])	flag[i] = 1,sum += 2;
			}
		}
		if(sum != 0)	printf("-1\n");
		else{
			vector<PII> v;
			for(int i=1; i<=n; i++){
				if(flag[i + 1])	v.push_back({i,i+1}),i++;
				else	v.push_back({i,i});
			}
			printf("%d\n",v.size());
			for(auto i : v)	printf("%d %d\n",i.first,i.second);
		}
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 7e5+5;
int cnt[N];
int main(){
	int n,x;
	scanf("%d%d",&n,&x);
	for(int i=1; i<=n; i++){
		int a;
		scanf("%d",&a);
		cnt[a]++;
	}
	for(int i=1; i<x; i++){
		cnt[i+1] += cnt[i] / (i + 1);
		cnt[i] %= (i + 1);
		if(cnt[i]){
			printf("No\n");
			return 0;
		}
	}
	printf("Yes\n");
	return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5+5;
const int MOD = 998244353;
int a[N],f[N];
int mod(int x){
	return x % MOD;
}
int power(int a,int b){
	int res = 1;
	while(b){
		if(b & 1)	res = mod(res * a);
		a = mod(a * a);
		b >>= 1;
	}
	return res;
}
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int t ;
	scanf("%lld",&t);
	while(t--){
		int n;
		scanf("%lld",&n);
		for(int i=1; i<=n; i++)	scanf("%lld",&a[i]);
		int cnt1=0,cnt2=0;
		for(int i=1; i<=n; i++)	cnt1 += a[i] == 0;
		for(int i=1; i<=cnt1; i++)	cnt2 += a[i] == 0;
		int inv = power(mod(n * (n - 1) / 2),MOD-2);
		for(int i=cnt2+1; i<=cnt1; i++){
			int tmp = mod((cnt1 - i + 1) * (cnt1 - i + 1));
			f[i] = mod(f[i-1] + power(mod(tmp * inv),MOD-2));
		}
		printf("%lld\n",f[cnt1]);
		for(int i=0; i<=cnt1; i++)	f[i] = 0;
	}
	return 0;
}

#include<bits/stdc++.h>
#define PII pair<int,int> 
using namespace std;
const int N = 4e5+5;
struct edge{
	int nxt,to;
	edge(){}
	edge(int _nxt,int _to){
		nxt = _nxt,to = _to;
	}
}e[2 * N];
int cnt,head[N],dis[N],out[N];
bool vis[N];
void add_edge(int from,int to){
	e[++cnt] = edge(head[from],to);
	head[from] = cnt;
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1; i<=m; i++){
		int u,v;
		scanf("%d%d",&u,&v);
		out[u]++;
		add_edge(v,u);
	}
	memset(dis,0x3f,sizeof(dis));
	priority_queue<PII> q;
	dis[n] = 0;
	q.push({0,n});
	while(!q.empty()){
		int now = q.top().second;q.pop();
		if(vis[now])	continue;
		vis[now] = true;
		for(int i = head[now]; i;i = e[i].nxt){
			int to = e[i].to;
			out[to]--;
			int x = dis[now] + out[to] + 1;
			//+ out[to] 是删去剩下的那些；+ 1 是这个路径长度
			if(dis[to] > x){
				dis[to] = x;
				q.push({-dis[to],to});
			} 
		}
	}
	printf("%d\n",dis[1]);
	return 0;
}

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N = 2e6+5;
struct node{
	int col,l,r;
}a[N];
int b[N],sum[2][N],tmp[N],tot,cnt;
bool cmp(node a,node b){
	if(a.l == b.l)	return a.r < b.r;
	return a.l < b.l;
}
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int t;
	scanf("%lld",&t);
	while(t--){
		tot = 0,cnt = 0;
		int n;
		scanf("%lld",&n);
		for(int i=1; i<=n; i++){
			scanf("%lld%lld%lld",&a[i].col,&a[i].l,&a[i].r);
			a[i].r++;//方便求并集 
			b[++tot] = a[i].l;b[++tot] = a[i].r;
		}
		//离散化 
		sort(b+1,b+tot+1);
		tot = unique(b+1,b+tot+1) - b - 1;
		for(int i=1; i<=n; i++){
			a[i].l = lower_bound(b+1,b+tot+1,a[i].l) - b;
			a[i].r = lower_bound(b+1,b+tot+1,a[i].r) - b;
		}
		//求每个点有什么颜色 
		for(int i=1; i<=n; i++){
			sum[a[i].col][a[i].l]++;
			sum[a[i].col][a[i].r]--;
		}
		for(int i=1; i<=tot; i++){
			sum[0][i] += sum[0][i-1];
			sum[1][i] += sum[1][i-1];
			if(sum[0][i] && sum[1][i]){   //得到关键点 
				tmp[++cnt] = i;
			}
		}
		//获取每个区间的关键点集合 
		for(int i=1; i<=n; i++){
			a[i].l = lower_bound(tmp+1,tmp+cnt+1,a[i].l) - tmp;
			a[i].r = lower_bound(tmp+1,tmp+cnt+1,a[i].r) - tmp - 1;
		}
		sort(a+1,a+n+1,cmp);
		int now_l = 0,now_r = 0; //求区间并集并统计答案 
		int ans = 0;
		for(int i=1; i<=n; i++){
			if(a[i].l > a[i].r)	ans++;
			else if(a[i].l > now_r){
				ans++;
				now_l = a[i].l,now_r = a[i].r;
			}
			else	now_r = max(now_r,a[i].r);
		}
		printf("%lld\n",ans);
		for(int i=0; i<=tot+2; i++)	for(int j=0; j<=1; j++)	sum[j][i] = 0;
	}
	return 0;
}

#include<bits/stdc++.h>
#define int long long
#define PII pair<int,int> 
using namespace std;
const int N = 5e5+5;
int ans = 0,fa[N],sz[N];
vector<PII> e[4 * N],c[N];
int find(int x){
	if(fa[x] ==  x)	return x;
	return find(fa[x]);
}
void modify(int now,int now_l,int now_r,int l,int r,PII w){
	if(l <= now_l && r >= now_r){
		e[now].push_back(w);
		return;
	}
	int mid = (now_l + now_r)>>1;
	if(l <= mid)	modify(now<<1,now_l,mid,l,r,w);
	if(r > mid)		modify(now<<1|1,mid+1,now_r,l,r,w);
}
void solve(int now,int now_l,int now_r){
	vector<int> tmp;
	for(auto i : e[now]){
		int u = find(i.first),v = find(i.second);
		if(sz[u] > sz[v])	swap(u,v);   //按秩合并 
		tmp.push_back(u);fa[u] = v;sz[v] += sz[u];
	}
	if(now_l == now_r){
		for(auto i : c[now_l]){
			ans += sz[find(i.first)] * sz[find(i.second)];
		}
	}
	else{
		int mid = (now_l + now_r)>>1;
		solve(now<<1,now_l,mid);solve(now<<1|1,mid+1,now_r);
	}
	reverse(tmp.begin(),tmp.end());  //撤销操作 
	for(int i : tmp){
		sz[fa[i]] -= sz[i];fa[i] = i; 
	}
}
signed main(){
	int n;
	scanf("%lld",&n);
	for(int i=1; i<n; i++){
		int u,v,col;
		scanf("%lld%lld%lld",&u,&v,&col);
		c[col].push_back({u,v});
		if(col > 1)	modify(1,1,n,1,col-1,{u,v});
		if(col < n)	modify(1,1,n,col+1,n,{u,v});
	}
	for(int i=1; i<=n; i++){
		fa[i] = i;
		sz[i] = 1;
	}
	solve(1,1,n);
	printf("%lld\n",ans);
	return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3005;
int a[N],sum[N],pre[N];
signed main(){
	int n,k;
	scanf("%lld%lld",&n,&k);
	for(int i=1; i<=n; i++){
		scanf("%lld",&a[i]);
		sum[i] = sum[i-1] + a[i];
		pre[i] = pre[i-1] + (a[i] == 0);
	}
	if(abs(sum[n]) > pre[n] * k){
		printf("-1\n");
		return 0;
	}
	int ans = -1;
	for(int l=1; l<=n; l++){
		for(int r=l; r<=n; r++){
			int sum1 = sum[r] - sum[l-1],cnt1 = pre[r] - pre[l-1];
			int sum2 = sum[n] - sum1,cnt2 = pre[n] - cnt1;
			ans = max(ans,min(abs(sum1 + cnt1 * k),abs(sum2 - cnt2 * k)));
			ans = max(ans,min(abs(sum1 - cnt1 * k),abs(sum2 + cnt2 * k)));
		}
	}
	printf("%lld\n",ans + 1);
	return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e6+5;
const int MOD = 998244353;
char s[N];
int all,dp[1<<18][18];
int mod(int x){
	return x % MOD;
}
int power(int a,int b){
	int res = 1;
	while(b){
		if(b & 1)	res = mod(res * a);
		a = mod(a * a);
		b >>= 1;
	}
	return res;
}
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int n;
	scanf("%lld",&n);
	scanf("%s",s+1);
	for(int i=1; i<=n; i++)	all += s[i] == '?';
	for(int i=1; i<=n; i++){  //枚举中心点 
		int l = i + 1,r = i - 1;
		int cnt = 0,sta = 0;
		while(l > 1 && r < n && (s[l-1] == s[r+1] || s[l-1] == '?' || s[r+1] == '?')){
			l--,r++;
			if(s[l] == '?' && s[r] != '?') sta |= (1<<(s[r] - 'a'));
			if(s[l] != '?' && s[r] == '?') sta |= (1<<(s[l] - 'a'));
			if(l != r && (s[l] == '?' || s[r] == '?'))	cnt++;
			for(int j=1; j<=17; j++)	dp[sta][j] = mod(dp[sta][j] + power(j,all-cnt));
		}
		sta = cnt = 0;
		l = i + 1,r = i;
		while(l > 1 && r < n && (s[l-1] == s[r+1] || s[l-1] == '?' || s[r+1] == '?')){
			l--,r++;
			if(s[l] == '?' && s[r] != '?') sta |= (1<<(s[r] - 'a'));
			if(s[l] != '?' && s[r] == '?') sta |= (1<<(s[l] - 'a'));
			if(l != r && (s[l] == '?' || s[r] == '?'))	cnt++;
			for(int j=1; j<=17; j++)	dp[sta][j] = mod(dp[sta][j] + power(j,all-cnt));
		}
	}
	for(int i=1; i<=17; i++){
		for(int j=0; j<(1<<17); j++){
			if((j >> (i-1)) & 1){
				for(int k=1; k<=17; k++)	dp[j][k] = mod(dp[j][k] + dp[j ^ (1<<(i-1))][k]);
			}
		}
	}
	int q;
	scanf("%lld",&q);
	while(q--){
		scanf("%s",s+1);
		int sta = 0;
		int m = strlen(s+1);
		for(int i=1; i<=m; i++)	sta |= (1<<(s[i] - 'a'));
		printf("%lld\n",dp[sta][m]);
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 300;
const int INF = 1e9+5;
int dp[N][N][N],sum[N],a[N];
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	memset(dp,0x3f,sizeof(dp));
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1; i<=n; i++){
		scanf("%d",&a[i]);
		sum[i] = sum[i-1] + a[i];
	}
	dp[0][0][m] = 0;
	for(int i=0; i<n; i++){
		for(int j=0; j<=m; j++){
			int mn = INF;
			for(int k=m; k>=0; k--){
				mn = min(mn,dp[i][j][k]);
				if(j + k <= m)	dp[i+1][j + k][k] = min(dp[i+1][j+k][k],mn + abs(j + k - sum[i+1]));
			}
		}
	}
	int ans = INF;
	for(int i=0; i<=m; i++)	ans = min(ans,dp[n][m][i]);
	printf("%d\n",ans);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 2e6+5;
const int INF = 1e9+5;
int n,a[N],b[N];
bool del[N];
bool check(int mid){
	for(int i=1; i<=n; i++)	del[i] = false;
	for(int i=1; i<=n; i++)	b[i] = a[i];
	b[n+1] = INF;
	for(int k=1; k<=mid; k++){
		int pos = 0;
		for(int i=1; i<=n; i++){
			if(b[i] <= mid - k + 1 && b[i] > b[pos] && !del[i]){
				pos = i;
			}
		}
		if(!pos)	return false;
		del[pos] = true;
		pos = n + 1;
		for(int i=1; i<=n; i++){
			if(b[i] < b[pos] && !del[i]){
				pos = i;
			}
		}
		b[pos] += mid - k + 1;
	}
	return true;
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int t;
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		for(int i=1; i<=n; i++)	scanf("%d",&a[i]);
		int l = 1,r = n;
		int ans = 0;
		while(l <= r){
			int mid = (l + r)>>1;
			if(check(mid)){
				ans = mid;
				l = mid + 1;
			}
			else	r = mid - 1;
		}
		printf("%d\n",ans);
	}
	return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 998244353;
const int N = 3e6+5;
int prime[N],tot;
bool flag[N];
int mod(int x){return ((x % MOD) + MOD)%MOD;}
void pre_work(int mx){
	for(int i=2; i<=mx; i++){
		if(!flag[i])	prime[++tot] = i;
		for(int j=1; j<=tot && i * prime[j] <= mx; j++){
			flag[i * prime[j]] = true;
			if(i % prime[j] == 0)	break;
		}
	}
}
int power(int a,int b){
	int res = 1;
	while(b){
		if(b & 1)	res = mod(res * a);
		a = mod(a * a);
		b >>= 1;
	}
	return res;
}
signed main(){
	pre_work(300000);
	int n,m;
	scanf("%lld%lld",&n,&m);
	int ans = 0;
	int tmp = 1,res = 1;
	__int128 p = 1;
	for(int i=1; i<=n; i++){   //屮，a 的长度 [1,n]，我以为就是 n，挂了好久屮！！！！ 
		p = ((__int128) p * m)%MOD;
		ans = (ans + p)%MOD;
	}
	tmp = 1,res = 1;
	for(int i=1; i<=n; i++){
		if(!flag[i] && tmp <= m)	tmp *= i;
		if(tmp > m)	res = 0;
		else	res = mod(res * mod(m / tmp));
		ans = mod(ans - res);
	}
	printf("%lld\n",ans);
	return 0;
}

#include<bits/stdc++.h>
#define PII pair<int,int> 
using namespace std;
const int N = 1e5+5;
vector<int> v[N];
vector<int> tmp,ans;
vector<PII> c;
int del[4];
int pre[N];
bool flag,vis[N];
void solve(int now,int fath){
	tmp.push_back(now);
	for(int to : v[now]){
		if(to == fath)	continue;
		if((del[1] == now && del[2] == to) || (del[1] == to && del[2] == now))	continue;
		solve(to,now);
	}
}
void find_circle(int now,int fath){
	vis[now] = true;
	for(int i : v[now]){
		if(i == fath)	continue;
		pre[i] = now;
		if(vis[i]){
			c.push_back({i,now});
			while(now != i){
				c.push_back({now,pre[now]});
				now = pre[now];
			}
			flag = true;
			return;
		}
		find_circle(i,now);
		if(flag)	return;
	}
	if(flag)	return;
}
int main(){
//	freopen("travel.in","r",stdin);
//	freopen("travel.out","w",stdout);
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1; i<=m; i++){
		int from,to;
		scanf("%d%d",&from,&to);
		v[from].push_back(to);
		v[to].push_back(from);
	}
	for(int i=1; i<=n; i++)	sort(v[i].begin(),v[i].end());
	if(m == n - 1){
		solve(1,0);
		ans = tmp;
	}
	else{
		find_circle(1,0);
		for(auto i : c){
			del[1] = i.first,del[2] = i.second;
			tmp.clear();
			solve(1,0);
			if(tmp < ans || ans.empty())	ans = tmp;
		}
	}
	for(int i : ans)	printf("%d ",i);
	return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e6+5;
struct edge{
	int nxt,to,val;
	edge(){}
	edge(int _nxt,int _to,int _val){
		nxt = _nxt,to = _to,val = _val;
	}
}e[2 * N];
int tot,head[N],cnt,limit;
void add_edge(int from,int to,int val){
	e[++tot] = edge(head[from],to,val);
	head[from] = tot;
}
int dfs(int now,int fath){
	multiset<int> st;
	for(int i = head[now]; i;i = e[i].nxt){
		int to = e[i].to;
		if(to == fath)	continue;
		int tmp = dfs(to,now) + e[i].val;
		if(tmp >= limit)	cnt++;
		else	st.insert(tmp);
	}
	int mx = 0;  //因为不能重复所以只可以向上传递一个，显然传递最大的是最优的
	while(!st.empty()){
		if(st.size() == 1){
			mx = max(mx,*st.begin());
			break;
		}
		int tmp = *st.begin();
		multiset<int>::iterator it = st.lower_bound(limit - tmp);   //找到最小的符合条件的值
		if(it == st.begin() && st.count(*it) == 1)	++it;
		if(it == st.end()){
			mx = max(mx,tmp);
			st.erase(st.begin());
		} 
		else{
			cnt++;
			st.erase(it);st.erase(st.begin());   //感觉这个先后顺序应该也很重要的 
		}
	} 
	return mx;
}
signed main(){
//	freopen("track.in","r",stdin);
//	freopen("track.out","w",stdout);
	int n,m;
	scanf("%lld%lld",&n,&m);
	for(int i=1; i<n; i++){
		int from,to,val;
		scanf("%lld%lld%lld",&from,&to,&val);
		add_edge(from,to,val);add_edge(to,from,val);
	}
	int l = 0,r = 1e9+5;
	int ans = 0;
	while(l <= r){
		int mid = (l + r)>>1;
		cnt=0;limit = mid;
		dfs(1,0);
		if(cnt >= m){
			ans = mid;
			l = mid + 1;
		}
		else	r = mid - 1;
	}
	printf("%lld\n",ans);
	return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 1e9+7;
int mod(int x){
	return x % MOD;
}
int power(int a,int b){
	int res = 1;
	while(b){
		if(b & 1)	res = mod(res * a);
		a = mod(a * a);
		b >>= 1;
	}
	return res;
}
signed main(){
	int w,n,k;
	scanf("%lld%lld%lld",&w,&n,&k);
	printf("%lld\n",mod(w * power(power(2,k),MOD-2)));
	return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 998244353;
const int N = 2e6+5;
struct edge{
	int nxt,to;
	edge(){}
	edge(int _nxt,int _to){
		nxt = _nxt,to = _to;
	}
}e[2 * N];
int cnt,head[N],deg[N],g[N],f[N];
void add_edge(int from,int to){
	e[++cnt] = edge(head[from],to);
	head[from] = cnt;
}
int mod(int x){
	return x % MOD;
} 
int power(int a,int b){
	int res = 1;
	while(b){
		if(b & 1)	res = mod(res * a);
		a = mod(a * a);
		b >>= 1;
	}
	return res;
}
signed main(){
	int n,m;
	scanf("%lld%lld",&n,&m);
	for(int i=1; i<=m; i++){
		int from,to;
		scanf("%lld%lld",&from,&to);
		add_edge(to,from);
		deg[from]++;
	}
	queue<int> q;
	for(int i=1; i<=n; i++){
		g[i] = 1,f[i] = 0;
		if(deg[i] == 0){
			q.push(i);
		}
	}
	while(!q.empty()){
		int now = q.front();q.pop();
		for(int i = head[now]; i;i = e[i].nxt){
			int to = e[i].to;
			f[to] = mod(f[to] + f[now] + g[now]);
			g[to] = mod(g[to] + g[now]);
			deg[to]--;
			if(deg[to] == 0)	q.push(to);
		}
	}
	int sum1 = 0,sum2 = 0;
	for(int i=1; i<=n; i++){
		sum1 = mod(sum1 + f[i]),sum2 = mod(sum2 + g[i]);
	}
	printf("%lld\n",mod(sum1 * power(sum2,MOD-2)));
	return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e7+5;
int a[N];
signed main(){
	int n,A,B,C;
	scanf("%lld%lld%lld%lld%lld", &n, &A, &B, &C, a + 1);
	for (int i = 2; i <= n; i++)
		a[i] = ((long long) a[i - 1] * A + B) % 100000001;
	for (int i = 1; i <= n; i++)
		a[i] = a[i] % C + 1;
	double ans = 0;
	for(int i=2; i<=n; i++)	ans += 1.0 / (max(a[i],a[i-1]));
	ans += 1.0 / max(a[1],a[n]);
	printf("%.3f",ans);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+5;
double f[N];
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		int n;scanf("%d",&n);
		f[1] = 1;
		for(int i=1; i<n; i++)	f[i+1] = f[i] + 1.0 / ( 1.0 * (n-i) / n);
		printf("%.2f\n",f[n]);
	}
	return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e6+5;
const int MOD = 998244353;
struct node{
	int x,y,val;
}a[N];
int f[N],cnt,A[N],B[N],C[N],D[N],E[N];
bool cmp(node a,node b){
	return a.val < b.val;
}
int mod(int x){
	return ((x % MOD)+MOD)%MOD;
}
int power(int a,int b){
	int res = 1;
	while(b){
		if(b & 1)	res = mod(res * a);
		a = mod(a * a);
		b >>= 1;
	}
	return res;
}
signed main(){
	int n,m;
	scanf("%lld%lld",&n,&m);
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			cnt++;
			a[cnt].x = i,a[cnt].y = j;
			scanf("%lld",&a[cnt].val);
		}
	}
	sort(a+1,a+cnt+1,cmp);
	int lst = 0;
	for(int i=1; i<=cnt; i++){
		if(a[i].val != a[i-1].val)	lst = i-1;
		int tmp = mod(lst * (a[i].x * a[i].x + a[i].y * a[i].y) + A[lst] + C[lst]);
		tmp = mod(tmp - 2 * a[i].x * B[lst] - 2 * a[i].y * D[lst]);
		f[i] = mod((tmp + E[lst]) * power(lst,MOD-2));
		A[i] = mod(A[i-1] + a[i].x * a[i].x);
		B[i] = mod(B[i-1] + a[i].x);
		C[i] = mod(C[i-1] + a[i].y * a[i].y);
		D[i] = mod(D[i-1] + a[i].y);
		E[i] = mod(E[i-1] + f[i]);
	}
	int x,y;
	scanf("%lld%lld",&x,&y);
	for(int i=1; i<=cnt; i++){
		if(a[i].x ==x && a[i].y == y){
			printf("%lld\n",f[i]);
			return 0;
		}
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 2e6+5;
struct edge{
	int nxt,to,val;
	edge(){}
	edge(int _nxt,int _to,int _val){
		nxt = _nxt,to = _to,val = _val;
	}
}e[N];
bool vis[N];
double f[N];
int cnt,head[N],deg[N];
void add_edge(int from,int to,int val){
	e[++cnt] = edge(head[from],to,val);
	head[from] = cnt;
}
double dp(int now){
	if(vis[now])	return f[now];
	double tmp = 0;vis[now] = true;
	for(int i = head[now]; i; i =e[i].nxt){
		int to = e[i].to;
		tmp += 1.0 * (e[i].val + dp(to)) / deg[now];
	}
	return f[now] = tmp;
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1; i<=m; i++){
		int from,to,val;
		scanf("%d%d%d",&from,&to,&val);
		add_edge(from,to,val);
		deg[from]++;
	}
	printf("%.2f\n",dp(1));
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 2e3+5;
const double INF = 100000000000000000.0;
int dis[N][N];
double k[N],dp[N][N][2];
int c[N],d[N];
void chkmn(double &a,double b){
	if(a > b)	a = b;
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	memset(dis,0x3f,sizeof(dis));
	int n,m,v,e;
	scanf("%d%d%d%d",&n,&m,&v,&e);
	for(int i=1; i<=n; i++)	scanf("%d",&c[i]);
	for(int i=1; i<=n; i++)	scanf("%d",&d[i]);
	for(int i=1; i<=n; i++)	scanf("%lf",&k[i]);
	for(int i=1; i<=e; i++){
		int from,to;
		int val;
		scanf("%d%d%d",&from,&to,&val);
		dis[from][to] = min(dis[from][to],val);
		dis[to][from] = min(dis[to][from],val); 
	}
	for(int k=1; k<=v; k++){
		for(int i=1; i<=v; i++){
			for(int j=1; j<=v; j++){
				dis[i][j] = min(dis[i][j],dis[i][k] + dis[k][j]);
			}
		}
		dis[k][k] = dis[k][0] = dis[0][k] = 0;
	}
	for(int i=0; i<=n; i++){
		for(int j=0; j<=m; j++){
			dp[i][j][0] = dp[i][j][1] = INF;
		}
	}
	dp[1][0][0] = dp[1][1][1] = 0;
	for(int i=2; i<=n; i++){
		for(int j=0; j<=min(i,m); j++){
			chkmn(dp[i][j][0],min(dp[i-1][j][0] + dis[c[i-1]][c[i]],dp[i-1][j][1] + k[i-1] * dis[d[i-1]][c[i]] + (1 - k[i-1]) * dis[c[i-1]][c[i]]));
			if(j != 0) chkmn(dp[i][j][1],min(dp[i-1][j-1][0] + k[i] * dis[c[i-1]][d[i]] + (1 - k[i]) * dis[c[i-1]][c[i]],dp[i-1][j-1][1] + k[i] * (k[i-1] * dis[d[i-1]][d[i]] + (1 - k[i-1]) * dis[c[i-1]][d[i]]) + (1 - k[i]) * (k[i-1] * dis[c[i]][d[i-1]] + (1 - k[i-1]) * dis[c[i]][c[i-1]])));
		}
	}
	double ans = INF;
	for(int i=0; i<=m; i++){
		chkmn(ans,min(dp[n][i][0],dp[n][i][1]));
	}
	printf("%.2f",ans);
	return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 105;
const int MOD = 998244353;
int a[N],pre[N],suf[N],c[N][N];
int mod(int x){
	return ((x%MOD)+MOD)%MOD;
}
int power(int a,int b){
	int res = 1;
	while(b){
		if(b & 1)	res = mod(res * a);
		a = mod(a * a);
		b >>= 1;
	}
	return res;
}
signed main(){
	int n;
	scanf("%lld",&n);
	for(int i=1; i<=n; i++)	scanf("%lld",&a[i]);
	for(int i=1; i<=n; i++){
		for(int j=i-1; j>=1; j--){
			if(a[j] > a[i]){
				pre[i] = i - j;
				break;
			}
		}
		for(int j=i+1; j<=n; j++){
			if(a[j] > a[i]){
				suf[i] = j - i;
				break;
			}
		}
	}
	c[0][0] = 1;
	for(int i=1; i<=n; i++){
		c[i][0] = 1;
		for(int j=1; j<=i; j++){
			c[i][j] = mod(c[i-1][j] + c[i-1][j-1]);
		}
	}
	for(int i=1; i<=n; i++){
		int ans = 0;
		for(int j=1; j<=n-1; j++){
			int tmp = 1;
			if(pre[i] && j - pre[i] >= 0)	tmp = mod(tmp - c[n - 1 - pre[i]][j - pre[i]] * power(c[n-1][j],MOD-2));
			if(suf[i] && j - suf[i] >= 0)	tmp = mod(tmp - c[n - 1 - suf[i]][j - suf[i]] * power(c[n-1][j],MOD-2));
			if(pre[i] && suf[i] && j - pre[i] - suf[i] >= 0)	tmp = mod(tmp + c[n - 1 - pre[i] - suf[i]][j - pre[i] - suf[i]] * power(c[n-1][j],MOD-2));
			ans = mod(ans + tmp);		
		}
		printf("%lld ",ans);
	}
	return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3005;
struct edge{
	int nxt,to;
	edge(){}
	edge(int _nxt,int _to){
		nxt = _nxt,to = _to;
	}
}e[N * 10];
bool tmp[N][N],vis[N];
int n,m,k,cnt,head[N],a[N][8],val[N];
void add_edge(int from,int to){
	e[++cnt] = edge(head[from],to);
	head[from] = cnt;
}
void solve(int s,int *a){
	memset(vis,false,sizeof(vis));
	queue<pair<int,int> > q;
	q.push({s,0});
	while(!q.empty()){
		int now = q.front().first;int d = q.front().second;q.pop();
		if(d > k)	continue;
		if(vis[now])	continue;
		vis[now] = true;
		for(int i = head[now]; i;i=e[i].nxt){
			int to = e[i].to;
			if(vis[to])	continue;
			if(d + 1 <= k)	q.push({to,d + 1});
			tmp[s][to] = true;tmp[to][s] = true;
			if(tmp[to][1] || tmp[1][to]){
				for(int j=1; j<=3; j++){   //更新答案 
					if(val[to] > val[a[j]] && to != a[1] && to != a[2] && to != a[3]){
						a[j+3] = a[j+2];a[j+2] = a[j+1];a[j+1] = a[j];
						a[j] = to;
						break;
					}
				}
			}
		}
	}
}
bool chk(int a,int b,int c,int d){
	if(a == b || a == c || a == d)	return false;
	if(b == c || b == d)	return false;
	if(c == d)	return false;
	return true;
}
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	scanf("%lld%lld%lld",&n,&m,&k);
	for(int i=2; i<=n; i++)	scanf("%lld",&val[i]);
	for(int i=1; i<=m; i++){
		int from,to;
		scanf("%lld%lld",&from,&to);
		add_edge(from,to);add_edge(to,from);
	}
	for(int i=1; i<=n; i++){  //对于每一个点，寻找最优的三个点，顺路求出所有符合条件的点 
		solve(i,a[i]);
	}
	int ans = 0;
	for(int i=2; i<=n; i++){   //枚举 B , C 
		for(int j=2; j<=n; j++){
			for(int l=1; l<=3; l++){
				if(!a[i][l])	continue;
				for(int r=1; r<=3; r++){
					if(!a[j][r])	continue;
					//这就相当于确定了四个值是什么了：A:a[l] B:i C:j D:a[r]
					int A = a[i][l],B = i,C = j,D = a[j][r]; 
					if(tmp[i][j] && chk(A,B,C,D)){
						ans = max(ans,val[A] + val[B] + val[C] + val[D]);
						break;
					}
				}
			}
		}
	}
	printf("%lld\n",ans);
	return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N =1e5+5;
const int INF = 1e18+5;
struct node{
	int mx_z,mn_z,mx_f,mn_f;
	bool ze;
	node(){
		mx_z = mn_z = mx_f = mn_f = 0;
		ze = false;
	}
};
node merge(node a,node b){   //区间合并 
	node c;
	c.mn_f = min(a.mn_f,b.mn_f);
	c.mx_z = max(a.mx_z,b.mx_z);
	c.ze = a.ze | b.ze;
	if(a.mn_z == 0)	c.mn_z = b.mn_z;
	else if(b.mn_z == 0)	c.mn_z = a.mn_z;
	else	c.mn_z = min(a.mn_z,b.mn_z);
	if(a.mx_f == 0)	c.mx_f = b.mx_f;
	else if(b.mx_f == 0)	c.mx_f = a.mx_f;
	else	c.mx_f = max(a.mx_f,b.mx_f);
	return c;
}
struct Tree{
	node tr[4 * N];
	void pushup(int now){
		tr[now] = merge(tr[now<<1],tr[now<<1|1]);
	}
	void build(int now,int now_l,int now_r,int *a){
		if(now_l == now_r){
			if(a[now_l] > 0)	tr[now].mx_z = tr[now].mn_z = a[now_l];
			if(a[now_l] < 0)	tr[now].mx_f = tr[now].mn_f = a[now_l];
			if(a[now_l] == 0)	tr[now].ze = true;
			return;
		}
		int mid = (now_l + now_r)>>1;
		build(now<<1,now_l,mid,a);build(now<<1|1,mid+1,now_r,a);
		pushup(now);
	}
	node query(int now,int now_l,int now_r,int l,int r){
		if(l <= now_l && r >= now_r)	return tr[now];
		int mid = (now_l + now_r)>>1;
		if(r <= mid)	return query(now<<1,now_l,mid,l,r);
		else if(l >= mid+1)	return query(now<<1|1,mid+1,now_r,l,r);
		else	return merge(query(now<<1,now_l,mid,l,r),query(now<<1|1,mid+1,now_r,l,r));
	}
}A,B;
int n,m,q,a[N],b[N];
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	scanf("%lld%lld%lld",&n,&m,&q);
	for(int i=1; i<=n; i++)	scanf("%lld",&a[i]);
	A.build(1,1,n,a);
	for(int i=1; i<=m; i++)	scanf("%lld",&a[i]);
	B.build(1,1,m,a);
	for(int i=1; i<=q; i++){
		int l1,r1,l2,r2;
		scanf("%lld%lld%lld%lld",&l1,&r1,&l2,&r2);
		node l = A.query(1,1,n,l1,r1);
		node r = B.query(1,1,m,l2,r2);
		a[1] = l.mx_z;a[2] = l.mx_f;a[3] = l.mn_z;a[4] = l.mn_f;
		b[1] = r.mx_z;b[2] = r.mx_f;b[3] = r.mn_z;b[4] = r.mn_f;
		int ans = -INF;
		for(int j=1; j<=4; j++){
			if(a[j] == 0)	continue;
			int tmp = r.ze ? 0 : INF;
			for(int k=1; k<=4; k++){
				if(b[k] != 0){
					tmp = min(tmp,a[j] * b[k]);
				}
			}
			if(tmp != INF)	ans = max(ans,tmp);
		}
		if(ans < 0 && l.ze)	ans = 0;
		printf("%lld\n",ans);
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 2e6+5;
double f[N];
double power(double a,int b){
	double res = 1;
	while(b){
		if(b & 1)	res = res * a;
		a = a * a;
		b >>= 1;
	}
	return res;
}
int main(){
	int m,n;
	scanf("%d%d",&m,&n);
	//设 f[i] 表示最大值为 i 的概率
	for(int i=1; i<=m; i++){
		f[i] = power(1.0 * i/m,n) - power(1.0 * (i-1)/m,n);
	} 
	double ans = 0;
	for(int i=1; i<=m; i++)	ans = ans + f[i] * i;
	printf("%.7f",ans);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
int a[10];
int main(){
	int n = 0;
	for(int i=1; i<=7; i++)	scanf("%d",&a[i]),n+=a[i];
	if(n < 7){
		printf("0.000\n");
		return 0;
	}
	double ans = 1;
	for(int i=1; i<=7; i++)	ans = 1.0 * ans * a[i] / (n - i + 1) * i;
	ans = 1.0 * ans * (n - 6);
	printf("%.3f",ans);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
double dp[1<<19];
double a[20][20];
int main(){
	int n;
	scanf("%d",&n);
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			scanf("%lf",&a[i][j]);
		}
	}
	dp[(1<<n)-1] = 1;
	for(int i = (1<<n)-1; i>=0; i--){
		int cnt = __builtin_popcount(i);
		for(int l=0; l<n; l++){
			for(int r=l+1; r<n; r++){
				if(((i>>l)&1) && ((i>>r)&1) && l != r && cnt > 1){
					dp[i ^ (1<<l)] += 1.0 * dp[i] * a[r][l] / (cnt * (cnt - 1) / 2.0);
					dp[i ^ (1<<r)] += 1.0 * dp[i] * a[l][r] / (cnt * (cnt - 1) / 2.0);
				}
			}
		}
	}
	for(int i=0; i<n; i++){
		printf("%.6f ",dp[1<<i]);
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
double x[N],x2[N];
int main(){
	int n;
	scanf("%d",&n);
	x[n] = x2[n] = 0;
	for(int i=n-1; i>=0; i--){
		x[i] = x[i+1] + 1.0 * n / (n - i);
		x2[i] = 1.0 * i / (n-i) * (2 * x[i] + 1) + x2[i+1] + 2.0 * x[i+1] + 1;
	}
	printf("%.2f\n",(x[0] + x2[0]) / 2.0);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+5;
double f[250][250],p[N],d[N];
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		memset(f,0,sizeof(f));
		int n,r;
		scanf("%d%d",&n,&r);
		for(int i=1; i<=n; i++)	scanf("%lf%lf",&p[i],&d[i]);
		f[0][0] = 1;double ans = 0;
		for(int i=0; i<n; i++){
			for(int j=0; j<=min(i,r); j++){
				double tmp = pow(1-p[i+1],r-j);  //i+1 在剩下几轮都不会被选择的概率。 
				f[i+1][j] += f[i][j] * tmp;
				if(j < r)	f[i+1][j+1] += f[i][j] * (1 - tmp),ans += f[i][j] * (1 - tmp) * d[i+1];
			}
		}
		printf("%.10f\n",ans);
	}
	return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e6+5;
const int MOD = 100003;
int f[N],a[N],cnt = 0;
int mod(int x){
	return x % MOD;
}
int power(int a,int b){
	int res = 1;
	while(b){
		if(b & 1) res = mod(res * a);
		a = mod(a * a);
		b >>= 1;
	} 
	return res;
}
signed main(){
	int n,k; 
	scanf("%lld%lld",&n,&k); 
	for(int i=1; i<=n; i++)	scanf("%lld",&a[i]); 
	for(int i=n; i>=1; i--){  //倒序操作，寻找必须操作的个数 
		if(a[i]){
			cnt++;
			for(int j=1; j*j<=i; j++){
				if(i % j == 0){
					a[j] ^= 1;
					if(j * j != i)	a[i / j] ^= 1;
				}
			}
		}
	}
	for(int i=n; i>=1; i--){   //为什么不从 cnt 开始？因为显然 f[cnt+1] != 0 
		int tmp = mod((n - i) * f[i+1]);
		f[i] = mod(mod(n + tmp) * power(i,MOD-2));
	}
	int ans = 0;
	if(cnt <= k)	ans = cnt;  //需要的数量 <=k 显然直接搞就好了 
	else{
		for(int i=cnt; i>k; i--)	ans = mod(ans + f[i]);  //不然一个个移动直到移动到 k 
		ans = mod(ans + k);
	}
	for(int i=1; i<=n; i++)	ans = mod(ans * i);
	printf("%lld\n",ans);
	return 0;
}