stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;



int const N=1e5+5, M=1e9+7, OO = 0x3f3f3f3f;



int n,k;

int arr[N];



int mem[N];

int solve(int i)

{

    if(i==n-1)

        return 0;

    if(mem[i]!=-1)

        return mem[i];

    int ret=OO;

    for(int j=1; j<=k && i+j<=n-1; j++)

        ret=min(ret,solve(i+j)+abs(arr[i]-arr[i+j]));

    return mem[i]=ret;

}





int main()

{

//    freopen("input.txt","rt",stdin);

//    freopen("output.txt","wt",stdout);

    scanf("%d %d",&n,&k);

    for(int i=0; i<n; i++)

        scanf("%d",arr+i);

    memset(mem, -1, sizeof mem);

    printf("%d\n",solve(0));



    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.3873268971290156x):
#include<bits/stdc++.h>

using namespace std;

int n,k; vector<int>v;

long long dp[100005];



int main() {

	cin >> n>>k; 

	v.resize(n + 1);

	for (int i = 1; i <= n;i++)cin >> v[i];

	fill(dp, dp + n + 1, 1e18);

	dp[1] = 0;

	for (int i = 1; i <= n; i++) {

		for (int j = 1; j <= k; j++) {

			if(i+j<=n)dp[i+j] = min(dp[i+j], dp[i] + abs(v[i] - v[i+j]));

		}

	}

	cout << dp[n];

}
// Slower C++ solution:
//Zory-2018

#include<cmath>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<map>

#include<set>

#include<queue>

#include<deque>

#include<bitset>

#include<vector>

#include<algorithm>

#include<iostream>

#include<stack>

using namespace std;



namespace mine

{

	const int MAX_N=310000;

	typedef long long ll;

	int mymax(int x,int y) {return x>y?x:y;}



	int a[MAX_N],mx[MAX_N];

	int ans[MAX_N];

	void main()

	{

		int n;scanf("%d",&n);

		int m=1<<n;

		for(int i=0;i<m;i++) scanf("%d",&a[i]);



		for(int k=1;k<m;k++)

		{

			ans[k]=mymax(a[0],ans[k-1]);

			mx[k]=a[0];

			for(int u=k;u>0;u=(u-1)&k)

				ans[k]=mymax(ans[k],a[u]+mx[k]),mx[k]=mymax(mx[k],a[u]);

			printf("%d\n",ans[k]);

		}

	}

};



int main()

{

	mine::main();

}


// Faster C++ solution for the same problem (measured speedup: 5.0713352582571645x):
#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#include<queue>

#include<vector>

#include<ctime>

#include<map>

#include<bitset>

#include<set>

#define LL long long

#define mp(x,y) make_pair(x,y)

#define pll pair<long long,long long>

#define pii pair<int,int>

using namespace std;

inline int read()

{

	int f=1,x=0;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

	return x*f;

}

int stack[20];

inline void write(LL x)

{

	if(x<0){putchar('-');x=-x;}

    if(!x){putchar('0');return;}

    int top=0;

    while(x)stack[++top]=x%10,x/=10;

    while(top)putchar(stack[top--]+'0');

}

inline void pr1(int x){write(x);putchar(' ');}

inline void pr2(LL x){write(x);putchar('\n');}



const int MAX_N=20;

int bin[MAX_N];

#define pr pair<int,int>

#define FR first

#define SE second

#define MP make_pair

int a[1<<MAX_N];pr b[1<<MAX_N];

int gmax(int x,int y){return a[x]>a[y]?x:y;}

pr merge(pr x,pr y)

{

	if(a[x.FR]>a[y.FR]) return MP(x.FR,gmax(x.SE,y.FR));

	else return MP(y.FR,gmax(x.FR,y.SE));

}

void fwt(int n)

{

	for(int i=0;i<n;i++)

		for(int j=bin[n]-1;j>=0;j--) if(j&bin[i])

				b[j]=merge(b[j],b[j^bin[i]]);

}

int main()

