Submission #40791734

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import sys
atcoder_cpp = r"""
#define PY_SSIZE_T_CLEAN
#include <Python.h>
#include <structmember.h>
#include "modint.hpp"
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

import sys


atcoder_cpp = r"""
#define PY_SSIZE_T_CLEAN
#include <Python.h>
#include <structmember.h>



#include "modint.hpp"










namespace atcoder_python {

PyDoc_STRVAR(atcoder_doc,
"AtCoder Library for Python\n\
");










static struct PyModuleDef atcodermodule = {
    PyModuleDef_HEAD_INIT,
    "atcoder",
    atcoder_doc,
    -1,
    NULL,
    NULL,
    NULL,
    NULL,
    NULL
};




PyMODINIT_FUNC
PyInit_atcoder(void)
{
    int i;
    PyObject *m;
    const char *name;
    PyTypeObject *typelist[] = {
        &ModIntType,
        NULL
    };

    m = PyModule_Create(&atcodermodule);
    if (m == NULL)
        return NULL;

    for (i=0 ; typelist[i] != NULL ; i++) {
        if (PyType_Ready(typelist[i]) < 0)
            return NULL;
        name = _PyType_Name(typelist[i]);
        Py_INCREF(typelist[i]);
        PyModule_AddObject(m, name, (PyObject *)typelist[i]);
    }
    return m;
}

} // namespace atcoder_python
"""


modint_hpp = r"""
#ifndef ACL_PYTHON_MODINT
#define ACL_PYTHON_MODINT


#define PY_SSIZE_T_CLEAN
#include <Python.h>
#include <structmember.h>
#include <utility>


#include "internal_math.hpp"



