#include <cstdio>
#include <cstdlib>
#include <cstdarg>
#include <cstring>
#include <vector>
#include <queue>
#include <list>
#include <string>
#include <ext/pb_ds/priority_queue.hpp>
#include <deque>
#include <set>
#include <map>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <climits>
#include <functional>
#include <cctype>
using namespace std;

#define MAXN 2333
class dinic
{
private:
   bool vis[MAXN];
   int dist[MAXN];
   int cure[MAXN];
   vector<int> G[MAXN];
   struct edge
   {
       int from, to, rem;
   };
   int s, t;
   vector<edge> edges;
public:
    dinic(int fr, int to)
    {
        s = fr;
        t = to;
    }
    void addedge(int u, int v, int c)
    {
        edges.push_back((edge){u, v, c});
        edges.push_back((edge){v, u, 0});
        int k = edges.size();
        G[u].push_back(k-2);
        G[v].push_back(k-1);
    }
    bool bfs()
    {
        memset(vis, 0, sizeof(vis));
        queue<int> q;
        q.push(s);
        vis[s] = true;
        dist[s] = 0;
        while(q.size())
        {
            int c = q.front();
            q.pop();
            for(int i = 0; i < G[c].size(); i++)
            {
                edge &e = edges[G[c][i]];
                if(!vis[e.to] && e.rem > 0)
                {
                    vis[e.to] = true;
                    dist[e.to] = dist[c] + 1;
                    q.push(e.to);
                }
            }
        }
        return vis[t];
    }
    int dfs(int x, int f)
    {
        if(f == 0 || x == t)return f;
        int tot = 0;
        int nt;
        for(int &i = cure[x]; i < G[x].size(); i++)
        {
            edge &e = edges[G[x][i]];
            if(dist[e.to] == dist[x] + 1 && (nt = dfs(e.to, min(f, e.rem))) > 0)
            {
                f -= nt;
                tot += nt;
                e.rem -= nt;
                edges[G[x][i]^1].rem += nt;
                if(f == 0)break;
            }
        }
        return tot;
    }
    int maxf()
    {
        int f = 0;
        while(bfs())
        {
            memset(cure, 0, sizeof(cure));
            f += dfs(s, 0x7fffffff);
        }
        return f;
    }
};
#define MAXM 10001
class MCMF
{
    struct edge
    {
        int from, to;
        int rem, cost;
    };
    int s, t;
    int cost[MAXM];
    int path[MAXM];
    int flow[MAXM];
    bool vis[MAXM];
    vector<int> G[MAXM];
    vector<edge> edges;
public:
    MCMF(int a, int b)
    {
        s = a;
        t = b;
    }
    void addedge(int f, int t, int c, int v)
    {
        edges.push_back((edge){f, t, c, v});
        edges.push_back((edge){t, f, 0, -v});
        int k = edges.size();
        G[f].push_back(k-2);
        G[t].push_back(k-1);
    }
    bool spfa(int &fl, int &ct)
    {
        queue<int> q;
        memset(vis, false, sizeof(vis));
        memset(cost, 0x3f, sizeof(cost));
        memset(flow, 0x3f, sizeof(flow));
        vis[s] = true;
        flow[s] = 0x3f3f3f3f;
        cost[s] = 0;
        q.push(s);
        while(q.size())
        {
            int c = q.front();
            q.pop();
            for(int i = 0; i < G[c].size(); i++)
            {
                edge &e = edges[G[c][i]];
                if(e.rem > 0 && cost[e.to] > cost[c] + e.cost)
                {
                    cost[e.to] = cost[c] + e.cost;
                    path[e.to] = G[c][i];
                    flow[e.to] = min(flow[c], e.rem);
                    if(!vis[e.to])
                    {
                        q.push(e.to);
                        vis[e.to] = true;
                    }
                }
            }
            vis[c] = false;
        }
        if(cost[t] == 0x3f3f3f3f)return false;
        fl += flow[t];
        ct += cost[t] * flow[t];
        for(int cur = t; cur != s; cur = edges[path[cur]].from)
        {
            int p = path[cur];
            edges[p].rem -= flow[t];
            edges[p^1].rem += flow[t];
        }
        return true;
    }
    int mcmf(int &c)
    {
        int f = 0;
        c = 0;
        while(spfa(f, c));
        return f;
    }
};
#define NEXT_SIZE 16
typedef struct trieNodeType
{
    bool isFinal;
    struct trieNodeType *(*next);
}trieNode, *pTrieNode;

