#include <bits/stdc++.h>
using namespace std;
#define Yalahwy cin.tie(0), cout.tie(0), cin.sync_with_stdio(0), cout.sync_with_stdio(0);
#define ll long long
#define ld long double
#define EPS 1e-9
#define INF INT_MAX
#define pb push_back
#define pf push_front
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
#define rep(i, k, n) for(int i=k; i < n ; i++)
#define rev(i, n, k) for(int i = n; i>= k; i--)
#define yes cout << "YES" << endl;
#define no cout << "NO" << endl;
#define NIL -1
// alt + ctrl + l
// يا رب
const ll MOD = 10;
const ll N = 1e6 + 5;
const ll C = 10;
//const ll K = 5;
const ll M = 10;
//const int OO=0x3f3f3f3f;
//const ll LOO=0x3f3f3f3f3f3f3f3f;
//int dx8[] = {+0, +0, -1, +1, +1, +1, -1, -1};
//int dy8[] = {-1, +1, +0, +0, +1, -1, +1, -1};
//int dx4[] = {+0, +0, -1, +1};
//int dy4[] = {-1, +1, +0, +0};
//struct cmp {
// bool operator()(M const& p1, M const& p2)
// {
// return p1.dis > p2.dis;
// }
//};
ll p_pow[N];
ll egcd(ll a, ll b, ll &x, ll &y){ /// ax + by = gcd(a,b)
if(!b){
x=1;
y=0;
return a;
}
ll g=egcd(b,a%b,y,x);
y-=(a/b)*x;
return g;
}
ll modInverse(ll a, ll m){ /// (a/b)%m = ((a%m)*(modInverse(b)%m))%m
ll x,y,g;
g=egcd(a,m,x,y);
if(g>1)
return -1;
return (x+m)%m;
}
ll fixMod(ll a, ll p){
return (a+p)%p;
}
ll pushBack(ll h1 , ll h2, ll xp, ll p){ // xp = x^(LenToPush(h2))
return ((h1*xp)%p + h2)%p;
}
ll pushFront(ll h1, ll h2, ll xp, ll p){ // xp = x^(MainLen(h1))
return (h1 + (h2*xp)%p)%p;
}
ll popFront(ll h1, ll h2, ll xp, ll p){ // xp=x^(MainLen(h1)-LenToPop(h2))
return fixMod(h1 - (h2*xp)%p, p);
}
ll popBack(ll h1, ll h2, ll xp, ll p){ // xp=x^(LenToPop(h2))
return (fixMod(h1 - h2, p) * modInverse(xp,p))%p;
}
vector<ll> h;
ll get(ll l, ll r, vector<ll>& H, ll xp, ll p){
if(l==0) return H[r];
ll val = popFront(H[r],H[l-1],xp, p);
return val;
}
int main() {
Yalahwy
p_pow[0] = 1;
ll p = 2, q;
for (ll i = 1; i <= 1000000 ; i++)
p_pow[i] = (p_pow[i-1] * p) % MOD;
string s;
cin >> s >> q;
h.resize(s.size());
h[0] = pushBack(h[0], s[0] - '0', p, MOD);
for (int i = 1; i < s.size(); ++i) {
h[i] = pushBack(h[i - 1], s[i] - '0', p, MOD);
}
while (q--){
ll l, r;
cin >> l >> r;
l--;
r--;
cout << get(l, r, h, p_pow[r - l + 1], MOD)<< endl;
}
}
Copy