#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

template<class S,class T>bool chmin(S&a,T b){if(a>b){a=b;return true;}return false;}
template<class S,class T>bool chmax(S&a,T b){if(a<b){a=b;return true;}return false;}
template<class T>T Min(T a,T b){return a<b?a:b;}
template<class T,class...Args>T Min(T a,T b,Args...args){return Min(Min(a,b),args...);}
template<class T>T Max(T a,T b){return a>b?a:b;}
template<class T,class...Args>T Max(T a,T b,Args...args){return Max(Max(a,b),args...);}
#define rep(i,n) for (ll i = 0;i < (ll)(n);i++)
#define Yes cout << "Yes\n"// YESの短縮
#define No cout << "No\n"// NOの短縮
#define YN(x) cout<<((x)?"Yes":"No")<<'\n'
#define rtr0 return(0)//return(0)の短縮
#define gyakugen(x) modpow(x,mod - 2,mod)
#define agyakugen(x) modpow(x,amod - 2,amod)
#define st(A) sort((A).begin(),(A).end())
#define rst(A) sort((A).rbegin(),(A).rend())
#define rev(A) reverse((A).begin(),(A).end())
#define unq(A) (A).erase(unique((A).begin(),(A).end()),(A).end())
#define all(A) (A).begin(),(A).end()
#define rall(A) (A).rbegin(),(A).rend()
using namespace std;
using ll = long long;//63bit型整数型
using ld = long double;//doubleよりも長い値を保存できるもの
using ull = unsigned long long;//符号がない64bit型整数
template <class T>using maxpq = priority_queue<T>;
template <class T>using minpq = priority_queue<T,vector<T>,greater<T>>;
ll mod = 998244353;
ll amod = 1000000007;
ll MINF = -5000000000000000000LL;
ll INF = 50000000000000LL;
ll inf = 2000000000;
ll minf = -2000000000;
ll BAD = -1;
ll zero = 0;
ld EPS = 1e-10;
vector<ll>randomhash = {(ll)1e9 + 7,(ll)1e9 + 801,((ll)1e8 * 8) + 29,((ll)1e8 * 7) + 159,((ll)1e8 * 9) + 221};
vector<ll>tate = {0,-1,0,1};//グリッド上の全探索時の四方向の上下のチェック
vector<ll>yoko = {1,0,-1,0};//グリッド上の全探索時の四方向の右左のチェック
vector<ll>etate = {0,-1,-1,-1,0,1,1,1};//グリッド上の全探索時の八方向の上下のチェック
vector<ll>eyoko = {1,1,0,-1,-1,-1,0,1};//グリッド上の全探索時の八方向の右左のチェック
vector<ll>hexsax = {0,1,1,0,-1,-1};
vector<ll>hexsay = {1,1,0,-1,-1,0};
// 素数
vector<bool> isprime;
vector<ll> Era(int n){// [0,n) の素数一覧
    isprime.assign(max(0,n),true);
    vector<ll> res;
    if(n<=0)return res;
    isprime[0]=false;
    if(n==1)return res;
    isprime[1]=false;
    for(ll i=2;i<n;i++){
        if(!isprime[i])continue;
        res.push_back(i);
        if(i*i<n)for(ll j=i*i;j<n;j+=i)isprime[j]=false;
    }
    return res;
}
ll ceil_div(ll a,ll b){
    if(b<=0)return INF;
    return a/b+(a%b>0);
}
// 数学
ull modmul(ull a,ull b,ull md){
    return (ull)((__uint128_t)a*b%md);
}
ll modpow(ll a,ll n,ll md){
    assert(md>0&&n>=0);
    a%=md;if(a<0)a+=md;
    ll res=1%md;
    while(n>0){
        if(n&1)res=(ll)((__int128)res*a%md);
        a=(ll)((__int128)a*a%md);
        n>>=1;
    }
    return res;
}

long long npow(long long a, long long n){
    long long res = 1;
    while (n > 0) {
		if (n & 1) res = res * a;
		a = a * a;
		n >>= 1;
	}
	return res;
}
long long isqrt(long long num){
    assert(num>=0);
    ll x=(ll)sqrtl((ld)num);
    while((x+1)>0&&(x+1)<=num/(x+1))x++;
    while(x>0&&x>num/x)x--;
    return x;
}
ld get_theta(ld px,ld py,ld fx,ld fy,ld sx,ld sy){
    ld fxv=fx-px,fyv=fy-py,sxv=sx-px,syv=sy-py;
    ld pfs=hypotl(fxv,fyv),pss=hypotl(sxv,syv);
    assert(pfs>0&&pss>0);
    ld c=(fxv*sxv+fyv*syv)/(pfs*pss);
    c=max((ld)-1,min((ld)1,c));
    return acosl(c)*180.0L/acosl(-1.0L);
}
ld Euclidean_distance(ll x1,ll y1,ll x2,ll y2){
    return hypotl((ld)x1-x2,(ld)y1-y2);
}
ll Manhattan_distance(ll x1,ll y1,ll x2,ll y2){
    return abs(x1-x2)+abs(y1-y2);
};
void change_bit(ll N,ll end,vector<ll>&X){
    if((ll)X.size()<end)X.resize(end);
    for(ll i=0;i<end;i++)X[i]=(i<64?(((ull)N>>i)&1ULL):0);
}
ll popcount(ll x){return __builtin_popcountll((ull)x);}

