#include <algorithm>
#include <iostream>
#include <set>
#include <vector>
using namespace std;

bool is_seq_arithmetic(vector<long long> V) {
    sort( V.begin(), V.end() );
    long long D = V[1] - V[0];
    for (int i=0; i<int(V.size()); ++i) if (V[i] != V[0] + i*D) return false;
    return true;
}

int main() {
    vector<long long> ages(6);
    for (long long &x : ages) cin >> x;
    sort( ages.begin(), ages.end() );
    vector<long long> possible_differences = { ages[1] - ages[0], ages[2] - ages[1] };
    set<long long> answers;
    for (long long d : possible_differences) for (long long x : ages) for (long long add : vector<long long>{x-d,x+d}) if (add > 0) {
        vector<long long> new_ages = ages;
        new_ages.push_back(add);
        if (is_seq_arithmetic(new_ages)) answers.insert(add);
    }
    for (long long x : answers) cout << x << endl;
}

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

const long long MOD = 1000000007;

int main() {
    int N;
    cin >> N;
    vector<int> S(N);
    for (int &s : S) cin >> s;

    vector<int> cycle_count(N+1,0);
    vector<bool> seen(N,false);

    for (int n=0; n<N; ++n) if (!seen[n]) {
        seen[n] = true;
        int clen = 1, where = n;
        while (true) {
            where = S[where];
            if (seen[where]) break;
            seen[where] = true;
            ++clen;
        }
        ++cycle_count[clen];
    }

    long long answer = 1;

    for (int len=1; len<=N; ++len) if (cycle_count[len]>0) {
        int cnt = cycle_count[len];
        vector<int> groups;
        if (len%2) groups = {1,2,4}; else groups = {4};
        vector<long long> dp(cnt+1,0);
        dp[0] = 1;
        for (int c=1; c<=cnt; ++c) {
            for (int g : groups) if (g <= c) {
                long long curr = 1;
                for (int j=0; j<g-1; ++j) curr = (curr * (c-1-j)) % MOD;
                for (int j=0; j<g-1; ++j) curr = (curr * len) % MOD;
                dp[c] = (dp[c] + curr * dp[c-g]) % MOD;
            }
        }
        answer = (answer * dp[cnt]) % MOD;
    }
    cout << answer << endl;
}

#include <vector>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cmath>
using namespace std;

#define x first
#define y second
typedef std::pair<int,int> pii; typedef long long ll; typedef unsigned int ui; 

template <typename T, typename U> std::istream&operator>>(std::istream&i, pair<T,U>&p) {i >> p.x >> p.y; return i;}
template<typename T>std::istream&operator>>(std::istream&i,vector<T>&t) {for(auto&v:t){i>>v;}return i;}


constexpr double PI = 3.14159265358979323846;
template <typename T> struct Segment;

template <typename T> struct Point : public pair<T,T> {
    using pair<T,T>::x;
    using pair<T,T>::y;

    Point(T a=0,T b=0) : pair<T,T>(a,b) {}
    Point(const pair<T,T> &p) : pair<T,T>(p.x,p.y) {}
    Point(const Point<T>&p) = default;
    Point<T>& operator=(const Point<T>&p) = default;

    Point<T>& operator-=(const Point<T>&p) { x -= p.x; y -= p.y; return *this; }
    Point<T>& operator+=(const Point<T>&p) { x += p.x; y += p.y; return *this; }
    Point<T>& operator*=(T f) { x *= f; y *= f; return *this; }
    Point<T> operator-(const Point<T>&p) const { Point<T> t(*this); t -= p; return t; }
    Point<T> operator+(const Point<T>&p) const { Point<T> t(*this); t += p; return t; }
    Point<T> operator*(T f) const { Point<T> t(*this); t *= f; return t; }

    T squaredDistance(const Point<T>&o) const { return Segment<T>{*this,o}.squaredLength(); }
    long double distance(const Point<T>&o) const { return Segment<T>{*this,o}.length(); }
};

// >0 left turn, <0 right turn, =0 straight
template <typename T> T ccw(const Point<T>&a, const Point<T>&b, const Point<T>&c) { return (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x); }
template <typename T> double cosangle(const Point<T>&a, const Point<T> &b, const Point<T> &c) {
    return (double)((b.x-a.x)*(c.x-a.x) + (b.y-a.y)*(c.y-a.y)) / a.distance(b) / a.distance(c);
}

template <typename T> double angle(const Point<T>&a, const Point<T> &b, const Point<T> &c) {
    return acos(cosangle(a,b,c));
}
template <typename T> int orientation(const Point<T>&a, const Point<T>&b, const Point<T>&c) { auto o = ccw(a,b,c); return (o>1e-6)-(o<-1e-6); }

template <typename T> struct Segment : public pair<Point<T>,Point<T>> {
    using pair<Point<T>,Point<T>>::x;
    using pair<Point<T>,Point<T>>::y;
    explicit Segment(Point<T> a={0,0}, Point<T> b={0,0}) : pair<Point<T>,Point<T>>(a,b) {}
    Segment(const Segment<T>&) = default;
    Segment<T>& operator=(const Segment<T>&) = default;
    inline T dx() const { return x.x - y.x; }
    inline T dy() const { return x.y - y.y; }
    T squaredLength() const { return dx()*dx()+dy()*dy(); }
    long double length() const { return sqrtl(squaredLength()); }
};

template <typename T> struct Polygon : public vector<Point<T>> {
    using vector<Point<T>>::vector;
    using vector<Point<T>>::at;
    using vector<Point<T>>::front;
    using vector<Point<T>>::back;

    T doubleSignedArea() const {
        if (this->empty()) return T(0);
        T area = back().x*front().y - back().y*front().x;
        for (int i = 0; i < this->size()-1; ++i) area += (at(i).x * at(i+1).y - at(i+1).x * at(i).y);
        return area;
    }

    double circumference() const {
        if (this->empty()) return T(0);
        T res = back().distance(front());
        for (int i = 0; i < this->size()-1; ++i) res += at(i).distance(at(i+1));
        return res;
    }
};

template <typename T> Polygon<T> convexhull(const vector<Point<T>> &v) {
    ui N = (ui)v.size(); vector<Point<T>> w(N+1); int lo = 0;
    for (int i = 0; i<N; ++i) if (v[i].y < v[lo].y || (v[i].y == v[lo].y && v[i].x < v[lo].x)) lo = i;
    Point<T> o = v[lo];
    for (int i = 0; i<N; ++i) w[i+1] = {v[i].x-o.x,v[i].y-o.y};
    swap(w[1],w[lo+1]);

    sort(w.begin()+2,w.end(),[](Point<T>&a,Point<T>&b) {
        if (a.y==0) return b.y != 0 || a.x < b.x;
        if (b.y==0) return false;
        auto disc = (a.x*b.y-a.y*b.x);
        return disc > 0 || (disc == 0 && a.y < b.y);
    });
    w[0] = w[N];
    ui M=1;
    for (int i=2;i<=N;++i) {
        while(ccw(w[M-1],w[M],w[i]) <= 0) if (M>1) --M; else if (i == N) break; else ++i;
        ++M; swap(w[M],w[i]);
    }
    Polygon<T> res(M);
    for (int i=0;i<M;++i) res[i] = {w[i+1].x+o.x,w[i+1].y+o.y};
    return res;
}



