#if 0 __END__ #endif #include #define fr(i,n) for(int i=0;i<(n);++i) #define foor(i,a,b) for(int i=(a);i<=(b);++i) #define rf(i,n) for(int i=(n);i-->0;) #define roof(i,b,a) for(int i=(b);i>=(a);--i) #define elsif else if #define all(x) x.begin(),x.end() #define Sort(x) sort(all(x)) #define Reverse(x) reverse(all(x)) #define PQ priority_queue #define NP(x) next_permutation(all(x)) #define M_PI 3.14159265358979323846 #define popcount __builtin_popcountll using namespace std; using vb=vector;using vvb=vector; using vi=vector;using vvi=vector;using vvvi=vector; using ll=long long; using vl=vector< ll>;using vvl=vector;using vvvl=vector; using ull=unsigned long long;using vu=vector;using vvu=vector; using dbl=double; using vd=vector;using vvd=vector;using vvvd=vector; using str=string; using vs=vector;using vvs=vector; using pii=pair; using vpii=vector;using mii=map; using pll=pair< ll, ll>; using vpll=vector;using mll=map< ll, ll>; using pdd=pair; using vpdd=vector;using mdd=map; using pss=pair; using vpss=vector;using mss=map; using pil=pair; using vpil=vector;using mil=map; using pli=pair< ll,int>; using vpli=vector;using mli=map< ll,int>; using pdi=pair; using vpdi=vector;using mdi=map; templatevector&operator<<(vector&v,const T t){v.push_back(t);return v;} templatemultiset&operator<<(multiset&m,const T t){m.insert(t);return m;} templateset&operator<<(set&s,const T t){s.insert(t);return s;} templatestack&operator<<(stack&s,const T t){s.push(t);return s;} templatestack&operator>>(stack&s,T&t){t=s.top();s.pop();return s;} templatequeue&operator<<(queue&q,const T t){q.push(t);return q;} templatequeue&operator>>(queue&q,T&t){t=q.front();q.pop();return q;} templatePQ,U>&operator<<(PQ,U>&q,const T t){q.push(t);return q;} templatePQ,U>&operator>>(PQ,U>&q,T&t){t=q.top();q.pop();return q;} templateistream&operator>>(istream&s,pair&p){return s>>p.first>>p.second;} istream&operator>>(istream&s,_Bit_reference b){int a;s>>a;assert(a==0||a==1);b=a;return s;} templateistream&operator>>(istream&s,vector&v){fr(i,v.size()){s>>v[i];}return s;} templateostream&operator<<(ostream&s,const pairp){return s<ostream&operator<<(ostream&s,const vectorv){fr(i,v.size()){i?s<<" "<ostream&operator<<(ostream&s,const dequed){fr(i,d.size()){i?s<<" "<_Bit_reference operator&=(_Bit_reference b,T t){return b=b&t;} template_Bit_reference operator^=(_Bit_reference b,T t){return b=b^t;} template_Bit_reference operator|=(_Bit_reference b,T t){return b=b|t;} templatepairoperator+(paira,pairb){return {a.first+b.first,a.second+b.second};} templatepairoperator-(paira,pairb){return {a.first-b.first,a.second-b.second};} templatepair&operator+=(pair&a,pairb){return a=a+b;} templatepair&operator-=(pair&a,pairb){return a=a-b;} void print(void){cout<<"\n";} void Print(void){cout<void print(T t){cout<void Print(T t){cout<void print(T&&t,U&&...u){cout<(u)...);} templatevoid Print(T&&t,U&&...u){cout<(u)...);} bool YN(bool b){print(b?"YES":"NO");return b;}bool PI(bool b){print(b?"POSSIBLE":"IMPOSSIBLE");return b;} bool Yn(bool b){print(b?"Yes":"No");return b;}bool Pi(bool b){print(b?"Possible":"Impossible");return b;} bool yn(bool b){print(b?"yes":"no");return b;}bool pi(bool b){print(b?"possible":"impossible");return b;} const int e5=1e5; const int e9=1e9; const int MD=1e9+7; const int md=998244353; const ll e18=1e18; templatestr to_string(const T&n){ostringstream s;s<bool chmax(T&a,T b){return abool chmin(T&a,T b){return a>b?(a=b,true):false;} templatevector>dijkstra(const vector>>&E,const U s,const T inf){using P=pair;vector

