結果

問題 No.3003 多項式の割り算 〜hard〜
ユーザー ルク
提出日時 2025-01-17 21:33:41
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 36,575 bytes
コンパイル時間 2,716 ms
コンパイル使用メモリ 233,608 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2025-01-17 21:34:14
合計ジャッジ時間 3,514 ms
ジャッジサーバーID
(参考情報)
judge3 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 20
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:1365:33: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
 1365 |         void edge_update(int s, auto g)
      |                                 ^~~~
main.cpp:1391:35: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
 1391 |         bool try_reconnect(int s, auto f)
      |                                   ^~~~

ソースコード

diff #

#ifdef DEVELOPMENT
#include "./local.h"
#endif
// AtCoder用.
#ifdef ATCODER
// boost.
#if __has_include(<boost/multiprecision/cpp_int.hpp>)
#include <boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;
#endif
// atcoder.
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
using mint = modint998244353;
using MINT = modint1000000007;
#endif
#endif
// オンラインジャッジ用.
#if defined(ONLINE_JUDGE) || defined(EVAL)
// bits.
#if __has_include(<bits/stdc++.h>)
#include <bits/stdc++.h>
using namespace std;
#endif
// ヒューリスティック.
#include <chrono>
#include <random>
using namespace chrono;
#endif

// テンプレート.
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define REP(i, cc, n) for (ll i = cc; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i <= (n); ++i)
#define rrep(i, n) for (ll i = n; i > 0; --i)
#define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i)
#define all(a) (a).begin(), (a).end()
#define yesNo(b) ((b) ? "Yes" : "No")
using ll = long long;
using ull = unsigned long long;
using lll = __int128_t;
using ld = long double;
string alphabet = "abcdefghijklmnopqrstuvwxyz";
string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
constexpr double pi = 3.141592653589793;
constexpr ll smallMOD = 998244353;
constexpr ll bigMOD = 1000000007;
constexpr ll INF = 1LL << 60;
constexpr ll dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
constexpr ll dy[] = {0, 1, 0, -1, 1, 1, -1, -1};