typedef struct trieType
{
    trieNode *root;
}trie;

void initTrie(trie *t)
{
    t -> root = (trieNode *)malloc(sizeof(trieNode));
    memset(t -> root, 0, sizeof(trieNode));
}
trieNode *appendChar(trieNode *d, int t)
{
    if(!d -> next)
    {
        d -> next = (pTrieNode *)malloc(sizeof(pTrieNode) * NEXT_SIZE);
        memset(d -> next, 0, sizeof(pTrieNode) * NEXT_SIZE);
    }
    if(!d -> next[t])
    {
        d -> next[t] = (pTrieNode)malloc(sizeof(trieNode));
        memset(d -> next[t], 0, sizeof(trieNode));
    }
    return d -> next[t];
}
void insertWord(trie *t, char *w, int len)
{
    trieNode *fw = t -> root;
    for(int i = 0; i < len; i++)
    {
        unsigned char c = w[i];
        unsigned hw = (c & (unsigned char)0xf0)>>4;   //高四位
        unsigned lw = c & (unsigned char)0x0f;        //低四位
        fw = appendChar(fw, hw);
        fw = appendChar(fw, lw);
    }
    fw -> isFinal = true;
}
bool existWord(trie *t, char *w, int len)
{
    trieNode *fw = t -> root;
    for(int i = 0; i < len; i++)
    {
        if(!fw -> next)
            return false;
        unsigned char c = w[i];
        unsigned hw = (c & (unsigned char)0xf0)>>4;
        unsigned lw = c & (unsigned char)0x0f;
        if(fw -> next[hw])
            fw = fw -> next[hw];
        else return false;
        if(fw -> next[lw])
            fw = fw -> next[lw];
        else return false;
        if(!fw)return false;
    }
    return fw -> isFinal;
}
void destroyTrieNodes(pTrieNode d)
{
    if(!d)return;
    if(!d -> next)return;
    for(int i = 0; i < NEXT_SIZE; i++)
        if(d -> next[i])destroyTrieNodes(d -> next[i]);
    for(int i = 0; i < NEXT_SIZE; i++)
        if(d -> next[i])free(d -> next[i]);
    free(d -> next);
}
void destroyTrie(trie *t)
{
    destroyTrieNodes(t -> root);
}

