//#include<iostream> //1002
//#include<string>
//using namespace std;
//int main(){
// string str;
// int sum=0;
// int j=0;
// string out[10]={
//"ling",
//"yi",
//"er",
//"san",
//"si",
//"wu",
//"liu",
//"qi",
//"ba",
//"jiu"
// };
// int ans[3];
// cin>>str;
// for(int i=0;i<str.size();i++){
// sum+=str[i]-'0';
// }
// for(int i=0;i<3;i++) ans[i]=0;
// int s=sum;
// while(s!=0){
// ans[j++]=s%10;
// s/=10;
// }
//
// if(sum>99) cout<<out[ans[2]]<<" "<<out[ans[1]]<<" "<<out[ans[0]]<<endl;
// else if(sum>9) cout<<out[ans[1]]<<" "<<out[ans[0]]<<endl;
// else if(sum>0) cout<<out[ans[0]]<<endl;
// else cout<<"ling"<<endl;
// system("pause");
// }
//#include<iostream> //1003
//#include<string>
//#include<map>
//using namespace std;
//int main(){
// int n;
// map<char,int> m;
// cin>>n;
// while(n--){
// string str;
// int p=0,t=0;
// cin>>str;
// for(int i=0;i<str.size();i++){
// m[str[i]]++;
// if(str[i]=='P') p=i;
// if(str[i]=='T') t=i;
// }
// if(m['P']==1&&m['T']==1&&m['A']!=0&&m.size()==3&&t-p!=1&&p*(t-p-1)==str.size()-t-1) cout<<"YES"<<endl;
// else cout<<"NO"<<endl;
// }
//}
//#include<iostream>
//#include<string>
//#include<algorithm>
//using namespace std;
//struct Student
//{
// string name;
// string id;
// int mark;
// bool operator < (const Student &A) const{
// return mark<A.mark;
// }
//}student[100];
//int main(){
// int n,i=0;
// cin>>n;
// while(n--){
// cin>>student[i].name>>student[i].id>>student[i].mark;
// i++;
// }
// sort(student,student+i);
// cout<<student[i-1].name<<" "<<student[i-1].id<<endl;
// cout<<student[0].name<<" "<<student[0].id<<endl;
//}
//#include<iostream> //这题用map更简单
//#define N 10000
//using namespace std;
//int main(){
// int n;
// int h[N],idx;
// cin>>n;
// for(int i=0;i<N;i++) h[i]=0;
// while(n--){
// cin>>idx;
// h[idx]=1;
// }
// for(int i=N;i>=2;i--){
// if(h[i]==1){
// int temp=i;
// while(temp!=1){
// if(temp%2==0){
// temp/=2;
// h[temp]=0;
// }
// else{
// temp=(3*temp+1)/2;
// h[temp]=0;
// }
// }
// }
// }
// int count=0;
// for(int i=N-1;i>=2;i--){
// if(h[i]==1){
// count++;
// if(count>1) cout<<" ";
// cout<<i;
// }
// }
//}
//#include<iostream>
//#include<string>
//using namespace std;
//int main(){
// string s;
// cin>>s;
// if(s.size()==3){
// for(int i=s[0]-'0';i>0;i--) cout<<"B";
// for(int i=s[1]-'0';i>0;i--) cout<<"S";
// for(int i=0;i<s[2]-'0';i++) cout<<i+1;
// }else if(s.size()==2){
// for(int i=s[0]-'0';i>0;i--) cout<<"S";
// for(int i=0;i<s[1]-'0';i++) cout<<i+1;
// }else {
// for(int i=0;i<s[0]-'0';i++) cout<<i+1;
// }
//}
//#include<iostream>
//#define N 100000
//using namespace std;
//int prime[N],flag=0;
//bool temp[N]={false};
//void init(){
// for(int i=2;i<N;i++){
// if(temp[i]==true) continue;
// prime[flag++]=i;
// for(int j=i*i;j<N;j+=i)
// temp[j]=true;
// }
//}
//int main(){
// int n,count=0;
// cin>>n;
// init();
// for(int i=0;prime[i+1]<=n;i++){
// if(prime[i+1]-prime[i]==2) count++;
// }
// cout<<count<<endl;
//}
//#include<iostream>
//using namespace std;
//void fZ(int A[],int low,int top){
///*int mid=(low+top)/2;
//for(int i=low;i<=mid;i++){
// int tmp=A[i];
// A[i]=A[top];
// A[top]=tmp;
// top--;
//}*/
//while(low<top){
// int tmp=A[low];
// A[low]=A[top];
// A[top]=tmp;
// low++;
// top--;
// }
//}
//int main(){
//int in[100],n,m,count=0;
//cin>>n>>m;
//while(n--) cin>>in[count++];
//m=m%count;
//fZ(in,0,count-1);
//fZ(in,0,m-1);
//fZ(in,m,count-1);
//int sum=0;
//for(int i=0;i<count;i++){
// if(sum++>0) cout<<" ";
// cout<<in[i];
//}
//system("pause");
//}
//#include<iostream>
//#include<string>
//using namespace std;
//int main(){
// string s[100];
// int i=0,count=0;
// while(cin>>s[i]) i++;
// for(int j=i-1;j>=0;j--){
// if(count++>0)cout<<" ";
// cout<<s[j];
// }
//}
//#include<iostream>
//using namespace std;
//int main(){
// int a,b,count=0;
// while(cin>>a>>b){
// if(count++>0)cout<<" ";
// if(b==0)cout<<"0 0";
// else cout<<a*b<<" "<<b-1;
// }
//}
//#include<iostream>
//using namespace std;
//int main(){
// int n,i=1;
// long long a,b,c;
// cin>>n;
// while(n--){
// cin>>a>>b>>c;
// if(a+b>c) cout<<"Case #"<<i++<<": true"<<endl;
// else cout<<"Case #"<<i++<<": false"<<endl;
// }
//}
//#include<iostream>
//#include<string>
//using namespace std;
//int main(){
// string a,b,c,d;
// cin>>a>>b>>c>>d;
// int flag=1;
// string data[7]={"MON","TUE","WED","THU","FRI","SAT","SUN"};
// for(int i=0;i<a.size(),i<b.size();i++){
// if(flag){
// if(a[i]==b[i]&&a[i]-'A'>=0&&a[i]-'A'<=13){
// cout<<data[a[i]-'A']<< " ";
// flag=0;
// }
// }
// else if(a[i]==b[i]){
// if(a[i]-'A'>=0&&a[i]-'A'<=13){
// printf("%02d:",a[i]-'A'+10);
// break;
// }
// if(a[i]-'0'>=0&&a[i]-'0'<=9){
// printf("%02d:",a[i]-'0');
// break;
// }
// }
// }
// for(int i=0;i<c.size(),i<d.size();i++){
// if(c[i]==d[i]&&((c[i]-'a'>=0&&c[i]-'a'<=26)||(c[i]-'A'>=0&&c[i]-'A'<=26))) {
// printf("%02d",i);
// break;
// }
// }
// system("pause");
//}
//#include<iostream>
//#include<algorithm>
//#include<string>
//using namespace std;
//struct Student
//{
// string id;
// int d;
// int c;
// bool operator< (const Student &A) const{
// if(d+c==A.d+A.c){
// if(d==A.d) return id<A.id;
// else return d>A.d;
// }else return d+c>A.d+A.c;
// }
//}first[100000],second[100000],third[100000],late[100000];
//
//int main(){
// int n,l,h,m=0;
// string id;
// int d,c;
// int fi=0,se=0,th=0,la=0;
// cin>>n>>l>>h;
// while(n--){
// cin>>id;
// cin>>d>>c;
// if(d>=l&&c>=l){
// m++;
// if(d>=h&&c>=h){
// first[fi].id=id;
// first[fi].d=d;
// first[fi].c=c;
// fi++;
// }
// else if(d>=h&&c<h){
// second[se].id=id;
// second[se].d=d;
// second[se].c=c;
// se++;
// }
// else if(d<h&&c<h&&d>c){
// third[th].id=id;
// third[th].d=d;
// third[th].c=c;
// th++;
// }else{
// late[la].id=id;
// late[la].d=d;
// late[la].c=c;
// la++;
// }
// }
// }
// sort(first,first+fi);
// sort(second,second+se);
// sort(third,third+th);
// sort(late,late+la);
// cout<<m<<endl;
// for(int i=0;i<fi;i++){
// cout<<first[i].id<<" "<<first[i].d<<" "<<first[i].c<<endl;
// }
// for(int i=0;i<se;i++){
// cout<<second[i].id<<" "<<second[i].d<<" "<<second[i].c<<endl;
// }
// for(int i=0;i<th;i++){
// cout<<third[i].id<<" "<<third[i].d<<" "<<third[i].c<<endl;
// }
// for(int i=0;i<la;i++){
// cout<<late[i].id<<" "<<late[i].d<<" "<<late[i].c<<endl;
// }
// system("pause");
//}
//#include<iostream>
//#include<string>
//using namespace std;
//int main(){
// string a;
// int b,q,r=0;
// cin>>a>>b;
// int flag=1;
// if(a.size==1){
// q=(a[0]-'0')/b;
// r=(a[0]-'0')%b;
// cout<<q<<" "<<r;
// return 0;
//
// }
// for(int i=0;i<a.size();i++){
// if(flag){
// q=(a[i]-'0'+10*r)/b;
// r=(a[i]-'0'+10*r)%b;
// if(q!=0){
// flag=0;
// cout<<q;
// }
// }else{
// q=(a[i]-'0'+10*r)/b;
// r=(a[i]-'0'+10*r)%b;
// cout<<q;
// }
// }
// cout<<" "<<r;
// system("pause");
//}
//#include<iostream>
//using namespace std;
//int main(){
// int n;
// int cc=0,cj=0,cb=0;
// int jj=0,jc=0,jb=0;
// int bb=0,bj=0,bc=0;
// char a,b;
// cin>>n;
// while(n--){
// cin>>a>>b;
// if(a=='C'&&b=='C') cc++;
// if(a=='C'&&b=='J') cj++;
// if(a=='C'&&b=='B') cb++;
// if(a=='B'&&b=='J') bj++;
// if(a=='B'&&b=='B') bb++;
// if(a=='B'&&b=='C') bc++;
// if(a=='J'&&b=='J') jj++;
// if(a=='J'&&b=='C') jc++;
// if(a=='J'&&b=='B') jb++;
// }
// cout<<cj+jb+bc<<" "<<jj+bb+cc<<" "<<jc+bj+cb<<endl;
// cout<<jc+bj+cb<<" "<<jj+bb+cc<<" "<<cj+jb+bc<<endl;
// if(bc>=cj&&bc>=jb) cout<<"B ";
// if(cj>bc&&cj>=jb) cout<<"C ";
// if(jb>cj&&jb>bc) cout<<"J ";
// if(cb>=jc&&cb>=bj) cout<<"B";
// if(jc>cb&&jc>=bj) cout<<"C";
// if(bj>jc&&bj>cb) cout<<"J";
// system("pause");
//}
//#include<iostream>
//#include<algorithm>
//using namespace std;
//int main(){
// int n;
// cin>>n;
// do{
// int ans[4]={0},count=0,temp;
// temp=n;
// while(n!=0){
// ans[count++]=n%10;
// n/=10;
// }
// sort(ans,ans+4);
// if(ans[0]==ans[1]&&ans[0]==ans[2]&&ans[0]==ans[3]){
// printf("%04d - %04d = %04d\n",temp,temp,temp-temp);
// return 0;
// }
// int n1=0,n2=0,q=1;
// for(int i=0;i<4;i++){
// n1+=ans[i]*q;
// n2+=ans[3-i]*q;
// q=q*10;
// }
// printf("%04d - %04d = %04d\n",n1,n2,n1-n2);
// n=n1-n2;
//
// }while(n!=6174);
// system("pause");
//}
//#include<iostream>
//#include<algorithm>
//#include<vector>
//using namespace std;
//struct Yue{
// double remain;
// double price;
// bool operator < (const Yue A) const{
// return price/remain>A.price/A.remain;//升序
// }
//}yue[1000];
//int main(){
// int n,d,count,tmp=0;
// double money=0;
// cin>>n>>d;
// count=n;
// while(count--){
// cin>>yue[tmp++].remain;
// }
// count=n;
// tmp=0;
// while(count--){
// cin>>yue[tmp++].price;
// }
// sort(yue,yue+n);
// for(int j=0;j<n;j++){
// if(d>yue[j].remain){
// d-=yue[j].remain;
// money+=yue[j].price;
// }else{
// money+=yue[j].price/yue[j].remain*d;
// break;
// }
// }
// printf("%.2lf",money);
//}
//#include<iostream>
//#include<algorithm>
//using namespace std;
//long a[100000]={0};
//int main(){
// int n,count=0;
// long p;
// cin>>n>>p;
// for(int i=0;i<n;i++){
// cin>>a[i];
// }
// sort(a,a+n);
// for(int i=0;i<n;i++)
// for(int j=i;j<n;j++){
// if(a[j]<=a[i]*p){
// if(count<j-i+1) count=j-i+1;
// }else break;
// }
// cout<<count;
// system("pause");
//}
//#include<iostream>
//using namespace std;
//int main(){
// int n,i;
// char c;
// cin>>n>>c;
// if(n==1) {
// cout<<c<<endl;
// cout<<0;
// return 0;
// }
// n--;
// for(i=1;n>=0;i++){
// n=n-2*(2*i+1);
// }
// int count= n+2*(2*(i-1)+1);//恢复减掉的
// i--;
// for(int j=0;j<i;j++){
// for(int ii=0;ii<j;ii++)cout<<" ";
// int tmp=2*(i-j)-1;
// while(tmp--) cout<<c;
// cout<<endl;
// }
// for(int j=1;j<i;j++){
// int tmp1=i-j-1;
// int tmp2=2*j+1;
// while(tmp1--)cout<<" ";
// while(tmp2--)cout<<c;
// cout<<endl;
// }
// cout<<count;
// system("pause");
//}
//#include<iostream>
//#include<string>
//#define LIM 1000000007
//using namespace std;
//int main(){
// string s;
// int p=0,pa=0,pat=0;
// cin>>s;
// int size=s.length();
// for(int i=0;i<size;i++){
// if(s[i]=='P') p++;
// if(s[i]=='A') pa=(pa+p)%LIM;
// if(s[i]=='T') pat=(pat+pa)%LIM;
// }
// cout<<pat;
//}
//#include<iostream>
//#include<map>
//using namespace std;
//int main(){
// char c;
// int hash[27]={0},count=0,idx=0;;
// while((c=getchar())!='\n'){
// if(c-'a'>=0&&c-'a'<=26){
// hash[c-'a']++;
// }else if(c-'A'>=0&&c-'A'<=26){
// hash[c-'A']++;
// }
// }
// for(int i=0;i<27;i++){
// if(count<hash[i]) {
// count=hash[i];
// idx=i;
// }
// }
// char out=idx+'a';
// cout<<out<<" "<<count;
// system("pause");
//}
//#include <iostream>
//#include <vector>
//#include <set>
//#include <algorithm>
//using namespace std;
//int n, maxheight = 0;
//vector<vector<int>> v;
//bool visit[10010];
//set<int> s;
//vector<int> temp;
//void dfs(int node, int height) {
// if(height > maxheight) {
// temp.clear();
// temp.push_back(node);
// maxheight = height;
// } else if(height == maxheight){
// temp.push_back(node);
// }
// visit[node] = true;
// for(int i = 0; i < v[node].size(); i++) {
// if(visit[v[node][i]] == false)
// dfs(v[node][i], height + 1);
// }
//}
//int main() {
// scanf("%d", &n);
// v.resize(n + 1);
// int a, b, cnt = 0, s1 = 0;
// for(int i = 0; i < n - 1; i++) {
// scanf("%d%d", &a, &b);
// v[a].push_back(b);
// v[b].push_back(a);
// }
// for(int i = 1; i <= n; i++) {
// if(visit[i] == false) {
// dfs(i, 1);
// if(i == 1) {
// if (temp.size() != 0) s1 = temp[0];
// for(int j = 0; j < temp.size(); j++)
// s.insert(temp[j]);
// }
// cnt++;
// }
// }
// if(cnt >= 2) {
// printf("Error: %d components", cnt);
// } else {
// temp.clear();
// maxheight = 0;
// fill(visit, visit + 10010, false);
// dfs(s1, 1);
// for(int i = 0; i < temp.size(); i++)
// s.insert(temp[i]);
// for(auto it = s.begin(); it != s.end(); it++)
// printf("%d\n", *it);
// }
// system("pause");
// return 0;
//}
//#include<iostream>
//#include<memory.h>
//#include<algorithm>
//using namespace std;
//int ans[10000]={0};
//int m,n;
//bool cmp(int x,int y){
// return x>y;
// }
//void sovle(){
// int num;
// cin>>num;
// for(int i=1;i<=num;i++){
// cin>>ans[i];
// }
// for(int i=sqrt(num);;i++){
// if(i*i>=num&&num%i==0) {
// m=i;
// n=num/m;
// break;
// }
// }
// sort(ans,ans+num,cmp);
// int out[m][n];
// bool
//
// }
//#include <iostream>
//#include <algorithm>
//#include <cmath>
//#include <cstdio>
//#include <cstring>
//#include <cctype>
//using namespace std;
//
//int N;
//
//bool compare(const int &a, const int &b)
//{
// return a > b;
//}
//
//void solve()
//{
// int A[N];
// for(int i = 0; i < N; i ++){
// cin >> A[i];
// }
// sort(A, A + N, compare);
//
// //以sqrt（n）向下寻找最大的n
// int m, n = sqrt(N);
// while(N % n != 0){
// n --;
// }
// m = N / n;
//
// int T[m][n];
// bool vis[m][n]; //vis[i][j] = true表示（i，j）已经访问过
// int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}, di = 0;
//
// for(int i = 0; i < m; i ++)
// for(int j = 0; j < n; j ++){
// vis[i][j] = false;
// }
//
// int i = 0, j = 0, k = 0;
// do{
// T[i][j] = A[k ++];
// vis[i][j] = true;
//
// int ni = i + dx[di], nj = j + dy[di];
// if(ni < 0 || ni >= m || nj < 0 || nj >= n || vis[ni][nj]){
// di = (di + 1) % 4;
// }
//
// i += dx[di];
// j += dy[di];
// }while(k < N);
//
// for(int i = 0; i < m; i ++){
// for(int j = 0; j < n; j ++){
// cout << T[i][j];
// if(j + 1 < n)
// cout << " ";
// }
// cout << endl;
// }
//
//}
//
//int main()
//{
// cin >> N;
// solve();
// return 0;
//}
//#include<iostream>
//using namespace std;
//int f(int n){
// if(n==1) return 0;
// if(n==2) return 1;
// return f(n-1)+f(n-1);
//}
//int main(){
// int a= f(10);
//
//}
//#include<iostream>
//using namespace std;
//#define N 1000
//int Tree[N];
//int findRoot(int x){
// if(x==-1) return x;
// else {
// int temp=findRoot(Tree[x]);
// Tree[x]=temp;
// return temp;
// }
//}
//int main(){
// int n,m;
// while(cin>>n&&n!=0){
// cin>>m;
// for(int i=1;i<=n;i++) Tree[i]=-1;
// while(m--){
// int a,b;
// cin>>a>>b;
// a=findRoot(a);
// b=findRoot(b);
// if(a!=b) Tree[a]=b;
// }
// int ans=0;
// for(int i=1;i<=n;i++){
// if(Tree[i]==-1) ans++;
// }
// cout<<ans-1;
// }
//}
//#include<iostream>
//using namespace std;
//#define N 100000001
//int Tree[N];
//int findRoot(int x){
// if(x==-1) return x;
// else {
// int temp=findRoot(Tree[x]);
// Tree[x]=temp;
// return temp;
// }
//}
//int sum[N];
//int main(){
// int n;
// while(cin>>n){
// for(int i=1;i<=N;i++){
// Tree[i]=-1;
// sum[i]=1;
// }
// while(n--){
// int a,b;
// cin>>a>>b;
// a=findRoot(a);
// b=findRoot(b);
// if(a!=b){
// Tree[a]=b;
// sum[b]+=sum[a];
// }
// }
// int ans=1;
// for(int i=1;i<=N;i++){
// if(Tree[i]==-1&&sum[i]>ans) ans=sum[i];
// }
// cout<<ans;
// }
//}
//最小生成树
//先把边排序，然后依次选取边；主要用到findRoot();
//#include<iostream>
//#include<algorithm>
//using namespace std;
//#define N 101
//int Tree[N];
//int findRoot(int x){
// if(Tree[x]==-1) return x;
// else{
// int temp=findRoot(Tree[x]);
// Tree[x]=temp;
// return temp;
// }
//}
//struct Edge{
// int a,b;
// int cost;
// bool operator< (const Edge &A) const{
// return cost<A.cost;
// }
//}edge[6000];
//int main(){
// int n;
// cin>>n;
// for(int i=1;i<=n*(n-1)/2;i++){
// cin>>edge[i].a>>edge[i].b>>edge[i].cost;
// }
// sort(edge+1,edge+1+n*(n-1)/2);
// for(int i=1;i<=n;i++){
// Tree[i]=-1;
// }
// int ans=0;
// for(int i=1;i<=n*(n-1)/2;i++){
// int a=findRoot(edge[i].a);
// int b=findRoot(edge[i].b);
// if(a!=b){
// Tree[a]=b;
// ans+=edge[i].cost;
// }
// }
// cout<<ans;
// system("pause");
//}
//Dijstra算法：单源
//#include<iostream>
//#include<vector>
//using namespace std;
//int main(){
// if(1||1&&0) cout<<100000<<endl;
// system("pause");
//}
//拓扑排序，把入度为0的放进队列，然后依次取出，并且相关点入度--
//#include<iostream>
//#include<vector>
//#include<queue>
//using namespace std;
//vector<int> edge[501];
//queue<int> Q;
//int main(){
// int inDegree[501];
// int n,m;
// while(cin>>n>>m){
// if(n==0&&m==0) break;
// for(int i=0;i<n;i++){
// inDegree[i]=0;
// edge[i].clear();
// }
// while(m--){
// int a,b;
// cin>>a>>b;
// inDegree[b]++;
// edge[a].push_back(b);
// }
// while(!Q.empty()) Q.pop();
// for(int i=0;i<n;i++){
// if(inDegree[i]==0) Q.push(i);
// }
// int cnt=0;
// while(!Q.empty()){
// int now=Q.front();
// Q.pop();
// cnt++;
// for(int i=0;i<edge[now].size();i++){
// inDegree[edge[now][i]]--;
// if(inDegree[edge[now][i]]==0){
// Q.push(edge[now][i]);
// }
// }
// }
// puts((cnt==n)?"YES":"NO");
//
// }
//}
//广度优先，不用递归，用个queue就行了，相当于层次遍历。一定是最优解，因为是一层一层遍历的。
//深度优先，用递归，相当于前序遍历，要回溯。
//void DFS(int x,int y,int time){
// int nx=x+go[i][0];
// int ny=y+go[i][1];
// if(nx<1||nx>n||ny<1||ny>m) continue;
// if(墙)continue;
// if(目标）{success=true; return;}
// maze[nx][ny]='X';//1.先设为已经用了
// DFS(nx,ny,time+1);//2.递归
// maze[nx][ny]='.';//3.如果回溯到了这里，就把他设为未用，便于其他人使用。
// if(success) return;
//}
//进制转化
//#include<iostream>
//using namespace std;
//int main(){
// int a,b;
// int d, ans[50],size=0;
// cin>>a>>b>>d;
// a=a+b;
// do{
// ans[size++]=a%d;//反向输出。
// a/=d;
// }while(a!=0);//为0时也能正常。
// for(int i=size-1;i>=0;i--){
// cout<<ans[i];
// }
// system("pause");
//}
//哈夫曼树
//使用priority_queue<int, vector<int>,greater<int>> Q; 是小顶堆。便以高效取出两个最小的元素。
//堆栈用q.top(); 队列用q.front();
//a=q.top();
//q.pop();
//b=q.top();
//q.pop();
//ans=+a+b;
//q.push(a+b);
//建立二叉排序树
//struct Node{ //定义
// Node *lchild;
// Node *rchild;
// int c;
// Node(int c):c(c),lchild(nullptr),rchild(nullptr){};
//};
//
//Node *ret = new Node(8);
//建立函数：
//Node *Insert(Node *T,int x){
// if(T==nullptr){
// Node *T= new Node(x);
// return T;
// }
// else if(x<T->c) T->lchild=Insert(T->lchild,x);
// elss if(x>T->c) T-.rchild=Insert(T->rchild,x);
// return T;
//}
//n阶旋转数组。
//#include<iostream>
//#include<memory.h>
//using namespace std;
//int main(){
// int n,num=1,dx=0,dy=0,count=0;
// cin>>n;
// int go[4][2]={0,1,1,0,0,-1,-1,0};
// int ans[100][100];
// int mark[100][100]={0};
// while(num<=n*n){
// ans[dx][dy]=num++;
// mark[dx][dy]=1;
// dx=dx+go[count][0];
// dy=dy+go[count][1];
// if(mark[dx][dy]==1||dx>=n||dx<0||dy>=n||dy<0) {
// dx=dx-go[count][0];
// dy=dy-go[count][1];
// count=(count+1)%4;
// dx=dx+go[count][0];
// dy=dy+go[count][1];
// }
// }
// for(int i=0;i<n;i++){
// for(int j=0;j<n;j++){
// cout<<ans[i][j];
// if(j<n-1)cout<<" ";
// }
// cout<<endl;
// }
// system("pause");
//}
//判断堆
//从数组1开始存，，画个图就明白了。
//#include<iostream>
//using namespace std;
//bool judgeMax(int a[],int n){
// for(int i=1;i<=n/2;i++){
// if(2*i+1<=n&&a[i]<a[2*i])return false;//有可能最后一个没有
// if(a[i]<a[2*i]) return false;
// }
// return true;
//}
//int main(){
// int n;
// cin>>n;
// int a[100];
// for(int i=1;i<=n;i++){
// cin>>a[i];
// }
// puts(judgeMax(a,n)?"YES":"NO");
// system("pause");
//}
//给定前序和中序
//递归：
/*
#include<iostream>
#include<string>
using namespace std;
struct Node{
Node *lchild;
Node *rchild;
char c;
Node(char c):c(c),lchild(nullptr),rchild(nullptr){};
};
string str1,str2;//定义全局
void postOrder(Node *T){
if(T==nullptr) return;
postOrder(T->lchild);
postOrder(T->rchild);
cout<<T->c;
}
Node *build(int s1,int e1,int s2,int e2){
//为前序第一个新建一个节点
Node *ret= new Node(str1[s1]);
int rootIdx;
//在中序序列中找
for(int i=s2;i<=e2;i++){
if(str2[i]==str1[s1]){
rootIdx=i;
break;
}
}
//递归
if(rootIdx!=s2){//左边
ret->lchild=build(s1+1,s1+(rootIdx-s2),s2,rootIdx-1);
}
if(rootIdx!=e2){//右边
ret->rchild=build(s1+(rootIdx-s2)+1,e1,rootIdx+1,e2);
}
return ret;//最后返回根节点
}
int main(){
cin>>str1>>str2;
int L1=str1.size();
int L2=str2.size();
Node *T=build(0,L1-1,0,L2-1);
postOrder(T);
system("pause");
}
*/
//求树的高度
//二叉树的所有路径：
/*
class Solution {
public:
void preOrder(TreeNode* root, vector<string> &v,string str){
if(!root) return;
if(!root->left&&!root->right) {
str+=to_string(root->val);
v.push_back(str);
return;
}
str+=to_string(root->val)+"->";
preOrder(root->left,v,str);
preOrder(root->right,v,str);
}
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> v;
preOrder(root,v,"");
return v;
}
*/
//递归算法求树的高度
/*
int getTreeHigh(BiTree Tree)
{
if (Tree==NULL) return 0;//递归出口
int LeftTreeHigh = getTreeHigh(Tree->lchild)+1;//分解成更小的规模。
int RightTreeHigh = getTreeHigh(Tree->rchild)+1;
return getMax(LeftTreeHigh,RightTreeHigh);
}
*/
//拓扑排序：
//需要一个邻接链表，以便在弹出节点时将所有与他相连的点的入度减一。
/*
#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;
vector<int> edge[501];
queue<int> Q;
int main(){
int m,n;
int inDegree[501];
while(scanf("%d%d",&m,&n)){
if(m==0&&n==0) break;
for(int i=0;i<m;i++){
inDegree[i]=0;
edge[i].clear();//下次用
}
while(n--){
int a,b;
scanf("%d%d",&a,&b);
edge[a].push_back(b);
inDegree[b]++;
}
while(!Q.empty()) Q.pop();
for(int i=0;i<m;i++){
if(inDegree[i]==0) Q.push(i);
}
int cnt=0;
while(!Q.empty()){
int newP = Q.front();
Q.pop();
cnt++;
for(int i=0;i<edge[newP].size();i++){
inDegree[edge[newP][i]]--;
if(inDegree[edge[newP][i]]==0){
Q.push(edge[newP][i]);
}
}
}
puts((cnt==n)?"YES":"NO");
}
}
*/
//括号匹配：用栈，将左括号进栈，碰到右括号则弹栈匹配。
//迷宫：用BFS也可以，BFS可以解最优解问题。层次遍历的思想，用队列即可实现。每次四个方向，依次进队；
//BFS（用队列按层次遍历就行 ）
//DFS（用递归）
//1.图形快（Flood Fill)(DFS解决)
/*
#include<stdio.h>
#include<iostream>
using namespace std;
char maze[101][101];//坐标从1开始
bool mark[101][101];
int n,m;
int go[][2]={1,0,-1,0,0,1,0,-1,1,1,1,-1,-1,-1,-1,1};
void DFS(int x,int y){
for(int i=0;i<8;i++){
int nx=x+go[i][0];
int ny=y+go[i][0];
if(nx<1||nx>n||ny<1||ny>m) continue;
if(maze[nx][ny]=='*') continue;
if(mark[nx][ny]=true) continue;
mark[nx][ny]=true;
DFS(nx,ny);
}
return;
}
int main(){
while(cin>>n>>m){
if(n==0&&m==0) break;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>maze[i][j];
mark[i][j]=false;
}
int ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
if(mark[i][j]==true) continue;
if(maze[i][j]=='*') continue;
DFS(i,j);
ans++;
}
cout<<ans;
}
}
}
*/
//最大字符串问题：动态规划问题
/*
class Solution {
public:
int max(int x,int y){if(x>y) return x; else return y;}
int lengthOfLIS(vector<int>& nums) {
if(nums.size()==0) return 0;
int tmp;
vector<int> a;
for(int i=0;i<nums.size();i++) a.push_back(1);
for(int i=1;i<nums.size();i++){
tmp=1;
for(int j=0;j<i;j++){
if(nums[i]>nums[j]){
tmp=max(tmp,a[j]+1);
}
a[i]=tmp;
}
}
for(int i=0;i<a.size();i++){
if(a[i]>tmp) tmp=a[i];
}
return tmp;
}
};
*/
//树的叶子权重
//二叉树的最近公共节点：
/*
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root==NULL||root==p||root==q) return root;
TreeNode* rootLeft=lowestCommonAncestor(root->left,p,q);
TreeNode* rootRight=lowestCommonAncestor(root->right,p,q);
if(rootLeft&&rootRight) return root;
else if(rootLeft) return rootLeft;
else return rootRight;
}
};
*/
//二叉搜索树的最近公共节点：根据搜索树的特性，如果在两边肯定一大一小，那根节点就是最近公共节点
/*
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if((root->val-p->val)*(root->val-q->val)<=0) return root;//递归出口
if(root->val>p->val) root=lowestCommonAncestor(root->left,p,q);//分解为更小规模
else root=lowestCommonAncestor(root->right,p,q);
return root;//输出
}
};
*/
//判断是不是二叉树：中序遍历为升序
/*
class Solution {
public:
vector<int> v;
bool isValidBST(TreeNode* root) {
if(root==NULL) return true;
inOrder(root);
for(int i=0;i<v.size()-1;i++){
if(v[i]>=v[i+1]) return false;
}
return true;
}
void inOrder(TreeNode* root){
if(root==NULL) return;
inOrder(root->left);
v.push_back(root->val);
inOrder(root->right);
}
};
*/
//最短路径：dijsktra单源
/*
#include<iostream>
#include<vector>
using namespace std;
struct E
{
int next;
int c;
int cost;
};
vector<E> edge[1001];//邻接表
int Dis[1001];
int cost[1001];
bool mark[1001];
int main(){
int n,m;
int S,T;
while(cin>>n>>m){
if(n==0&&m==0) break;
for(int i=1;i<=n;i++){
edge[i].clear();
Dis[i]=-1;
mark[i]=false;
}
while(m--){
int a,b,c,cost;
cin>>a>>b>>c>>cost;
E tmp;
tmp.c=c;
tmp.cost=cost;
tmp.next=b;
edge[a].push_back(tmp);
tmp.next=a;
edge[b].push_back(tmp);
}
cin>>S>>T;
Dis[S]=0;
mark[S]=true;
int newP=S;
for(int i=1;i<n;i++){//还剩n-1个点没加进去
for(int j=0;j<edge[newP].size();j++){
int t=edge[newP][j].next;
int c=edge[newP][j].c;
int co=edge[newP][j].cost;
if(mark[t]==true) continue;
if(Dis[t]==-1||Dis[t]>Dis[newP]+c||Dis[t]==Dis[newP]+c
&& cost[t]>cost[newP]+co){
Dis[t]=Dis[newP]+c;
cost[t]=cost[newP]+co;
}
}
int min=123123123;
for(int j=1;j<=n;j++){
if(mark[j]==true) continue;
if(Dis[j]==-1) continue;
if(Dis[j]<min){
min=Dis[j];
newP=j;
}
}
mark[newP]=true;
}
cout<<Dis[T]<<" "<<cost[T];
}
}
*/
/*
进栈出栈问题：
class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
stack<int>s;
int count=0;
for(int i=0;i<pushed.size();i++){
s.push(pushed[i]);
while(!s.empty()&&s.top()==popped[count]){
s.pop();
count++;
}
}
if(!s.empty()) return false;
return true;
}
};
*/
/*
完全二叉树：利用广度遍历，当遇到null指针结束，如果后面还有数字的话则表示失败；
class Solution {
public:
vector<TreeNode*> V;
queue<TreeNode*>Q;
bool isCompleteTree(TreeNode* root) {
if(root==NULL) return true;
Q.push(root);
while(Q.front()!=NULL){
TreeNode * tmp=Q.front();
Q.pop();
Q.push(tmp->left);
Q.push(tmp->right);
}
while(!Q.empty()){
if(Q.front()!=NULL) return false;
Q.pop();
}
return true;
}
};
*/
/*
平衡二叉树：
class Solution {
public:
bool isBalanced(TreeNode* root) {
if(!root||!root->left&&!root->right) return true;
if(abs(maxDepth(root->left)-maxDepth(root->right))>1) return false;
return isBalanced(root->left)&&isBalanced(root->right);
}
int maxDepth(TreeNode* root){
return root==NULL?0:max(maxDepth(root->left),maxDepth(root->right))+1;
}
};
*/
//文件操作
/*
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<string.h>
using namespace std;
#define N 10
struct Student{
char name[10];
char id[10];
int score;
bool operator <(const Student &A) const{
return strcmp(name,A.name)<0;
}
}student[10];
void write(){
FILE * f;
if((f = fopen("student1.txt","wb"))==NULL){
printf("error");
return;
}
for(int i=0;i<N;i++){
if(fwrite(&student[i],sizeof(struct Student),1,f)!=1){//成功返回1
printf("error");
}
}
fclose(f);
}
void load(){
FILE *f;
if((f=fopen("student.txt","rb"))==NULL){
printf("error");
return;
}
for(int i=0;i<N;i++){
if(fread(&student[i],sizeof(struct Student),1,f)!=1){
if(feof(f)){
fclose(f);
return;
}
printf("error");
}
}
fclose(f);
}
int main(){
//printf("enter data of students\n");
//for(int i=0;i<N;i++){
// scanf("%s%s%d",student[i].name,student[i].id,&student[i].score);
//}
load();
sort(student,student+N);
write();
for(int i=0;i<N;i++){
printf("%s %s %d\n",student[i].name,student[i].id,student[i].score);
}
system("pause");
return 0;
}
*/
//一道上机题
/*
#include<iostream>
#include<string>
using namespace std;
int flag[26]={0};
int main(){
string s;
cin>>s;
for(int i=0;i<s.length();i++){
if(falg[s[i]-'a']==0){
cout<<s[i];
flag[s[i]-'a']=1;
}else continue;
}
return 0;
}*/ |
转播