#define next(x) (x==M-1?0:x+1)

class Inexact {
public:

    void solve(istream& cin, ostream& cout) {
        int N, W, H; cin >> N >> W >> H;
        vector<Point<ll>> A(N); cin >> A;
        auto Poly = convexhull(A);
        if (Poly.size() <= 2) {
            cout << 0 << '\n';
            return;
        }
        int M = Poly.size();

        vector<Point<double>> DPoly;
        for (int i = 0; i < M; ++i) DPoly.emplace_back(Poly[i].x, Poly[i].y);

        double ans = PI;

        Point<ll> Orig{0,0};
        for (int flip = 0; flip < 2; ++flip) {
            for (int rot = 0; rot < 4; ++rot) {
                int L = 0, R = 0;
                for (int i = 0; i < M; ++i) {
                    if (ccw(Orig, Poly[L], Poly[i]) > 0) L = i;
                    if (ccw(Orig, Poly[R], Poly[i]) < 0) R = i;
                }

                ans = min(ans, angle(Orig, Poly[L], Poly[R]));

                while (true) {
                    if (Poly[L].y <= Poly[next(L)].y) break; // no x-intercept

                    ll num = Poly[L].y * Poly[next(L)].x - Poly[L].x * Poly[next(L)].y;
                    ll den = Poly[L].y - Poly[next(L)].y;

                    Point<double> intercept{double(num)/den, 0};
                    if (intercept.x >= W) break;

                    // find the right-most point from intercept
                    while (true) {
                        if (orientation(intercept, DPoly[R], DPoly[next(R)]) == -1) {
                            R = next(R);
                        } else {
                            break;
                        }
                    }

                    // find whether the angle L/Intercept/R is <= 45 degrees
                    ans = min(ans, angle(intercept, DPoly[L], DPoly[R]));
                    L = next(L);
                }

                swap(W, H);
                for (auto &a: Poly) { swap(a.x, a.y); a.y = H - a.y; }
                for (auto &a: DPoly) { swap(a.x, a.y); a.y = H - a.y; }
            }

            for (auto &a: Poly) a.x = W - a.x;
            for (auto &a: DPoly) a.x = W - a.x;
            reverse(Poly.begin(),Poly.end());
            reverse(DPoly.begin(),DPoly.end());
        }

        cout << fixed << setprecision(10) << ans * 180.0 / PI << '\n';
    }
};


int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	Inexact solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n; cin >> n;
  vector<int> v;
  copy_n(istream_iterator<int>(cin), n, back_inserter(v));
  bool ok = false;
  for (int i=0; i<n; ++i) {
    auto w = v; // make a copy
    rotate(w.begin(), w.begin()+i, w.end());
    ok |= is_sorted(w.begin(), w.end());
  }
  cout << (ok ? "Phew\n" : "Lie\n");
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    
    for(int i=0; i<n; i++) printf("%c", 'a');
    for(int i=0; i<n; i++) printf("%c", 'b');
    printf("\n");

    for(int i=0; i<n-1; i++) printf("%c", 'a');
    printf("%c", 'b');
    printf("%c", 'a');
    for(int i=0; i<n-1; i++) printf("%c", 'b');
    printf("\n");

    return 0;
}

#include <iostream>
using namespace std;
#define int int64_t

struct rectangle {
  int x1, y1, x2, y2;
  int area() const { return (x2-x1)*(y2-y1); }
};
istream& operator>>(istream& is, rectangle& r) {
  return is >> r.x1 >> r.y1 >> r.x2 >> r.y2;
}

signed main() {
  int t; cin >> t;
  while (t--) {
    rectangle a, b;
    cin >> a >> b;
    int w = min(a.x2, b.x2) - max(a.x1, b.x1);
    int h = min(a.y2, b.y2) - max(a.y1, b.y1);
    int best = max(a.area(), b.area());
    if (w >= 0 && h >= 0) {
      best = max(best, rectangle{0, min(a.y1, b.y1),
                                   w, max(a.y2, b.y2)}.area());
      best = max(best, rectangle{0, min(a.x1, b.x1),
                                   h, max(a.x2, b.x2)}.area());
    }
    cout << best << '\n';
  }
}

/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author majk
 */

#ifndef MAJK_LIB
#define MAJK_LIB

#include <vector>
#include <stack>
#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <iomanip>
#include <set>
#include <functional>
#include <algorithm>
#include <numeric>
#include <cassert>
#include <cmath>
#include <string>
#include <queue>
#include <array>
#include <bitset>
using namespace std;

#define x first
#define y second
typedef std::pair<int,int> pii; typedef long long ll; typedef unsigned long long ull; typedef unsigned int ui; typedef pair<ui,ui> puu;

template <typename T, typename U> std::istream&operator>>(std::istream&i, pair<T,U>&p) {i >> p.x >> p.y; return i;}
template<typename T>std::istream&operator>>(std::istream&i,vector<T>&t) {for(auto&v:t){i>>v;}return i;}
template <typename T, typename U> std::ostream&operator<<(std::ostream&o, const pair<T,U>&p) {o << p.x << ' ' << p.y; return o;}
template<typename T>std::ostream&operator<<(std::ostream&o,const vector<T>&t) {if(t.empty())o<<'\n';for(size_t i=0;i<t.size();++i){o<<t[i]<<" \n"[i == t.size()-1];}return o;}
template<typename T> using minheap = priority_queue<T, vector<T>, greater<T>>;
template<typename T> using maxheap = priority_queue<T, vector<T>, less<T>>;
ui logceil(ll x) { return x?8*sizeof(ll)-__builtin_clzll(x):0; }

namespace std { template<typename T,typename U>struct hash<pair<T,U>>{hash<T>t;hash<U>u;size_t operator()(const pair<T,U>&p)const{return t(p.x)^(u(p.y)<<7);}}; }
template<typename T,typename F>T bsh(T l,T h,const F&f){T r=-1,m;while(l<=h){m=(l+h)/2;if(f(m)){l=m+1;r=m;}else{h=m-1;}}return r;}
template<typename F> double bshd(double l,double h,const F&f,double p=1e-9){ui r=3+(ui)log2((h-l)/p);while(r--){double m=(l+h)/2;if(f(m)){l=m;}else{h=m;}}return (l+h)/2;}
template<typename T,typename F>T bsl(T l,T h,const F&f){T r=-1,m;while(l<=h){m=(l+h)/2;if(f(m)){h=m-1;r=m;}else{l=m+1;}}return r;}
template<typename F> double bsld(double l,double h,const F&f,double p=1e-9){ui r=3+(ui)log2((h-l)/p);while(r--){double m=(l+h)/2;if(f(m)){h=m;}else{l=m;}}return (l+h)/2;}
template<typename T> T gcd(T a,T b) { if (a<b) swap(a,b); return b?gcd(b,a%b):a; }


