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

#define ll long long
#define pb push_back
#define mp make_pair

void solve() {

    ll n;
    cin >> n;
    vector<char> v;
    while (n > 0) {
        ll a = (n-1) % 26;
        if(a==26)a = 0;
        v.pb('a' + a );
        if (n == 26)n = 0;
        else n = (n-1) / 26;
        //cout << a <<" " << n << endl;
    }



    ll x = v.size();
    for (ll i = x - 1; i >= 0; i--) {
        cout << v[i];
    }





}


int main()
{

    ios::sync_with_stdio(0);
    cin.tie(0);

    ll T;
    T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }




}


Measured memory_bytes: 3584
#include <iostream>
#include <math.h>
#include <algorithm>
#include <functional> 
#include <string>
#include <vector>

#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <utility>

using namespace std;

typedef long long LL;

#define dump(c) { for (auto it = c.begin(); it != c.end(); ++it) if (it == c.begin()) cout << *it; else cout << ' ' << *it; cout << endl; } 
#define rep(i,n) for (int i = 0; i < (n); ++i)

const int MOD = 1000000007;

template<typename T>
T gcd(T a, T b) 
{
    if (b < a) { //! make sure a <= b
        T tmp = b;
        b = a;
        a = tmp;
    }

    T r = b % a;
    while (r) {
        b = a;
        a = r;
        r = b % a;
    }

    return a;
}

//! return lcm of a and b
template<typename T>
T lcm(T a, T b) 
{
    return a * b / gcd<T>(a, b);
}

int main()
{
    LL A, B, C, D;
    cin >> A >> B >> C >> D;
    LL L = lcm(C, D);

    LL ans = (B - A +1) - ((B / C + B / D - B / L) - ((A-1) / C + (A-1) / D - (A-1) / L));

    cout << ans << endl;

    return 0;
}


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

#define int long long
#define double long double

using namespace std;

template<class T> string tostr(T x) { stringstream o; o << x; return o.str(); }
template<class T> T sqr(T x) { return x*x; }
template<class T> T mypow(T x, int n) { T r = 1; while (n > 0) { if (n & 1)r = r*x; x = x*x; n >>= 1; }return r; }

int toint(string s) { int v; stringstream i(s); i >> v; return v; }
bool check(int x, int y, int w, int h) { return x >= 0 && y >= 0 && w > x && h > y; }
int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }

#define REP(i,a,b)	for(int (i) = (a);i < (b);(i)++)
#define rep(i,n)	REP(i,0,n)
#define PER(i,a,b)	for(int (i) = (a-1);i >= (b);(i)--)
#define per(i,n)	PER(i,n,0)
#define each(i,n)	for(auto &i : n)
#define clr(a)		memset((a), 0 ,sizeof(a))
#define mclr(a)		memset((a), -1 ,sizeof(a))
#define all(a)		(a).begin(),(a).end()
#define dump(val) 	cerr << #val " = " << val << endl;
#define dum(val)	cerr << #val " = " << val;
#define FILL(a,v)	fill(a,a+sizeof(a)/sizeof(*a),v)

const int dx[8] = { +1,+0,-1,+0,+1,+1,-1,-1 };
const int dy[8] = { +0,-1,+0,+1,-1,+1,-1,+1 };
const int mod = 1e9 + 7;
const int INF = 1e9;

signed main() {

	int n, a, b;
	cin >> n >> a >> b;

	int mi = a * (n - 1) + b;
	int ma = a + b * (n - 1);

	int ans = max(0ll, ma - mi + 1);

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

 int main(void)
 {

 int a[10000], min, max, n, i;
 long long sum = 0;
 
scanf("%d", &n);


for(i = 0; i < n; i++)
{
 	scanf("%d", &a[i]);
 	sum = sum +  a[i];
 }
	 max = min = a[0];

for(i = 1; i < n; i++)
{
	if(a[i] > max)
	{
		max = a[i];
	}
 	
	if(a[i] < min)
	{
		min = a[i];
	}

 }
	
	 printf("%d %d %lld\n", min, max, sum);

 	
	return 0;

 }

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

#define ll long long
#define vi vector<long long>
#define r(i, a) for(int i=0; i<a; i++)
#define re(i, a, b) for(int i=a; i<b; i++)
#define inp(a,b) cin>>a>>b
#define in(a) cin>>t
#define pb push_back
#define mod 1000000007
#define ma unordered_map<long long>
#define se unordered_set<long long>


ll func(){
        
    ll a, b;
    cin>>a>>b;
    return a*b;
}


int main(){

ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
// sieve();
 
//int t;
//cin >> t;
//for(ll i=1; i<=t; i++)
//{

//    func();
cout<<func()<<endl;

//if(func())
//    cout<<"YES" << endl;
//else
//    cout <<"NO"<<endl; 
//cout<<"Case:"<<i<<" "<<     <<endl;
//}
return 0;
}




Measured memory_bytes: 3584
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;
 
int main() {
    ll x, y, z;
    cin >> x >> y >> z;
    out(x*y/2);
    re0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
typedef  long long ll;
ll gcd(ll x,ll y){
   if(y==0) return x;
   else return gcd(y,x%y);
}
ll lcm(ll x,ll y){
   return x/gcd(x,y)*y;
}
using namespace std;
int main(){ 
   int a[3][3];
   rep(i,3){
      rep(j,3){
         cin>>a[i][j];
      }
   }
   int n;
   cin>>n;
   rep(i,n){
      int n;
      cin>>n;
      rep(j,3){
         rep(k,3){
            if(a[j][k]==n) a[j][k]=0;
         }
      }
   }
   int count=0;
      int coun=0;
      int cou=0;
      int ans=0;
      int an=0;
      int anss=0;
   rep(i,3){
      
      if(a[i][0]==0) count++;
      if(a[i][1]==0) coun++;
      if(a[i][2]==0) cou++;
      if(a[0][i]==0) ans++;
      if(a[1][i]==0) an++;
      if(a[2][i]==0) anss++;
   }
   int nana,na;
   if(a[0][0]==0 && a[1][1]==0 && a[2][2]==0)  nana=0;
   else  nana=1;
   if(a[0][2]==0 && a[1][1]==0 && a[2][0]==0)  na=0;
   else  na=1;

   if(count==3 || coun==3 || cou==3 || ans==3 || an==3 || anss==3 ||nana==0 || na==0){
      cout<<"Yes";
   }
   else{
      cout<<"No";
   }


}

Measured memory_bytes: 256
# coding: utf-8
# Your code here!
import math
from collections import defaultdict
 
N = int(input())
 
memo = defaultdict(lambda: -1)
memo[0] = 0
def recursive(n):
    if memo[n] != -1:
        return memo[n]
    
    min_num_operation = n
    
    index = 0
    temp_n = n
    while temp_n > 0:
        if temp_n % 9 == 0:
            index += 1
            temp_n //= 9
        else:
            index += int(math.log(temp_n, 9))
            break
    if index > 0:
        min_num_operation = min(min_num_operation, 1 + recursive(int(n - math.pow(9, index))))
        
    index = 0
    temp_n = n
    while temp_n > 0:
        if temp_n % 6 == 0:
            index += 1
            temp_n //= 6
        else:
            index += int(math.log(temp_n, 6))
            break
    if index > 0:
        min_num_operation = min(min_num_operation, 1 + recursive(int(n - math.pow(6, index))))
        
    memo[n] = min_num_operation
    
    return min_num_operation
 
print(recursive(N))

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

using namespace std;
#define ff first
#define ss second
#define pb push_back
#define quicker ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
typedef long long ll;
 
int main()
{
    quicker
    ll a, b, c, k;
    cin >> a >> b >> c >> k;
    if (k <= a) cout << k;
    else if (k <= a + b) cout << a;
    else cout << (2 * a + b - k);
    return 0;
}


Measured memory_bytes: 3584
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<math.h>
#include<string>
#include <iomanip>
#include<deque>
#include<queue>
#include<stack>
#include<set>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef int itn;
const ll LINF = 1e18;
const int INF = 1e9;

//マクロ定義
#define vvint(vec,n,m,l) vector<vector<int>> vec(n, vector<int>(m,l));	// lで初期化
#define vvll(vec,n,m,l) vector<vector<ll>> vec(n,vector<ll>(m,l));
#define vint vector<int>
#define pint pair<int,int>
#define rep(i,a) for(int i=0;i<(a);i++)
#define all(x) (x).begin(),(x).end()
#define debug system("pause")				//デバッグ用
#define ret return 0

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 (b < a) { a = b; return 1; } return 0; }

#define ketasitei setprecision(15) //15桁表示

int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	int a,b,c;
    cin>>a>>b>>c;
    
    if(a==b && b==c || a!=b && a!=c && b!=c)
    {
        cout<<"No"<<endl;
    }
    else
    {
cout<<"Yes"<<endl;
    }

	return 0;
}

