#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std; using namespace atcoder;
using ll=long long; using LL=__int128; using mint=modint998244353;
using ld = long double;
using pll=pair<ll,ll>; using tu=tuple<ll,ll,ll>; using tu4 = tuple<ll,ll,ll,ll>;using vl=vector<ll>; using vb=vector<bool>; using vvb=vector<vb>; using vvl=vector<vl>; using vs=vector<string>; using vld=vector<long double>; using vc=vector<char>; using vmi=vector<mint>; using vp = vector<pll>; using vt = vector<tu>;using graph = vvl; using Graph = vector<vp>;
template<class T=ll> auto vec2(ll n,ll m,T x=T()){return vector(n,vector<T>(m,x));} template<class T=ll> auto vec3(ll n,ll m,ll l,T x=T()){return vector(n,vector(m,vector<T>(l,x)));} 
template<class T=ll> auto vec4(ll a,ll b,ll c,ll d,T x=T()){return vector(a,vector(b,vector(c,vector<T>(d,x))));} 
template<class T> using rpq=priority_queue<T,vector<T>,greater<T>>; // 小さい順priority_queue
using inverse_priority_queue=rpq<ll>;
const ll Inf=2147483647LL, Inf9=1000000000LL, inf=9223372036854775807LL, inf18=1000000000000000000LL, mod=998244353LL;
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define Re(n) for(ll i = 0; i<(ll)(n);i++)
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define rep1(i,n) for(ll i=1;i<=(ll)(n);i++)
#define rep3(i,s,t) for(ll i=(ll)(s);i<(ll)(t);i++)
#define pb push_back
#define p(s) cout<<(s)<<'\n'
#define p2(s,t) cout<<(s)<<" "<<(t)<<'\n'
#define p3(s,t,u) cout<<(s)<<" "<<(t)<<" "<<(u)<<'\n'
#define p4(s,t,u,v) cout<<(s)<<" "<<(t)<<" "<<(u)<<" "<<(v)<<'\n'
#define pe(s) cout<<(s)<<' '
#define pval(s) cout<<(s).val()<<'\n'
#define Sort(A) sort(all(A))
#define RSort(A) sort(rall(A))
#define p_yes() p("Yes")
#define p_no() p("No")

template<class T> inline ll sz(const T& x){return (ll)x.size();} // サイズ取得
ostream& operator<<(ostream& os,const mint& x){return os<<x.val();} // mint出力
istream& operator>>(istream& is,mint& x){ll v; is>>v; x=mint(v); return is;} // mint入力
template<class T> inline bool chmin(T& a,const T& b){if(a>b){a=b; return true;} return false;} // 最小値更新
template<class T> inline bool chmax(T& a,const T& b){if(a<b){a=b; return true;} return false;} // 最大値更新
template<class T,class U> ll LB(const vector<T>& v,const U& a){return lower_bound(all(v),a)-v.begin();} // lower_boundのindex
template<class T,class U> ll UB(const vector<T>& v,const U& a){return upper_bound(all(v),a)-v.begin();} // upper_boundのindex
template<class T> T vec_min(const vector<T>& v){assert(!v.empty()); return *min_element(all(v));} // vectorの最小値
template<class T> T vec_max(const vector<T>& v){assert(!v.empty()); return *max_element(all(v));} // vectorの最大値
template<class T> T vec_sum(const vector<T>& v){T res=T(0); for(const auto& x:v) res+=x; return res;} // vectorの総和

template<class T=ll> vector<T> cin_vl(ll n){vector<T> ret(n); rep(i,n) cin>>ret[i]; return ret;} // vector入力、型省略時ll
template<class T=ll> vector<vector<T>> cin_vvl(ll h,ll w){vector<vector<T>> ret(h,vector<T>(w)); rep(i,h) rep(j,w) cin>>ret[i][j]; return ret;} // h*w入力、型省略時ll
template<class T=ll> pair<vector<T>,vector<T>> cin_xy(ll n){vector<T> x(n),y(n); rep(i,n) cin>>x[i]>>y[i]; return {x,y};} // x,y入力、型省略時ll
template<class T=ll> tuple<vector<T>,vector<T>,vector<T>> cin_xyz(ll n){vector<T> x(n),y(n),z(n); rep(i,n) cin>>x[i]>>y[i]>>z[i]; return {x,y,z};} // x,y,z入力、型省略時ll
template<class T=ll> vector<vector<T>> Cin_vl(ll n,ll k){vector<vector<T>> ret(k,vector<T>(n)); rep(i,n) rep(j,k) cin>>ret[j][i]; return ret;} // n行k列入力を列ごと保持、型省略時ll
template<class T=ll> vector<pair<T,T>> cin_pairs(ll n){vector<pair<T,T>> ret(n); rep(i,n) cin>>ret[i].first>>ret[i].second; return ret;} // pair列入力、型省略時ll
template<class T=ll> vector<tuple<T,T,T>> cin_tuples(ll n){vector<tuple<T,T,T>> ret(n); rep(i,n){T a,b,c; cin>>a>>b>>c; ret[i]={a,b,c};} return ret;} // 3要素tuple列入力、型省略時ll

template<class T> void cout_vl(const vector<T>& a,char sep=' ',char end='\n'){rep(i,sz(a)){if(i) cout<<sep; cout<<a[i];} cout<<end;} // vector出力
template<class T> void Cout_vl(const vector<T>& a,const vector<T>& b){rep(i,sz(a)) cout<<a[i]<<" "<<b[i]<<'\n';} // 2vector縦出力
template<class T> void cout_vvl(const vector<vector<T>>& a){for(const auto& e:a) cout_vl(e);} // 2次元vector出力
template<class T=ll> void Swap(vector<vector<T>>& v,ll& h,ll& w){vector<vector<T>> ret(w,vector<T>(h));rep(i,h) rep(j,w) ret[j][i]=v[i][j];v.swap(ret);swap(h,w);}//h*w行列をw*h行列に変換 hとwを自動でswap