{

	bin[0]=1;for(int i=1;i<MAX_N;i++) bin[i]=bin[i-1]<<1;

	

	int n;scanf("%d",&n);a[bin[n]]=0;

	for(int i=0;i<bin[n];i++) scanf("%d",&a[i]),b[i]=MP(i,bin[n]);

	fwt(n);

	int lst=0;

	for(int i=1;i<bin[n];i++)

	{

		lst=max(a[b[i].FR]+a[b[i].SE],lst);

		printf("%d\n",lst);

	}

}

/*

4

75 26 45 72 81 47 97 97 2 2 25 82 84 17 56 32

*/
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define ld long double

#define sf scanf

#define pf printf

#define pb push_back

#define llu unsigned long long

#define U unsigned int

#define SIZE 10000000

#define pie 3.14159265358979323

#define minuss 1e-6

#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)



#define BIG 100000000000000



ll  lcm(ll a,ll b)

{

    ll GCD=__gcd(a,b);

    ll lcm=(a*b)/GCD;

    return lcm;

}

ll dp[1000005];

ll weight[1000005];

ll total,val;

int main()

{

    cin>>total>>val;

    for ( int i = 1; i <=total; i++ )

        cin>>weight[i];



    weight[0]=SIZE;

    for(int i=2; i<=total; i++)

    {

        dp[i]=BIG;

        for(int j=1; j<=val; j++)

            if(i-j>=1)

                dp[i]=min(dp[i],abs(weight[i]-weight[i-j])+dp[i-j]);



    }

    cout<<dp[total]<<endl;

    return 0;

}




// Faster C++ solution for the same problem (measured speedup: 5.218216388806832x):
#include<cstdio>

#include<algorithm>

using namespace std;



#define ll long long 



#define file_io 0



ll i,t,j;

ll n,k,h[100005],dp[100005];



int main(){

	if (file_io){

		freopen(".in","r",stdin);

		freopen(".out","w",stdout);

	}

	

	scanf("%lld%lld",&n,&k);

	

	for (i=1; i<=n; ++i){

		scanf("%lld",&h[i]);

	}

	

	dp[1]=0;

	for (i=2; i<=n; ++i){

		dp[i]=2e9;

		for (t=max(1ll,i-k); t<i; ++t){

			dp[i]=min(dp[t]+abs(h[i]-h[t]),dp[i]);

		}

	}

	

	printf("%lld\n",dp[n]);

	

	return 0;

}
// Slower C++ solution:
#include<iostream>

#include<algorithm>

#include<map>

using namespace std;

typedef pair<int,int> P;

#define fr first

#define sc second

P seg[1<<18];

int n;

void update(int id,int pt){

  int k = id + n - 1;

  seg[k].fr += pt;

  seg[k].sc = -id;

  while(k != 0){

    k = ( k - 1 ) / 2;

    seg[k] = max(seg[2*k+1],seg[2*k+2]);

  }

}

void init(int size) {

  n = 1;

  while(n < size) n *= 2;

}

int main(){

  int N,R,L;

  cin >> N >> R >> L;

  init(N);

  for(int i = 0 ; i < N ; i++ ) update(i,0);

  int mostid = 0 , now = 0 , sum[100000] = {};

  for(int i = 0 ; i < R ; i++ ){

    int d,t,x;

    cin >> d >> t >> x;

    update(d-1,x);

    sum[mostid] += t - now;

    now = t;

    mostid = -seg[0].sc;

  }

  sum[mostid] += L - now;

  int rec = 0;

  for(int i = 0 ; i < N ; i++) if( sum[rec] < sum[i] ) rec = i;

  cout << rec + 1 << endl;

}

// Faster C++ solution for the same problem (measured speedup: 2.3427095671104445x):
#include<cstdio>

#include<algorithm>

#include<map>

using namespace std;

typedef pair<int,int> P;

#define fr first

#define sc second

P seg[1<<18];

int n;

void update(int id,int pt){

  int k = id + n - 1;

  seg[k].fr += pt;

  seg[k].sc = -id;

  while(k != 0){

    k = ( k - 1 ) / 2;

    seg[k] = max(seg[2*k+1],seg[2*k+2]);

  }

}

void init(int size) {

  n = 1;

  while(n < size) n *= 2;

  for(int i = 0 ; i < size ; i++ ) update(i,0);

}

