akhauriyash/Code-Regression huggingface dataset:
import java.io.*;
import java.util.*;

public class Main {
    FastScanner in;
    PrintWriter out;

    void solve() {
        int n = in.nextInt();
        TreeMap<Integer, Integer> count = new TreeMap<>();
        for (int i = 0; i < n; i++) {
            int x = in.nextInt();
            count.put(x, count.getOrDefault(x, 0) + 1);
        }
        int res = 0;
        while (!count.isEmpty()) {
            Map.Entry<Integer, Integer> entry = count.pollLastEntry();
            if (entry.getValue() != 1) {
                count.put(entry.getKey(), entry.getValue() - 1);
            }
            int pw2 = 1;
            while (pw2 <= entry.getKey()) {
                pw2 *= 2;
            }
            int need = pw2 - entry.getKey();
            Integer got = count.get(need);
            if (got != null) {
                res++;
                if (got.equals(1)) {
                    count.remove(need);
                } else {
                    count.put(need, got - 1);
                }
            }
        }
        out.println(res);
    }

    void run() {
        try {
            in = new FastScanner(new File("Main.in"));
            out = new PrintWriter(new File("Main.out"));

            solve();

            out.close();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }

    void runIO() {

        in = new FastScanner(System.in);
        out = new PrintWriter(System.out);

        solve();

        out.close();
    }

    class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner(File f) {
            try {
                br = new BufferedReader(new FileReader(f));
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
        }

        public FastScanner(InputStream f) {
            br = new BufferedReader(new InputStreamReader(f));
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                String s = null;
                try {
                    s = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (s == null)
                    return null;
                st = new StringTokenizer(s);
            }
            return st.nextToken();
        }

        boolean hasMoreTokens() {
            while (st == null || !st.hasMoreTokens()) {
                String s = null;
                try {
                    s = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (s == null)
                    return false;
                st = new StringTokenizer(s);
            }
            return true;
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }
    }

    public static void main(String[] args) {
        new Main().runIO();
    }
}

Measured memory_bytes: 59628
import itertools as ite
N=int(input())
C=[0]*6
J="MARCH"
for i in range(N):
    C[J.find(input()[0])]+=1
ans=0
for i,j,k in list(ite.combinations(range(5),3)):
    ans+=C[i]*C[j]*C[k]
print(ans)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
int main() {
  int n;
  cin >> n;
  vector<int> p(n);
  REP(i, n) {
    cin >> p.at(i);
  }
  vector<int> subp(3);
  int count = 0;
  vector<int> subr(3);
  REP(i, n - 2) {
    subp.at(0) = p.at(i);
    subp.at(1) = p.at(i + 1);
    subp.at(2) = p.at(i + 2);
    subr = subp;
    sort(subr.begin(), subr.end());
    if (subr.at(1) == subp.at(1)) {
      count++;
    }
  }
  cout << count << endl;
}

Measured memory_bytes: 256
ret = []
while True:
    x = raw_input().split()
    if int(x[0]) == int(x[1]) == 0: break

    if int(x[0]) > int(x[1]):
        ret += ['%s %s' % (x[1], x[0])]
    else:
        ret += ['%s %s' % (x[0], x[1])]

for x in ret:
    print(x)

Measured memory_bytes: 6280
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
using static System.Math;

public static class P
{
    public static void Main()
    {
        int q = int.Parse(Console.ReadLine());
        Node root = null;
        HashSet<int> keys = new HashSet<int>();
        for (int i = 0; i < q; i++)
        {
            var query = Console.ReadLine().Split();
            if (query[0] == "print")
            {
                Console.WriteLine(" " + string.Join(" ", Node.GetInOrderWalk(root)));
                Console.WriteLine(" " + string.Join(" ", Node.GetPreOrderWalk(root)));
                continue;
            }
            var key = int.Parse(query[1]);
            if (query[0] == "insert")
            {
                keys.Add(key);
                var z = new Node() { Key = key };
                {
                    Node y = null;
                    Node x = root;
                    while (x != null)
                    {
                        y = x;
                        x = z.Key < x.Key ? x.Left : x.Right;
                    }
                    if (y == null) root = z;
                    else if (z.Key < y.Key) y.Left = z;
                    else y.Right = z;
                }
                continue;
            }

            var node = root;
            while (node != null && node.Key != key)
            {
                if (key < node.Key) node = node.Left;
                else node = node.Right;
            }
            Console.WriteLine(node != null ? "yes" : "no"); ;
        }
    }
}


class Node
{
    public int Key;
    public Node Left;
    public Node Right;

    public static IEnumerable<int> GetInOrderWalk(Node node) =>
        node == null ?
        Enumerable.Empty<int>() :
        GetInOrderWalk(node.Left)
        .Concat(new[] { node.Key })
        .Concat(GetInOrderWalk(node.Right));

    public static IEnumerable<int> GetPreOrderWalk(Node node) =>
        node == null ?
        Enumerable.Empty<int>() :
        new[] { node.Key }
        .Concat(GetPreOrderWalk(node.Left))
        .Concat(GetPreOrderWalk(node.Right));
}



Measured memory_bytes: 199296
k = int(input())
hoge = input().split()
A,B = int(hoge[0]), int(hoge[1])

ans = 0
huga = 0
for i in range(B):
  ans += k
  if A<=ans and ans <= B:
    huga = 1
    break

if huga == 1:
  print("OK")
else:
  print("NG")

Measured memory_bytes: 9180
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using ld = long double;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
const int INF = 100010001;
const ll LINF = (ll)INF*INF*10;

int main() {
    int n, u, v;
    cin >> n >> u >> v;
    --u; --v;
    swap(u, v);
    vvi G(n);
    rep(i, n-1) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    queue<int> q;
    q.push(u);
    vi kuo(n, -1);
    kuo[u] = 0;
    while(!q.empty()) {
        int now = q.front();
        q.pop();

        for(int ne:G[now]) {
            if(kuo[ne] == -1) {
                kuo[ne] = kuo[now]+1;
                q.push(ne);
            }
        }
    }

    int num = kuo[v];
    if(num == 1) {
        cout << 0 << endl;
        return 0;
    }
    while(kuo[v] != num/2+1) {
        for(int ne:G[v]) {
            if(kuo[ne] == kuo[v]-1) {
                v = ne;
                break;
            }
        }
    }


    q.push(v);
    int kk = 0;
    while(!q.empty()) {
        int now = q.front();
        q.pop();
        kk = kuo[now];

        for(int ne:G[now]) {
            if(kuo[ne] == kuo[now] + 1) {
                q.push(ne);
            }
        }
    }

    kk--;

    cout << kk << endl;
}

Measured memory_bytes: 6272
<?php
list($H, $W, $N) = array_map("intval", explode(" ", trim(fgets(STDIN))));
list($y, $x) = array_map("intval", explode(" ", trim(fgets(STDIN))));
$S = trim(fgets(STDIN));
$T = trim(fgets(STDIN));

echo isOK("R", "L", $W, $x) && isOK("D", "U", $H, $y) ? "YES" : "NO";

function isOK($inc, $dec, $size, $current){
    global $S, $T;
    $max = $size;
    $min = 1;
    for($i = strlen($S)-1; $i>=0; $i--){
        if($T[$i] == $dec)$max = min($max+1, $size);
        if($T[$i] == $inc)$min = max($min-1, 1);
        if($S[$i] == $inc)$max = $max-1;
        if($S[$i] == $dec)$min = $min+1;
        if($max<$min)return false;
    }
    return $min <= $current && $current <= $max;
}


Measured memory_bytes: 4728
from sys import stdin


def main() -> None:
    s, t = [next_str() for _ in range(2)]
    print("Yes" if sorted(s) < (sorted(t, reverse=True)) else "No")


def next_str() -> str:
    result = ""
    while True:
        tmp = stdin.read(1)
        if tmp.strip() != "":
            result += tmp
        elif tmp != '\r':
            break
    return result


if __name__ == '__main__':
    main()

Measured memory_bytes: 3060
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <tuple>
#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, a, b, c;
    cin >> x >> y >> a >> b >> c;

    vl v;

    vl p(a);
    rep(i, a) {
        cin >> p[i];
    }
    sort(rall(p));
    rep(i, x) {
        v.pb(p[i]);
    }

    vl q(b);
    rep(i, b) {
        cin >> q[i];
    }
    sort(rall(q));
    rep(i, y) {
        v.pb(q[i]);
    }

    rep(i, c) {
        ll r;
        cin >> r;
        v.pb(r);
    }
    sort(rall(v));

    ll ans = 0;
    rep(i, x+y) {
        ans += v[i];
    }
    
    out(ans);
    re0;
}

Measured memory_bytes: 7664
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		long A = in.nextLong();
		long B = in.nextLong();
		long K = in.nextLong();
		in.close();
		if (A >= K) {
			System.out.println((A - K) + " " + B);
			return;
		} else {
			K -= A;
		}