ll ceil_div(ll a,ll b){assert(b!=0); if(b<0) a=-a,b=-b; if(a>=0) return (a+b-1)/b; return -((-a)/b);} // 切り上げ除算
ll floor_div(ll a,ll b){assert(b!=0); if(b<0) a=-a,b=-b; if(a>=0) return a/b; return -((-a+b-1)/b);} // 切り下げ除算
ll isqrt(ll n){ll x=sqrtl(n); while((LL)(x+1)*(x+1)<=n) x++; while((LL)x*x>n) x--; return x;} // floor(sqrt(n))
template<class T> vector<T> sort_unique_vec(vector<T> v){sort(all(v)); v.erase(unique(all(v)),v.end()); return v;} // sortして重複削除した新vector
template<class T> vector<ll> compress(const vector<T>& v){auto xs=sort_unique_vec(v); vector<ll> ret; for(auto& x:v) ret.pb(LB(xs,x)); return ret;} // 座標圧縮後のindex列
template<class T> vector<T> prefix_sum(const vector<T>& v){vector<T> s(sz(v)+1,0); rep(i,sz(v)) s[i+1]=s[i]+v[i]; return s;} // 1次元累積和
template<class T> vector<vector<T>> prefix_sum2(const vector<vector<T>>& a){int h=sz(a),w=sz(a[0]); vector<vector<T>> s(h+1,vector<T>(w+1,0)); rep(i,h)rep(j,w)s[i+1][j+1]=s[i+1][j]+s[i][j+1]-s[i][j]+a[i][j]; return s;} // 2次元累積和
template<class T> T range_sum(const vector<T>& s,ll l,ll r){return s[r]-s[l];} // 累積和から[l,r)の和
template<class T> vector<pair<T,ll>> run_length(const vector<T>& v){vector<pair<T,ll>> ret; for(auto& x:v){if(ret.empty()||ret.back().first!=x) ret.pb({x,1}); else ret.back().second++;} return ret;} // ランレングス圧縮
vector<pair<char,ll>> run_length(const string& s){vector<pair<char,ll>> ret; for(char c:s){if(ret.empty()||ret.back().first!=c) ret.pb({c,1}); else ret.back().second++;} return ret;} // 文字列ランレングス圧縮
template<class T> ll argmin(const vector<T>& v){assert(!v.empty()); return min_element(all(v))-v.begin();} // 最小値のindex
template<class T> ll argmax(const vector<T>& v){assert(!v.empty()); return max_element(all(v))-v.begin();} // 最大値のindex
template<class T> bool in_vec(const vector<T>& v,const T& x){return binary_search(all(v),x);} // sort済vectorに存在するか


bool even(ll x){return x%2==0;}
bool odd(ll x){return x%2!=0;}
ll grid_id(ll x,ll y,ll w){return x*w+y;}//座標からGridのID
pll grid_xy(ll id,ll w){return {id/w,id%w};}//GridのIDから座標

ll gcd(ll a,ll b){if(b==0) return abs(a); return gcd(b,a%b);} // 最大公約数
ll lcm(ll a,ll b){return a/gcd(a,b)*b;} // 最小公倍数
ll Exp(ll x,ll y){ll cnt=-1; while(x>0) x/=y,cnt++; return cnt;} // y進桁数-1
ll powmod(ll x,ll k,ll m){if(k==0) return 1%m; ll r=powmod(x,k/2,m); r=(LL)r*r%m; if(k&1) r=(LL)r*x%m; return r;} // mod累乗
template<class T> T square(T x){return x*x;} // 二乗
template<class T> void Uni_erase(vector<T>& v){sort(all(v)); v.erase(unique(all(v)),v.end());} // sortして重複削除
inline bool OutIn(ll x,ll n){return 0<=x&&x<n;}
inline bool OutIn(ll x,ll y,ll h,ll w){return 0<=x&&x<h&&0<=y&&y<w;}
inline bool OutIn(ll x,ll y,ll z,ll a,ll b,ll c){return 0<=x&&x<a&&0<=y&&y<b&&0<=z&&z<c;} // グリッド範囲内判定
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll Random(ll l,ll r){uniform_int_distribution<ll> dist(l,r-1); return dist(rng);} // [l,r)乱数
void YesNo(bool x){x?p_yes():p_no();} // Yes/No出力
vl vl_n(ll n){vl ret(n); rep(i,n) ret[i]=i; return ret;} // 0..n-1のvector生成
vl vl_N(ll n){vl ret(n); rep(i,n) ret[i]=i+1; return ret;} // 1..nのvector生成

vl dx={0,1,0,-1}, dy={1,0,-1,0};
vl dx8={1,1,0,-1,-1,-1,0,1}, dy8={0,1,1,1,0,-1,-1,-1}; // 8近傍

vector<mint> fac,finv,pow2;
void factorial(ll N=1000000LL){ll M=N+100; fac.assign(M+1,1); finv.assign(M+1,1); pow2.assign(M+1,1); rep1(i,M) fac[i]=fac[i-1]*i; finv[M]=fac[M].inv(); for(ll i=M;i>=1;i--) finv[i-1]=finv[i]*i; rep1(i,M) pow2[i]=pow2[i-1]*2;} // N+100まで階乗・逆階乗・2の累乗前計算
void ensure_factorial(ll N){if((ll)fac.size()>N) return; factorial(N);} // 階乗表の不足分確保
mint nCr(ll N,ll r){if(N<0||r<0||N<r) return 0; ensure_factorial(N); return fac[N]*finv[r]*finv[N-r];} // 二項係数
mint nPr(ll N,ll r){if(N<0||r<0||N<r) return 0; ensure_factorial(N); return fac[N]*finv[N-r];} // 順列数

//SegTree

template<class S,S(*op)(S,S),S(*e)()>
struct SegBase:segtree<S,op,e>{
    using Base=segtree<S,op,e>;
    using Base::Base;
};

