akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)

const int mod=1000000007;

bool IsPrime(int num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false; // 偶数はあらかじめ除く

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            // 素数ではない
            return false;
        }
    }

    // 素数である
    return true;
}

int main(){
    int n;
    cin>>n;
    vector<int> plist;
    for(int i=11;i<55556;i+=10){
        if(IsPrime(i)) plist.push_back(i);
    }
    rep(i,n){
      if(i)cout<<" ";
      cout<<plist[i];
    }
    cout<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() 
{ 
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll whole_sum = 0;
    int n;
    cin >> n;
    vector<ll> a(n), sum1(n), sum2(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        whole_sum += a[i];
        if(!(i&1)) {
            sum1[i] = (i-1 >= 0 ? sum1[i-1] : 0) + 2*a[i];
            sum2[i] = (i-1 >= 0 ? sum2[i-1] : 0);
        } else {
            sum2[i] = (i-1 >= 0 ? sum2[i-1] : 0) + 2*a[i];
            sum1[i] = (i-1 >= 0 ? sum1[i-1] : 0);
        }
    }
    for(int i = 0; i < n; i++) {
        ll diff;
        if(i&1) {
            diff = (i-2 >= 0 ? sum2[i-2] : 0) + sum1[n-1] - (i-1 >= 0 ? sum1[i-1] : 0);
        } else {
            diff = (i-2 >= 0 ? sum1[i-2] : 0) + sum2[n-1] - (i-1 >= 0 ? sum2[i-1] : 0);
        }
        cout << whole_sum - diff << " ";
    }
    cout << endl;
    return 0; 
}

Measured memory_bytes: 3712
#include <iostream>
#include <cstdio>
#include <algorithm>
#define S second
using namespace std;

int n, s;
pair<int, int> a[100005];
int main()
{
	int i;
	cin >> n;
	for (i =0; i < n; i++) {
		scanf ("%d", &a[i].first);
		a[i].S = i % 2;
	}
	sort(a, a + n);
	for (i = 0; i < n; i++) {
		if (a[i].S != i % 2) s++;
	}
	cout << s/2;
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <stdio.h>
#include <map>
#include <set>
#include <string>
using namespace std;

int main() {
	int k=0,n,f;
	string s;
	map<string,int> mp;
	set<int> st[1001];
	map<string,int>::iterator it;
	set<int>::iterator si;  
	while(cin >> s >> n) {
		it=mp.find(s);
		if (it==mp.end()) {st[k].insert(n); mp.insert(map<string,int>::value_type(s,k++));}
		else st[(*it).second].insert(n);
	}
	for (it=mp.begin(); it!=mp.end(); it++) {
		cout << (*it).first << endl;
		f=0;
		for (si=st[(*it).second].begin();si!=st[(*it).second].end();si++) if (f==0) {f=1;cout << *si;} else cout << ' ' << *si;
		cout << endl;    
	}
    return 0;
	}

Measured memory_bytes: 1276
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::cmp::*;
use std::collections::*;
use std::io::Write;

#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), std::io::stderr());
            writeln!(err, "{} = {:?}", e, $e).unwrap()
        })*
    };
}

fn main() {
    loop {
        let h = read::<usize>();
        if h == 0 {
            return;
        }
        let mut grid = vec![vec![]; h];
        for y in 0..h {
            grid[y] = read_vec::<usize>();
        }
        let before = grid.iter()
            .map(|ref row| row.iter().sum::<usize>())
            .sum::<usize>();
        grid.reverse();
        loop {
            let mut marked = HashSet::new();
            for y in 0..h {
                for x in 0..3 {
                    // 0 means not exists.
                    if grid[y][x] != 0
                        && grid[y][x] == grid[y][x + 1]
                        && grid[y][x] == grid[y][x + 2]
                    {
                        marked.insert((x, y));
                        marked.insert((x + 1, y));
                        marked.insert((x + 2, y));
                    }
                }
            }
            if marked.is_empty() {
                break;
            }

            // reconstruct
            let mut new_grid = vec![vec![0; 5]; h];
            let mut removed = vec![0; 5];
            for y in 0..h {
                for x in 0..5 {
                    while removed[x] + y < h && marked.contains(&(x, removed[x] + y)) {
                        removed[x] += 1;
                    }
                    if removed[x] + y >= h {
                        continue; // 0 is already set.
                    }
                    new_grid[y][x] = grid[removed[x] + y][x];
                }
            }
            grid = new_grid;
        }
        let after = grid.iter()
            .map(|ref row| row.iter().sum::<usize>())
            .sum::<usize>();
        println!("{}", before - after);
    }
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}



Measured memory_bytes: 5060
import heapq

n, m = map(int, input().split())
job_list = [[] for _ in range(m)]
for _ in range(n):
    k, v = map(int, input().split())
    if k-1 < m:
        job_list[k-1].append(-v)

q = []
ans = 0
for i in range(m):
    for push_item in job_list[i]:
        heapq.heappush(q, push_item)
    if len(q) > 0:
        ans += -heapq.heappop(q)
print(ans)


Measured memory_bytes: 17732
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i ,n) for(int i = 0 ; i < (n) ; i ++ )
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using vin=vector<int>;
using P = pair<int, int>;
const int inf=1e9+7;
const ll INF=1e18;

int main() {
  int n,m;
  cin>>n>>m;
  vin s(m),c(m);
  rep(i,m) cin>>s[i]>>c[i];
  bool ok=true;
  int ans=0;
  rep(i,m){
    if(n!=1&&s[i]==1&&c[i]==0) ok=false; 
  }
  ///////////
  map<int,int> mp;
  rep(i,m){
    
   if(mp.count(s[i])) {
    	if(mp[s[i]]!=c[i]){
     	  ok=false;
     	}
    
     
   }
   else{
    mp[s[i]]=c[i]; 
     ans+=c[i]*pow(10,n-s[i]);
   }
    
    
  }//rep
  if(ok){
    if(mp[1]==0){
         if(n!=1){
           ans+=pow(10,n-1);
         }
      else ans=0;
    }
    cout<<ans<<endl;
  }
  else cout<<-1<<endl;
}





Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MOD = 1e9 + 7;
const ll INF = LLONG_MAX;