typedef struct _AVL
{
    struct _AVL *left, *right;
    int data;
    int height;
    int size;
}AVLNode, *pNode, *AVLTree;
#define HEIGHT(x) ((x)?(x)->height:-1)
#define SIZE(x) ((x)?(x)->size:0)
void maintain(pNode k)
{
    if(k)
    {
        k -> height = max(HEIGHT(k -> left), HEIGHT(k -> right)) + 1;
        k -> size = SIZE(k -> left) + SIZE(k -> right) + 1;
    }
} 
pNode singleRotateLL(pNode k)
{
    pNode k1 = k -> left;
    k -> left = k1 -> right;
    k1 -> right = k;
    maintain(k);
    maintain(k1);
    return k1;
}
pNode singleRotateRR(pNode k)
{
    pNode k1 = k -> right;
    k -> right = k1 -> left;
    k1 -> left = k;
    maintain(k);
    maintain(k1);
    return k1;
}
pNode doubleRotateLR(pNode k)
{
    k -> left = singleRotateRR(k -> left);
    return singleRotateLL(k);
}
pNode doubleRotateRL(pNode k)
{
    k -> right = singleRotateLL(k -> right);
    return singleRotateRR(k);
}
AVLTree insert(AVLTree t, int x)
{
    if(!t)
    {
        t = new AVLNode;
        t -> data = x;
        t -> size = 1;
        t -> left = t -> right = 0;
    }else
    {
        if(x < t -> data)   
        {
            t -> left = insert(t -> left, x);
            if(HEIGHT(t -> left) - HEIGHT(t -> right) == 2)
            {
                if(x < t -> left -> data)
                    t = singleRotateLL(t); 
                else    
                    t = doubleRotateLR(t);    
            }
        }else 
        {
            t -> right = insert(t -> right, x);
            if(HEIGHT(t -> right) - HEIGHT(t -> left) == 2)
            {
                if(x >= t -> right -> data)
                    t = singleRotateRR(t);
                else
                    t = doubleRotateRL(t);
            }
        }
    }
    maintain(t);
    return t;
}
pNode delBalance(pNode k)
{
    if(HEIGHT(k -> right) - HEIGHT(k -> left) == 2)
    {
        if(k -> right)
        {
            if(HEIGHT(k -> right -> right) >= HEIGHT(k -> right -> left))
                k = singleRotateRR(k);
            else
                k = doubleRotateRL(k);
        }
    }
    if(HEIGHT(k -> left) - HEIGHT(k -> right) == 2)
    {
        if(k -> left)
        {
            if(HEIGHT(k -> left -> left) >= HEIGHT(k -> left -> right))
                k = singleRotateLL(k); 
            else
                k = doubleRotateLR(k);
        }
    }
    #define put0 main
    maintain(k);
    return k;
}
AVLTree delNode(AVLTree t, int x)
{
    if(!t)
        return NULL;
    if(x == t -> data)
    {
        if(!t -> right)
        {
            pNode tmp = t;
            t = t -> left;
            free(tmp);
        }else
        {
            pNode tmp = t -> right;
            while(tmp -> left)
                tmp = tmp -> left;
            t -> data = tmp -> data;
            t -> right = delNode(t -> right, t -> data);
        }
        maintain(t);
        return t;
    }
    if(x < t -> data)
    {
        t -> left = delNode(t -> left, x);
    }else
    {
        t -> right = delNode(t -> right, x);
    }
    if(t -> left)
        t -> left = delBalance(t -> left);
    if(t -> right)
        t -> right = delBalance(t -> right);
    if(t)
        t = delBalance(t);
    return t;
}

int Smaller(pNode t, int x)
{
    if(!t)return 0;
    if(x < t -> data)
        return Smaller(t -> left, x);
    else
        return 1 + SIZE(t -> left) + Smaller(t -> right, x);
}

int last = 0;
struct _SegNode
{
    int ls, rs;   
    AVLTree rt;  
    int l, r;  
}ns[MAXN<<1];
int data[MAXN];
int build(int l, int r)
{
    int cur = ++last;
    ns[cur].l = l;
    ns[cur].r = r;
    ns[cur].rt = NULL;

    for(int i = l; i <= r; i++) 
        ns[cur].rt = insert(ns[cur].rt, data[i]);
    if(l == r)
        return cur;
    int mid = (l+r)>>1;
    if(l <= mid)
    {
        ns[cur].ls = build(l, mid);
        ns[cur].rs = build(mid+1, r);
    }
    return cur;
}

int queryTree(int c, int l, int r, int n)
{
    if(ns[c].l == l && ns[c].r == r)
        return Smaller(ns[c].rt, n);  
    int ls= ns[c].ls;
    int rs = ns[c].rs;
    if(r <= ns[ls].r)  
        return queryTree(ls, l, r, n);
    else if(l >= ns[rs].l) 
        return queryTree(rs, l, r, n);
    else  
        return queryTree(ls, l, ns[ls].r, n) + queryTree(rs, ns[rs].l, r, n);
}

