#include <vector>

typedef long long ll;

using namespace std;

int MOD;
vector < ll > st, pot10;
string num;

int left(const int &x){ return (x << 1); }
int right(const int &x){ return ((x << 1) + 1); }
int padre(const int &x){ return (x >> 1); }

void calcularPot10()
{
    pot10.push_back(1 % MOD);

    for(int i = 1; i < 300010; i++)
        pot10.push_back((((pot10.back() % MOD) * (10 % MOD)) % MOD));
}

int cantDigitos(int L, int R){ return ((R - (((L + R) / 2) + 1)) + 1); }

void build(int p, int L, int R)
{
    if(L == R)
    {
        st[p] = (num[L] - '0');

        return;
    }

    build(left(p), L, ((L + R) / 2));
    build(right(p), (((L + R) / 2) + 1), R);

    ll r1 = st[left(p)], r2 = st[right(p)];

    st[p] = (((((r1 % MOD) * (pot10[cantDigitos(L, R)] % MOD)) % MOD) + (r2 % MOD)) % MOD);
}

int query(int p, int L, int R, int i, int j)
{
    if((L > j) || (R < i))
        return (-1);
    if((L >= i) && (R <= j))
        return (st[p] % MOD);

    ll r1 = query(left(p), L, ((L + R) / 2), i, j);
    ll r2 = query(right(p), (((L + R) / 2) + 1), R, i, j);

    if(r1 == (-1))
        return r2;
    if(r2 == (-1))
        return r1;

    return (((((r1 % MOD) * (pot10[(min(j, R) - (((L + R) / 2) + 1)) + 1] % MOD)) % MOD) + (r2 % MOD)) % MOD);
}

void update(int p, int L, int R, int ind, int val)
{
    if((L > ind) || (R < ind))
        return;
    if((L == ind) && (R == ind))
    {
        st[p] = val;

        return;
    }

    update(left(p), L, ((L + R) / 2), ind, val);
    update(right(p), (((L + R) / 2) + 1), R, ind, val);

    ll r1 = st[left(p)], r2 = st[right(p)];

    st[p] = (((((r1 % MOD) * (pot10[cantDigitos(L, R)] % MOD)) % MOD) + (r2 % MOD)) % MOD);
}

vector < int > dominando(string n, int d, vector < int > t, vector < int > a, vector < int > b)
{
    int Q = (int)t.size();
    int sz = (int)n.size();
    vector < int > r;
    num = (" " + n);
    MOD = d;
    calcularPot10();

    st = vector < ll >(((sz * 4) + 10), 0);

    build(1, 1, sz);

    for(int i = 0; i < Q; i++)
    {
        if(!t[i])
        {
            r.push_back(query(1, 1, sz, a[i], b[i]));
        }
        else
        {
            update(1, 1, sz, a[i], b[i]);
        }
    }

    return r;
}