int main()
{
    string s;
    cin >> s;
    ll ans = 0;
    ll cnt = 0;
    for (int i = 0; i < s.length(); i++)
    {
        if (s[i] == 'B')
            cnt++;
        else
            ans += cnt;
    }
    cout << ans << endl;
}


Measured memory_bytes: 640
#include<iostream>
#include<stdio.h>
using namespace std;

int n, A[50];

// 入力値のMから選んだ要素を引いていく再帰関数
int solve (int i, int m){
    if (m == 0) return 1;
    if (i >= n) return 0;
    int res = solve(i + 1, m) || solve(i + 1, m - A[i]);
    return res;
}

int main() {
   int q, M, i;

   scanf("%d", &n);
   for (i = 0; i < n; i++) scanf("%d", &A[i]);
   scanf("%d", &q);
   for (i = 0; i < q; i++){
       scanf("%d", &M);
       if (solve(0, M)) cout << "yes" << endl;
       else cout << "no" << endl;
   } 
   return 0;
}


Measured memory_bytes: 3156
/*#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>

#include <boost/rational.hpp>
*/
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
using ll = long long;
using ld = long double;
using pll = pair<ll,ll>;
#define rep2(i, s, n) for (ll i = (s); i < (ll)(n); i++)
#define rep3(i, n) for (ll i = 1; i < (ll)(n+1); i++)
#define rep4(i, s, n) for (ll i = (s); i < (ll)(n+1); i++)
#define repr(i,n) for (ll i = (n-1); i>=0;i--)
#define repr3(i,n) for(ll i = (n);i>0;i--)
#define repr4(i,s,n) for(ll i = (n);i>=(s);i--)
#define stlen(s) ll s.size()-1
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()
#define cout(n) cout<<std::fixed<<std::setprecision(n)
using Graph = vector<vector<int>>;
using Graphw = vector<vector<pair<ll,ll>>>;
#define INF1  INT_MAX;
#define INF2  LLONG_MAX;
#define PI  3.14159265358979323846;
#define MOD 1000000007;
/*
namespace mp = boost::multiprecision;
// 任意長整数型
using Bint = mp::cpp_int;
// 仮数部長が32の浮動小数点数型
using Real32 = mp::number<mp::cpp_dec_float<32>>;
// 仮数部長が1024の浮動小数点数型
using Real1024 = mp::number<mp::cpp_dec_float<1024>>;
// 有理数型
using Rat = boost::rational<Bint>;
*/
const int mod = 1000000007;



int main(){
int N;
cin>>N;
ll A[N];
rep(i,N)cin>>A[i];
ll s=0,a=0;
s=A[0];
rep3(i,N-1){
a+=A[i];
}
ll min_=abs(s-a);
rep3(i,N-2){
    s+=A[i];
    a-=A[i];
    min_=min(min_,abs(s-a));
}
cout<<min_<<endl;
return 0;
}

Measured memory_bytes: 5076
fun main(args: Array<String>) {
    val line = readLine()
    val nums = line!!.split(" ").map { it.toInt() }
    val ans = solve(nums)
    print(ans)
}

fun solve(nums: List<Int>): Int {
    val tapNum = nums[0]
    val needNum = nums[1]
    
    val integral = (needNum - 1) / (tapNum - 1)
    val remaining = (needNum - 1) % (tapNum - 1) == 0

    return if (remaining) {
        integral
    } else {
        integral + 1
    }
}



Measured memory_bytes: 37872
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define ULL unsigned long long
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define pll pair<LL,LL>
#define x first
#define y second
#define pi acos(-1)
#define sqr(x) ((x)*(x))
#define pdd pair<double,double>
#define MEMS(x) memset(x,-1,sizeof(x))
#define MEM(x) memset(x,0,sizeof(x))
#define less Less
#define EPS 1e-4
#define arg ARG
#define cpdd const pdd
#define rank Rank
#define KK 500
#define MXN 200005
vector<pii> v[200005];
int dep[200005];
void dfs(int x,int f){
    for(auto &it:v[x]){
        if(it.y!=f){
            dfs(it.y,x);
            it.x=dep[it.y]+1;
           // printf("%d %d %d\n",x,it.y,it.x);
        }
    }
    sort(v[x].begin(),v[x].end());
    reverse(v[x].begin(),v[x].end());
    if(f!=0&&v[x].size()==1);
    else
    dep[x]=v[x][0].x;
}
void dfs2(int x,int f,int sum){
    for(auto it:v[x]){
        if(it.y!=f){
            if(it.x==v[x][0].x){
                if(v[x].size()==1){
                    dfs2(it.y,x,sum+1);
                }
                else{
                    dfs2(it.y,x,max(v[x][1].x,sum)+1);
                }
            }
            else{
                dfs2(it.y,x,max(v[x][0].x,sum)+1);
            }
        }
    }
    if(f!=0){
        v[x].back().x=sum;
    }
}
int val[200005];
int l[200005];
int d[200005];
int main(){
    int n;
    scanf("%d",&n);
    for(int i = 1;i<n;i++){
        int x,y;
        scanf("%d %d",&x,&y);
        v[x].pb(mp(-1,y));
        v[y].pb(mp(-1,x));
        d[x]++;
        d[y]++;
    }
    dfs(1,0);
    dfs2(1,0,0);
    LL ans=0;
    for(int i = 1;i<=n;i++){
        sort(v[i].begin(),v[i].end());
        reverse(v[i].begin(),v[i].end());
      //  for(auto it:v[i])
      //  printf("%d ",it.x);
      //  printf("\n");
        if(v[i].size()==1){
       //     ans+=2;
            val[i]=2;
            v[i].pb(mp(0,0));
            if(v[i][0].x==1)val[i]--;
            
        }
        else{
         //   ans+=v[i][1].x+2;
            val[i]=v[i][1].x+2;
            if(v[i][1].x==v[i][0].x)val[i]-=2;
            if(v[i][1].x==v[i][0].x-1)val[i]--;
        }
     //   printf("%d %lld\n",i,ans);
    }
    char c[200005];
    scanf("%s",c+1);
    queue<int> q;
    for(int i = 1;i<=n;i++){
        if(c[i]=='1'){
            q.push(i);
            l[i]=0;
        }
        else{
            l[i]=1e9;
        }
        d[i]--;
        val[i]--;
        if(d[i]==0)q.push(i);

    }
    while(!q.empty()){
        int x=q.front();
        q.pop();
        if(v[v[x][0].y][0].y==x){
 
        }
        else{
            if(--d[v[x][0].y]==0){
                q.push(v[x][0].y);
            }
        }
       /* if(c[x]=='1'){
            l[v[x][0].y]=min(l[v[x][0].y],v[x][1].x+1);
        }
        else{*/
            if(val[x]>=l[x])
            l[v[x][0].y]=min(l[v[x][0].y],v[x][1].x+1);
        //}
    }
    for(int i = 1;i<=n;i++){
        //printf("%d %d %d\n",val[i],l[i],ans);
        if(val[i]>=l[i])
        {   
           // printf("%d %d %d\n",i,val[i],l[i]);
            ans+=val[i]-l[i]+1;
        }
    }
    printf("%lld\n",ans+1);
}