ll cutup(ll a,ll b){return ceil_div(a,b);}
void Run_Length_Encoding(const string&A,vector<pair<ll,ll>>&RLE){
    RLE.clear();
    if(A.empty())return;
    RLE.push_back({A[0],1});
    for(ll i=1;i<(ll)A.size();i++){
        if(RLE.back().first==A[i])RLE.back().second++;
        else RLE.push_back({A[i],1});
    }
}
bool is_in_grid(ll i,ll j,ll H,ll W){return 0<=i&&i<H&&0<=j&&j<W;}
// 座標圧縮: valsに元の値を昇順で保存し、返り値は各要素の圧縮後index
// vector<ll> vals; vector<int> B=coordinate_compress(A,vals);
template<class T>
vector<int> coordinate_compress(const vector<T>&A,vector<T>&vals){
    vals=A;sort(vals.begin(),vals.end());vals.erase(unique(vals.begin(),vals.end()),vals.end());
    vector<int> res(A.size());
    for(int i=0;i<(int)A.size();i++)res[i]=(int)(lower_bound(vals.begin(),vals.end(),A[i])-vals.begin());
    return res;
}
// 素因数分解 O(sqrt(N))
vector<pair<ll,int>> prime_factorize(ll n){
    assert(n>=1);vector<pair<ll,int>> res;
    for(ll p=2;p<=n/p;p+=(p==2?1:2))if(n%p==0){
        int cnt=0;while(n%p==0)n/=p,cnt++;
        res.push_back({p,cnt});
    }
    if(n>1)res.push_back({n,1});
    return res;
}
// 約数列挙 O(sqrt(N))、昇順
vector<ll> divisors(ll n){
    assert(n>=1);vector<ll> a,b;
    for(ll i=1;i<=n/i;i++)if(n%i==0){a.push_back(i);if(i!=n/i)b.push_back(n/i);}
    reverse(b.begin(),b.end());a.insert(a.end(),b.begin(),b.end());return a;
}
template<long long MOD>
class ModInt {
private:
    long long val;
    // 拡張ユークリッドの互除法で逆元を計算
    static long long mod_pow(long long base,long long exp,long long md) {
        long long result = 1;
        base%=md;
        while(exp>0){
            if(exp&1)result=(long long)((__int128)result*base%md);
            base=(long long)((__int128)base*base%md);
            exp >>= 1;
        }
        return result;
    }
    // フェルマーの小定理を使った逆元計算（MODが素数の場合）
    static long long mod_inv(long long a,long long md) {
        return mod_pow(a,md-2,md);
    }
public:
    // コンストラクタ
    ModInt() : val(0) {}
    ModInt(long long x) : val(((x % MOD) + MOD) % MOD) {}

    // 値の取得
    long long value() const { return val; }