void update(int c, int pos, int v)
{ 
    ns[c].rt = delNode(ns[c].rt, data[pos]);   
    ns[c].rt = insert(ns[c].rt, v);            
    int ls = ns[c].ls;
    int rs = ns[c].rs;
    if(ls && pos >= ns[ls].l && pos <= ns[ls].r) 
        update(ls, pos, v);
    else if(rs && pos >= ns[rs].l && pos <= ns[rs].r)
        update(rs, pos, v);
}
void change(int pos, int v)
{
    update(1, pos, v);
    data[pos] = v;   
}
int solve(int l, int r, int k)
{
    int x = 0;
    int y = 0x7fffffff;   
    int ans = 0;
    while(x <= y)
    {
        int mid = (x+y)>>1;
        int f = queryTree(1, l, r, mid); 
        if(f >= k)    
        {
            y = mid-1;
            ans = mid;
        }
        else
            x = mid+1;
    }
    return ans;
}
#include <cstdio>
#include <cstring>
using namespace std;
#define ALPHA 26
#define BASE 'a'
class SAM
{
    int last, size;
    public:
    struct state
    {
        int len, link;
        int next[ALPHA];
        int fast, fast_len; 
        bool mark;
        void init()
        {
            len = fast = fast_len = 0;
            link = -1;
            mark = false;
            memset(next, 0, sizeof(next));
        }
    }st[MAXN << 1];
    int newst()
    {
        st[size++].init();
        return size-1;
    }
    SAM()
    {
        last = size = 0;
        newst();
    }
    void expand(int c)
    {
        int cur = newst();
        st[cur].len = st[last].len + 1;
        int p;
        for(p = last; p != -1 && !st[p].next[c]; p = st[p].link)
            st[p].next[c] = cur;
        if(p == -1)st[cur].link = 0;
        else
        {
            int q = st[p].next[c];
            if(st[q].len == st[p].len + 1)st[cur].link = q;
            else
            {
                int clone = newst();
                st[clone].len = st[p].len+1;
                st[clone].link = st[q].link;
                memcpy(st[clone].next, st[q].next, sizeof(st[clone].next));
                for(; p != -1 && st[p].next[c] == q; p = st[p].link)
                    st[p].next[c] = clone;
                st[q].link = st[cur].link = clone;
            }
        }
        last = cur;
    }
    void mark_suffix() 
    {
        for(int p = last; p != -1; p = st[p].link)
            st[p].mark = true;
    }
    void calc_fast()
    {
        for(int p = 0; p < size; p++)
        {
            int q, f = 0;
            for(int i = 0; i < ALPHA; i++)
            {
                if(st[p].next[i])
                {
                    f++;
                    q = st[p].next[i];
                }
            }
    
            if(f == 1 && !st[p].mark)
            {
                st[p].fast = q;
                st[p].fast_len = 1;
            }
        }
    }
    int fast_go(int s)
    {
                
        int p, sum = 0;
        for(p = s; st[p].fast; p = st[p].fast)
            sum += st[p].fast_len;           
                   
        for(int q = s; st[q].fast; q = st[q].fast)
        {
            sum -= st[q].fast_len;
            st[q].fast = p;
            st[q].fast_len += sum;          
        }
        return p;    
    }
    int top;
    int *psa;
    void dfs(int u, int d)
    {
        if(st[u].mark)psa[top++] = d;  
        for(int i = 0; i < ALPHA; i++) 
        {
            if(st[u].next[i])   
            {
                state &go = st[st[u].next[i]];
                fast_go(st[u].next[i]); 
                if(go.fast)  
                    dfs(go.fast, d-1-go.fast_len);  
                else
                    dfs(st[u].next[i], d-1);  
            }
        }
    }
    void buildSA(int len, int *buf)
    {
          
        mark_suffix();
        calc_fast();
        top = 0;
        psa = buf;
        dfs(0, len);
    }
}sam;
int f(){freopen("ha14c.in", "r", stdin);freopen("ha14c.out", "w", stdout);}
int sa[MAXN];
char buf[MAXN];
int height[MAXN];
int rank[MAXN];
void calc_height(int n)
{
    char *p = buf-1;
    for(int i = 1; i <= n; i++)
        rank[sa[i]] = i;
    int k = 0;
    for(int i = 1; i <= n; i++)
    {
        if(k)k--;
        int j = sa[rank[i]-1];
        while(p[i+k] == p[j+k])k++;
        height[rank[i]] = k;
    }
}
int put0(){puts("0");}
class Bignum
{
    void mknum(const char *s, int len = -1)
    {
        sign = 0;
        if(*s == '-')
        {
            mknum(s+1);
            sign = 1;
            return;
        }
        int l;
        if(len == -1)
            l = strlen(s);
        else
            l = len;
        l = strlen(s);
        bits.clear();
        bits.resize(l);
        for(int i = l-1; i >= 0; i--)
            bits[l-i-1] = s[i] - '0';
        maintain();
    }
    void mknum(string &s)
    {
        mknum(s.c_str(), s.length());
    }

