akhauriyash/Code-Regression huggingface dataset:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	long mod = 1_000_000_007;
	
	public static void main(String[] args) throws IOException {
		Main mainObj = new Main();
		mainObj.solve();
	}

	public void solve() throws IOException {
		FastScanner fs = new FastScanner();
		int n = fs.nextInt();
		int k = fs.nextInt();
		
		long[] numGcdArr = new long[k+1];
		
		for(int i = k ; i >= 1; i--) {
			long numOfI = k/i;
			long gcdINum = pow(numOfI, (long)n);
			
			int mulIGcdBase = 2;
			while(i * mulIGcdBase <= k) {
				gcdINum = calcMod(gcdINum + calcMod((-1)*numGcdArr[i * mulIGcdBase]));
				mulIGcdBase++;
			}
			numGcdArr[i] = gcdINum;
		}
		
		long ans = 0;
		for(int i = 1; i <= k; i++) {
			ans = calcMod(ans + i*numGcdArr[i]);
		}
		
		System.out.println(ans);
	}
	
	long pow(long base, long n) {
		long retVal = 1;
		while(n > 0) {
			if((n&1) == 1) {
				retVal *= base;
			}
			n >>= 1;
			base *= base;
			base = base % mod;
			retVal = retVal % mod;
		}
		return retVal;
	}

	long calcMod(long base) {
		if(base >= 0) {
			return base % mod;
		}else {
			while(base < 0) {
				base += mod;
			}
			return base;
		}
	}
	

	public class FastScanner {

		BufferedReader reader;
		private StringTokenizer st;

		public FastScanner() {
			st = null;
			reader = new BufferedReader(new InputStreamReader(System.in));
		}

		public String next() throws IOException {
			if (st == null || !st.hasMoreElements()) {
				st = new StringTokenizer(reader.readLine());
			}
			return st.nextToken();
		}

		public String nextLine() throws IOException {
			st = null;
			String readLine = null;
			readLine = reader.readLine();
			return readLine;
		}

		public int nextInt() throws NumberFormatException, IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws NumberFormatException, IOException {
			return Long.parseLong(next());
		}

		public int[] nextIntArr(int n) throws NumberFormatException, IOException {
			int[] retArr = new int[n];
			for (int i = 0; i < n; i++) {
				retArr[i] = nextInt();
			}
			return retArr;
		}

		public long[] nextLongArr(int n) throws NumberFormatException, IOException {
			long[] retArr = new long[n];
			for (int i = 0; i < n; i++) {
				retArr[i] = nextLong();
			}
			return retArr;
		}

		public void close() throws IOException {
			reader.close();
		}
	}

}


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

int main() {
 std::ios::sync_with_stdio(false);
  int n, a[222222], b[222222], i;
  cin>>n;
  for(i=1; i <= n; ++i) cin >> a[i];
  int evens, odds;

  if(1&n) {
    evens = n/2+2;
    odds = n/2+1;
  }
  else {
    evens = n/2;
    odds = n/2+1;
  }

  for(i = 1; i <= n; ++i) {
    if(i&1) {
      b[odds] = a[i];
      if(1&n) odds--;
      else odds++;
    }
    else
    {
      b[evens] = a[i];
      if(1&n) evens++;
      else evens--;
    }
  }
  for(i = 1; i <= n; ++i) cout << b[i] << " ";
  return 0;
}


Measured memory_bytes: 3712
#include <algorithm>
#include <cmath>
#include <complex>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
#include <functional>
#include <cstring>
#include <regex>
#include <random>
#include <cassert>
#include <stack>
#include <climits>
#include <chrono>
#include <fstream>
using namespace std;

#pragma region

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, s, n) for (int i = (s); i < (int)(n); i++)
#define revrep(i, n) for (int i = (n) - 1; i >= 0; i--)
#define revrepr(i, s, n) for (int i = (n) - 1; i >= s; i--)
#define debug(x) cerr << #x << ": " << x << "\n"
#define popcnt(x) __builtin_popcount(x)

const double PI = acos(-1.0);

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

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; }

template<class T>
istream& operator >>(istream &is, vector<T> &v) {
    for (int i = 0; i < (int)v.size(); i++) cin >> v.at(i);
    return is;
}

template<class T, class U>
ostream& operator <<(ostream &os, pair<T, U> p) {
    cout << '(' << p.first << ", " << p.second << ')';
    return os;
}

template<class T>
void print(const vector<T> &v, const string &delimiter = " ") { rep(i, v.size()) cout << (0 < i ? delimiter : "") << v.at(i); cout << endl; }

template<class T>
void print(const vector<vector<T>> &vv, const string &delimiter) { for (const auto &v: vv) print(v, delimiter); }

#pragma endregion

int cnt_decimal_part(const string &s) {
    size_t p = s.find('.');
    if (p == string::npos) return 0;
    return s.size() - s.find('.') - 1;
}

int cnt_exp(ll x, int p) {
    int res = 0;
    while (x % p == 0) {
        res++;
        x /= p;
    }
    return res;
}

int main() {
    int n;
    cin >> n;
    vector<ll> a(n);
    rep(i, n) {
        string s;
        cin >> s;
        int c = cnt_decimal_part(s);
        if (0 < c) s.erase(s.find('.'), 1);
        rep(i, 9 - c) s.push_back('0');
        a[i] = stoll(s);
    }

    ll ans = 0;
    vector<vector<ll>> cnt(19, vector<ll>(19));
    
    rep(i, n) {
        int e2 = min(18, cnt_exp(a[i], 2)), e5 = min(18, cnt_exp(a[i], 5));
        repr(x, 18 - e2, 19) repr(y, 18 - e5, 19) {
            ans += cnt[x][y];
        }
        cnt[e2][e5]++;
    }

    cout << ans << endl;
}

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

//計算
long long sum(string t) {
	long long ret = 0, n = 0;
	for (int i = 0; i < t.size(); i++) {
		if (t[i] != '+')n = n * 10 + (t[i] - '0');
		if (t[i] == '+' || i == t.size() - 1) { ret += n; n = 0; }
	}
	return ret;
}