		if (B >= K) {
			System.out.println(0 + " " + (B - K));
		} else {
			System.out.println(0 + " " + 0);
		}
	}
}

Measured memory_bytes: 23380
#include<iostream>
#include<string>
#include<map>
using namespace std;
typedef long long ll;
const int Max = 1e5 + 5;
int lst[Max];

int main()
{
	ll x, y;
	cin >> y >> x;
	ll res = 1e18+5;
	for (int i = 1;i <= x - 1;i++)
	{
		ll a = (x - i) * y;
		ll b = i * (y / 2);
		ll c = x * y - a - b;
		res = min(res, max(a, max(b, c)) - min(a, min(b, c)));
		a = i * y;
		b = (x - i) / 2 * y;
		c = x * y - a - b;
		res = min(res, max(a, max(b, c)) - min(a, min(b, c)));
	}
	for (int i = 1;i <= y - 1;i++)
	{
		ll a = (y - i) * x;
		ll b = i * (x / 2);
		ll c = x * y - a - b;
		res = min(res, max(a, max(b, c)) - min(a, min(b, c)));
		a = i * x;
		b = (y - i) / 2 * x;
		c = x * y - a - b;
		res = min(res, max(a, max(b, c)) - min(a, min(b, c)));
	}
	cout << res;
}

Measured memory_bytes: 3108
#include <bits/stdc++.h>
#define simplify ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
#define endl "\n"
using namespace std;

const int N=2e6+5;
const int mod=1e9+7;
int fact[N];
int invFact[N];
int inverseMod(int x,int mod);

void precompute(){
    fact[0]=fact[1]=1;

    for(int i=2;i<N;i++){
        fact[i]=fact[i-1]*i;
        fact[i]%=mod;
    }
    invFact[N-1]=inverseMod(fact[N-1],mod);

    for(int i=N-2;i>=0;i--){
        invFact[i]=invFact[i+1]*(i+1);
        invFact[i]%=mod;
    }
}
int NCR(int n,int r){

    if(r>n)return 0;
    int num=fact[n];
    num*=invFact[r];
    num%=mod;
    num*=invFact[n-r];
    num%=mod;
    return num;
}
int NCR2(int n,int r){

    if(r>n)return 0;
    int ans=fact[n];
    ans*=inverseMod(fact[r],mod);
    ans%=mod;
    ans*=inverseMod(fact[n-r],mod);
    ans%=mod;
    return ans;
}

int power(int x,int n,int mod){
    //(x^n)%mod
    int result=1;
    while(n){
        if(n%2)
            result=(result*x)%mod;
        x=(x*x)%mod;
        n/=2;
    }
    return result;
}

int inverseMod(int x,int mod){
    return power(x,mod-2,mod);
}




int32_t main() {

    simplify
    precompute();
    int k,n;
    string s;
    cin>>k;
    cin>>s;

    n=s.size()+k;

    int ans=power(26,n,mod);
    int sub=0;
    for(int i=0;i<s.size();i++){
        int add=NCR2(n,i)*power(25,n-i,mod);
        add%=mod;
        sub+=add;
        sub%=mod;
    }
    ans=(ans-sub+mod)%mod;
    cout<<ans<<endl;



    return 0;
}