namespace atcoder_python {


/* modint object **************************************/

/* It is the struct that treats the modular arithmetic.
reference: https://github.com/atcoder/ac-library/blob/master/atcoder/modint.hpp
           https://github.com/atcoder/ac-library/blob/master/atcoder/internal_math.hpp


    >>> ModInt.set_mod(7)
    >>> a = ModInt(12)
    >>> a
    5               # 12 == 5  (mod 7)
    >>> a += 6
    >>> a
    4               # 5 + 6 == 4  (mod 7)
    >>> a *= 3
    >>> a
    5               # 4 * 3 == 5  (mod 7)
    >>> ModInt(4).inv
    2               # 4 * 2 == 1  (mod 7)
    >>> a //= 4
    >>> a
    3               # equivalent to `a *= ModInt(4).inv`
    >>> a **= 2
    >>> a
    2               # 3 ** 2 == 2  (mod 7)


*/

extern PyTypeObject ModIntType;


#define ModInt_Check(v) PyObject_TypeCheck(v, &ModIntType)

#define CHECK_BINOP_MODINT(v, w)                           \
    do {                                                  \
        if ((!PyLong_Check(v) && !ModInt_Check(v))        \
            || (!PyLong_Check(w) && !ModInt_Check(w))){   \
            Py_RETURN_NOTIMPLEMENTED;                     \
        }                                                 \
    } while (0)

struct ModIntObject
{
    PyObject_HEAD
    unsigned int v;
    static inline unsigned int mod;
    static inline unsigned long long im;
};


static ModIntObject *
ModInt_FromUnsignedInt(unsigned int v)
{
    PyTypeObject* type = &ModIntType;
    ModIntObject* z = (ModIntObject*)type->tp_alloc(type, 0);
    if (v > ModIntObject::mod) v %= ModIntObject::mod;
    z->v = v;
    return z;
}


static unsigned int
ModInt_AsUnsignedInt(PyObject *vv)
{
    ModIntObject *v;

    if (!ModInt_Check(vv)) return -1;
    v = (ModIntObject *)vv;
    return v->v;
}


static unsigned int
UnsignedInt_FromPyObject(PyObject *o)
{
    long v;
    if (PyLong_Check(o)){
        Py_ssize_t size_o = Py_SIZE(o);
        if (size_o < 0 || size_o > 1) {
            o = PyNumber_Remainder(o, PyLong_FromUnsignedLong((unsigned long)ModIntObject::mod));
        }
        v = PyLong_AsLong(o);
    } else {
        v = (long)ModInt_AsUnsignedInt(o);
    }
    if (v >= ModIntObject::mod) v %= ModIntObject::mod;
    return (unsigned int)v;
}

static PyObject *
ModInt_to_decimal_string(PyObject *vv)
{
    ModIntObject *v;

    if (!ModInt_Check(vv)) return NULL;
    v = (ModIntObject *)vv;
    return PyUnicode_FromFormat("%u", v->v);

}


static PyObject *
ModInt_add(PyObject *a, PyObject *b)
{
    ModIntObject *z;

    CHECK_BINOP_MODINT(a, b);

    unsigned int _a, _b, result;
    _a = UnsignedInt_FromPyObject(a);
    _b = UnsignedInt_FromPyObject(b);
    result = _a + _b;
    if (result >= ModIntObject::mod) result -= ModIntObject::mod;
    z = ModInt_FromUnsignedInt(result);
    return (PyObject *)z;
}

static PyObject *
ModInt_sub(PyObject *a, PyObject *b)
{
    ModIntObject *z;

    CHECK_BINOP_MODINT(a, b);

    unsigned int _a, _b, result;
    _a = UnsignedInt_FromPyObject(a);
    _b = UnsignedInt_FromPyObject(b);
    result = _a - _b;
    if (result >= ModIntObject::mod) result += ModIntObject::mod;
    z = ModInt_FromUnsignedInt(result);
    return (PyObject *)z;
}

static unsigned int
_ModInt_mul(unsigned int a, unsigned int b)
{
    unsigned long long z = a;
    z *= b;
    unsigned long long x = (unsigned long long)(((unsigned __int128)(z)*ModIntObject::im) >> 64);
    // unsigned int result = (unsigned int)(z - x * ModIntObject::mod);
    // if (result >= ModIntObject::mod) result += ModIntObject::mod;
    unsigned long long y = x * ModIntObject::mod;
    return (unsigned int)(z - y + (z < y ? ModIntObject::mod : 0));
}

static PyObject *
ModInt_mul(PyObject *a, PyObject *b)
{
    ModIntObject *z;

    CHECK_BINOP_MODINT(a, b);

    unsigned int _a, _b;
    _a = UnsignedInt_FromPyObject(a);
    _b = UnsignedInt_FromPyObject(b);
    unsigned int result = _ModInt_mul(_a, _b);
    z = ModInt_FromUnsignedInt(result);
    return (PyObject *)z;
}

static unsigned int
ModInt_pow_fast(unsigned int a, unsigned long long n)
{
    unsigned int result = 1;
    while (n) {
        if (n & 1) result = _ModInt_mul(result, a);
        a = _ModInt_mul(a, a);
        n >>= 1;
    }
    return result;
}


static PyObject *
ModInt_pow(PyObject *v, PyObject *w, PyObject *x)
{
    ModIntObject *z;

    if (!ModInt_Check(v) || !PyLong_Check(w)) Py_RETURN_NOTIMPLEMENTED;

    int overflow;
    unsigned int result = 1;
    unsigned int a = ModInt_AsUnsignedInt(v);
    long long n = PyLong_AsLongLongAndOverflow(w, &overflow);
    if (overflow) {
        PyErr_SetString(PyExc_OverflowError, "exponent -> long long");
    }
    if (n < 0) {
        auto eg = inv_gcd(a, ModIntObject::mod);
        if (eg.first != 1){
            PyErr_Format(PyExc_ValueError, "There is no inverse element of %u in mod %u",
                        a, ModIntObject::mod);
        }
        a = (unsigned int)eg.second;
        n = -n;
    }
    result = ModInt_pow_fast(a, (unsigned long long)n);
    z = ModInt_FromUnsignedInt(result);
    return (PyObject *)z;
}

static PyObject *
ModInt_neg(PyObject *v)
{
    ModIntObject *z;
    int a = (int)ModInt_AsUnsignedInt(v);
    a = -a + ModIntObject::mod;
    z = ModInt_FromUnsignedInt((unsigned int)a);
    return (PyObject *)z;
}

static PyObject *
ModInt_pos(PyObject *v)
{
    Py_INCREF(v);
    return v;
}

static int
ModInt_bool(PyObject *v)
{
    return ModInt_AsUnsignedInt(v) != 0;
}

static PyObject *
ModInt_AsPyLong(PyObject *v)
{
    return (PyObject *)PyLong_FromUnsignedLong((unsigned long)ModInt_AsUnsignedInt(v));
}



static PyObject *
ModInt_floor_div(PyObject *a, PyObject *b)
{
    ModIntObject *z;

    CHECK_BINOP_MODINT(a, b);

    unsigned int _a, _b;
    _a = UnsignedInt_FromPyObject(a);
    _b = UnsignedInt_FromPyObject(b);
    auto eg = inv_gcd(_b, ModIntObject::mod);
    if (eg.first != 1){
        PyErr_Format(PyExc_ValueError, "There is no inverse element of %u in mod %u",
                     _b, ModIntObject::mod);
    }
    z = ModInt_FromUnsignedInt(_ModInt_mul(_a, (unsigned int)eg.second));
    return (PyObject *)z;
}




static PyNumberMethods ModInt_as_number = {
    (binaryfunc)ModInt_add,     /* nb_add */
    (binaryfunc)ModInt_sub,     /* nb_subtract */
    (binaryfunc)ModInt_mul,     /* nb_multiply */
    0,                          /* nb_remainder */
    0,                          /* nb_divmod */
    ModInt_pow,                 /* nb_power */
    ModInt_neg,                 /* nb_negative */
    ModInt_pos,                 /* tp_positive */
    0,                          /* tp_absolute */
    ModInt_bool,                /* tp_bool */
    0,                          /* nb_invert */
    0,                          /* nb_lshift */
    0,                          /* nb_rshift */
    0,                          /* nb_and */
    0,                          /* nb_xor */
    0,                          /* nb_or */
    ModInt_AsPyLong,            /* nb_int */
    0,                          /* nb_reserved */
    0,                          /* nb_float */
    0,                          /* nb_inplace_add */
    0,                          /* nb_inplace_subtract */
    0,                          /* nb_inplace_multiply */
    0,                          /* nb_inplace_remainder */
    0,                          /* nb_inplace_power */
    0,                          /* nb_inplace_lshift */
    0,                          /* nb_inplace_rshift */
    0,                          /* nb_inplace_and */
    0,                          /* nb_inplace_xor */
    0,                          /* nb_inplace_or */
    ModInt_floor_div,            /* nb_floor_divide */
    0,                          /* nb_true_divide */
    0,                          /* nb_inplace_floor_divide */
    0,                          /* nb_inplace_true_divide */
    ModInt_AsPyLong,            /* nb_index */
};


PyDoc_STRVAR(ModInt_doc,
u8"It is the struct that treats the modular arithmetic\n"
"implemented based on AtCoder Library.\n\n"
"The following operations between (ModInt/int) and (ModInt/int)\n"
"are supported:\n"
"    '+', '+=', '-', '-=', '*', '*=', '//', '//=',\n"
"    '==', '!='\n\n"
"And the following operations between (ModInt) and (int)\n"
"are supported:\n"
"    '**', '**='\n\n"
"You must first set the mod using the method ModInt.set_mod().\n\n"
"ModInt(n)  (Constructor)\n"
"    Parameters\n"
"    ----------\n"
"    n : int\n"
"    \n"
"    Returns\n"
"    -------\n"
"    x : ModInt\n"
"    \n"
"    Constraints\n"
"    -----------\n"
"    mod is already set\n"
"    \n"
"    Complexity\n"
"    ----------\n"
"    \u039F(1)\n\n"
"Operations ('+', '+=', '-', '-=', '*', '*=', '==', '!=')\n"
"    Constraints\n"
"    -----------\n"
"    Nothing\n"
"    \n"
"    Complexity\n"
"    ----------\n"
"    \u039F(1)\n\n"
"Operations ('//', '//=')\n"
"    Constraints\n"
"    -----------\n"
"    gcd(rhs, mod) = 1\n"
"    \n"
"    Complexity\n"
"    ----------\n"
"    \u039F(log(mod))\n\n"
"Operations ('**', '**=')\n"
"    If rhs is negative, lhs is replaced by inverse element of lhs\n"
"    (and rhs is replaced by -rhs).\n"
"    If you want the inverse element of lhs, use 'inv' attribute\n"
"    insted of this.\n\n"
"    Constraints\n"
"    -----------\n"
"    -2^63 <= rhs < 2^63\n"
"    \n"
"    Complexity\n"
"    ----------\n"
"    \u039F(log(rhs))\n\n"
"Attribute ('inv')\n"
"    Get the inverse element\n"
"    Note that the result is calculated each time you access.\n\n"
"    Constraints\n"
"    -----------\n"
"    gcd(self, mod) = 1\n"
"    \n"
"    Complexity\n"
"    ----------\n"
"    \u039F(log(mod))"
);


static int
ModInt_compare(unsigned int self, unsigned int other)
{
    return self == other ? 0 : 1;
}

static PyObject *
ModInt_richcompare(PyObject *self, PyObject *other, int op)
{
    int result;

    CHECK_BINOP_MODINT(self, other);

    if (!(op == Py_EQ || op == Py_NE)) Py_RETURN_NOTIMPLEMENTED;
    result = ModInt_compare(UnsignedInt_FromPyObject(self), UnsignedInt_FromPyObject(other));
    Py_RETURN_RICHCOMPARE(result, 0, op);
}




static PyObject *
ModInt_get_mod(ModIntObject *self, PyObject *args) {
    return PyLong_FromUnsignedLong((unsigned long)self->mod);
}

PyDoc_STRVAR(modint_get_mod_doc,
u8"get_mod()\n"
"--\n\n"
"Get the mod\n\n"
"Parameters\n"
"----------\n"
"Nothing\n"
"\n"
"Returns\n"
"-------\n"
"mod : int\n"
"    the mod value of ModInt\n"
"\n"
"Constraints\n"
"-----------\n"
"Nothing\n"
"\n"
"Complexity\n"
"----------\n"
"\u039F(1)"
);

#define ACL_PYTHON_MODINT_GET_MOD_METHODDEF \
    {"get_mod",                            \
     (PyCFunction)ModInt_get_mod,          \
     METH_NOARGS | METH_CLASS,             \
     modint_get_mod_doc},




static PyObject *
ModInt_set_mod(ModIntObject *self, PyObject *args) {
    unsigned int m;
    if (!PyArg_ParseTuple(args, "I", &m)) return NULL;
    ModIntObject::mod = m;
    ModIntObject::im = (unsigned long long)(-1) / m + 1;
    Py_RETURN_NONE;
}

PyDoc_STRVAR(modint_set_mod_doc,
u8"set_mod(mod)\n"
"--\n\n"
"Set the mod\n\n"
"Parameters\n"
"----------\n"
"mod : int\n"
"    the mod value\n"
"\n"
"Returns\n"
"-------\n"
"None\n"
"\n"
"Constraints\n"
"-----------\n"
"1 <= mod <= 2 * 10^9 + 1000\n"
"\n"
"Complexity\n"
"----------\n"
"\u039F(1)"
);

#define ACL_PYTHON_MODINT_SET_MOD_METHODDEF \
    {"set_mod",                            \
     (PyCFunction)ModInt_set_mod,          \
     METH_VARARGS | METH_CLASS,            \
     modint_set_mod_doc},

static PyMethodDef ModInt_methods[] = {
    ACL_PYTHON_MODINT_GET_MOD_METHODDEF
    ACL_PYTHON_MODINT_SET_MOD_METHODDEF
    {NULL} /* Sentinel */
};

// static PyMemberDef ModInt_members[] = {
//     {"v", T_UINT, offsetof(ModIntObject, v), READONLY},
//     {NULL} /* Sentinel */
// };

static PyObject *
ModInt_get_inv(PyObject *self, void *closure)
{
    ModIntObject *v;
    v = (ModIntObject *)self;
    auto eg = inv_gcd(v->v, ModIntObject::mod);
    assert(eg.first == 1);
    return (PyObject *)ModInt_FromUnsignedInt(eg.second);
}

PyDoc_STRVAR(modint_inv_doc,
u8"Get the inverse element\n\n"
"Parameters\n"
"----------\n"
"Nothing\n"
"\n"
"Returns\n"
"-------\n"
" x : int\n"
"    inverse element\n"
"\n"
"Constraints\n"
"-----------\n"
"gcd(self, mod) = 1\n"
"\n"
"Complexity\n"
"----------\n"
"\u039F(log(mod))"
);

static PyGetSetDef ModInt_getsets[] = {
    {"inv", (getter)ModInt_get_inv, NULL, modint_inv_doc, NULL},
    {NULL} /* Sentinel */
};

static int
ModInt_init(ModIntObject *self, PyObject *args, PyObject *kwargs)
{
    PyObject *o = nullptr;
    long v = 0;

    if (!PyArg_ParseTuple(args, "|O", &o)) return -1;
    if (o == nullptr) {
        v = 0;
    } else if (PyLong_Check(o)){
        if (Py_ABS(Py_SIZE(o)) > 1 || Py_SIZE(o) < 0) {
            o = PyNumber_Remainder(o, PyLong_FromUnsignedLong((unsigned long)self->mod));
        }
        v = PyLong_AsLong(o);
    } else if (ModInt_Check(o)) {
        v = (long)ModInt_AsUnsignedInt(o);
    } else {
        PyErr_SetString(PyExc_TypeError, "required: 'int' or 'ModInt'");
        return -1;
    }

    if (v >= self->mod) v %= (long)self->mod;
    if (v < 0) v += self->mod;

    self->v = v;
    return 0;
}

static PyObject *
ModInt_new(PyTypeObject *type, PyObject *args, PyObject *kwargs)
{
    ModIntObject *self;
    self = (ModIntObject *)type->tp_alloc(type, 0);
    return (PyObject *)self;
}


PyTypeObject ModIntType = {
    PyVarObject_HEAD_INIT(&PyType_Type, 0)
    "atcoder.ModInt",                           /* tp_name */
    sizeof(ModIntObject),                       /* tp_basicsize */
    0,                                          /* tp_itemsize */
    0,                                          /* tp_dealloc */
    0,                                          /* tp_vectorcall_offset */
    0,                                          /* tp_getattr */
    0,                                          /* tp_setattr */
    0,                                          /* tp_as_async */
    ModInt_to_decimal_string,                   /* tp_repr */
    &ModInt_as_number,                          /* tp_as_number */
    0,                                          /* tp_as_sequence */
    0,                                          /* tp_as_mapping */
    0,                                          /* tp_hash */
    0,                                          /* tp_call */
    0,                                          /* tp_str */
    PyObject_GenericGetAttr,                    /* tp_getattro */
    PyObject_GenericSetAttr,                    /* tp_setattro */
    0,                                          /* tp_as_buffer */
    Py_TPFLAGS_DEFAULT,                         /* tp_flags */
    ModInt_doc,                                 /* tp_doc */
    0,                                          /* tp_traverse */
    0,                                          /* tp_clear */
    ModInt_richcompare,                         /* tp_richcompare */
    0,                                          /* tp_weaklistoffset */
    0,                                          /* tp_iter */
    0,                                          /* tp_iternext */
    ModInt_methods,                             /* tp_methods */
    0,                                          /* tp_members */
    ModInt_getsets,                             /* tp_getset */
    0,                                          /* tp_base */
    0,                                          /* tp_dict */
    0,                                          /* tp_descr_get */
    0,                                          /* tp_descr_set */
    0,                                          /* tp_dictoffset */
    (initproc)ModInt_init,                      /* tp_init */
    0,                                          /* tp_alloc */
    ModInt_new,                                 /* tp_new */
    PyObject_Del,                               /* tp_free */
};




} // namespace atcoder_python