int main() {
	string s; cin >> s;
	long long ans = 0;

	//bit全探索
	for (int bit = 0; bit < (1 << s.size() - 1); bit++) {
		string formula; int x = 1;
		formula += s[0];

		for (int i = s.size() - 2; i >= 0; i--) {
			if (bit&(1 << i))formula += '+';
			formula += s[x];
			x++;
		}

		ans += sum(formula);
	}

	cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int N,M;
    long long int K;
    cin >> N >> M >> K;
    
    vector<long long int> A(N);
    vector<long long int> B(M);
    vector<long long int> a(N+1);
    vector<long long int> b(M+1);
    a.at(0) = 0;
    b.at(0) = 0;
    int i;


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

    int ans = 0;
    for(i=0;i<N;i++){
        a.at(i+1) = a.at(i) + A.at(i);
    }
    
    for(i=0;i<M;i++){
        b.at(i+1) = b.at(i) + B.at(i);
    }

    int j = M;
    for(i=0;i<N+1;i++){
        if(a.at(i) > K){
            break;
        }
        while(a.at(i) + b.at(j) > K){
            j --;
        }
        ans = max(i+j,ans);
    }

    cout << ans << endl;
}


Measured memory_bytes: 9572
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#include<cmath>


#define REP(i,n) for (int i = 0; (i) < (n); ++ (i))
#define FOR(i,n) for (int i = 1; (i) <= (n); ++ (i))
#define dump(x)  cout << #x << " = " << (x) << endl;
#define pb push_back
#define int long long
//#define lint long long

const int INF = 1e18;
const int MOD = 1e9+7;
//const lint LINF = 1e18;
const double eps = 0.000000001;//もとの値の10^(-16)まで

using namespace std;

//typedef pair<int, int> P;
//priority_queue< P, vector<P>, greater<P> > q;//ダイクストラの時、greaterで小さい順
int v1[200000];
signed main(){
  int n;
  cin >> n;
  REP(i,n){
    cin >> v1[i];
  }
  sort(v1,v1+n);
  double ans = v1[0];
  REP(i,n-1){
    ans = (ans+v1[i+1])/2.0;
  }
  cout << ans << endl;
  return 0;
}


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

using namespace std;

int main(){
    int N;
    cin >> N;
    vector<int> A(N);
    int min = 1000000000+1;
    for(int i= 0; i< N;i++){
        cin >> A[i];
        if (A[i] < min){
            min = A[i];
        }
    }
    int next_min = min;
    while(1){
        for(int i= 0; i< N;i++){
            int p = A[i] % min;
            if(p!= 0 && p < next_min){
                next_min = p;
            }
        }
        if(min == next_min) {
            cout << min << endl;
            break;
        }
        min = next_min;
    }
    return 0;
}

Measured memory_bytes: 640
solver::Int->Int->Int
solver n k = 1 + div (n-k) (k-1) + if mod (n-k) (k-1) == 0 then 0 else 1

main::IO()
main=do
  nkc<-getLine
  _<-getLine
  let n:k:[]=map read (words nkc)
  print (solver n k)

Measured memory_bytes: 18812
import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {
	public Scanner scanner = new Scanner(System.in);
	public static final long MODN = 1000000007;
	public PrintStream out = System.out;
	
	public void start() {
		long n = scanNum();
		long[] a = scanNums(n);
		
		long sum1 = 0;
		long sum2 = 0;
		
		for(int i=0; i < n; i++) {
			sum2 += sum1 * a[i];
			sum2 %= MODN;
			sum1 += a[i];
			sum1 %= MODN;
		}
		
		out.print(sum2);
	}
	
	//Javaではlong型でも%dでよい
	public void printNums(long[] nums) { for(long cur : nums) out.printf("%d ", cur); out.println();}
	public void printNums(List<Long> nums) { for(long cur : nums) out.printf("%d ", cur); out.println();}
	public long scanNum() { return scanner.nextLong(); }
	public String scanLine() { return scanner.nextLine(); }
	
	public long[] scanNums(long num) {
		long[] ret = new long[(int) num];
		for(int i=0; i < num; i++) {
			ret[i] = scanner.nextLong();
		}
		return ret;
	}
	
	public List<Long> longArrayToList(long[] arr){
		List<Long> ret = new ArrayList<>(arr.length);
		for(long cur : arr) {
			ret.add(cur);
		}
		return ret;
	}
	
	public Main() {
		
	}
	
	public static void main(String[] args) {
		Main kpc = new Main();
		kpc.start();
	}

}


Measured memory_bytes: 62956
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0;i<(n);i++)
typedef long long ll;
int main() {
//input
int k,x;
cin>>k>>x;

//compute

//output
if(k*500>=x)printf("Yes");
else printf("No");

	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
 
int main (void)
{
  int n;
  scanf("%d",&n);
 
  int a[n],i;
  for(i=0;i<n;i++){
    scanf("%d",&a[i]);
  }
   
  int j;
  for(j=n-1;j>0;j--){
    printf("%d ",a[j]);
  }
  printf("%d",a[0]);
  printf("\n");
  return 0;
}

Measured memory_bytes: 600
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long ll;
typedef pair<ll,ll> P;
const ll mod=1000000007;
const ll LINF=1LL<<60;
const int INF=1<<30;

int main(){
	ll x;cin>>x;
	ll ans = 0;
	ans += x / 500 * 1000;
	ans += (x % 500) / 5 * 5;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
  int n,i,ans,b;cin >> n;
  ans = 0;
  int a[n];
  for (i=0;i<n;i++) cin >> a[i];
  for (i=0;i<n;i++){
    cin >> b;
    ans += b;
  }
  int c[n-1];
  for (i=0;i<n-1;i++) cin >> c[i];
  for (i=1;i<n;i++){
    if (a[i]-1 == a[i-1]){
      ans += c[a[i]-2];
    }
  }
  cout << ans << endl;  
}
  

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

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

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

	vector<int> v(n);
	forn(i, n) cin >> v[i];

	int mini = pow(10, 6);
	int counter = 0;

	forn(i, n) {
		if(mini > v[i]) {
			++counter;
			mini = v[i];
		}
	}

	cout << counter << "\n";

	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <vector>
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if(a < b){ a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if(a > b){ a = b; return 1; } return 0; }
typedef long long ll;
int main()
{
  ll h,w; cin >> h >> w;
  ll res = 1e+15;
  if(h % 3 == 0 || w % 3 == 0) res = 0;
  else res = min(h, w);

  rep1(i,h-1) {
    ll a = i*w;
    ll b = (h - i)*(w/2);
    ll c = (h - i)*((w+1)/2);
    chmin(res, max({a,b,c}) - min({a,b,c}));
  }

  rep1(i,w-1) {
    ll a = i*h;
    ll b = (w - i)*(h/2);
    ll c = (w - i)*((h+1)/2);
    chmin(res, max({a,b,c}) - min({a,b,c}));
  }  

  cout << res << "\n";
  return 0;
}


Measured memory_bytes: 256
#include <cstdio>

const int MAXN=1e5+5;
int n,cnt_4,cnt_not4;
int a[MAXN];

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		if(a[i]%4==0) ++cnt_4;
		else if(a[i]%2) ++cnt_not4;
	}
	if(cnt_4>=cnt_not4 || (cnt_4>=cnt_not4-1 && cnt_4+cnt_not4==n)) printf("Yes");
	else printf("No");
	return 0;
}

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