Measured memory_bytes: 35508
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;

int main()
{
	int n,a,b,c,d;
	scanf("%d",&n);
	if(n>=1000 && n<=9999)
	{
		b=n%1000%100%10;
		c=n%1000%100/10;
		b=n%1000/100;
		a=n/1000;
		if(a == b && b == c || a == b && b ==c && c == d)
			printf("Yes\n");
		else if(b == c && c == d)
			printf("Yes\n");
        else 
        	printf("No\n");
    }
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
#define abs(n) ((n) >= 0 ? (n) : -1 * (n))

bool psb(int t, int x, int y)
{
    if(t % 2 == (x+y) % 2 && t >= (x+y)) return 1;
    else return 0;
}

int main()
{
    int n, bt = 0, bx = 0, by = 0, t, x, y;
    cin >> n;
    for(int i = 0; i < n; i++){
        scanf("%d%d%d", &t, &x, &y);
        if(psb(abs(t-bt), abs(x-bx), abs(y-by)) == 0){
            cout << "No" << endl;
            return 0;
        }
        bt = t; bx = x; by = y;
    }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 256
n=int(input())
a,b=map(int,input().split())
p=list(map(int,input().split()))
x,y,z=0,0,0
for i in p:
  if i<=a:
    x+=1
  elif i<=b:
    y+=1
  else:
    z+=1
print(min(x,y,z))

Measured memory_bytes: 3064
#include<iostream>
#include<string>
#include<set>
using namespace std;

int main() {
	string s;
	cin >> s;
	string t = "abcdefghijklmnopqrstuvwxyz";
	set<char>scr;
	string ans = "None";
	for (int i = 0;i < s.size();i++) {
		scr.insert(s.at(i));
	}
	for (int i = 0;i < 26;i++) {
		if (scr.find(t.at(i))==scr.end()) {
			ans = t[i];
			break;
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 512
#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>>pppp(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;
  cin>>N;
  vector<int>A(N+2);
  for(int i=1;i<=N;i++){
    cin>>A[i];
  }
  int sum=0;
  for(int i=0;i<=N;i++){
    sum+=abs(A[i+1]-A[i]);
  }
  for(int i=1;i<=N;i++){
    int disp=A[i]-A[i-1];
    int disn=A[i+1]-A[i];
    cout<<sum+abs(A[i+1]-A[i-1])-(abs(disp)+abs(disn))<<endl;
  }
 return 0;
}

Measured memory_bytes: 3744
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <utility>

using namespace std;

int main() {
    int N, M, X;
    cin >> N >> M >> X;
    int A[M];
    int cost[N+1] = {};
    for (int i = 0; i < M; i++) {
        cin >> A[i];
        cost[A[i]] = 1;
    }

    int left = 0;
    for (int i = 0; i < X; i++) {
        left += cost[i];
    }
    int right = 0;
    for (int i = X+1; i <= N; i++) {
        right += cost[i];
    }

    cout << min(left, right) << endl;
    

    
}

Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>

using ll = long long int;
const int INF = (1<<30);
const ll INFLL = (1ll<<60);
const ll MOD = (ll)(1e9+7);

#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	a = (a<MOD)?a:(a-MOD);
	b = (b<MOD)?b:(b-MOD);
	a += b;
	a = (a<MOD)?a:(a-MOD);
}

int main(void){
	std::string s;
	std::cin >> s;
	s[1] = 'B'+'R'-s[1];
	std::cout << s << std::endl;
	return 0;
}


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


int main(){
  int N;
  cin >> N;
  vector<int> P(N*N);
  for(auto& p : P){
    cin >> p;
  }
  vector<vector<int>> C(N, vector<int>(N));
  vector<vector<int>> D(N, vector<int>(N, 1));
  int l=0, r=N;
  while(l<r){
    for(int ii=l; ii<r; ii++){
      C[l][ii] = l+1;
      C[r-1][ii] = l+1;
      C[ii][l] = l+1;
      C[ii][r-1] = l+1;
    }
    l++;
    r--;
  }

  int ans = 0;
  for(auto& p : P){
    int row = (p-1)/N;
    int col = (p-1)%N;
    ans += C[row][col]-1;
    C[row][col]--;
    D[row][col]=0;
    queue<pair<int, int>> q;
    q.push({row, col});
    vector<pair<int, int>> moves = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    while(q.size()){
      auto current = q.front();
      q.pop();
      for(auto m : moves){
        int next_x = current.first+m.first;
        int next_y = current.second+m.second;
        if(0<=next_x && next_x<N && 0<=next_y && next_y<N){
          int tmp = C[current.first][current.second]+D[next_x][next_y];
          for(auto m2 : moves){
            if(0<=next_x+m2.first && next_x+m2.first<N && 0<=next_y+m2.second && next_y+m2.second<N){
              tmp = min(C[next_x+m2.first][next_y+m2.second]+D[next_x][next_y], tmp);
            }
          }
          if(tmp < C[next_x][next_y]){
            C[next_x][next_y]=tmp;
            q.push({next_x, next_y});
          }
        }
      }
    }
  }
  cout << ans << endl;
  
  return 0;
}


Measured memory_bytes: 6088
#include <iostream>
using namespace std;

int main()
{
    int a,b;
    cin >>a>>b;

    if(a > b){
        cout<<"a > b"<<endl;
    }else if(a < b){
        cout<<"a < b"<<endl;
    }else{
        cout<<"a == b"<<endl;
    }
    
    return 0;
}

Measured memory_bytes: 1156
N = int(input())
S = [int(i) for i in input().split()]

def solve() :
    S.sort()
    par = [S.pop()]
    rst = S
    for _ in range(N) :
        n_par = []
        n_rst = []
        
        for p in par[::-1] :
            flg = True
            while rst :
                if rst[-1] < p :
                    n_par.append(rst.pop())
                    flg = False
                    break
                else :
                    n_rst.append(rst.pop())
            if flg :
                return 'No'
                
        par += n_par
        par.sort()
        rst += n_rst
        rst.sort()
            
    return 'Yes'
    
print(solve())

Measured memory_bytes: 133932
def i():
	return int(input())
def i2():
	return map(int,input().split())
def s():
	return str(input())
def l():
	return list(input())
def intl():
	return list(int(k) for k in input().split())


x1,y1,x2,y2= i2()
x3 = x2 - (y2 - y1)
y3 = y2 + (x2 - x1)
x4 = x3 - (y3 - y2)
y4 = y3 + (x3 - x2)
print(x3,y3,x4,y4)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n; cin >> n;
  int mn, mx;
  cin >> mn; mx = mn;
  for (int i = 1; i < n; i++) {
    int t; cin >> t;
    mn = min(mn, t);
    mx = max(mx, t);
  }
  cout << mx - mn << endl;
}

Measured memory_bytes: 256
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 modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)


def C(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res


def main():
    s = ni()
    mod = 10 ** 9 + 7
    ans = [0] * 2001
    ans[0] = 1
    for i in range(3, 6):
        ans[i] = 1
    for i in range(6, s + 1):
        ans[i] = (ans[i - 1] + ans[i - 3]) % mod
    print(ans[s])


if __name__ == '__main__':
    main()


Measured memory_bytes: 9252
import java.util.*;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int h = sc.nextInt();
		int w = sc.nextInt();
		char[][] field = new char[h][];
		for (int i = 0; i < h; i++) {
		    field[i] = sc.next().toCharArray();
		}
		for (int i = 0; i < h; i++) {
		    for (int j = 0; j < w; j++) {
		        if (field[i][j] == '.') {
		            continue;
		        }
		        int count = 0;
		        if (i != 0 && field[i - 1][j] == '#') {
		            count++;
		        }
		        if (i != h - 1 && field[i + 1][j] == '#') {
		            count++;
		        }
		        if (j != 0 && field[i][j - 1] == '#') {
		            count++;
		        }
		        if (j != w - 1 && field[i][j + 1] == '#') {
		            count++;
		        }
		        if (count == 0) {
		            System.out.println("No");
		            return;
		        }
		    }
		}
        System.out.println("Yes");
	}
}