#endif  // ACL_PYTHON_MODINT
"""


internal_math_hpp = r"""
#ifndef ACL_PYTHON_INTERNAL_MATH
#define ACL_PYTHON_INTERNAL_MATH

#include <algorithm>
#include <utility>
#include <tuple>
#include <vector>


// reference: https://github.com/atcoder/ac-library/blob/master/atcoder/internal_math.hpp



namespace atcoder_python {



constexpr long long
safe_mod(long long x, long long m) {
    x %= m;
    if (x < 0) x += m;
    return x;
}


constexpr std::pair<long long, long long>
inv_gcd(long long a, long long b)
{
    a = safe_mod(a, b);
    if (a == 0) return {b, 0};
    long long s = b, t = a;
    long long m0 = 0, m1 = 1;
    while (t) {
        long long u = s / t;
        s -= t * u;
        m0 -= m1 * u;
        auto tmp = s;
        s = t;
        t = tmp;
        tmp = m0;
        m0 = m1;
        m1 = tmp;
    }
    if (m0 < 0) m0 += b / s;
    return {s, m0};
}


std::pair<long long, long long>
_crt(const std::vector<long long>& r, const std::vector<long long>& m) {
    int n = int(r.size());
    // Contracts: 0 <= r0 < m0
    long long r0 = 0, m0 = 1;
    for (int i = 0; i < n; i++) {
        long long r1 = safe_mod(r[i], m[i]), m1 = m[i];
        if (m0 < m1) {
            std::swap(r0, r1);
            std::swap(m0, m1);
        }
        if (m0 % m1 == 0) {
            if (r0 % m1 != r1) return {0, 0};
            continue;
        }
        // assume: m0 > m1, lcm(m0, m1) >= 2 * max(m0, m1)

        // (r0, m0), (r1, m1) -> (r2, m2 = lcm(m0, m1));
        // r2 % m0 = r0
        // r2 % m1 = r1
        // -> (r0 + x*m0) % m1 = r1
        // -> x*u0*g = r1-r0 (mod u1*g) (u0*g = m0, u1*g = m1)
        // -> x = (r1 - r0) / g * inv(u0) (mod u1)

        // im = inv(u0) (mod u1) (0 <= im < u1)
        long long g, im;
        std::tie(g, im) = inv_gcd(m0, m1);

        long long u1 = (m1 / g);
        // |r1 - r0| < (m0 + m1) <= lcm(m0, m1)
        if ((r1 - r0) % g) return {0, 0};

        // u1 * u1 <= m1 * m1 / g / g <= m0 * m1 / g = lcm(m0, m1)
        long long x = (r1 - r0) / g % u1 * im % u1;

        // |r0| + |m0 * x|
        // < m0 + m0 * (u1 - 1)
        // = m0 + m0 * m1 / g - m0
        // = lcm(m0, m1)
        r0 += x * m0;
        m0 *= u1;  // -> lcm(m0, m1)
        if (r0 < 0) r0 += m0;
    }
    return {r0, m0};
}


constexpr long long
pow_mod_constexpr(long long x, long long n, int m) {
    if (m == 1) return 0;
    unsigned int _m = (unsigned int)(m);
    unsigned long long r = 1;
    unsigned long long y = safe_mod(x, m);
    while (n) {
        if (n & 1) r = (r * y) % _m;
        y = (y * y) % _m;
        n >>= 1;
    }
    return r;
}

constexpr bool
is_prime_constexpr(int n) {
    if (n <= 1) return false;
    if (n == 2 || n == 7 || n == 61) return true;
    if (n % 2 == 0) return false;
    long long d = n - 1;
    while (d % 2 == 0) d /= 2;
    constexpr long long bases[3] = {2, 7, 61};
    for (long long a : bases) {
        long long t = d;
        long long y = pow_mod_constexpr(a, t, n);
        while (t != n - 1 && y != 1 && y != n - 1) {
            y = y * y % n;
            t <<= 1;
        }
        if (y != n - 1 && t % 2 == 0) {
            return false;
        }
    }
    return true;
}



unsigned long long
floor_sum_unsigned(unsigned long long n,
                   unsigned long long m,
                   unsigned long long a,
                   unsigned long long b) {
    unsigned long long ans = 0;
    while (true) {
        if (a >= m) {
            ans += n * (n - 1) / 2 * (a / m);
            a %= m;
        }
        if (b >= m) {
            ans += n * (b / m);
            b %= m;
        }

        unsigned long long y_max = a * n + b;
        if (y_max < m) break;
        // y_max < m * (n + 1)
        // floor(y_max / m) <= n
        n = (unsigned long long)(y_max / m);
        b = (unsigned long long)(y_max % m);
        std::swap(m, a);
    }
    return ans;
}


} // namespace atcoder_python


