#define _CRT_SECURE_NO_WARNINGS
//#pragma GCC optimize(3, "Ofast", "inline")
#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
#include<array>
#include<random>
using namespace std;
#define for1 for(int i = 1;i <= n;i++)
#define for0 for(int i = 0;i < n;i++) 
#define forj1 for(int j = 1;j <= n;j++) 
#define forj0 for(int j = 0;j < n;j++) 
#define form1 for (int j = 1; j <= m; j++)
#define form0 for (int j = 0; j < m; j++)
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define arrn int* arr = new int[n+2];arr[0] = 0,arr[n+1]=0
#define brrn int* brr = new int[n+2];brr[0] = 0,brr[n+1]=0
#define carr for1 cin >> arr[i]
#define carrn arrn;carr 
#define coarr for1 cout<<arr[i]<<" ";cout<<endl
#define yes  cout<<"Yes\n"
#define no cout<<"No\n"
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define endl '\n'
#define blank ' '
#define cn int n;cin>>n
#define cnm int n,m;cin>>n>>m
#define T() int _; cin >> _; while (_--)
#define int  long long
#define  ll long long
#define pii pair<int,int>
const int mode = 998244353;
const int mod = 1e9 + 7;
mt19937_64 rnd(time(0));
typedef uint64_t hash_t;
//chrono::high_resolution_clock::now().time_since_epoch().count()
int ksm(int a, int b = mode - 2)
{
    a %= mode;
    int ans = 1;
    while (b)
    {
        if (b % 2 == 1)
        {
            ans = ans * a % mode; b--;
        }
        a = a * a % mode;
        b >>= 1;
    }
    return ans;
}
int gcd(int a, int b)
{
    if (b == 0)return a;
    return gcd(b, a % b);
}
long long lcm(long long a, long long b)
{
    return (a * b) / gcd(a, b);
}
//const int mod = 1000002361;
bool ccmp(string x, string y)
{
    return x.size() > y.size();
}
long long qpow(int a, int b)
{
    a% mod;
    if (b == 0)return 1ll;
    int ret = 1ll;
    while (b)
    {
        if (b % 2)ret = (ret * a) % mod;
        b >>= 1;
        a = (a * a) % mod;
    }
    return ret % mod;
}