template<typename T>class vector2:public vector<vector<T>>{public:vector2(){} vector2(size_t a,size_t b,T t=T()):vector<vector<T>>(a,vector<T>(b,t)){}};
template<typename T>class vector3:public vector<vector2<T>>{public:vector3(){} vector3(size_t a,size_t b,size_t c,T t=T()):vector<vector2<T>>(a,vector2<T>(b,c,t)){}};
template<typename T>class vector4:public vector<vector3<T>>{public:vector4(){} vector4(size_t a,size_t b,size_t c,size_t d,T t=T()):vector<vector3<T>>(a,vector3<T>(b,c,d,t)){}};
template<typename T>class vector5:public vector<vector4<T>>{public:vector5(){} vector5(size_t a,size_t b,size_t c,size_t d,size_t e,T t=T()):vector<vector4<T>>(a,vector4<T>(b,c,d,e,t)){}};


#endif

class averaging {
public:
    void solve(istream& cin, ostream& cout) {
        int N, K; cin >> N >> K;
        vector<int> A(N); cin >> A;
        int tot = 0;
        for (int a: A) tot += a;
        vector5<bool> D(N+1, N+1, N+1, 101, 101, false);
        D[0][0][0][0][0] = true;
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j <= i; ++j) {
                for (int k = 0; k <= i; ++k) {
                    for (int l = 0; l <= 100; ++l) {
                        for (int m = 0; m <= 100; ++m) {
                            if (D[i][j][k][l][m]) {
                                D[i+1][j+1][k][l+A[i]][m] = true;
                                D[i+1][j][k+1][l][m+A[i]] = true;
                                D[i+1][j][k][l][m] = true;
                            }
                        }
                    }
                }
            }
        }

        pii best = {0, 1};
        pii diff = {K, 1};
        for (int i = 1; i < N; ++i) {
            for (int j = 1; j < N; ++j) {
                int k = N - i - j;
                if (k > 0) {
                    for (int l = 1; l < 100; ++l) {
                        for (int m = 1; m < 100; ++m) {
                            int n = tot - l - m;
                            if (D[N][i][j][l][m]) {
                                int den = i*j*k*3;
                                int num = j*k*l + i*k*m + i*j*n;
                                int numDiff = abs(num - K*i*j*k*3);
                                if (numDiff * diff.y < den * diff.x) {
                                    diff = {numDiff, den};
                                    best = {num, den};
                                } else if (numDiff * diff.y == den * diff.x && num < K*i*j*k*3) {
                                    diff = {numDiff, den};
                                    best = {num, den};
                                }
                            }
                        }
                    }
                }
            }
        }

        int g = gcd(best.x, best.y);
        cout << best.x / g << '/' << best.y / g << endl;
    }
};


int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	averaging solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
    return 0;
}

#include <algorithm>
#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    int W;
    cin >> W;
    map< string, string > wordlist;
    for (int w=0; w<W; ++w) {
        string word;
        cin >> word;
        string sorted_word = word;
        sort( sorted_word.begin(), sorted_word.end() );
        if (wordlist.count(sorted_word) == 0) wordlist[sorted_word] = word;
    }

    int Q;
    cin >> Q;
    for (int q=0; q<Q; ++q) {
        string query;
        cin >> query;
        sort( query.begin(), query.end() );
        string answer = "";
        for (int subset = 1; subset < (1<<9); ++subset) {
            string used = "";
            for (int i=0; i<9; ++i) if (subset & 1<<i) used += query[i];
            if (wordlist.count(used) == 0) continue;
            if (used.size() < answer.size()) continue;
            if (used.size() > answer.size()) { answer = wordlist[used]; continue; }
            answer = min( answer, wordlist[used] );
        }
        if (answer == "") answer = "IMPOSSIBLE";
        cout << answer << "\n";
    }
}

#include <vector>
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;

typedef long long ll; 

class die {
public:
    void solve(istream& cin, ostream& cout) {
        vector<int> A(6); cin >> A;
        ll S; cin >> S;
        int Q; cin >> Q;
        --Q;
        S -= A[Q];

        vector<int> M(3, 0);
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 6; ++j) {
                int k = min(j, 5-j);
                if (i != k) {
                    M[i] |= 1<<(3*A[j]+k-3);
                }
            }
        }

        map<int, int> C;
        vector<int> D{0};
        C[0] = 0;
        int cur = 0, id = 0;
        while (true) {
            int next = (cur&((1<<27)-1))<<3;
            for (int i = 0; i < 3; ++i) {
                if ((cur & M[i]) != M[i]) next |= 1<<i;
            }
            cur = next;
            D.push_back(cur);
            auto it = C.find(cur);
            if (it != C.end()) break;

            C[cur] = ++id;
        }

        int prep = C[cur];
        int per = id + 1 - C[cur];
        
        if (S > prep) S = (S - prep) % per + prep;

        if ((D[S]>>min(Q,5-Q))&1) cout << "ADA" << '\n';
        else cout << "BOB" << '\n';
    }
};


int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	die solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
    return 0;
}

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int N;
vector< vector<int> > G;
vector<bool> visited;
vector< vector<int> > solution;
bool OK;

bool dfs(int v) {
    visited[v] = true;
    vector<int> unmatched_children;
    for (int x : G[v]) if (!visited[x]) if (!dfs(x)) unmatched_children.push_back(x);
    while (unmatched_children.size() >= 2u) {
        int a = unmatched_children.back();
        unmatched_children.pop_back();
        int b = unmatched_children.back();
        unmatched_children.pop_back();
        solution.push_back( {a,b,v} );
    }
    if (unmatched_children.empty()) return false;
    solution.push_back( {unmatched_children[0], v, -1} );
    return true;
}