d;fr(i,E.size()){d<,greater

>pq;pq<<(d[s]=P{0,s});while(pq.size()){P a=pq.top();pq.pop();U v=a.second;if(d[v].first>=a.first){for(P e:E[v]){if(d[v].first+e.firstmap>dijkstra(map>>E,const U s,const T inf){using P=pair;mapd;for(pair>e:E){d[e.first]=P{inf,e.first};}PQ,greater

>pq;pq<<(d[s]=P{0,s});while(pq.size()){P a=pq.top();pq.pop();U v=a.second;if(d[v].first>=a.first){for(P e:E[v]){if(d[v].first+e.first&E,int s,int t){ll z=0;vi b(E.size(),-1);for(int i=0;;++i){static auto dfs=[&](int v,ll f,auto&dfs)->ll{if(v==t)return f;b[v]=i;for(auto&p:E[v]){if(b[p.first]T distsq(paira,pairb){return (a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second);} templateT max(const vectora){assert(a.size());T m=a[0];for(T e:a){m=max(m,e);}return m;} templateT min(const vectora){assert(a.size());T m=a[0];for(T e:a){m=min(m,e);}return m;} templateT gcd(const T a,const T b){return a?gcd(b%a,a):b;} templateT gcd(const vectora){T g=a[0];for(T e:a){g=gcd(g,e);}return g;} //templatevectorLCS(vectorA,vectorB){int N=A.size(),M=B.size();vector>>d(N+1,vector>(M+1));fr(i,N){fr(j,M){if(A[i]==B[j]){d[i+1][j+1]={d[i][j].first+1,{i,j}};}else{d[i+1][j+1]=max(d[i][j+1],d[i+1][j]);}}}vectorr;for(pii p={N,M};d[p.first][p.second].first;p=d[p.first][p.second].second){r<s=LCS(vector(S.begin(),S.end()),vector(T.begin(),T.end()));return str(s.begin(),s.end());} //templatevector>ConvexHull(vector>V){if(V.size()<=3){return V;}Sort(V);rf(i,V.size()-1)V<>r;for(pairp:V){int s=r.size();while(s>=2&&(p.second-r[s-1].second)*(p.first-r[s-2].first)<(p.second-r[s-2].second)*(p.first-r[s-1].first)){r.pop_back();--s;}r<s[b]){swap(a,b);}s[b]+=s[a];p[a]=b;}}void unite(pii p){return unite(p.first,p.second);}bool same(int a,int b){extend(a);extend(b);return find(a)==find(b);}bool same(pii p){return same(p.first,p.second);}int size(int x){extend(x);return s[find(x)];}}; //ll MST(vector>&E){Sort(E);UnionFind uf;ll z=0;for(auto&e:E){if(!uf.same(e.second)){z+=e.first;uf.unite(e.second);}}return z;} //ll strmod(const str&s,const int m){ll x=0;fr(i,s.size()){x=(x*10+s[i]-48)%m;}return x;} vvl mul(const vvl&A,const vvl&B,const int m){vvl C;fr(y,A.size()){C<=0?a%m:(m-(-a%m))%m:1)*(t=pow(a,n>>1,m),t*t%m)%m:!!a;} ll inv(const ll x,const int p){assert(x!=0);return pow(x,p-2,p);} //ll inv(const ll x){return inv(x,MD);} vpll fact(const int n,const int p){assert(nint MSB(T N){int r=-1;for(;N>0;N/=2){++r;}return r;} templateclass SegmentTree{vectorS;T(*const op)(T a,T b);const T zero;const int B;public:SegmentTree(int N,T(*f)(T a,T b),const T zero):S(1<v,T(*f)(T a,T b),const T zero):SegmentTree(v.size(),f,zero){fr(i,v.size()){S[S.size()/2+i]=v[i];}roof(i,S.size()/2-1,1){S[i]=op(S[i*2],S[i*2+1]);}}T calc(int l,int r){l+=B;r+=B;if(l>r){return zero;}if(l==r){return S[l];}T L=S[l],R=S[r];for(;l/20){z+=B[i];i-=i&-i;}return z;} //void BITadd(vl&B,int i,ll x){while(i>i&1){a=A;b=B;c=C;d=D;A=a+b;B=a;C=c+d;D=c;}a=A%m;b=B%m;c=C%m;d=D%m;}return b;} vi primes(int n){vb b(n+1);vi p;foor(i,2,n){if(!b[i]){p<=L;j-=i){B[j-L]=false;}}}vl P;for(ll i=max(2ll,L);i<=R;++i){if(B[i-L]){P<dfs=[&](int i,int p){for(int j:E[i])if(j!=p){par[0][j]=i;dep[j]=dep[i]+1;dfs(j,i);}};par[0][root]=root;dfs(root,root);fr(i,par.size()-1){fr(j,par[0].size()){par[i+1][j]=par[i][par[i][j]];}}}int operator()(int a,int b){if(dep[a]>dep[b])swap(a,b);for(int t=dep[b]-dep[a],i=0;t;t>>=1,++i){if(t&1){b=par[i][b];}}if(a==b)return a;rf(i,par.size()){if(par[i][a]!=par[i][b]){a=par[i][a];b=par[i][b];}}return par[0][a];}int dist(int a,int b){return dep[a]+dep[b]-2*dep[operator()(a,b)];}}; vpli factor(ll N){vpli r;for(ll i=2;i*i<=N;++i){if(N%i==0){r<1){r<bool{if(rank[a]!=rank[b])return rank[a]void sort2(vector&a,vector&b){int N=a.size();assert(b.size()==N);vector>v;fr(i,N){v<{a[i],b[i]};}Sort(v);fr(i,N){a[i]=v[i].first;b[i]=v[i].second;}} templatevoid sort3(vector&a,vector&b,vector&c){int N=a.size();assert(b.size()==N);assert(c.size()==N);vector>>v;fr(i,N){v.push_back({a[i],{b[i],c[i]}});}Sort(v);fr(i,N){a[i]=v[i].first;b[i]=v[i].second.first;c[i]=v[i].second.second;}} //vi toposo(vvi E){int N=E.size();vi T(N,-1);{vvi R(N);vi v;{vb u(N);functionf=[&](int i){if(u[i])return;u[i]=true;for(int j:E[i]){R[j]<f=[&](int i){T[i]=k;for(int j:R[i]){if(T[j]==-1){f(j);}}};rf(i,v.size()){if(T[v[i]]==-1){f(v[i]);++k;}}}}return T;} //vb SAT2(vvi E){int N=E.size();assert(N%2==0);vi T=toposo(E);vb z(N);fr(i,N/2){if(T[2*i]==T[2*i+1]){return vb{};}z[2*i+(T[2*i]a2){swap(a1,a2);swap(m1,m2);}return INV(m1,m2)*(a2-a1)%m2*m1+a1;} //ull mulull(ull a,ull b,ull m){using ld=long double;ll t=a*b-m*ull(ld(a)*ld(b)/ld(m));return t+m*(t<0)-m*(t>=ll(m));} //ll powll(const ll a,const ll n,const ll m){return n?n%2?mulull(a,powll(a,n-1,m),m):powll(mulull(a,a,m),n/2,m):!!a;} //bool MillerRabin(int n){if(n<2){return false;}int d=n-1,s=0;for(;d%2==0;d/=2){++s;}if(s==0){return n==2;}for(int a:{2,7,61})if(a=2&&mf[x]==x;}int minfactor(int x){assert(x>=2);assert(x=1);assert(x1){if(v.empty()||v.back().first=1);assert(x1;--m){if(pow(t,1<>B; ll K;cin>>K; --K; A=pow(A,K,10); int z=0; fr(i,3){ B[i]%=10; z+=A[0][i]*B[i]; } print(z%10); return 0; } #if 0 #endif