int main(){
int n;
int b;
int c;
int d;
while(cin >> n){
int a[n+1];
b=1;
while(b<n+1){
a[b]=0;
b=b+1;}
a[1]=1;
d=0;
b=2;
while(b<n+1){
if(a[b]==0){d=d+1; c=2; while(1){if(c*b>n){break;} a[c*b]=1; c=c+1;}}
b=b+1;}
cout << d <<endl;}


}

Measured memory_bytes: 5064
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using p = pair<int, int>;
#define INF 1000000000
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repX(i, n ,x) for (int i = x; i < (int)(n); i++)
#define repBack(i, n) for (int i = n; i > 0; i--)

int main() {
    ll N,K,Q;
    cin >> N >> K >> Q;
    vector<ll> a(N);
    int ans = N;
    rep(i,Q){
        int A;
        cin >> A;
        --A;
        if(a[A]==-1)continue;
        if(K-((i+1)-a[A])<0){
            a[A] = -1;
        }else{
            a[A] ++;
        }
    }
    rep(i,N){
        if(a[i]==-1){
            cout << "No" << endl;
            continue;
        }
        if(K-(Q-a[i])<=0){
            cout << "No" << endl;
        }else{
            cout << "Yes" << endl;
        }
    }

    return 0;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
using namespace std;

int main(){
  int N;
  string S, s1, s2;
  cin >> N >> S;
  // もし長さが奇数であればダメ
  if (N % 2 == 1){
    cout << "No" << endl;
    return 0;
  }
  // 文字列を半分にする
  s1 = S.substr(0, N/2);
  s2 = S.substr(N/2, N/2);
  // 半分にした文字列同士を比較する
  if (s1 == s2) cout << "Yes" << endl;
  else cout << "No" << endl;
}


Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int64_t n, m;
  cin >> n >> m;
  
  int64_t ans;
  
  if(2*n < m){
    ans = n + (m - 2*n)/4;
  }
  
  else{
    ans = m / 2;
  }
  
  cout << ans << endl;

}
       

Measured memory_bytes: 3600
#include<stdio.h>
#include<stdlib.h>

typedef const void cv;

int upint(cv *a, cv *b) { 
  return *(int *)a < *(int *)b ? -1 : *(int *)a > *(int *)b ? 1 : 0; 
}

int main(void){
  int n, k, i, p[1020] = {0};
  scanf("%d",&n);
  scanf("%d",&k);
  for(i=0;i<n;i++){
    scanf("%d",&p[i]);
  }
  
  qsort(p,n,sizeof(int),upint);
  int result=0;
  for(i=0;i<k;i++) result += p[i];
  printf("%d\n",result);
  
  return 0;
}

Measured memory_bytes: 1736
from collections import deque
N, K = map(int, input().split())
nums = list(map(str, input().split()))
can_use_nums = set([str(i) for i in range(10)])
for num in nums:
    can_use_nums.remove(num)
# print(can_use_nums)

queue = deque([[num] for num in can_use_nums if num != '0'])
# print(queue)
min_num = float('inf')
while queue:
    num = queue.popleft()
    if N <= int(''.join(num)):
        min_num = min(min_num, int(''.join(num)))
    else:
        for add_num in can_use_nums:
            t_num = num.copy()
            if min_num > int(''.join(num) + add_num):
                t_num.append(add_num)
                queue.append(t_num)
print(min_num)


Measured memory_bytes: 11756
length = gets.to_i
result_array = gets.chomp.split(" ").map(&:to_i)

#array_length 個の要素を含む 0-オリジンの配列 array_value
def bubbleSort(array_value, array_length)
    flag = 1 #逆の隣接要素が存在する
    exchange_ct = 0
  
    while flag == 1 do
        
        flag = 0
        
        for j in 1..(array_length - 1) do
            
            temp_index = array_length - j
            
            if array_value[temp_index] < array_value[temp_index - 1]
                
                array_value[temp_index - 1], array_value[temp_index] = array_value[temp_index], array_value[temp_index - 1]  
                
                exchange_ct += 1
                
                flag = 1
            end
        end
    end
    
    exchange_ct
end

exchange_ct = bubbleSort(result_array, length)

puts result_array.join(" ")
puts exchange_ct



Measured memory_bytes: 6872
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
//#include<bits/stdc++.h>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

int P;
ll modpow(ll A, ll B) {
	ll kotae = 1;
	while (B > 0) {
		if (B & 1) kotae = kotae * A % P;
		A = A * A % P;
		B >>= 1;
	}
	return kotae;
}
int cnt[10000];
int main() {
	//cin.tie(0);
	//ios::sync_with_stdio(false);


	char c;
	int N = 0;
	while ((c = getchar_unlocked()) >= '0') N = N * 10 + c - '0';
	while ((c = getchar_unlocked()) >= '0') P = P * 10 + c - '0';
	if (P == 2) {
		ll kotae = 0;
		rep(i, N) {
			if ((getchar_unlocked() - '0') % 2 == 0) kotae += i + 1;
		}
		printf("%lld", kotae);
		return 0;
	}
	if (P == 5) {
		ll kotae = 0;
		rep(i, N) {
			if ((getchar_unlocked() - '0') % 5 == 0) kotae += i + 1;
		}
		printf("%lld", kotae);
		return 0;
	}

	cnt[0] = 1;
	ll kotae = 0;
	const int p = P;
	int gyaku = modpow(10, P - 2);
	int ima = 1;
	int mae = 0;
	rep(i, N) {
		int a = getchar_unlocked() - '0';
		a = (a * ima + mae) % p;
		kotae += cnt[a];
		cnt[a]++;
		mae = a;

		ima = ima * gyaku % p;
	}

	printf("%lld", kotae);

	Would you please return 0;
}