    void us_addto(Bignum &b)  
    {
        int mlen = max(b.bits.size(), bits.size());
        int slen = bits.size();
        int olen = b.bits.size();
        bits.resize(mlen);
        for(int i = 0; i < mlen; i++)
        {
            int s = 0;
            if(i < slen)s += bits[i];
            if(i < olen)s += b.bits[i];
            bits[i] = s;
        }
        maintain();
    }
    class FFTer
    {
        class Complex
        {
        public:
            double real, image;
            Complex(double a = 0, double b = 0)
            {
                real = a;
                image = b;
            }
            Complex operator + (const Complex &o){return Complex(real+o.real, image+o.image);}
            Complex operator - (const Complex &o){return Complex(real-o.real, image-o.image);}
            Complex operator * (const Complex &o){return Complex(real*o.real-image*o.image, real*o.image+o.real*image);}
            Complex operator * (double k){return Complex(real*k, image*k);}
            Complex operator / (double k){return Complex(real/k, image/k);}
        };
        public:
        vector<Complex> a;  
        int n;               
        FFTer(vector<int> &vec)
        {
            a.resize(vec.size());
            for(int i = 0; i < vec.size(); i++)
                a[i].real = vec[i];
            n = vec.size();
        }
        void transform()
        {
            int j = 0;
            int k;
            for(int i = 0; i < n; i++)
            {
                if(j > i)swap(a[i], a[j]);
                k = n;
                while(j & (k >>= 1))j &= ~k;
                j |= k;
            }
        }
        void FFT(bool IDFT = false)
        {
            const double Pi = IDFT?-acos(-1.0):acos(-1.0);
                         
            transform();   
            for(int s = 1; s < n; s <<= 1)
            {    
                for(int t = 0; t < n; t += s<<1)
                {
            
                    double x = Pi/s;
                    Complex omgn(cos(x), sin(x));
                    Complex omg(1.0, 0.0);    
                    for(int m = 0; m < s; m++)
                    {            
                        int a1 = m+t;
                        int a2 = m+t+s;   
            
                        Complex comm = omg * a[a2];
                        a[a2] = a[a1] - comm;
                        a[a1] = a[a1] + comm;  
                        omg = omg * omgn;
                    }
                }
            }
            if(IDFT)
                for(int i = 0; i < n; i++)
                    a[i] = a[i] / n;
        }
        void mul(FFTer &o)
        {
            int s = 1;
            while(s < n + o.n)s <<= 1;
            n = o.n = s;
            a.resize(s);
            o.a.resize(s);

            FFT(false);
            o.FFT(false);
            for(int i = 0; i < n; i++)
                a[i] = a[i] * o.a[i];
            FFT(true);
        }
    };
    void us_multo(Bignum &b)
    {
        FFTer x(bits);
        FFTer y(b.bits);
        x.mul(y);
        bits.clear();
        bits.resize(x.a.size());
        for(int i = 0; i < x.n; i++)
            bits[i] = (int)(x.a[i].real+0.5);
        maintain();
    }
    void us_multo_simu(Bignum &b)
    {
        vector<int> r;
        r.resize(max(length(),b.length())<<1);
        for(int i = 0; i < length(); i++)
            for(int j = 0; j < b.length(); j++)
                r[i+j] += bits[i] * b.bits[j];
        *(&(this -> bits)) = r;
        maintain();
    }
    void us_subto(Bignum &b)
    {
        int mlen = length();
        int olen = b.length();
        for(int i = 0; i < mlen; i++)
        {
            int s = bits[i];
            if(i < olen)s -= b.bits[i];
            bits[i] = s;
            if(bits[i] < 0)
            {
                bits[i] += 10;
                bits[i+1] -= 1;
            }
        }
        for(int i = bits.size() - 1; !bits[i] && i >= 1; i--)bits.pop_back();
        if(bits.size() == 1 && bits[0] == 0)sign = 0;
    }
    void us_divto(Bignum &b)
    {
        if(length() == 1 && bits[0] == 0)return;
        Bignum L("0");
        L.sign = 0;
        Bignum R(*this);
        R.sign = 0;
        Bignum two("2");
        R *= two;
        Bignum one("1");
        one.sign = 0;
        while(L + one != R)
        {
            Bignum M = L+R;
            M.divto2();
            Bignum t = M*b;
            if(t > *this)
            {
                R = M;
            }else if(t < *this)
            {
                L = M;
            }else
            {
                *this = M;
                L = M;
                break;
            }
        }
        *this = L;
    }
public:
    int sign;
    vector<int> bits;
    int length()
    {
        return bits.size();
    }
    void maintain()
    {
        for(int i = 0; i < bits.size(); i++)
        {
            if(i + 1 < bits.size())
                bits[i+1] += bits[i]/10;
            else if(bits[i] > 9)
                bits.push_back(bits[i]/10);
            bits[i] %= 10;
        }
        if(bits.size() == 0)
        {
            bits.push_back(0);
            sign = 0;
        }
        for(int i = bits.size() - 1; !bits[i] && i >= 1; i--)bits.pop_back();
    }