Measured memory_bytes: 23116
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int a = scan.nextInt();
		boolean hantei =false;

		for(int i=0;i<=a;i++) {
			int nokori = n-i;
			if(nokori%500==0) {
				hantei = true;
				break;
			}else {
				continue;
			}
		}
		if(hantei==true) {
			System.out.println("Yes");
		}else {
			System.out.println("No");
		}

	}

}


Measured memory_bytes: 21844
#include<bits/stdc++.h>
using namespace std;
struct card{
  string input;
  int value;
  int num;
};

void BubbleSort(card *,int);
void SelectionSort(card *,int);

int main(){
  int i,j,n;
  card c[36],b[36];
  
  cin>>n;
  for(i=0;i<n;i++){
    cin>>c[i].input;
    c[i].num=i;
    b[i].num=i;
    b[i].input=c[i].input;
    c[i].value=c[i].input[1]-'0';
    b[i].value=c[i].value;
  }
  BubbleSort(c,n);
  SelectionSort(b,n);
  return 0;
}

void BubbleSort(card c[],int n){
  int i,j,count=0;
  for(i=0;i<n;i++){
    for(j=n-1;j>i;j--){
      if(c[j].value<c[j-1].value)swap(c[j],c[j-1]);
    }
  }
  for(i=0;i<n-1;i++)if((c[i].value==c[i+1].value)&&(c[i].num>c[i+1].num))count++;
  for(i=0;i<n;i++){
    if(i==n-1)cout<<c[i].input;
    else cout<<c[i].input<<" ";
  }
  cout<<endl;
  if(count==0)cout<<"Stable"<<endl;
  else cout<<"Not stable"<<endl;
}

void SelectionSort(card c[],int n){
  int i,j,minj,count=0;
  for(i=0;i<n;i++){
    minj=i;
    for(j=i;j<n;j++)if(c[j].value<c[minj].value)minj=j;
    swap(c[i],c[minj]);
  }
  for(i=0;i<n-1;i++)if((c[i].value==c[i+1].value)&&(c[i].num>c[i+1].num))count++;
  for(i=0;i<n;i++){
    if(i==n-1)cout<<c[i].input;
    else cout<<c[i].input<<" ";
  }
  cout<<endl;
  if(count==0)cout<<"Stable"<<endl;
  else cout<<"Not stable"<<endl;
}



Measured memory_bytes: 3128
n,q=map(int,input().split())
e=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(lambda x:int(x)-1,input().split())
  e[a].append(b)
  e[b].append(a)
ps=[0 for i in range(n)]
for i in range(q):
  p,x=map(int,input().split())
  ps[p-1]+=x

s=[-1 for i in range(n)]
sc=[0]
s[0]=0
while sc:
  nsc=[]
  for i in sc:
    s[i]+=ps[i]
    for j in e[i]:
      if s[j]==-1:
        nsc.append(j)
        s[j]=s[i]
  sc=nsc

r=""
for i in range(n):
  r+=str(s[i])+" "
print(r[:-1])

Measured memory_bytes: 65288
s = input()

V = ["dream", "dreamer", "erase", "eraser"]

t = len(s)
hiki = 1
while t > 0 and hiki == 1:
    hiki = 0
    for i in range(len(V)):
        # print(len(V[i]), s[:t], s[t-len(V[i]):t], V[i])
        if t >= len(V[i]) and s[t-len(V[i]):t] == V[i]:
            t -= len(V[i])
            hiki = 1

if t == 0:
    print("YES")
else:
    print("NO")

Measured memory_bytes: 40304
/*
 * 2518.cc: B2D
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 10;

/* typedef */

typedef set<string> ss;

/* global variables */

/* subroutines */

bool cmphalf(const string &s) {
  int l = s.size(), lh = l >> 1;
  for (int i = 0, j = lh; i < lh; i++, j++)
    if (s[i] != s[j]) return false;
  return true;
}