Measured memory_bytes: 256
import math

# input
#
# n = 5
# k = 10
# a = [1, 2, 3, 2, 3]

n, k = map(int, input().split())
a = [int(ai) for ai in input().split()]

# make jumpto
#
# 0 -> 6 (5)
# 1 -> 4 (2)
# 2 -> 5 (2)
# 3 -> 7 (3)
# 4 -> 8 (3)

jumpto = [[-1] * n]
la = -1
li = -1
for (ca, ci) in sorted(zip(a, range(n))):
    if ca == la:
        jumpto[0][ci] = jumpto[0][li] + li - ci
        jumpto[0][li] = ci - li
    else:
        jumpto[0][ci] = n
    la = ca
    li = ci

# doubling jumpto
#
# 0 -> 6 ->  9 (8)
# 1 -> 4 ->  8 (6)
# 2 -> 5 -> 11 (8)
# 3 -> 7 -> 10 (6)
# 4 -> 8 -> 12 (7)
#
# 0 -> 6 ->  9 -> 13 -> 17  (16)
# 1 -> 4 ->  8 -> 12 -> 15  (13)
# 2 -> 5 -> 11 -> 14 -> 18  (15)
# 3 -> 7 -> 10 -> 16 -> 19  (15)
# 4 -> 8 -> 12 -> 15 -> 21  (16)

levels = int(math.log(k, 2))
for l in range(1, levels + 1):
    jumpto.append([-1] * n)
    for i in range(n):
        f = jumpto[l - 1][i]
        s = jumpto[l - 1][(i + f + 1) % n]
        jumpto[l][i] = f + 1 + s

# step1
s = 0
while True:
    jumped = False
    for l in range(levels, -1, -1):
        if s + jumpto[l][s % n] < n * k:
            s += jumpto[l][s % n] + 1
            jumped = True
            break
    if not jumped:
        break

# step2
ret = []
while s < n * k:
    if s + jumpto[0][s % n] < n * k:
        s = s + jumpto[0][s % n] + 1
    else:
        ret.append(str(a[s % n]))
        s += 1

print(' '.join(ret))


Measured memory_bytes: 121940
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define M 1000000007LL
#define rep(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define sep(i,a,b) for(ll i=(ll)a;i>=(ll)b;i--)
#define mll map<ll,ll>
#define vl vector<ll>
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define sz(v) ((ll)v.size())
#define all(a) a.begin(),a.end()
#define F first
#define S second
#define pii pair<ll,ll> 
#define mod 1000000007
#define MAXN 300002
ll dsu[100002];
ll sum,sq;
ll pp=0;
void join(ll x,ll y)
{
  
  while(dsu[x]>0) x=dsu[x];
  while(dsu[y]>0) y=dsu[y]; 
 if(x==y) return;
  if(dsu[x]>dsu[y])
  swap(x,y);
  sq=sq-dsu[x]*dsu[x]-dsu[y]*dsu[y]+(dsu[x]+dsu[y])*(dsu[x]+dsu[y]);
  dsu[x]+=dsu[y];
  dsu[y]=x;
 
 //  if(pp==4) exit(0);
}
int main() {
       ios::sync_with_stdio(false);
       cin.tie(0);
       cout.tie(0);
       ll n,m;
       cin>>n>>m;
       memset(dsu,-1,sizeof(dsu));
       vector< pii > v;
       for(ll i=0;i<m;i++)
       {
        ll x,y;
        cin>>x>>y;
        v.pb({x,y});
       }
       reverse(all(v));
       sum=n,sq=n;
       vector<ll> ans;
       for(auto it:v)
       {
         ans.pb((sum*sum-sq)/2);
       // cout<<dsu[it.F]<<" "<<dsu[it.S];
        join(it.F,it.S);
       }
       reverse(all(ans));
       for(auto it: ans)
       {
        cout<<it<<endl;
       }
       return 0;

}

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