int main() {
    cin >> N;
    G.resize(2*N);
    int F;
    cin >> F;
    while (F--) {
        int x, y;
        cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    OK = true;
    visited.resize(2*N,false);
    for (int n=0; n<2*N; ++n) if (!visited[n]) if (!dfs(n)) OK = false;
    cout << (OK ? "POSSIBLE\n" : "IMPOSSIBLE\n");
    if (OK) for (auto row : solution) cout << row[0] << " " << row[1] << " " << row[2] << "\n";
}

N = int(input())
A, B = map(int, input().split())

best_k = 2000
for i in range(0, N+1):
    for j in range(0, N+1):
        if (i * A + j * B) % N != 0: continue
        if i + j == 0: continue
        best_k = min(best_k, i+j)
print(best_k)        

#include <vector>
#include <iostream>
using namespace std;

#define x first
#define y second
typedef std::pair<int,int> pii; typedef long long ll; typedef unsigned long long ull; typedef unsigned int ui; typedef pair<ui,ui> puu;

template<typename T>class vector2:public vector<vector<T>>{public:vector2(){} vector2(size_t a,size_t b,T t=T()):vector<vector<T>>(a,vector<T>(b,t)){}};


template <unsigned int N> class Field {
    typedef unsigned int ui;
    typedef unsigned long long ull;
	inline ui pow(ui a, ui p){ui r=1,e=a;while(p){if(p&1){r=((ull)r*e)%N;}e=((ull)e*e)%N;p>>=1;}return r;}
	inline ui inv(ui a){return pow(a,N-2);}
public:
    inline Field(int x = 0) : v(x) {}
	inline Field<N> pow(int p){return (*this)^p; }
	inline Field<N> operator^(int p){return {(int)pow(v,(ui)p)};}
    inline Field<N>&operator+=(const Field<N>&o) {if (v+o.v >= N) v += o.v - N; else v += o.v; return *this; }
    inline Field<N>&operator-=(const Field<N>&o) {if (v<o.v) v -= o.v-N; else v-=o.v; return *this; }
    inline Field<N>&operator*=(const Field<N>&o) {v=(ull)v*o.v % N; return *this; }
    inline Field<N>&operator/=(const Field<N>&o) { return *this*=inv(o.v); }
    inline Field<N> operator+(const Field<N>&o) const {Field<N>r{*this};return r+=o;}
    inline Field<N> operator-(const Field<N>&o) const {Field<N>r{*this};return r-=o;}
    inline Field<N> operator*(const Field<N>&o) const {Field<N>r{*this};return r*=o;}
    inline Field<N> operator/(const Field<N>&o) const {Field<N>r{*this};return r/=o;}
    inline Field<N> operator-() {if(v) return {(int)(N-v)}; else return {0};};
    inline Field<N>& operator++() { ++v; if (v==N) v=0; return *this; }
    inline Field<N> operator++(int) { Field<N>r{*this}; ++*this; return r; }
    inline Field<N>& operator--() { --v; if (v==-1) v=N-1; return *this; }
    inline Field<N> operator--(int) { Field<N>r{*this}; --*this; return r; }
    inline bool operator==(const Field<N>&o) const { return o.v==v; }
	inline bool operator!=(const Field<N>&o) const { return o.v!=v; }
	inline explicit operator ui() const { return v; }
	inline static vector<Field<N>>fact(int t){vector<Field<N>>F(t+1,1);for(int i=2;i<=t;++i){F[i]=F[i-1]*i;}return F;}
	inline static vector<Field<N>>invfact(int t){vector<Field<N>>F(t+1,1);Field<N> X{1};for(int i=2;i<=t;++i){X=X*i;}F[t]=1/X;for(int i=t-1;i>=2;--i){F[i]=F[i+1]*(i+1);}return F;}
private: ui v;
};
template<unsigned int N>istream &operator>>(std::istream&is,Field<N>&f){unsigned int v;is>>v;f=v;return is;}
template<unsigned int N>ostream &operator<<(std::ostream&os,const Field<N>&f){return os<<(unsigned int)f;}
template<unsigned int N>Field<N> operator+(int i,const Field<N>&f){return Field<N>(i)+f;}
template<unsigned int N>Field<N> operator-(int i,const Field<N>&f){return Field<N>(i)-f;}
template<unsigned int N>Field<N> operator*(int i,const Field<N>&f){return Field<N>(i)*f;}
template<unsigned int N>Field<N> operator/(int i,const Field<N>&f){return Field<N>(i)/f;}

typedef Field<1000000007> FieldMod;

class treequeries {
public:
    void solve(istream& cin, ostream& cout) {
        int Q; cin >> Q;
        vector<FieldMod> B(31, 0);
        vector2<int> C(31, 31, 0);
        for (int i = 0; i <= 30; ++i) {
            C[i][0] = C[i][i] = 1;
            for (int j = 1; j < i; ++j) C[i][j] = C[i-1][j-1] + C[i-1][j];
        }
        auto add = [&](int x, FieldMod s) {
            int pref = 0, cnt = 0;
            for (int i = 30; i >= 0; --i) {
                if (x&1<<i) {
                    for (int j = 0; j <= i; ++j) B[cnt+j] += s * C[i][j];

                    pref |= 1<<i;
                    cnt++;
                }
            }
        };

        for (int q = 0; q < Q; ++q) {
            int t, l, r; cin >> t >> l >> r;
            if (t == 0) {
                FieldMod X; cin >> X;
                add(r, X);
                add(l, -X);
            } else {
                FieldMod ans = 0;
                for (int i = 31-r; i < 31-l; ++i) ans += B[i];
                cout << ans << '\n';
            }
        }
    }
};

int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	treequeries solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
    return 0;
}

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int N; cin >> N;
    vector<int> A(N); for (int&a:A) cin >> a;
    vector<int> P{1};
    int rest = 0, cur = A[0];
    for (int i = 1; i < N; ++i) {
        if (A[i] <= A[0]/2) {  
            cur += A[i];
            P.push_back(i+1);
        } else {
            rest += A[i];
        }
    }

    if (cur > rest) {
        cout << P.size() << endl;
        for (int i = 0; i < P.size(); ++i) cout << P[i] << " \n"[i==P.size()-1];
    } else {
        cout << 0 << endl;
    }
}

#include <iostream>
#include <string>

using namespace std;
typedef long long ll;

int main() {
    string S; cin >> S;
    ll a = 0, b = 0, c = 0;    
    for (int i = 0; i < S.size(); ++i) {
        if (S[i] == 'o') {
            b += a;
        } else if (i > 0 && S[i-1] == 'v') {
            a++;
            c += b;
        }
    }
    cout << c << endl;
}

#include <iostream>

using namespace std;

constexpr int MOD = 998244353;
    
int main() {
    int R, C; cin >> R >> C;
    int X = 1;
    while (R--) X = (2*X)%MOD;
    while (C--) X = (2*X)%MOD;
    cout << X << endl;
}

#include <iostream>

using namespace std;

bool prime(int x) {
    if (x < 2) return false;
    for (int i = 2; i*i <= x; ++i) {
        if (x%i == 0) return false;
    }
    return true;
}


int main(int argc, char ** argv){
	int n; cin >> n;
    int m = n;
    while (!prime(m)) ++m;
    cout << m << "\n1 " << n << '\n';
    for (int i = 0; i < n-1; ++i) {
        cout << i+1 << ' ' << i+2 << '\n';
    }

    for (int i = 0; i < m-n; ++i) {
        cout << i+1 << ' ' << i+1+n/2 << '\n';
    }
}

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;
int main() {
    string S; cin >> S;
    int N = S.size();
    int i = 0, j = N-1;
    string A;
    while (j-i >= 3) {
        if (S[i] == S[j]) {
            A.push_back(S[i]);
            ++i; --j;
        } else if (S[i] == S[j-1]) {
            A.push_back(S[i]);
            ++i; j -= 2;
        } else {
            A.push_back(S[i+1]);
            if (S[i+1] == S[j]) {
                --j;
            } else {
                j -= 2;
            }
            i += 2;
        }
    }
    string B = A;
    if (j >= i) A.push_back(S[i]);
    reverse(B.begin(),B.end());
    cout << A << B << endl;
}

#include <iostream>
#include <vector>

using namespace std;