/* main */

int main() {
  int n;
  string s;
  cin >> n >> s;
  int slen = s.size();

  int cnt = 0;
  
  for (int k = 1; k <= n; k++) {
    int l = 1 << k, lh = l >> 1;
    ss sts;

    for (int i = 0; i < slen; i += l) sts.insert(s.substr(i, l));

    int cntk = 0;
    for (ss::iterator sit = sts.begin(); sit != sts.end(); sit++) {
      if (! cmphalf(*sit)) cntk++;
    }
    cnt += cntk;

    //printf("%d: %d\n", k, cntk);
  }

  printf("%d\n", cnt);
  return 0;
}

Measured memory_bytes: 1244
#include<bits/stdc++.h>
#define rep(i,n)for(ll i=0;i<n;i++)
using namespace std;
typedef long long ll;
typedef pair<ll, ll>P;

ll X[40], Y[40];
ll len[2];
P h[2][15000000];
void dfs(ll idx, ll s, ll g, ll x, ll y) {
	if (s == g) {
		h[idx][len[idx]++] = P(x, y);
		return;
	}
	dfs(idx, s + 1, g, x + X[s], y + Y[s]);
	dfs(idx, s + 1, g, x - X[s], y - Y[s]);
	dfs(idx, s + 1, g, x, y);
}
int main() {
	ll n, d; scanf("%lld%lld", &n, &d);
	rep(i, n)scanf("%lld%lld", &X[i], &Y[i]);
	dfs(0, 0, n / 2, 0, 0);
	dfs(1, n / 2, n, 0, 0);
	sort(h[0], h[0] + len[0], greater<>());
	sort(h[1], h[1] + len[1]);
	ll s = 0, t = 0;
	deque<P>que;
	ll Max = LLONG_MIN;
	rep(i, len[0]) {
		for (; t < len[1] && h[1][t].first <= d - h[0][i].first; t++) {
			while (!que.empty() && que.back().second < h[1][t].second)
				que.pop_back();
			que.emplace_back(h[1][t]);
		}
		for (; s < len[1] && h[1][s].first < -d - h[0][i].first; s++) {
			if (!que.empty() && que.front() == h[1][s])que.pop_front();
		}
		if (!que.empty())
			Max = max(Max, h[0][i].second + que.front().second);
	}
	printf("%lld\n", Max);
}

Measured memory_bytes: 451696
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int N;
    cin >> N;
    vector <pair <int, int> > idx_num(N);
    for (int i = 0; i < N; ++i) {
        int a;
        cin >> a;
        idx_num[i] = make_pair(a, i+1);
    }
    sort(idx_num.begin(), idx_num.end());
    for (int i = 0; i < N; ++i) {
        cout << idx_num[i].second << " ";
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 1536
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

# 2点間の距離の平均を求めればよい

MOD = 10**9 + 7

N,M,K = map(int,read().split())

def cumprod(arr,MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr,Lsq**2).reshape(Lsq,Lsq)
    for n in range(1,Lsq):
        arr[:,n] *= arr[:,n-1]; arr[:,n] %= MOD
    for n in range(1,Lsq):
        arr[n] *= arr[n-1,-1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U,MOD):
    x = np.arange(U,dtype=np.int64); x[0] = 1
    fact = cumprod(x,MOD)
    x = np.arange(U,0,-1,dtype=np.int64); x[0] = pow(int(fact[-1]),MOD-2,MOD)
    fact_inv = cumprod(x,MOD)[::-1]
    return fact,fact_inv

U = 10**6
fact, fact_inv = make_fact(U,MOD)

coef = fact[N*M-2] * fact_inv[K-2] % MOD * fact_inv[N*M-K] % MOD

x = (N-1)*N*(N+1)*M*M//6
y = (M-1)*M*(M+1)*N*N//6
answer = coef * ((x+y) % MOD) % MOD
print(answer)

Measured memory_bytes: 51520
/*************************
author : coldbeer
2019-06-01 7:31:14 pm IST
*************************/
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
    int n; cin >> n;
    cout << (n - 2) * 180 << endl;
	return 0;
}


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

#define fi first
#define se second
#define pb push_back
#define mod(n,k) ( ( ((n) % (k)) + (k) ) % (k))
#define forn(i,a,b) for(int i = a; i < b; i++)
#define forr(i,a,b) for(int i = a; i >= b; i--)
#define all(x) (x).begin(), (x).end()

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int N,K; cin >> N >> K;
	ll sum = 0;
	vi A(N);
	for(auto &x : A)cin >> x;
	sort(all(A));
	forn(i,0,K)sum += A[i];
	cout << sum << '\n';
	return 0;
}
/*
__builtin_mul_overflow(x,y,&x)
-fsplit-stack
*/


Measured memory_bytes: 3620
#include <stdio.h>
#include <stdlib.h>
#define SIZE 1001

int main(void){
  int N, K, p[SIZE], i, j, tmp, ans = 0;
  scanf("%d %d", &N, &K);
  for(i = 0; i < N; i++){
  	scanf(" %d", &p[i]);
  }
  for(i = 0; i < N - 1; i++){
    for(j = i+1; j < N; j++){
      if(p[i] > p[j]){
        tmp = p[i];
        p[i] = p[j];
        p[j] = tmp;
      }
    }
  }
  for(i = 0; i < K; i++)ans += p[i];
  printf("%d", ans);
  return 0;
}

Measured memory_bytes: 1716
#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,X,Y;
  cin>>N>>K>>X>>Y;
  if(N<=K){cout<<X*N<<endl;}
  else{cout<<X*K+(N-K)*Y<<endl;}
  
  return 0;
}

Measured memory_bytes: 3592
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <set>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iterator>
#include <bitset>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <iomanip>
#include <cassert>
//#include <utility>
//#include <memory>
//#include <functional>
//#include <deque>
//#include <cctype>
//#include <ctime>
//#include <numeric>
//#include <list>
//#include <iomanip>