int main(){

  int N,R,L;

  scanf("%d %d %d",&N,&R,&L);

  init(N);

  int mostid = 0 , now = 0 , sum[100000] = {};

  for(int i = 0 ; i < R ; i++ ){

    int d,t,x;

    scanf("%d %d %d",&d,&t,&x);

    update(d-1,x);

    sum[mostid] += t - now;

    now = t;

    mostid = -seg[0].sc;

  }

  sum[mostid] += L - now;

  int rec = 0;

  for(int i = 0 ; i < N ; i++) if( sum[rec] < sum[i] ) rec = i;

  printf("%d\n",rec+1);

}
// Slower C++ solution:
#include<iostream>

#include<cstdio>

#include<algorithm>

#include<queue>

using namespace std;

int n,k;

long long ans;

int main()

{

    scanf("%d%d",&n,&k);

    for(int b=k+1;b<=n;b++)

    {

        ans+=n/b*(b-k);

        if(k>0)ans+=max(0,n%b-k+1);

        else ans+=max(0,n%b-k);

    }

    printf("%lld",ans);

}

// Faster C++ solution for the same problem (measured speedup: 5.042463162887655x):
#include<cstdio>

#include<algorithm>

using namespace std;

int N,K;

long long ans=0;

int main() {

	#ifdef LOACL

	freopen("in.txt","r",stdin);

	freopen("out.txt","w",stdout);

	#endif

	scanf("%d %d",&N,&K);

	if(K==0)ans=1ll*N*N;

	else {

		for(int b=K+1;b<=N;b++) {

			int x1=b-K;

			int x2=N/b;

			int k=N-x2*b;

			if(k>=K)ans+=k-K+1;

			ans+=x1*x2;

		}

	}

	printf("%lld\n",ans);

	return 0;

}
// Slower C++ solution:
#include <stdio.h>

#include <iostream>

#include <iomanip>

#include <math.h>

#include <string>

using namespace std;

int main () { 

	long long x,y = 1;

	cin >> x;

	for(int i = 1; i <= x; i++){

			y = y * i % (1000000007);

		}

	cout << y << endl;

} 			


// Faster C++ solution for the same problem (measured speedup: 3.5478908017436175x):
#include <cstdio>

const long long MOD=1e9+7;

int n;

long long ans=1;

int main()

{

	scanf("%d",&n);

	for(int i=1;i<=n;i++) ans=(ans*i)%MOD;

	printf("%lld",ans);

}
// Slower C++ solution:
#define _CRT_SECURE_NO_WARNINGS

#include<bits/stdc++.h>

#include<unordered_map>

#include<unordered_set>	

using namespace std;

typedef long long ll;

#define bay_bay return 0;

#define fori(n) for(int i=0;i<n;++i)

#define for1(n) for(int i=1;i<=n;i+=3)

#define all(v) ((v).begin()), ((v).end())	

#define sz(v) v.size()

#define endl "\n"

constexpr auto EPS = 1e-9;

#define ff fflush(stdout);

const int mod = 1000000007LL;

clock_t T;

#define ctime cerr << "Time : " << double(clock() - T) / CLOCKS_PER_SEC << endl

void GOAT()

{

	std::ios_base::sync_with_stdio(0);

	cin.tie(NULL);

	cout.tie(NULL);

#ifndef ONLINE_JUDGE

	freopen("in.txt", "r", stdin);

	//freopen("output.txt", "w	", stdout);

#else

#endif

}

ll arr[100009],dp[100009], n,k;



int main()

{

	//GOAT();

	cin >> n >> k;

	for (int i = 1; i <= n;i++)

		cin >> arr[i];

	memset(dp, -1, sizeof dp);

	dp[1] = 0;

	for (int i = 1; i <= n; i++)

	{

		for (int j = 1; j <= k; j++)

		{

			if (i + j <= n)

			{

				ll ch = dp[i] + abs(arr[i] - arr[i + j]);

				if (ch < dp[i + j] || dp[i + j] == -1)dp[i + j] = ch;

			}

		}

	}

	cout << dp[n] << endl;

}

// Faster C++ solution for the same problem (measured speedup: 1.2867088223150762x):
/******

author :- Mahmoud Tarek.

*******/



#include<bits/stdc++.h>



using namespace std ;



#define rg register

#define dbg(v) cerr << #v << " " << v ;

