cgiosy

const replaceSetMap = (object) => {
  if (object) {
    if (object.constructor === Set) return [...object];
    if (object.constructor === Map) return Object.fromEntries(object);
  }
  return object;
};

const decycle = (rootObject, { replacer = replaceSetMap, seen = new WeakMap() } = {}) => {
  const _decycle = (object, path = "$") => {

cgiosy

#define private public
#include <bitset>
#undef private

#include <bits/stdc++.h>
#include <x86intrin.h>
using namespace std;

template<size_t _Nw> void _M_do_sub(_Base_bitset<_Nw> &A, const _Base_bitset<_Nw> &B) {
	for(int i=0, c=0; i<_Nw; i++)

cgiosy

auto m=partition(A.begin(), A.end(), [&](pii p) { return p<pii{}; });
sort(A.begin(), m, [&](pii a, pii b) { return cross(a, b)<0; });
sort(m, A.end(), [&](pii a, pii b) { return cross(a, b)<0; });

cgiosy

#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
#define R(i,n) for(int i=0; i<n; i++)
using namespace std;
int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	int N, Q;
	cin>>N>>Q;
	alignas(32) long X[2048];

cgiosy

namespace io {
	const signed IS=1<<22;
	char I[IS+1],*J=I;

	inline void daer(){char*p=I;while(*J)*p++=*J++;p[fread(p,1,I+IS-p,stdin)]=0;J=I;}
	template<int N=10,typename T=int>inline T getu(){if(J>=I+IS-64)daer();T x=0;int k=0;do x=x*10+(*J-'0');while(*++J>='0'&&++k<N);++J;return x;}
	struct f{f(){I[fread(I,1,IS,stdin)]=0;}}flu;
};
using namespace io;

cgiosy

template<class T=int, class O=less<T>>
struct heap_set {
	priority_queue<T, vector<T>, O> q, del;
	const T& top() const { return q.top(); }
	int size() const { return int(q.size()-del.size()); }
	bool empty() const { return !size(); }
	void flush() { while(del.size() && q.top()==del.top()) q.pop(), del.pop(); }
	void insert(const T x) { q.push(x); flush(); }
	void pop() { q.pop(); flush(); }
	void erase(const T x) { del.push(x); flush(); }

cgiosy

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
constexpr int MXN=1e5;

int A[MXN], B[MXN], N;
ll D[MXN];
ll f(int j, int i) { return D[j] + 1LL*A[i]*B[j]; }
bool cmp(int i, int j, int x) { return f(i, x)<f(j, x); }

cgiosy

// int rank[N]; vector<int> G[N];
auto rank_tree(int i, int p=-1) {
	int x=0, y=0;
	for(int j:G[i]) if(j!=p) {
		auto z=rank_tree(j, i);
		y|=x&z, x|=z;
	}
	x=(x|(1<<31-__builtin_clz(y<<1|1))-1)+1;
	rank[i]=__builtin_ctz(x);
	return x;

cgiosy

// LEETCODE
#include <bits/stdc++.h>

namespace leetcode {
	#define __COUT_DEFAULT_DELIMITER__ ","
	// #define __PARSE_INT128__
	// #define __PARSE_CHAR_QUOTE__ '\'
	// #define __PARSE_STRING_DELIMITER__ " ,]})"

cgiosy

#include <bits/stdc++.h>
using namespace std;

int N, Q, t, l, r; long x;
struct node {
	long a, b, m, n;
	void input() { cin>>a; m=n=a; }
	node operator+(node& R) {
		return {a+R.a, 0, max(m, R.m), min(n, R.n)};
	}