Measured memory_bytes: 256
import sys,math,string,bisect
input=sys.stdin.readline
from collections import deque,defaultdict
L=lambda : list(map(int,input().split()))
Ls=lambda : list(input().split())
M=lambda : map(int,input().split())
I=lambda :int(input())
S=lambda :input().strip()
k=I()
n=input()
print(n.count("ABC"))


Measured memory_bytes: 3956
import java.util.Scanner;

public class Main {

	static int solve(String s, String t) {
		int min = 1001;

		for (int i = 0; i < s.length() - t.length() + 1; i++) {
			int count = 0;
			for (int j = 0; j < t.length(); j++) {
				if (s.charAt(i + j) != t.charAt(j))
					count++;
			}
			if (count < min)
				min = count;
		}

		return min;
	}

	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);

		String s, t;
		s = stdIn.next();
		t = stdIn.next();
		int result = solve(s, t);
		System.out.println(result);

		stdIn.close();
	}
}


Measured memory_bytes: 27124
import java.io.*;
import java.util.*;

class Main {

	public static void main(String[] args) throws Exception {
		final Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[][] x = new int[N][2];
		int[][] y = new int[N][2];
		for (int i = 0; i < N; i++) {
			x[i][0] = sc.nextInt() - 1;
			x[i][1] = i;
			y[i][0] = sc.nextInt() - 1;
			y[i][1] = i;
		}
		Arrays.sort(x, (a, b) -> Integer.compare(a[0], b[0]));
		Arrays.sort(y, (a, b) -> Integer.compare(a[0], b[0]));
		Queue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
		for (int i = 0; i < N - 1; i++) {
			pq.offer(new int[]{x[i + 1][0] - x[i][0], x[i + 1][1], x[i][1]});
			pq.offer(new int[]{y[i + 1][0] - y[i][0], y[i + 1][1], y[i][1]});
		}

		UnionFind uf = new UnionFind(N);
		long a = 0;
		while (!pq.isEmpty()) {
			int[] p = pq.poll();
			if (uf.union(p[1], p[2])) {
				a += p[0];
			}
		}

		System.out.println(a);
	}

	private static class UnionFind {

		private int[] parent;
		private int[] count;

		public UnionFind(int n) {
			parent = new int[n];
			count = new int[n];
			for (int i = 0; i < n; i++) {
				parent[i] = i;
				count[i] = 1;
			}
		}

		public boolean union(int v, int w) {
			int a = root(v);
			int b = root(w);
			if (a == b) return false;

			if (count[a] >= count[b]) {
				parent[b] = a;
			} else {
				parent[a] = b;
			}
			count[a] = count[b] = count[a] + count[b];

			return true;
		}

		public boolean connected(int v, int w) {
			return root(v) == root(w);
		}

		public int count(int v) {
			return count[root(v)];
		}

		private int root(int v) {
			while (parent[v] != parent[parent[v]]) parent[v] = parent[parent[v]];
			return parent[v];
		}
	}

}


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

#define ff first
#define ss second
#define pb push_back
#define ll long long
#define ull unsigned long long
#define min3(a, b, c) min(a, min(b, c))
#define max3(a, b, c) max(a, max(b, c))
#define mst(ss,b) memset(ss,b,sizeof(ss));
#ifdef Cyberdebut
#define dbg(x) cerr << #x << " = " << x << endl
#else
#define dbg(x)
#endif
typedef pair <int, int> pii;
const int inf = 0x3f3f3f3f;
const ll INF = (1LL<<62)-1;
const ll mod = 1e9+7;
const int N = 1e5+5;

int n, k;
int a[N];

int  main(){
//    ios::sync_with_stdio(false);
    cin>>n>>k;
    for(int i=1; i<=n; i++){
        cin>>a[i];
    }
    int gg = a[1], mx = a[1];
    for(int i=2; i<=n; i++)gg = __gcd(gg, a[i]), mx = max(mx, a[i]);
    if(k <= mx && k%gg == 0)puts("POSSIBLE");
    else puts("IMPOSSIBLE");
    return 0;
}


//    lower_bound()
//    __builtin_popcount()
//    ios::sync_with_stdio(false);
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
//    const double eps=1e-12;
//    #pragma comment(linker,"/STACK:102400000,102400000")



Measured memory_bytes: 640
import java.io.PrintWriter
val pw = PrintWriter(System.out)

fun main(args : Array<String>) {
    func()
    pw.flush()
}

fun func() {
    val n = nextInt()

    var max = 0
    var sum = 0
    repeat(n) {
        val p = nextInt()
        if (p > max) max = p
        sum += p
    }

    println(sum - max/2)
}

fun next() = readLine()!!
fun nextInt() = next().toInt()

fun println(value : Any) {
    pw.println(value)
}

Measured memory_bytes: 33536
#include <cstdio>
int readint() {
	char ch = getchar_unlocked();
	int res = 0;
	while('0' <= ch && ch <= '9') {
		res = res * 10 + (ch - '0');
		ch = getchar_unlocked();
	}
	return res;
}
char buf[1024];
void writeint(int x, char endch) {
	int ptr = 0, g;
	while(x > 0) {
		g = x / 10;
		buf[ptr++] = x - g * 10;
		x = g;
	}
	if(ptr == 0) {
		buf[ptr++] = 0;
	}
	while(ptr--) {
		putchar_unlocked(buf[ptr] + '0');
	}
	putchar_unlocked(endch);
}
int g[] = { 1, 9, 46, 233, 1182, 5985, 30301, 153401 };
int N, A[1024000];
int main() {
	int N = readint();
	for(int i = 0; i < N; ++i) {
		A[i] = readint();
	}
	// https://oeis.org/A108870 modified
	int sz = sizeof(g) / sizeof(int), lim = 1;
	while(lim < sz && g[lim] < N) ++lim;
	int cnt = 0;
	for(int i = lim - 1; i >= 0; --i) {
		for(int j = g[i]; j < N; ++j) {
			int pos = j, pt = j - g[i], x = A[j];
			while(pt >= 0 && A[pt] > x) {
				A[pos] = A[pt];
				pos -= g[i];
				pt -= g[i];
				++cnt;
			}
			A[pos] = x;
		}
	}
	writeint(lim, '\n');
	for(int i = lim - 1; i >= 0; --i) {
		writeint(g[i], (i != 0 ? ' ' : '\n'));
	}
	writeint(cnt, '\n');
	for(int i = 0; i < N; ++i) {
		writeint(A[i], '\n');
	}
	return 0;
}