#endif  // ACL_PYTHON_INTERNAL_MATH
"""



setup_py = r"""
from setuptools import setup, Extension

sources = ['./atcoder.cpp']
extra_compile_args = ['-std=c++17', '-O2', '-mtune=native',
                      '-march=native', '-I.']
extensions = [Extension('atcoder',
                        sources=sources,
                        extra_compile_args=extra_compile_args)]

setup(name='atcoder', version='0.1', ext_modules=extensions)
"""

if sys.argv[-1] == 'ONLINE_JUDGE':
    with open('./atcoder.cpp', 'w') as f:
        f.write(atcoder_cpp)
    with open('./modint.hpp', 'w') as f:
        f.write(modint_hpp)
    with open('./internal_math.hpp', 'w') as f:
        f.write(internal_math_hpp)
    with open('./setup.py', 'w') as f:
        f.write(setup_py)
    import subprocess
    cmd = f"{sys.executable} setup.py build_ext --inplace"
    subprocess.run(cmd.split())
    exit()





from collections import deque
from atcoder import ModInt


def main():
    ModInt.set_mod(998244353)
    input = sys.stdin.readline
    Q = int(input())
    S = deque([1])
    ans = ModInt(1)
    ten = ModInt(10)
    for _ in range(Q):
        t, *q = map(int, input().split())
        if t == 1:
            x = q[0]
            S.append(x)
            ans = 10 * ans + x
        elif t == 2:
            x = S.popleft()
            ans -= x * ten ** len(S)
        else:
            print(ans)





if __name__ == '__main__':
    main()

Submission Info

Judge Result