Measured memory_bytes: 27264
#include <bits/stdc++.h>
#define ll long long int
#define ld long double
#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define mk make_pair
#define mt make_tuple
#define MOD 1000000007
#define fo(i,a,b) for(i=a;i<b;i++)
#define foe(i,a,b) for(i=a;i<=b;i++)
#define all(x) x.begin(), x.end()
#define vi vector<int>
#define vl vector <long long int>
#define pii pair <int,int>
#define pll pair <long long int, long long int>
#define vpii vector< pair<int,int> >
#define vpll vector < pair <long long int,long long int> >
#define boost ios::sync_with_stdio(false); cin.tie(0)
using namespace std;
const int inf = 1e9 + 5;
const ll inf64 = 1e18 + 5;

map <string, bool> mp;
const int N = 10;
vector <ll> v;
ll to_num(string s)
{
	ll res = 0;
	for(int i = 0; i < s.size(); i++) {
		res *= 10;
		int x = s[i] - '0';
		res += x;
	}
	return res;
}
void rec(string s)
{
	if(s.size() > N || mp[s])
	return;
	
	mp[s] = true;
	if(s.size() > 0)
	v.pb(to_num(s));
	
	if(s.size() == 0) {
		for(int i = 1; i < 10; i++) {
			s += char(i + '0');
			rec(s);
			s.pop_back();
		}
	}
	else {
		int x = s.back() - '0';
		for(int i = max(0, x - 1); i <= min(9, x + 1); i++) {
			s += char(i + '0');
			rec(s);
			s.pop_back();
		}
	}
}
int main()
{
	boost;
	rec("");
	sort(all(v));
	int k;
	cin >> k;
	cout << v[k - 1] << '\n';
}


Measured memory_bytes: 26352
#include<bits/stdc++.h>
using namespace std;

#define rep(i,n) for(ll i = 0; i < n; i++)
#define per(i,n) for(ll i = n-1; i >= 0; i--)
#define REP(i,n) for(ll i = 1; i < n; i++)
#define PER(i,n) for(ll i = n; i >= 1; i--)
#define sz(x) int(x.size())
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define YesorNo(a) printf(a ? "Yes\n" : "No\n")
#define endl '\n'
#define fi first
#define se second
using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
using vi = vector<int>;
using vii = vector<vi>;
using vl = vector<ll>;
using vll = vector<vl>;
using vs = vector<string>;
using vb = vector<bool>;
using vc = vector<char>;
using vcc = vector<vc>;
using vP = vector<P>;
using vPP = vector<vP>;
using vPl = vector<Pl>;
const int dx[] = {0,1,0,-1,1,1,-1,-1};
const int dy[] = {1,0,-1,0,1,-1,-1,1};
const int inf = (1<<30)-1;
const ll infll = (1LL<<62)-1;
ll ceil(const ll &a, const ll &b){return ((a)+(b)-1)/b;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }



int main(){
  int d;
  cin >> d;
  int k = 26;
  vP c(k);
  rep(i,k) {
    int v;
    cin >> v;
    c[i] = make_pair(v,i);
  }
  sort(rall(c));
  vii s(d,vi(k));
  rep(i,d)rep(j,k) cin >> s[i][j];
  rep(i,d) {
    int day = (c[i%k].se) + 1;
    cout << day << endl;
  }
}

Measured memory_bytes: 3680
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
typedef long long lint;
#define rep(i,n) for(lint (i)=0;(i)<(n);(i)++)
#define repp(i,m,n) for(lint (i)=(m);(i)<(n);(i)++)
#define repm(i,n) for(lint (i)=(n-1);(i)>=0;(i)--)
#define INF (1ll<<60)
#define all(x) (x).begin(),(x).end()
const lint MOD =1000000007;
const lint MAX = 1000000;
using Graph =vector<vector<lint>>;
typedef pair<lint,lint> P;
typedef map<lint,lint> M;
 
lint fac[MAX], finv[MAX], inv[MAX];
 