int main(){
  string S;
  cin >> S;
  string y = "Yes";
  if(S.at(0) == 'A' && S.at(1) == 'A' && S.at(2) == 'A') y = "No";
  if(S.at(0) == 'B' && S.at(1) == 'B' && S.at(2) == 'B') y = "No";
  cout << y << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9+7;
const int INF = 2e9;
 
int main(){
    int n;
    vector<int> h, dp;
    cin >> n;
    h.resize(n);
    for(int i=0; i<n; i++){
        cin >> h[i];
    }
    dp.resize(n);
    dp[0] = 0;
    dp[1] = abs(h[1]-h[0]);
    for(int i=2; i<n; i++){
        dp[i] = INF;
        for(int j=i-2; j<i; j++){
            dp[i] = min(dp[i],abs(h[i]-h[j])+dp[j]);
        }
    }
    cout << dp[n-1] << endl;
}

Measured memory_bytes: 1152
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <iomanip>
#include <bitset>
#include <set>
#include <map>
#include <stdio.h>
#include <numeric>

#define rep(i,n) for (long long int i = 0; i < (n); i++)
#define rep1(i,n) for (long long int i = 1; i < (n); i++)
#define FOR(i,a,b) for (int i=(a); i < (b); i++)
#define INF 100000000000
#define MOD 1000000007 //10^9+7
using namespace std;
using ll = long long;
using P = pair<int, int>;

// 負の数にも対応した % 演算
long long mod(long long val, long long m) {
    long long res = val % m;
    if (res < 0) res += m;
    return res;
}

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

long long lcm(ll a, ll b)
{
    return a / gcd(a, b) * b ;
}

int main()
{
    string s; cin >> s;
    int b = 0, r= 0;
    rep(i,s.length()) {
        if(s[i] == '1')
            b++;
        else
            r++;
    }
    cout << min(b,r)*2 << endl;
    return 0;
}


Measured memory_bytes: 512
import sys


stdin = sys.stdin
def ns(): return stdin.readline().rstrip()
def ni(): return int(stdin.readline().rstrip())
def nm(): return map(int, stdin.readline().split())
def nl(): return list(map(int, stdin.readline().split()))


def main():
    n = ni()
    d, x = nm()
    ans = x
    for i in range(n):
        a = ni()
        ans += (d - 1) // a + 1
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 8972
#include<bits/stdc++.h>
using namespace std;
int main(){
	int h,w;
  cin>>h>>w;
  vector<vector<char > >mat(h,vector<char >(w));
  for(int i=0;i<h;i++)
    for(int j=0;j<w;j++)cin>>mat[i][j];
  int pos=1;
  int count=0;
  for(int i=0;i<h;i++)
    for(int j=0;j<w;j++){
      if(mat[i][j]=='.')continue;
      count=0;
      for(int k=-1;k<=1;k++)
        for(int l=-1;l<=1;l++)
        	if((k==0 || l==0) && !(k==0 && l==0))
            	if(i+k>=0 && i+k<h && j+l>=0 && j+l<w && mat[i+k][j+l]=='#')count++;
        if(count==0)pos=0;
    }
  if(pos==1)cout<<"Yes\n";
  else cout<<"No\n";
    
}

Measured memory_bytes: 3644
N = int(input())

A = list(map(int,input().split()))
B = [] #累積和するぞ！

s = 0
for a in A:
    s += a
    B.append(s)

sabun_m = abs(B[N-1] - (B[0]*2))

'''
1 2 3 4

1 | 2 3 4 (1234-1)-1
'''

for b in B[1:N-1]:
    sabun = abs(B[N-1] - (b*2))
    if sabun < sabun_m:
        sabun_m = sabun
        
print(sabun_m)

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

int cnt(ll n){
  int digits=0;
  while(n>0){
    n/=10;
    digits++;
  }
  return digits;
}

int main(){
  ll n; cin>>n;
  int ans=cnt(n);
  for(ll a=1LL;a*a<=n;a++){
    if(n%a!=0)continue;
    const ll b=n/a;
    const int cur=max(cnt(a),cnt(b));
    ans=min(ans,cur);
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>

using namespace std;

int Y[3] = {500, 100, 50};
int X, C[3];

long long solve(int i, int m)
{
	long long res = 0;
	if (m < 0) return 0;
	if (m == 0) return 1;
	if (i > 2) return 0;
	for (int j = 0; j <= C[i]; j++) {
		res += solve(i + 1, m - Y[i] * j);
	}
	return res;
}


int main()
{
	cin >> C[0];
	cin >> C[1];
	cin >> C[2];
	cin >> X;
	cout << solve(0, X) << endl;
	return 0;
}

Measured memory_bytes: 256
#[allow(unused)]
use proconio::marker::*;
use proconio::{fastout, input};
#[allow(unused)]
use std::cmp::{max, min};
#[allow(unused)]
use std::collections::{HashMap, HashSet, VecDeque};
#[fastout]
fn main() {
    input! {
      n: usize,
      a: [u128; n],
    }
    let mut ans: u128 = 1;
    if a.iter().any(|&a| a == 0) {
        println!("{}", 0);
        return;
    }
    for i in 0..n {
        ans *= a[i];
        if ans > 1_000_000_000_000_000_000 as u128 {
            println!("{}", -1);
            return;
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 5328
#include<bits/stdc++.h>
using namespace std;
deque < int > n2;
int zh=0;
int zx1,zx2;
int main()
{
	int n;
	cin>>n;
	int o;
	for(int i=0;i<n;i++)
	{
		cin>>o;
		n2.push_back(o);
		zh+=o;
	}
	zx1=0;
	int i=0;
	for(;zx1<=zh/2;i++)
	{
		zx2=zx1;
		zx1+=n2[i]; 
	}
	cout<<min((zh-(zx2*2)),((zx1*2)-zh))<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long int lli;

int main(){
	lli n;
	cin >> n;
	vector<lli> factor;
	for(lli i=1; i*i<=n; i++){
		if(n%i==0){
			factor.push_back(i);
			if(i*i!=n){
				factor.push_back(n/i);
			}
		}
	}
	lli ans = 0;
	for(lli i: factor){
		if(i>1 and n/(i-1)==n%(i-1)){
			ans += i-1;
		}
	}
	cout << ans << endl;
    return 0;
}

Measured memory_bytes: 384
import sys
N = int(input())
t=[0]*(N+1)
x=[0]*(N+1)
y=[0]*(N+1)
#距離を保管する変数
dist = 0
#時間の差を保管しておくための変数
dt = 0 
#初期値を保管しておく
now_x =0
now_y =0

t[0] = 0
x[0] = now_x
y[0] = now_y
for i in range(1,N+1):
    t[i],x[i],y[i] = map(int, input().split())
    
for i in range(1,N+1):    
    #距離を計算する
    dist = abs(x[i]-x[i-1])+abs(y[i]-y[i-1])
    dt = abs(t[i] - t[i-1])
    #時間が足りないときは絶対にいけない
    if(dist > dt):
        print('No')
        sys.exit()
    else:
        #dtが偶数なら、進む距離も偶数なはず
        #その逆も然り
        if(dt %2 != dist %2):
            print('No')
            sys.exit()
    
print('Yes')

Measured memory_bytes: 11636
import heapq
from collections import deque

WHITE = 0
GRAY = 1
BLACK = 2

n = int(raw_input())
M = []
for i in xrange(n):
    M.append(deque([]))
color = [WHITE] * n
d = [float('inf')] * n

for i in xrange(n):
    a = map(int, raw_input().split())
    for j in xrange(a[1]):
        M[a[0]].append((a[2*(j+1)],a[2*(j+1)+1]))

def dijkstra():
    d[0] = 0

    PQ = []
    heapq.heappush(PQ,(0,0))#value, node
    
    color[0] = GRAY

    while len(PQ) > 0:
        f = heapq.heappop(PQ)
        u = f[1]
        color[u] = BLACK

        if d[u] < f[0]:
            continue

        for j in xrange(len(M[u])):
            v = M[u][j][0]
            if color[v] == BLACK:
                continue
            if d[v] > d[u] + M[u][j][1]:
                d[v] = d[u] + M[u][j][1]
                heapq.heappush(PQ, (d[v],v))
                color[v] = GRAY

    for i in xrange(n):
        print "{} {}".format(i, d[i])

    return 0

def main():
    dijkstra()
    return 0

main()

Measured memory_bytes: 67096
import sys
input=lambda: sys.stdin.readline().rstrip()
n=int(input())
A=sorted([int(i) for i in input().split()],reverse=True)
import heapq
C=[]
heapq.heappush(C,-A[0])
ans=0
for i in range(1,n):
  cur=-heapq.heappop(C)
  ans+=cur
  heapq.heappush(C,-A[i])
  heapq.heappush(C,-A[i])
print(ans)

Measured memory_bytes: 31544
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>

using namespace std;

#define NMAX 200010

int a[NMAX];
int imos[NMAX];

void reset(int n) {
    for(int i = 0; i < n; i++) imos[i] = 0;
}

int max(int a, int b) {
    if(a > b) return a;
    else return b;
}

int min(int a, int b) {
    if(a > b) return b;
    else return a;
}

int get_int() {
    int res = 0;
    char c = getchar();
    while(c != EOF && c != ' ' && c != '\n') {
        res *= 10;
        res += c - '0';
        c = getchar();
    }
    return res;
}

int main(){

    int n, k;
    n = get_int();
    k = get_int();
    for(int i = 0; i < n; i++) a[i] = get_int();

    for(int itr = 0; itr < k; itr++) {
        int f = 0;
        reset(n+1);
        for(int i = 0; i < n; i++){
            f = (a[i] != n);
            imos[max(0, i - a[i])]++;
            imos[min(n, i + a[i] + 1)]--;
        }
        int acc = 0;
        for(int i = 0; i < n; i++){
            acc += imos[i];
            a[i] = acc;
        }
        if(!f) break;
    }

    for(int i = 0; i < n; i++) printf("%d\n", a[i]);
    return 0;
}


Measured memory_bytes: 5220
import re
s=input().replace("?",".")
t=input()
for i in range(len(s)-len(t),-1,-1):
    if re.match(s[i:i+len(t)],t):
        s=s.replace(".","a")
        print(s[:i]+t+s[i+len(t):])
        exit()
print("UNRESTORABLE")

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
const int N=200;

 
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll n,fn,wn;
	cin >> n;
	wn = n;
	fn = 0ll;

	while(wn!=0){
		fn += wn%10;
		wn/=10;
	}
	if(n%fn==0){
		cout << "Yes" << endl;
	}else{
		cout << "No" << endl;
	}
	
	
	return 0;
}

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

#define rep(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define rng(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
#define rbf(i, v) for (auto& (i) : (v))
#define All(x) (x).begin(),(x).end()
#define cAll(x) (x).cbegin(),(x).cend()
#define COL(x) cout << x << endl
#define CO(x) cout << x
//#define int long long

template<typename T> inline constexpr auto square(T x) { return (x) * (x); }

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<PII> VP;

const int MOD = 1000000007;
const int INF = INT_MAX;

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

	VI A(N), B(N+1);
	B[0] = INF;
	B[N] = INF;
	rng(i, 1, N) cin >> B[i];

	rep(i, N) {
		A[i] = min(B[i], B[i + 1]);
	}

	int sum = accumulate(All(A), 0);

	COL(sum);

	return 0;
}

Measured memory_bytes: 764
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include <bitset>
#include<math.h>
#include<map>
#include<set>
using namespace std;
#define INF 11000000000
#define MOD 1000000007
typedef long long ll;
typedef pair<ll,ll> P;


int main(){
  int X,ans=1;
  cin>>X;
  for(int i=2;i<X;i++){
    int temp=1;
    while(temp*i<=X){
      temp*=i;
    }
    if(temp!=i) ans=max(ans,temp);
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 888
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<set>
#include<map>
#include<queue>
#include<cmath>
#define REP(i,a) for (int i = 0;i < (a);++i)
#define FOR(i,a,b) for (int i = (a);i < (b); ++i)
#define FORR(i,a,b) for (int i = (a);i >= (b); --i)
#define ALL(obj) (obj).begin(),(obj).end()
#define SORT(list) sort(ALL((list)));
#define MOD 1000000007
using namespace std;
using ll = long long;
ll gcd(ll a,ll b){
    return b?gcd(b,a%b):a;
}
int main(){
    ll n;
    cin >> n;
    vector<ll>a(n);
    vector<bool>pf(1001000);
    REP(i,1001000)pf[i]=false;
    REP(i,n)
        cin >> a[i];
    bool ok=true;
    REP(i,n){
        ll tmp = a[i];
        FOR(j,2,(int)ceil(sqrt(a[i]))+1){
            if(tmp%j==0 and pf[j]){
                ok=false;
                goto jump;
            }
            while(tmp%j==0){
                tmp/=j;
                pf[j]=true;
            }
        }
        if(tmp!=1){
            if(pf[tmp]){
                ok = false;
                break;
            }
            pf[tmp]=true;
        }
    }
    jump:
    if(ok){
        cout << "pairwise coprime" << endl;
        return 0;
    }

    int g = gcd(a[0],a[1]);
    REP(i,n){
        g = gcd(g,a[i]);
    }
    if(g==1){
        cout << "setwise coprime" << endl;
    }
    else{
        cout << "not coprime" << endl;
    }

    return 0;
}


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

int main() {
  int A, B, C;
  cin >> A >> B >> C;

  for(int i=1; i <= B; i++) {
    if(A * i % B == C) {
      cout << "YES" << endl;
      return 0;
    }
  }
  cout << "NO" << endl;
}

Measured memory_bytes: 3616
s = list(map(len, input().split('T')))
x, y = map(int, input().split())

dp = [set([s[0]]), set([0])]

for i in range(1, len(s)):
    nxt = set()
    for j in dp[i % 2]:
        nxt.add(j + s[i])
        nxt.add(j - s[i])
    dp[i % 2] = nxt

if x in dp[0] and y in dp[1]:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3784
def nc2(n):
	return (n*(n-1))//2
n=int(input())
l=list(map(int,input().split()))
cnt=[0]*(n+1)
for i in l:
	cnt[i]+=1
ans=0
for i in range(1,n+1):
	ans+=nc2(cnt[i])
#print(ans)
for i in l:
	print(ans-nc2(cnt[i])+nc2(cnt[i]-1))


Measured memory_bytes: 81996
import sys
input = sys.stdin.readline
N,Q = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(N-1)]
PX = [tuple(map(int,input().split())) for i in range(Q)]

es = [[] for i in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

xs = [0] * N
for p,x in PX:
    xs[p-1] += x

ans = [0] * N
ans[0] = xs[0]
visited = [0] * N
stack = [0]
while stack:
    v = stack.pop()
    visited[v] = 1
    for to in es[v]:
        if visited[to]: continue
        stack.append(to)
        ans[to] = ans[v] + xs[to]

print(*ans)

Measured memory_bytes: 116312
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))

sat = sum(B)
for i in range(N-1):
    if A[i]+1==A[i+1]:
        sat += C[A[i]-1]
print(sat)


Measured memory_bytes: 3060
n=int(input())
h=list(map(int,input().split()))
dp=[0]*n
dp[0]=0
dp[1]=abs(h[1]-h[0])
for i in range(2,n):
  dp[i]=min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]))
print(dp[n-1])

Measured memory_bytes: 52208
program xor_circle
  implicit none
  integer :: n, a(100000) = 0, x = 0, i
  read(*,*) n
  read(*,*) a(1:n)
  do i = 1, n
    x = xor(x,a(i))
  end do
  if (x == 0) then
    write(*,'(a)') "Yes"
  else
    write(*,'(a)') "No"
  end if
  stop
end program xor_circle

Measured memory_bytes: 1152
#include <iostream>
#include <string>
#include <utility>
#include <stack>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <climits>
#include <set>
#include <numeric>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <cfloat>
using namespace std;
long long A[200000];
long long cumsum_A[200000];
const long long MOD = 1000000007;
int main(){
  int N;
  cin >> N;
  for(int i = 0; i < N; i++){
    cin >> A[i];
  }

  cumsum_A[N - 1] = A[N - 1];
  for(int i = N - 2; i >= 0; i--){
    cumsum_A[i] = (A[i] + cumsum_A[i + 1]) % MOD;
  }

  long long ans = 0;
  for(int i = 0; i < N - 1; i++){
    long long tmp = (A[i] * cumsum_A[i + 1]) % MOD;
    ans = (ans + tmp) % MOD;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 6708
import java.util.Scanner;

/**
 *
 * @author bhatti
 */
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        boolean[] blacklist = new boolean[]{true, true, true, true, true,
            true, true, true, true, true};

        for (int i = 0; i < K; ++i) {
            int d = sc.nextInt();
            blacklist[d] = false;
        }
        boolean breaked = false;    
        while (true) {
            breaked = false;
            StringBuilder builder = new StringBuilder(String.valueOf(N));
            for (int j = 0; j < builder.length(); ++j) {
                int value = Integer.valueOf(builder.substring(j, j + 1)).intValue();
                if (!blacklist[value]) {
                   // builder.setCharAt(j, String.valueOf(getNext(blacklist, value)).charAt(0));
                   breaked = true;
                   break;
                }
            }
            if (!breaked){
                System.out.println(N);
                break;
            }
            N++;
        }
        
    }
}


Measured memory_bytes: 38228
import java.util.*;
import java.util.Collections;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int X = sc.nextInt();
    int A = 0;
    int cnt = N;
    List<Integer> list = new ArrayList<Integer>();
    for (int i = 0; i < N; i++) {
      list.add(sc.nextInt());
      X -= list.get(i);
    }
    Collections.sort(list);
    int min = list.get(0);
    while (X >= min) {
      X = X - min;
      cnt++;
    }
    System.out.println(cnt);
  }
}


