#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
const int MAX = 2e5;
vector<int> pw2 = [](){
vector<int> ret;
ret.push_back(1);
for (int i = 1; i <= MAX; ++i) {
ret.push_back(ret.back() * 2 % 10);
}
return ret;
}();
class SegmentTree {
private:
vector<int> tree;
vector<int> leaves;
int n;
inline void pull(int p, int s, int e) {
int mid = (s + e) / 2;
tree[p] = (tree[2 * p] * pw2[e - mid] + tree[2 * p + 1]) % 10;
}
void build(int p, int s, int e) {
if (s == e) {
tree[p] = leaves[s];
return;
}
int mid = (s + e) / 2;
build(2 * p, s, mid);
build(2 * p + 1, mid + 1, e);
pull(p, s, e);
}
int query(int p, int s, int e, int l, int r) {
if (s > r || e < l) {
return 0;
}
if (l <= s && e <= r) {
return (tree[p] * pw2[r - e]) % 10;
}
int mid = (s + e) / 2;
return (query(2 * p, s, mid, l, r) + query(2 * p + 1, mid + 1, e, l, r)) % 10;
}
public:
SegmentTree(const string &s) {
n = s.size();
for (char c : s) {
leaves.push_back(c - '0');
}
tree.resize(4 * n);
build(1, 0, n - 1);
}
int query(int l, int r) {
return query(1, 0, n - 1, l, r);
}
};
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
string s;
cin >> s;
SegmentTree seg(s);
int q;
cin >> q;
while (q--) {
int l, r;
cin >> l >> r;
--l;
--r;
int ans = seg.query(l, r);
cout << ans << '\n';
}
return 0;
}
Copy