#define _USE_MATH_DEFINES #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; class RangeMinimumQuery { private: int n; vector data; int query(int a, int b, int k, int l, int r){ if(r < a || b < l) return INT_MAX; if(a <= l && r <= b) return data[k]; int x = query(a, b, k*2+1, l, (l+r)/2); int y = query(a, b, k*2+2, (l+r+1)/2, r); return min(x, y); } public: RangeMinimumQuery(int n0){ // コンストラクタ(要素数を指定) n = 1; while(n < n0) n *= 2; data.assign(2*n-1, INT_MAX); } RangeMinimumQuery(vector vi){ // コンストラクタ(配列を指定) int n0 = vi.size(); n = 1; while(n < n0) n *= 2; data.assign(2*n-1, INT_MAX); for(int i=0; i=0; --i) data[i] = min(data[i*2+1], data[i*2+2]); } void update(int k, int x){ // k番目の要素をxに変更する k += n - 1; data[k] = x; while(k > 0){ k = (k - 1) / 2; data[k] = min(data[k*2+1], data[k*2+2]); } } int query(int a, int b){ // 区間[a,b]の最小値を返す return query(a, b, 0, 0, n-1); } }; int main() { int n; cin >> n; vector > v(n); for(int i=0; i> v[i].first; v[i].second = i; } sort(v.begin(), v.end()); vector index(n); for(int i=0; i len(n-1, 0); for(int i=0; i> m >> x >> d; vector a(m), b(m); for(int i=0; i b[i]) swap(a[i], b[i]); else ++ b[i]; x = (x + d) % (n * (n - 1LL)); } long long ans = 0; for(int i=0; i b2) swap(a2, b2); ans += rmq.query(a2, b2 - 1); } cout << ans << endl; return 0; }