//#if __cplusplus >= 201103L
//#include <array>
//#include <tuple>
//#include <initializer_list>
//#include <forward_list>
//
//#define cauto const auto&
//#else

//#endif

using namespace std;


typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;

#define VV(T) vector<vector< T > >

template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
    v.assign(a, vector<T>(b, t));
}

template <class F, class T>
void convert(const F &f, T &t){
    stringstream ss;
    ss << f;
    ss >> t;
}

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define reep(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) reep((i),0,(n))
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define F first
#define S second
#define mkp make_pair
#define RALL(v) (v).rbegin(),(v).rend()
#define DEBUG
#ifdef DEBUG
#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#else
#define dump(x) 
#define debug(x) 
#endif
#define LDcout(x,n) fixed<<setprecision(n)<<x

#define MOD 1000000007LL
#define EPS 1e-8
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
#define maxs(x,y) x=max(x,y)
#define mins(x,y) x=min(x,y)

string s;
vector<string> ans;
bool check(string a){
    rep(i,25){
        rep(j,a.size()){
            if(a[j]=='b'+i){
                a[j]--;
                break;
            }
        }
    }
    if(a==s.substr(0,a.size())) return true;
    return false;
}

void foo(string t){
    if(t.size()==s.size()){
        if(check(t)) ans.PB(t);
        return;
    }
    int pos=t.size();
    string tmp=t+s[pos];
    if(check(tmp)) foo(tmp);
    tmp.back()++;
    if(check(tmp)) foo(tmp);
}


void mainmain(){
    while(cin>>s){
        if(s=="#") return;
        ans=vector<string>(0);
        foo("");
        sort(ALL(ans));
        ans.erase(unique(ALL(ans)),ans.end());
        if(ans.size()<10){
            cout<<ans.size()<<endl;
            rep(i,ans.size()){
                cout<<ans[i]<<endl;
            }
        }
        else{
            cout<<ans.size()<<endl;
            rep(i,5) cout<<ans[i]<<endl;
            reep(i,ans.size()-5,ans.size()) cout<<ans[i]<<endl;
        }
    }
}


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
      cout<<fixed<<setprecision(20);
    mainmain();
}

Measured memory_bytes: 2584
from fractions import gcd