template <unsigned int N> class Field {
    typedef unsigned int ui;
    typedef unsigned long long ull;
public:
    inline Field(int x = 0) : v(x) {}
    inline Field<N>&operator+=(const Field<N>&o) {if (v+o.v >= N) v += o.v - N; else v += o.v; return *this; }
    inline Field<N>&operator*=(const Field<N>&o) {v=(ull)v*o.v % N; return *this; }
    inline Field<N> operator*(const Field<N>&o) const {Field<N>r{*this};return r*=o;}
	inline explicit operator ui() const { return v; }
private: ui v;
};
template<unsigned int N>ostream &operator<<(std::ostream&os,const Field<N>&f){return os<<(unsigned int)f;}
template<unsigned int N>Field<N> operator*(int i,const Field<N>&f){return Field<N>(i)*f;}

typedef Field<998244353> F;

int main() {
    ios_base::sync_with_stdio(false);
    
    int N, M; cin >> N >> M;
    vector<int> C(N); for (int &c: C) { cin >> c; --c; }
    
    vector<vector<F>> D(N+1, vector<F>(N+1, 1));
    for (int l = 1; l <= M; ++l) {
        for (int a = 0; a + l <= M; ++a) {
            pair<int,int> lo = {C[a],0};
            for (int i = 0; i < l; ++i) lo = min(lo, {C[a+i],i});
            int j = lo.second;
            if (j < 0 || j >= l) { D[a][l] = 0; continue; }
            F left = 0, right = 0;
            for (int u = 0; u <= j; ++u) left += D[a][u] * D[a+u][j-u];
            for (int v = j+1; v <= l; ++v) right += D[a+j+1][v-(j+1)] * D[a+v][l-v];
            D[a][l] = left * right;
        }
    }
    
    cout << D[0][N] << endl;
}

#include <iostream>
#include <vector>

using namespace std;

template <unsigned int N> class Field {
    typedef unsigned int ui;
    typedef unsigned long long ull;
public:
    inline Field(int x = 0) : v(x) {}
	inline Field<N> pow(int p){return (*this)^p; }
    inline Field<N>&operator+=(const Field<N>&o) {if (v+o.v >= N) v += o.v - N; else v += o.v; return *this; }
    inline Field<N>&operator*=(const Field<N>&o) {v=(ull)v*o.v % N; return *this; }
    inline Field<N> operator*(const Field<N>&o) const {Field<N>r{*this};return r*=o;}
	inline explicit operator ui() const { return v; }
private: ui v;
};
template<unsigned int N>ostream &operator<<(std::ostream&os,const Field<N>&f){return os<<(unsigned int)f;}
template<unsigned int N>Field<N> operator+(int i,const Field<N>&f){return Field<N>(i)+f;}
template<unsigned int N>Field<N> operator*(int i,const Field<N>&f){return Field<N>(i)*f;}

typedef Field<998244353> F;

int main() {
    ios_base::sync_with_stdio(false);
    
    int N, M; cin >> N >> M;
    vector<int> C(M); for (int &c: C) { cin >> c; --c; }
    vector<int> W;
    for (int i = 0; i < M; ++i) if (W.empty() || W.back() != C[i]) W.push_back(C[i]);
    M = W.size();
    if (M > 2*N) { cout << "0\n"; return 0; }
    vector<vector<int>> E(N);
    for (int i = 0; i < M; ++i) E[W[i]].push_back(i);
       
    vector<vector<F>> D(M+1, vector<F>(M+1, 1));
    for (int l = 1; l <= M; ++l) {
        for (int a = 0; a + l <= M; ++a) {
            int lo = W[a];
            for (int i = 0; i < l; ++i) lo = min(lo, W[a+i]);
            int j = E[lo][0] - a;
            int k = E[lo].back() - a;
            if (j < 0 || k >= l) { D[a][l] = 0; continue; }
            F left = 0, right = 0;
            for (int u = 0; u <= j; ++u) left += D[a][u] * D[a+u][j-u];
            for (int v = k+1; v <= l; ++v) right += D[a+k+1][v-(k+1)] * D[a+v][l-v];
            D[a][l] = left * right;
            for (int m = 0; m < E[lo].size()-1; ++m) {
                if (E[lo][m] + 1 != E[lo][m+1]) {
                    D[a][l] *= D[E[lo][m]+1][E[lo][m+1] - E[lo][m] - 1];
                }
            }
        }
    }
    
    cout << D[0][M] << endl;
}

#include <vector>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cassert>
#include <cmath>
using namespace std;

#define x first
#define y second
typedef std::pair<int,int> pii; typedef long long ll; typedef unsigned long long ull; typedef unsigned int ui; typedef pair<ui,ui> puu;

template<typename T>std::istream&operator>>(std::istream&i,vector<T>&t) {for(auto&v:t){i>>v;}return i;}
template <typename T> bool in(T a, T b, T c) { return a <= b && b < c; }

bool fractionGreaterOrEqual(double a, double b, double c, double d) {
	return a/b >= c/d;
}

int TOTAL;

/* UpperEnvelope that with O(N) build and amortized O(1) query.
 * The updates need be sorted by (m,b), the queries need to be sorted by x, and
 * updates need to come before queries. */
namespace LinearEnvelope {
	template<typename T> struct Line { T m, b; int id; };

	template <typename T>
	struct Upper {
		Line<T> *V;
		T t; int i, s;

		Upper(int w) : V(new Line<T>[w]), t(0), i(0), s(0) { TOTAL++; }
		~Upper() { TOTAL--; }
		//~Upper() { delete []V; }
		void clear() { i = s = 0; t = 0; }

		void insert_line(T m, T b, int i = 0) {
			assert(t == 0);
			if (s > 0 && V[s-1].m == m && V[s-1].b >= b) return;
			while (s > 0 && ((V[s-1].b < b) || (V[s-1].b == b && V[s-1].m < m))) --s;
			while (s >= 2 && fractionGreaterOrEqual(V[s-2].b - V[s-1].b, V[s-1].m - V[s-2].m, V[s-1].b - b, m - V[s-1].m)) --s;
			V[s++] = {m,b,i};
		}

		pair<T,int> advance(T x) {
			assert(x >= 0);
			t += x;
			while (i+1 < s && V[i].m * t + V[i].b < V[i+1].m * t + V[i+1].b) ++i;
			return {V[i].m * t + V[i].b, V[i].id};
		}
	};
};


class RPPS {
public:
    vector<vector<int>> E;
    vector<ll> A,B,RA,RB;
    vector<int> Enter,Exit;
    int T;

    void dfs(int u, ll a, ll b) {
        A[u] += a;
        B[u] += b;
        Enter[u] = T++;
        for (int v:E[u]) dfs(v, A[u], B[u]);
        Exit[u] = T;
    }

    struct Block {
        Block(int L, int R, const vector<ll>&A, const vector<ll>&B) : U(2*(R-L)), L(L), R(R), off(0), cur(0) {
            for (int i = L; i < R; ++i) W.push_back({{B[i], A[i]*B[i]}, i});
            for (int i = L; i < R; ++i) if (A[i] < 0 || B[i] < 0) W.push_back({{-B[i], -A[i]*B[i]}, i});
            sort(W.begin(),W.end());
            build();
        }

