// Those who cannot remember the past are
// condemned to repeat it (use DP -_-)
// - George Santayana
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define ll long long
#define ull unsigned long long
#define MOD 1000000007
#define PI 3.14159265
#define ceil(a, b) (((a) / (b)) + ((a) % (b) ? 1 : 0))
#define imin INT_MIN
#define imax INT_MAX
#define llmax LLONG_MAX
#define llmin LLONG_MIN
#define inf 2000000000
#define nl '\n'
#define ppcnt __builtin_popcount
#define ppcntll __builtin_popcountll
#define clz __builtin_clz
#define clzll __builtin_clzll
#define ctz __builtin_ctz
#define ctzll __builtin_ctzll
#define modulo(a, b, mod) ((((a) % (mod)) * ((b) % (mod))) % (mod))
#define cnte(v, x) count(all(v), (x))
#define mine(v) min_element(all(v))
#define maxe(v) max_element(all(v))
#define updmin(a, b) a = min(a, b)
#define updmax(a, b) a = max(a, b)
#define findmod(x, m) x = ((x) % (m) + (m)) % m
#define getmod(x, m) ((x) % (m) + (m)) % (m)
#define debug(x) cout << "x: " << (x) << nl;
#define debug2(x, y) cout << "x: " << (x) << " y: " << y << nl;
#define ordered_set tree<ll, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_map tree<int, int, less<>, rb_tree_tag, tree_order_statistics_node_update>
//vector<int> dx = {0, 0, 1, -1, 1, 1, -1, -1}, dy = {1, -1, 0, 0, 1, -1, 1, -1};
//vector<int> dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
template<typename T = int> istream& operator>>(istream& in, vector<pair<int, int>>& v){
for (auto& [x, y] : v) in >> x >> y;
return in;
}
template<typename T = int> istream& operator>>(istream& in, vector<T>& v){
for (T& i : v) in >> i;
return in;
}
template<typename T = int> ostream& operator<<(ostream& out, const vector<T>& v){
for (const T& x : v)
out << x << ' ';
return out;
}
template<typename T = pair<int, int>> ostream& operator << (ostream& out, const vector<pair<int, int>>& v){
for(auto& [x, y] : v){
out << x << ' ' << y << nl;
}
return out;
}
void Start_Crushing() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
}
ll BinExp(ll b, ll e, ll mod = 10){
ll res = 1;
while(e){
if(e & 1)
res = modulo(res, b, mod);
b = modulo(b, b, mod);
e >>= 1;
}
return res;
}
struct segmentTree{
struct node{
ll value, length;
node(){
value = length = 0;
}
node(ll value, ll length){
this -> value = value;
this -> length = length;
}
};
vector<node> tree;
int size, n;
segmentTree(int n){
this -> n = n;
size = 1;
}
node merge(node& a, node& b){
ll value = a.value * BinExp(2ll, b.length) % 10;
return {(value + b.value) % 10, a.length + b.length};
}
void build(string& s, int idx, int tl, int tr){
if(tl >= n) return;
if(tl == tr){
tree[idx] = node(s[tl] - '0', 1);
return;
}
int mid = tl - (tl - tr) / 2;
build(s, idx * 2 + 1, tl, mid);
build(s, idx * 2 + 2, mid + 1, tr);
tree[idx] = merge(tree[idx * 2 + 1], tree[idx * 2 + 2]);
}
void build(string& s){
for(size = 1; size < n; size *= 2);
tree.assign(size * 2, node());
build(s, 0, 0, size - 1);
}
node query(int l, int r, int idx, int tl, int tr){
if(tr < l or tl > r) return {0, 0};
if(tl >= l and tr <= r){
return tree[idx];
}
int mid = tl - (tl - tr) / 2;
node left = query(l, r, idx * 2 + 1, tl, mid);
node right = query(l, r, idx * 2 + 2, mid + 1, tr);
return merge(left, right);
}
node query(int l, int r){
return query(l, r, 0, 0, size - 1);
}
};
void solve(){
string s; cin >> s;
segmentTree st((int)s.size());
st.build(s);
int q; cin >> q;
while(q--){
int l, r; cin >> l >> r;
cout << st.query(--l, --r).value << nl;
}
}
int main(){
Start_Crushing();
int t = 1;
// /*Multiple test cases?*/ cin >> t;
while (t--) {
solve();
if(!t)
break;
cout << nl;
}
// for(int tc = 1; tc <= t; tc++){
// cout << "Case #" << tc << ": ";
// solve();
// if(tc != t)
// cout << nl;
// }
return 0;
}
Copy