typedef long long ll ;



int n, k;

vector<int> a ;

int mx = 0 ;

int mem[100002] ;



int solve(int i){

if(i + 1 == n) return 0 ;

int & ret = mem[i];

if(~ret) return ret ;

ret = mx ;

for(int j = 1 ; j <= k ; j++){

    if(i + j < n){

        ret = min(ret, abs(a[i] - a[i + j]) + solve(i + j)) ;

    }

}

return ret ;

}



int main() {

//    freopen("in.txt", "r", stdin) ;

     cin >> n >> k ;

     a.resize(n) ;



     for(int i = 0 ; i < n ; i++){

        cin >> a[i] ;

        if(i >= 1){

            mx += abs(a[i] - a[i - 1]) ;

        }

     }



     if(mx == 0) mx = a[0] ;





     memset(mem, -1, sizeof mem) ;



     cout << solve(0);

}



/*

  Empty set of troubles.

*/
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

#define rep(i,n) for(int i = 0; i < (n); ++i)

#define ll long long

const ll INF = 1e18;



int main(void)

{

    ll n, m, l=0, r=INF;

    cin >> n >> m;

    vector<ll> a(200000,0);

    rep(i,m){

        ll a, b;

        cin >> a >> b;

        l = max(l, a);

        r = min(r, b);

    }

    cout << max(0LL, r-l+1) << endl;

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.6279685297061968x):
#include <bits/stdc++.h>

using namespace std;

#define rep(i,n) for(int i = 0; i < (n); ++i)



int main(void)

{

    int n, m, l=1, r;

    cin >> n >> m;

  	r = n;

    rep(i,m){

        int a, b;

        cin >> a >> b;

        l = max(l, a);

        r = min(r, b);

    }

    cout << max(0, r-l+1) << endl;

    return 0;

}
// Slower C++ solution:
/*alurquiza*/

//

#include <bits/stdc++.h>



using namespace std;



const int SIZE = 18,SIZE2 = 1 << SIZE;

int DP[SIZE2];

int MAX[SIZE2][4];

vector<int> V(SIZE2);



bool comp(const int &a,const int &b){

    if(a == -1)

        return false;

    if(b == -1)

        return true;



    if(V[a] >= V[b])

        return true;

    return false;

}



void join(int mask,int smask){

    MAX[mask][2] = MAX[smask][0];

    MAX[mask][3] = MAX[smask][1];



    int N = 4;

    stable_sort(MAX[mask],MAX[mask] + N);

    N = unique(MAX[mask],MAX[mask] + N) - MAX[mask];



    stable_sort(MAX[mask],MAX[mask] + N,comp);

}



int main()

{

//    ios_base::sync_with_stdio(0);

//    cin.tie(0); cout.tie(0);



//    freopen(".in","r",stdin);

//    freopen("F.out","w",stdout);



    int N;

    cin >> N;



    for(int i = 0;i < (1 << N);i++)

        cin >> V[i];



    for(int mask = 0;mask < (1 << N);mask++){

        MAX[mask][0] = mask;

        MAX[mask][1] = -1;



        for(int i = 0;(1 << i) <= mask;i++){

            if((1 << i) & mask){

                int nmask = mask ^ (1 << i);

                join(mask,nmask);

            }

        }

        if(MAX[mask][1] != -1)

            DP[mask] = V[MAX[mask][1]];

        DP[mask] += V[MAX[mask][0]];

    }



    for(int i = 1;i < (1 << N);i++){

        DP[i] = max(DP[i],DP[i - 1]);

        cout << DP[i] << '\n';

    }



    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 2.107504556964714x):


# include <bits/stdc++.h>

# define A first

# define B second

# define PII pair<int,int>

using namespace std;

const int maxn = 1<<18;

int a[maxn+3];

PII imax[maxn];

void fun(int x, PII &y)

{

    if(x == y.A || x == y.B) return;

    if(a[x] > a[y.A]) y.B = y.A,y.A = x;

    else if(a[x] > a[y.B]) y.B=x;

}

int main()