void COMinit() 
{
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (lint i = 2; i < MAX; i++)
    {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
 
long long COM(lint n, lint k)
{
    if (n < k)
        return 0;
    if (n < 0 || k < 0)
        return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
 
lint primary(lint num)
{
    if (num < 2) return 0;
    else if (num == 2) return 1;
    else if (num % 2 == 0) return 0;
 
    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            return 0;
        }
    }
 
    return 1;
}
   long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
    lint lcm(lint a,lint b){
        return a/__gcd(a,b)*b;
    }
     lint gcd(lint a,lint b){
        return __gcd(a,b);
    } 
    lint x[510][510];
  int main(){
      lint n,m,q;
      cin>>n>>m>>q;
      rep(i,m){
          lint l,r;
          cin>>l>>r;
          x[l][r]++;
      }
      rep(i,n)rep(j,n)x[i+2][j+1]+=x[i+1][j+1];
      rep(i,n)rep(j,n)x[i+1][j+2]+=x[i+1][j+1];
      rep(i,q){
          lint l,r;
          cin>>l>>r;
          cout<<x[r][r]+x[l-1][l-1]-x[r][l-1]-x[l-1][r]<<endl;
      }
    }
      
    
  

Measured memory_bytes: 5664
#include<bits/stdc++.h>
using namespace std;
int main(){
    int c[3][3];
    int sum=0;
    for(int i=0;i<3;i++)for(int j=0;j<3;j++){
        cin >> c[i][j];
        sum += c[i][j];
    }
    if(sum==3*(c[0][0]+c[1][1]+c[2][2]))cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N,K = inputMap()
	A = inputList()

	if N <= 2*K:
		T = [N for i in range(N)]
		print(*T)
		sys.exit()

	for j in range(K):
		T = [0 for i in range(N)]
		for i,val in enumerate(A):
			#print(T)
			tmp_min = max(0,i-val)
			T[tmp_min] += 1

			if i+val+1 > N-1:
				continue
			tmp_max = min(N-1,i+val+1)
			T[tmp_max] -= 1

		for i,val in enumerate(T):
			if i == 0:
				continue
			T[i] += T[i-1]
		A = T

	print(*A)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()


Measured memory_bytes: 168220
// B - Great Ocean View
#include <bits/stdc++.h>
using namespace std;

int main(){
	int n; cin>>n;
	int ans = 0;
	int maxi = 1;
	for(int i=0; i<n; ++i){
		int h; cin>>h;
		if(maxi<=h){
			maxi = h;
			++ans;
		}
	}
	cout<< ans <<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;

typedef long long int ll;

int main(){
	int n, k;cin >> n >> k;
	vector<int> v(n);
	for(int i = 0;i < n;i++)cin >> v[i];
	sort(v.begin(), v.end());
	int ans = INT_MAX;
	for(int i = 0;i < n - k + 1;i++){
		ans = min(v[i + k - 1] - v[i], ans);
	}
	cout << ans;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
#define int long long
#define pb push_back
#define endl "\n";
#define deb1(x) cout << #x << ": " << x << endl
#define deb2(x, y) cout << #x << ": " << x << " | " << #y << ": " << y << endl
#define fast                      \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
#define printclock cerr << "Time : " << 1000 * (ld)clock() / (ld)CLOCKS_PER_SEC << "ms\n";
#define vii vector<int>
#define pii pair<int, int>
#define prec(n) fixed << setprecision(n)
#define mp make_pair
#define all(a) a.begin(), a.end()
#define rep(i, a, n) for (int i = (a); i < (n); ++i)
#define MOD LLONG_MAX
inline void get(vector<int> &arr, int n)
{
    int a;
    for (int i = 0; i < n; i++)
    {
        cin >> a;
        arr.push_back(a);
    }
}
inline void print(vector<int> &arr, int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}
int dp[100005];
void solve(vii &h, int K, int n)
{
    rep(i, 2, n + 1)
    {
        rep(jump, 1, K + 1)
        {
            if (i - jump >= 1)
            {
                dp[i] = min(dp[i], dp[i - jump] + abs(h[i - jump] - h[i]));
            }
        }
    }
}
int32_t main()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
    fast;
    //check if cin >> n
    //---------------------------------
    int t;
    t = 1;
    while (t--)
    {
        int n, k;
        cin >> n >> k;
        vii h(n + 1);
        rep(i, 1, n + 1)
        {
            cin >> h[i];
        }
        memset(dp, 100, sizeof(dp));
        dp[1] = 0;
        solve(h, k, n);
        cout << dp[n] << endl;
    }
    return 0;
}

Measured memory_bytes: 4792
#include <bits/stdc++.h>

int main() {
    using namespace std;
    constexpr unsigned long max_size = 10000;
    unsigned long N, M;
    cin >> N >> M;
    bitset<max_size> A, B, mask;
    for(unsigned long i = 0; i < N; ++i){
        string s;
        cin >> s;
        for(unsigned long j = 0; j < N; ++j)A[i * 100 + j] = s[j] == '#';
    }
    for(unsigned long i = 0; i < M; ++i){
        string s;
        cin >> s;
        for(unsigned long j = 0; j < M; ++j){
            mask[i * 100 + j] = true;
            B[i * 100 + j] = s[j] == '#';
        }
    }
    for(unsigned long i = 0; i < 100 * N; ++i)if((A >> i & mask) == B)return 0 & puts("Yes");
    puts("No");
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

int memo[100200], n, k, h[1000200];

int dp(int pos) {
    if (pos > n - 1) return 1 << 30;
    if (pos == n - 1) return 0;
    if (memo[pos] != -1) return memo[pos];
    int res = 1 << 30;
    for(int K = 1; K <= k; K++) {
        res = min(res, abs((h[pos + K] - h[pos])) + dp(pos + K));
    }
    return memo[pos] = res;
}
int main() {
    cin >> n >> k;
    memset(memo, -1, sizeof(memo));
    for(int i = 0; i < n; i++) cin >> h[i];
    cout << dp(0) << "\n";
    return 0;
}

Measured memory_bytes: 7552
import java.util.Scanner;

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
	int N =  sc.nextInt();
	int M =  sc.nextInt();
	int[] z = new int[N];

	for (int i = 0; i < M; i++){
        int s = sc.nextInt();
        int c = sc.nextInt();
        if ((z[s-1] != 0 && z[s-1] != c) || (N >= 2 && s == 1 && c == 0)){
            System.out.println(-1);
            return;
        }
        z[s-1] = c;
	}
	if (N >= 2 && z[0] == 0){
        z[0] = 1;
    }
	for (int i = 0; i < z.length; i++){
        System.out.print(z[i]);
    }
  }
}

Measured memory_bytes: 23124
def find_numbers(grid):
    for a1 in range(0, 101):
        for a2 in range(0, 101):
            if (grid[0] + grid[3] + grid[6]) - 3 * a1 == (grid[1] + grid[4] + grid[7]) - 3 * a2:
                for a3 in range(0, 101):
                    if (grid[0] + grid[3] + grid[6]) - 3 * a1 == (grid[2] + grid[5] + grid[8]) - 3 * a3:
                        return True
    return False


grid = []
for _ in range(3):
    grid.extend(list(map(int, input().split())))

print("Yes" if find_numbers(grid) else "No")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;

using int32 = int_fast32_t;
using int64 = int_fast64_t;

const int32 INF = 1e9;
const int32 MOD = 1e9+7;
const int64 LLINF = 1e18;

#define YES(n) cout << ((n) ? "YES\n" : "NO\n"  )
#define Yes(n) cout << ((n) ? "Yes\n" : "No\n"  )
#define ANS(n) cout << (n) << "\n"
#define REP(i,n) for(int64 i=0;i<(n);++i)
#define FOR(i,a,b) for(int64 i=(a);i<(b);i++)
#define FORR(i,a,b) for(int64 i=(a);i>=(b);i--)
#define ALL(obj) (obj).begin(),(obj).end()
#define pii pair<int32,int32>
#define pll pair<int64,int64>
#define pb(a) push_back(a)
#define mp make_pair

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int32 h,w;
    cin >> h >> w;
    vector<vector<int32>> ans(h, vector<int32>(w, -1));
    int32 x = 0;
    int32 y = 0;
    int32 n;
    cin >> n;
    FOR(i,1,n+1){
        int32 a;
        cin >> a;
        REP(j,a){
            ans[x][y] = i;
            if(x % 2 == 0){
                if(y == w - 1){
                    x++;
                }else{
                    y++;
                }
            }else{
                if(y == 0){
                    x++;
                }else{
                    y--;
                }
            }
        }
    }
    REP(i,h){
        REP(j,w){
            cout << ans[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

Measured memory_bytes: 384
import java.util.Scanner;
import java.util.Stack;
import java.util.LinkedList;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int h, w, x, y, count, xx=0;
        int[] movex = {1,-1,0,0,1,-1,1,-1}, movey = {0,0,1,-1,1,-1,-1,1};
        while(true){
            count = 0;
            w = sc.nextInt();
            h = sc.nextInt();
            if(w == 0 && h==0) break;
            int[][] search = new int[h+2][w+2];
            int[][] c = new int[h+2][w+2];
            for(int i=1;i<=h;i++){
                for(int j=1;j<=w;j++){
                    c[i][j] = sc.nextInt();
                }
            }
            int tmp = 0;
            Stack<Integer> map = new Stack<Integer>();
            do{
                outer:
                for(int i=1;i<=h;i++){
                    for(int j=1;j<=w;j++){
                        tmp = count;
                        if(search[i][j] == 0 && c[i][j] == 1){
                            if(map.empty()){
                                int n = i*100+j;
                                map.push(n);
                                search[i][j] = 1;
                                count++;
                                break outer;
                            }
                        }
                    }
                }
                while(!map.empty()){
                    int n = map.pop();
                    x = n/100;
                    y = n%100;
                    for(int i=0;i<8;i++){
                        if(c[x+movex[i]][y+movey[i]] == 1 && search[x+movex[i]][y+movey[i]] == 0){
                            map.push((x+movex[i])*100+(y+movey[i]));
                            search[x+movex[i]][y+movey[i]] = 1;
                        }
                    }
                }
                if(count==tmp) break;
            }while(xx<=h*w);
            System.out.println(count);
        }
    }
}


Measured memory_bytes: 50432
#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;

    vector<int> A(N);
    for(int i = 0; i < N; i++){
        cin >> A.at(i);
    }

    sort(A.begin(), A.end());
    reverse(A.begin(), A.end());

    int alice = 0, bob = 0;
    for(int i = 0; i < N; i++){
        if(i % 2 == 0) alice += A.at(i);
        else bob += A.at(i);
    }

    cout << alice - bob << endl;

}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        sc.nextLine();
        String s = sc.nextLine();
        sc.close();
        System.out.println(s.substring(0, k - 1) + Character.toLowerCase(s.charAt(k - 1)) + s.substring(k, n));
    }
}