int one(int n)//计算二进制下1的个数
{
    if (n == 0)return 0;
    if (n == 1)return 1;
    int ret = 0;
    for (int i = 0; i < 63; i++)
    {
        int w = n / (1ll << (i + 1));
        ret = (ret + (w * (1ll << i))) % mode;
        int yu = n % (1ll << (i + 1));
        if (yu >= 1ll << i)
        {
            ret = (ret + (yu - (1ll << i) + 1)) % mode;
        }
    }

    return ret % mode;
}
bool isspire(int n)
{
    if (n <= 1)return false;
    if (n == 2)return true;
    for (int i = 2; i <= sqrt(n); i++)
    {
        if (n % i == 0)return false;
    }
    return true;
}
int n;/*, q;
int arr[200001];
int v[500001];
int tree[500001];
int tree2[500001];
int wwr[200001][2];
int cnt = 0;
map<int, int>mp;
int lowbit(int i)
{
    return(i & -i);
}
void build()
{
    for1
    {
        if (arr[i] > 0)
        {
            int j = mp[arr[i]];
            while (j <= cnt)
            {
                tree[j] += arr[i];
                tree2[j] += 1;
                j += lowbit(j);
            }
        }
    }
}
void _add(int v,int i)
{
    while (i <= cnt)
    {
        tree[i] += v;
        if (v > 0)tree2[i] += 1;
        else tree2[i] -= 1;
        i += lowbit(i);
    }
}
int que(int i)
{
    int ans = 0;
    while (i)
    {
        ans += tree[i];
        i -= lowbit(i);
    }
    return ans;
}
int que1(int i)
{
    int ans = 0;
    while (i)
    {
        ans += tree2[i];
        i -= lowbit(i);
    }
    return ans;
}*/
//signed main()
//{
//    IOS;
//    // precalc();
//    //int mod = 1e13;
//    cin >> n >> q;
//    carr;
//    int sum = 0;
//    int plus = 0;
//    for1 if(arr[i]>0)mp[arr[i]]++,plus++;
//    for (int i = 1; i <= q; i++)
//    {
//        cin >> wwr[i][0] >> wwr[i][1];
//        if(wwr[i][1]>0)
//        mp[wwr[i][1]]++;
//    }
//    for (auto z : mp)
//    {
//        mp[z.first] = ++cnt;
//        v[cnt] = z.first;
//    }
//    build();
//    for (int i = 1; i <= q; i++)
//    {
//        int nn = 0;
//        int w = wwr[i][0];
//        if (wwr[i][1] <= 0)
//        {
//            if (arr[w] > 0)
//            {
//                sum += wwr[i][1];
//                plus--;
//                int j = mp[arr[w]];
//                _add(-arr[w], j);
//                arr[w] = wwr[i][1];
//            }
//            else
//            {
//                int cha = arr[w] - wwr[i][1];
//                sum -= cha;
//                arr[w] = wwr[i][1];
//            }
//        }
//        else
//        {
//            if (arr[w] > 0)
//            {
//                int k = mp[arr[w]];
//                int j = mp[wwr[i][1]];
//                _add(-arr[w], k);
//                _add(wwr[i][1], j);
//                arr[w] = wwr[i][1];
//            }
//            else
//            {
//                plus++;
//                sum -= arr[w];
//                //arr[i] = wwr[i][1];
//                int j = mp[wwr[i][1]];
//                _add(wwr[i][1], j);
//                arr[w] = wwr[i][1];
//            }
//        }
//        int l = 0, r = cnt;
//        while (l <= r)
//        {
//            int mid = (l + r) >> 1;
//            if (que(mid) + sum >= 0)r = mid - 1;
//            else l = mid + 1;
//        }
//        int now = que1(l)+1;
//        cout << now << endl;
//    }
//}
int  k, m, a1, d;
int a[400001];
int mp1[800001];
int mp2[800001];
signed main()
{

    cin >> n >> k >> m >> a1 >> d;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    if(d!=0)
    {
    int l = 0, r = 1e18;
    auto cheak = [&](int x)
    {
        for1 mp1[i] = 0, mp2[i] = 0;
        for (int i = 1; i <= m; i++)
        {
            if (a[i] >= x)mp1[1ll]++;
            else
            {
                if (a[i] + a1 + d * (i - 1ll) < x)
                {
                    ;
                }
                else
                {
                    mp1[1ll]++;
                    int zhi = a[i] + a1 + d * (i - 1ll) - x;
                    int miao = zhi / d + 1ll;
                    mp2[1ll + miao]++;
                }
            }
        }
        for (int i = m + 1; i <= n; ++i)
        {
            if (a[i] >= x)mp1[1ll]++;
            else
            {
                if (a[i] + a1 + d * (m - 1) < x)
                {
                    ;
                }
                else
                {
                    int sk = i - m + 1ll;
                    mp1[sk]++;
                    int zhi = a[i] + a1 + d * (m - 1ll) - x;
                    int miao = zhi / d + 1ll;
                    mp2[sk + miao]++;
                }
            }
        }
        int now = 0;
        int ans = 0;
        for (int i = 1; i <= n; i++)
        {
            now += mp1[i];
            now -= mp2[i];
            ans = max(ans, now);
        }
        return ans >= k;




    };
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (cheak(mid))l = mid + 1;
        else r = mid - 1;
    }
    cout << r << endl;
}
    else
    {
       
        sort(a + 1ll, a + 1ll + n);
        a[n - k + 1ll] += a1;
        sort(a + 1ll, a + 1ll + n);
        cout << a[n - k + 1ll] << endl;
    }
}
//int arr[1000001];
//int sm[4000004];
//int mx[4000004];
//int mxcnt[4000004];
//int semx[4000004];
////int semxcnt[400004];
//int ad1[4000004];
//int ad2[4000004];
//int ad3[4000004];
//int ad4[4000004];
//int hismx[4000004];
//void up(int i)
//{
//    int z = i << 1;
//    int y = i << 1 | 1;
//    sm[i] = sm[z] + sm[y];
//    hismx[i] = max({hismx[z], hismx[y]});
//    if (mx[z] > mx[y])
//    {
//        mx[i] = mx[z];
//        mxcnt[i] = mxcnt[z];
//        semx[i] = max(mx[y], semx[z]);
//    }
//    else if (mx[z] < mx[y])
//    {
//        mx[i] = mx[y];
//        mxcnt[i] = mxcnt[y];
//        semx[i] = max(mx[z], semx[y]);
//    }
//    else
//    {
//        mx[i] = mx[z];
//        mxcnt[i] = mxcnt[z] + mxcnt[y];
//        semx[i] = max(semx[z], semx[y]);
//    }
//}
//void build(int l, int r, int i)
//{
//    if (l == r)
//    {
//        sm[i] = arr[l];
//        mx[i] = arr[l];
//        mxcnt[i] = 1;
//        semx[i] = -1e18;
//       // semxcnt[i] = 1;
//        ad1[i] = 0;
//        ad2[i] = 0;
//        ad3[i] = 0;
//        ad4[i] = 0;
//        hismx[i] = arr[l];
//        return;
//    }
//    int mid = (l + r) >> 1;
//    build(l, mid, i << 1);
//    build(mid + 1, r, i << 1 | 1);
//    up(i);
//    ad1[i] = 0;
//    ad2[i] = 0;
//    ad3[i] = 0;
//    ad4[i] = 0;
//}
//
//void lazy(int i, int n,int v1,int v2,int v3,int v4)
//{   
//    hismx[i] = max({ mx[i] + v3, hismx[i]});
//    ad3[i] = max(ad1[i]+v3,ad3[i]);
//    ad4[i] = max(ad2[i] + v4, ad4[i]);
//    sm[i] += v1 * mxcnt[i];
//    sm[i] += v2 * (n-mxcnt[i]);
//    mx[i] += v1;
//    semx[i] += (semx[i] == -1e18) ? 0 : v2;
//    ad1[i] += v1;
//    ad2[i] += v2;
//}
//void down(int i, int z, int y)
//{
//    int l = i << 1;
//    int r = i << 1 | 1;
//    int t = max(mx[l], mx[r]);
//    if(mx[l]>=mx[r])
//    lazy(l, z, ad1[i], ad2[i],ad3[i],ad4[i]);
//    else
//        lazy(l, z, ad2[i], ad2[i],ad4[i],ad4[i]);
//    if (mx[r]==t)
//    lazy(r, y, ad1[i], ad2[i],ad3[i],ad4[i]);
//    else
//        lazy(r, y, ad2[i], ad2[i],ad4[i],ad4[i]);
//    ad1[i] = 0;
//    ad2[i] = 0;
//    ad3[i] = 0;
//    ad4[i] = 0;
//}
//
//array<int, 3> que(int jl, int jr, int l, int r, int i)
//{
//    if (jl <= l && r <= jr)
//    {
//        return { sm[i],mx[i],hismx[i] };
//    }
//    int mid = (l + r) >> 1;
//    down(i, mid - l + 1, r - mid);
//    array<int, 3>ans = { 0,(int)-1e18,(int)-1e18 };
//    if (jl <= mid)
//    {
//        array<int, 3>a = que(jl, jr, l, mid, i << 1);
//        ans[0] += a[0];
//        ans[1] = max(ans[1], a[1]);
//        ans[2] = max(ans[2], a[2]);
//    }
//    if (mid + 1 <= jr)
//    {
//        array<int, 3>a = que(jl, jr, mid + 1, r, i << 1 | 1);
//        ans[0] += a[0];
//        ans[1] = max(ans[1], a[1]);
//        ans[2] = max(ans[2], a[2]);
//    }
//    
//    return ans;
//
//}
//void update(int jl, int jr, int jv, int l, int r, int i)
//{
//    if (jv >= mx[i])return;
//    if (l >= jl && r <= jr&&jv>semx[i])
//    {
//
//        lazy(i, r - l + 1, jv - mx[i], 0ll, jv - mx[i], 0ll);
//    }
//    else
//    {
//        int mid = (l + r) >> 1;
//        down(i, mid - l + 1, r - mid);
//        if (jl <= mid)
//            update(jl, jr, jv, l, mid, i << 1);
//        if (jr >= mid + 1)
//            update(jl, jr, jv, mid + 1, r, i << 1 | 1);
//        up(i);
//    }
//   
//}
//void _add(int jl, int jr, int jv, int l, int r, int i)
//{
//    if (l >= jl && r <= jr)
//    {
//        lazy(i, r - l + 1, jv, jv, jv, jv);
//    }
//    else
//    {
//        int mid = (l + r) >> 1;
//        down(i, mid - l + 1, r - mid);
//        if (jl <= mid)
//            _add(jl, jr, jv, l, mid, i << 1);
//        if (jr >= mid + 1)
//            _add(jl, jr, jv, mid + 1, r, i << 1 | 1);
//        up(i);
//    }
//   
//}