namespace SegMax_impl{ll op(ll a,ll b){return max(a,b);}ll e(){return -inf;}}
namespace SegMin_impl{ll op(ll a,ll b){return min(a,b);}ll e(){return inf;}}
namespace SegSum_impl{ll op(ll a,ll b){return a+b;}ll e(){return 0;}}
namespace SegXOR_impl{ll op(ll a,ll b){return a^b;}ll e(){return 0;}}
namespace SegOR_impl{ll op(ll a,ll b){return a|b;}ll e(){return 0;}}
namespace SegAND_impl{ll op(ll a,ll b){return a&b;}ll e(){return ~0LL;}}
namespace SegGCD_impl{ll op(ll a,ll b){return gcd(a,b);}ll e(){return 0;}}

using SegMax=SegBase<ll,SegMax_impl::op,SegMax_impl::e>;
using SegMin=SegBase<ll,SegMin_impl::op,SegMin_impl::e>;
using SegSum=SegBase<ll,SegSum_impl::op,SegSum_impl::e>;
using SegXOR=SegBase<ll,SegXOR_impl::op,SegXOR_impl::e>;
using SegOR=SegBase<ll,SegOR_impl::op,SegOR_impl::e>;
using SegAND=SegBase<ll,SegAND_impl::op,SegAND_impl::e>;
using SegGCD=SegBase<ll,SegGCD_impl::op,SegGCD_impl::e>;

namespace SegMinMax_impl{
    struct S{ll mx,mn;};
    S op(S a,S b){return {max(a.mx,b.mx),min(a.mn,b.mn)};}
    S e(){return {-inf,inf};}
}
struct SegMinMax:SegBase<SegMinMax_impl::S,SegMinMax_impl::op,SegMinMax_impl::e>{
    using S=SegMinMax_impl::S;
    using Base=SegBase<S,SegMinMax_impl::op,SegMinMax_impl::e>;
    using Base::Base; using Base::set;
    static vector<S> cv(const vector<ll>&a){vector<S>v;v.reserve(a.size());for(ll x:a)v.pb({x,x});return v;}
    SegMinMax(const vector<ll>&a):Base(cv(a)){}
    void set(int i,ll x){Base::set(i,{x,x});}
};

namespace SegArgMax_impl{
    struct S{ll val,id;};
    S op(S a,S b){return a.val!=b.val?(a.val>b.val?a:b):(a.id<b.id?a:b);}
    S e(){return {-inf,inf};}
}
struct SegArgMax:SegBase<SegArgMax_impl::S,SegArgMax_impl::op,SegArgMax_impl::e>{
    using S=SegArgMax_impl::S;
    using Base=SegBase<S,SegArgMax_impl::op,SegArgMax_impl::e>;
    using Base::Base; using Base::set;
    static vector<S> cv(const vector<ll>&a){vector<S>v;rep(i,sz(a))v.pb({a[i],i});return v;}
    SegArgMax(const vector<ll>&a):Base(cv(a)){}
    void set(int i,ll x){Base::set(i,{x,i});}
};

namespace SegArgMin_impl{
    struct S{ll val,id;};
    S op(S a,S b){return a.val!=b.val?(a.val<b.val?a:b):(a.id<b.id?a:b);}
    S e(){return {inf,inf};}
}
struct SegArgMin:SegBase<SegArgMin_impl::S,SegArgMin_impl::op,SegArgMin_impl::e>{
    using S=SegArgMin_impl::S;
    using Base=SegBase<S,SegArgMin_impl::op,SegArgMin_impl::e>;
    using Base::Base; using Base::set;
    static vector<S> cv(const vector<ll>&a){vector<S>v;rep(i,sz(a))v.pb({a[i],i});return v;}
    SegArgMin(const vector<ll>&a):Base(cv(a)){}
    void set(int i,ll x){Base::set(i,{x,i});}
};

namespace SegMaxSubarray_impl{
    const ll NEG=-(1LL<<60);
    struct S{ll sum,pref,suff,best;};
    S gen(ll x){return {x,x,x,x};}
    S op(S a,S b){
        return {a.sum+b.sum,max(a.pref,a.sum+b.pref),max(b.suff,b.sum+a.suff),max({a.best,b.best,a.suff+b.pref})};
    }
    S e(){return {0,NEG,NEG,NEG};}
}
struct SegMaxSubarray:SegBase<SegMaxSubarray_impl::S,SegMaxSubarray_impl::op,SegMaxSubarray_impl::e>{
    using S=SegMaxSubarray_impl::S;
    using Base=SegBase<S,SegMaxSubarray_impl::op,SegMaxSubarray_impl::e>;
    using Base::Base; using Base::set;
    static vector<S> cv(const vector<ll>&a){vector<S>v;v.reserve(a.size());for(ll x:a)v.pb(SegMaxSubarray_impl::gen(x));return v;}
    SegMaxSubarray(const vector<ll>&a):Base(cv(a)){}
    void set(int i,ll x){Base::set(i,SegMaxSubarray_impl::gen(x));}
};

namespace SegAffine_impl{
    struct S{
        mint a,b;
        mint eval(mint x)const{return a*x+b;}
    };
    S op(S f,S g){return {g.a*f.a,g.a*f.b+g.b};}
    S e(){return {1,0};}
}
struct SegAffine:SegBase<SegAffine_impl::S,SegAffine_impl::op,SegAffine_impl::e>{
    using S=SegAffine_impl::S;
    using Base=SegBase<S,SegAffine_impl::op,SegAffine_impl::e>;
    using Base::Base;
};

namespace SegBracket_impl{
    struct S{ll sum,mn;};
    S gen(char c){return c=='('?S{1,0}:S{-1,-1};}
    S op(S a,S b){return {a.sum+b.sum,min(a.mn,a.sum+b.mn)};}
    S e(){return {0,0};}
}
struct SegBracket:SegBase<SegBracket_impl::S,SegBracket_impl::op,SegBracket_impl::e>{
    using S=SegBracket_impl::S;
    using Base=SegBase<S,SegBracket_impl::op,SegBracket_impl::e>;
    using Base::Base; using Base::set;
    static vector<S> cv(const string&s){vector<S>v;v.reserve(s.size());for(char c:s)v.pb(SegBracket_impl::gen(c));return v;}
    SegBracket(const string&s):Base(cv(s)){}
    void set(int i,char c){Base::set(i,SegBracket_impl::gen(c));}
    bool valid(int l,int r){auto x=Base::prod(l,r);return x.sum==0&&x.mn>=0;}
};