Measured memory_bytes: 20948
def main():
    n, k = [int(e) for e in input().split()]
    P = [int(e) for e in input().split()]
    C = [int(e) for e in input().split()]

    A = []
    for i in range(1, n + 1):
        score = 0
        max_score = -(10 ** 18)
        move_count = 0
        di = i
        S = set()
        while True:
            di = P[di - 1]
            if di in S or move_count == k:
                break

            score += C[di - 1]
            if max_score < score:
                max_score = score

            move_count += 1
            S.add(di)

        if score > 0 and move_count < k:
            re = None
            if k % move_count != 0:
                re = k % move_count
                score = score * (k // move_count)
            else:
                re = move_count
                score = score * (k // move_count - 1)

            max_score = score
            di = i
            for si in range(re):
                di = P[di - 1]
                score += C[di - 1]
                if max_score < score:
                    max_score = score

        A.append(max_score)

    print(max(A))


if __name__ == '__main__':
    main()


Measured memory_bytes: 126916
from math import ceil
N,H=map(int,input().split())
A,B=[],[]
for i in range(N):
    a,b=map(int,input().split())
    A.append(a);B.append(b)
B.sort(reverse=True)
sw=max(A)
cnt=0
dam=0
for i in range(N):
    if B[i]<sw:
        break
    cnt+=1
    dam+=B[i]
    if dam>=H:
        print(cnt)
        exit()
cnt+=ceil((H-dam)/sw)
print(cnt)

Measured memory_bytes: 11296
using System;
using System.Collections.Generic;
using System.Configuration;
using System.Linq;
using System.Web;

namespace Competitive
{
    internal class Solution
    {
        public int N;
        public void Run()
        {
            int all, right, sharp, obtuse;
            all = 0;
            right = 0;
            sharp = 0;
            obtuse = 0;

            string line;
            while ((line = Console.ReadLine()) != null)
            {
                var values = line.Split(' ').Select(s => int.Parse(s)).ToArray();
                Array.Sort(values);

                if (values[2] >= values[1] + values[0])
                {
                    Console.WriteLine("{0} {1} {2} {3}", all, right, sharp, obtuse);
                    return;
                }

                all++;
                int a = values[2] * values[2] - values[1] * values[1] - values[0] * values[0];
                if (a == 0) right++;
                if (a > 0) obtuse++;
                if (a < 0) sharp++;
            }
        }
    }

    // libs ----------
    

    // common ----------

    internal static class Input
    {
        public static string ReadString()
        {
            string line = Console.ReadLine();
            return line;
        }

        public static int ReadInt()
        {
            string line = Console.ReadLine();
            return int.Parse(line);
        }

        public static int[] ReadIntArray()
        {
            string line = Console.ReadLine();
            return line.Split(' ').Select(int.Parse).ToArray();            
        }

        public static long ReadLong()
        {
            string line = Console.ReadLine();
            return long.Parse(line);
        }

        public static long[] ReadLongArray()
        {
            string line = Console.ReadLine();
            return line.Split(' ').Select(long.Parse).ToArray();
        }

        public static double[] ReadDoubleArray()
        {
            string line = Console.ReadLine();
            return line.Split(' ').Select(double.Parse).ToArray();
        }
    }
    
    internal class Program
    {
        public static void Main(string[] args)
        {
            var s = new Solution();
            s.Run();
        }
    }
}


Measured memory_bytes: 16380
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main(void){
    int n,k,count=0;
    scanf("%d%d",&n,&k);
    long long a[n],b[n*(n+1)/2],ans=0,max=0;
    for (int i=0; i<n; i++){
        scanf("%lld",&a[i]);
    }
    for (int i=0; i<n; i++){
        long long sum=0;
        for (int j=i; j<n; j++){
            sum+=a[j];
            b[count]=sum;
            if (b[count]>max){
                max=b[count];
            }
            count++;
        }
    }
    
    int count2=0,p=0;
    for (p=0; pow(2,p)<max; p++){
    }
    p--;
    
    for (int i=p; i>=0; i--){
        count2=0;
        for (int j=0; j<count; j++){
            if (b[j]>=pow(2,i)){
                count2++;
            }
        }
        if (count2>=k){
            ans+=pow(2,i);
            for (int j=0; j<count; j++){
                if (b[j]<pow(2,i)){
                    b[j]=0;
                } else {
                    b[j]-=pow(2,i);
                }
            }
        } else {
            for (int j=0; j<count; j++){
                if (b[j]<pow(2,i)){
                } else {
                    b[j]-=pow(2,i);
                }
            }
        }
    }
    printf("%lld\n",ans);
    return 0;
}

Measured memory_bytes: 4096
function gets(str){
  this._s = str.split("\n");
  this._y = 0;
};
gets.prototype = {
  a: function(f){
    var s = this._s, y = this._y, r;
    if(typeof s[y] === "string")s[y] = s[y].split(" ").reverse();
    r = s[y].pop();
    if(!s[y].length)this._y++;
    return f?r:+r;
  },
  l: function(f){
    var s = this._s[this._y++].split(" ");
    return f?s:s.map(a=>+a);
  },
  m: function(n,f){
    var s = this._s, y = this._y, r = [], i = 0;
    if(f)for(;i < n; i++)r[i] = s[y+i].split(" ");
    else for(;i < n; i++)r[i] = s[y+i].split(" ").map(a=>+a);
    this._y += n;
    return r;
  },
};
var o=new gets(require("fs").readFileSync("/dev/stdin","utf8"));

console.log(main());
function main(){
  var x = o.a();
  var y = o.a();
  return x + y / 2;
}

Measured memory_bytes: 21192
from math import factorial
def comb (x,y):
	return factorial(x)//factorial(x-y)//factorial(y)

w,h,ax,ay,bx,by=map(int,input().split())
dx=abs(ax-bx)
dx=min(dx,w-dx)
dy=abs(ay-by)
dy=min(dy,h-dy)
ans=1
if dx*2==w:ans*=2
if dy*2==h:ans*=2
ans*=comb(dx+dy,dx)
print(ans%100000007)

Measured memory_bytes: 7780
#define a(x,y) a[x][y]++
a[99][99],x,y,z,i;main(){for(;~scanf("%d,%d,%d",&x,&y,&z);){x+=10;y+=10;a(x,y);a(x-1,y);a(x,y-1);a(x+1,y);a(x,y+1);if(z>1)a(x+1,y+1),a(x+1,y-1),a(x-1,y+1),a(x-1,y-1);if(z>2)a(x-2,y),a(x+2,y),a(x,y-2),a(x,y+2);}for(z=0,x=9;x++<19;)for(y=9;y++<19;){!a[x][y]&&z++;if(a[x][y]>i)i=a[x][y];}printf("%d\n%d\n",z,i);exit(0);}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define ll long long
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
ll int gcd (ll int a,ll int b) { return b ? gcd (b, a % b) : a; }

int main()
{
	int n;
	cin>>n;
	int a[n],b[n],c[n];
	for (int i = 0; i < n; ++i)
		cin>>a[i]>>b[i]>>c[i];
	
	int dp[n][3];
	dp[0][0]=a[0];
	dp[0][1]=b[0];
	dp[0][2]=c[0];
	for(int i=1;i<n;i++)
	{
		dp[i][0]=a[i]+max(dp[i-1][1],dp[i-1][2]);
		dp[i][1]=b[i]+max(dp[i-1][0],dp[i-1][2]);
		dp[i][2]=c[i]+max(dp[i-1][1],dp[i-1][0]);
		//cout<<dp[i][0]<<" "<<dp[i][1]<<" "<<dp[i][2]<<"\n";
	}
	cout<<max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2]))<<"\n";
}


