题意：
现在有(n)堆石子，每堆石子有(a_i)个。
之后会有(m)次，每次选择([l,r])的石子堆中的石子扔(k)个，若不足，则尽量扔。
现在输出(1)~(m)次，每次最多能取到多少石子（输出第(i)次的情况时，要考虑前(i-1)次）。
给出的区间不存在包含关系。
思路：
稍微暴力点想就是一个二分图，将(k_i)拆在左边，然后石子在右边，每次最大匹配。
但这做法显然不可行，时间复杂度不能承受。
这种一般就考虑(hall)定理：假设前面都满足的情况下，如果现在新加进来一段区间，假设我们取走(k)个石子，那么就是现在要满足最大匹配，因为也不能影响前面取的，那么现在所有包含([l,r])的区间都要满足：取石子的量不超过石子个数。
这理解了这个题基本就做出来了，接下来就是维护信息。
定义(a_i:)右端点不超过(i)的所有区间的需求量；
定义(b_i:)左端点不超过(i)的所有区间的需求量；
定义(s_i:1)~(i)堆石子的个数和。
那么一段区间的需求量即为：(a_r-b_{l-1})。
将上面说的一大段话形式化就有：
对于所有的(l < r:a_r-b_{l-1}leq s_r-s_{l-1})，移项：(s_r-a_rgeq s_{l-1}-b_{l-1})。
令(f_i=s_i-a_i,g_i=s_i-b_i)。
当我们在区间([l,r])中新增需求时，会减小(f)，所以(k_i=min(k_i,f_R-g_L),Lleq l-1,Rgeq r)。
那么我们只需要维护(f)的后缀最小值和(g)的前缀最大值即可。
需求确定后，对(f_{r..n},g_{l..n})都有影响，是一个区间修改问题。
所以线段树维护一下即可。
写得可能有点乱。。总之就是理解那一大段话，知道(hall)定理怎么用的，其它也比较好出来。。
代码如下：
/*
* Author: heyuhhh
* Created Time: 2019/11/6 16:25:01
*/
#include <bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << '
'; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
#else
#define dbg(...)
#endif
void pt() {std::cout << '
'; }
template<typename T, typename...Args>
void pt(T a, Args...args) {std::cout << a << ' '; pt(args...); }
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 40005;
int n, m;
int a[N];
int f[N << 2], g[N << 2];
int lzf[N << 2], lzg[N << 2];
void push_up(int o) {
f[o] = min(f[o << 1], f[o << 1|1]);
g[o] = max(g[o << 1], g[o << 1|1]);
}
void push_down(int o) {
if(lzf[o] != 0) {
f[o << 1] += lzf[o];
f[o << 1|1] += lzf[o];
lzf[o << 1] += lzf[o];
lzf[o << 1|1] += lzf[o];
lzf[o] = 0;
}
if(lzg[o] != 0) {
g[o << 1] += lzg[o];
g[o << 1|1] += lzg[o];
lzg[o << 1] += lzg[o];
lzg[o << 1|1] += lzg[o];
lzg[o] = 0;
}
}
void build(int o, int l, int r) {
if(l == r) {
f[o] = g[o] = a[l];
return;
}
int mid = (l + r) >> 1;
build(o << 1, l, mid); build(o << 1|1, mid + 1, r);
push_up(o);
}
void updf(int o, int l, int r, int L, int R, int v) {
if(L <= l && r <= R) {
f[o] += v;
lzf[o] += v;
return;
}
push_down(o);
int mid = (l + r) >> 1;
if(L <= mid) updf(o << 1, l, mid, L, R, v);
if(R > mid) updf(o << 1|1, mid + 1, r, L, R, v);
push_up(o);
}
void updg(int o, int l, int r, int L, int R, int v) {
if(L <= l && r <= R) {
g[o] += v;
lzg[o] += v;
return;
}
push_down(o);
int mid = (l + r) >> 1;
if(L <= mid) updg(o << 1, l, mid, L, R, v);
if(R > mid) updg(o << 1|1, mid + 1, r, L, R, v);
push_up(o);
}
int queryf(int o, int l, int r, int L, int R) {
if(L <= l && r <= R) return f[o];
push_down(o);
int mid = (l + r) >> 1;
int res = INF;
if(L <= mid) res = queryf(o << 1, l, mid, L, R);
if(R > mid) res = min(res, queryf(o << 1|1, mid + 1, r, L, R));
return res;
}
int queryg(int o, int l, int r, int L, int R) {
if(L <= l && r <= R) return g[o];
push_down(o);
int mid = (l + r) >> 1;
int res = -INF;
if(L <= mid) res = queryg(o << 1, l, mid, L, R);
if(R > mid) res = max(res, queryg(o << 1|1, mid + 1, r, L, R));
return res;
}
void run(){
cin >> n;
int x, y, z, p; cin >> x >> y >> z >> p;
for(int i = 1; i <= n; i++) {
a[i] = ((i - x) * (i - x) + (i - y) * (i - y)
+ (i - z) * (i - z)) % p, a[i] += a[i - 1];
}
build(1, 0, n);
cin >> m;
cin >> a[1] >> a[2] >> x >> y >> z >> p;
for(int i = 3; i <= m; i++) a[i] = (a[i - 1] * x + a[i - 2] * y + z) % p;
for(int i = 1; i <= m; i++) {
int l, r; cin >> l >> r;
a[i] = min(a[i], queryf(1, 0, n, r, n) - queryg(1, 0, n, 0, l - 1));
updf(1, 0, n, r, n, -a[i]);
updg(1, 0, n, l, n, -a[i]);
cout << a[i] << '
';
}
}
int main() {
//freopen("../input.in", "r", stdin);
//freopen("../output.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
run();
return 0;
}