/*
SegArgMax seg(v) 区間最大値とその最左位置を管理 O(N)
pair相当 seg.prod(l,r) {最大値,その最左index}を返す O(logN)
void seg.set(i,x) A[i]=xに更新 O(logN)
SegArgMin seg(v) 区間最小値とその最左位置を管理 O(N)
pair相当 seg.prod(l,r) {最小値,その最左index}を返す O(logN)
void seg.set(i,x) A[i]=xに更新 O(logN)

SegMaxSubarray seg(v) 動的な最大部分配列和を管理、空部分列は不可 O(N)
S seg.prod(l,r) {sum,pref,suff,best}を返す O(logN)
void seg.set(i,x) A[i]=xに更新 O(logN)

SegAffine seg(v) 一次関数f(x)=ax+bの列を合成して管理 O(N)
S seg.prod(l,r) f[r-1]∘...∘f[l]を{a,b}で返す O(logN)
mint seg.prod(l,r).eval(x) 区間の合成関数をxに適用 O(logN)

SegBracket seg(s) 括弧列を構築 O(N)
S seg.prod(l,r) [l,r)の{総和,最小prefix和}を返す O(logN)
bool seg.valid(l,r) [l,r)が正しい括弧列か判定 O(logN)
void seg.set(i,c) i番目を'('または')'に更新 O(logN)

SegMinMax::S={mx,mn}
SegArgMax::S / SegArgMin::S={val,id}
SegMaxSubarray::S={sum,pref,suff,best}
SegAffine::S={a,b}
SegBracket::S={sum,mn}
区間はすべて[l,r)

void seg.set(i,x) i番目をxに更新 O(logN)
S seg.get(i) i番目の値を返す O(1)
S seg.prod(l,r) [l,r)の集約値を返す O(logN)
S seg.all_prod() 全区間の集約値を返す O(1)
int seg.max_right<f>(l) f(prod(l,r))を満たす最大rを返す O(logN)
int seg.min_left<f>(r) f(prod(l,r))を満たす最小lを返す O(logN)

SegMax seg(v) 区間最大値を管理 O(N)
SegMin seg(v) 区間最小値を管理 O(N)
SegSum seg(v) 区間和を管理 O(N)
SegXOR seg(v) 区間XORを管理 O(N)
SegOR seg(v)  区間ORを管理 O(N)
SegAND seg(v) 区間ANDを管理 O(N)
SegGCD seg(v) 区間GCDを管理 O(N)
SegMinMax seg(v) 区間最大値・最小値を同時管理 O(N)
*/
//LazySegtree

template<class S,S(*op)(S,S),S(*e)(),class F,S(*mp)(F,S),F(*cp)(F,F),F(*id)()>
struct LazySegBase:lazy_segtree<S,op,e,F,mp,cp,id>{
    using B=lazy_segtree<S,op,e,F,mp,cp,id>;
    using B::B;
};

struct LazyAssignF{ll x=0;bool set=false;};
constexpr ll LSEG_INF=(1LL<<62);


// add + min
namespace LazyAddMin_impl{
    ll op(ll a,ll b){return min(a,b);}
    ll e(){return LSEG_INF;}
    ll mp(ll f,ll x){return x+f;}
    ll cp(ll f,ll g){return f+g;}
    ll id(){return 0;}
}
struct LazyAddMin:LazySegBase<ll,LazyAddMin_impl::op,LazyAddMin_impl::e,ll,LazyAddMin_impl::mp,LazyAddMin_impl::cp,LazyAddMin_impl::id>{
    using B=LazySegBase<ll,LazyAddMin_impl::op,LazyAddMin_impl::e,ll,LazyAddMin_impl::mp,LazyAddMin_impl::cp,LazyAddMin_impl::id>;
    using B::B;
    LazyAddMin(int n):B(vector<ll>(n)){}
};


// add + max
namespace LazyAddMax_impl{
    ll op(ll a,ll b){return max(a,b);}
    ll e(){return -LSEG_INF;}
    ll mp(ll f,ll x){return x+f;}
    ll cp(ll f,ll g){return f+g;}
    ll id(){return 0;}
}
struct LazyAddMax:LazySegBase<ll,LazyAddMax_impl::op,LazyAddMax_impl::e,ll,LazyAddMax_impl::mp,LazyAddMax_impl::cp,LazyAddMax_impl::id>{
    using B=LazySegBase<ll,LazyAddMax_impl::op,LazyAddMax_impl::e,ll,LazyAddMax_impl::mp,LazyAddMax_impl::cp,LazyAddMax_impl::id>;
    using B::B;
    LazyAddMax(int n):B(vector<ll>(n)){}
};


// sum common
namespace LazySum_impl{
    struct S{ll val,size;};
    S op(S a,S b){return {a.val+b.val,a.size+b.size};}
    S e(){return {0,0};}
    vector<S> cv(const vector<ll>&a){vector<S>v;for(ll x:a)v.pb({x,1});return v;}
}


// add + sum
namespace LazyAddSum_impl{
    using S=LazySum_impl::S;
    S mp(ll f,S x){return {x.val+f*x.size,x.size};}
    ll cp(ll f,ll g){return f+g;}
    ll id(){return 0;}
}
struct LazyAddSum:LazySegBase<LazySum_impl::S,LazySum_impl::op,LazySum_impl::e,ll,LazyAddSum_impl::mp,LazyAddSum_impl::cp,LazyAddSum_impl::id>{
    using S=LazySum_impl::S;
    using B=LazySegBase<S,LazySum_impl::op,LazySum_impl::e,ll,LazyAddSum_impl::mp,LazyAddSum_impl::cp,LazyAddSum_impl::id>;
    using B::B;using B::set;
    LazyAddSum(int n):B(LazySum_impl::cv(vector<ll>(n))){}
    LazyAddSum(const vector<ll>&a):B(LazySum_impl::cv(a)){}
    void set(int i,ll x){B::set(i,{x,1});}
    ll sum(int l,int r){return B::prod(l,r).val;}
};