        void build() {
            U.clear();
            for (auto &w:W) U.insert_line(w.x.x, w.x.y);
            cur = U.advance(0LL).x;
        }

        void add(int l, int r, ll x) {
            if (l >= R || r <= L) return;
            else if (l <= L && r >= R) {
                cur = U.advance(x).x;
                off += x;
            } else {
                for (auto &w:W) {
                    w.x.y += w.x.x * off;
                    if (in(l, w.y, r)) {
                        w.x.y += w.x.x * x;
                    }
                }
                off = 0;
                build();
            }
        }

        ll get(int l, int r) {
            if (l >= R || r <= L) return numeric_limits<ll>::min();
            else if (l <= L && r >= R) return cur;
            else {
                ll ans = numeric_limits<ll>::min();
                for (auto &w:W) {
                    if (in(l, w.y, r)) {
                        ans = max(ans, w.x.x * off + w.x.y);
                    }
                }
                return ans;
            }
        }

        LinearEnvelope::Upper<ll> U;
        vector<pair<pair<ll,ll>,int>> W;
        int L, R;
        ll off, cur;
    };

void solve(istream& cin, ostream& cout) {
    TOTAL = 0;
    int N, Q; cin >> N >> Q;
    E.resize(N);
    A.resize(N);
    B.resize(N);
    RA.resize(N);
    RB.resize(N);
    Enter.resize(N);
    Exit.resize(N);

    for (int i = 1; i < N; ++i) {
        int p; cin >> p; --p;
        E[p].push_back(i);
    }
    cin >> A >> B;

    T = 0;
    dfs(0, 0, 0);

    for (int i = 0; i < N; ++i) {
        RA[Enter[i]] = A[i];
        RB[Enter[i]] = B[i];
    }

    int BS = max(1,(int)sqrt(N/6));
    vector<Block> D;
    D.reserve(1+(N-1)/BS);
    for (int i = 0; i < N; i+=BS) D.emplace_back(i, min(i+BS,N), RA, RB);
    
    ll diff = 0;
    for (int q = 0; q < Q; ++q) {
        int t,v; cin >> t >> v;
        --v;
        if (t == 1) {
            ll x; cin >> x;
            for (Block&b:D) b.add(Enter[v],Exit[v],x);
        } else {
            ll ans = numeric_limits<ll>::min();
            for (Block&b:D) ans = max(ans, b.get(Enter[v],Exit[v]));
            cout << ans << '\n';
        }
    }
}
};


int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	RPPS solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
    return 0;
}

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

#define x first
#define y second
typedef long long ll; 

template<typename T,typename F>T bsl(T l,T h,const F&f){T r=-1,m;while(l<=h){m=(l+h)/2;if(f(m)){h=m-1;r=m;}else{l=m+1;}}return r;}


/** Successive shortest paths algorithm. Runs in O(maxFlow * (|E| + sumCosts)). */
template<typename Cap = int, typename Cost = int>
struct SSPA {
    struct Edge{
        Cost c; Cap f; int to, rev;
        Edge(int _to, Cost _c, Cap _f, int _rev):c(_c), f(_f), to(_to), rev(_rev){}
    };
    int N, source, sink;
    vector<vector<Edge>> G;
    SSPA(int N, int source, int sink): N(N), source(source), sink(sink), G(N) {}
    void addEdge(int a, int b, Cap cap, Cost cost) {
        assert(cap>=0);
        assert(a>=0&&a<N&&b>=0&&b<N);
        if(a==b){assert(cost>=0); return;}
        G[a].emplace_back(b, cost, cap, G[b].size());
        G[b].emplace_back(a, -cost, 0, G[a].size()-1);
    }

    pair<Cap, Cost> minCostMaxFlow() {
        /* Vertex potentials. These are maintained so that all edges with non-zero
         * residual have non-negative length. Thus, Dijkstra can be used instead of
         * Bellman-Ford in each step of the algorithm. */
        vector<Cost> Pi(N, 0);
        Cost infty = std::numeric_limits<Cost>::max();
        Cap totFlow = 0;
        Cost totCost = 0;
        while (true) {
            vector<Cost> D(N, infty);
            vector<int> Prev(N, -1);
            D[source] = 0;

            vector<vector<int>> Q{{source}};
            for (int i = 0; i < Q.size(); ++i) {
                for (int j = 0; j < Q[i].size(); ++j) {
                    int u = Q[i][j];
                    if (D[u] < i) continue;

                    for (auto &e: G[u]) {
                        if (e.f > 0) {
                            Cost c = D[u] + e.c;
                            if (D[e.to] > c) {
                                D[e.to] = c;
                                while (c >= Q.size()) Q.emplace_back();
                                Q[c].push_back(e.to);
                                Prev[e.to] = u;
                            }
                        }
                    }
                }
            }

            // if sink is unreachable, flow is optimal
            if (D[sink] == infty) break;

            // reconstruct some shortest path
            int v = sink;
            vector<int> Path;
            while (v != -1) { Path.push_back(v); v = Prev[v]; }
            reverse(Path.begin(),Path.end());

            // found the minimum of the edge residuals along the path
            Cap augment = std::numeric_limits<Cap>::max();
            int L = Path.size();
            for (int i = 0; i < L-1; ++i) {
                int u = Path[i], v = Path[i+1];
                for (auto&e: G[u]) {
                    // be careful, there might be multiedges
                    if (e.to == v && e.f > 0 && D[v] == D[u] + e.c) {
                        augment = min(augment, e.f);
                        break;
                    }
                }
            }

            for (int i = 0; i < L-1; ++i) {
                int u = Path[i], v = Path[i+1];
                for (auto&e: G[u]) {
                    if (e.to == v && e.f > 0 && D[v] == D[u] + e.c) {
                        e.f -= augment;
                        G[v][e.rev].f += augment;
                        break;
                    }
                }
            }

            // store the cost & flow size
            Cost cost = Pi[source] - Pi[sink] + D[sink];
            totFlow += augment;
            totCost += cost * augment;

            // remove potentials from costs
            for (int i = 0; i < N; ++i) {
                for (auto &e: G[i]) {
                    e.c -= Pi[e.to] - Pi[i];
                }
            }


            // add potentials to costs again
            for (int i = 0; i < N; ++i) {
                for (auto &e: G[i]) {
                    e.c += (Pi[e.to] - D[e.to]) - (Pi[i] - D[i]);
                }
            }

            // update potentials based on the results
            for (int i = 0; i < N; ++i) Pi[i] -= D[i];

        }
        return {totFlow,totCost};
    }
};

