#pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include //#include using namespace std; //using namespace atcoder; #define ll long long int constexpr double time_limit = 4.8; struct Input { int n, q, wt, st; vector w; vector> lr; void input() { cin >> n >> q >> wt >> st; w.resize(n); for (int i = 0; i < n; ++i) { cin >> w[i]; } lr.resize(q); for (int i = 0; i < q; ++i) { cin >> lr[i].first >> lr[i].second; } } }; struct Solver { int n, q, wt, st; vector w; vector> lr; vector cs; // cumulative sum of w vector p; Solver(const Input& input) { n = input.n; q = input.q; wt = input.wt; st = input.st; w = input.w; lr = input.lr; // initialize cs cs.resize(n + 1, 0); for (int i = 0; i < n; ++i) { cs[i + 1] = cs[i] + w[i]; } } void mo() { int sqrt_n = (int)sqrt(n) + 1; vector>> groups(sqrt_n + 1); for (int i = 0; i < q; ++i) { auto [l, r] = lr[i]; groups[sqrt_n * cs[l] / cs.back()].push_back({r, l, i}); } p.clear(); p.reserve(q); bool flag = false; for (vector>& group : groups) { if (group.empty()) { continue; } sort(group.begin(), group.end()); if (flag) { reverse(group.begin(), group.end()); } for (auto [r, l, i] : group) { p.push_back(i); } flag ^= true; } } void print() { for (int i = 0; i < q; ++i) { cout << p[i]; if (i == q - 1) { cout << "\n"; } else { cout << " "; } } } }; int main() { Input input; input.input(); Solver solver(input); solver.mo(); solver.print(); return 0; }