Measured memory_bytes: 6460
n = int(input())

rt = {}

sl = [[-1 for i in range(3)] for i in range(n)]

for i in range(n):
  id, *s = list(map(int, input().split()))
  if s[0] >= 0 and s[1] >= 0:
    for j in s:
      rt[j] = id
    sl[s[0]][0] = s[1]
    sl[s[1]][0] = s[0]
    sl[id][1] = 2
  elif s[0] >= 0 and s[1] == -1:
    rt[s[0]] = id
    sl[id][1] = 1
  elif s[1] >= 0 and s[0] == -1:
    rt[s[1]] = id
    sl[id][1] = 1

p = [[] for i in range(n)]

for i in range(n):
  p[i] = [i]
  while True:
    try:
      p[i].append(rt[p[i][-1]])
    except:
      break

for i in range(n):
  for j in range(n):
    if i in p[j]:
      sl[i][2] = max(sl[i][2], p[j].index(i))

for i in range(n):
  print("node " + str(i) + ": parent = ", end = "")
  if len(p[i]) == 1 and n == 1:
    print("-1, sibling = -1, degree = 0, depth = 0, height = 0, root")
  elif len(p[i]) == 1 and n > 1:
    print("-1, sibling = -1, degree = " + str(sl[i][1]) + ", depth = 0, height = " + str(sl[i][2]) + ", root")
  else:
    if sl[i][1] == -1:
      print(str(p[i][1]) + ", sibling = " + str(sl[i][0]) + ", degree = 0, depth = " + str(len(p[i])-1) + ", height = 0" +", leaf")
    else:
      print(str(p[i][1]) + ", sibling = " + str(sl[i][0]) + ", degree = " + str(sl[i][1]) + ", depth = " + str(len(p[i])-1) + ", height = " + str(sl[i][2]) +", internal node")


Measured memory_bytes: 5632
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <map>
#include <tuple>
#include <iostream>
#include <deque>
#include <array>
#include <set>
#include <functional>