    // 四則演算の演算子オーバーロード
    ModInt operator+(const ModInt& other) const {
        return ModInt((val + other.val) % MOD);
    }
    ModInt operator-(const ModInt& other) const {
        return ModInt((val - other.val + MOD) % MOD);
    }
    ModInt operator*(const ModInt& other) const {
        return ModInt((long long)((__int128)val*other.val%MOD));
    }
    ModInt operator/(const ModInt& other) const {
        assert(other.val != 0);  // 0除算チェック
        return ModInt((long long)((__int128)val*mod_inv(other.val,MOD)%MOD));
    }
    // 代入演算子
    ModInt& operator+=(const ModInt& other) {
        val = (val + other.val) % MOD;
        return *this;
    }
    ModInt& operator-=(const ModInt& other) {
        val = (val - other.val + MOD) % MOD;
        return *this;
    }
    ModInt& operator*=(const ModInt& other) {
        val=(long long)((__int128)val*other.val%MOD);
        return *this;
    }
    ModInt& operator/=(const ModInt& other) {
        assert(other.val != 0);  // 0除算チェック
        val=(long long)((__int128)val*mod_inv(other.val,MOD)%MOD);
        return *this;
    }
    // 比較演算子
    bool operator==(const ModInt& other) const {
        return val == other.val;
    }
    bool operator!=(const ModInt& other) const {
        return val != other.val;
    }
    // 単項演算子
    ModInt operator+() const {
        return *this;
    }
    ModInt operator-() const {
        return ModInt(val == 0 ? 0 : MOD - val);
    }
    // べき乗
    ModInt pow(long long exp) const {
        return ModInt(mod_pow(val, exp, MOD));
    }
    ModInt inv() const {
        assert(val!=0);
        return ModInt(mod_inv(val,MOD));
    }
    // 出力用
    friend std::ostream& operator<<(std::ostream& os, const ModInt& m) {
        return os << m.val;
    }
    // 入力用
    friend std::istream& operator>>(std::istream& is, ModInt& m) {
        long long x;
        is >> x;
        m = ModInt(x);
        return is;
    }
};
// Rolling Hash
template<class T>
struct rolling_hash{
    vector<ull>Power,hash,InvPower;
    ll B = 0;
    ll MOD = 0;
    void set_number(ll base,ll md){
        assert(md>1);
        B=base%md;if(B<0)B+=md;
        MOD=md;
        assert(B!=0);
    }
    void do_hash(const T &S) {
        assert(MOD>1&&B!=0);
        ll N = S.size();
        Power.resize(N+1);
        InvPower.resize(N+1);
        hash.resize(N+1);
        Power[0] = 1;
        InvPower[0] = 1;
        ull invB=modpow(B,MOD-2,MOD);
        for(ll i=0;i<N;i++){
            Power[i+1]=modmul(Power[i],B,MOD);
            InvPower[i+1]=modmul(InvPower[i],invB,MOD);
            ll v=(ll)S[i]%MOD;if(v<0)v+=MOD;
            hash[i+1]=(hash[i]+modmul((ull)v,Power[i],MOD))%MOD;
        }
    }
    ll get_hash(ll l, ll r) {
        ull res = (hash[r]+MOD-hash[l])%MOD;
        res = modmul(res,InvPower[l],MOD);
        return res;
    }
};
// Floyd-Warshall
template<class T>
struct Floyd_Warshall{
    vector<vector<T>> ans;
    int N=0;
    static constexpr T INF_T=numeric_limits<T>::max()/4;
    void reset(int n){
        N=n;
        ans.assign(N,vector<T>(N,INF_T));
        for(int i=0;i<N;i++)ans[i][i]=0;
    }
    void indirected_set(int u,int v,T cost){ans[u][v]=ans[v][u]=cost;}
    void undirected_set(int u,int v,T cost){indirected_set(u,v,cost);}
    void directed_set(int u,int v,T cost){ans[u][v]=cost;}
    void do_Floyd_Warshall(){
        for(int k=0;k<N;k++)for(int i=0;i<N;i++)for(int j=0;j<N;j++){
            if(ans[i][k]==INF_T||ans[k][j]==INF_T)continue;
            chmin(ans[i][j],ans[i][k]+ans[k][j]);
        }
    }
    T get(int u,int v){return ans[u][v];}
};
// Combination: calu() O(N), get() O(1)（MODは素数を想定）
template<class T>
struct combination{
    vector<T> factorial,invfactorial;
    ll MOD,N;
    void reset(T n,T md){N=(ll)n+1;MOD=md;factorial.assign(N,1);invfactorial.assign(N,1);}
    void calu(){
        assert(1<MOD&&N<=MOD);
        for(ll i=1;i<N;i++)factorial[i]=(T)((__int128)factorial[i-1]*i%MOD);
        if(N<=1)return;
        invfactorial[N-1]=(T)modpow((ll)factorial[N-1],MOD-2,MOD);
        for(ll i=N-1;i>=1;i--)invfactorial[i-1]=(T)((__int128)invfactorial[i]*i%MOD);
    }
    T get(T n,T r)const{
        if(r<0||r>n||n<0||n>=N)return 0;
        return (T)((__int128)factorial[n]*invfactorial[r]%MOD*invfactorial[n-r]%MOD);
    }
    T permutation(T n,T r)const{
        if(r<0||r>n||n<0||n>=N)return 0;
        return (T)((__int128)factorial[n]*invfactorial[n-r]%MOD);
    }
};
// Dijkstra
template<class T>
struct dijkstra{
    vector<vector<pair<int,T>>> graph;
    vector<T> ans;vector<int> prev;
    priority_queue<pair<T,int>,vector<pair<T,int>>,greater<pair<T,int>>> pq;
    static constexpr T INF_T=numeric_limits<T>::max()/4;
    void do_dijkstra(int start){
        ans.assign(graph.size(),INF_T);prev.assign(graph.size(),-1);pq={};
        pq.push({0,start});ans[start]=0;
        while(!pq.empty()){
            auto [cost,vertex]=pq.top();pq.pop();
            if(cost!=ans[vertex])continue;
            for(auto [nextvertex,w]:graph[vertex]){
                T nextcost=cost+w;
                if(!chmin(ans[nextvertex],nextcost))continue;
                prev[nextvertex]=vertex;pq.push({nextcost,nextvertex});
            }
        }
    }
    void make_indirectedgraph(int u,int v,T cost){graph[u].push_back({v,cost});graph[v].push_back({u,cost});}
    void make_directedgraph(int u,int v,T cost){graph[u].push_back({v,cost});}
    T output(int end){return ans[end];}
    vector<int> path(int end)const{
        if(end<0||end>=(int)ans.size()||ans[end]==INF_T)return {};
        vector<int> res;for(int v=end;v!=-1;v=prev[v])res.push_back(v);
        reverse(res.begin(),res.end());return res;
    }
    void reset(int N){graph.assign(N,{});ans.assign(N,INF_T);prev.assign(N,-1);pq={};}
};
// BFS（重みなし）
vector<int> bfs(const vector<vector<int>>&graph,int start){
    int N=(int)graph.size();vector<int> dist(N,-1);queue<int> q;
    dist[start]=0;q.push(start);
    while(!q.empty()){
        int v=q.front();q.pop();
        for(int to:graph[v])if(dist[to]==-1)dist[to]=dist[v]+1,q.push(to);
    }
    return dist;
}
vector<int> bfs(const vector<vector<int>>&graph,const vector<int>&starts){
    int N=(int)graph.size();vector<int> dist(N,-1);queue<int> q;
    for(int s:starts)if(dist[s]==-1)dist[s]=0,q.push(s);
    while(!q.empty()){
        int v=q.front();q.pop();
        for(int to:graph[v])if(dist[to]==-1)dist[to]=dist[v]+1,q.push(to);
    }
    return dist;
}
// 01-BFS: 辺の重みは0か1
vector<int> bfs01(const vector<vector<pair<int,int>>>&graph,int start){
    int N=(int)graph.size(),I=numeric_limits<int>::max()/4;vector<int> dist(N,I);deque<int> q;
    dist[start]=0;q.push_front(start);
    while(!q.empty()){
        int v=q.front();q.pop_front();
        for(auto [to,w]:graph[v]){
            assert(w==0||w==1);
            if(dist[to]<=dist[v]+w)continue;
            dist[to]=dist[v]+w;
            if(w)q.push_back(to);else q.push_front(to);
        }
    }
    return dist;
}
// トポロジカルソート。閉路があると空vectorを返す
vector<int> topological_sort(const vector<vector<int>>&graph){
    int N=(int)graph.size();vector<int> indeg(N),res;queue<int> q;
    for(int v=0;v<N;v++)for(int to:graph[v])indeg[to]++;
    for(int v=0;v<N;v++)if(indeg[v]==0)q.push(v);
    while(!q.empty()){
        int v=q.front();q.pop();res.push_back(v);
        for(int to:graph[v])if(--indeg[to]==0)q.push(to);
    }
    if((int)res.size()!=N)res.clear();
    return res;
}
// Union-Find
template<class T>
struct unionfind {
public:
    vector<T> parent, rank;
    void reset(T N) { // 初期化
        parent.resize(N);
        rank.assign(N, 1); // 各集合のサイズを 1 にする
        for (T i = 0; i < N; i++) parent[i] = i;
    }
    T leader(T x) { // 経路圧縮による親の取得
        if (parent[x] == x) return x;
        return parent[x] = leader(parent[x]); // 経路圧縮
    }
    void marge(T x,T y){ // 既存名を維持
        T a=leader(x),b=leader(y);
        if(a==b)return;
        if(rank[a]<rank[b])swap(a,b);
        parent[b]=a;
        rank[a]+=rank[b];
    }
    void merge(T x,T y){marge(x,y);}
    bool same(T x, T y) { // 同じ集合か判定
        return leader(x) == leader(y);
    }
    T size(T x) { // 集合のサイズを取得
        return rank[leader(x)];
    }
    vector<vector<T>> groups(){
        vector<vector<T>> res(parent.size());
        for(T i=0;i<(T)parent.size();i++)res[leader(i)].push_back(i);
        res.erase(remove_if(res.begin(),res.end(),[](const vector<T>&v){return v.empty();}),res.end());
        return res;
    }
    void check(T N) { // デバッグ用: 親の確認
        for (T i = 0; i < N; i++) cout << parent[i] << " ";
        cout << "\n";
    }
};
// SCC
struct SCC {
    //kosaraju法を用いたSCC
    int N;
    // グラフ
    vector<vector<int>> g, rg;