class Stock {
public:
    void solve(istream& cin, ostream& cout) {
        int N; cin >> N;
        vector<int> A(2*N), B(2*N);
        for (int i = 0; i < 2*N; ++i) {
            cin >> A[i] >> B[i];
        }

        // find T: O(N log MAX log N)
        int T = bsl(0, 1000000000, [&](int t) {
            // ( (price at 0) x (-price at t) x (is initial stock) )
            vector<pair<pair<int, ll>, bool>> Stocks(2*N);
            for (int i = 0; i < 2*N; ++i) {
                Stocks[i] = {{B[i], -(A[i]*ll(t) + B[i])}, i<N};
            }
            sort(Stocks.begin(),Stocks.end());
            ll best = 0;
            vector<ll> CanHave, Required;
            for (int i = 0; i < 2*N; ++i) {
                best = max(best, -Stocks[i].x.y);
                if (Stocks[i].y) {
                    CanHave.push_back(best);
                } else {
                    Required.push_back(-Stocks[i].x.y);
                }
            }
            sort(CanHave.begin(),CanHave.end());
            sort(Required.begin(),Required.end());
            for (int i = 0; i < N; ++i) {
                if (CanHave[i] < Required[i]) return false;
            }
            return true;
        });

        if (T == -1) {
            cout << -1 << endl;
            return;
        }

        vector<pair<pair<int,ll>,int>> Begin(2*N);
        vector<pair<ll, int>> End(2*N);
        for (int i = 0; i < 2*N; ++i) {
            ll end = A[i]*ll(T) + B[i];
            // bigger start => process later
            // bigger end => process earlier
            Begin[i] = {{B[i], -end}, i};

            // bigger end => process later
            // bigger id => process earlier
            End[i] = {end, -i};
        }
        sort(Begin.begin(),Begin.end());
        sort(End.begin(),End.end());
        reverse(Begin.begin(),Begin.end());
        reverse(End.begin(),End.end());

        // SSPA, using O(dijkstra * flow)
        SSPA<int,int> G(6*N+2, 6*N, 6*N+1);
        for (int i = 0; i < 2*N; ++i) {
            if (i != 2*N-1) {
                int j = Begin[i].y;
                int k = Begin[i+1].y;
                G.addEdge(N+j, N+k, N, 0); // perform exchange at t=0

                j = -End[i].y;
                k = -End[i+1].y;
                G.addEdge(3*N+j, 3*N+k, N, 0); // perform exchange at t=T
            }

            if (Begin[i].y < N) {
                int j = Begin[i].y;
                G.addEdge(6*N, j, 1, 0); // super source
                G.addEdge(j, N+j, 1, 1); // exchange for something at t=0
                G.addEdge(j, 3*N+j, 1, 0); // hold until t=T
            }

            if ((-End[i].y) >= N) {
                int j = -End[i].y;
                G.addEdge(N+j, 5*N+(j-N), 1, 0); // was kept from t=0
                G.addEdge(3*N+j, 5*N+(j-N), 1, 1); // was exchanged at t=T
                G.addEdge(5*N+(j-N), 6*N+1, 1, 0); // super sink
            }

            G.addEdge(N+i, 3*N+i, N, 0); // hold between 0 and T
        }

        auto res = G.minCostMaxFlow();
        assert(res.x == N);
        cout << T << ' ' << res.y << '\n';

    }
};


int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	Stock solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main(){
    int a, b, c;
    cin >> a >> b >> c;
    cout << min(a + 2, min(b + 1, c)) * 3 - 3;
}

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

typedef pair<int,int> pii;

#define x first
#define y second

int main() {
    int N; cin >> N;
    vector<pii> O(N), T(N);
    for (int i = 0; i < N; i++) cin >> O[i].x >> O[i].y;
    for (int i = 0; i < N; i++) cin >> T[i].x >> T[i].y;
    sort(O.begin(),O.end());
    sort(T.begin(),T.end());
    reverse(T.begin(),T.end());

    vector<pii> Ans(N);
    for (int i = 0; i < N; i++) Ans[i] = {O[i].x+T[i].x, O[i].y+T[i].y};
    sort(Ans.begin(),Ans.end());
    cout << Ans[0].x << ' ' << Ans[0].y << endl;
}

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

int main() {
	ll N; cin >> N;
	vector<ll> ans;

	for (ll i = 1; i*i <= N; ++i) {
		if (N%i==0) {
			ans.push_back(N*(i-1)/2 + i);
			if (i*i!=N) {
				ans.push_back(N*(N/i-1)/2 + N/i);
			}
		}
	}
	sort(ans.begin(),ans.end());
	
	for (int i = 0; i < ans.size(); ++i) {
		cout << ans[i] << " \n"[i==ans.size()-1];
	}

}

#include <iostream>
#include <vector>

using namespace std;

template <unsigned int N> class Field {
    typedef unsigned int ui;
    typedef unsigned long long ull;
	inline ui pow(ui a, ui p){ui r=1,e=a;while(p){if(p&1){r=((ull)r*e)%N;}e=((ull)e*e)%N;p>>=1;}return r;}
	inline ui inv(ui a){return pow(a,N-2);}
public:
    inline Field(int x = 0) : v(x) {}
	inline Field<N> pow(int p){return (*this)^p; }
	inline Field<N> operator^(int p){return {(int)pow(v,(ui)p)};}
    inline Field<N>&operator+=(const Field<N>&o) {if (v+o.v >= N) v += o.v - N; else v += o.v; return *this; }
    inline Field<N>&operator-=(const Field<N>&o) {if (v<o.v) v -= o.v-N; else v-=o.v; return *this; }
    inline Field<N>&operator*=(const Field<N>&o) {v=(ull)v*o.v % N; return *this; }
    inline Field<N>&operator/=(const Field<N>&o) { return *this*=inv(o.v); }
    inline Field<N> operator+(const Field<N>&o) const {Field<N>r{*this};return r+=o;}
    inline Field<N> operator-(const Field<N>&o) const {Field<N>r{*this};return r-=o;}
    inline Field<N> operator*(const Field<N>&o) const {Field<N>r{*this};return r*=o;}
    inline Field<N> operator/(const Field<N>&o) const {Field<N>r{*this};return r/=o;}
    inline Field<N> operator-() {if(v) return {(int)(N-v)}; else return {0};};
    inline Field<N>& operator++() { ++v; if (v==N) v=0; return *this; }
    inline Field<N> operator++(int) { Field<N>r{*this}; ++*this; return r; }
    inline Field<N>& operator--() { --v; if (v==-1) v=N-1; return *this; }
    inline Field<N> operator--(int) { Field<N>r{*this}; --*this; return r; }
    inline bool operator==(const Field<N>&o) const { return o.v==v; }
	inline bool operator!=(const Field<N>&o) const { return o.v!=v; }
	inline explicit operator ui() const { return v; }
	inline static vector<Field<N>>fact(int t){vector<Field<N>>F(t+1,1);for(int i=2;i<=t;++i){F[i]=F[i-1]*i;}return F;}
	inline static vector<Field<N>>invfact(int t){vector<Field<N>>F(t+1,1);Field<N> X{1};for(int i=2;i<=t;++i){X=X*i;}F[t]=1/X;for(int i=t-1;i>=2;--i){F[i]=F[i+1]*(i+1);}return F;}
private: ui v;
};
template<unsigned int N>istream &operator>>(std::istream&is,Field<N>&f){unsigned int v;is>>v;f=v;return is;}
template<unsigned int N>ostream &operator<<(std::ostream&os,const Field<N>&f){return os<<(unsigned int)f;}
template<unsigned int N>Field<N> operator+(int i,const Field<N>&f){return Field<N>(i)+f;}
template<unsigned int N>Field<N> operator-(int i,const Field<N>&f){return Field<N>(i)-f;}
template<unsigned int N>Field<N> operator*(int i,const Field<N>&f){return Field<N>(i)*f;}
template<unsigned int N>Field<N> operator/(int i,const Field<N>&f){return Field<N>(i)/f;}

