CSES - Aalto Competitive Programming 2024 - wk8 - Wed - Results
Submission details
Task:A TIMES B!
Sender:AleksandrPolitov
Submission time:2024-10-30 17:46:36 +0200
Language:C++
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#2ACCEPTED0.00 sdetails
#3ACCEPTED0.00 sdetails
#4ACCEPTED0.00 sdetails
#5ACCEPTED0.00 sdetails
#6ACCEPTED0.00 sdetails
#7ACCEPTED0.00 sdetails
#8ACCEPTED0.00 sdetails
#9ACCEPTED0.00 sdetails
#10ACCEPTED0.00 sdetails
#11ACCEPTED0.00 sdetails
#12ACCEPTED0.00 sdetails
#13ACCEPTED0.00 sdetails
#14ACCEPTED0.00 sdetails
#15ACCEPTED0.00 sdetails
#16ACCEPTED0.00 sdetails
#17ACCEPTED0.00 sdetails
#18ACCEPTED0.00 sdetails
#19ACCEPTED0.00 sdetails
#20ACCEPTED0.00 sdetails
#21ACCEPTED0.00 sdetails
#22ACCEPTED0.00 sdetails
#23ACCEPTED0.00 sdetails
#24ACCEPTED0.00 sdetails
#25ACCEPTED0.00 sdetails
#26ACCEPTED0.00 sdetails
#27ACCEPTED0.00 sdetails
#28ACCEPTED0.00 sdetails
#29ACCEPTED0.00 sdetails
#30ACCEPTED0.00 sdetails
#31ACCEPTED0.00 sdetails
#32ACCEPTED0.00 sdetails
#33ACCEPTED0.00 sdetails
#34ACCEPTED0.00 sdetails
#35ACCEPTED0.00 sdetails
#36ACCEPTED0.00 sdetails
#37ACCEPTED0.00 sdetails
#38ACCEPTED0.00 sdetails
#39ACCEPTED0.00 sdetails
#40ACCEPTED0.00 sdetails
#41ACCEPTED0.00 sdetails
#42ACCEPTED0.00 sdetails
#43ACCEPTED0.00 sdetails
#44ACCEPTED0.00 sdetails
#45ACCEPTED0.00 sdetails
#46ACCEPTED0.00 sdetails
#47ACCEPTED0.00 sdetails
#48ACCEPTED0.00 sdetails
#49ACCEPTED0.00 sdetails
#50ACCEPTED0.00 sdetails
#51ACCEPTED0.00 sdetails
#52ACCEPTED0.00 sdetails
#53ACCEPTED0.00 sdetails
#54ACCEPTED0.00 sdetails
#55ACCEPTED0.00 sdetails
#56ACCEPTED0.04 sdetails
#57ACCEPTED0.04 sdetails
#58ACCEPTED0.04 sdetails
#59ACCEPTED0.04 sdetails
#60ACCEPTED0.02 sdetails
#61ACCEPTED0.32 sdetails
#62ACCEPTED0.35 sdetails
#63ACCEPTED0.40 sdetails
#64ACCEPTED0.16 sdetails
#65ACCEPTED0.32 sdetails

Compiler report

input/code.cpp: In function 'int solve()':
input/code.cpp:324:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  324 |     for (int i = 0; i < a.size(); i++) A[i]=a[i]-'0';
      |                     ~~^~~~~~~~~~
input/code.cpp:325:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  325 |     for (int i = 0; i < b.size(); i++) B[i]=b[i]-'0';
      |                     ~~^~~~~~~~~~