int main() {
	int x, a; std::cin >> x >> a;
	if (x < a) {
		std::cout << 0 << std::endl;
	}
	else {
		std::cout << 10 << std::endl;
	}
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int sCnt[100004], tCnt[100004], q, a, b, c, d;

int main() {
	string s;
	memset(sCnt,0,sizeof(sCnt));
	memset(tCnt,0,sizeof(tCnt));
	cin>>s;
	for(int i = 1 ; i <= s.length();i++){
		if(s[i-1]=='A')	sCnt[i] = sCnt[i-1]+1;
		else	sCnt[i] = sCnt[i-1];
	}
	cin>>s;
	for(int i = 1 ; i <= s.length();i++){
		if(s[i-1]=='A')	tCnt[i] = tCnt[i-1]+1;
		else	tCnt[i] = tCnt[i-1];
	}
	cin>>q;
	while(q--){
		cin>>a>>b>>c>>d;
		int x = sCnt[b]-sCnt[a-1], y = tCnt[d]-tCnt[c-1];
		x = (x+b-a+1)%3, y = (y+d-c+1)%3;
		if(x==y)	cout<<"YES\n";
		else	cout<<"NO\n";
	}
	return 0;
}

Measured memory_bytes: 1536
fn solve() {
    let n: usize = read();
    let m = read();
    let mut a: HashSet<usize> = HashSet::new();
    for i in 0..m {
        a.insert(read::<usize>() - 1);
    }
    // -1, 0, 1, ... n
    let mut anss = vec![0; n + 2];
    anss[1] = 1;
    for i in 2..n + 2 {
        if !a.contains(&(i - 2)) {
            anss[i] = (anss[i - 1] + anss[i - 2]) % MOD;
        }
    }
    println!("{}", anss[n + 1]);
}

fn main() {
    let stack_size = 104_857_600;
    let thd = std::thread::Builder::new().stack_size(stack_size);
    thd.spawn(|| solve()).unwrap().join().unwrap();
}

// =========
#[allow(unused_imports)]
use std::cmp::{max, min, Reverse};
#[allow(unused_imports)]
use std::collections::{BinaryHeap, HashMap, HashSet};
#[allow(unused_imports)]
use std::process::exit;

#[allow(dead_code)]
const MOD: usize = 1_000_000_007;

fn read<T: std::str::FromStr>() -> T {
    use std::io::Read;
    let stdin = std::io::stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

// =========


Measured memory_bytes: 2892
import java.io.*;
import java.util.*;
public class Main {
	
	public static void main(String[] args) {
	
		MyScanner sc = new MyScanner();
		int n=sc.nextInt();
		Long k=sc.nextLong();
		Long x=0L;
		Long ans=0L;
		Long a[]=new Long[n];
		String a_[]=new String[n];
		for(int i=0;i<n;i++) {
			a[i]=sc.nextLong();
			String abit=Long.toBinaryString(a[i]);
			
			a_[i]=String.format("%41s",abit);
			
			
		}
		int count[]=new int[41];
		for(int j=0;j<=40;j++) {
			for(int i=0;i<n;i++) {
				if(a_[i].charAt(j)=='1') {
					count[j]++;
				}
		
			}
			
			if(2*count[j]<n&&(long)Math.pow(2,40-j)+x<=k) {
				if((long)Math.pow(2,40-j)+x<=k) {
					x+=(long)Math.pow(2,40-j);
					ans+=(n-count[j])*(long)Math.pow(2,40-j);
					}
				}
			else{
				ans+=count[j]*(long)Math.pow(2,40-j);
			}
			
		}
		System.out.println(ans);
	}
	
	public static PrintWriter out;

	public static class MyScanner {
		BufferedReader br;
		StringTokenizer st;

		public MyScanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

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

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

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

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

		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return str;
		}

	}
	

}





Measured memory_bytes: 105324
#include <stdio.h>
#include <stdlib.h>

int main (void) {
    int x;
    scanf("%d", &x);
    if ( x == 7 || x == 5 || x == 3 ) {
        printf("YES\n");
    } else {
        printf("NO\n");
    }
    return EXIT_SUCCESS;
}

Measured memory_bytes: 128
n, y = map(int,input().split())
a = -1
b = -1
c = -1

for i in range(n+1):
    for j in range(n+1):
        if 0 <= n - i - j <= 2000 and y == 10000*i + 5000*j + 1000*(n - i - j):
            a = i
            b = j
            c = n - i -j
            break
print(a,b,c)


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

int main(void) {
    int R, G, B, N;
    cin >> R >> G >> B >> N;
    int ans = 0;
    for (int i = 0; i <= 3000; i++) {
        for (int j = 0; j <= 3000; j++) {
            int have = i * R + j * G;
            if ((N - have) % B == 0 && (N - have) / B >= 0) ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3572
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A,B,C,D;
  cin >> A >> B >> C >> D ;
 
  if ( A + B > C + D ) {
    cout << "Left" << endl;
  }
  else if ( A + B < C + D ) {
    cout << "Right" << endl;
  }
  else  {
    cout << "Balanced" << endl;
  }
}

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

using namespace std;

int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};


int main(){
	int i,j,N,n,d;
	while(cin>>N,N){
		struct{int x,y;} log[205]={0}, Min={0}, Max={0};
		for(i=1;i<N;i++){
			cin>>n>>d;
			log[i].x=log[n].x+dx[d];
			log[i].y=log[n].y+dy[d];
			Max.x=max(Max.x, log[i].x);
			Max.y=max(Max.y, log[i].y);
			Min.x=min(Min.x, log[i].x);
			Min.y=min(Min.y, log[i].y);
		}
		cout << Max.x-Min.x+1 << ' ' << Max.y - Min.y+1 << endl;
	}
	return 0;
}

Measured memory_bytes: 0
N = int(input())
Cs = []
Ss = []
Fs = []
for i in range(N-1):
    c, s, f = map(int, input().split())
    Cs.append(c)
    Ss.append(s)
    Fs.append(f)

for start in range(N):
    time = 0
    current_i = start
    while current_i < N-1:
        if time >= Ss[current_i]:
            if time % Fs[current_i] == 0:
                time += Cs[current_i]
                current_i += 1
            else:
                time = Fs[current_i] * (time // Fs[current_i] + 1)
        else:
            time = Ss[current_i]

    print(time)


Measured memory_bytes: 3188
#include <cstring>
#include <cstdlib>
#include <map>
#include <unordered_map>
#include <string>
#include <list>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <cstdio>
#include <iostream>
#include <set>
#include <unordered_set>
using namespace std;

#define ABS(a) ((a)<0?(-(a)):(a))
#define CS while(cases())
#define I(n) int n = gi()
#define II(n) n = gi()
#define L(n) ll n = gli()
#define LL(n) n = gli()
#define F(i, n) for (int i = 0; i < n; i++)
#define Fa(n, a) for (int i = 0; i < n; i++) a[i] = gi()
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef pair<int, int> pii;

template<class T>
T gcd(T a, T b) {
    return (b == 0 ? a : gcd(b, a%b));
}

int gi() {
    int a;
    scanf("%d", &a);
    return a;
}

ll gli() {
    ll a;
    scanf("%lld", &a);
    return a;
}

int cases() {
    static int t = gi();
    return t--;
}

#define MD 1000000007
char r[20];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    L(n);
    int w = 0;
    while (n) {
        r[w++] = 'a' + ((n-1)%26);
        n -= (n-1)%26;
        n /= 26;
    }
    while (w)
        printf("%c", r[--w]);
    printf("\n");

    return 0;
}


Measured memory_bytes: 3692
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<string>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long int ll;
typedef vector<pair<ll,ll> > Q;
typedef pair<int,int> P;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
const ll inf=1e9+7;
ll gcd(ll a, ll b) { return (b ? gcd(b, a % b) : a); }
ll lcm(ll a, ll b) { return a / (gcd(a, b)) * b; }

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

  cout<<min(b,a*n)<<endl;
}

Measured memory_bytes: 256
N = int(input())
s = [[0 for i in range(3)] for j in range(N)]
dp = [[0 for i in range(3)] for j in range(N+1)]
for i in range(N):
    s[i] = [int(j) for j in input().split()]


    
for i in range(1,N+1):
    for j in range(3):
        dp[i][j] = max(dp[i-1][(j+1)%3]+s[i-1][j],dp[i-1][(j+2)%3]+s[i-1][j])

print(max(dp[N]))


Measured memory_bytes: 45732
import random
import sys
import time

input = sys.stdin.readline

def main():
    d = int(input())
    c = list(map(int, input().split()))
    s = []
    for _ in range(d):
        s.append(list(map(int, input().split())))
    
    start_time = time.time()
    ans = []
    suff = 0
    # while True:
    #     elapsed_time = time.time() - start_time
    #     if elapsed_time >= 1.8:
    #         break
        
    # ここから
    last = [0 for _ in range(26)]
    for i in range(d):
        tmpsuf = 0
        tmpc = 0
        for con in range(26):
            ttttt = suff + s[i][con]
            minus = 0
            for j in range(26):
                if con == j:
                    continue
                minus -= (i - last[j]) * c[j]
            ttttt += minus
            if ttttt > tmpsuf:
                tmpsuf = ttttt
                tmpc = con
        last[tmpc] = i
        suff = tmpsuf
        ans.append(tmpc)


    print(*[a + 1 for a in ans])

if __name__ == '__main__':
    main()


Measured memory_bytes: 9900
#2020-03-19
while True:
    n, x = map(int,input().split())
    count = 0
    if n == x == 0:
        break
    
    for i in range(1,n + 1):
        for j in range(1,i):
            for k in range(1,j):
                if i + j + k == x:
                    count += 1
    print(count)


Measured memory_bytes: 5596
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<ctype.h>

long long num[100000]={0};


int main()

{
    long long n,i,number,a,b,sum=0;
    scanf("%lld",&n);

    for(i=0;i<n;i++)
    {
        scanf("%lld",&number);
        num[number-1]++;
        sum=sum+number;
    }
    int q;
    scanf("%d",&q);
    long long res[q];
    //int a,b,add[q],ll=q;
    for(i=0;i<q;i++)
    {
        scanf("%lld %lld",&a,&b);
        res[i]=sum-num[a-1]*(a-b);
        sum=res[i];
        num[b-1]=num[b-1]+num[a-1];
        num[a-1]=0;

    }
    for(i=0;i<q;i++)
    {
        printf("%lld\n",res[i]);
    }

    return 0;
}


Measured memory_bytes: 3264
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
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; }

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, l;
	cin >> n >> l;
	int sum = 0, mi = 10000;
	vector<int> a(n);
	rep(i,n){
		a[i] = l + i;
		sum += a[i];
		if(abs(a[i]) < abs(mi)) mi = a[i];
	}
	int ans = sum - mi;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3660