    Bignum(string &s)
    {
        Bignum();
        mknum(s);
    }
    Bignum(const char *s)
    {
        Bignum();
        mknum(s);
    }
    Bignum(int n)
    {
        Bignum();
        char buf[15];
        sprintf(buf, "%d", n);
        mknum(buf);
    }
    Bignum()
    {
        sign = 0;
        bits.push_back(0);
    }
    Bignum(const Bignum& b) 
    {
        copy(b);
    }
    void copy(const Bignum& b)
    {
        sign = b.sign;
        bits = b.bits;
    }

    bool us_cmp(Bignum &b)   
    {
        if(length() != b.length())return false;
        int l = length();
        for(int i = 0; i < l; i++)
            if(bits[i] != b.bits[i])
                return false;
        return true;
    }
    bool us_larger(Bignum &b)
    {
        if(length() > b.length())return true;
        else if(length() < b.length())return false;
        int l = length();
        for(int i = l-1; i >= 0; i--)
            if(bits[i] > b.bits[i])
                return true;
            else if(bits[i] < b.bits[i])
                return false;
        return false;
    }
    bool operator== (Bignum &o)
    {
        if(sign != o.sign)
            return false;
        return us_cmp(o);
    }
    bool operator!= (Bignum &o)
    {
        return !(*this == o);
    }
    bool operator> (Bignum &o)
    {
        if(sign == 0 && o.sign == 1)return true;
        if(sign == 1 && o.sign == 0)return false;
        if(sign == o.sign && sign)return !us_larger(o);
        return us_larger(o);
    }
    bool operator< (Bignum &o)
    {
        return !(*this == o || *this > o);   
    }
    bool operator<= (Bignum &o)
    {
        return *this < o || *this == o;
    }
    bool operator>= (Bignum &o)
    {
        return *this > o || *this == o;
    }

// -------------------------------
    Bignum& operator+= (Bignum &o)
    {
        if(!sign && !o.sign)
        {
            us_addto(o);
            sign = 0;
        }
        else if(sign && o.sign)
        {
            us_addto(o);
            sign = 1;
        }
        else if(sign && !o.sign)
        {
            if(o.us_larger(*this))
            {
                Bignum t(o);
                t.us_subto(*this);
                *this = t;
                sign = 0;
            }else
            {
                us_subto(o);
                sign = 1;
                if(bits.size() == 1 && bits[0] == 0)sign = 0;
            }
        }else if(!sign && o.sign)
        {
            if(us_larger(o))
            {
                us_subto(o);
                sign = 0;
            }else
            {
                Bignum t(o);
                t.us_subto(*this);
                *this = t;
                sign = 1;
                if(bits.size() == 1 && bits[0] == 0)sign = 0;
            }
        }
        return *this;
    }
    Bignum operator+ (Bignum &o)
    {
        Bignum t(*this);
        t += o;
        return t;
    }