Measured memory_bytes: 5832
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
typedef long long int ll;
typedef pair<ll,ll> P;
typedef vector<ll> VI;
typedef vector<VI> VVI;
const ll MOD = 1000000007;
const ll INF = 1e18;
#define REP(i,n) for(int i=0;i<n;i++)
#define ALL(v) v.begin(),v.end()

int main(){
	int n, q; cin >> n >> q;
	fenwick_tree<ll> fw(n);
	int a;
	REP(i,n){
		cin >> a;
		fw.add(i,a);
	}
	while(q--){
		int t, x, y;
		cin >> t >> x >> y;
		if(t==0)
			fw.add(x,y);
		else
			cout << fw.sum(x,y) << endl;
	}
	return 0;
}

Measured memory_bytes: 8204
#include <bits/stdc++.h>
using namespace std;

int main()
{
    string T;
    cin >> T;
    /*for (int i = 1; i < T.size(); i++)
    {

        if (i + 1 < T.size())
        {

            if (T.at(i + 1) == 'D' && T.at(i) == '?')
            {
                T.at(i) = 'P';
            }
        }
        else if (T.at(i) == '?')
        {
            T.at(i) = 'D';
        }
    }*/
    for (int i = 0; i < T.size(); i++)
    {
        if (T.at(i) == '?')
        {
            T.at(i) = 'D';
        }
    }
    cout << T << endl;
}