#include <iostream>
#include <numeric>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    vector<int> a(3);
    for (auto& e : a) cin >> e;
    int sum = accumulate(a.begin(), a.end(), 0);
    int ma = *max_element(a.begin(), a.end());

    cout << (sum % 2 == ma % 2 ? (ma * 3 - sum) / 2 : ((ma + 1) * 3 - sum) / 2) << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bits/stdc++.h>
#include<cmath>
#include<bitset>
#include<stack>
#include<queue>
#define ll long long
#define itn int
#define co(ans) cout<<ans<<endl;
#define COYE cout<<"YES"<<endl;
#define COYe cout<<"Yes"<<endl;
#define COye cout<<"yes"<<endl;
#define CONO cout<<"NO"<<endl;
#define CONo cout<<"No"<<endl;
#define COno cout<<"no"<<endl;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n)  FFOR(i,1,n)
#define SORT(V) sort((V).begin(),(V).end())
#define REVERSE(V) reverse((V).begin(),(V).end())
#define INF ((1LL<<62)-(1LL<<31))
#define MOD 1000000007
#define MAX 510000
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;}
using namespace std;


int main(){
  long double A,B,C;
  cin>>A>>B>>C;
  
  if(A+B+2*sqrt(A*B)<C) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}

Measured memory_bytes: 256
# 1
# https://atcoder.jp/contests/keyence2019/tasks/keyence2019_a
if False:
    print('YES' if set(input().split())==set(list('1974')) else 'NO')

# 2
# https://atcoder.jp/contests/keyence2019/tasks/keyence2019_b
if True:
    S=input()
    ans='NO'
    K='keyence'
    for i in range(len(S)-1):
        for j in range(i,len(S)):
            if S[:i+1]+S[j:]==K: ans='YES'
    print(ans)

# 3
# https://atcoder.jp/contests/aising2019/tasks/aising2019_a
if False:
    N=int(input())
    H=int(input())
    W=int(input())
    print((N-H+1)*(N-W+1))

# 4
# https://atcoder.jp/contests/aising2019/tasks/aising2019_b
if False:
    N=int(input())
    A,B=map(int,input().split())
    P=[int(i) for i in input().split()]
    cnt=[0,0,0]
    for p in P:
        if p<=A: cnt[0]+=1
        elif A<p<=B: cnt[1]+=1
        else: cnt[2]+=1
    print(min(cnt)) 

# 5
# https://atcoder.jp/contests/caddi2018b/tasks/caddi2018b_a
if False: print(input().count('2'))

Measured memory_bytes: 3188
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define int long long
#define mp make_pair
#define endl "\n"
#define pii pair<int,int> 
#define ff first
#define ss second
#define mii map<int,int>
#define si set<int>
#define sti stack<int>
#define qi queue<int>
#define vi vector<int>
#define pq priority_queue<int>
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const int M=1e9+7;

int32_t main(){
    IOS;
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    int cur=0;
    while(a>0&&c>0){
        if(cur==1){
            a-=d;
            cur=0;
        }
        else{
            c-=b;
            cur=1;
        }
    }
    if(cur) cout<<"Yes";
    else cout<<"No";
}


Measured memory_bytes: 3640
N, S = map(int, input().split())
A = list(map(int, input().split()))
#d = sum(A)
mod = 998244353

"""
多項式係数を使った数え上げでリベンジしてみる。
maspyさんのを参考に実装する。

（注意）多項式係数全てを書き下すと、d = sum(A)次式になるが、
これは Ai*N = 3000*3000 次になりTLEする。。。
S次の項までで打ち切る事を忘れない事。

やってみてわかったけど、実装自体はdpでやったのとほぼ同じ。
多項式係数を使う方法は実質flexibleなdpということ？
"""

f = [0] * (1 + S) # f[i] = (coefficient of degree i)
ans = 0

for i in range(N):
    g = [0] * (1 + S) # g = (1 + f) * (1 + x^{A[i]})
    f[0] += 1
    for j in range(1 + S):
        if j - A[i] < 0:
            g[j] = f[j]
        else:
            g[j] = f[j] + f[j - A[i]]
    ans += g[S]
    ans %= mod
    f = g

print(ans)


Measured memory_bytes: 101852
#include <stdio.h>

struct card
{
	char type;
	int value;
};

int main(void)
{
	int n, i, j, minj;
	scanf("%d", &n);
	struct card a[36];
	struct card b[36];
	struct card tmp;
	
	for(i = 0; i < n; i++){
		scanf(" %c%d", &a[i].type, &a[i].value);
		b[i] = a[i];
	}
	
	for(i = 0; i < n; i++){
		for(j =n-1; j >= i+1; j--){
			if(a[j].value < a[j-1].value){
				tmp = a[j];
				a[j] = a[j-1];
				a[j-1] = tmp;
			}
		}
	}
	
	for(i = 0; i < n; i++){
		if(i != n-1)printf("%c%d ", a[i].type, a[i].value);
		else printf("%c%d\n", a[i].type, a[i].value);
	}
	printf("Stable\n");
	
	for(i = 0; i < n; i++){
		minj = i;
		for(j = i; j < n; j++){
			if(b[j].value < b[minj].value)minj = j;
		}
		tmp = b[i];
		b[i] = b[minj];
		b[minj] = tmp;
	}
	
	for(i = 0; i < n; i++){
		if(i != n-1)printf("%c%d ", b[i].type, b[i].value);
		else printf("%c%d\n", b[i].type, b[i].value);
	}
	int k=0;
	for(i = 0; i < n; i++){
		if(a[i].type != b[i].type)k++;
	}
	if(k!=0)printf("Not stable\n");
	else printf("Stable\n");
	
	return 0;
}


Measured memory_bytes: 2044
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int main(){
    FAST
    int n;
    cin>>n;
    int sum=0;
    int a[n],b[n-1];
    for(int i=0;i<n-1;i++) cin>>b[i];
    sum+=b[0];
    for(int i=1;i<n-1;i++){
        if(b[i]>b[i-1])
         sum+=b[i-1];
        else sum+=b[i];
    }
    cout<<sum+b[n-2];
}

Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>


typedef struct{
    double x;
    double y;
}coordinate;