    Bignum& operator*= (Bignum &o)
    {
        if(length() + o.length() > 800)
            us_multo(o);                 
        else
            us_multo_simu(o);             
        if(sign == o.sign)sign = 0;
        else sign = 1;
        return *this;
    }
    Bignum operator* (Bignum &o)
    {
        Bignum t(*this);
        t *= o;
        return t;
    }

    Bignum& operator-= (Bignum &o)
    {
        if(!sign && !o.sign) 
        {
            if(us_larger(o))
            {
                us_subto(o);
                sign = 0;
            }
            else
            {
                Bignum t(o);
                t.us_subto(*this);
                *this = t;
                sign = 1;
                if(bits.size() == 1 && bits[0] == 0)sign = 0;
            }
        }else if(sign && o.sign)
        {
            if(us_larger(o))
            {
                us_subto(o);
                sign = 1;
                if(bits.size() == 1 && bits[0] == 0)sign = 0;
            }else
            {
                Bignum t(o);
                t.us_subto(*this);
                *this = t;
                sign = 0;
            }
        }else if(!sign && o.sign)
        {
            us_addto(o);
            sign = 0;
        }else if(sign && !o.sign)
        {
            us_addto(o);
            sign = 1;
        }
        return *this;
    }
    Bignum operator- (Bignum &o)
    {
        Bignum t(*this);
        t -= o;
        return t;
    }

    Bignum& divto2()
    {
        if(!bits.size())return *this;
        bits[0] >>= 1;
        int i;
        for(i = 1; i < bits.size(); i++)
        {
            if(bits[i] & 1)bits[i-1] += 5;
            bits[i] >>= 1;
        }
        if(bits[i-1] == 0)bits.pop_back();
        return *this;
    }
    Bignum& operator/= (Bignum &o)
    {
        us_divto(o);
        if(sign == o.sign)sign = 0;
        else sign = 1;
        return *this;
    }
    Bignum operator/ (Bignum &o)
    {
        Bignum t(*this);
        t /= o;
        return t;
    }

    Bignum abs()
    {
        Bignum t(*this);
        t.sign = 0;
        return t;
    }


    Bignum sqrt()
    {
        Bignum L("0"), R(*this);
        Bignum one("1");
        Bignum m, t;
        while(L + one != R)
        {
            m = L+R;
            m.divto2();
            Bignum t = m*m;
            if(t == *this)return m;
            else if(t > *this)R = m;
            else L = m;
        }
        return L;
    }


    Bignum pow(Bignum &e)
    {
        if(e.sign)return 1;
        Bignum ans("1");
        Bignum base(*this);
        Bignum zero("0");
        Bignum exp(e);
        while(exp > zero)
        {
            if(exp.bits[0] & 1)
            {
                ans *= base;
            }
            base *= base;
            exp.divto2();
        }
        if(sign && e.bits[0] & 1)ans.sign = 1;
        return ans;
    }

    Bignum log(Bignum &base)
    {
        if(sign)return 0;
        if(length() == 1 && bits[0] == 1)return 0;
        if(*this <= base)return 1;
        Bignum one("1");

        Bignum r("1");
        Bignum c("0");
        while(r < *this)
        {
            r *= base;
            c += one;
        }
        if(r != *this)c -= one; 
        return c;
    }
    Bignum lg()
    {
        Bignum ten("10");
        return log(ten);
    }

