#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e4 + 7;
const double pi = acos(-1);
const int mod = 998244353;
const double eps = 1e-8;
int ab[maxn*2],ac[maxn*2],bc[maxn*2];
int check(char x,char y){
	if(x == '?' || y == '?' || x == y) return 1;
	return 0;
}
void init(string a,string b,int n,int m,int *vis){
	for(int i = 0;i < n;i++){
		for(int j = 0;j < m;j++){
			// +maxn是为了吧反着可能出现负数的情况也记录 
			if(!check(a[i],b[j])) vis[i-j+maxn] = 1;
		}
	}
	return;
}
int main(){
	int M = 2e3;
//	ios::sync_with_stdio(false);
//	cin.tie(0),cout.tie(0);
	string a,b,c;
	cin >> a >> b >> c;
	int la = a.size(),lb = b.size(),lc = c.size();
	//预处理两两字符串之间可以重合的位置 
	init(a,b,la,lb,ab);
	init(a,c,la,lc,ac);
	init(b,c,lb,lc,bc);
	//暴力跑每一处循环 
	int ans = 3 * M;
	//i枚举ab之间的间隔 
	for(int i = -(M<<1);i <= (M<<1);i++){
		//j枚举ac 
		for(int j = -(M<<1);j <= (M<<1);j++){			 
			if(!ab[i+maxn] && !ac[j+maxn] && !bc[j-i+maxn]){
				int l = min(0,min(i,j));
				int r = max(la,max(lb+i,lc+j));
				ans = min(ans,r-l);
			}
		}
	}
	cout << ans << endl;
	return 0;
}
### Prompt

Please create a solution in Cpp to the following problem:

Snuke has a string s. From this string, Anuke, Bnuke, and Cnuke obtained strings a, b, and c, respectively, as follows:

* Choose a non-empty (contiguous) substring of s (possibly s itself). Then, replace some characters (possibly all or none) in it with `?`s.



For example, if s is `mississippi`, we can choose the substring `ssissip` and replace its 1-st and 3-rd characters with `?` to obtain `?s?ssip`.

You are given the strings a, b, and c. Find the minimum possible length of s.

Constraints

* 1 \leq |a|, |b|, |c| \leq 2000
* a, b, and c consists of lowercase English letters and `?`s.

Input

Input is given from Standard Input in the following format:


a
b
c


Output

Print the minimum possible length of s.

Examples

Input

a?c
der
cod


Output

7


Input

atcoder
atcoder
???????


Output

7

### Response

```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e4 + 7;
const double pi = acos(-1);
const int mod = 998244353;
const double eps = 1e-8;
int ab[maxn*2],ac[maxn*2],bc[maxn*2];
int check(char x,char y){
	if(x == '?' || y == '?' || x == y) return 1;
	return 0;
}
void init(string a,string b,int n,int m,int *vis){
	for(int i = 0;i < n;i++){
		for(int j = 0;j < m;j++){
			// +maxn是为了吧反着可能出现负数的情况也记录 
			if(!check(a[i],b[j])) vis[i-j+maxn] = 1;
		}
	}
	return;
}
int main(){
	int M = 2e3;
//	ios::sync_with_stdio(false);
//	cin.tie(0),cout.tie(0);
	string a,b,c;
	cin >> a >> b >> c;
	int la = a.size(),lb = b.size(),lc = c.size();
	//预处理两两字符串之间可以重合的位置 
	init(a,b,la,lb,ab);
	init(a,c,la,lc,ac);
	init(b,c,lb,lc,bc);
	//暴力跑每一处循环 
	int ans = 3 * M;
	//i枚举ab之间的间隔 
	for(int i = -(M<<1);i <= (M<<1);i++){
		//j枚举ac 
		for(int j = -(M<<1);j <= (M<<1);j++){			 
			if(!ab[i+maxn] && !ac[j+maxn] && !bc[j-i+maxn]){
				int l = min(0,min(i,j));
				int r = max(la,max(lb+i,lc+j));
				ans = min(ans,r-l);
			}
		}
	}
	cout << ans << endl;
	return 0;
}
```