void kock(int n, coordinate p1, coordinate p2){
    if(n==0){
        return;
    }
    coordinate s;
    coordinate t;
    coordinate u;

    s.x=(2*p1.x+1*p2.x)/3;
    s.y=(2*p1.y+1*p2.y)/3;
    t.x=(1*p1.x+2*p2.x)/3;
    t.y=(1*p1.y+2*p2.y)/3;

    u.x=(t.x-s.x)*cos(M_PI/3)-(t.y-s.y)*sin(M_PI/3)+s.x;
    u.y=(t.x-s.x)*sin(M_PI/3)+(t.y-s.y)*cos(M_PI/3)+s.y;

    kock(n-1, p1, s);
    printf("%.8f %.8f\n", s);
    kock(n-1, s, u);
    printf("%.8f %.8f\n", u);
    kock(n-1, u, t);
    printf("%.8f %.8f\n", t);
    kock(n-1, t, p2);


}

int main(void){
    int n;
    scanf("%d", &n);
    coordinate p1;
    p1.x=0.0;
    p1.y=0.0;
    coordinate p2;
    p2.x=100.0;
    p2.y=0.0;

    printf("0.00000000 0.00000000\n");
    kock(n, p1, p2);
    printf("100.00000000 0.00000000\n");

    return 0;
}




Measured memory_bytes: 2052
#pragma GCC optimize ("O2")
#pragma GCC diagnostic ignored "-Wunused-variable"
#pragma GCC diagnostic ignored "-Wunused-result"
#pragma GCC diagnostic ignored "-Wunused-label"

#define DEBUG 0
#define dd if (DEBUG)

#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define trav(a, A) for (auto & a : A)
#define all(a) (a).begin (), (a).end ()
#define rall(a) (a).rbegin (), (a).rend ()
#define sz(a) (int) (a).size ()
#define szl(a) (int) (a).length ()
#define FASTIO cin.sync_with_stdio (0); cin.tie (0); cin.exceptions (cin.failbit);

typedef long long ll;
typedef pair <int, int> pii;
#define f first
#define s second
#define mp(a, b) make_pair((a), (b))
typedef vector <int> vi;
typedef vector <vi> mi;
typedef vector <ll> vll;
typedef vector <vll> mll;
#define pb(a) push_back ((a))

const ll MOD = 1e+9+7;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int INFi = 0x3f3f3f3f;
const ll MAXN = 1e+5+7;

ll fac[MAXN] = {1, 1}, facInv[MAXN] = {1, 1}, inv[MAXN] = {0, 1};

// for (i = 2; i < MAXN; ++i)
// {
//     fac[i] = fac[i - 1] * i % MOD;
//     inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
//     facInv[i] = facInv[i - 1] * inv[i] % MOD;
// }

ll calc (int n, int k)
{
    if (n < k || n < 0 || k < 0) return 0;
    return fac[n] * facInv[k] % MOD * facInv[n - k] % MOD;
}

ll mod_sum (ll a, ll b)
{
    a += b;
    if (a > MOD) a -= MOD;
    else if (a < 0) a += MOD;
    return a;
}

int main ()
{
    FASTIO;
    ll i, j, n, k, sum = 0, l;
    cin >> n >> k;
    vll A (n);
    trav (a, A)
        cin >> a;
    sort (all (A));
    for (i = 2; i < MAXN; ++i)
    {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        facInv[i] = facInv[i - 1] * inv[i] % MOD;
    }
    for (i = sum = 0; i < n; ++i)
    {
        ll qnt_min = calc (n - i - 1, k - 1), qnt_max = calc (i, k - 1);
        sum = mod_sum (sum, ((mod_sum (qnt_max, -qnt_min))*A[i])%MOD);
    }
    cout << sum << '\n';

    return 0;
}




Measured memory_bytes: 3328
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def f(n):
    r = 2
    ret = 1
    for i in range(n, n-r, -1):
        ret *= i
    for i in range(1, r+1):
        ret //= i
    return ret * 2 + n


class Bisect:
    def __init__(self, func):
        self.__func = func

    def bisect_left(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if self.__func(mid) < x:
                lo = mid+1
            else:
                hi = mid
        return lo

    def bisect_right(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if x < self.__func(mid):
                hi = mid
            else:
                lo = mid+1
        return lo

@mt
def slv(N, M, A):
    A.sort(reverse=True)
    print(A)
    b = Bisect(f)

    i = b.bisect_left(M, 1, N)
    if f(i) != M:
        i -= 1
    l = f(i)

    ans = 0
    for j in range(i):
        ans += A[j] * 2
        ans += A[j] * (i-1)

    rem = M - l
    print(i, l, rem)
    j = 0
    while rem != 0:
        ans += A[j] + A[i]
        rem -= 1
        if rem == 0:
            break
        ans += A[j] + A[i]
        rem -= 1
        if rem == 0:
            break
        j += 1


    return ans

import numpy as np
@mt
def slv2(N, M, A):
    C = Counter(A)
    L = 1 << (max(A).bit_length() + 1)
    B = [C[i] for i in range(L)]
    D = np.fft.rfft(B)
    D *= D
    E = list(map(int, np.round(np.fft.irfft(D))))
    ans = 0
    c = 0
    i = L - 1

    while c != M:
        n = E[i]
        if c + n > M:
            n = M-c
        c += n
        ans += i * n
        i -= 1

    return ans

def main():
    N, M = read_int_n()
    A = read_int_n()
    print(slv2(N, M,A))

    # N = 10**5
    # M = random.randint(1, N**2)
    # A = [random.randint(1, 10**5) for _ in range(N)]
    # print(slv(N, M, A))


if __name__ == '__main__':
    main()


Measured memory_bytes: 46600
#include <bits/stdc++.h>
using namespace std;
#define REP(i,x,n) for(int i = x; i < n; i++)
#define MAX 100
#define INF 1000000001
typedef long long ll;

int n,m;
// char X[100][100];
// int dp[1000000001];

int main(void) {
    cin >> n >> m;
    vector<int> a(n);
    REP(i,0,n) cin >> a[i];
    // cout << m << endl;
    map<int,int> ma;
    vector<int> SUM(n+1);
    SUM[0] = 0;
    REP(i,0,n) {
        SUM[i+1] = (SUM[i] + a[i]) % m;
        // cout << a[i] << endl;
        // cout << (SUM[i] + a[i]) % m << endl;
    }
    
    // REP(i,0,n+1) {
    //     cout << SUM[i] << endl;
    // }
    
    ll ans = 0;
    REP(i,0,SUM.size()) {
     ans += ma[SUM[i]];
     ma[SUM[i]]++; 
    }
    
    cout << ans << endl;
}

Measured memory_bytes: 3968