Measured memory_bytes: 3756
#include <bits/stdc++.h>
using namespace std;

using int32 = int_fast32_t;
using int64 = int_fast64_t;

const int32 INF = 1e9;
const int32 MOD = 1e9+7;
const int64 LLINF = 1e18;

#define YES(n) cout << ((n) ? "YES\n" : "NO\n"  )
#define Yes(n) cout << ((n) ? "Yes\n" : "No\n"  )
#define ANS(n) cout << (n) << "\n"
#define REP(i,n) for(int64 i=0;i<(n);++i)
#define FOR(i,a,b) for(int64 i=(a);i<(b);i++)
#define FORR(i,a,b) for(int64 i=(a);i>=(b);i--)
#define ALL(obj) (obj).begin(),(obj).end()
#define pii pair<int32,int32>
#define pll pair<int64,int64>
#define pb(a) push_back(a)
#define mp make_pair

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int32 n;
    cin >> n;
    vector<pii> tasks(n);
    REP(i,n){
        int32 a,b;
        cin >> a >> b;
        tasks[i] = mp(b,a);
    }
    sort(ALL(tasks));
    int64 curTime = 0;
    REP(i,n){
        int32 a,b;
        tie(b,a) = tasks[i];
        curTime += a;
        if(b < curTime){
            Yes(false);
            return 0;
        }
    }
    Yes(true);
    return 0;
}

