// #define _GLIBCXX_DEBUG // for STL debug (optional) #include #include #include #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; using ll = long long int; using int64 = long long int; template void chmax(T &a, T b) {a = max(a, b);} template void chmin(T &a, T b) {a = min(a, b);} template void chadd(T &a, T b) {a = a + b;} int dx[] = {0, 0, 1, -1}; int dy[] = {1, -1, 0, 0}; const int INF = 1LL << 29; const ll LONGINF = 1LL << 60; const ll MOD = 1000000007LL; int main() { int N, Q; scanf("%d%d", &N, &Q); vector< pair > items; for(int i=0; i rec(Q); for(int i=0; i L(N), R(N); { ll SL = 0, wsum = 0; for(int i=1; i=0; i--) { ll W, X1; tie(X1, W) = items[i+1]; ll X0 = items[i].first; wsum += W; SR += wsum * (X1 - X0); R[i] = SR; } } for(int i=0; i