{

    int N, n, ans=0;

    scanf("%d",&n);

    N = 1<<n;

    a[N] = 0;

    for(int i=0; i<N; ++i) scanf("%d",&a[i]), imax[i].A=i, imax[i].B=N;

    for(int i=1; i<N; ++i)

    {

        for(int j=0; j<n; ++j)

        {

            if(i&(1<<j))

            {

                int k=i^(1<<j);

                fun(imax[k].A, imax[i]);

                fun(imax[k].B, imax[i]);

            }

        }

    }

    for(int i=1; i<N; ++i)

    {

        ans = max(ans, a[imax[i].A]+a[imax[i].B]);

        printf("%d\n",ans);

    }

    return 0;

}
// Slower C++ solution:
#include <iostream>

#include <algorithm>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

using namespace std;



int main()

{

    long long n;

    scanf("%lld",&n);

    long long i,sum=1;

    for(i=1; i<=n; i++)

    {

        sum*=i;

        sum%=1000000007;

    }

    printf("%lld\n",sum);

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 3.486423034471254x):
#include <stdio.h>

#include <algorithm>

using namespace std;



int main()

{

	int n,i;

	long long sum=1;

	scanf("%d",&n);

	for(i=1;i<=n;i++)

	{

		sum*=i;

		sum%=(1000000000+7);

	}

	printf("%lld\n",sum);

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define INF 1LL<<62

#define inf 1000000007



int main() {

	ll n,m;

	cin>>n>>m;

	bool ac[100010]={false};

	ll wa[100010]={};

	for(ll i=0;i<m;i++){

		ll now;string s;

		cin>>now>>s;

		now--;

		if(s=="WA"){

			if(ac[now]==false){

				wa[now]++;

			}

		}

		else{

			ac[now]=true;

		}

	}

	ll accnt=0;ll wacnt=0;

	for(ll i=0;i<n;i++){

		if(ac[i]){

			accnt++;

			wacnt+=wa[i];

		}

	}

	cout << accnt<<" "<<wacnt;

	// your code goes here

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.8892142935891627x):
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define INF 1LL<<62

#define inf 1000000007

 	bool ac[100010]={};

	ll wa[100010]={};

int main() {

	ll n,k;

	cin>>n>>k;



	for(ll i=0;i<k;i++){

		ll x;string s;

		cin>>x>>s;x--;

		if(s=="AC"){

			ac[x]=true;

		}

		else{

			if(ac[x]!=true){

				wa[x]++;

			}

		}

	}

		ll cnt1=0;

		ll cnt2=0;

		for(ll i=0;i<n;i++){

			if(ac[i]){

				cnt1++;

				cnt2+=wa[i];

			}

		}

		cout << cnt1<<" "<<cnt2;	

	// your code goes here

	return 0;

}
// Slower C++ solution:
#include<iostream>

#include<string>

using namespace std;

int main(){

	int k;

	string s;

	cin>>k>>s;

	if(s.length()<=k) cout<<s<<endl;

	else{

		for(int i=0;i<k;i++){

			cout<<s[i];

		}

		cout<<"...";

	}

	return 0;

} 

// Faster C++ solution for the same problem (measured speedup: 5.263026182483441x):
#include <stdio.h>

#include <string.h>

int main(){

	int k;

	scanf("%d",&k);

	char s[100];

	scanf("%s",&s);

	int lol = strlen(s);

	s[k] = '\0';

	for(int i=0;s[i]!='\0';i++){

		printf("%c",s[i]);

	}

	if(k<lol){

		printf("...");

	}

return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

int n,k;

int dp[100005],num[100005];

int main() {

	cin.tie(),cout.tie();

	memset(dp,233333,sizeof(dp));

	cin>>n>>k;

	for (int i=1;i<=n;i++) cin>>num[i];

	dp[0]=0;

	dp[1]=0;

	for (int i=2;i<=n;i++) {

		for (int j=max(1,i-k);j<=i-1;j++) {

			int add=fabs(num[i]-num[j]);

			dp[i]=min(dp[i],dp[j]+add);

		}

//		cout<<i<<':'<<dp[i]<<endl;

	}

	cout<<dp[n]<<endl;

	return 0;

} 

// Faster C++ solution for the same problem (measured speedup: 1.404411657386128x):
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll inf=1e9;

ll n,k,num[2000005],dp[2000005];

inline ll smax(ll x,ll y) {return x>y?x:y;}

inline ll smin(ll x,ll y) {return x<y?x:y;}

inline ll sabs(ll x) {return x>0?x:-x;}

int main() {

	cin>>n>>k;

	for (int i=1;i<=n;i++) cin>>num[i];

	for (int i=1;i<=n;i++) dp[i]=inf;

	dp[1]=0;

	dp[2]=dp[1]+sabs(num[1]-num[2]);

//	cout<<smax(1,10000)<<' '<<smin(1,10000)<<' '<<sabs(5-100);

	for (ll i=3;i<=n;i++) 

		for (ll j=i-1;j>=smax(1,i-k);j--) 

			dp[i]=smin(dp[i],dp[j]+abs(num[i]-num[j]));

	

//	for (int i=1;i<=n;i++) cout<<dp[i]<<' ';

//	cout<<endl;

	cout<<dp[n]<<endl;

	return 0;

}
// Slower C++ solution:
#include <cstdio>

#include <cstring>

#include <vector>

using std::vector;



#define MAXN 100005

#define MAXH 405

int indeg[MAXH],outdeg[MAXH];

bool vis[MAXH];

vector<int> G[MAXH];



void add_edge(int u,int v)

{

    outdeg[u]++;indeg[v]++;

    G[u].push_back(v);G[v].push_back(u);

}



bool dfs(int v)

{

    bool f=indeg[v]!=outdeg[v];

    vis[v]=true;

    for(auto to:G[v])

    {

        if(!vis[to]) 

            f|=dfs(to);

    }

    return f;

}



int main()

{

    int N,H;

    int a[MAXN],b[MAXN],c[MAXN],d[MAXN];

    scanf("%d%d",&N,&H);

    for(int i=1;i<=N;i++) 

    {

        scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);

        int l,r;

        l= ( c[i]==0 ? a[i] : -c[i] );

        r= ( d[i]==0 ? -b[i] : d[i] );

        add_edge(l+H,r+H);

    }



    bool flag=true;

    for(int i=0;flag && i<=H;i++) 

    {

        if(outdeg[i]>indeg[i]) 

            flag=false;

    }

    for(int i=H+1;flag && i<=2*H;i++)

    {

        if(indeg[i]>outdeg[i]) 

             flag=false;

    }



    memset(vis,false,sizeof(vis));

    for(int i=0;flag && i<=2*H;i++)

    {

        if((indeg[i]||outdeg[i])&&!vis[i]) 

            flag &=dfs(i);

    }



    if(flag) 

    {

        printf("YES\n"); 

    }

    else

    { 

        printf("NO\n");

    }

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 4.942855767904982x):
#include<cstdio>

#include<cstring>

#define retrun return

#define cpnst const

int CT[444][444],DEG[444],SZ[444],Lm=401;

class UFS

{

	int Fa[1111];

	public:

	void init(){for(register int i=1;i<=1000;i++)Fa[i]=i;}

	int rt(int x){return Fa[x]^x?Fa[x]=rt(Fa[x]):x;}

	bool merge(int x,int y){return x=rt(x),y=rt(y),Fa[x]=y,x^y;}

}U;

void rd()

{

	int a,b,c,d;

	scanf("%d%d%d%d",&a,&b,&c,&d);

	if(c)a=-c;if(d)b=d;else b=-b;

	U.merge(a+201,b+201),CT[a+201][b+201]++,

	DEG[a+201]++,DEG[b+201]--,SZ[a+201]++,SZ[b+201]++;

}

int UNB[11111];

void cover(int x)

{UNB[U.rt(x)]=1;}

int main()

{

	register int i;

	int n;

	scanf("%d%*d",&n),U.init();

	for(i=1;i<=n;i++)rd();

	for(i=-200;i<=200;i++)

	{

		if(i<0&&DEG[i+201]>0)return puts("NO"),0;

		if(i>0&&DEG[i+201]<0)return puts("NO"),0;

	}for(i=1;i<=Lm;i++)

		if(DEG[i])cover(i);

	for(i=1;i<=Lm;i++)

		if(SZ[i])

			if(!UNB[U.rt(i)])return puts("NO"),0;

	puts("YES");

}

/*

Just go for it.

*/
// Slower C++ solution:
#include <iostream>

#include <cstdio>

#include <cstring>

#define int long long

#define N 100002

using namespace std;

int n,i,a[N],c[N*2],sum[N],l,r,mid,ans;

int lowbit(int x)

{

	return x&(-x);

}

void modify(int x,int y)

{

	for(int i=x;i<=N+n;i+=lowbit(i)) c[i]+=y;

}

int ask(int x)

{

	int ans=0;

	for(int i=x;i>=N-n;i-=lowbit(i)) ans+=c[i];

	return ans;

}

bool check(int x)

{

	int ans=0;

	memset(c,0,sizeof(c));

	for(int i=1;i<=n;i++){

		if(a[i]<x) sum[i]=sum[i-1]-1;

		else sum[i]=sum[i-1]+1;

	}

	for(int i=0;i<=n;i++){

		ans+=ask(sum[i]+N);

		modify(sum[i]+N,1);

	}

	if(ans>=n*(n+1)/4) return 1;

	return 0;

}

signed main()

{

	cin>>n;

	for(i=1;i<=n;i++){

		cin>>a[i];

		r=max(r,a[i]);

	}

	while(l<=r){

		mid=(l+r)/2;

		if(check(mid)){

			ans=mid;

			l=mid+1;

		}

		else r=mid-1;

	}

	cout<<ans<<endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 3.3632062159806706x):
#include <cstdio>

#include <cstring>

#include <algorithm>

#define ll long long

#define inf 1<<30

#define il inline 

il void readl(ll &x){

    x=0;ll f=1;char c=getchar();

    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}

    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}

    x*=f;

}