input/code.cpp:332:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  332 |     for (int i = 0; i < ab.size()-1; i++) {
      |                     ~~^~~~~~~~~~~~~
input/code.cpp:339:23: warning: comparison of integer expressions of different signedness:...

Code

#ifdef ONPC
    #define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>

#define char unsigned char
#define rep(i, a, b) for(int i=a; i< (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back

#define LSOne(S) ((S) & -(S))

using namespace std;
// mt19937 rnd(239);
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

template <typename T> int sgn(T x) { return (T(0) < x) - (x < T(0)); }
typedef long double T;
typedef complex<T> pt;
#define X real()
#define Y imag()

template<class T>
istream& operator>> (istream& is, complex<T>& p) {
    T value;
    is >> value;
    p.real(value);
    is >> value;
    p.imag(value);
    return is;
}

typedef long long ll;
typedef long double ld;

using pi = pair<ll, ll>;
using vi = vector<ll>;
template <class T>
using pq = priority_queue<T>;
template <class T>
using pqg = priority_queue<T, vector<T>, greater<T>>;

int popcnt(int x) { return __builtin_popcount(x); }
int popcnt(ll x) { return __builtin_popcountll(x); }

#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define LB(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define UB(c, x) distance((c).begin(), upper_bound(all(c), (x)))

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef DEBUG
#define dbg(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << endl;
#else
#define dbg(x...)
#endif

template<typename S, typename T = S> void chmin(S &s, T t) {s = s < t ? s : t;}
template<typename S, typename T = S> void chmax(S &s, T t) {s = s > t ? s : t;}

const int INF = 1e9; // 10^9 = 1B is < 2^31-1
const ll LLINF = 4e18; // 4*10^18 is < 2^63-1
const double EPS = 1e-9;
const ll MOD = 1e9+7;

namespace fft {
    struct cmpl {
        double x, y;
        cmpl() {
            x = y = 0;
        }
        cmpl(double x, double y) : x(x), y(y) {}
        inline cmpl conjugated() const {
            return cmpl(x, -y);
        }
    };
    inline cmpl operator+(cmpl a, cmpl b) {
        return cmpl(a.x + b.x, a.y + b.y);
    }
    inline cmpl operator-(cmpl a, cmpl b) {
        return cmpl(a.x - b.x, a.y - b.y);
    }
    inline cmpl operator*(cmpl a, cmpl b) {
        return cmpl(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
    }

    int base = 1; // current power of two (2^base >= n)
    vector<cmpl> roots = {{0, 0}, {1, 0}}; // complex roots of 1 (with bases from 1 to base), 1-based indexing
    vector<int> rev = {0, 1}; // rev[i] = reversed bit representation of i
    const double PI = static_cast<double>(acosl(-1.0));

    void ensure_base(int nbase) { // if base < nbase increase it
        if (nbase <= base) {
            return;
        }
        rev.resize(1 << nbase);
        for (int i = 1; i < (1 << nbase); i++) {
            rev[i] = (rev[i >> 1] >> 1) + ((i & 1) << (nbase - 1));
        }
        roots.resize(1 << nbase);
        while (base < nbase) {
            double angle = 2 * PI / (1 << (base + 1));
            for (int i = 1 << (base - 1); i < (1 << base); i++) {
                roots[i << 1] = roots[i];
                double angle_i = angle * (2 * i + 1 - (1 << base));
                roots[(i << 1) + 1] = cmpl(cos(angle_i), sin(angle_i));
            }
            base++;
        }
    }

    void fft(vector<cmpl>& a, int n = -1) {
        if (n == -1) {
            n = (int) a.size();
        }
        assert((n & (n - 1)) == 0); // ensure that n is a power of two
        int zeros = __builtin_ctz(n);
        ensure_base(zeros);
        int shift = base - zeros;
        for (int i = 0; i < n; i++) {
            if (i < (rev[i] >> shift)) {
                swap(a[i], a[rev[i] >> shift]);
            }
        }
        for (int k = 1; k < n; k <<= 1) {
            for (int i = 0; i < n; i += 2 * k) {
                for (int j = 0; j < k; j++) {
                    cmpl z = a[i + j + k] * roots[j + k];
                    a[i + j + k] = a[i + j] - z;
                    a[i + j] = a[i + j] + z;
                }
            }
        }
    }

    vector<cmpl> fa, fb;

    vector<long long> square(const vector<int>& a) {
        if (a.empty()) {
            return {};
        }
        int need = (int) a.size() + (int) a.size() - 1;
        int nbase = 1;
        while ((1 << nbase) < need) {
            nbase++;
        }
        ensure_base(nbase);
        int sz = 1 << nbase;
        if ((sz >> 1) > (int) fa.size()) {
            fa.resize(sz >> 1);
        }
        for (int i = 0; i < (sz >> 1); i++) {
            int x = (2 * i < (int) a.size() ? a[2 * i] : 0);
            int y = (2 * i + 1 < (int) a.size() ? a[2 * i + 1] : 0);
            fa[i] = cmpl(x, y);
        }
        fft(fa, sz >> 1);
        cmpl r(1.0 / (sz >> 1), 0.0);
        for (int i = 0; i <= (sz >> 2); i++) {
            int j = ((sz >> 1) - i) & ((sz >> 1) - 1);
            cmpl fe = (fa[i] + fa[j].conjugated()) * cmpl(0.5, 0);
            cmpl fo = (fa[i] - fa[j].conjugated()) * cmpl(0, -0.5);
            cmpl aux = fe * fe + fo * fo * roots[(sz >> 1) + i] * roots[(sz >> 1) + i];
            cmpl tmp = fe * fo;
            fa[i] = r * (aux.conjugated() + cmpl(0, 2) * tmp.conjugated());
            fa[j] = r * (aux + cmpl(0, 2) * tmp);
        }
        fft(fa, sz >> 1);
        vector<long long> res(need);
        for (int i = 0; i < need; i++) {
            res[i] = llround(i % 2 == 0 ? fa[i >> 1].x : fa[i >> 1].y);
        }
        return res;
    }
    
    // interface

    vector<long long> multiply(const vector<int>& a, const vector<int>& b) {
        if (a.empty() || b.empty()) {
            return {};
        }
        if (a == b) {
            return square(a);
        }
        int need = (int) a.size() + (int) b.size() - 1;
        int nbase = 1;
        while ((1 << nbase) < need) nbase++;
        ensure_base(nbase);
        int sz = 1 << nbase;
        if (sz > (int) fa.size()) {
            fa.resize(sz);
        }
        for (int i = 0; i < sz; i++) {
            int x = (i < (int) a.size() ? a[i] : 0);
            int y = (i < (int) b.size() ? b[i] : 0);
            fa[i] = cmpl(x, y);
        }
        fft(fa, sz);
        cmpl r(0, -0.25 / (sz >> 1));
        for (int i = 0; i <= (sz >> 1); i++) {
            int j = (sz - i) & (sz - 1);
            cmpl z = (fa[j] * fa[j] - (fa[i] * fa[i]).conjugated()) * r;
            fa[j] = (fa[i] * fa[i] - (fa[j] * fa[j]).conjugated()) * r;
            fa[i] = z;
        }
        for (int i = 0; i < (sz >> 1); i++) {
            cmpl A0 = (fa[i] + fa[i + (sz >> 1)]) * cmpl(0.5, 0);
            cmpl A1 = (fa[i] - fa[i + (sz >> 1)]) * cmpl(0.5, 0) * roots[(sz >> 1) + i];
            fa[i] = A0 + A1 * cmpl(0, 1);
        }
        fft(fa, sz >> 1);
        vector<long long> res(need);
        for (int i = 0; i < need; i++) {
        res[i] = llround(i % 2 == 0 ? fa[i >> 1].x : fa[i >> 1].y);
        }
        return res;
    }

    vector<int> multiply_mod(const vector<int>& a, const vector<int>& b, int m) {
        if (a.empty() || b.empty()) {
            return {};
        }
        int need = (int) a.size() + (int) b.size() - 1;
        int nbase = 0;
        while ((1 << nbase) < need) {
            nbase++;
        }
        ensure_base(nbase);
        int sz = 1 << nbase;
        if (sz > (int) fa.size()) {
            fa.resize(sz);
        }
        for (int i = 0; i < (int) a.size(); i++) {
            int x = (a[i] % m + m) % m;
            fa[i] = cmpl(x & ((1 << 15) - 1), x >> 15);
        }
        fill(fa.begin() + a.size(), fa.begin() + sz, cmpl{0, 0});
        fft(fa, sz);
        if (sz > (int) fb.size()) {
            fb.resize(sz);
        }
        if (a == b) {
            copy(fa.begin(), fa.begin() + sz, fb.begin());
        } else {
            for (int i = 0; i < (int) b.size(); i++) {
                int x = (b[i] % m + m) % m;
                fb[i] = cmpl(x & ((1 << 15) - 1), x >> 15);
            }
            fill(fb.begin() + b.size(), fb.begin() + sz, cmpl{0, 0});
            fft(fb, sz);
        }
        double ratio = 0.25 / sz;
        cmpl r2(0, -1);
        cmpl r3(ratio, 0);
        cmpl r4(0, -ratio);
        cmpl r5(0, 1);
        for (int i = 0; i <= (sz >> 1); i++) {
            int j = (sz - i) & (sz - 1);
            cmpl a1 = (fa[i] + fa[j].conjugated());
            cmpl a2 = (fa[i] - fa[j].conjugated()) * r2;
            cmpl b1 = (fb[i] + fb[j].conjugated()) * r3;
            cmpl b2 = (fb[i] - fb[j].conjugated()) * r4;
            if (i != j) {
                cmpl c1 = (fa[j] + fa[i].conjugated());
                cmpl c2 = (fa[j] - fa[i].conjugated()) * r2;
                cmpl d1 = (fb[j] + fb[i].conjugated()) * r3;
                cmpl d2 = (fb[j] - fb[i].conjugated()) * r4;
                fa[i] = c1 * d1 + c2 * d2 * r5;
                fb[i] = c1 * d2 + c2 * d1;
            }
            fa[j] = a1 * b1 + a2 * b2 * r5;
            fb[j] = a1 * b2 + a2 * b1;
        }
        fft(fa, sz);
        fft(fb, sz);
        vector<int> res(need);
        for (int i = 0; i < need; i++) {
            long long aa = llround(fa[i].x);
            long long bb = llround(fb[i].x);
            long long cc = llround(fa[i].y);
            res[i] = static_cast<int>((aa + ((bb % m) << 15) + ((cc % m) << 30)) % m);
        }
        return res;
    }
}  // namespace fft
/*
use these:
vector<int> multiply_mod(const vector<int>& a, const vector<int>& b, int m)
vector<ll> square(const vector<int>& a)
vector<ll> multiply(const vector<int>& a, const vector<int>& b) // (if a == b it uses square)
*/

int solve() {
    string a,b;std::cin >> a >> b;
    reverse(all(a));
    reverse(all(b));
    vector<int> A(a.size()), B(b.size());
    for (int i = 0; i < a.size(); i++) A[i]=a[i]-'0';
    for (int i = 0; i < b.size(); i++) B[i]=b[i]-'0';

    vector<ll> ab=fft::multiply(A,B);
    ab.pb(0);


    string res="";
    for (int i = 0; i < ab.size()-1; i++) {
        if(ab[i]>=10) {
            ab[i+1]+=ab[i]/10;
            ab[i]%=10;
        }
    }

    for (int i = 0; i < ab.size(); i++) {
        res+=to_string(ab[i])[0];
    }
    while(!res.empty() && res.back()=='0') res.pop_back();
    reverse(all(res));
    std::cout << res << std::endl;
    
    


    
    return 0;
}

int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int TET = 1;
    //cin >> TET;
    for (int i = 1; i <= TET; i++) {
        #ifdef ONPC
            cout << "TEST CASE#" << i << endl;
        #endif
        
        if (solve()) {
            break;
        }

        #ifdef ONPC
            cout << "__________________________" << endl;
        #endif
    }
    #ifdef ONPC
        cerr << endl << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl;
    #endif
}

Test details

Test 1

Verdict: ACCEPTED

input
8
5

correct output
40

user output
40

Test 2

Verdict: ACCEPTED

input
9
1

correct output
9

user output
9

Test 3

Verdict: ACCEPTED

input
9
5

correct output
45

user output
45

Test 4

Verdict: ACCEPTED

input
2
5

correct output
10

user output
10

Test 5

Verdict: ACCEPTED

input
8
7

correct output
56

user output
56

Test 6

Verdict: ACCEPTED

input
48
92

correct output
4416

user output
4416

Test 7

Verdict: ACCEPTED

input
1
40

correct output
40

user output
40

Test 8

Verdict: ACCEPTED

input
97
74

correct output
7178

user output
7178

Test 9

Verdict: ACCEPTED

input
58
8

correct output
464

user output
464

Test 10

Verdict: ACCEPTED

input
15
24

correct output
360

user output
360

Test 11

Verdict: ACCEPTED

input
4
7

correct output
28

user output
28

Test 12

Verdict: ACCEPTED

input
906
417

correct output
377802

user output
377802

Test 13

Verdict: ACCEPTED

input
778
105

correct output
81690

user output
81690

Test 14

Verdict: ACCEPTED

input
2
989

correct output
1978

user output
1978

Test 15

Verdict: ACCEPTED

input
2830
5329

correct output
15081070

user output
15081070

Test 16

Verdict: ACCEPTED

input
9
51382

correct output
462438

user output
462438

Test 17

Verdict: ACCEPTED

input
25053
71372

correct output
1788082716

user output
1788082716

Test 18

Verdict: ACCEPTED

input
258180
674616

correct output
174172358880

user output
174172358880

Test 19

Verdict: ACCEPTED

input
8821
2

correct output
17642

user output
17642

Test 20

Verdict: ACCEPTED

input
1742712
9600618

correct output
16731112196016

user output
16731112196016

Test 21

Verdict: ACCEPTED

input
8898606
2936506

correct output
26130809910636

user output
26130809910636

Test 22

Verdict: ACCEPTED

input
82670092
60138633

correct output
4971666322864236

user output
4971666322864236

Test 23

Verdict: ACCEPTED

input
54746871
83822602

correct output
4589025178578342

user output
4589025178578342

Test 24

Verdict: ACCEPTED

input
477252461
1032684

correct output
492850980435324

user output
492850980435324

Test 25

Verdict: ACCEPTED

input
5932935
379

correct output
2248582365

user output
2248582365

Test 26

Verdict: ACCEPTED

input
620114
3126641

correct output
1938873857074

user output
1938873857074

Test 27

Verdict: ACCEPTED

input
452757081
222748761

correct output
100851078826726641

user output
100851078826726641

Test 28

Verdict: ACCEPTED

input
689748332
888826746

correct output
613066765490487672

user output
613066765490487672

Test 29

Verdict: ACCEPTED

input
111337
25

correct output
2783425

user output
2783425

Test 30

Verdict: ACCEPTED

input
809
84435378

correct output
68308220802

user output
68308220802

Test 31

Verdict: ACCEPTED

input
9641697369926504411
425970950212942028697061039529...

correct output
410708299033321711216812810174...

user output
410708299033321711216812810174...

Test 32

Verdict: ACCEPTED

input
793769623129909085108356241071...

correct output
264404012608186879272715560773...

user output
264404012608186879272715560773...

Test 33

Verdict: ACCEPTED

input
8539777831492675800
436

correct output
3723343134530806648800

user output
3723343134530806648800

Test 34

Verdict: ACCEPTED

input
946492187160898604892390431179...

correct output
585982368537725512535970251461...

user output
585982368537725512535970251461...

Test 35

Verdict: ACCEPTED

input
874046401974324184707688863838...

correct output
174556202198322810668657866310...

user output
174556202198322810668657866310...

Test 36

Verdict: ACCEPTED

input
168584663428092347854539803060...

correct output
235958453587245776929148968707...

user output
235958453587245776929148968707...

Test 37

Verdict: ACCEPTED

input
279013912031336395843652482056...

correct output
856375236460411618343887929304...

user output
856375236460411618343887929304...

Test 38

Verdict: ACCEPTED

input
909594443312661242668561455177...

correct output
801297086685128929836268694647...

user output
801297086685128929836268694647...

Test 39

Verdict: ACCEPTED

input
521558480102200460144622364590...

correct output
403176935665359352292583479223...

user output
403176935665359352292583479223...

Test 40

Verdict: ACCEPTED

input
198766521920629467015839613580...

correct output
197951285207558548760833360414...

user output
197951285207558548760833360414...

Test 41

Verdict: ACCEPTED

input
388239940637354291806784217812...

correct output
354893636094929851749498258576...

user output
354893636094929851749498258576...

Test 42

Verdict: ACCEPTED

input
580031950564534684773525167998...

correct output
225288306472433597677862095876...

user output
225288306472433597677862095876...

Test 43

Verdict: ACCEPTED

input
673497493525004204568833306269...

correct output
104167516519697053781119530996...

user output
104167516519697053781119530996...

Test 44

Verdict: ACCEPTED

input
583582406474458495157747860432...

correct output
355985267949419682046226194863...

user output
355985267949419682046226194863...

Test 45

Verdict: ACCEPTED

input
154401310284121033413839709675...

correct output
472687322036571910421947159369...

user output
472687322036571910421947159369...

Test 46

Verdict: ACCEPTED

input
964784520177212016698
135881607827957154173561484162...

correct output
131096471809203739325264543904...

user output
131096471809203739325264543904...

Test 47

Verdict: ACCEPTED

input
506417941420848908877158785176...

correct output
124940484872553056181800567857...

user output
124940484872553056181800567857...

Test 48

Verdict: ACCEPTED

input
278205703909200971326699489015...

correct output
213362541886605761113025837459...

user output
213362541886605761113025837459...

Test 49

Verdict: ACCEPTED

input
488919747667763730629078434642...

correct output
244261035002054726047225565934...

user output
244261035002054726047225565934...

Test 50

Verdict: ACCEPTED

input
683013292533355268532590162229...

correct output
271255985219635665074840248062...

user output
271255985219635665074840248062...

Test 51

Verdict: ACCEPTED

input
701382950383712289025758984281...

correct output
396240397875971182850884660551...

user output
396240397875971182850884660551...

Test 52

Verdict: ACCEPTED

input
950530137216618089651057517232...

correct output
525100658977646195130452101103...

user output
525100658977646195130452101103...

Test 53

Verdict: ACCEPTED

input
758180874616256083097058082046...

correct output
612777382638418549100062437996...

user output
612777382638418549100062437996...

Test 54

Verdict: ACCEPTED

input
282198270649528096385750216226...

correct output
878945962031578099916769892430...

user output
878945962031578099916769892430...

Test 55

Verdict: ACCEPTED

input
374271236006180996628555027124...

correct output
205927043926518428842129271440...

user output
205927043926518428842129271440...

Test 56

Verdict: ACCEPTED

input
789860669365068182777748873091...

correct output
369460448033120451265094062370...

user output
369460448033120451265094062370...

Test 57

Verdict: ACCEPTED

input
826700926013863385104801713448...

correct output
291751287859134397942962144651...

user output
291751287859134397942962144651...

Test 58

Verdict: ACCEPTED

input
947468718382260248801518078140...

correct output
226868697296935607336651841496...

user output
226868697296935607336651841496...

Test 59

Verdict: ACCEPTED

input
177252461103268440789803954968...

correct output
111876380249200192763403085310...

user output
111876380249200192763403085310...

Test 60

Verdict: ACCEPTED

input
393293577943612353036749957226...

correct output
336630505716557163667422969707...

user output
336630505716557163667422969707...

Test 61

Verdict: ACCEPTED

input
320114112664152374910455416563...

correct output
136407754249269979820422504376...

user output
136407754249269979820422504376...

Test 62

Verdict: ACCEPTED

input
152757081122748761316522074282...

correct output
107712372482584798763194835348...

user output
107712372482584798763194835348...

Test 63

Verdict: ACCEPTED

input
889748332988826746683887083103...

correct output
729454517423131565738173030712...

user output
729454517423131565738173030712...

Test 64

Verdict: ACCEPTED

input
311337350148998951898280698942...

correct output
245742878826375358332482490843...

user output
245742878826375358332482490843...

Test 65

Verdict: ACCEPTED

input
709744353788876782171034561202...

correct output
198288295923437797210097622398...

user output
198288295923437797210097622398...