Measured memory_bytes: 21844
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cstdio>
#include<cstring>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(n) rep(i,n)
#define all(n) n.begin(),n.end()

const int MAXN = 55, MAXD = 31;

int main()
{
    int n;
    while(cin >> n && n)
    {
        int pa[MAXD][MAXN][MAXN] = {};
        int date[MAXN][MAXD] = {};
        int f, day;
        REP(n)
        {
            rep(d, MAXD)pa[d][i][i] = 1;
            cin >> f;
            rep(j, f)
            {
                cin >> day;
                date[i][day] = 1;
            }
        }

        for(int d =1; d < MAXD; d++)
        {
            rep(i,n)rep(k,n)pa[d][i][k] = pa[d - 1][i][k];

            rep(i,n)rep(j,n)if(date[i][d] == 1 && date[j][d] == 1)
            {
                //cout << "day" << d << "   " << i << "," << j << " Ok" << endl;
                rep(k, n)if(pa[d - 1][i][k] || pa[d -1][j][k])
                {
                    //cout << "k " << k << endl;
                    pa[d][i][k] = 1;
                    pa[d][j][k] = 1;
                }
            }
        }

        int ans = -1;
        rep(d, MAXD)
        {
            rep(i, n)
            {
                int num = 0;
                rep(j,n) num += pa[d][i][j];
                if(num == n) { ans = d; break;}
            }
            if(ans > 0) break;
        }
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 1540
import math
def main():
    X = int(input())
    for i in range(X, 2*10**5+1):
        if i % 2 == 0 and i != 2:
            continue
        is_prime = True
        for j in range(2, math.floor(math.sqrt(i))+1):
            if i % j == 0:
                is_prime = False
        if is_prime :
            print(i)
            break
if __name__ == "__main__":
    main()

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

long long l;

long double solve();

int main() {
  cout << fixed << setprecision(10);
  cin >> l;
  cout << solve() << endl;
  return 0;
}

long double solve() {
  long double res = 0, p = l / 3.0;
  return p * p * p;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
#define INF (1<<28)
int N,M;
int t[20000];
int u[20000];
int dp[20000][256];

void init(){
  for(int i=0;i<20000;i++)
    for(int j=0;j<256;j++)
      dp[i][j]=INF;
}

int calc(int a,int b){
  if(a+b<0)return 0;
  if(a+b>=256)return 255;
  return a+b;
}

int dist(int a,int b){
  return (a-b)*(a-b);
}

int main(){
  while(1){
    cin>>N>>M;
    if(N==0&&M==0)break;
    init();
    for(int i=0;i<M;i++)cin>>t[i];
    for(int i=0;i<N;i++)cin>>u[i];
    for(int i=0;i<M;i++)dp[0][calc(128,t[i])]=dist(calc(128,t[i]),u[0]);

    for(int i=0;i+1<N;i++){
      for(int j=0;j<256;j++){
	if(dp[i][j]==INF)continue;
	//cout<<i<<' '<<j<<' '<<dp[i][j]<<endl;
	for(int k=0;k<M;k++){
	  int A=calc(j,t[k]);
	  //cout<<A<<endl;
	  dp[i+1][A]=min(dp[i+1][A],dp[i][j]+dist(A,u[i+1]));
	  
	}
      }
    }
    int ans=INF;
    for(int i=0;i<256;i++)
      ans=min(ans,dp[N-1][i]);
    cout<<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 21240
#include <bits/stdc++.h>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()
#define fi first
#define se second
#define endl "\n"
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

//const ll MOD = 998244353;
const ll MOD = (1e+9) + 7;
const ll INF = 2e+9 + 10;
typedef pair<ll, ll> P;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);

  int N; cin >> N;
  string S; cin >> S;

  rep(i, S.size()) {
    int x = (S[i]-'A'+N)%26;
    S[i] = (char)(x+'A');
  }
  cout << S << endl;

  return 0;
}

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

int main() {
	int N;
	cin >> N;
	vector <int> height(N);
	for(int i = 0; i < N; i++) {
		cin >>height[i];
	}
	int max = 0;
	int ans = 0;
	for(int i = 0;i < N;i++){
	if(max <= height[i]){
		max = height[i];
        ans++;
	}
	}
cout << ans<< endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
#define mod 1000000007LL
 
ll f1[100010],f2[100010],sum1[100010],sum2[100010];
ll h1[100010],h2[100010],num[100010],n,sa,sb;
 
inline ll rd()
{
    ll x=0;char ch=getchar();
    for (;ch<'0'||ch>'9';ch=getchar());
    for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
    return x;
}
 
int main()
{
    n=rd();sa=rd();sb=rd();
    for (int i=1;i<=n;i++) num[i]=rd();
    num[0]=-1000000000000000000LL;
    for (int i=2;i<=n;i++)
    {
        int l=0,r=i-1;
        while (l<r)
        {
            int mid=((l+r)>>1)+1;
            if (num[i]-num[mid]>=sb) l=mid;
            else r=mid-1;
        }
        h1[i]=l;l=0;r=i-1;
        while (l<r)
        {
            int mid=((l+r)>>1)+1;
            if (num[i]-num[mid]>=sa) l=mid;
            else r=mid-1;
        }
        h2[i]=l;
    }
    f1[0]=sum1[0]=f2[0]=sum2[0]=1;
    int s1=1,s2=1;
    for (int i=1;i<=n;i++)
    {
        if (num[i]-num[i-1]<sa) s1=i;
        if (num[i]-num[i-1]<sb) s2=i;
        int hh1=(i<n)?min(h1[i+1],(ll)i-1):n-1,hh2=(i<n)?min(h2[i+1],(ll)i-1):n-1;
        if (s1-1<=hh1) f1[i]=(sum2[hh1]-(s1>1?sum2[s1-2]:0)+mod)%mod;
        if (s2-1<=hh2) f2[i]=(sum1[hh2]-(s2>1?sum1[s2-2]:0)+mod)%mod;
        sum1[i]=(sum1[i-1]+f1[i])%mod;sum2[i]=(sum2[i-1]+f2[i])%mod;
    }
    printf("%lld\n",(f1[n]+f2[n])%mod);
    return 0;
}

Measured memory_bytes: 5760
N, M = map(int, input().split())
AC, WA = [0]*(N+1), [0]*(N+1)
for _ in range(M):
    p, S = input().split()
    if AC[int(p)] == 0:
        if S == 'AC':
            AC[int(p)] = 1
        else:
            WA[int(p)] += 1

ac, wa = 0, 0
for i in range(N+1):
    ac += AC[i]
    wa += AC[i] * WA[i]
print(ac, wa)

Measured memory_bytes: 4596
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;

int main(void){
	int n;
	while(cin>>n,n){
		std::set<int> a[100];
		std::vector<int> s;
		int m,k;
		for(int i=0;i<n;i++){
			cin>>m;
			for(int j=0;j<m;j++){
				cin>>k;
				a[i].insert(k);
			}
		}
		int z;
		cin>>k,z;
		for(int i=0;i<k;i++){
			cin>>z;
			s.push_back(z);
		}

		int c=0;
		int number=9999;
		int i,j;
		for(i=0;i<n;i++){
			if(a[i].size()<s.size())continue;
			for(j=0;j<s.size();j++){
				if(a[i].find(s[j])==a[i].end())break;
			}
			if(j==s.size())c++;
			if(j==s.size())number=i+1;
			if(c==2)break;
		}
		if(c==1)cout<<number<<endl;
		else cout<<"-1"<<endl;
	}
	return 0;
}

Measured memory_bytes: 3516
#include <bits/stdc++.h>
typedef long long LL;
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)

using namespace std;

int main(void)
{
  int n, k;
  cin >> n >> k;
  vector<vector<LL> > v(n+1,vector<LL>());
  REP(i,n) {
    LL t,d;
    cin >> t >> d;
    v[t].push_back(d);
  }
  vector<LL> uniq,comm;
  REP(i,n+1) {
    if(v[i].empty()) continue;
    sort(v[i].begin(), v[i].end());
    uniq.push_back(v[i].back());
    v[i].pop_back();
    for(auto c:v[i]) comm.push_back(c);
  }
  sort(uniq.rbegin(), uniq.rend());
  sort(comm.rbegin(), comm.rend());
  uniq.insert(uniq.begin(),0ll);
  comm.insert(comm.begin(),0ll);
  REP(i,uniq.size()-1) uniq[i+1]+=uniq[i];
  REP(i,comm.size()-1) comm[i+1]+=comm[i];
  LL answer = 0ll;
  FOR(i,1,k+1) {
    if(uniq.size()-1 < i || comm.size()-1 < k-i) continue;
    answer=max(answer,i*i+uniq[i]+comm[k-i]);
  }
  cout << answer << endl;
  return 0;
}


Measured memory_bytes: 6904
import collections
N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
q = collections.deque()
q.append(0)
dist = [-1]*N
dist[0] = 0
while len(q) != 0:
    v = q.popleft()
    for w in graph[v]:
        if dist[w] > -1:
            continue
        dist[w] = v + 1
        q.append(w)
print('Yes')
for i in range(1,N):
    print(dist[i])

Measured memory_bytes: 36972
#include <iostream>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);++i)
#define rep(i,a,b) for (int i=a; i<(b);++i)
typedef long long ll;
const long long MOD = 1e9 + 7;
const int MAX = 200001;

int H,W,A,B;
ll fact[MAX],finv[MAX];
ll inv(ll x){
    int res = 1;
    int k = MOD - 2;
    ll y = x;
    while(k){
        if(k & 1) res = (res * y) % MOD;
        y = (y * y) % MOD;
        k >>= 1;
    }
    return res;
}

ll comb(int n, int k){
    if(n < k || n < 0 || k < 0) return 0;
    return fact[n] * (finv[k] * finv[n-k] % MOD) % MOD;
}

int main(){
    cin >> H >> W >> A >> B;
    ll ans = 0;

    fact[0] = fact[1] = 1;
    finv[0] = finv[1] = 1;
    rep(i,2,MAX) {
        fact[i] = fact[i-1] * i % MOD;
        finv[i] = inv(fact[i]) % MOD;
    }
    rep(i,B,W){
        ans += (comb(H-A-1+i,i) * comb(W+A-i-2,A-1)) % MOD;
        ans %= MOD;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3968
#include<iostream>
#include<vector>

using namespace std;

int main()
{
    int n;
    int i;
    string s, ans;
    cin >> n;
    cin >> s;
    ans = s;
    if(s.size() > n)
    {
        ans = "";
        for(i=0; i<n; i++)
        {
            ans += s[i];
        }
        ans += "...";
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
map<int,int> s;
int main(){
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m,q;
    while(cin>>n){
        s.clear();
        for(int i=0;i<n;++i){
            cin>>q;
            ++s[q];
        }
        bool flag=true;
        cin>>m;
        while(m--){
            cin>>q;
            if(s[q]){
                --s[q];
            }else {
                flag=false;
            }
        }
        cout<<(flag?"YES":"NO")<<endl;
    }
    return 0;
}


Measured memory_bytes: 9728
#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());
    
    int now = 0;
    int cnt = 0;
    int ans = 0;
    for(int i = 0; i < N; i++) {
        if(A.at(i)!=now) {
            ans += cnt%2;
            now = A.at(i);
            cnt = 1;
        }
        else cnt++;
    }
    ans += cnt%2;
    cout << ans << endl;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
#include <iomanip>
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF=1001001001;
vector<pair<int64_t,int64_t>>prime_factorize(int64_t x){
  vector<pair<int64_t,int64_t>>p;
  for(int64_t i=2;i*i<=x;i++){
    int cnt=0;
    if(x%i==0){
    while(x%i==0){cnt++;x/=i;}
    p.push_back(make_pair(i,cnt));
    }
  }
  if(x!=1){p.push_back(make_pair(x,1));}
  return p; 
}
int main() {
  int N,K;
  cin>>N>>K;
  vector<int>x(N);
  for(int i=0;i<N;i++){
    cin>>x[i];
  }
  vector<int>dis;
  for(int i=0;i<N-1;i++){
    dis.push_back(x[i+1]-x[i]);
  }
  vector<int64_t>table(N+2);
  for(int i=0;i<N-1;i++){
    table[i+1]=table[i]+dis[i];
  }
  int64_t ans=999999999999999;
  for(int i=0;i<N;i++){
    if(N-K>=i){
    int64_t sum=0;
    int start=min(abs(x[i]),abs(x[i+K-1]));
    sum=start+table[i+K-1]-table[i];
    //cout<<sum<<endl;
    ans=min(ans,sum);
    }
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 4936
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

int main() {
  int a,b,c;
  cin >>a>>b>>c;
  if((a-c)*(c-b)>=0){
    cout<<"Yes"<<endl;
  }else cout <<"No"<<endl;
}



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

using namespace std;
typedef long long ll;
#define tr(container, it) \
    for (auto it = container.begin(); it != container.end(); it++)
#define scontains(c, x) ((c).find(x) != (c).end())   //O(log n)
#define contains(c, x) (find((c).begin(),(c).end(),x) != (c).end()) //O(n)
#define ill(_x)  ll _x;scanf("%lld",&_x);
#define idb(_x)  double _x;scanf("%lf",&_x);
#define pll pair<ll,ll>
#define mll map<ll,ll>
#define vll vector<ll>
#define sll set<ll>
#define vs vector<string>
#define in0(x, a, b)((x)>=a && (x)<=b    )
#define in1(x, a, b)((x)>a && (x)<b)
#define  rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define endl '\n'
#define int int64_t
const double pi = 3.14159265358979323846;
const int INF = 0x3f3f3f3f;
const int MOD = (int) (1e9) + 7;

int tc, q;
map<int, int> factorize(long long n)
{
    map<int, int> factors;
    int count = 0;

    while (!(n % 2)) {
        n >>= 1;
        count++;
    }

    if(count)factors[2] = count;

    for (long long i = 3; i <= sqrt(n); i += 2) {
        count = 0;
        while (n % i == 0) {
            count++;
            n = n / i;
        }
        if (count)
            factors[i] = count;
    }

    if (n > 2)
        factors[n] = 1;
    return factors;
}



void _() {
    int n, m;
    cin >> n >> m;
    string s,t;
    cin >> s >>t;
    int l = n*m/ __gcd(n, m);
    for (int i = 0; i < __gcd(n, m); ++i) {
        if(s[i*n/__gcd(n,m)] != t[i*m/__gcd(n,m)]){
            cout << -1 ;return;
        }
    }
    cout << l;

};

#undef int
int main() {
#if __MINGW32__
    freopen("C:\\Users\\hiroo\\CLionProjects\\competitive\\Input.txt", "r", stdin);
    freopen("C:\\Users\\hiroo\\CLionProjects\\competitive\\Output.txt", "w", stdout);

#endif

    _();
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);


}

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

using namespace std;
using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
#define REP(i,n) for(ll i = 0;i < (ll)n;i++)
#define REPD(i,n) for(ll i = (ll)n - 1;i >= 0;i--)
#define ALL(x) (x).begin(),(x).end()
#define FILLl(n,first_dimension_size,value) fill((ll*)n,(ll*)(n+first_dimension_size),value)
#define FILL(n,first_dimension_size,value) fill((int*)n,(int*)(n+first_dimension_size),value)
#define INF (1 << 30)
#define MOD 1000000007
//int dy[4] = {-1,0,0,1};
//int dx[4] = {0,1,-1,0};

class UnionFind{
  public:
  vector<ll> par;
  UnionFind(ll size) : par(size,-1){}
  bool unite(int x,int y){
    x = root(x),y = root(y);
    if(x == y)return false;
    if(par[y] < par[x])swap(x,y);
    par[x] += par[y];
    par[y] = x;
    return true;
  }
  bool find(int x,int y){
    return root(x) == root(y);
  }
  int root(int x){
    return par[x] < 0 ? x : par[x] = root(par[x]);
  }
  int size(int x){
    return -par[root(x)];
  }
};

struct edge{
  int we,fr,to;
  bool operator<(const edge &other){
    return we < other.we;
  }
};

int main(){

  int n;
  cin >> n;
  vector<tuple<int,int,int>> vx,vy;
  vector<edge> v;
  REP(i,n){
    int x,y;cin >> x >> y;
    vx.push_back(make_tuple(x,y,i));
    vy.push_back(make_tuple(y,x,i));
  }
  sort(ALL(vx));
  sort(ALL(vy));
  REP(i,n-1)v.push_back({abs(get<0>(vx[i])-get<0>(vx[i+1])),get<2>(vx[i]),get<2>(vx[i+1])});
  REP(i,n-1)v.push_back({abs(get<0>(vy[i])-get<0>(vy[i+1])),get<2>(vy[i]),get<2>(vy[i+1])});
  sort(ALL(v));
  UnionFind uf(n);
  ll res = 0;
  for(auto nv : v){
    if(uf.find(nv.fr,nv.to))continue;
    uf.unite(nv.fr,nv.to);
    res += nv.we;
  }
  cout << res << endl;


  
  

  return 0;
}


Measured memory_bytes: 7340
n = int(input())
flag = 0
ML = []
MM = []
MR = []
L = 0
R = 0
for _ in range(n):
    s = input()
    saisho = 0
    cur = 0
    for w in s:
        if w == "(":
            cur += 1
        else:
            cur -= 1
            saisho = min(saisho, cur)
    if cur > 0:
        ML.append((saisho, cur))
    elif cur < 0:
        MR.append((-cur + saisho, -cur))
    else:
        MM.append((saisho, cur))
ML.sort(reverse=True)
MR.sort(reverse=True)
leftnow = 0
for saisho, delta in ML:
    if leftnow + saisho < 0:
        flag = 1
    leftnow += delta
for saisho, delta in MM:
    if leftnow + saisho < 0:
        flag = 1
    leftnow += delta
rightnow = 0
for saisho, delta in MR:
    if rightnow + saisho < 0:
        flag = 1
    rightnow += delta

if rightnow != leftnow:
    flag = 1
if flag:
    print("No")
else:
    print("Yes")


Measured memory_bytes: 80304
#include<iostream>
#include<cstring>

int main() {
	char s[11];
	std::cin >> s;
	int n = strlen(s);

	long long int ans = 0, sum = 0, temp = 0;
	for (int i = 0; i < (1 << n-1); i++) {
		sum = 0;
		temp = s[0] - '0';
		for (int j = 0; j < n-1; j++) {
			if (i >> j & 1) {
				sum += temp;
				temp = s[j + 1] - '0';
			}
			else {
				temp = temp * 10 + s[j + 1] - '0';
			}
		}
		sum += temp;
		ans += sum;
	}
	printf("%lld", ans);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
const long int maxN = 1e5 + 1;
 
bool can = false;
 
vector<bool> visited;

void dfs(int sum, int x)
{
	if(visited[sum]) return;
	if(sum > x)
		return;
	else if(sum < x)
	{
		visited[sum] = true;
		dfs(sum + 100, x);
		dfs(sum + 101, x);
		dfs(sum + 102, x);
		dfs(sum + 103, x);
		dfs(sum + 104, x);
		dfs(sum + 105, x);
	}
	else
	{
		can = true;
		return;
	}
}
 
int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int x;
	cin >> x;
	visited.assign(maxN, false);
	dfs(0, x);
	if(can)
		printf("1\n");
	else
		printf("0\n");
	return 0;
}

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

#define REP(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define rep(i, n) REP (i, 0, n)
#define mset(a, n) memset(a, n, sizeof(a))

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pair<int, int> > vpii;

const int INF = 1000000000;
const int MOD = 1000000007;
const double EPS = 1e-8;

int main() {
	int n;
	while (cin >> n, n) {
		int a[n], ans = -10000000;
		rep (i, n) cin >> a[i];
		int dp[n];
		dp[0] = a[0];
		REP (i, 1, n) {
			// dp[i] = dp[i - 1] + a[i];
			dp[i] = max(dp[i - 1] + a[i], a[i]);
		}
		rep(i, n) {
			ans = max(ans, dp[i]);
		}
		cout << ans << endl;
	}
}

Measured memory_bytes: 1184
A = ["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"]

K = int(input())

print(A[K-1])


Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int l,d,n;
	cin>>l>>d>>n;
	int ctr=0;
	for(int i=l;i<=d;i++)
	{
		if(i%n==0)
		{
			ctr++;
		}
	}
	cout<<ctr<<endl;
}

Measured memory_bytes: 3632
MOD=10**9
from decimal import Decimal
import sys
input=sys.stdin.readline
    
def w(i,m):
    cnt=0
    while(i>0 and i%m==0):
        i//=m
        cnt+=1
    return cnt

N=int(input())
A=[int(Decimal(input())*Decimal(MOD)) for i in range(N)]
dic=[{} for i in range(N)]
dp=[[0]*51 for i in range(51)]

for i in range(N):
    dic[i][2],dic[i][5]=w(A[i],2),w(A[i],5)
    dp[dic[i][2]][dic[i][5]]+=1

for i in reversed(range(51)):
    for j in reversed(range(51)):
        if i==50 and j==50:
            continue
        if i==50:
            dp[i][j]+=dp[i][j+1]
        elif j==50:
            dp[i][j]+=dp[i+1][j]
        else:
            dp[i][j]+=dp[i][j+1]+dp[i+1][j]-dp[i+1][j+1]
ans=0

for i in range(N):
    t,f=max(18-dic[i][2],0),max(18-dic[i][5],0)
    res=dp[t][f]
    if t<=dic[i][2] and f<=dic[i][5]:
        res-=1
    ans+=res
print(ans//2)

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

int main()
{
	int n, k;
	cin>>n>>k;
	vector<int> A(n, 0);
	for(int i = 0;i<n;i++)
		cin>>A[i];

	vector<int> dp(n ,0);

	dp[0] = 0,dp[1] = abs(A[1]-A[0]);

	int ans;
	for(int i = 2;i<n;i++)
	{
		ans = INT_MAX;
		for(int j = i-1; j>=0 && j>= i-k;j--)
		{
			ans = min(ans, dp[j]+abs(A[j]-A[i]));
		}

		dp[i] = ans;
	}

	cout<<dp[n-1]<<endl;
}

Measured memory_bytes: 1024