il void read(int &x){

    x=0;int f=1;char c=getchar();

    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}

    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}

    x*=f;

}

using namespace std;



#define N 100010

#define lowbit(x) x&-x

int c[N*10];

int n,a[N],s[N*10];

void add(int x){

    for(int i=x;i<=2*N;i+=lowbit(i))c[i]++;

}

ll query(int x){

    ll sum=0;

    for(int i=x;i>0;i-=lowbit(i))sum+=c[i];

    return sum;

}

bool check(int x){

    for(int i=1;i<=2*N;i++)c[i]=0;

    s[0]=0;

    for(int i=1;i<=n;i++)

        s[i]=s[i-1]+(a[i]>=x?1:-1);

    ll sum=0;

    for(int i=0;i<=n;i++){

        sum+=query(s[i]+N);

        add(s[i]+N);

    }

    return sum>=1ll*n*(n+1)/4;

}

int main(){

    read(n);

    int l=0,r=0;

    for(int i=1;i<=n;i++){

        read(a[i]);

        r=max(r,a[i]);

    }

    int ans=0;

    while(l<=r){

        int mid=(l+r)>>1;

        if(check(mid)) l=mid+1;

        else r=mid-1;

    }

    printf("%d\n",r);

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;



int n,m;

int l[1000000];

int dp[1000000];

main()

{

    cin>>n>>m;

    fill(dp,dp+n+1,1e9);

    for(int i=1;i<=n;i++){

        cin>>l[i];

    }

    dp[1]=0;

    dp[2]=abs(l[2]-l[1]);

    for(int i=3;i<=n;i++){

        for(int j=i-1;j>=i-m;j--){

            if(j<0)break;;

            dp[i]=min(dp[i],dp[j]+abs(l[j]-l[i]));//cout<<j<<" ";

        }//cout<<dp[i];

        //cout<<"\n";

    }

    cout<<dp[n];

}


// Faster C++ solution for the same problem (measured speedup: 5.216509879714194x):
#include <cstdio>

#include <algorithm>

#include <vector>

using namespace std;

 

int n,dp[100005],a[100005],k; 

int main(){

	scanf("%d%d",&n,&k);

	for (int i=1;i<=n;i++){

		scanf("%d",&a[i]);

	}

	for (int i=2;i<=n;i++){

		dp[i]=dp[i-1]+abs(a[i]-a[i-1]);

		for (int j=max(1,i-k);j<i;j++){

			dp[i]=min(dp[i],dp[j]+abs(a[i]-a[j])); 

		}

	}

	printf("%d\n",dp[n]);

	return 0;

}