// assign + min
namespace LazyAssignMin_impl{
    ll op(ll a,ll b){return min(a,b);}
    ll e(){return LSEG_INF;}
    ll mp(LazyAssignF f,ll x){return f.set?f.x:x;}
    LazyAssignF cp(LazyAssignF f,LazyAssignF g){return f.set?f:g;}
    LazyAssignF id(){return {};}
}
struct LazyAssignMin:LazySegBase<ll,LazyAssignMin_impl::op,LazyAssignMin_impl::e,LazyAssignF,LazyAssignMin_impl::mp,LazyAssignMin_impl::cp,LazyAssignMin_impl::id>{
    using B=LazySegBase<ll,LazyAssignMin_impl::op,LazyAssignMin_impl::e,LazyAssignF,LazyAssignMin_impl::mp,LazyAssignMin_impl::cp,LazyAssignMin_impl::id>;
    using B::B;using B::apply;
    LazyAssignMin(int n):B(vector<ll>(n)){}
    void apply(int l,int r,ll x){B::apply(l,r,{x,true});}
};


// assign + max
namespace LazyAssignMax_impl{
    ll op(ll a,ll b){return max(a,b);}
    ll e(){return -LSEG_INF;}
    ll mp(LazyAssignF f,ll x){return f.set?f.x:x;}
    LazyAssignF cp(LazyAssignF f,LazyAssignF g){return f.set?f:g;}
    LazyAssignF id(){return {};}
}
struct LazyAssignMax:LazySegBase<ll,LazyAssignMax_impl::op,LazyAssignMax_impl::e,LazyAssignF,LazyAssignMax_impl::mp,LazyAssignMax_impl::cp,LazyAssignMax_impl::id>{
    using B=LazySegBase<ll,LazyAssignMax_impl::op,LazyAssignMax_impl::e,LazyAssignF,LazyAssignMax_impl::mp,LazyAssignMax_impl::cp,LazyAssignMax_impl::id>;
    using B::B;using B::apply;
    LazyAssignMax(int n):B(vector<ll>(n)){}
    void apply(int l,int r,ll x){B::apply(l,r,{x,true});}
};


// assign + sum
namespace LazyAssignSum_impl{
    using S=LazySum_impl::S;
    S mp(LazyAssignF f,S x){return f.set?S{f.x*x.size,x.size}:x;}
    LazyAssignF cp(LazyAssignF f,LazyAssignF g){return f.set?f:g;}
    LazyAssignF id(){return {};}
}
struct LazyAssignSum:LazySegBase<LazySum_impl::S,LazySum_impl::op,LazySum_impl::e,LazyAssignF,LazyAssignSum_impl::mp,LazyAssignSum_impl::cp,LazyAssignSum_impl::id>{
    using S=LazySum_impl::S;
    using B=LazySegBase<S,LazySum_impl::op,LazySum_impl::e,LazyAssignF,LazyAssignSum_impl::mp,LazyAssignSum_impl::cp,LazyAssignSum_impl::id>;
    using B::B;using B::apply;using B::set;
    LazyAssignSum(int n):B(LazySum_impl::cv(vector<ll>(n))){}
    LazyAssignSum(const vector<ll>&a):B(LazySum_impl::cv(a)){}
    void apply(int l,int r,ll x){B::apply(l,r,{x,true});}
    void set(int i,ll x){B::set(i,{x,1});}
    ll sum(int l,int r){return B::prod(l,r).val;}
};


// minmax common
namespace LazyMinMax_impl{
    struct S{ll mx,mn;};
    S op(S a,S b){return {max(a.mx,b.mx),min(a.mn,b.mn)};}
    S e(){return {-LSEG_INF,LSEG_INF};}
    vector<S> cv(const vector<ll>&a){vector<S>v;for(ll x:a)v.pb({x,x});return v;}
}


// add + minmax
namespace LazyAddMinMax_impl{
    using S=LazyMinMax_impl::S;
    S mp(ll f,S x){return {x.mx+f,x.mn+f};}
    ll cp(ll f,ll g){return f+g;}
    ll id(){return 0;}
}
struct LazyAddMinMax:LazySegBase<LazyMinMax_impl::S,LazyMinMax_impl::op,LazyMinMax_impl::e,ll,LazyAddMinMax_impl::mp,LazyAddMinMax_impl::cp,LazyAddMinMax_impl::id>{
    using S=LazyMinMax_impl::S;
    using B=LazySegBase<S,LazyMinMax_impl::op,LazyMinMax_impl::e,ll,LazyAddMinMax_impl::mp,LazyAddMinMax_impl::cp,LazyAddMinMax_impl::id>;
    using B::B;using B::set;
    LazyAddMinMax(int n):B(LazyMinMax_impl::cv(vector<ll>(n))){}
    LazyAddMinMax(const vector<ll>&a):B(LazyMinMax_impl::cv(a)){}
    void set(int i,ll x){B::set(i,{x,x});}
};


// assign + minmax
namespace LazyAssignMinMax_impl{
    using S=LazyMinMax_impl::S;
    S mp(LazyAssignF f,S x){return f.set?S{f.x,f.x}:x;}
    LazyAssignF cp(LazyAssignF f,LazyAssignF g){return f.set?f:g;}
    LazyAssignF id(){return {};}
}
struct LazyAssignMinMax:LazySegBase<LazyMinMax_impl::S,LazyMinMax_impl::op,LazyMinMax_impl::e,LazyAssignF,LazyAssignMinMax_impl::mp,LazyAssignMinMax_impl::cp,LazyAssignMinMax_impl::id>{
    using S=LazyMinMax_impl::S;
    using B=LazySegBase<S,LazyMinMax_impl::op,LazyMinMax_impl::e,LazyAssignF,LazyAssignMinMax_impl::mp,LazyAssignMinMax_impl::cp,LazyAssignMinMax_impl::id>;
    using B::B;using B::apply;using B::set;
    LazyAssignMinMax(const vector<ll>&a):B(LazyMinMax_impl::cv(a)){}
    void apply(int l,int r,ll x){B::apply(l,r,{x,true});}
    void set(int i,ll x){B::set(i,{x,x});}
};