// init.
struct Init
{
    Init()
    {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout << fixed << setprecision(15);
    }
} init;
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &vec)
{
    os << "[";
    rep(i, vec.size())
    {
        os << vec[i];
        if (i != vec.size() - 1)
            os << ", ";
    }
    os << "]";
    return os;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<vector<T>> &vec)
{
    os << "[";
    rep(i, vec.size())
    {
        os << vec[i];
        if (i != vec.size() - 1)
            os << ", ";
    }
    os << "]";
    return os;
}
template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &pair_var)
{
    os << "(" << pair_var.first << ", " << pair_var.second << ")";
    return os;
}
template <typename T>
ostream &operator<<(ostream &os, const set<T> &st)
{
    os << "{";
    for (auto itr = st.begin(); itr != st.end(); ++itr)
    {
        os << *itr;
        if (next(itr) != st.end())
            os << ", ";
    }
    os << "}";
    return os;
}
template <typename T>
ostream &operator<<(ostream &os, const set<T, greater<T>> &st)
{
    os << "{";
    for (auto itr = st.begin(); itr != st.end(); ++itr)
    {
        os << *itr;
        if (next(itr) != st.end())
            os << ", ";
    }
    os << "}";
    return os;
}
template <typename T>
ostream &operator<<(ostream &os, const multiset<T> &st)
{
    os << "{";
    for (auto itr = st.begin(); itr != st.end(); ++itr)
    {
        os << *itr;
        if (next(itr) != st.end())
            os << ", ";
    }
    os << "}";
    return os;
}
template <typename T>
ostream &operator<<(ostream &os, const multiset<T, greater<T>> &st)
{
    os << "{";
    for (auto itr = st.begin(); itr != st.end(); ++itr)
    {
        os << *itr;
        if (next(itr) != st.end())
            os << ", ";
    }
    os << "}";
    return os;
}
template <typename T>
ostream &operator<<(ostream &os, const queue<T> &que)
{
    queue<T> que2 = que;
    os << "{";
    while (!que2.empty())
    {
        os << que2.front();
        que2.pop();
        if (!que2.empty())
            os << ", ";
    }
    os << "}";
    return os;
}
template <typename T>
ostream &operator<<(ostream &os, const deque<T> &deq)
{
    os << "{";
    rep(i, deq.size())
    {
        os << deq[i];
        if (i != deq.size() - 1)
            os << ", ";
    }
    os << "}";
    return os;
}
template <typename T, typename U>
ostream &operator<<(ostream &os, const map<T, U> &mp)
{
    os << "{";
    for (auto itr = mp.begin(); itr != mp.end(); ++itr)
    {
        os << *itr;
        if (next(itr) != mp.end())
            os << ", ";
    }
    os << "}";
    return os;
}
template <typename T>
ostream &operator<<(ostream &os, const stack<T> &stk)
{
    stack<T> stk2 = stk;
    os << "{";
    while (!stk2.empty())
    {
        os << stk2.top();
        stk2.pop();
        if (!stk2.empty())
            os << ", ";
    }
    os << "}";
    return os;
}
template <typename T>
ostream &operator<<(ostream &os, const priority_queue<T> &que)
{
    priority_queue<T> que2 = que;
    os << "{";
    while (!que2.empty())
    {
        os << que2.top();
        que2.pop();
        if (!que2.empty())
            os << ", ";
    }
    os << "}";
    return os;
}
template <class T>
bool chmax(T &a, T b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, T b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
size_t HashCombine(const size_t seed, const T &v)
{
    return seed ^ (std::hash<T>()(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2));
}
template <class T, class S>
struct std::hash<std::pair<T, S>>
{
    size_t operator()(const std::pair<T, S> &keyval) const noexcept
    {
        return HashCombine(std::hash<T>()(keyval.first), keyval.second);
    }
};
template <class T>
struct std::hash<std::vector<T>>
{
    size_t operator()(const std::vector<T> &keyval) const noexcept
    {
        size_t s = 0;
        for (auto &&v : keyval)
            s = HashCombine(s, v);
        return s;
    }
};
template <int N>
struct HashTupleCore
{
    template <class Tuple>
    size_t operator()(const Tuple &keyval) const noexcept
    {
        size_t s = HashTupleCore<N - 1>()(keyval);
        return HashCombine(s, std::get<N - 1>(keyval));
    }
};
template <>
struct HashTupleCore<0>
{
    template <class Tuple>
    size_t operator()(const Tuple &keyval) const noexcept { return 0; }
};
template <class... Args>
struct std::hash<std::tuple<Args...>>
{
    size_t operator()(const tuple<Args...> &keyval) const noexcept
    {
        return HashTupleCore<tuple_size<tuple<Args...>>::value>()(keyval);
    }
};

// 約数列挙→O(√N).
vector<ll> all_divisors(ll N)
{
    vector<ll> res;
    for (ll i = 1; i * i <= N; ++i)
    {
        if (N % i != 0)
            continue;
        res.push_back(i);
        if (N / i != i)
            res.push_back(N / i);
    }
    sort(res.begin(), res.end());
    return res;
}

// 素因数分解→O(√N).
vector<pair<ll, ll>> prime_factorize(ll N)
{
    vector<pair<ll, ll>> res;
    for (ll p = 2; p * p <= N; ++p)
    {
        if (N % p != 0)
            continue;
        ll e = 0;
        while (N % p == 0)
        {
            ++e;
            N /= p;
        }
        res.emplace_back(p, e);
    }
    if (N != 1)
    {
        res.emplace_back(N, 1);
    }
    return res;
}

// 繰り返し二乗法→O(logY).
template <class T>
T pow_mod(T A, T N, T M)
{
    T res = 1 % M;
    A %= M;
    while (N)
    {
        if (N & 1)
            res = (res * A) % M;
        A = (A * A) % M;
        N >>= 1;
    }
    return res;
}

// 回文判定→O(N).
bool isPalindrome(string str)
{
    ll low = 0;
    ll high = str.length() - 1;
    while (low < high)
    {
        if (str[low] != str[high])
        {
            return false;
        }
        low++;
        high--;
    }
    return true;
}
map<char, ll> alphabetHash = {
    {'a', 2},
    {'b', 3},
    {'c', 5},
    {'d', 7},
    {'e', 11},
    {'f', 13},
    {'g', 17},
    {'h', 19},
    {'i', 23},
    {'j', 29},
    {'k', 31},
    {'l', 37},
    {'m', 41},
    {'n', 43},
    {'o', 47},
    {'p', 53},
    {'q', 59},
    {'r', 61},
    {'s', 67},
    {'t', 71},
    {'u', 73},
    {'v', 79},
    {'w', 83},
    {'x', 89},
    {'y', 97},
    {'z', 101},
};
// 文字列の数字に対するmod計算→O(|S|).
ll string_mod(string s, ll mod)
{
    ll rest = 0;
    for (char c : s)
    {
        ll v = c - '0';
        rest = (rest * 10 + v) % mod;
    }
    return rest;
}

// 二次元累積和.
struct CumulativeSum2D
{
    vector<vector<ll>> data;
    CumulativeSum2D(vector<vector<ll>> &source)
    {
        ll h = source.size();
        ll w = 0;
        if (h != 0)
            w = source[0].size();
        data.resize(h + 1, vector<ll>(w + 1, 0));
        rep(i, h)
        {
            rep(j, w)
            {
                data[i + 1][j + 1] = source[i][j];
            }
        }
        rep(i, h + 1)
        {
            rep(j, w)
            {
                data[i][j + 1] += data[i][j];
            }
        }
        rep(i, h)
        {
            rep(j, w + 1)
            {
                data[i + 1][j] += data[i][j];
            }
        }
    }
    // (x1,y1)から(x2,y2)までの矩形和→O(1).
    ll query(ll x1, ll y1, ll x2, ll y2)
    {
        return data[x2][y2] - data[x1][y2] - data[x2][y1] + data[x1][y1];
    }
};

// UnionFind.
struct UnionFind
{
    vector<ll> parent;
    vector<ll> parentSize;
    UnionFind(ll N)
    {
        rep(i, N + 1)
        {
            parent.push_back(i);
            parentSize.push_back(1);
        }
    }
    ll root(ll x)
    {
        if (parent[x] == x)
            return x;
        parent[x] = root(parent[x]);
        return parent[x];
    }
    bool unite(ll x, ll y)
    {
        x = root(x);
        y = root(y);
        if (x == y)
            return false;
        if (parentSize[x] > parentSize[y])
            swap(x, y);
        parent[x] = y;
        parentSize[y] += parentSize[x];
        return true;
    }
    bool same(ll x, ll y)
    {
        return root(x) == root(y);
    }
    ll size(ll x)
    {
        return parentSize[root(x)];
    }
};
struct RollBackUnionFind
{
    vector<ll> parent;
    stack<pair<ll, ll>> history;
    RollBackUnionFind(ll N)
    {
        parent.assign(N, -1);
    }
    ll root(ll x)
    {
        if (parent[x] < 0)
            return x;
        return root(parent[x]);
    }
    bool unite(ll x, ll y)
    {
        x = root(x);
        y = root(y);
        history.push({x, parent[x]});
        history.push({y, parent[y]});
        if (x == y)
            return false;
        if (parent[x] > parent[y])
            swap(x, y);
        parent[x] += parent[y];
        parent[y] = x;
        return true;
    }
    ll same(ll x, ll y)
    {
        return root(x) == root(y);
    }
    ll size(ll x)
    {
        return (-parent[root(x)]);
    }
    void undo()
    {
        parent[history.top().first] = history.top().second;
        history.pop();
        parent[history.top().first] = history.top().second;
        history.pop();
    }
    void snapshot()
    {
        while (!history.empty())
            history.pop();
    }
    void rollback()
    {
        while (!history.empty())
        {
            undo();
        }
    }
};

// Math.
struct NCR
{
    ll max = 510000, mod = 0;
    vector<ll> fact, inv, inv_fact;
    NCR(ll mod = 998244353)
    {
        this->mod = mod;
        fact.resize(max);
        inv.resize(max);
        inv_fact.resize(max);
        fact[0] = 1;
        fact[1] = 1;
        inv[0] = 1;
        inv[1] = 1;
        inv_fact[0] = 1;
        inv_fact[1] = 1;
        for (ll i = 2; i < max; i++)
        {
            fact[i] = fact[i - 1] * i % mod;
            inv[i] = mod - inv[mod % i] * (mod / i) % mod;
            inv_fact[i] = inv_fact[i - 1] * inv[i] % mod;
        }
    }
    ll nCr(ll n, ll r)
    {
        ll x = fact[n];
        ll y = inv_fact[n - r];
        ll z = inv_fact[r];
        if (n < r)
            return 0;
        if (n < 0 || r < 0)
            return 0;
        return x * ((y * z) % mod) % mod;
    }
};

// Graph.
struct Edge
{
    ll to;
    ll cost;
    Edge(ll to, ll cost) : to(to), cost(cost) {}
    bool operator>(const Edge &e) const
    {
        return cost > e.cost;
    }
};
struct Graph
{
    vector<vector<Edge>> g;
    Graph(ll n)
    {
        g.resize(n);
    }
    ll size()
    {
        return g.size();
    }
    void add_edge(ll from, ll to, ll cost = 1)
    {
        g[from].push_back(Edge(to, cost));
        g[to].push_back(Edge(from, cost));
    }
    void add_directed_edge(ll from, ll to, ll cost = 1)
    {
        g[from].push_back(Edge(to, cost));
    }
    pair<ll, vector<ll>> tree_diameter()
    {
        function<pair<ll, ll>(ll, ll)> dfs = [&](ll v, ll p) -> pair<ll, ll>
        {
            pair<ll, ll> res = {0, v};
            for (auto e : g[v])
            {
                if (e.to == p)
                    continue;
                auto [d, u] = dfs(e.to, v);
                d += e.cost;
                if (res.first < d)
                {
                    res.first = d;
                    res.second = u;
                }
            }
            return res;
        };
        auto [d, u] = dfs(0, -1);
        auto [d2, v] = dfs(u, -1);
        vector<ll> path;
        function<void(ll, ll, ll)> get_path = [&](ll v, ll p, ll u)
        {
            if (v == u)
            {
                path.push_back(v);
                return;
            }
            for (auto e : g[v])
            {
                if (e.to == p)
                    continue;
                get_path(e.to, v, u);
                if (!path.empty())
                {
                    path.push_back(v);
                    return;
                }
            }
        };
        get_path(u, -1, v);
        return {d2, path};
    }
    vector<Edge> &operator[](ll v)
    {
        return g[v];
    }
};
struct Dijkstra
{
    vector<ll> dist;
    vector<ll> prev;

    // dijkstraを構築
    Dijkstra(Graph &g, ll s)
    {
        ll n = g.size();
        dist.assign(n, INF);
        prev.assign(n, -1);
        priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
        dist[s] = 0;
        pq.emplace(dist[s], s);
        while (!pq.empty())
        {
            auto p = pq.top();
            pq.pop();
            ll v = p.second;
            if (dist[v] < p.first)
                continue;
            for (auto &e : g[v])
            {
                if (dist[e.to] > dist[v] + e.cost)
                {
                    dist[e.to] = dist[v] + e.cost;
                    prev[e.to] = v;
                    pq.emplace(dist[e.to], e.to);
                }
            }
        }
    }

    // 最小コストを求める
    ll get_cost(ll to)
    {
        return dist[to];
    }

    // 最短経路を求める
    vector<ll> get_path(ll to)
    {
        vector<ll> get_path;
        for (ll i = to; i != -1; i = prev[i])
        {
            get_path.push_back(i);
        }
        reverse(get_path.begin(), get_path.end());
        return get_path;
    }

    // 到達可能か調べる
    bool cango(ll to)
    {
        return (dist[to] != INF);
    }
};
struct Bellman_ford
{
    vector<ll> dist;
    vector<ll> prev;
    ll start;
    ll size;
    bool cl = false;

    // bellman_fordを構築
    Bellman_ford(Graph &g, ll s)
    {
        start = s;
        ll n = g.size();
        size = n;
        dist.assign(n, INF);
        prev.assign(n, -1);
        vector<ll> counts(n);
        vector<bool> inqueue(n);

        queue<ll> q;
        dist[s] = 0;
        q.push(s);
        inqueue[s] = true;

        while (!q.empty())
        {
            ll from = q.front();
            q.pop();
            inqueue[from] = false;

            for (auto &e : g[from])
            {
                ll d = dist[from] + e.cost;
                if (d < dist[e.to])
                {
                    dist[e.to] = d;
                    prev[e.to] = from;
                    if (!inqueue[e.to])
                    {
                        q.push(e.to);
                        inqueue[e.to] = true;
                        ++counts[e.to];

                        if (n < counts[e.to])
                            cl = true;
                    }
                }
            }
        }
    }

    // 最小コストを求める
    ll get_cost(ll to)
    {
        return dist[to];
    }

    // 最短経路を求める
    vector<ll> get_path(ll to)
    {
        vector<ll> path;
        if (dist[to] != INF)
        {
            for (ll i = to; i != -1; i = prev[i])
            {
                path.push_back(i);
            }
            reverse(path.begin(), path.end());
        }
        return path;
    }

    // 到達可能か調べる
    bool cango(ll to)
    {
        return (dist[to] != INF);
    }

    // 閉路の有無を調べる
    bool closed()
    {
        return cl;
    }
};
struct Warshall_floyd
{
    vector<vector<ll>> d;
    vector<vector<ll>> next;
    bool cl = false;

    // warshall_floydを構築
    Warshall_floyd(Graph &g)
    {
        ll n = g.size();
        d.resize(n, vector<ll>(n, INF));
        next.resize(n, vector<ll>(n, -1));

        for (ll i = 0; i < n; i++)
        {
            d[i][i] = 0;
        }

        for (ll i = 0; i < n; i++)
        {
            for (auto e : g[i])
            {
                d[i][e.to] = e.cost;
                next[i][e.to] = e.to;
            }
        }

        for (ll k = 0; k < n; ++k)
        {
            for (ll i = 0; i < n; ++i)
            {
                for (ll j = 0; j < n; ++j)
                {
                    if (d[i][j] > d[i][k] + d[k][j])
                    {
                        d[i][j] = d[i][k] + d[k][j];
                        next[i][j] = next[i][k];
                    }
                }
            }
        }

        for (ll i = 0; i < n; i++)
        {
            if (d[i][i] < 0)
            {
                cl = true;
                break;
            }
        }
    }

    // 最小コストを求める
    ll get_cost(ll from, ll to)
    {
        return d[from][to];
    }

    // 最短経路を求める
    vector<ll> get_path(ll from, ll to)
    {
        if (d[from][to] == INF)
            return {};
        vector<ll> path;
        for (ll at = from; at != to; at = next[at][to])
        {
            if (at == -1)
                return {};
            path.push_back(at);
        }
        path.push_back(to);
        return path;
    }

    // 到達可能か調べる
    bool cango(ll from, ll to)
    {
        return d[from][to] != INF;
    }

    // 負の閉路の有無を調べる
    bool closed()
    {
        return cl;
    }
};

// others.
struct Timer
{
    Timer(ll ms) : duration(ms), start_time(steady_clock::now()) {}
    bool isTimeOver() const
    {
        auto current_time = steady_clock::now();
        auto elapsed = duration_cast<milliseconds>(current_time - start_time).count();
        return elapsed >= duration;
    }
    ll duration;
    steady_clock::time_point start_time;
};

class FunctionalGraph
{
private:
    const ll V;
    ll loop_id;
    vector<ll> nx;
    void make_loop(const ll st, ll nw, vector<ll> &vec)
    {
        while (nx[nw] != st)
        {
            vec.push_back(nx[nw]);
            visit[nx[nw]] = loop_id;
            nw = nx[nw];
        }
    }
    ll dfs(ll u, vector<ll> &vec)
    {
        visit[u] = -loop_id;
        ll v = nx[u];
        if (visit[v] == -loop_id)
        {
            vec.push_back(u), vec.push_back(v);
            visit[u] = visit[v] = loop_id;
            make_loop(u, v, vec);
            loop_id++;
            return 0;
        }
        else if (visit[v] == 0)
        {
            const ll res = dfs(v, vec);
            if (res == 0)
                return 0;
            else
                return visit[u] = res;
        }
        return visit[u] = (visit[v] > 0 ? -visit[v] : visit[v]);
    }
    void make_graph()
    {
        graph.resize(V);
        for (ll i = 0; i < V; i++)
        {
            if (visit[i] < 0)
                graph[nx[i]].push_back(i);
        }
    }

public:
    vector<ll> visit;
    vector<vector<ll>> loop, graph;
    FunctionalGraph(const ll node_size)
        : V(node_size), loop_id(1), nx(V, 0), visit(V, 0) {}
    void add_edge(ll u, ll v)
    {
        nx[u] = v;
        if (u == nx[u])
            visit[u] = loop_id++, loop.push_back({u});
    }
    void solve()
    {
        for (ll i = 0; i < V; i++)
        {
            if (visit[i] == 0)
            {
                vector<ll> vec;
                dfs(i, vec);
                if (!vec.empty())
                    loop.push_back(move(vec));
            }
        }
    }
};

ll non_mod_ncr(ll n, ll r)
{
    ll res = 1;
    for (ll i = 0; i < r; i++)
    {
        res *= (n - i);
    }
    for (ll i = 0; i < r; i++)
    {
        res /= (i + 1);
    }
    return res;
}

// 前計算O(N log N)、クエリO(log N)
struct FastTruthFactorizes
{
public:
    ll N_MAX;
    vector<ll> spf;
    FastTruthFactorizes(ll N_MAX)
    {
        this->N_MAX = N_MAX;
        spf.resize(N_MAX);
        rep(i, N_MAX) spf[i] = i;
        // 調和級数の和でO(N log N).
        for (ll p = 2; p * p <= N_MAX; p++)
        {
            for (int i = p; i < N_MAX; i += p)
            {
                if (spf[i] == i)
                    spf[i] = p;
            }
        }
    }
    // 素因数分解するO(log N).
    map<ll, ll> factorize(ll n)
    {
        map<ll, ll> mp;
        while (n != 1)
        {
            ll p = spf[n];
            mp[p]++;
            n /= p;
        }
        return mp;
    }
    // 約数を列挙するO(log N).
    vector<ll> calcDevisors(ll n)
    {
        vector<ll> Y;
        auto mp = factorize(n);
        vector<pair<ll, ll>> V;
        for (auto pa : mp)
        {
            V.push_back(pa);
        }
        dfs(0, 1, Y, V);
        return Y;
    }

private:
    void dfs(ll cur_idx, ll cur_val, vector<ll> &Y, vector<pair<ll, ll>> &mp)
    {
        ll N = mp.size();
        if (cur_idx == N)
        {
            Y.push_back(cur_val);
            return;
        }
        ll v = mp[cur_idx].first;
        ll c = mp[cur_idx].second;
        ll mul = 1;
        rep(p, c + 1)
        {
            dfs(cur_idx + 1, cur_val * mul, Y, mp);
            mul *= v;
        }
        return;
    }
};

// 素数判定O(1).
bool millerRabin(ll num)
{
    if (num == 1)
        return false;
    if (num == 2)
        return true;
    if (num % 2 == 0)
        return false;
    ll d = num - 1;
    ll s = 0;
    while (d % 2 == 0)
    {
        d /= 2;
        s++;
    }
    vector<ll> primes;
    if (num < 4759123141LL)
    {
        primes = {2, 7, 61};
    }
    else
    {
        primes = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
    }
    for (auto &p : primes)
    {
        if (p >= num)
            return true;
        ll t, x = pow_mod<lll>(p, d, num);
        if (x != 1)
        {
            for (t = 0; t < s; t++)
            {
                if (x == num - 1)
                    break;
                x = lll(x) * x % num;
            }
            if (t == s)
                return false;
        }
    }
    return true;
}

// エラトステネスの篩O(N log log N).
vector<ll> eratosthenes(ll target)
{
    ll limit = sqrtl(target) + 1;
    vector<bool> primes(target + 1, true);
    primes[0] = primes[1] = false;

    for (ll n = 2; n <= limit; ++n)
    {
        if (primes[n])
        {
            for (ll multiple = n * 2; multiple <= target; multiple += n)
            {
                primes[multiple] = false;
            }
        }
    }

    vector<ll> result;
    for (ll i = 0; i <= target; ++i)
    {
        if (primes[i])
        {
            result.push_back(i);
        }
    }

    return result;
}

template <typename T>
bool next_combination(const T first, const T last, int k)
{
    const T subset = first + k;
    if (first == last || first == subset || last == subset)
    {
        return false;
    }
    T src = subset;
    while (first != src)
    {
        src--;
        if (*src < *(last - 1))
        {
            T dest = subset;
            while (*src >= *dest)
            {
                dest++;
            }
            iter_swap(src, dest);
            rotate(src + 1, dest + 1, last);
            rotate(subset, subset + (last - dest) - 1, last);
            return true;
        }
    }
    rotate(first, subset, last);
    return false;
}

template <typename T>
class dynamic_connectivity
{
    class euler_tour_tree
    {
    public:
        struct node;
        using np = node *;
        using lint = long long;
        struct node
        {
            np ch[2] = {nullptr, nullptr};
            np p = nullptr;
            int l, r, sz;
            T val = et, sum = et;
            bool exact;
            bool child_exact;
            bool edge_connected = 0;
            bool child_edge_connected = 0;
            node() {}
            node(int l, int r) : l(l), r(r), sz(l == r), exact(l < r), child_exact(l < r) {}
            bool is_root()
            {
                return !p;
            }
        };
        vector<unordered_map<int, np>> ptr;
        np get_node(int l, int r)
        {
            if (ptr[l].find(r) == ptr[l].end())
                ptr[l][r] = new node(l, r);
            return ptr[l][r];
        }
        np root(np t)
        {
            if (!t)
                return t;
            while (t->p)
                t = t->p;
            return t;
        }
        bool same(np s, np t)
        {
            if (s)
                splay(s);
            if (t)
                splay(t);
            return root(s) == root(t);
        }
        np reroot(np t)
        {
            auto s = split(t);
            return merge(s.second, s.first);
        }
        pair<np, np> split(np s)
        {
            splay(s);
            np t = s->ch[0];
            if (t)
                t->p = nullptr;
            s->ch[0] = nullptr;
            return {t, update(s)};
        }
        pair<np, np> split2(np s)
        {
            splay(s);
            np t = s->ch[0];
            np u = s->ch[1];
            if (t)
                t->p = nullptr;
            s->ch[0] = nullptr;
            if (u)
                u->p = nullptr;
            s->ch[1] = nullptr;
            return {t, u};
        }
        tuple<np, np, np> split(np s, np t)
        {
            auto u = split2(s);
            if (same(u.first, t))
            {
                auto r = split2(t);
                return make_tuple(r.first, r.second, u.second);
            }
            else
            {
                auto r = split2(t);
                return make_tuple(u.first, r.first, r.second);
            }
        }
        template <typename First, typename... Rest>
        np merge(First s, Rest... t)
        {
            return merge(s, merge(t...));
        }
        np merge(np s, np t)
        {
            if (!s)
                return t;
            if (!t)
                return s;
            while (s->ch[1])
                s = s->ch[1];
            splay(s);
            s->ch[1] = t;
            if (t)
                t->p = s;
            return update(s);
        }
        int size(np t) { return t ? t->sz : 0; }
        np update(np t)
        {
            t->sum = et;
            if (t->ch[0])
                t->sum = fn(t->sum, t->ch[0]->sum);
            if (t->l == t->r)
                t->sum = fn(t->sum, t->val);
            if (t->ch[1])
                t->sum = fn(t->sum, t->ch[1]->sum);
            t->sz = size(t->ch[0]) + (t->l == t->r) + size(t->ch[1]);
            t->child_edge_connected = (t->ch[0] ? t->ch[0]->child_edge_connected : 0) | (t->edge_connected) | (t->ch[1] ? t->ch[1]->child_edge_connected : 0);
            t->child_exact = (t->ch[0] ? t->ch[0]->child_exact : 0) | (t->exact) | (t->ch[1] ? t->ch[1]->child_exact : 0);
            return t;
        }
        void push(np t)
        {
            // 遅延評価予定
        }
        void rot(np t, bool b)
        {
            np x = t->p, y = x->p;
            if ((x->ch[1 - b] = t->ch[b]))
                t->ch[b]->p = x;
            t->ch[b] = x, x->p = t;
            update(x);
            update(t);
            if ((t->p = y))
            {
                if (y->ch[0] == x)
                    y->ch[0] = t;
                if (y->ch[1] == x)
                    y->ch[1] = t;
                update(y);
            }
        }
        void splay(np t)
        {
            push(t);
            while (!t->is_root())
            {
                np q = t->p;
                if (q->is_root())
                {
                    push(q), push(t);
                    rot(t, q->ch[0] == t);
                }
                else
                {
                    np r = q->p;
                    push(r), push(q), push(t);
                    bool b = r->ch[0] == q;
                    if (q->ch[1 - b] == t)
                        rot(q, b), rot(t, b);
                    else
                        rot(t, 1 - b), rot(t, b);
                }
            }
        }
        void debug(np t)
        {
            if (!t)
                return;
            debug(t->ch[0]);
            cerr << t->l << "-" << t->r << " ";
            debug(t->ch[1]);
        }

    public:
        euler_tour_tree() {}
        euler_tour_tree(int sz)
        {
            ptr.resize(sz);
            for (int i = 0; i < sz; i++)
                ptr[i][i] = new node(i, i);
        }
        int size(int s)
        {
            np t = get_node(s, s);
            splay(t);
            return t->sz;
        }
        bool same(int s, int t)
        {
            return same(get_node(s, s), get_node(t, t));
        }
        void set_size(int sz)
        {
            ptr.resize(sz);
            for (int i = 0; i < sz; i++)
                ptr[i][i] = new node(i, i);
        }
        void update(int s, T x)
        {
            np t = get_node(s, s);
            splay(t);
            t->val = fn(t->val, x);
            update(t);
        }
        void edge_update(int s, auto g)
        {
            np t = get_node(s, s);
            splay(t);
            function<void(np)> dfs = [&](np t)
            {
                assert(t);
                if (t->l < t->r && t->exact)
                {
                    splay(t);
                    t->exact = 0;
                    update(t);
                    g(t->l, t->r);
                    return;
                }
                if (t->ch[0] && t->ch[0]->child_exact)
                    dfs(t->ch[0]);
                else
                    dfs(t->ch[1]);
            };
            while (t && t->child_exact)
            {
                dfs(t);
                splay(t);
            }
        }
        bool try_reconnect(int s, auto f)
        {
            np t = get_node(s, s);
            splay(t);
            function<bool(np)> dfs = [&](np t) -> bool
            {
                assert(t);
                if (t->edge_connected)
                {
                    splay(t);
                    return f(t->l);
                }
                if (t->ch[0] && t->ch[0]->child_edge_connected)
                    return dfs(t->ch[0]);
                else
                    return dfs(t->ch[1]);
            };
            while (t->child_edge_connected)
            {
                if (dfs(t))
                    return 1;
                splay(t);
            }
            return 0;
        }
        void edge_connected_update(int s, bool b)
        {
            np t = get_node(s, s);
            splay(t);
            t->edge_connected = b;
            update(t);
        }
        bool link(int l, int r)
        {
            if (same(l, r))
                return 0;
            merge(reroot(get_node(l, l)), get_node(l, r), reroot(get_node(r, r)), get_node(r, l));
            return 1;
        }
        bool cut(int l, int r)
        {
            if (ptr[l].find(r) == ptr[l].end())
                return 0;
            np s, t, u;
            tie(s, t, u) = split(get_node(l, r), get_node(r, l));
            merge(s, u);
            np p = ptr[l][r];
            np q = ptr[r][l];
            ptr[l].erase(r);
            ptr[r].erase(l);
            delete p;
            delete q;
            return 1;
        }
        T get_sum(int p, int v)
        {
            cut(p, v);
            np t = get_node(v, v);
            splay(t);
            T res = t->sum;
            link(p, v);
            return res;
        }
        T get_sum(int s)
        {
            np t = get_node(s, s);
            splay(t);
            return t->sum;
        }
    };
    int dep = 1;
    vector<euler_tour_tree> ett;
    vector<vector<unordered_set<int>>> edges;
    int sz;

public:
    dynamic_connectivity(int sz) : sz(sz)
    {
        ett.emplace_back(sz);
        edges.emplace_back(sz);
    }
    bool link(int s, int t)
    {
        if (s == t)
            return 0;
        if (ett[0].link(s, t))
            return 1;
        edges[0][s].insert(t);
        edges[0][t].insert(s);
        if (edges[0][s].size() == 1)
            ett[0].edge_connected_update(s, 1);
        if (edges[0][t].size() == 1)
            ett[0].edge_connected_update(t, 1);
        return 0;
    }
    bool same(int s, int t)
    {
        return ett[0].same(s, t);
    }
    int size(int s)
    {
        return ett[0].size(s);
    }
    vector<int> get_vertex(int s)
    {
        return ett[0].vertex_list(s);
    }
    void update(int s, T x)
    {
        ett[0].update(s, x);
    }
    T get_sum(int s)
    {
        return ett[0].get_sum(s);
    }
    bool cut(int s, int t)
    {
        if (s == t)
            return 0;
        for (int i = 0; i < dep; i++)
        {
            edges[i][s].erase(t);
            edges[i][t].erase(s);
            if (edges[i][s].size() == 0)
                ett[i].edge_connected_update(s, 0);
            if (edges[i][t].size() == 0)
                ett[i].edge_connected_update(t, 0);
        }
        for (int i = dep - 1; i >= 0; i--)
        {
            if (ett[i].cut(s, t))
            {
                if (dep - 1 == i)
                {
                    dep++;
                    ett.emplace_back(sz);
                    edges.emplace_back(sz);
                }
                return !try_reconnect(s, t, i);
            }
        }
        return 0;
    }
    bool try_reconnect(int s, int t, int k)
    {
        for (int i = 0; i < k; i++)
        {
            ett[i].cut(s, t);
        }
        for (int i = k; i >= 0; i--)
        {
            if (ett[i].size(s) > ett[i].size(t))
                swap(s, t);
            auto g = [&](int s, int t)
            { ett[i + 1].link(s, t); };
            ett[i].edge_update(s, g);
            auto f = [&](int x) -> bool
            {
                for (auto itr = edges[i][x].begin(); itr != edges[i][x].end();)
                {
                    auto y = *itr;
                    itr = edges[i][x].erase(itr);
                    edges[i][y].erase(x);
                    if (edges[i][x].size() == 0)
                        ett[i].edge_connected_update(x, 0);
                    if (edges[i][y].size() == 0)
                        ett[i].edge_connected_update(y, 0);
                    if (ett[i].same(x, y))
                    {
                        edges[i + 1][x].insert(y);
                        edges[i + 1][y].insert(x);
                        if (edges[i + 1][x].size() == 1)
                            ett[i + 1].edge_connected_update(x, 1);
                        if (edges[i + 1][y].size() == 1)
                            ett[i + 1].edge_connected_update(y, 1);
                    }
                    else
                    {
                        for (int j = 0; j <= i; j++)
                        {
                            ett[j].link(x, y);
                        }
                        return 1;
                    }
                }
                return 0;
            };
            if (ett[i].try_reconnect(s, f))
                return 1;
        }
        return 0;
    }
    constexpr static T et = T();
    constexpr static T fn(T s, T t)
    {
        return s + t;
    }
};

int main()
{
    ll a, b;
    cin >> a >> b;
    if (b % 3 == 0)
    {
        cout << 0 << " " << a << endl;
    }
    else if (b % 3 == 1)
    {
        cout << a << " " << 0 << endl;
    }
    else
    {
        cout << -a << " " << -a << endl;
    }
    return 0;
}
0