n,m=map(int,input().split())
s=input()
t=input()
x=gcd(n,m)
l=n*m//gcd(n,m)
for i in range(x):
    if s[i*(n//x)]!=t[i*(m//x)]:
        print(-1)
        exit()
print(l)

Measured memory_bytes: 5432
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cctype>

#include <algorithm>
#include <functional>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <iostream>
#include <limits>
#include <numeric>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

struct Node {
    int u;
    ll step;

    Node(int u, ll step) : u(u), step(step) {}

    bool operator>(const Node& rhs) const { return step > rhs.step; }
};

struct Edge {
    int v, w;
    Edge* next;
};

const int N = 100010, M = 200010;

int n, m;
int s, t, a, b;
ll ans;
Edge* g[N];
bool vis[N];
ll diss[N], disa[N], disb[N], da[N], db[N];

void adde(int u, int v, int w);
void runspt(int s, ll* dis);
void dfs(int u);

int main() {
    scanf("%d%d%d%d%d%d", &n, &m, &s, &t, &a, &b);
    while (m--) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        adde(u, v, w);
        adde(v, u, w);
    }
    runspt(a, disa);
    ans = disa[b];
    if (disa[s] != -1) {
        runspt(b, disb);
        runspt(s, diss);
        dfs(t);
    }
    printf("%lld\n", ans);
    return 0;
}

void dfs(int u) {
    if (vis[u])
        return;
    vis[u] = true;
    da[u] = disa[u];
    db[u] = disb[u];
    for (Edge* p = g[u]; p; p = p->next)
        if (diss[p->v] + p->w == diss[u]) {
            dfs(p->v);
            da[u] = min(da[u], da[p->v]);
            db[u] = min(db[u], db[p->v]);
        }
    ans = min(ans, min(da[u] + disb[u], db[u] + disa[u]));
}

void runspt(int s, ll* dis) {
    memset(dis, -1, sizeof(ll) * (n + 1));
    priority_queue<Node, vector<Node>, greater<Node>> q;
    q.emplace(s, dis[s] = 0);
    while (!q.empty()) {
        Node tmp = q.top();
        q.pop();
        if (tmp.step != dis[tmp.u])
            continue;
        for (Edge* p = g[tmp.u]; p; p = p->next)
            if (dis[p->v] == -1 || dis[p->v] > tmp.step + p->w)
                q.emplace(p->v, dis[p->v] = tmp.step + p->w);
    }
}

void adde(int u, int v, int w) {
    static Edge pool[M * 2];
    static Edge* p = pool;
    p->v = v;
    p->w = w;
    p->next = g[u];
    g[u] = p;
    ++p;
}


Measured memory_bytes: 16444
#include <bits/stdc++.h>
#define SIZE 300005
#define MOD 1000000007LL
#define INF 1 << 29
#define LLINF 1LL << 60
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define DOWN(i,b,a) for(int i=b;i>=a;i--)
#define SET(a,c) memset(a,c,sizeof a)
#define BIT(i,j) ((i)>>(j))&1
#define ALL(o) (o).begin(), (o).end()
#define ERASE(o) (o).erase(unique((o).begin(),(o).end()), (o).end())
#define SQ(x) ((x)*(x))
using namespace std;
typedef long long ll;
typedef pair<ll,ll> Pll;
typedef pair<int, int> Pii;
typedef pair<double, double> Pdd;
typedef complex<double> dcomplex;
template<typename T> inline void priv(vector<T>a){REP(i,a.size()){cerr<<a[i]<<((i==a.size()-1)?"\n":" ");}}
ll gcd(ll a,ll b){int c=max(a,b);int d=min(a,b);return c==0||d==0?c:gcd(c%d,d);}
ll lcm(ll a,ll b){return a==0||b==0?0:a*b/gcd(a,b);}
ll fact(ll a){ll b=1;FOR(i,1,a)b*=i;return b;}

class P
{
public:
  double x,y;
  P(){};P(double x,double y):x(x),y(y){};
  P operator+(const P&q){P t;t.x=x+q.x;t.y=y+q.y;return t;}
  P operator+=(const P&q){x+=q.x;y+=q.y;return *this;}
  P operator-(const P&q){P t;t.x=x-q.x;t.y=y-q.y;return t;}
  P operator-=(const P&q){x-=q.x;y-=q.y;return *this;}
  template<typename T> P operator*(T d){return P(x*d,y*d);}
  template<typename T> P operator*=(T d){x*=d;y*=d;return *this;}
  template<typename T> P operator/(T d){return P(x/d,y/d);}
  template<typename T> P operator/=(T d){x/=d;y/=d;return *this;}
  bool operator<(const P&q){return (x!=q.x)?(x<q.x):(y<q.y);}
  bool operator>(const P&q){return (x!=q.x)?(x>q.x):(y>q.y);}
  double norm(void){return sqrt(x*x+y*y);}
  double arg(void){return acos(x/this->norm())*P(1,0).sign(*this);}
  P nvec(){return P(y,-x);}
  P rotate(double t){double c=cos(t),s=sin(t);return P(c*x-s*y,s*x+c*y);}
  P reverseX(void){return P(-x,y);}
  P reverseY(void){return P(x,-y);}
  P unit(void){return (*this).norm()==0?P(0,0):(*this)/(*this).norm();}
  P floor(void){return P((int)x,(int)y);}
  double dot(const P&q){return x*q.x+y*q.y;}
  double det(const P&q){return x*q.y-y*q.x;}
  int sign(const P&q){double d = (*this).det(q); return (d>0)-(d<0);}
  static bool on_seg(P p1,P p2,P q){return (p1-q).det(p2-q)==0&&(p1-q).dot(p2-q)<=0;}
  static P intersection(P p1,P p2,P q1,P q2){return p1+(p2-p1)*((q2-q1).det(q1-p1)/(q2-q1).det(p2-p1));}
  static bool crossing(P p1,P p2,P q1,P q2)
  {
    if((p2-p1).sign(q2-q1)==0) return on_seg(p1,p2,q1)||on_seg(p1,p2,q2)||on_seg(q1,q2,p1)||on_seg(q1,q2,p2);
    double x=(q2-q1).det(q1-p1)/(q2-q1).det(p2-p1);
    double y=(p2-p1).det(p1-q1)/(p2-p1).det(q2-q1);
    return x<=1 && x>=0 && y<=1 && y>=0;
  }
};

int main()
{
  int q; cin >> q;
  REP(i,q)
  {
    double x0,y0,x1,y1,x2,y2,x3,y3;
    cin>>x0>>y0>>x1>>y1>>x2>>y2>>x3>>y3;
    P ans = P::intersection(P(x0,y0),P(x1,y1),P(x2,y2),P(x3,y3));
    printf("%.10lf %.10lf\n",ans.x,ans.y);
  }
  return 0;
}

Measured memory_bytes: 3284
N=int(input())
A=[int(i) for i in input().split()]
AVE=sum(A)/N
D=abs(A[-1]-AVE)
ans=N-1
for i in reversed(range(N)):
    d=abs(A[i]-AVE)
    if d<=D:
        ans=i
        D=d
print(ans)

Measured memory_bytes: 3064
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<cmath>
#include<iomanip>
#include<cstring>
#define initdp(a,b) for(int i=0;i<=a;i++)for(int j=0;j<=b;j++)dp[i][j]=-1;
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
#define ll long long
#define pll pair<ll,ll>
#define rep(i,n) for(int i=0;i<n;i++)
#define repd(i,n) for(int i=n-1;i>=0;i--)
#define waste ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define inf 1e9+1
#define inf1 1e18+1
#define mod 1000000007
#define pie 3.14159265358979323846
#define N 1005
#define mid(l,r) l+(r-l)/2
using namespace std;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int ddx[8]={1,1,0,-1,-1,-1,0,1},ddy[8]={0,1,1,1,0,-1,-1,-1};
void mad(ll &a,ll b){a=(a+b)%mod;if(a<0)a+=mod;}
ll gcd(ll a,ll b){ if(a>b)swap(a,b);if(!a)return b;return gcd(b%a,a);}
ll n,w[N],s[N],v[N];
ll dp[N][10005];
int id[N];
ll maxi=-inf;
ll rec(int ii,ll wt){
	int i=id[ii];
	if(ii==n)return 0;
  	if(wt>maxi)return 0;
	if(dp[i][wt]!=-1)return dp[i][wt];
	if(wt<=s[i])dp[i][wt]=rec(ii+1,wt+w[i])+v[i];
	dp[i][wt]=max(dp[i][wt],rec(ii+1,wt));
	return dp[i][wt];
}
bool fun(int i,int j){
	if(s[i]+w[i]==s[j]+w[j])return v[i]>v[j];
	return s[i]+w[i]<s[j]+w[j];
}
void solve(){
	cin>>n;
	rep(i,n){cin>>w[i]>>s[i]>>v[i];maxi=max(maxi,s[i]);}
  	initdp(n,maxi);
	rep(i,n)id[i]=i;
	sort(id,id+n,fun);
	cout<<rec(0,0);
}
int main()
{
	waste;
	int t;
	//cin>>t;
	t=1;
	while(t--){
		solve();
	}
}

Measured memory_bytes: 78592
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define ALL(c) (c).begin(), (c).end()
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v, x) (std::find(v.begin(), v.end(), x) != v.end())
using namespace std;

using ll = long long;
using P = pair<ll, ll>;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline void dump(vector<T> v) { for (auto& x : v) cerr << x << " "; cerr << endl; }
template<class T> inline void dump(vector<pair<T, T>> v) { for (auto& p : v) cerr << p.first << " " << p.second << endl; }
template<class T> inline void dump(vector<vector<T>> vv) { for (auto& v : vv) {for (auto& x : v) cerr << x << " "; cerr << endl;} }