// add + argmax
namespace LazyAddArgMax_impl{
    struct S{ll val,id;};
    S op(S a,S b){return a.val!=b.val?(a.val>b.val?a:b):(a.id<b.id?a:b);}
    S e(){return {-LSEG_INF,LSEG_INF};}
    S mp(ll f,S x){return x.id==LSEG_INF?x:S{x.val+f,x.id};}
    ll cp(ll f,ll g){return f+g;}
    ll id(){return 0;}
}
struct LazyAddArgMax:LazySegBase<LazyAddArgMax_impl::S,LazyAddArgMax_impl::op,LazyAddArgMax_impl::e,ll,LazyAddArgMax_impl::mp,LazyAddArgMax_impl::cp,LazyAddArgMax_impl::id>{
    using S=LazyAddArgMax_impl::S;
    using B=LazySegBase<S,LazyAddArgMax_impl::op,LazyAddArgMax_impl::e,ll,LazyAddArgMax_impl::mp,LazyAddArgMax_impl::cp,LazyAddArgMax_impl::id>;
    static vector<S> cv(const vector<ll>&a){vector<S>v;rep(i,sz(a))v.pb({a[i],i});return v;}
    LazyAddArgMax(const vector<ll>&a):B(cv(a)){}
    void set(int i,ll x){B::set(i,{x,i});}
};


// add + argmin
namespace LazyAddArgMin_impl{
    struct S{ll val,id;};
    S op(S a,S b){return a.val!=b.val?(a.val<b.val?a:b):(a.id<b.id?a:b);}
    S e(){return {LSEG_INF,LSEG_INF};}
    S mp(ll f,S x){return x.id==LSEG_INF?x:S{x.val+f,x.id};}
    ll cp(ll f,ll g){return f+g;}
    ll id(){return 0;}
}
struct LazyAddArgMin:LazySegBase<LazyAddArgMin_impl::S,LazyAddArgMin_impl::op,LazyAddArgMin_impl::e,ll,LazyAddArgMin_impl::mp,LazyAddArgMin_impl::cp,LazyAddArgMin_impl::id>{
    using S=LazyAddArgMin_impl::S;
    using B=LazySegBase<S,LazyAddArgMin_impl::op,LazyAddArgMin_impl::e,ll,LazyAddArgMin_impl::mp,LazyAddArgMin_impl::cp,LazyAddArgMin_impl::id>;
    static vector<S> cv(const vector<ll>&a){vector<S>v;rep(i,sz(a))v.pb({a[i],i});return v;}
    LazyAddArgMin(const vector<ll>&a):B(cv(a)){}
    void set(int i,ll x){B::set(i,{x,i});}
};


// chmin + max
namespace LazyChminMax_impl{
    ll op(ll a,ll b){return max(a,b);}
    ll e(){return -LSEG_INF;}
    ll mp(ll f,ll x){return min(f,x);}
    ll cp(ll f,ll g){return min(f,g);}
    ll id(){return LSEG_INF;}
}
struct LazyChminMax:LazySegBase<ll,LazyChminMax_impl::op,LazyChminMax_impl::e,ll,LazyChminMax_impl::mp,LazyChminMax_impl::cp,LazyChminMax_impl::id>{
    using B=LazySegBase<ll,LazyChminMax_impl::op,LazyChminMax_impl::e,ll,LazyChminMax_impl::mp,LazyChminMax_impl::cp,LazyChminMax_impl::id>;
    using B::B;
    LazyChminMax(int n):B(vector<ll>(n)){}
};


// chmax + min
namespace LazyChmaxMin_impl{
    ll op(ll a,ll b){return min(a,b);}
    ll e(){return LSEG_INF;}
    ll mp(ll f,ll x){return max(f,x);}
    ll cp(ll f,ll g){return max(f,g);}
    ll id(){return -LSEG_INF;}
}
struct LazyChmaxMin:LazySegBase<ll,LazyChmaxMin_impl::op,LazyChmaxMin_impl::e,ll,LazyChmaxMin_impl::mp,LazyChmaxMin_impl::cp,LazyChmaxMin_impl::id>{
    using B=LazySegBase<ll,LazyChmaxMin_impl::op,LazyChmaxMin_impl::e,ll,LazyChmaxMin_impl::mp,LazyChmaxMin_impl::cp,LazyChmaxMin_impl::id>;
    using B::B;
    LazyChmaxMin(int n):B(vector<ll>(n)){}
};


// ll affine + sum/min/max
namespace LazyAffineStats_impl{
    struct S{ll sum,mx,mn,size;};
    struct F{ll a=1,b=0;};

    S op(S x,S y){
        return {x.sum+y.sum,max(x.mx,y.mx),min(x.mn,y.mn),x.size+y.size};
    }

    S e(){return {0,-LSEG_INF,LSEG_INF,0};}

    S mp(F f,S x){
        if(!x.size)return x;
        ll sum=f.a*x.sum+f.b*x.size;
        if(f.a>=0)return {sum,f.a*x.mx+f.b,f.a*x.mn+f.b,x.size};
        return {sum,f.a*x.mn+f.b,f.a*x.mx+f.b,x.size};
    }

    F cp(F f,F g){return {f.a*g.a,f.a*g.b+f.b};}
    F id(){return {};}

    vector<S> cv(const vector<ll>&a){
        vector<S>v;
        for(ll x:a)v.pb({x,x,x,1});
        return v;
    }
}

struct LazyAffineStats:LazySegBase<LazyAffineStats_impl::S,LazyAffineStats_impl::op,LazyAffineStats_impl::e,LazyAffineStats_impl::F,LazyAffineStats_impl::mp,LazyAffineStats_impl::cp,LazyAffineStats_impl::id>{
    using S=LazyAffineStats_impl::S;
    using F=LazyAffineStats_impl::F;
    using B=LazySegBase<S,LazyAffineStats_impl::op,LazyAffineStats_impl::e,F,LazyAffineStats_impl::mp,LazyAffineStats_impl::cp,LazyAffineStats_impl::id>;

