1
#include<bits/stdc++.h>
2
using namespace std;
3
namespace fast_IO{
4
    namespace input{                  //input
5
    template<typename T>
6
    inline T read(){
7
        if constexpr (std::is_same_v<T,int>){
8
            int tot=0,t=1;char ch=getchar();
9
            while(!isdigit(ch)){if(ch=='-') t=-1;ch=getchar();}
10
            while(isdigit(ch)){tot=tot*10+ch-'0';ch=getchar();}
11
            return tot*t;
12
        }
13
        else if constexpr (std::is_same_v<T,char>){
14
            char ch=getchar();
15
            while(isspace(ch)) ch=getchar();
16
            return ch;
17
        }
18
        else if constexpr (std::is_same_v<T,std::string>){
19
            std::string s;char ch=getchar();
20
            while(isspace(ch)) ch=getchar();
21
            while(!isspace(ch)&&ch!=EOF) s+=ch,ch=getchar();
22
            return s;
23
        }
24
        else if constexpr (std::is_same_v<T,double>){
25
            char ch=getchar();int sign=1;double tot=0.0;
26
            while(isspace(ch)) ch=getchar();
27
            if(ch=='-') sign=-1,ch=getchar();
28
            else if(ch=='+') ch=getchar();
29
            while(isdigit(ch)) tot=tot*10.0+(ch-'0')*1.0,ch=getchar();
30
            if(ch=='.'){
31
                ch=getchar();
32
                double val=0.0,fac=1.0;
33
                while(isdigit(ch)){
34
                    val=val*10.0+(ch-'0')*1.0;
35
                    fac*=10.0;ch=getchar();
36
                }
37
                tot+=1.0*val/fac;
38
            }
39
            if(ch=='e'||ch=='E'){
40
                ch=getchar();int exp_sign=1;
41
                if(ch=='-') exp_sign=-1,ch=getchar();
42
                else if(ch=='+') ch=getchar();
43
                double val=0.0;
44
                while(isdigit(ch)){
45
                    val=val*10.0+(ch-'0')*1.0;
46
                    ch=getchar();
47
                }
48
                tot*=std::pow(10.0,exp_sign*val);
49
            }
50
            return 1.0*sign*tot;
51
        }
52
    }
53
    inline char read_upper(){
54
        char ch=getchar();
55
        while(!isupper(ch)) ch=getchar();
56
        return ch;
57
    }
58
    inline char read_lower(){
59
        char ch=getchar();
60
        while(!islower(ch)) ch=getchar();
61
        return ch;
62
    }
63
    inline char read_num(){
64
        char ch=getchar();
65
        while(!isdigit(ch)) ch=getchar();
66
        return ch;
67
    }
68
    }using namespace input;
69
    namespace output{                                    //output
70
    template<typename T>
71
    inline void print(T x){
72
        if(x<0) putchar('-'),x=-x;
73
        static int sta[35];int top=0;
74
        do{sta[top++]=x%10,x/=10;}while(x);
75
        while(top) putchar(sta[--top]+'0');
76
    }
77
    inline char print(const char &x){return putchar(x);}
78
    template<typename T>
79
    inline void print(T *x){while(*x) putchar(*(x++));}
80
    inline void print(const string &x){for(int i=0;i<(int)x.size();i++) putchar(x[i]);}
81
    inline std::string floor(double x,int pot){
82
        std::string s="";if(x<0) s+='-';
83
        int t=(int)x;s+=std::to_string(t)+'.';x-=1.0*t;
84
        while(pot) x*=10.0,s+=(((int)x)%10+'0'),pot--;
85
        return s;
86
    }
87
    template<typename T,typename...Ts>
88
    inline void print(const T &x,const Ts&...y){print(x),print(y...);}
89
    }using namespace output;
90
}using namespace fast_IO;
91
signed main(signed argc,char* argv[]){
92

93
  return 0;
94
}