    Bignum factorial()
    {
        Bignum r("1");
        Bignum zero("0");
        Bignum one("1");
        Bignum t(*this);
        while(t > zero)
        {
            r *= t;
            t -= one;
        }
        return r;
    }

// -----------------------------------    
    friend istream& operator>>(istream &is, Bignum &b)
    {
        string s;
        is >> s;
        b.mknum(s);
        return is;
    }
    friend ostream& operator<<(ostream &os, Bignum b)
    {
        if(b.sign)os << '-';
        for(int i = b.bits.size()-1; i >= 0; i--)os << b.bits[i];
        return os;
    }

    string to_string()
    {
        int sz = length();
        string s;
        if(sign)
            s.resize(sz+1);
        else
            s.resize(sz);
        int i = 0;
        if(sign)s[i++] = '-';
        for(int j = sz-1; i < sz+sign; i++, j--)
            s[i] = bits[j] + '0';
        return s;
    }    
};
const int MOD = (479<<21)+1;   
const int G = 3;    
typedef long long LL;
LL quick_pow(LL a, LL b)
{
    LL res = 1;
    LL base = a%MOD;
    while(b)
    {
        if(b & 1)
        {
            res *= base;
            res %= MOD;
        }
        b >>= 1;
        base *= base;
        base %= MOD;
    }
    return res;
}

LL omg[MAXM+1];

void calcOmg()
{
    for(int i = 0; i <= MAXM; i++)
    {
        int k = 1 << i;
        omg[i] = quick_pow(G, (MOD-1)/k);
    }
}

class NTTer
{
public:
    LL a[MAXN];
    LL len;
    void trans()
    {
        int j = len >> 1;
        for(int i = 1; i < len-1; i++)
        {
            if(i < j)swap(a[i], a[j]);
            int k = len >> 1;
            while(j >= k)
            {
                j -= k;
                k >>= 1;
            }
            if(j < k)j += k;
        }
    }
    void NTT(bool DNTT = false)
    {
        trans();
        int id = 0;
        for(int h = 2; h <= len; h <<= 1)
        {
            id++;
            for(int j = 0; j < len; j += h)
            {
                LL omgn = 1;
                for(int k = j; k < j + h/2; k++)
                {
                    LL u = a[k] % MOD;
                    LL t = omgn * a[k + h/2] % MOD;
                    a[k] = (u+t)%MOD;
                    a[k+h/2] = (u-t+MOD)%MOD;
                    omgn = omgn*omg[id]%MOD;
                }
            }
        }
        if(DNTT)
        {
            for(int i = 1; i < len/2; i++)
                swap(a[i], a[len-i]);
            LL inv = quick_pow(len, MOD-2);
            for(int i = 0; i < len; i++)
                a[i] = a[i] * inv % MOD;
        }
    }
    void mul(NTTer &o)
    {
        int s = 1;
        while(s < len+o.len) s<<=1;
        len = o.len = s;
        NTT(false);
        o.NTT(false);
        for(int i = 0; i < len; i++)
            a[i] = a[i]*o.a[i]%MOD;
        NTT(true);
    }    
};
bool vis[MAXN];
int primes[MAXN];
int miu[MAXN];
int k = f();
int calc(int limit)
{
    memset(vis, false, sizeof(vis));
    memset(miu, 0, sizeof(miu));
    int tot = 0;
    miu[1] = 1;   
    for(int i = 2; i <= limit; i++)
    {
        if(!vis[i])  
        {
            primes[tot++] = i;
            miu[i] = -1;
         
        }
        for(int j = 0; j < tot; j++)
        {
            int k = i*primes[j];   
            if(k > limit)break;
            vis[k] = true;
            if(i % primes[j]) 
                miu[k] = -miu[i];     
            else                      
                break;                
        }
    }
}