    // Kosaraju 用
    vector<int> comp, order;
    vector<bool> used;

    // 結果
    int scc_count;
    vector<vector<int>> groups;   // 各 SCC に含まれる頂点
    vector<vector<int>> dag;      // 縮約 DAG
    vector<int> sz;               // SCC サイズ
    vector<int> indeg, outdeg;    // DAG の入出力次数

    // --- コンストラクタ ---
    SCC() : N(0) {}
    SCC(int n) { reset(n); }

    void reset(int n) {
        N = n;
        g.assign(N, {});
        rg.assign(N, {});
    }

    void add_edge(int u, int v) {
        g[u].push_back(v);
        rg[v].push_back(u);
    }

    // --- 1回目 DFS（帰りがけ順） ---
    //stackに積む行動
    void dfs1(int v) {
        used[v] = true;
        for (int to : g[v]) {
            if (!used[to]) dfs1(to);
        }
        order.push_back(v);
    }

    // --- 2回目 DFS（逆グラフ） ---
    //stackに積んだものを集合に直す行動
    void dfs2(int v, int c) {
        comp[v] = c;
        groups[c].push_back(v);
        for (int to : rg[v]) {
            if (comp[to] == -1) dfs2(to, c);
        }
    }

    void do_scc() {
        // 1st DFS
        used.assign(N, false);
        order.clear();
        for (int i = 0; i < N; i++) {
            if (!used[i]) dfs1(i);
        }

        // 2nd DFS
        comp.assign(N, -1);
        scc_count = 0;
        groups.clear();

        for (int i = N - 1; i >= 0; i--) {
            int v = order[i];
            if (comp[v] == -1) {
                groups.push_back({});
                dfs2(v, scc_count);
                scc_count++;
            }
        }

        // SCC サイズ
        sz.assign(scc_count, 0);
        for (int i = 0; i < scc_count; i++) {
            sz[i] = (int)groups[i].size();
        }

        // 縮約 DAG 構築
        dag.assign(scc_count, {});
        indeg.assign(scc_count, 0);
        outdeg.assign(scc_count, 0);

        // 重複辺除去
        set<pair<int,int>> seen;
        for (int v = 0; v < N; v++) {
            for (int to : g[v]) {
                int a = comp[v];
                int b = comp[to];
                if (a != b && !seen.count({a, b})) {
                    seen.insert({a, b});
                    dag[a].push_back(b);
                    outdeg[a]++;
                    indeg[b]++;
                }
            }
        }
    }
};
// Fenwick Tree: 0-indexed。add(p,x), sum(l,r)=[l,r)
template<class T>
struct FenwickTree{
    int N=0;vector<T> bit;
    FenwickTree()=default;
    explicit FenwickTree(int n){reset(n);}
    explicit FenwickTree(const vector<T>&A){
        reset((int)A.size());
        for(int i=0;i<N;i++)bit[i+1]+=A[i];
        for(int i=1;i<=N;i++){int j=i+(i&-i);if(j<=N)bit[j]+=bit[i];}
    }
    void reset(int n){N=n;bit.assign(N+1,T{});}
    void add(int p,T x){assert(0<=p&&p<N);for(++p;p<=N;p+=p&-p)bit[p]+=x;}
    T sum(int r)const{assert(0<=r&&r<=N);T res{};for(;r>0;r-=r&-r)res+=bit[r];return res;}
    T sum(int l,int r)const{assert(0<=l&&l<=r&&r<=N);return sum(r)-sum(l);}
    T get(int p)const{return sum(p,p+1);}
    // 累積和がx以上となる最小index。全要素が非負のとき使用
    int lower_bound(T x)const{
        if(x<=T{})return 0;
        int p=0;T s{};int k=1;while((k<<1)<=N)k<<=1;
        for(;k;k>>=1)if(p+k<=N&&s+bit[p+k]<x)s+=bit[p+=k];
        return min(p,N);
    }
};
// Segment Tree
template <class S, S (*op)(S, S), S (*e)()> struct segtree {
    public:
        segtree() : segtree(0) {}
        segtree(int n) : segtree(std::vector<S>(n, e())) {}
        segtree(const std::vector<S>& v) : _n(int(v.size())){
            log = ceil_pow2(_n);
            size = 1 << log;
            d = std::vector<S>(2 * size, e());
            for (int i = 0; i < _n; i++) d[size + i] = v[i];
            for (int i = size - 1; i >= 1; i--) {
                update(i);
            }
        }

        void set(int p, S x) {
            assert(0 <= p && p < _n);
            p += size;
            d[p] = x;
            for (int i = 1; i <= log; i++) update(p >> i);
        }

        S get(int p) {
            assert(0 <= p && p < _n);
            return d[p + size];
        }

        S prod(int l, int r) {
            assert(0 <= l && l <= r && r <= _n);
            S sml = e(), smr = e();
            l += size;
            r += size;

            while (l < r) {
                if (l & 1) sml = op(sml, d[l++]);
                if (r & 1) smr = op(d[--r], smr);
                l >>= 1;
                r >>= 1;
            }
            return op(sml, smr);
        }

        S all_prod() { return d[1]; }

        template <bool (*f)(S)> int max_right(int l) {
            return max_right(l, [](S x) { return f(x); });
        }
        template <class F> int max_right(int l, F f) {
            assert(0 <= l && l <= _n);
            assert(f(e()));
            if (l == _n) return _n;
            l += size;
            S sm = e();
            do{
                while (l % 2 == 0) l >>= 1;
                if (!f(op(sm, d[l]))) {
                    while (l < size) {
                        l = (2 * l);
                        if (f(op(sm, d[l]))) {
                            sm = op(sm, d[l]);
                            l++;
                        }
                    }
                    return l - size;
                }
                sm = op(sm, d[l]);
                l++;
            }while ((l & -l) != l);
            return _n;
        }

        template <bool (*f)(S)> int min_left(int r) {
            return min_left(r, [](S x) { return f(x); });
        }
        template <class F> int min_left(int r, F f) {
            assert(0 <= r && r <= _n);
            assert(f(e()));
            if (r == 0) return 0;
            r += size;
            S sm = e();
            do{
                r--;
                while (r > 1 && (r % 2)) r >>= 1;
                if (!f(op(d[r], sm))) {
                    while (r < size) {
                        r = (2 * r + 1);
                        if (f(op(d[r], sm))) {
                            sm = op(d[r], sm);
                            r--;
                        }
                    }
                    return r + 1 - size;
                }
                sm = op(d[r], sm);
            }while ((r & -r) != r);
            return 0;
        }

    private:
        int _n, size, log;
        std::vector<S> d;

        void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
        int ceil_pow2(int n) {
            int x = 0;
            while ((1U << x) < (unsigned int)(n)) x++;
            return x;
        }
};
// Lazy Segment Tree
template <class S,S (*op)(S, S),S (*e)(),class F,S (*mapping)(F, S),F (*composition)(F, F),F (*id)()>
struct lazy_segtree {