typedef Field<998244353> FF;

int main(int argc, char* argv[]) {
    int n; cin >> n;
    auto F = FF::fact(n);
    auto I = FF::invfact(n);
    FF ans = n * F[n];
    for (int i = 1; i < n; ++i) ans -= F[n]*I[i];
    cout << ans << endl;
}

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

#define MAXN 500000

int N;
int A[MAXN];
long long sum;

#define TOO_SMALL -1
#define OK 0
#define TOO_BIG 1

int is_score(int value) {
    vector<int> C(N+1,0);
    for (int i = 0; i < N; ++i) ++C[A[i]];
    ++C[value];

    int less = 0;
    long long left = 0, right = 0;
    for (int k = 0, i = 0; k <= N; k++) {
        int val = (i == k && (i == N || A[i] < value)) ? value : A[i++];
        left += val;
        --C[val];
        right -= min(val, k);
        less += C[k];
        right += N-k-less;
        if (left > right + (long long)(k+1)*k) {
            return (i == k) ? TOO_BIG : TOO_SMALL;
        }
    }
    return OK;
}

int main(int,char**) {
    ios_base::sync_with_stdio(false);
    
    scanf("%d", &N);
    sum = 0;
    for (int i = 0; i < N; i++) {
        scanf("%d", A + i);
        sum += A[i];
    }

    sort(A,A+N,greater<int>());
    int parity = sum & 1;
    int lo = 0, hi = (N - parity) / 2, lores = -1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (is_score(2*mid + parity) == TOO_SMALL) {
            lo = mid + 1;
        } else {
            lores = mid;
            hi = mid - 1;
        }
    }
    
    lo = lores; 
    hi = (N - parity) / 2; 
    int hires = -1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (is_score(2*mid + parity) == TOO_BIG) {
            hi = mid - 1;
        } else {
            hires = mid;
            lo = mid + 1;
        }
    }
    
    if (lores == -1 || hires == -1) printf("-1\n"); 
    else {
        for (int i = lores; i <= hires; ++i) printf("%d ", 2*i+parity);
        printf("\n");
    }
}

#include <iostream>
#include <vector>
#include <string>

typedef long long ll;
using namespace std;

int main() {
    int N; cin >> N;
    vector<ll> L(N); 
    for (ll &l: L) cin >> l;
    string T; cin >> T;
    bool hadWater = false;
    ll time = 0, stamina = 0, twiceGrass = 0;
    for (int i = 0; i < N; ++i) {
        if (T[i] == 'L') {
            time += L[i];
            stamina -= L[i];
            if (stamina < 0) {
                /* not enough stamina, walk or swim "in place" to gain it */
                time -= stamina * (hadWater ? 3 : 5);
                stamina = 0;
            }
        } else if (T[i] == 'W') {
            hadWater = true;
            stamina += L[i];
            time += 3 * L[i];
        } else {
            stamina += L[i];
            time += 5 * L[i];
            twiceGrass += 2*L[i];   
        }
        /* no more than stamina/2 of walking can be converted to flying to save time,
         * otherwise there would not be enough stamina at this point */
        twiceGrass = min(twiceGrass, stamina);
    }

    if (stamina > 0) {
        // convert walking to flying
        time -= (5-1) * twiceGrass/2;

        // convert swimming to flying
        time -= (3-1) * (stamina - twiceGrass)/2;
    }

    cout << time << endl;
}

import random

def isPrime(n):
    """
    Miller-Rabin primality test.

    A return value of False means n is certainly not prime. A return value of
    True means n is very likely a prime.
    """
    if n!=int(n):
        return False
    n=int(n)
    #Miller-Rabin test for prime
    if n==0 or n==1 or n==4 or n==6 or n==8 or n==9:
        return False

    if n==2 or n==3 or n==5 or n==7:
        return True
    s = 0
    d = n-1
    while d%2==0:
        d>>=1
        s+=1
    assert(2**s * d == n-1)

    def trial_composite(a):
        if pow(a, d, n) == 1:
            return False
        for i in range(s):
            if pow(a, 2**i * d, n) == n-1:
                return False
        return True

    for i in range(20):#number of trials
        a = random.randrange(2, n)
        if trial_composite(a):
            return False

    return True

def gcd(x, y):
    return x if y == 0 else gcd(y, x % y)

n = int(input())

divs = [n]

def split(parts):
    global divs
    divs = [gcd(d, p) for d in divs for p in parts if gcd(d, p) != 1]

while not all([isPrime(x) for x in divs]):
    x = random.randint(0, n - 1)
    g = gcd(n, x)
    if gcd(n, x) != 1:
        split([g, n // g])
        continue
    y = int(input('sqrt {}\n'.format(x * x % n)))
    if x == y:
        continue
    a, b = abs(x - y), x + y
    g = gcd(x, y)
    split([a // g, b // g, g])

print('!', len(divs), ' '.join(str(d) for d in sorted(divs)))

#include <vector>
#include <stack>
#include <iostream>
#include <algorithm>
#include <bitset>
using namespace std;

typedef unsigned int ui;
typedef long long ll;

struct Sieve : public std::vector<bool> {
    // ~10ns * n
	explicit Sieve(ui n) : vector<bool>(n+1, true), n(n) {
		at(0) = false;
		if (n!=0) at(1) = false;
		for (ui i = 2; i*i <= n; ++i) {
			if (at(i)) for (int j = i*i; j <= n; j+=i) (*this)[j] = false;
		}
	}

	vector<int> primes() const {
		vector<int> ans;
		for (int i=2; i<=n; ++i) if (at(i)) ans.push_back(i);
		return ans;
	}

private:
	int n;
};

constexpr int M = 2e5;
auto P = Sieve{M}.primes();

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    vector<int> G(M, 0);
    int Q = P.size();
    for (int i = 0; i < Q; ++i) {
        for (int j = i; j < Q; ++j) {
            if (ll(P[i])*P[j] >= M) break;
            P.push_back(P[i]*P[j]);
        }
    }
    
    bitset<M> PB;
    for (int p : P) PB[p] = true;
    
    int N, F; cin >> N >> F;
    PB[F] = false;
    
    vector<bitset<M>> W(100);
    W[0] = PB;
    for (int i = 1; i < M; ++i) {
        while (W[G[i]][i]) G[i]++;
        W[G[i]] |= PB << i;
    }
    cerr << *max_element(G.begin(),G.end()) << endl;

    int g = 0;
    for (int i = 0; i < N; i++) {
        int r,w,b;
        cin >> r >> w >> b;
        g ^= G[w-r-1];
        g ^= G[b-w-1];
    }
    if (g == 0) {
        cout << "Bob\nAlice\n";
    } else {
        cout << "Alice\nBob\n";
    }
}