constexpr int INF = 1e9+5;
constexpr long long INFLL = 1LL<<60;
constexpr double eps = (1e-9);

constexpr int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return x ? mod - x : 0;}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}

  friend ostream& operator << (ostream& os, const mint& m) noexcept {
    return os << m.x;
  }

  friend istream& operator<< (istream& is, mint& m) noexcept {
    return is >> m.x;
  }
};

struct combination {
  vector<mint> fact, ifact;  // 階乗と階乗の逆元
  combination(int n):fact(n+1),ifact(n+1) {  // 階乗と階乗の逆元を n まで求める
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
};

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

  ll n, k;
  cin >> n >> k;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];
  sort(ALL(a));

  combination comb(n);

  mint ans = 0;
  for (int i = 0; i <= n-k; i++) {
    ans += comb(n-1-i, k-1) * a[n-1-i];
    ans -= comb(n-1-i, k-1) * a[i];
  }

  cout << ans << endl;

  return 0;
}


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

int poww(int a, int b)
{
    int ans=1;
    if (b == 0)
    {
        return 1;
    }
    
    for (int i = 0; i < b; i++)
    {
        ans *= a;
    }
    return ans;
    
}

int main()
{
    int N, M, answer = 0;
    cin >> N >> M;
    vector<int> s(M, 0);
    vector<int> c(M, 0);
    vector<int> han(N,0);
    for (int i = 0; i < M; i++)
    {
        cin >> s.at(i);
        cin >> c.at(i);
    }

    if (N == 1 && M ==0)
    {
        cout << 0;
        exit(0);
    }
    

    for (int i = 0; i < M; i++)
    {
        if (s.at(i) == 1 && c.at(i) == 0 && N != 1)
        {
            cout << -1;
            exit(0);
        }
        
    }

    for (int i = 0; i < M-1; i++)
    {
        for (int j = i+1; j < M; j++)
        {
            if (s.at(i) == s.at(j) && c.at(i) != c.at(j))
            {
                cout << -1;
                exit(0);
            }
            
        }
        
    }

    for (int i = 0; i < M-1; i++)
    {
        for (int j = i+1; j < M; j++)
        {
            if (s.at(i) == s.at(j))
            {
                s.at(i) = 0;
            }
            
        }
        
    }

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (s.at(j) == i+1)
            {
                han.at(i) = i+1;
            }
            
        }
        
    }

    for (int i = 0; i < M; i++)
    {
        if (s.at(i) == 0)
        {
            answer += 0;
        }

        else if (s.at(i) == 1)
        {
            answer += c.at(i)*(poww(10, N-1));
        }

        else if (s.at(i) == 2)
        {
            answer += c.at(i)*(poww(10, N-2));
        }

        else if (s.at(i) == 3)
        {
            answer += c.at(i)*(poww(10, N-3));
        }
        
    }

    for (int i = 0; i < N; i++)
    {
        if (han.at(i) == i+1)
        {
            answer += 0;
        }

        else
        {
            if (i+1 == 1)
            {
                answer += poww(10, N-1);
            }

            else
            {
                answer += 0;
            }
            
            
        }
        
    }



    cout << answer;
    
    
    
    
    

    
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <string>

#define rep(i, a, b) for ( int i = (a); i < (b); i++ )
#define per(i, a, b) for ( int i = (b)-1; i >= (a); i--)
#define pb push_back
#define mp make_pair
#define bg begin()
#define en end()
#define all(v) (v).begin(), (v).end()
#define sz(v) (int)(v).size()

using namespace std;

typedef long long ll;
typedef long double ld;

static const long long MOD = 1000000007;
static const long long INF = 1<<31;

int ans;
string s, t;

int main(void) {
    cin >> s >> t;
    t.pop_back();
    /*
    bool ok = true;
    for (int i=0; i<sz(s); i++) {
        if (s[i]!=t[i]) ok = false;
    }
    

    if (ok) puts("Yes");
    else puts("No");
    */

   if (s==t) puts("Yes");
   else puts("No");
    

    //cout << ans << endl;

	return 0;
}


Measured memory_bytes: 3640
// see https://gist.github.com/LumaKernel/ff55d49ee1af69b7388f15b707e75c15
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <complex>
#include <random>
#include <iomanip>

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> VI;
typedef vector<P> VP;

#define omajinai ios::sync_with_stdio(false);cin.tie(0)

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define RFOR(i,b,a) for(int i=(b)-1;i>=(a);--i)
#define RREP(i,n) RFOR(i,n,0)

#define LFOR(i,a,b) for(ll i=(a);i<(b);++i)
#define RLFOR(i,b,a) for(ll i=(b)-1;i>=(a);--i)

#define ALL(a) (a).begin(),(a).end()
#define UNIQUE(a) (a).erase(unique((a).begin(),(a).end()),(a).end())
#define MP make_pair
#define PB push_back
#define EACH(i,c) REP(i,(int)(c).size())
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

#define dump(x) cerr << "[L " << __LINE__ << "] " << #x << " = " << (x) << "\n";
#define dump2(x,y) cerr << "[L " << __LINE__ << "] " << #x << " = " << (x)\
			<< " , " << #y << " = " << (y) << "\n";

const ll INF = 1e12;
const double EPS = 1e-10;

ll n,s;

ll f(ll b, ll n){
	return b>n ? n : f(b, n/b) + n%b;
}

ll solve(){
	if(n<s)return -1;
	if(n==s)return n+1;
	// if 2 <= s <= root(n)
	// O(√n log n) ? ですかね ?
	for(ll i=2;i*i<=n;i++){
		if(f(i, n) == s){
			return i;
		}
	}
	ll ans = INF;
	// if root(n) < b <= n
	for(ll i=1;i*i<=n;i++){
		ll b = (n-s)/i+1;
		if(b<2)continue;
		if(f(b, n)==s) ans = min(ans, b);
	}
	if(ans == INF) return -1;
	return ans;
}

int main() {
	cin >> n >> s;

	cout << solve();
	cout << endl;
}


Measured memory_bytes: 256