    public:
        lazy_segtree() : lazy_segtree(0) {}
        lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
        lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) {
            log = ceil_pow2(_n);
            size = 1 << log;
            d = std::vector<S>(2 * size, e());
            lz = std::vector<F>(size, id());
            for (int i = 0; i < _n; i++) d[size + i] = v[i];
            for (int i = size - 1; i >= 1; i--) {
                update(i);
            }
        }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        return d[p];
    }

    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return e();

        l += size;
        r += size;

        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push(r >> i);
        }

        S sml = e(), smr = e();
        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }

        return op(sml, smr);
    }

    S all_prod() { return d[1]; }

    void apply(int p, F f) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = mapping(f, d[p]);
        for (int i = 1; i <= log; i++) update(p >> i);
    }
    void apply(int l, int r, F f) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return;

        l += size;
        r += size;

        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        {
            int l2 = l, r2 = r;
            while (l < r) {
                if (l & 1) all_apply(l++, f);
                if (r & 1) all_apply(--r, f);
                l >>= 1;
                r >>= 1;
            }
            l = l2;
            r = r2;
        }

        for (int i = 1; i <= log; i++) {
            if (((l >> i) << i) != l) update(l >> i);
            if (((r >> i) << i) != r) update((r - 1) >> i);
        }
    }

    template <bool (*g)(S)> int max_right(int l) {
        return max_right(l, [](S x) { return g(x); });
    }
    template <class G> int max_right(int l, G g) {
        assert(0 <= l && l <= _n);
        assert(g(e()));
        if (l == _n) return _n;
        l += size;
        for (int i = log; i >= 1; i--) push(l >> i);
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!g(op(sm, d[l]))) {
                while (l < size) {
                    push(l);
                    l = (2 * l);
                    if (g(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <bool (*g)(S)> int min_left(int r) {
        return min_left(r, [](S x) { return g(x); });
    }
    template <class G> int min_left(int r, G g) {
        assert(0 <= r && r <= _n);
        assert(g(e()));
        if (r == 0) return 0;
        r += size;
        for (int i = log; i >= 1; i--) push((r - 1) >> i);
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!g(op(d[r], sm))) {
                while (r < size) {
                    push(r);
                    r = (2 * r + 1);
                    if (g(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

    private:
        int _n, size, log;
        std::vector<S> d;
        std::vector<F> lz;
        int ceil_pow2(int n) {
            int x = 0;
            while ((1U << x) < (unsigned int)(n)) x++;
            return x;
        }
        void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
        void all_apply(int k, F f) {
            d[k] = mapping(f, d[k]);
            if (k < size) lz[k] = composition(f, lz[k]);
        }
        void push(int k) {
            all_apply(2 * k, lz[k]);
            all_apply(2 * k + 1, lz[k]);
            lz[k] = id();
        }
};
// Grid
template<typename T>
void rotate(vector<vector<T>>& ary,bool rev=false){
  if(ary.empty()||ary[0].empty())return;
  int n=ary.size(),m=ary[0].size();
  vector copy(m,vector<T>(n));
  rep(i,n)rep(j,m){
    if(!rev)copy[j][n-i-1]=ary[i][j];
    else copy[m-j-1][i]=ary[i][j];
  }
  ary=copy;
}
// Segment Tree presets

using segS = ll;

segS oop(segS a,segS b){
    return a+b;
}
segS ee(){
    return 0;
}
struct segS2{
    ll sum;
    ll mn;
};
segS2 o3p(segS2 a,segS2 b){
    segS2 res;
    res.sum=a.sum+b.sum;
    res.mn = min(a.mn,a.sum+b.mn);
    return res;
}
segS2 e3(){
    return {0,0};
}
//遅延セグ木のベース
using mint = ModInt<998244353>;
using amint = ModInt<1000000007>;

void print_1D(const vector<ll>&A,bool kaigyou){
    ll N = A.size();
    cout << "----------\n";
    for(int i = 0;i<N;i++){
        cout << A[i] << " ";
        if(kaigyou)cout << "\n";
    }
    cout << "\n";
    cout << "----------\n";
}
void print_2D(const vector<vector<bool>>&A){
    ll N = A.size();
    cout << "----------\n";
    for(int i = 0;i<N;i++){
        for(ll ii=0;ii<(ll)A[i].size();ii++){
            cout << A[i][ii] << " ";
        }
        cout << "\n";
    }
    cout << "----------\n";
}
vector<ll> prefix_1Dsum(const vector<ll>&A){
    ll N = A.size();
    vector<ll>B(N+1);
    for(int i = 0;i<N;i++){
        B[i+1]+=A[i];
        B[i+1]+=B[i];
    }
    return B;
}
vector<vector<ll>> prefix_2Dsum(const vector<vector<ll>>&A){
    ll N = A.size();
    ll M = A[0].size();
    vector<vector<ll>>B(N+1,vector<ll>(M+1));
    for(int i = 0;i<N;i++){
        for(int ii = 0;ii<M;ii++){
            B[i+1][ii+1]+=A[i][ii];
            B[i+1][ii+1]+=B[i+1][ii];
        }
    }
    for(int ii = 0;ii<M;ii++){
        for(int i = 0;i<N;i++){
            B[i+1][ii+1]+=B[i][ii+1];
        }
    }
    return B;
}
ll get_prefix_1Dsum(const vector<ll>&A,ll l,ll r){// 1-indexed, [l,r]
    assert(1<=l&&l<=r&&r<(ll)A.size());
    return A[r]-A[l-1];
}
ll get_prefix_2Dsum(const vector<vector<ll>>&A,ll x1,ll y1,ll x2,ll y2){// 1-indexed, inclusive
    assert(1<=x1&&x1<=x2&&x2<(ll)A.size());
    assert(1<=y1&&y1<=y2&&y2<(ll)A[0].size());
    return A[x2][y2]-A[x1-1][y2]-A[x2][y1-1]+A[x1-1][y1-1];
}
// 実行時間計測（AHCなど）
struct Timer{
    chrono::steady_clock::time_point start_time;
    Timer(){reset();}
    void reset(){start_time=chrono::steady_clock::now();}
    double ms()const{return chrono::duration<double,milli>(chrono::steady_clock::now()-start_time).count();}
    double sec()const{return ms()/1000.0;}
};
struct XorShift64 {
    uint64_t x;
    XorShift64(uint64_t seed=88172645463325252ULL){ x = seed ? seed : 88172645463325252ULL; }
    inline uint64_t next_u64(){
        x ^= x << 13;
        x ^= x >> 7;
        x ^= x << 17;
        return x;
    }
    inline uint32_t next_u32(){ return (uint32_t)next_u64(); }
    inline uint64_t next_int(uint64_t m){assert(m>0);return next_u64()%m;}
    inline ll next_ll(ll l,ll r){assert(l<r);return l+(ll)next_int((uint64_t)(r-l));}
    inline double next_double(){return (double)(next_u64()>>11)*(1.0/9007199254740992.0);} // [0,1), 53-bit
    template<class T>void shuffle_vector(vector<T>&A){for(int i=(int)A.size()-1;i>0;i--)swap(A[i],A[next_int(i+1)]);}
};

// Euler Tour
using S = long long;
S Sum_e(){return 0;}
S Sum_op(S a,S b){return a+b;}

using U = pair<int,int>;
U Min_e(){return {1000000000,1000000000};}
U Min_op(U a,U b){return min(a,b);}

class EulerTour{
    public:
        EulerTour() : n(0),turn(0){}
        explicit EulerTour(const int &_n){
            n = _n;
            turn = 0;
            Graph.assign(n,{});
            vw.assign(n,0);
            finish.assign(n,0);
            discover.assign(n,0);

            init_v_cost1.assign(2*n, 0);
            init_e_cost1.assign(2*n, 0);
            init_v_cost2.assign(2*n, 0);
            init_e_cost2.assign(2*n, 0);
            init_depth_visit.assign(2*n, Min_e());

            v_cost1 = segtree<S, Sum_op, Sum_e>(2*n);
            e_cost1 = segtree<S, Sum_op, Sum_e>(2*n);
            v_cost2 = segtree<S, Sum_op, Sum_e>(2*n);
            e_cost2 = segtree<S, Sum_op, Sum_e>(2*n);
            depth_visit = segtree<U, Min_op, Min_e>(2*n);
        }

        inline void addEdge(const int &u, const int &v, const long long &w){
            Graph[u].emplace_back(pair(v,w));
            Graph[v].emplace_back(pair(u,w));
        }

        inline void addVCost(const int &i,const long long &w){vw[i] = w;}

        inline void changeECost(int u,int v,const long long &nw){
            // ※ Graph自体の更新はしていない
            if(discover[u] > discover[v])swap(u,v);
            // 辺は2回しか通らない → O(logN)で更新可
            e_cost1.set(discover[v],nw);
            e_cost2.set(discover[v],nw);
            e_cost2.set(finish[v],-nw);
        }

        inline S distV(const int &u,const int &v){int a=lca(u,v);return rootV(u)+rootV(v)-2*rootV(a)+vw[a];}
        inline S distE(const int &u,const int &v){int a=lca(u,v);return rootE(u)+rootE(v)-2*rootE(a);}
        inline S partV(const int &root){return v_cost1.prod(discover[root],finish[root]);}
        inline S partE(const int &root){return e_cost1.prod(discover[root]+1,finish[root]);}

        inline int lca(int u, int v){
            if(u == v)return u;
            if(discover[u] > discover[v])swap(u,v);
            return depth_visit.prod(discover[u],finish[v]+1).second;
        }

        inline void build(){
            assert(n>0);
            turn=0;
            fill(init_v_cost1.begin(),init_v_cost1.end(),0);
            fill(init_e_cost1.begin(),init_e_cost1.end(),0);
            fill(init_v_cost2.begin(),init_v_cost2.end(),0);
            fill(init_e_cost2.begin(),init_e_cost2.end(),0);
            fill(init_depth_visit.begin(),init_depth_visit.end(),Min_e());
            dfs(0,-1,0,0);
            v_cost1 = segtree<S, Sum_op, Sum_e>(init_v_cost1);
            e_cost1 = segtree<S, Sum_op, Sum_e>(init_e_cost1);
            v_cost2 = segtree<S, Sum_op, Sum_e>(init_v_cost2);
            e_cost2 = segtree<S, Sum_op, Sum_e>(init_e_cost2);
            depth_visit = segtree<U, Min_op, Min_e>(init_depth_visit);
        }

        int n, turn;
        vector<vector<pair<int,long long>>> Graph;
        segtree<S, Sum_op, Sum_e> v_cost1, e_cost1, v_cost2, e_cost2;
        segtree<U, Min_op, Min_e> depth_visit;
        vector<long long> vw;
        vector<int> discover,finish;

        vector<S> init_v_cost1, init_e_cost1, init_v_cost2, init_e_cost2;
        vector<U> init_depth_visit;

        // 0 → v の頂点・辺cost
        inline long long rootV(const int &v){return v_cost2.prod(0,discover[v]+1);}
        inline long long rootE(const int &v){return e_cost2.prod(1,discover[v]+1);}

        void dfs(const int &now,const int &pre,const long long &w,const int &d){
            // 行きがけ処理
            discover[now] = turn;
            init_depth_visit[turn] = U(d,now);
            init_v_cost1[turn] = vw[now];
            init_v_cost2[turn] = vw[now];
            init_e_cost1[turn] = w;
            init_e_cost2[turn] = w;
            turn++;
            for(auto &&[next,nw]:Graph[now]){
                if(next == pre)continue;
                dfs(next,now,nw,d+1);
            }
            // 帰りがけ処理
            finish[now] = turn;
            if(pre != -1)init_depth_visit[turn] = U(d-1,pre);
            init_v_cost1[turn] = 0;
            init_e_cost1[turn] = 0;
            init_v_cost2[turn] = -vw[now];
            init_e_cost2[turn] = -w;
            turn++;
        }
};
vector<long long> divisor(long long n) {
    vector<long long> ret;
    for (long long i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            ret.push_back(i);
            if (i * i != n) ret.push_back(n / i);
        }
    }
    sort(ret.begin(), ret.end()); // 昇順に並べる
    return ret;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string S;
    cin >> S;
    if(S.size()==1&&(S[0]=='2')){
        cout << "0" << "\n";
        Yes;
        rtr0;
    }
    if((S[S.size()-1]-'0')%2==0){
        cout << 0 << "\n";
    }
    else{
        cout << 1 << "\n";
    }
    No;
    return 0;
}