Measured memory_bytes: 3328
#include <bits/stdc++.h> 
using namespace std;
typedef long long ll; const ll MM = 1000000000;ll mod = MM + 7;
#define rep(i, n) for(ll i=0; i<n; i++)
#define Rep(i, j, n) for(ll i=j; i<n; i++)
#define all(vec) vec.begin(), vec.end()
template<class T> inline bool chmin(T& a, T b) {if(a > b) {a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) {if(a < b) {a = b; return true;} return false;}
const ll INF = 1LL << 60;

int main() {
    char n; cin >> n;
    int a = n - '0' + '1';
    cout << char(a) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long
#define rep(i,a,b) for(int i=a;i<b;i++)
#define mp make_pair
#define pb push_back
int mod;
int power(int a,int b) {int res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
int32_t main()
{
	IOS;
	int n,m;
	cin>>n>>m;
	cout<<n*(n-1)/2 + m*(m-1)/2;

	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <set>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <bits/stdc++.h>

using namespace std;


int main() {

    int n, a[100001], first = -1;
    scanf("%d", &n);
    
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        if (a[i] > first)
            first = a[i];
    }
    sort(a, a+n);
    
    int ans, value = first;
    for (int i = 0; i < n; i++) {
        if (value > abs(first/2.0-a[i])) {
            value = abs(first/2.0-a[i]);
            ans = i;
        }
    }
    printf("%d %d\n", first, a[ans]);
    
    return 0;
}



Measured memory_bytes: 640
#include <bits/stdc++.h>
#define REP(i, a, b) for (int i = (a); i < (b); ++i)

using namespace std;
using ll = long long;

/**
 * main
 */
int main () {
  vector<int> v = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
  int K; cin >> K;
  cout << v[K - 1] << endl;
}


Measured memory_bytes: 256
n,x,m=map(int,input().split())

used=[0]*m
used[x]=1
cnt=1
y=x
while True:
    y=y**2
    y%=m
    cnt+=1

    if used[y]>0:
        loopst=used[y]
        loopend=cnt-1
        break
    
    used[y]=cnt

ans=0
loopsum=0
beforesum=0
for i in range(m):
    if loopst<=used[i]<=loopend:
        loopsum+=i
    if 0<used[i]<loopst:
        beforesum+=i

if n>loopend:
    n-=loopst-1
    ans+=beforesum
    ans+=n//(loopend-loopst+1)*loopsum
    n%=(loopend-loopst+1)
    
    for i in range(m):
        if used[i]==loopst:
            x=i
            break

for i in range(n):
    ans+=x
    x=x**2
    x%=m

print(ans)


Measured memory_bytes: 68700
#include <bits/stdc++.h>
#define REP(i, n) for(long long i=0; i<n; i++)
#define REPR(i, n) for(long long i=n-1; i>=0; i--)
#define FOR(i, m, n) for(long long i=m; i<=n; i++)
#define FORR(i, m, n) for(long long i=m; i>=n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define VSORTR(v) sort(v.rbegin(), v.rend());
#define ALL(v) (v).begin(),(v).end()
#define FIN ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

using namespace std;
using ll = long long;
using ull = unsigned long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;
const ll mod = 1e9+7;
const ll inf = 1e15;
ll power(ll a,ll b){return b?power(a*a%mod,b/2)*(b%2?a:1)%mod:1;}


int main(){FIN
    ll n;cin>>n;
    map<ll,ll> mp;
    REP(i,n) {
        ll a; cin>>a;
        mp[a]++;
    }
    ll ans=0;
    for(auto p:mp){
        if (p.second>=p.first) ans += p.second-p.first;
        else ans += p.second;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 9516
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1<<16;

class RSQ2{
public:
  ll n,dat[2*MAX_N-1],td[2*MAX_N-1];
  //?????????
  RSQ2(){n=MAX_N,memset(dat,0,sizeof(dat)),memset(td,0,sizeof(td));};
  
  //[a,b)????????????x???????????????,query(a,b,x);
  ll add(int a,int b,ll x,int k=0,int l=0,int r=-1){
    if(r==-1) r=n;
    if(r<=a||b<=l)return 0;
    if(a<=l&&r<=b){
      dat[k]+=(r-l)*x; 
      td[k]+=x;
      return dat[k];
    }

    dat[k]+=(min(r,b)-max(l,a))*x;
    ll kl=k*2+1,kr=k*2+2,t=td[k]*(r-l)/2;
    dat[kl]+=t, dat[kr]+=t;
    td[kl]+=td[k], td[kr]+=td[k];
    td[k]=0;

    ll vl=add(a,b,x,k*2+1,l,(l+r)/2);
    ll vr=add(a,b,x,k*2+2,(l+r)/2,r);
    return vl+vr;
  }
  
  //[a,b)??????????????????
  ll sum(int a,int b){return a>=b? 0:add(a,b,0);}
};


struct data{int l,r;};
struct P{int x,y;};
const int Base=30000;

int main(){
  int n;
  while(cin>>n,n){
    vector<vector<data> > LR(MAX_N);
    vector<P> A(n);
    for(int i=0;i<n;i++)cin>>A[i].x>>A[i].y,A[i].x+=Base,A[i].y+=Base;
    for(int i=0;i<n;i++)
      if(A[i].y==A[(i+1)%n].y)
	LR[A[i].y].push_back((data){A[i].x,A[(i+1)%n].x});
    
    map <int,data> C;
    A.resize(4);
    for(int i=0;i<4;i++)cin>>A[i].x>>A[i].y,A[i].x+=Base,A[i].y+=Base;
    for(int i=0;i<4;i++)
      if(A[i].y==A[(i+1)%4].y)C[A[i].y]=(data){A[i].x,A[(i+1)%4].x};
    
    RSQ2 T;
    ll ans=0;
    for(int i=0,cl=0,cr=0;i<MAX_N;i++){
      if(C.count(i)&&!cl&&!cr) cl=C[i].l,cr=C[i].r;
      else if(C.count(i)) cl=cr=0;

      for(int j=0;j<LR[i].size();j++){
	int l = LR[i][j].l,r=LR[i][j].r;
	l<r ? T.add(l,r,1): T.add(r,l,-1);
      }
      ans+=T.sum(0,cl)+T.sum(cr,T.n);
    }
    cout <<ans<<endl;
  }


  return 0;
}

Measured memory_bytes: 6712
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }
template<class T> ostream& operator << (ostream& out,const vector<T> V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }
template<class T> ostream& operator << (ostream& out,const vector<vector<T> > Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }
template<class S,class T> ostream& operator << (ostream& out,const map<S,T> mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }

/*
 <url:>
 問題文============================================================
 =================================================================
 解説=============================================================
 ================================================================
 */

void A(){
    ll N,K; cin >> N >> K;
    vector<ll> A(N); for(auto& in:A) cin >> in;
    vector<ll> x(200001);
    set<ll> s;
    for(int i = 0; i < N;i++){
        x[A[i]]++;
        s.insert(A[i]);
    }
    sort(x.begin(),x.end());
    ll ans = 0;
    for(int i = 0; i <= 200000;i++){
        if(s.size() <= K) break;
        if(x[i] == 0) continue;
        ans += x[i];
        s.erase(*s.begin());
    }
    cout << ans << endl;
}
int main(void) {
    cin.tie(0); ios_base::sync_with_stdio(false);
    A();
    return 0;
}


Measured memory_bytes: 12800
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <unordered_map>
#include <utility>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <cstdio>
#include <math.h>
#include <stdio.h>
#include <deque>

using namespace std;

#define REP(i,n,m) for( long long int i = (n); i < (m); i++ )
#define REV(v) for (auto itr = v.rbegin(); itr != v.rend(); itr++)
#define ll long long
#define ALL(a) (a).begin(), (a).end()
#define SORT(v) sort( ALL(v) );
#define LAST(v) v[v.size()-1]
#define ZERO(a) memset(a,0,sizeof(a));
#define MINUS(a) memset(a,-1,sizeof(a));
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pi pair<int, int>
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define IIN(a) int a; cin >> a;
#define LIN(a) ll a; cin >> a;
#define SIN(a) string a; cin >> a;
#define VL(v,n) vector<ll> v(n);
#define Read_VL(v,n) vector<ll> v(n);REP(i,0,n)cin>>v[i];
#define sumV(v,n) Vl(acm,n) REP(i,0,n) acm[i] = v[i] + ( i == 0 ? 0 : acm[i - 1]);
#define EPS (1e-10)
#define INF 1000000000000LL

void YN(bool b){cout<<(b?"YES":"NO")<<"\n";}
void Yn(bool b){cout<<(b?"Yes":"No")<<"\n";}
void yn(bool b){cout<<(b?"yes":"no")<<"\n";}

template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}

template<class T>void puta(T&&t){cout<<t<<"\n";}
template<class H,class...T>void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}


template<class T=ll>struct Graph{
	int n;
	vector<vector<tuple<ll,T>>>edge;
	Graph(int N=1):n(N){edge.resize(n);}
	void add(ll f,ll t,T c,bool d=false){
		edge[f].emplace_back(t,c);
		if(!d)edge[t].emplace_back(f,c);
	}
	void view(){
		REP(i,0,n)for(auto&e:edge[i])
			puta(i,"=>",get<0>(e),", cost :",get<1>(e));
	}
};


bool length_cmp( string &a, string &b ){
  return a.size() < b.size();
}

ll StoLL( string s )
{
	ll num=0;
  REP( i, 0, s.size() ){
    num = num * 10 + ( s[i] ^ 48 );
  }
  return num;
}

ll CtoLL( char c )
{
	if( 'a' <= c && c <= 'z'){
		return (ll)( c ^ 96 ) ;
	}
	else if( 'A' <= c && c <= 'Z'){
		return (ll)( c ^ 64 );
	}
  return 0;
}

ll MOD=1000000007;
ll dx[4] = { 1, 0, -1, 0 };
ll dy[4] = { 0, 1, 0, -1 };
//I ASCII code: '0' = 48; 'A' = 65; 'a' = 97

ll gcd( ll a, ll b ){
  if( b == 0 )return a;
  return gcd(b,a%b);
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    LIN(n)
    LIN(x)
    Read_VL(a,n)
    REP(i,0,n){
      a[i] = abs( a[i] - x );
    }
    SORT(a)

    ll ans = a[0];
    if(n>1){
      REP( i, 1, n ){
        ans = fmin( ans, gcd(ans,a[i] ) );
      }
    }
    puta( ans );
    return 0;
}


Measured memory_bytes: 1024