    LazyAffineStats(int n):B(LazyAffineStats_impl::cv(vector<ll>(n))){}
    LazyAffineStats(const vector<ll>&a):B(LazyAffineStats_impl::cv(a)){}

    void affine(int l,int r,ll a,ll b){B::apply(l,r,{a,b});}
    void add(int l,int r,ll x){affine(l,r,1,x);}
    void mul(int l,int r,ll x){affine(l,r,x,0);}
    void assign(int l,int r,ll x){affine(l,r,0,x);}
    void set(int i,ll x){B::set(i,{x,x,x,1});}
    ll sum(int l,int r){return B::prod(l,r).sum;}
    ll max(int l,int r){return B::prod(l,r).mx;}
    ll min(int l,int r){return B::prod(l,r).mn;}
};


// mint affine + sum
namespace LazyAffineSum_impl{
    struct S{mint val;ll size;};
    struct F{mint a=1,b=0;};

    S op(S x,S y){return {x.val+y.val,x.size+y.size};}
    S e(){return {0,0};}
    S mp(F f,S x){return {f.a*x.val+f.b*x.size,x.size};}
    F cp(F f,F g){return {f.a*g.a,f.a*g.b+f.b};}
    F id(){return {};}

    template<class T>
    vector<S> cv(const vector<T>&a){
        vector<S>v;
        for(auto x:a)v.pb({mint(x),1});
        return v;
    }
}

struct LazyAffineSum:LazySegBase<LazyAffineSum_impl::S,LazyAffineSum_impl::op,LazyAffineSum_impl::e,LazyAffineSum_impl::F,LazyAffineSum_impl::mp,LazyAffineSum_impl::cp,LazyAffineSum_impl::id>{
    using S=LazyAffineSum_impl::S;
    using F=LazyAffineSum_impl::F;
    using B=LazySegBase<S,LazyAffineSum_impl::op,LazyAffineSum_impl::e,F,LazyAffineSum_impl::mp,LazyAffineSum_impl::cp,LazyAffineSum_impl::id>;

    LazyAffineSum(int n):B(LazyAffineSum_impl::cv(vector<ll>(n))){}
    template<class T> LazyAffineSum(const vector<T>&a):B(LazyAffineSum_impl::cv(a)){}

    void affine(int l,int r,mint a,mint b){B::apply(l,r,{a,b});}
    void add(int l,int r,mint x){affine(l,r,1,x);}
    void mul(int l,int r,mint x){affine(l,r,x,0);}
    void assign(int l,int r,mint x){affine(l,r,0,x);}
    mint sum(int l,int r){return B::prod(l,r).val;}
};


// flip + ones
namespace LazyFlipSum_impl{
    struct S{ll one,size;};
    S op(S a,S b){return {a.one+b.one,a.size+b.size};}
    S e(){return {0,0};}
    S mp(bool f,S x){return f?S{x.size-x.one,x.size}:x;}
    bool cp(bool f,bool g){return f^g;}
    bool id(){return false;}
}

struct LazyFlipSum:LazySegBase<LazyFlipSum_impl::S,LazyFlipSum_impl::op,LazyFlipSum_impl::e,bool,LazyFlipSum_impl::mp,LazyFlipSum_impl::cp,LazyFlipSum_impl::id>{
    using S=LazyFlipSum_impl::S;
    using B=LazySegBase<S,LazyFlipSum_impl::op,LazyFlipSum_impl::e,bool,LazyFlipSum_impl::mp,LazyFlipSum_impl::cp,LazyFlipSum_impl::id>;

    static vector<S> cv(const vector<ll>&a){vector<S>v;for(ll x:a)v.pb({!!x,1});return v;}
    LazyFlipSum(int n):B(cv(vector<ll>(n))){}
    LazyFlipSum(const vector<ll>&a):B(cv(a)){}

    void flip(int l,int r){B::apply(l,r,true);}
    void set(int i,ll x){B::set(i,{!!x,1});}
    ll ones(int l,int r){return B::prod(l,r).one;}
};


// flip + inversion
namespace LazyFlipInv_impl{
    struct S{ll zero,one,inv;};

    S op(S a,S b){
        return {a.zero+b.zero,a.one+b.one,a.inv+b.inv+a.one*b.zero};
    }

    S e(){return {0,0,0};}

    S mp(bool f,S x){
        if(!f)return x;
        return {x.one,x.zero,x.zero*x.one-x.inv};
    }

    bool cp(bool f,bool g){return f^g;}
    bool id(){return false;}
}

struct LazyFlipInv:LazySegBase<LazyFlipInv_impl::S,LazyFlipInv_impl::op,LazyFlipInv_impl::e,bool,LazyFlipInv_impl::mp,LazyFlipInv_impl::cp,LazyFlipInv_impl::id>{
    using S=LazyFlipInv_impl::S;
    using B=LazySegBase<S,LazyFlipInv_impl::op,LazyFlipInv_impl::e,bool,LazyFlipInv_impl::mp,LazyFlipInv_impl::cp,LazyFlipInv_impl::id>;

    static vector<S> cv(const vector<ll>&a){
        vector<S>v;
        for(ll x:a)v.pb(x?S{0,1,0}:S{1,0,0});
        return v;
    }

    LazyFlipInv(int n):B(cv(vector<ll>(n))){}
    LazyFlipInv(const vector<ll>&a):B(cv(a)){}

    void flip(int l,int r){B::apply(l,r,true);}
    void set(int i,ll x){B::set(i,x?S{0,1,0}:S{1,0,0});}
    ll inversions(int l,int r){return B::prod(l,r).inv;}
};


// arithmetic progression add + sum
namespace LazyAPAddSum_impl{
    struct S{ll sum,size,idxsum;};
    struct F{ll a=0,b=0;};