//int mul(int a, int b) {
//    return (int)((1ll * a * b) % mod);
//}
//int binpow(int a, int pw) {
//    int b = 1;
//    while (pw) {
//        if (pw & 1)
//            b = mul(b, a);
//        a = mul(a, a);
//        pw >>= 1;
//    }
//    return b;
//}
//int inv(int a) {
//    return binpow(a, mod - 2);
//}
//const int N = 1000001;
//int ff[N], rr[N];
//void precalc() {
//    ff[0] = 1;
//    for (int i = 1; i < N; i++)
//        ff[i] = mul(ff[i - 1], i);
//    rr[N - 1] = inv(ff[N - 1]);
//    for (int i = N - 2; i > -1; i--)
//        rr[i] = mul(rr[i + 1], i + 1);
//}
//int C(int n, int k) {
//    if (n < 0 || k < 0 || n < k)
//        return 0;
//    return mul(ff[n], mul(rr[k], rr[n - k]));
//}
//
//int add(int a, int b) {
//    if (a + b >= mod)
//        return a + b - mod;
//    return a + b;
//}
//int arr[100001];
//int mn[400004];
//int mx[400004];
//int sm[400004];
//int laz[400004];
//int change[400004];
//bool vis[400004];
//array<int, 3> build(int l, int r, int i)
//{
//    if (l == r)
//    {
//        sm[i] = arr[l];
//        mx[i] = arr[l];
//        mn[i] = arr[l];
//        laz[i] = 0;
//        return{ sm[i],mx[i],mn[i] };
//    }
//    int mid = (l + r) >> 1;
//    array<int, 3> a = build(l, mid, i << 1);
//    array<int, 3> b = build(mid + 1, r, i << 1 | 1);
//    sm[i] = a[0] + b[0];
//    mx[i] = max(a[1], b[1]);
//    mn[i] = min(a[2], b[2]);
//    laz[i] = 0;
//    return { sm[i],mx[i],mn[i] };
//}
//void lazy(int i, int n, int v)
//{
//    if (vis[i])
//    {
//        sm[i] = n * change[i];
//        mx[i] = change[i];
//        mn[i] = change[i];
//        laz[i] = change[i];
//    }
//    if (v != 0) {
//        sm[i] += n * v;
//        mx[i] += v;
//        mn[i] += v;
//        laz[i] += v;
//    }
//}
//void down(int i, int z, int y)
//{
//    if (laz[i] != 0 || vis[i])
//    {
//        lazy(i << 1, z, laz[i]);
//        lazy(i << 1 | 1, y, laz[i]);
//    }
//    laz[i] = 0; vis[i] = false;
//}
//void up(int i)
//{
//    sm[i] = sm[i << 1] + sm[i << 1 | 1];
//    mx[i] = max(mx[i << 1], mx[i << 1 | 1]);
//    mn[i] = min(mn[i << 1], mn[i << 1 | 1]);
//}
//array<int, 3> que(int jl, int jr, int l, int r, int i)
//{
//    if (jl <= l && r <= jr)
//    {
//        return{ sm[i],mx[i],mn[i] };
//    }
//    int mid = (l + r) >> 1;
//    down(i, mid - l + 1, r - mid);
//    array<int, 3>ans = { 0,-1e18,1e18 };
//    if (jl <= mid)
//    {
//        array<int, 3>a = que(jl, jr, l, mid, i << 1);
//        ans[0] += a[0];
//        ans[1] = max(a[1], ans[1]);
//        ans[2] = min(a[2], ans[2]);
//    }
//    if (jr >= mid + 1)
//    {
//        array<int, 3>a = que(jl, jr, mid + 1, r, i << 1 | 1);
//        ans[0] += a[0];
//        ans[1] = max(a[1], ans[1]);
//        ans[2] = min(a[2], ans[2]);
//    }
//    return ans;
//}
//void _add(int jl, int jr, int jv, int l, int r, int i)
//{
//    if (l >= jl && r <= jr)
//    {
//        lazy(i, r - l + 1, jv);
//    }
//    else
//    {
//        int mid = (l + r) >> 1;
//        down(i, mid - l + 1, r - mid);
//        if (jl <= mid)
//            _add(jl, jr, jv, l, mid, i << 1);
//        if (jr >= mid + 1)
//            _add(jl, jr, jv, mid + 1, r, i << 1 | 1);
//        up(i);
//    }
//}void update(int jl, int jr, int jv, int l, int r, int i)
//{
//    if (l >= jl && r <= jr)
//    {
//        change[i] = jv;
//        vis[i] = true;
//        laz[i] = 0;
//        lazy(i, r - l + 1, laz[i]);
//    }
//    else
//    {
//        int mid = (l + r) >> 1;
//        down(i, mid - l + 1, r - mid);
//        if (jl <= mid)
//            update(jl, jr, jv, l, mid, i << 1);
//        if (jr >= mid + 1)
//            update(jl, jr, jv, mid + 1, r, i << 1 | 1);
//        up(i);
//    }
//}
//int mul(int a, int b) {
//        return (int)((1ll * a * b) % mod);
//    }
//    int binpow(int a, int pw) {
//        int b = 1;
//        while (pw) {
//            if (pw & 1)
//                b = mul(b, a);
//            a = mul(a, a);
//            pw >>= 1;
//        }
//        return b;
//    }
//    int inv(int a) {
//        return binpow(a, mod - 2);
//    }
//    const int N = 100001;
//    int ff[N], rr[N];
//    void precalc() {
//        ff[0] = 1;
//        for (int i = 1; i < N; i++)
//            ff[i] = mul(ff[i - 1], i);
//        rr[N - 1] = inv(ff[N - 1]);
//        for (int i = N - 2; i > -1; i--)
//            rr[i] = mul(rr[i + 1], i + 1);
//    }
//    int C(int n, int k) {
//        if (n < 0 || k < 0 || n < k)
//            return 0;
//        return mul(ff[n], mul(rr[k], rr[n - k]));
//    }
//    
//    int add(int a, int b) {
//        if (a + b >= mod)
//            return a + b - mod;
//        return a + b;
//    }
//namespace string_hash
//{#define LL long long
//    const int N = 1e6 + 20;
//    const int mod1 = 998244353;
//    const int mod2 = 1e9 + 7;
//    const int P = 1000007;
//    LL p1[N], p2[N];
//    // 双模数初始化
//    void mod_init()
//    {
//        p1[0] = p2[0] = 1;
//        for (int i = 1; i < N; i++)
//        {
//            p1[i] = p1[i - 1] * P % mod1;
//            p2[i] = p2[i - 1] * P % mod2;
//        }
//    }
//    struct Hash_String
//    {
//        string str;
//        int string_size;
//        vector<LL> h1, h2;
//        Hash_String(string s) : str(s), h1(s.size() + 1), h2(s.size() + 1)
//        {
//            str = ' ' + str;
//            string_size = str.size() - 1;
//            for (int i = 1; i < str.size(); i++)
//            {
//                h1[i] = (h1[i - 1] * P + str[i]) % mod1;
//                h2[i] = (h2[i - 1] * P + str[i]) % mod2;
//            }
//        }
//        pair<LL, LL> get(int l, int r)
//        {
//            if (l > r)
//                return { 0, 0 };
//            // assert(l <= r && l >= 1 && r <= string_size);
//            LL res1 = ((h1[r] - h1[l - 1] * p1[r - l + 1] % mod1) % mod1 + mod1) % mod1;
//            LL res2 = ((h2[r] - h2[l - 1] * p2[r - l + 1] % mod2) % mod2 + mod2) % mod2;
//            return { res1, res2 };
//        }
//        ll oneget(int l, int r) // 用于没办法用pair，只能用一个整数，但是单hash又会错的情况
//        {
//            if (l > r)
//                return 0;
//            LL res1 = ((h1[r] - h1[l - 1] * p1[r - l + 1] % mod1) % mod1 + mod1) % mod1;
//            LL res2 = ((h2[r] - h2[l - 1] * p2[r - l + 1] % mod2) % mod2 + mod2) % mod2;
//            return (res1 + P * res2);
//        }
//        pair<LL, LL> get_substring(int l1, int r1, int l2, int r2)
//        {
//            auto [v1, v2] = get(l1, r1);
//            auto [vv1, vv2] = get(l2, r2);
//            return make_pair((v1 * p1[r2 - l2 + 1] % mod1 + vv1) % mod1, (v2 * p2[r2 - l2 + 1] % mod2 + vv2) % mod2);
//            // get_hash(l1, r1) * p[r2 - l2 + 1] + get_hash(l2, r2)
//        }
//    };
//};
//using namespace string_hash;
// int arr[100001];
//int sm1[400004];
//int sm0[400004];
//int mx1[400004];
//int mx0[400004];
//int pre1[4000004];
//int suf1[4000004];
//int pre0[4000004];
//int suf0[4000004];
//bool revers[400004];
//int change[400004];
//bool vis[400004];
//void up(int i, int l, int r)
//{
//    int mid = (l + r) >> 1;
//    sm1[i] = sm1[i << 1] + sm1[i << 1 | 1];
//    sm0[i] = sm0[i << 1] + sm0[i << 1 | 1];
//    mx1[i] = max({ mx1[i << 1],mx1[i << 1 | 1] ,suf1[i << 1] + pre1[i << 1 | 1] });
//    mx0[i] = max({ mx0[i << 1], mx0[i << 1 | 1] ,suf0[i << 1] + pre0[i << 1 | 1] });
//    if (pre1[i << 1] == mid - l + 1)
//        pre1[i] = pre1[i << 1] + pre1[i << 1 | 1];
//    else pre1[i] = pre1[i << 1];
//    if (pre0[i << 1] == mid - l + 1)
//        pre0[i] = pre0[i << 1] + pre0[i << 1 | 1];
//    else pre0[i] = pre0[i << 1];
//    if (suf1[i << 1 | 1] == r - mid)
//        suf1[i] = suf1[i << 1 | 1] + suf1[i << 1];
//    else suf1[i] = suf1[i << 1 | 1];
//    if (suf0[i << 1 | 1] == r - mid)
//        suf0[i] = suf0[i << 1 | 1] + suf0[i << 1];
//    else suf0[i] = suf0[i << 1 | 1];
//}
//void build(int l, int r, int i)
//{
//    if (l == r)
//    {
//        sm1[i] = arr[l];
//        sm0[i] = 1-arr[l];
//        mx1[i] = sm1[i];
//        mx0[i] = sm0[i];
//        pre1[i] = sm1[i];
//        pre0[i] = sm0[i];
//        suf1[i] = sm1[i];
//        suf0[i] = sm0[i];
//        vis[i] = false;
//        revers[i] = false;
//        change[i] = 0;
//        //return{ sm1[i],sm0[i],mx1[i],mx0[i],pre1[i],pre0[i],suf1[i],suf0[i] };
//        return;
//    }
//    int mid = (l + r) >> 1;
//    build(l, mid, i << 1);
//    build(mid + 1, r, i << 1 | 1);
//    up(i, l, r);
//    vis[i] = false;
//    revers[i] = false;
//    change[i] = 0;
//    //return{ sm1[i],sm0[i],mx1[i],mx0[i],pre1[i],pre0[i],suf1[i],suf0[i] };
//}
//void ulazy(int i, int n,int v)
//{
//        if (v == 1) {
//            sm1[i] = n;
//            sm0[i] = 0;
//            mx1[i] = n;
//            mx0[i] = 0;
//            pre1[i] = n;
//            pre0[i] = 0;
//            suf1[i] = n;
//            suf0[i] = 0;
//        }
//        else
//        {
//            sm1[i] = 0;
//            sm0[i] = n;
//            mx1[i] = 0;
//            mx0[i] = n;
//            pre1[i] = 0;
//            pre0[i] = n;
//            suf1[i] = 0;
//            suf0[i] = n;
//        }
//        change[i] = v;
//        vis[i] = true;
//        revers[i] = false;
//}
//void rlazy(int i, int n)
//{
//        swap(sm1[i], sm0[i]);
//        swap(mx1[i], mx0[i]);
//        swap(pre1[i], pre0[i]);
//        swap(suf1[i], suf0[i]);
//        revers[i] = !revers[i];
//}
//void down(int i, int z, int y)
//{
//    if (vis[i])
//    {
//        ulazy(i << 1, z,change[i]);
//        ulazy(i << 1 | 1, y,change[i]);
//        vis[i] = false;
//    }
//    if (revers[i])
//    {
//        rlazy(i << 1, z);
//        rlazy(i << 1 | 1, y);
//        revers[i] = false;
//    }
//}
//int ques(int jl, int jr, int l, int r, int i)
//{
//    if (jl <= l && r <= jr)
//    {
//        return sm1[i];
//    }
//    int mid = (l + r) >> 1;
//    int ans = 0;
//    down(i, mid - l + 1, r - mid);
//    //array<int, 4>ans = { 0,-1e18,0,0 };
//    if (jl <= mid)
//    {
//        ans+= ques(jl, jr, l, mid, i << 1);
//
//    }
//    if (mid + 1 <= jr)
//    {
//        ans+=  ques(jl, jr, mid + 1, r, i << 1 | 1);
//
//    }
//    return ans;
//
//}
//array<int, 4> que(int jl, int jr, int l, int r, int i)
//{
//    if (jl <= l && r <= jr)
//    {
//        return{ sm1[i],mx1[i],pre1[i],suf1[i] };
//    }
//    int mid = (l + r) >> 1;
//    down(i, mid - l + 1, r - mid);
//    //array<int, 4>ans = { 0,-1e18,0,0 };
//    if (jr <= mid)
//    {
//       return que(jl, jr, l, mid, i << 1);
//        
//    }
//    if ( mid + 1<=jl)
//    {
//       return  que(jl, jr, mid + 1, r, i << 1 | 1);
//       
//    }
//    array<int, 4>a = que(jl, jr, l, mid, i<<1);
//    array<int, 4>b = que(jl, jr, mid + 1, r, i<<1|1);
//    int z = 0, zz = 0;
//    if (a[2] == mid - max(jl,l) + 1)z = a[2] + b[2];
//    else z = a[2];
//    if (b[3] == min(jr,r) - mid)zz = b[3] + a[3];
//    else zz = b[3];
//    return{ a[0] + b[0],max({a[1],b[1],a[3] + b[2]}),z,zz };
//    
//}
//void _reverse(int jl, int jr, int l, int r, int i)
//{
//    if (l >= jl && r <= jr)
//    {
//        rlazy(i, r - l + 1);
//    }
//    else
//    {
//        int mid = (l + r) >> 1;
//        down(i, mid - l + 1, r - mid);
//        if (jl <= mid)
//            _reverse(jl, jr, l, mid, i << 1);
//        if (jr >= mid + 1)
//            _reverse(jl, jr, mid + 1, r, i << 1 | 1);
//        up(i,l,r);
//    }
//}void update(int jl, int jr, int jv, int l, int r, int i)   
//{
//    if (l >= jl && r <= jr)
//    {
//       
//        ulazy(i, r - l + 1,jv);
//    }
//    else
//    {
//        int mid = (l + r) >> 1;
//        down(i, mid - l + 1, r - mid);
//        if (jl <= mid)
//            update(jl, jr, jv, l, mid, i << 1);
//        if (jr >= mid + 1)
//            update(jl, jr, jv, mid + 1, r, i << 1 | 1);
//        up(i,l,r);
//    }
//}
//const int NN = 2049;
//int tree1[NN][NN];
//int tree2[NN][NN];
//int tree3[NN][NN];
//int tree4[NN][NN];
//int n, m;
////int lowbit(int i)
////{
////    return(i & -i);
////}
//void add1(int x, int y, int v)
//{
//    int v1 = v;
//    int v2 = v * x;
//    int v3 = v * y;
//    int v4 = x * y * v;
//    for (int i = x; i <= n; i += (lowbit(i)))
//    {
//        for (int j = y; j <= m; j += lowbit(j))
//        {
//            tree1[i][j] += v1;
//            tree2[i][j] += v2;
//            tree3[i][j] += v3;
//            tree4[i][j] += v4;
//        }
//    }
//}
//void add1(int a, int b, int c, int d,int v)
//{
//    add1(a, b, v);
//    add1(c+1, b, -v);
//    add1(a, d+1, -v);
//    add1(c+1, d+1, v);
//}
//int query1(int x, int y)
//{
//    int ans = 0;
//    for (int i = x; i > 0; i -= lowbit(i))
//    {
//        for (int j = y; j > 0; j -= lowbit(j))
//        {
//            ans += ((x+1)*(y+1)*tree1[i][j]);
//            ans -= ((y+1)*tree2[i][j]);
//            ans -= ((x+1)*tree3[i][j]);
//            ans += tree4[i][j];
//        }
//    }
//    return ans;
//}
//int query(int a, int b, int c, int d)
//{
//    return query1(a-1, b-1) + query1(c, d) - query1(a - 1, d) - query1(c, b - 1);
//}
/*   int tree1[114514];
   int tree2[114514];
   int n;
   void add1(int* tree,int i, int v)
   {
       while (i <= n)
       {
           tree[i] += v;
           i += (i & -i);
       }
   }
   void add12(int l, int r, int v)
   {
       add1(tree1,l, v);
       add1(tree1,r+1, -v);
       add1(tree2,l, (l - 1) * v);
       add1(tree2,r+1, -(r * v));
   }
   int query1(int * tree,int i)
   {
       int ans = 0;
       while (i)
       {
           ans += tree[i];
           i -= (i & -i);
       }
       return ans;
   }
   int query(int l,int r)
   {
       return r * query1(tree1, r) - query1(tree2, r) - (l - 1) * query1(tree1, l - 1) + query1(tree2, l - 1);
   }*/
   /* auto adj = [&]() {//set维护中位数板子
       if (ma.size() >= mi.size() + 3)
       {
           auto a = ma.begin();
           suma += *a;
           sumb -= *a;
           mi.insert(*a);
           ma.erase(a);
       }
       if (ma.size() > mi.size())return;
       auto a = --mi.end();
       suma -= *a;
       sumb += *a;
       ma.insert(*a);
       mi.erase(a);
   };*/
   //    int wwr[1001];
   //int find(int x)
   //{
   //    if (x != wwr[x])
   //    {
   //        int w = find(wwr[x]);
   //        wwr[x] = w;
   //        return w;
   //    }
   //    else
   //    {
   //        return x;
   //    }
   //}
   //void wbwb(int a, int b)
   //{
   //    int fa = find(a);
   //    int fb = find(b);
   //    if (fa != fb)
   //    {
   //        wwr[fa] = fb;
   //       // cnt[fb] += cnt[fa];
   //    }
   //}
       //int prime[1000010] = { 0 };//质数
       //int minp[1000010] = { 0 };//最小质因子
       //void olshai(int n)
       //{
       //    int cnt = 0;
       //    for (int i = 2; i <= n; i++)
       //    {
       //        if (minp[i] == 0) { minp[i] = i; prime[++cnt] = i; }
       //        for (int j = 1; j <= cnt; j++) { if (prime[j] > minp[i] || prime[j] > n / i) break; minp[i * prime[j]] = prime[j]; }
       //    }
       //
       //}
     /*  auto dij = [&](int s, int d[], bool vis[]) {
           priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
           for (int i = 0; i <= 1 * n; i++)
               d[i] = 1e18, vis[i] = 0;
           d[s] = 0;
           q.push({ 0,s });
           while (q.size()) {
               auto t = q.top();
               q.pop();
               int u = t.second;
               if (vis[u]) continue;
               vis[u] = true;
               for (auto ed : arr[u]) {
                   int v = ed.first, w = ed.second;
                   if (d[v] > d[u] + w) {
                       d[v] = d[u] + w;
                       q.push({ d[v],v });
                   }
               }
           }
       };*/
   /*    int mergesort(vector<int>& nums, int l, int r)
       {
           long long ret = 0;
           if (l >= r)
               return 0;
           int mid = (l + r) >> 1;
           ret = (ret + mergesort(nums, l, mid)) % mod;
           ret = (ret + mergesort(nums, mid + 1, r)) % mod;
           int cur1 = l, cur2 = mid + 1, i = l;
           while (cur1 <= mid && cur2 <= r)
           {
               if (nums[cur1] <= nums[cur2])
               {
                   tem[i++] = nums[cur1++];
               }
               else {
       
                   ret = ((ret + mid) % mod - cur1 + 1) % mod;
                   tem[i++] = nums[cur2++];
       
               }
           }
           while (cur1 <= mid)tem[i++] = nums[cur1++];
           while (cur2 <= r)tem[i++] = nums[cur2++];
           for (int i = l; i <= r; i++)
               nums[i] = tem[i];
           return ret % mod;
       }*/
       //int InversePairs(vector<int>& nums) {
       //    tem.resize(nums.size());
       //    return mergesort(nums, 0, nums.size() - 1) % mod;
       //}
       //多重背包模板
       // int n, m;
       //int a[101];
       //int b[101];
       //int c[101];
       //int dp[40000 + 1];
       //int que[50000 + 100000 + 1]; cin >> n >> m;
       //for1
       //{
       //    cin >> a[i] >> b[i] >> c[i];
       //}
       //
       //for1
       //{
       //
       //
       //for (int md = 0; md <= min(m , b[i] - 1); md++)
       //{
       //    int l = 0, r = 0;
       //
       //    for (int j = m - md,k = 0; j >= 0 && k <= c[i]; j -= b[i],k++)
       //    {
       //        while (l < r && dp[que[r - 1]] <= dp[j] + a[i] * ((que[r - 1] - j) / b[i]))
       //        {
       //            r--;
       //        }
       //        que[r++] = j;
       //
       //    }
       //    for (int j = m - md; j >= 0; j -= b[i])
       //    {
       //
       //        dp[j] = dp[que[l]] + a[i] * ((j - que[l]) / b[i]);  
       //        if (j == que[l])l++;
       //        int wwr = j - b[i] * (c[i] + 1);
       //        if (wwr >= 0)
       //        { 
       //            while (l < r && dp[que[r - 1]] <= dp[wwr] + a[i] * ((que[r - 1] - wwr) / b[i]))
       //                r--;
       //            que[r++] = wwr;
       //        }
       //    }
       //}
       //
       //}
       //cout << dp[m] << endl;..
       //  vector :c.assign(beg, end)	将另外一个容器[x.begin(), x.end()) 里的内容拷贝到c中
       //vector<int>::iterator it;
       // 相当于声明了一个迭代器类型的变量it
       //less<int> 表示数字大的优先级大，堆顶为最大的数字
       //greater<int>表示数字小的优先级大，堆顶为最小的数字，优先队列比较要写结构体cmp
       //mp.lower_bound()	返回一个迭代器，指向键值 >= key的第一个元素
       //mp.upper_bound()	返回一个迭代器，指向键值 > key的第一个元素             for(auto [x, y] : mp)
       //getline(cin, s)会获取前一个输入的换行符，需要在前面添加读取换行符的语句。如：getchar() 或 cin.get()
       //tolower(s[i])	转换为小写
       //toupper(s[i])	转换为大写
       //transform(s.begin(), s.end(), s.begin(), ::tolower);//转换小写
       //transform(s.begin(), s.end(), s.begin(), ::toupper);//转换大写 find返回-1是找不到
       //bitset<n> a(s)	a是string对象s中含有的位串的副本
       //bitset<n> a(s, pos, n)	a是s中从位置pos开始的n个位的副本 bitset可以进行位操作可以通过 [] 访问元素 
       //b.count()	b中为1的个数
       //fill(a.begin(), a.end(), x)填充
       //tuple获取对应元素的值通过get<n>(tuple)方法获取, n必须为数字不能是变量
       //tie可以让tuple变量中的三个值依次赋到tie中的三个变量中tie(one, two, three) = t;
       //accumulate(beg, end, init)作用：对一个序列的元素求和init为对序列元素求和的初始值返回值类型：与init 相同
       //atoi(const char*)将字符串转换为int类型int a = atoi(s.c_str());
       //is_sorted(beg, end) 判断序列是否有序（升序），返回bool值
       //iota(beg, end，初始值)让序列递增赋值如 把数组赋值为：0 1 2 3 4 5
       //max_element+min_element找最大最小值
       ////找到a,b,c,d的最大值和最小值
       //mx = max({ a, b, c, d });
       //mn = min({ a, b, c, d });
       //nth_element(beg, nth, end)复杂度： 平均O(N)O(N)寻找第序列第n小的值
       //shuffle(b.begin(), b.end()); 随机打乱序列的顺序
       //reverse(beg, end)对序列进行翻转
       //stable_sort区别在于stable_sort()能够保证相等元素的相对位置，排序时不会改变相等元素的相对位置
       //unique(beg, end)消除重复元素，返回消除完重复元素的下一个位置的地址
       // 消除重复元素一般需要原序列是有序序列 unique 之后 a 数组为 { 1, 2, 3, 6, 3 }前面为无重复元素的数组，后面则是重复元素移到后面，返回a[4]
       //int len = unique(b, b + n) - b;//消除 b 的重复元素，并获取长度