    S op(S x,S y){return {x.sum+y.sum,x.size+y.size,x.idxsum+y.idxsum};}
    S e(){return {0,0,0};}
    S mp(F f,S x){return {x.sum+f.a*x.idxsum+f.b*x.size,x.size,x.idxsum};}
    F cp(F f,F g){return {f.a+g.a,f.b+g.b};}
    F id(){return {};}
}

struct LazyAPAddSum:LazySegBase<LazyAPAddSum_impl::S,LazyAPAddSum_impl::op,LazyAPAddSum_impl::e,LazyAPAddSum_impl::F,LazyAPAddSum_impl::mp,LazyAPAddSum_impl::cp,LazyAPAddSum_impl::id>{
    using S=LazyAPAddSum_impl::S;
    using F=LazyAPAddSum_impl::F;
    using B=LazySegBase<S,LazyAPAddSum_impl::op,LazyAPAddSum_impl::e,F,LazyAPAddSum_impl::mp,LazyAPAddSum_impl::cp,LazyAPAddSum_impl::id>;

    static vector<S> cv(const vector<ll>&a){
        vector<S>v;
        rep(i,sz(a))v.pb({a[i],1,i});
        return v;
    }

    LazyAPAddSum(int n):B(cv(vector<ll>(n))){}
    LazyAPAddSum(const vector<ll>&a):B(cv(a)){}

    void add_linear(int l,int r,ll a,ll b){B::apply(l,r,{a,b});}
    void add_ap(int l,int r,ll a,ll d){add_linear(l,r,d,a-d*l);}
    void set(int i,ll x){B::set(i,{x,1,i});}
    ll sum(int l,int r){return B::prod(l,r).sum;}
};
/*
LazyAddMinMax seg(v) 区間加算・区間最大最小 O(N)
LazyAssignMinMax seg(v) 区間代入・区間最大最小 O(N)
S seg.prod(l,r) {mx,mn}を返す O(logN)

LazyAddArgMax seg(v) 区間加算・区間最大値と最左位置 O(N)
LazyAddArgMin seg(v) 区間加算・区間最小値と最左位置 O(N)
S seg.prod(l,r) {val,id}を返す O(logN)

LazyChminMax seg(v) 区間chmin(A[i]=min(A[i],x))・区間最大 O(N)
LazyChmaxMin seg(v) 区間chmax(A[i]=max(A[i],x))・区間最小 O(N)

LazyAffineStats seg(v) 区間Affine変換・区間和最大最小 O(N)
void seg.affine(l,r,a,b) [l,r)をA[i]=a*A[i]+bに変更 O(logN)
void seg.add(l,r,x) [l,r)にx加算 O(logN)
void seg.mul(l,r,x) [l,r)をx倍 O(logN)
void seg.assign(l,r,x) [l,r)をxに代入 O(logN)
S seg.prod(l,r) {sum,mx,mn,size}を返す O(logN)

LazyAffineSum seg(v) mint列の区間Affine変換・区間和 O(N)
void seg.affine(l,r,a,b) [l,r)をA[i]=a*A[i]+bに変更 O(logN)
void seg.add(l,r,x) [l,r)にx加算 O(logN)
void seg.mul(l,r,x) [l,r)をx倍 O(logN)
void seg.assign(l,r,x) [l,r)をxに代入 O(logN)
mint seg.sum(l,r) [l,r)の和を返す O(logN)

LazyFlipSum seg(v) 01列の区間反転・区間1個数 O(N)
void seg.flip(l,r) [l,r)の0/1を反転 O(logN)
ll seg.ones(l,r) [l,r)の1の個数を返す O(logN)

LazyFlipInv seg(v) 01列の区間反転・転倒数 O(N)
void seg.flip(l,r) [l,r)の0/1を反転 O(logN)
ll seg.inversions(l,r) [l,r)の転倒数(1,0)の組数を返す O(logN)

LazyAPAddSum seg(v) 等差数列加算・区間和 O(N)
void seg.add_ap(l,r,a,d) A[l+i]+=a+d*i を行う O(logN)
void seg.add_linear(l,r,a,b) A[i]+=a*i+b を行う O(logN)
ll seg.sum(l,r) [l,r)の和を返す O(logN)

void seg.apply(l,r,f) [l,r)に写像fを作用 O(logN)
void seg.set(i,x) i番目を変更 O(logN)
S seg.get(i) i番目を返す O(logN)
S seg.prod(l,r) [l,r)の集約値を返す O(logN)
S seg.all_prod() 全体の集約値を返す O(1)
int seg.max_right<f>(l) 条件を満たす最大rを返す O(logN)
int seg.min_left<f>(r) 条件を満たす最小lを返す O(logN)

LazyAddMin seg(v) 区間加算・区間最小 O(N)
LazyAddMax seg(v) 区間加算・区間最大 O(N)
LazyAddSum seg(v) 区間加算・区間和 O(N)
LazyAssignMin seg(v) 区間代入・区間最小 O(N)
LazyAssignMax seg(v) 区間代入・区間最大 O(N)
LazyAssignSum seg(v) 区間代入・区間和 O(N)

*/

signed main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    

    //inplaceに見える
    ll n, b, c;
    cin >> n >> b >> c;
    auto a = cin_vl(n);

    //inplace2本かおもろい
    vl v1(2*n+10,-Inf*n), v2(2*n+10,-Inf*n);
    v1[n] = 0, v2[n-1] = 0;


    LazyAddMax seg1(v1), seg2(v2);

    rep(i,n){
        if(i != 0)seg2.set(n-(i+1),seg1.prod(n-i+1,n-i+c));
        seg1.apply(n-i,n-i+c-1,a[i]);
        seg1.set(n-(i+1),seg2.prod(n-(i+1),n-(i+1)+(b-1)));
        /*
        rep(i,2*n) cout << max(-1LL,seg1.get(i)) << ' ';
        cout << endl;
        rep(i,2*n) cout << max(-1LL,seg2.get(i)) << ' ';
        cout << endl;
        */
        
    }

    p(seg1.prod(0,c));

}//手動セグ木をやります