akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#include<stdlib.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)

#define MERGE_SIZE 100
typedef int MGDTIDF;
void merge_IDF(MGDTIDF d[], int l, int m, int r){
  static MGDTIDF tmp[MERGE_SIZE];
  int x = l, y = m+1;
  rep2(i, l, r+1){
    int index = -1;
    if((y == r+1) || (x < m+1 && (d[x] <= d[y]))){
      index = x;
      x++;
    }else{
      index = y;
      y++;
    }
    tmp[i] = d[index];
  }
  rep2(i, l, r+1){
    d[i] = tmp[i];
  }
}
void merge_sort_IDF(MGDTIDF d[], int l, int r){
  int m = (l+r)/2;
  if(l < m) merge_sort_IDF(d, l, m);
  if(m+1 < r) merge_sort_IDF(d, m+1, r);
  merge_IDF(d, l, m, r);
}

#define N 100
int main(void){
  int n, m;
  scanf("%d%d", &n, &m);
  int a[N];
  int sum = 0;
  rep(i, n){
    scanf("%d", &a[i]);
    sum += a[i];
  }
  merge_sort_IDF(a, 0, n-1);
  int co = 0;
  rrep(i, n){
    int now = a[i];
    if((double)now/sum < (double)1/(4*m)){
      printf("No\n");
      return 0;
    }
    co++;
    if(co == m) break;
  }
  printf("Yes\n");
  return 0;
}

Measured memory_bytes: 1640
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main() {
	int a, b, i=0,c=0,aa[100],ba[100];
	char op,opa[100];
	
	while (1){
		scanf("%d %c %d", &a, &op, &b);
		aa[i] = a;
		ba[i] = b;
		opa[i] = op;
		if ('?' == op) {
			break;
		}
		i++;
		c = i;
	}
	
	for (i = 0; i < c; i++) {
		switch (opa[i]){
			case '+':
			printf("%d\n", aa[i] + ba[i]);
			break;
			case '-':
				printf("%d\n", aa[i] - ba[i]);
				break;
			case '*':
				printf("%d\n", aa[i] * ba[i]);
				break;
			case '/':
				printf("%d\n", aa[i] / ba[i]);
				break;
		default:
			break;
		}
	}
}

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


int main(){
	long long H,W,N;
	cin >> H >> W >> N;
	int a,b;
	long long black[10]={};
	vector<pair<int,int>> vec;
	for(int i=0;i<N;i++){
		cin >> a >> b;
		for(int j=a;j>a-3;j--){
			for(int k=b;k>b-3;k--){
				if(j<=0 || k<=0)continue;
				if(j>=H-1 || k>=W-1)continue;
				vec.push_back(make_pair(j,k));
			}
		}
	}
	
	sort(vec.begin(),vec.end());
	
	if(N != 0){
	int first = vec[0].first,second = vec[0].second;
	int count = 1;
	for(int i=1;i<vec.size();i++){
		if(first == vec[i].first && second == vec[i].second){
			count++;
		}else{
			black[count]++;
			
			first = vec[i].first;
			second = vec[i].second;
			count = 1;
		}
	}
	black[count]++;
	}
	
	long long allBlack=0;
	for(int i=0;i<10;i++){
		allBlack += black[i];
	}
	black[0] = (H-2)*(W-2) - allBlack;
	
	for(int i=0;i<10;i++){
		cout << black[i] << endl;
	}
	
	return 0;
}


Measured memory_bytes: 10348
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

#ifndef U_L_LONG
typedef unsigned long long U_L_LONG;
#endif
#ifndef L_LONG
typedef long long L_LONG;
#endif

static void ABC120D_DecayedBridges();
static void ABC119C_SyntheticKadomatsu();
static void ABC120B_KthCommonDivisor();

#if 1
int main()
{
	//ABC120D_DecayedBridges();
	//ABC119C_SyntheticKadomatsu();
	ABC120B_KthCommonDivisor();

	fflush(stdout);
	return 0;
}
#endif

static void ABC120B_KthCommonDivisor()
{
	int A = 0, B = 0, K = 0;

	scanf(" %d %d %d", &A, &B, &K);

	int target = 100;
	int count = 0;
	while (1) {
		if (((A % target) == 0) && ((B % target) == 0)) {
			count++;
			if (count == K) {
				break;
			}
		}
		target--;
	}

	printf("%d\n", target);
}


Measured memory_bytes: 256
import java.util.*;
import java.lang.*;


public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int h[] = new int[n];
        for (int i = 0; i < n; i++) {
            h[i] = sc.nextInt();
        }
        Arrays.sort(h);
        int sa[] = new int[n - k + 1];
        for (int i = 0; i < n - k + 1; i++) {
            sa[i] = h[i + k - 1] - h[i];
        }
        Arrays.sort(sa);
        System.out.println(sa[0]);
    }
}

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

int main() {
  string S;
  cin >> S;

  if (S == "A"){
    cout << "T" << endl;
  }
  if (S == "T"){
    cout << "A" << endl;
  }
  if (S == "G"){
    cout << "C" << endl;
  }
  if (S == "C"){
    cout << "G" << endl;
  }
}


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

typedef long long ll;

using namespace std;

#define swap(a, b)    do { typeof(a) __tmp = (a); (a) = (b); (b) = __tmp; } while(0)
#define repd(i, a, b) for(typeof(b) i = a; i < (b); ++i)
#define rep(i, n)     repd(i, 0, n)
#define dump(x)       cerr << #x << " = " << (x) << endl
#define debug(x)      cerr << "L" << __LINE__ << ": " << #x << " = " << (x) << endl
#define YesNo(x) cout << ((x) ? "Yes" : "No") << endl
#define YESNO(x) cout << ((x) ? "YES" : "NO") << endl
                
const ll moda = 998244353;
ll log10(ll a) {ll ret = 0;while(a != 0) {a /= 10;++ret;}return ret;}
ll sub(ll a, ll b){
	a %= moda;
	b %= moda;
	if(a < b) a += moda;
	return (a - b) % moda;
}

class subsetsum {
public:
	ll n;
	vector<ll> a;
	vector<vector<ll>> table;
	ll mod;

	subsetsum() : mod(0x7FFFFFFFFFFFFFFF) {}
	subsetsum(ll n0) : mod(0x7FFFFFFFFFFFFFFF) {init(n0);}
	subsetsum(ll n0, ll mod0) : mod(mod0){init(n0);}

	void init(ll n0) {
		n = n0;
		a = vector<ll>(n, 0);
		table = vector<vector<ll>>(n + 1);
	}
	
	bool is_normal() {
		if(n == 0) return false;
		if( a.size() != n || table.size() != n + 1 ) return false;
		return true;
	}

	/*
	 *  各要素を RGB の3色に塗り分け、その色を i 個目まで決めた時に、
	 *  R を塗った要素の合計が j であるような場合の数
	 *  border 以上、sum 以下の組み合わせを数え上げ
	 */
	ll dp1(ll border, ll sum) {
		if(!is_normal()) {cerr << "dp1: is_normal() is false" << endl;return 0;}

		table = vector<vector<ll>>(n + 1, vector<ll>(sum + 1, 0));
		table[0][0] = 1;
		for(size_t i = 1; i <= sum; ++i) table[0][i] = 0;

		for(size_t i = 0; i < n; ++i) {
			for(size_t j = 0; j <= sum; ++j) {
				table[i + 1][j] = (2 * table[i][j]) % mod ;
				if(j >= a[i]) {
					table[i + 1][j] = (table[i + 1][j] + table[i][j - a[i]]) % mod;
				}
			}
		}

		ll ret = 0;
		repd(i, border, sum+1) {
			ret = (ret + table[n][i]) % mod;
		}

		return ret;
	}

	/*
	 *  各要素を RG の2色に塗り分け、その色を i 個目まで決めた時に、
	 *  R を塗った要素の合計が j であるような場合の数
	 */
	ll dp2(ll sum) {
		if(!is_normal()) {cerr << "dp1: is_normal() is false" << endl;return 0;}

		table = vector<vector<ll>>(n + 1, vector<ll>(sum + 1, 0));
		table[0][0] = 1;
		for(size_t i = 1; i <= sum; ++i) table[0][i] = 0;

		for(size_t i = 0; i < n; ++i) {
			for(size_t j = 0; j <= sum; ++j) {
				table[i + 1][j] = table[i][j];
				if(j >= a[i]) {
					table[i + 1][j] = (table[i + 1][j] + table[i][j - a[i]]) % mod;
				}
			}
		}

		return table[n][sum];
	}
};

int main(int argc, const char* argv[]) {
	ll n, sum = 0;
	cin >> n;
	subsetsum sss(n, moda);
	rep(i, n) {
		cin >> sss.a[i];
		sum += sss.a[i];
	}

	ll u = 1; rep(i, n) u = (u * 3) % moda;
	ll a = sss.dp1((sum + 2 - 1) / 2, sum);
	ll b = ( (sum % 2 == 0) ? sss.dp2(sum / 2) : 0 );

	cout << (sub(u, 3 * a) + 3 * b) % moda << endl;

	return 0;
}


Measured memory_bytes: 318016
import java.util.Scanner;

public class Main {

    static long ans = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long x = Long.parseLong(sc.next());
        for (int i = -118; i <= 119; i++) {
            for (int j = -118; j <= 119; j++) {
                if (x == (long)Math.pow(i, 5) - (long)Math.pow(j, 5)) {
                    System.out.println(i + " " + j);
                    return;
                }
            }
        }
    }
}

Measured memory_bytes: 38764
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		try (Scanner s = new Scanner(System.in)) {
			char[] array = new char[10];
			int pos = 0;
			String str = s.next();
			int n = str.length();
			for (int i = 0; i < n; i++) {
				char c = str.charAt(i);
				switch (c) {
				case 'B':
					if (pos > 0) {
						pos--;
					}
					break;
				default:
					array[pos++] = c;
					break;
				}
			}
			for (int i = 0; i < pos; i++) {
				System.out.print(array[i]);
			}
			System.out.println();
		}

	}

}


Measured memory_bytes: 21844
#include <algorithm>
#include <cassert>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <list>

using std::list;
using std::max;
using std::min;
using std::vector;

int main()
{
  int cnt = 0;
  for(int i = 0; i < 4; i++) {
    char ch = getchar();
    if(ch == '+') {
      cnt++;
    } else if(ch == '-') {
      cnt--;
    }
  }
  printf("%d\n", cnt);
  return 0;
}


Measured memory_bytes: 888
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
typedef long double ld;
const ll INF = 1e+14;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second

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

    int N; cin >> N;
    map<int, int> pf;
    for(int _n =2; _n <= N; _n++) {
      int n = _n;
      for(int i = 2; i * i <= n; i++) {
        while(n % i == 0) {
            pf[i] ++;
            n /= i;
        }
      }
      if(n != 1) pf[n] ++;
    }
    map<int, int>::iterator ite;
    int co74 = 0, co24 = 0, co14 = 0, co4 = 0, co2 = 0;
    for(ite = pf.begin(); ite != pf.end(); ite ++) {
        int k = ite->second;
        if(k >= 74) co74 ++;
        if(k >= 24) co24 ++;
        if(k >= 14) co14 ++;
        if(k >= 4) co4 ++;
        if(k >= 2) co2 ++;
    }
    cout << co74 + co24 * (co2 - 1) + co14 * (co4 - 1) + co4 * (co4 - 1) * (co2 - 2) / 2 << endl;

    return 0;
}

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

typedef long long ll;
static const ll INF = 1ll<<60;
static const ll MOD = 1e9+7;

int main(){
    int N;
    int A[100+10];
    cin>>N;
    for(int i=0; i<N; i++) cin>>A[i];

    int ans = 0;
    for(int i=0; i<N; i++){
        if((i+1)%2 != 0 && A[i]%2 != 0) ans++;
    }

    cout<<ans<<endl;
}

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

int main(){
  string s;
  cin >> s;
  string answer="Heisei";
  
  int a=s.at(5)-48,b=s.at(6)-48;
  
  if(a==1||b>4){
    answer="TBD";
  }
  cout << answer << endl;
}

Measured memory_bytes: 256
MOD = 998244353
n, s = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)
dp = Array.new(n + 1).map{Array.new(s + 1, 0)}
dp[0][0] = 1
n.times do |i|
    (s + 1).times do |j|
        dp[i + 1][j] = (dp[i + 1][j] + dp[i][j] * 2) % MOD
        if j + a[i] <= s
            dp[i + 1][j + a[i]] = (dp[i + 1][j + a[i]] + dp[i][j]) % MOD
        end
    end
end
puts dp[n][s]

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

int main(){

    ll s;
    cin >> s;

    vector<ll> a(2,0),b(2,0);
    ll t=sqrt(s)+1;
    if(t==1e+9+1)t--;
    t*=t;
    a[0]=sqrt(t);
    b[1]=a[0];
    ll u=t-s;
    for(ll j=sqrt(u);j>0;j--){
        if(u%j==0){
            a[1]=j;
            b[0]=u/j;
            break;
        }
    }
    cout << "0 0 " << a[0] << " " << a[1] << " " << b[0] << " " << b[1] << endl;
    assert(a[0]*b[1]-a[1]*b[0]==s);

    return 0;
}

Measured memory_bytes: 256
/*
Author: yww
Language: C++
Mail: weeerrr720@qq.com
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<functional>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<bitset>
#include<assert.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
void open(const char *s){
#ifndef ONLINE_JUDGE
	char str[100];sprintf(str,"%s.in",s);freopen(str,"r",stdin);sprintf(str,"%s.out",s);freopen(str,"w",stdout);
#endif
}
void open2(const char *s){
#ifdef DEBUG
	char str[100];sprintf(str,"%s.in",s);freopen(str,"r",stdin);sprintf(str,"%s.out",s);freopen(str,"w",stdout);
#endif
}
template <class T>
int upmin(T &a, const T &b){return (b<a?a=b,1:0);}
template <class T>
int upmax(T &a, const T &b){return (b>a?a=b,1:0);}
namespace io
{
	const int SIZE=(1<<20)+1;
	char ibuf[SIZE],*iS,*iT;
	char obuf[SIZE],*oS=obuf,*oT=oS+SIZE-1;
	int getc()
	{
		(iS==iT?iS=ibuf,iT=ibuf+fread(ibuf,1,SIZE,stdin):0);
		return iS==iT?EOF:*(iS++);
	}
	int f;
	char c;
	template <class T>
	void get(T &x)
	{
		f=1;
		for(c=getc();(c<'0'||c>'9')&&c!='-';c=getc());
		(c=='-'?f=-1,c=getc():0);
		x=0;
		for(;c>='0'&&c<='9';c=getc())
			x=x*10+c-'0';
		x*=f;
	}
	void flush()
	{
		fwrite(obuf,1,oS-obuf,stdout);
		oS=obuf;
	}
	void putc(char x)
	{
		*(oS++)=x;
		if(oS==oT)
			flush();
	}
	int a[55],t;
	template <class T>
	void put(T x)
	{
		if(!x)
			putc('0');
		x<0?putc('-'),x=-x:0;
		while(x)
		{
			a[++t]=x%10;
			x/=10;
		}
		while(t)
			putc(a[t--]+'0');
	}
	void space()
	{
		putc(' ');
	}
	void enter()
	{
		putc('\n');
	}
	struct flusher
	{
		~flusher()
		{
			flush();
		}
	}
	io_flusher;
}
int main()
{
	int y,m,d;
	scanf("%d/%d/%d",&y,&m,&d);
	if(y<2019||y==2019&&m<4||y==2019&&m==4&&d<=30)
		printf("Heisei\n");
	else
		printf("TBD\n");
	return 0;
}

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

int main() {
    string s, t;
    cin >> s >> t;
    rep(i,s.size()){
        if(s[i] != t[i]){
            cout << "No" << endl;
            break;
        }else if(i == s.size()-1){
            cout << "Yes" << endl;
        }
    }
    
    return 0;
}

Measured memory_bytes: 3628
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AABC
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] s = Console.ReadLine().Split(' ');
            int a = int.Parse(s[0]);
            int b = int.Parse(s[1]);

            if((a*b) == 15)
            {
                Console.WriteLine("*");
            }
            else if((a + b) == 15)
            {
                Console.WriteLine("+");
            }
            else
            {
                Console.WriteLine("x");
            }
        }
    }
}


Measured memory_bytes: 13140
#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 << "Balanced" << endl;
  else if (a+b > c+d) cout << "Left" << endl;
  else cout << "Right" << endl;
  return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
int main(){
  long N;cin>>N;long nl=to_string(N).length();
  queue<string>q;
  q.push("3");q.push("5");q.push("7");
  long ans=0;
  while(1){
    string s=q.front();q.pop();
    if(s.length()>nl){cout<<ans;return 0;}
    if(s.find("3")!=string::npos &&
      s.find("5")!=string::npos &&
      s.find("7")!=string::npos &&
      atoi(s.c_str())<=N
      )ans++;
    q.push(s+"3");q.push(s+"5");q.push(s+"7");
  }
}

Measured memory_bytes: 3584
#include<cstdio>
#include<bitset>
#define RI register int
#define CI const int&
using namespace std;
const int N=50005;
int n,m,tp,x[N<<1],y[N<<1]; char s[N<<1];
namespace Case1
{
	bitset <N> vis[N]; bool c[N];
	inline void solve(void)
	{
		RI i,j; for (i=1;i<=n;++i) vis[i].set(i);
		for (i=1;i<=m;++i) vis[x[i]]=vis[y[i]]=vis[x[i]]|vis[y[i]];
		for (i=1;i<=n;++i) if (vis[i].count()==n)
		{
			for (c[i]=1,j=m;j;--j) if (c[x[j]]) s[j]='^',c[y[j]]=1;
			else if (c[y[j]]) s[j]='v',c[x[j]]=1; else s[j]='^';
			return (void)(puts(s+1));
		}
		puts("-1");
	}
};
namespace Case2
{
	int tar[N],c[N];
	inline void solve(void)
	{
		if (n<=2) return (void)(puts("-1")); RI i;
		for (i=1;i<=n;++i) c[tar[i]=i]=1; for (i=m;i;--i)
		if (c[tar[x[i]]]>=c[tar[y[i]]]) s[i]='v',--c[tar[x[i]]],++c[tar[x[i]]=tar[y[i]]];
		else s[i]='^',--c[tar[y[i]]],++c[tar[y[i]]=tar[x[i]]]; puts(s+1);
	}
};
int main()
{
	RI i; for (scanf("%d%d%d",&n,&m,&tp),i=1;i<=m;++i)
	scanf("%d%d",&x[i],&y[i]); if (tp==1) Case1::solve(); else Case2::solve();
	return 0;
}

Measured memory_bytes: 307072
#include <bits/stdc++.h>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define REP(i,n) for(ll i=0;i<n;i++)
#define FOR(i,n1,n2) for(ll i=n1;i<n2;i++)
#define bFOR(i,n1,n2) for(ll i=n1;i>=n2;i--)
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
typedef long long int ll;
typedef unsigned long long int ull; 
typedef pair<ll,ll> Pi;
typedef tuple<ll,ll,ll> Tu;
const int INF=(ll)(1LL<<30)-1;
const double INFd=100000000000.0;
const double PI=3.14151926535;
const ll INFl=(ll)9223372036854775807;
const int MAX=10000;
const ll MOD=(ll)1e9+7;
const ll tMOD=(ll)998244353;
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 dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};
int mdx[8]={0,1,0,-1,1,1,-1,-1},mdy[8]={-1,0,1,0,1,-1,1,-1};


template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}


ll n,m,k;
ll a[200100],b[200100];

int main(){
  cin>>n>>m>>k;
  FOR(i,1,n+1)cin>>a[i];
  FOR(i,2,n+1)a[i]+=a[i-1];
  FOR(i,1,m+1)cin>>b[i];
  FOR(i,2,m+1)b[i]+=b[i-1];
  int ans=0;
  for(int i=0;i<=n;i++){
    if(a[i]>k)break;
    ll t=k-a[i];
    int seab=upper_bound(b,b+m+1,t)-b-1;
    ans=max(ans,seab+i);
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 6728
#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 1 << 20;
int n,dat[2*MAX_N-1];
void init(int n_){
  n=1;
  while(n<n_) n*=2;
  for(int i=0;i<2*n-1;i++) dat[i]=-1;
}
void update(int k,int a){
  k+=n-1;
  dat[k]=a;
  while(k>0){
    k=(k-1)/2;
    dat[k]=max(dat[k*2+1],dat[k*2+2]);
  }
}
int query(int a,int b,int k=0,int l=0,int r=n){
  if(r<=a||b<=l) return -1;
  if(a<=l&&r<=b) return dat[k];
  else{
    int vl=query(a,b,k*2+1,l,(l+r)/2);
    int vr=query(a,b,k*2+2,(l+r)/2,r);
    return max(vl,vr);
  }
}
int main(){
  init(300001);
  int m,T;
  cin>>m>>T;
  for(int i=0,x; i<m; i++) {
    cin>>x;
    update(x,x);
  }
  int d[300001];
  memset(d,0,sizeof(d));
  for(int i=2; i<=300000; i++) {
    for(int j=0;;j++) {
      if(j*i>300000) break;
      d[i]=max(d[i],query(j*i,min((j+1)*i,300001))-j*i);
    }
  }
  while(T--) {
    int x;
    cin>>x;
    cout<<d[x]<<endl;
  }
  return 0;
}


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

#define lli long long
#define FOR(i,a,b) for (lli i=(a);i<(b);i++)
#define REP(i,n) for (lli i=0;i<(n);i++)
#define rep(i,n) for (lli i=0;i<(n);i++)

#define INF INT_MAX/3
#define PB push_back
#define pb push_back
#define all(a) (a).begin(),(a),end()
#define pll pair<lli,lli>

int main(){
  lli n,Min=INF,Max=-INF,sum=0;
  lli a[10000];
  cin>>n;
  rep(i,n){
    cin>>a[i];
    Min=min(Min,a[i]);
    Max=max(Max,a[i]);
    sum+=a[i];
  }

  cout<<Min<<" "<<Max<<" "<<sum<<endl;
  
  return 0;
}

Measured memory_bytes: 3152
#include <bits/stdc++.h>
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (ll i = (ll)(a); i < (ll)(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define ll long long
#define lld long double
#define ALL(x) x.begin(), x.end()
#ifdef DEBUG
#define line() cerr << "[" << __LINE__ << "] ";
#define dump(i) cerr << #i ": " << i << " ";
#define dumpl(i) cerr << #i ": " << i << endl;
#else
#define line(i)
#define dump(i)
#define dumpl(i)
#endif
using namespace std;
int main(int argc, char const *argv[])
{
    int n, c;
    cin >> n >> c;
    vector<vector<int>> v(n, vector<int>(3, 0));
    rep(i, n)
    {
        cin >> v[i][0] >> v[i][1] >> v[i][2];
    }
    sort(ALL(v));
    vector<int> a(c, 1 << 30);
    int ans = 0;
    rep(i, n)
    {
        rep(j, c)
        {
            if (j == ans)
            {
                a[ans] = v[i][1];
                // cerr << ans << " " << v[i][1] << " " << v[i][0] << endl;
                ans++;
                break;
            }
            if (a[j] < v[i][0])
            {
                //cerr << j << " " << v[i][1] << " " << v[i][0] << endl;
                a[j] = v[i][1];
                break;
            }
        }
        sort(ALL(a));
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 5760
#include <bits/stdc++.h>
using namespace std;
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define in(x,y,h,w) x >= 0 && x < h && y >= 0 && y < w

#define int long long
//typedef    long long          ll;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      P;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
 
const int INF=1e+18;
const double EPS=1e-9;
const int MOD=998244353;

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

struct bimatch{
	int n;
	vector<vector<int>> G;
	vector<int> match;
	vector<bool> used;
	bimatch(int siz) : n(siz),G(siz),match(siz),used(siz){}
	void add_edge(int u,int v){
		G[u].pb(v);
		G[v].pb(u);
	}
	bool dfs(int v){
		used[v] = true;
		for(int i = 0;i < G[v].size();i++){
			int u = G[v][i],w = match[u];
			if(w < 0 || !used[w] && dfs(w)){
				match[v] = u;
				match[u] = v;
				return true;
			}
		}
		return false;
	}
	int build(){
		int res = 0;
		for(int i = 0;i < n;i++) match[i] = -1;
		for(int v = 0;v < n;v++){
			if(match[v] < 0){
				for(int i = 0;i < n;i++) used[i] = false;
				if(dfs(v)) res++;
			}
		}
		return res;
	}
};

int a[110][110],ans1[110][110],ans2[110][110];

signed main(){
	int n,m;
	cin >> n >> m;
	for(int i = 0;i < n;i++){
		for(int j = 0;j < m;j++){
			cin >> a[i][j]; a[i][j]--;
		}
	}
	for(int i = 0;i < m;i++){
		bimatch bim(n * 2);
		int used[110][110];
		for(int j = 0;j < n;j++){
			for(int k = 0;k < n;k++) used[j][k] = -1;
		}
		for(int j = 0;j < n;j++){
			for(int k = 0;k < m;k++){
				if(a[j][k] >= 0 && used[j][a[j][k] / m] < 0){
					bim.add_edge(j + n,a[j][k] / m);
					used[j][a[j][k] / m] = k;
				}
			}
		}
		bim.build();
		for(int j = 0;j < n;j++){
			int aite = bim.match[j + n];
			ans1[j][i] = a[j][used[j][aite]];
			a[j][used[j][aite]] = -1;
		}
	}
	for(int i = 0;i < n;i++){
		for(int j = 0;j < m;j++) cout << ans1[i][j] + 1 << " ";
		cout << endl;
	}
	for(int i = 0;i < m;i++){
		vector<int> vec;
		for(int j = 0;j < n;j++) vec.pb(ans1[j][i]);
		sort(all(vec));
		for(int j = 0;j < n;j++) ans2[j][i] = vec[j];
	}
	for(int i = 0;i < n;i++){
		for(int j = 0;j < m;j++) cout << ans2[i][j] + 1 << " ";
		cout << endl;
	}
}

Measured memory_bytes: 884
import java.util.Scanner;
import java.math.BigDecimal;
public class Main{
	static int calculate(int yen){
		BigDecimal bd = new BigDecimal(yen*1.05);
		BigDecimal bd1 = bd.setScale(-3, BigDecimal.ROUND_UP);
		return bd1.intValue();
	}
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int yen = 100000;
		for(int i=0;i<n;i++){
			yen =calculate(yen);
		}
		System.out.println(yen);
		scan.close();
	}
}

Measured memory_bytes: 17256
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<string>
using namespace std;

typedef long long ll;
const int INF = 1e+9;

int main() {
	int a[5], mi = 10, sum = 0;
	for (int i = 0; i < 5; ++i) {
		cin >> a[i];
		if (a[i] % 10)
			mi = min(mi, a[i] % 10);
		sum += ceil(a[i] / 10.0) * 10;
	}
	cout << sum + mi - 10 << endl;
	return 0;
}

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

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<pdd> vdd;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define mem(a,b) memset(a, b, sizeof(a) )
#define all(x) (x).begin(),(x).end()
#define INF 1000000000000
#define MOD 1000000007
#define PB push_back
#define MP make_pair
#define F first
#define S second

inline void normal(ll &a) { a %= MOD; (a < 0) && (a += MOD); }
inline ll modMul(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a*b)%MOD; }
inline ll modAdd(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a+b)%MOD; }
inline ll modSub(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); a -= b; normal(a); return a; }
inline ll modPow(ll b, ll p) { ll r = 1; while(p) { if(p&1) r = modMul(r, b); b = modMul(b, b); p >>= 1; } return r; }
inline ll modInverse(ll a) { return modPow(a, MOD-2); }
inline ll modDiv(ll a, ll b) { return modMul(a, modInverse(b)); }

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}

int main(){
    int h,w,a,b;
    cin>>h>>w>>a>>b;
    vector<string>hw(h);
    rep(i,h){
        rep(j,w){
            if(h-i>b){
                if(j<a){
                    hw[i].PB('0');
                }
                else{hw[i].PB('1');}
            }
            else{
                if(j<a){
                    hw[i].PB('1');
                }
                else{
                    hw[i].PB('0');
                }
            }
        }
    }
    rep(i,h){
         cout<<hw[i]<<endl;
    }
}


Measured memory_bytes: 2304
import bisect
N,M=map(int,input().split())
A=list(map(int,input().split()))
cards=[list(map(int,input().split())) for _ in range(M)]
cards.sort(key=lambda x:x[1],reverse=True)
A.sort()
tmpsum=[0]*(N+1)
allsum=sum(A)
buf=0
id=0
l=0
r=0
for i in range(N):
    buf=buf+A[i]
    tmpsum[i+1]=buf
#print(cards,A,tmpsum)
i=0
while (r<N)and(i<M):
    l=r
    r=min(r+cards[i][0],N)
    #print(l,r)
    if A[min(r,N-1)]<cards[i][1]:
        allsum=allsum-(tmpsum[r]-tmpsum[l])+cards[i][1]*(r-l)#cards[i][0]
    elif A[l]>=cards[i][1]:#A[r]=>cards[i][1]
        break
    else:#A[r]=>cards[i][1],A[l]<cards[i][1]
        id=bisect.bisect_left(A,cards[i][1])
        allsum=allsum-(tmpsum[id]-tmpsum[l])+cards[i][1]*(id-l)
        break
    i=i+1
print(allsum)



Measured memory_bytes: 82200
n = int(input())
a = list(map(int,input().split()))
ai = [(val, ind) for ind,val in enumerate(a)]
ai.sort(reverse=True)

dp = [[0] * (n+1) for _  in  range(n+1)]
for i,tmp in enumerate(ai,1):
    val , val_i = tmp
    for right in range(i+1):
        left = i-right
        if(left==0):
            dp[left][right] = dp[left][right-1] + val * abs((n-right)  - val_i)
        elif(right==0):
            dp[left][right] = dp[left-1][right] + val * abs((val_i - (left-1)))
        else:
            dp[left][right] = max(dp[left][right-1] + val * abs((n-right)  - val_i),
                                    dp[left-1][right] + val * abs((val_i - (left-1))))


ans = 0
for i in range(n+1):
    ans = max(ans, dp[n-i][i])
print(ans)

Measured memory_bytes: 100256
// template version 1.2
using namespace std;
#include <iostream>
#include <bits/stdc++.h>

#define infile "../test/sample-1.in"
#define int long long
// #define INF 2147483647
#define INF 1000000000000000000LL
#define MOD 1000000007LL

// {{{ define basic macro
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define _rrep(i,n) rrepi(i,0,n)
#define rrepi(i,a,b) for(int i=(int)(b-1);i>=(int)(a);--i)
#define rrep(...) _overload3(__VA_ARGS__,rrepi,_rrep,)(__VA_ARGS__)

#define foreach(x,a) for(auto& (x) : (a) )
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)

#define all(x) (x).begin(),(x).end()
#define sum(v) accumulate(all(v), 0LL)
#define sz(x) ((int)(x).size())
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define uni(x) sort(all(x));x.erase(unique(all(x)),x.end())
#define ten(n) ((int)1e##n)

template<class T> inline void chmax(T &a, const T &b) { if(a < b) a = b; }
template<class T> inline void chmin(T &a, const T &b) { if(a > b) a = b; }

template<typename A, size_t N, typename T> // n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

template <class T = int>
T in() {T x; cin>>x; return (x);}

struct Fast {
  Fast(){
    std::cin.tie(0);
    ios::sync_with_stdio(false);
  }
} fast;
// }}}
//{{{ dump macro
#ifdef PCM
  #include "dump.hpp"
#else
  #define dump(...) 42
  #define dump_1d(...) 42
  #define dump_2d(...) 42
#endif
//}}}
//{{{ others
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long double ld;
typedef pair<int,int> pii;
typedef tuple<int,int,int> iii;
template<typename T>
using PQ = priority_queue<T, vector<T>, greater<T>>;

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

struct RangeSumVector {/*{{{*/
  vector<int> data;
  vector<int> a_sum; //accumulative sum
  RangeSumVector(){}

  int &operator[](int i){
    return data[i];
  }
  void push_back(int v){
    data.push_back(v);
  }

  void calc(){
    a_sum = vector<int>(sz(data));
    a_sum[0] = data[0];
    for(int i=1; i<sz(data); i++){
      a_sum[i] += a_sum[i-1] + data[i];
    }
  }

  int rsum(int l, int r) {  // return sum of [l, r] of data.
    l = std::max(0LL, l);
    r = std::min(r, sz(a_sum)-1);
    if (l > r) return 0;
    return a_sum[r] - (l-1>=0 ? a_sum[l-1] : 0);
  }
};/*}}}*/

int solve(){
  string A;cin>>A;
  int n = sz(A);
  int dp[n]={}; dp[0] = 1;
  vector<RangeSumVector> x(26);

  rep(i, n){
    rep(j, 26){
      int alp = A[i]-'a';
      if (j==alp){
        x[j].pb(1);
      }
      else{
        x[j].pb(0);
      }
    }
  }
  rep(i, 26){
    x[i].calc();
  }

  rep(i, 1, n){
    dp[i] = dp[i-1];
    int idx = A[i]-'a';
    dp[i] += i;
    dp[i] -= x[idx].rsum(0, i-1);
  }

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

  return 0;
}

int test(){ //{{{
  return 0;
}
//}}}

signed main() { //{{{
#ifdef INPUT_FROM_FILE
  std::ifstream in(infile);
  std::cin.rdbuf(in.rdbuf());
#endif
#ifdef PCM
  test();
#endif
  solve();
  return 0;
} //}}}


Measured memory_bytes: 84508
#include <iostream>
#include <algorithm>
#include <array>
#include <cstdint>
#include <functional>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string>
#include <utility>
#include <vector>

#define INF 1000000000
#define MOD 1000000007
#define rep(i,a,b) for(uint32 i = (a); i < (b); ++i)
#define bitget(a,b) (((a) >> (b)) & 1)
#define ALL(x) (x).begin(),(x).end()
#define C(x) std::cout << #x << " : " << x << std::endl
#define scanf scanf_s

using int32 = std::int_fast32_t;
using int64 = std::int_fast64_t;
using uint32 = std::uint_fast32_t;
using uint64 = std::uint_fast64_t;

uint32 getd(uint64 a) {
	uint32 ret = 0;
	while (a) {
		++ret;
		a /= 10;
	}
	return ret;
}

int main(void) {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	uint32 n;
	std::cin >> n;
	std::vector<std::pair<uint32,uint32>> a(n);
	rep(i, 0, n) {
		std::cin >> a[i].first;
		a[i].second = i;
	}
	std::sort(ALL(a));
	uint32 c[2][2] = {};
	rep(i, 0, n)
		++c[i & 1][a[i].second & 1];
	std::cout << c[0][1] << "\n";
	return 0;
}

Measured memory_bytes: 1792
//satyaki3794
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define MOD (1000000007LL)
#define LEFT(n) (2*(n))
#define RIGHT(n) (2*(n)+1)

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef pair<ii, int> iii;

ll pwr(ll base, ll p, ll mod = MOD){
ll ans = 1;while(p){if(p&1)ans=(ans*base)%mod;base=(base*base)%mod;p/=2;}return ans;
}


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


int cnt[26];


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

    for(int i=0;i<26;i++)
        cnt[i] = MOD;

    int n;
    cin>>n;
    while(n--){
        string str;
        cin>>str;
        vector<int> cnt_(26, 0);
        for(int i=0;i<(int)str.length();i++)
            cnt_[str[i]-'a']++;
        for(int i=0;i<26;i++)
            cnt[i] = min(cnt[i], cnt_[i]);
    }

    for(int i=0;i<26;i++)
        while(cnt[i]--)
            cout<<((char)('a'+i));
    return 0;
}
 









Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int BIT = 22-6+1;
const int N = 100;
ll dp[N][1<<BIT];

ll solve(int n,int *mask,ll *val){
  for(int i=0;i<n;i++)
    for(int j=0;j<(1<<BIT);j++)dp[i][j]=0;
  dp[0][0]=0;
  dp[0][mask[0]]=val[0];
  for(int i=1;i<n;i++){
    for(int j=0;j<(1<<BIT);j++){
      dp[i][j]=max(dp[i][j],dp[i-1][j]);
      if (j&mask[i])continue;
      dp[i][j|mask[i]] = max(dp[i][j|mask[i]],dp[i-1][j]+val[i]);
    }
  }
  ll ret = 0;
  for(int i=0;i<(1<<BIT);i++)ret=max(ret,dp[n-1][i]);
  return ret;
}

main(){
  int n;
  while(cin>>n && n){
    int mask[n];ll val[n];
    for(int i=0;i<n;i++){
      int m;cin>>m>>val[i];
      mask[i]=0;
      for(int j=0;j<m;j++){
	int f,t;
	cin>>f>>t;
	f-=6;
	t-=6;
	while(f < t)mask[i]|=(1<<f),f++;
      }
    }
    cout << solve(n,mask,val) << endl;
  }
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
#define N 500005
using namespace std;
int n,x,kk,a[N],head[N],dp[N],g[2][N];
struct Tree{int nxt,to;}e[N];
inline void link(int x,int y){e[++kk].nxt=head[x];e[kk].to=y;head[x]=kk;}
void dfs(int u){
	for (int i=head[u];i;i=e[i].nxt) dfs(e[i].to);
	memset(g,63,sizeof(g));g[0][0]=0;
	int now=0,last=1;
	for (int i=head[u];i;i=e[i].nxt){
		swap(now,last);int v=e[i].to;
		memset(g[now],63,sizeof(g[now]));
		for (int j=a[u];~j;j--){
			if (j-a[v]>=0) g[now][j]=min(g[last][j-a[v]]+dp[v],g[now][j]);
			if (j-dp[v]>=0) g[now][j]=min(g[last][j-dp[v]]+a[v],g[now][j]);
		}
	}
	for (int i=0;i<=a[u];i++) dp[u]=min(dp[u],g[now][i]);
}
int main(){
	memset(dp,127,sizeof(dp));
	scanf("%d",&n);
	for (int i=2;i<=n;i++){
		scanf("%d",&x);
		link(x,i);
	}
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	dfs(1);
	if (dp[1]<1e9) puts("POSSIBLE");
	else puts("IMPOSSIBLE");
	return 0;
}

Measured memory_bytes: 10624
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <sstream>
#include <string>
#include <map>
#include <set>
using namespace std;

#define loop(i,a,b) for(int i=(a);i<int(b);i++)
#define rep(i,b) loop(i,0,b)
#define all(c) (c).begin(), (c).end()

int main(){
    int s;
    while(cin >> s && s){
        rep(i,9){
            int p;cin>>p;
            s-=p;
        }
        cout << s << endl;
    }
}

Measured memory_bytes: 1160
#include <stdio.h>
#include <stdlib.h>
#define N 10



int main(void){
    int n,x,t,total_time;
    scanf("%d %d %d",&n,&x,&t);

    total_time = (n / x) * t;
    if(n % x != 0){
        total_time += t;
    }
    printf("%d\n",total_time);
    return 0;
}

Measured memory_bytes: 1728
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(a); (i)<(b); ++(i))
#define rFor(i, a, b) for(int (i)=(a)-1; (i)>=(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef pair<int, int> pii;

const lint mod = 1e9 + 7;

lint powmod(long x, long n){
  lint ret = 1;
  while(n > 0){
    if(n&1) ret *= x, ret %= mod, n -= 1;
    else x *= x, x %= mod, n >>= 1;
  }
  return ret;
}

vector<lint> fact;
vector<lint> revfact;

void setfact(int n){
  fact.resize(n+1); revfact.resize(n+1);
  fact[0] = 1;
  rep(i, n) fact[i+1] = fact[i] * (i+1) % mod;
  
  revfact[n] = powmod(fact[n], mod-2);
  for(int i=n-1; i>=0; i--) revfact[i] = revfact[i+1] * (i+1) % mod;
}

int main(){
    int n;
    string s;
    cin >> n >> s;
    if(s[0] == 'W' || s[2*n-1] == 'W'){
        printf("0\n");
        return 0;
    }
    int ed[2*n];
    ed[0] = 0;
    int cnt = 0;
    rep(i, 2*n-1){
        ed[i+1] = ed[i] ^ (s[i] == s[i+1]);
        cnt += ed[i+1];
    }
    if(cnt != n){
        printf("0\n");
        return 0;
    }
    setfact(n);
    lint ans = fact[n];
    lint cur = 0;
    rep(i, 2*n){
        if(ed[i]) ans = ans * (cur--) % mod;
        else ++cur;
    }
    printf("%lld\n", ans);
}

Measured memory_bytes: 2948
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,f[2200005][22],nxt[2200005][4];
char s[1200005];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=0;i<=n;i++)
	{
		scanf("%s",s);
		for(int j=0;j<(1<<i);j++)
			if(s[j]=='1') f[(1<<i)+j][i]=1;
	}
	//nxt[1][0]=nxt[1][1]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<(1<<i);j++)
		{
			int nw=(1<<i)+j;
			if(j&(1<<(i-1)))
			{
				nxt[nw][1]=nw-(1<<i);
				nxt[nw][0]=nxt[nw-(1<<i)][0];
				nxt[nw][2]=nxt[nw-(1<<i)][2];
				nxt[nw][3]=i-1;
			}
			else
			{
				nxt[nw][0]=nw-(1<<(i-1));
				nxt[nw][1]=nxt[nw-(1<<(i-1))][1];
				nxt[nw][3]=nxt[nw-(1<<(i-1))][3];
				nxt[nw][2]=i-1;
			}
		//	printf("i=%d,j=%d,nw=%d,nxt=%d,%d,%d,%d\n"
		//	,i,j,nw,nxt[nw][0],nxt[nw][1],nxt[nw][2],nxt[nw][3]);
		}
	}
	for(int i=n;i>0;i--)
		for(int j=i;j<=n;j++)
		{
			for(int k=0;k<(1<<j);k++)
			{
				int nw=(1<<j)+k,t=(k&((1<<i)-1))+(1<<i),tnw=(nw>>i)<<i;
				int len0=nxt[t][2],len1=nxt[t][3],nw0=nxt[t][0]-(1<<len0),nw1=nxt[t][1];
				f[tnw>>i][0]+=f[nw][i];
				if(nxt[t][0]) f[(tnw>>(i-len0-1))+nw0][len0]+=f[nw][i];
				if(nxt[t][1]) f[(tnw>>(i-len1-1))+nw1][len1]+=f[nw][i];
				//if(f[nw][i])printf("i=%d,j=%d,k=%d,nw=%d,t=%d,len=%d,%d,nw=%d,%d,f=%d,nxtf=(%d,%d),(%d,%d)\n"
			//	,i,j,k,nw,t,len0,len1,nw0,nw1,f[nw][i],(tnw>>(i-len0-1))+nw0,len0,(tnw>>(i-len1-1))+nw1,len1);
			}
		}
	for(int i=n;i>=0;i--)
		for(int j=0;j<(1<<i);j++)
		{
			if(f[(1<<i)+j][0]>=m)
			{
			//	printf("i=%d,j=%d\n",i,j);
				for(int k=i-1;k>=0;k--)
					printf("%d",(j>>k)&1);
				return 0;
			}
		}
	return 0;
}

Measured memory_bytes: 217216
/*#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#pragma GCC target("avx2")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")*/
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <math.h>
#include <cmath>
#include <vector>
#include <map>
#include <algorithm>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <cassert>
#include <random>
#include <deque>
#include <bitset>
#include <string>
#include <queue>
#include <complex>

//#define int long long

#define mp(a, b) make_pair(a, b)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

#define endl '\n'


using namespace std;
typedef long long ll;
typedef long double ld;

mt19937 mrand(random_device{}());

const double PI = acos((double)-1);
const double eps = 1e-7;
const ll inf0 = 1023 * 1024 * 1024;
const ll inf = inf0 * inf0;
const ll mod = 1e9 + 7;
//const ll mod = 998244353;

void solve();
void scan();

signed main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
	cout << fixed; cout.precision(15);
	solve();
	return 0;
}

void solve() {
	int n, m;
	cin >> n >> m;
	vector<pair<int, int>> ans;
	int cur = n - 1;
	vector<bool> used(n + 1, false);
	for (int i = 1; i <= n; i++) {
		while ((cur > 0 && used[cur]) || 2 * cur == n)
			cur--;
		if (cur <= 0) break;
		ans.push_back({ i, i + cur });
		used[cur] = true;
		used[n - cur] = true;
		cur -= 2;
	}
	for (int i = 0; i < m; i++)
		cout << ans[i].first << " " << ans[i].second << endl;
	return;
}

Measured memory_bytes: 4244
#include"bits/stdc++.h"
using namespace std;

//typedef
//------------------------------------------
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
typedef vector<string> VS;
typedef pair<LL, LL> PLL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define PB push_back
#define MP make_pair
#define SORT(c) sort((c).begin(),(c).end())
#define COUT(x) cout<<x<<endl

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double PI = acos(-1.0);
const LL MOD = 1e9 + 7;
const ULL INF= 1e20;

//function
//--------------------------------------------
LL gcd(LL, LL);
bool isEven(LL);
void coutY();
void coutN();

int main() {
	LL n;
	cin >> n;
	LL a, b, c, d;
	cin >> a >> b >> c >> d;
	string s;
	cin >> s;
	FOR(i, a, max(c,d)) {
		if (s[i - 1] == '#' && s[i] == '#') {
			coutN();
			return 0;
		}
	}
	if (c > d) {
		FOR(i, b-1, d) {
			string tmp = s.substr(i-1, 3);
			if (tmp == "...") {
				coutY();
				return 0;
			}
		}
		coutN();
		return 0;
	}
	coutY();
	return 0;
}

LL gcd(LL a, LL b) {
	if (a == 0 || b == 0)return 0;
	if (a < b)swap(a, b);
	if (a % b == 0)return b;
	else gcd(b, a % b);
}
bool isEven(LL a) {
	return !((bool)(a % 2));
}
void coutY() {
	cout << "Yes" << endl;
	return;
}
void coutN() {
	cout << "No" << endl;
	return;
}

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

int main(){
    int K,H1,H2,M1,M2;
    cin>>H1>>M1>>H2>>M2>>K;
    int sum = (H2-H1)*60 + (M2-M1);
    cout<<sum-K;
    return 0;
}

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

using namespace std;

int main()
{
    long long n,k,i,ans=0;
    cin>>n>>k;
    int a[n];
    for(i=0;i<n;i++)
    {
       cin>>a[i];
    }
    sort(a,a+n);
    for(i=0;i<n;i++)
   {
     if(a[i]>=k)
     {
       ans=n-i;
       break;
     }
   }
   cout<<ans;
    return 0;
}


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

map<string, int> M;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	string s;
	cin >> n;
	for (int i =0; i < n; i++){
		cin >> s;
		M[s]++;
	}
	vector<pair<int, string>> vet;
	for (map<string, int>::iterator it = M.begin(); it != M.end(); it++){
		vet.push_back({it->second * -1, it->first});
	}
	sort(vet.begin(), vet.end());
	for (int i = 0; i < vet.size() && vet[i].first == vet[0].first; i++){
		cout << vet[i].second << endl;
	}
	return 0;
}

Measured memory_bytes: 29324
object Main{
  def main(args:Array[String]) = {
    val sc = new java.util.Scanner(System.in)
    val List(n,m,c) = List.fill(3)(sc.nextInt)
    val bList = List.fill(m)(sc.nextInt)
    val count = (1 to n).map(_ => List.fill(m)(sc.nextInt).zip(bList).map{case (x,y) => x*y}.sum).count(_ > -c)
    println(count)
  }
}

Measured memory_bytes: 27604
#include <bits/stdc++.h>
using namespace std;
//P,Q大きさNの順列で、Pの辞書順aとQの辞書順bの差を求める


int main(){
  int N;
  cin >> N;
  vector<int> v(N);
  vector<int> P(N);
  vector<int> Q(N);
  
  for(int i= 0;i<N;i++){
    cin >> P[i];
  }
  for(int i= 0;i<N;i++){
    cin >> Q[i];
  }
  for(int i = 1;i<=N;i++){
    v[i-1] = i;
  }
  sort(v.begin(), v.end());
  int a = 0;
  do {
    // 1行で今の並び方を出力
    
    vector<int> R;
    a++;
    
    for (int x : v) {
      R.push_back(x);
    }

    if(R == P) break;
  } while (next_permutation(v.begin(), v.end()));

  
  sort(v.begin(), v.end());
  int b = 0;
  do {
    // 1行で今の並び方を出力
    
    vector<int> R;
    b++;
  
    for (int x : v) {
      R.push_back(x);
    }
 
    if(R == Q) break;
  } while (next_permutation(v.begin(), v.end()));
  
  
  cout << abs(a-b) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
typedef long long i64;
int main(){
  int D,N;
  cin >> D >> N;
  N = (N==100 ? 101:N);
  cout << ((int)pow(100,D))*N << endl;
  return 0;
}

Measured memory_bytes: 892
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
using namespace std;
int main() {
	int a,b;
	cin>>a>>b;
	if(a>8 || b>8)
		cout<<":("<<endl;
	else
		cout<<"Yay!"<<endl; 
	return 0;
} 

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

int n, x[1000010], a[1000010];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%1d", &x[i]);
    }
    for (int i = 1; i < n; i++) {
        a[i] = abs(x[i] - x[i + 1]);
    }
    n--;
    bool flag = 1;
    for (int i = 1; i <= n; i++) {
        flag &= (a[i] == 0 || a[i] == 2);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (flag && a[i] == 2) a[i] = 1;
        if (((n - 1) & (i - 1)) == (i - 1)) (ans += a[i]) %= 2;
    }
    if (flag && ans) ans = 2;
    printf("%d\n", ans);
    return 0;
}

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

#if DEBUG && !ONLINE_JUDGE
  #include "header.h"
#else
  #define debug(args...)
#endif

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

#define pb push_back
#define all(x) x.begin(),x.end()
#define SZ(x) (int)(x).size()
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define rep(i,a,b) for(auto i=(a);i<b;i++)

#define INF (int)1e9
#define EPS 1e-9
#define MOD 1000000007
void preprocess(void) {
  return;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.precision(20);
  //freopen("input.txt","r",stdin);
  //freopen("output.txt","w",stdout);
  preprocess();
  int n; cin>>n;
  vector<long double> ar(n);
  rep(i,0,n) cin>>ar[i];
  sort(all(ar));
  long double sum = 0;
  rep(i,1,n) {
    sum = (ar[i] + ar[i-1])/2;
    ar[i] = sum;
  }
  cout<<ar[n-1]<<endl;
}



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

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

    if (a <= 0 && 0 <= b) cout << "Zero" << endl;
    else if (0 < a) cout << "Positive" << endl;
    else if (b < 0 && (b - a) % 2 != 0) cout << "Positive" << endl;
    else if (b < 0 && (b - a) % 2 == 0) cout << "Negative" << endl; 
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
ll read(){
	ll a=0,b=getchar(),c=1;
	while(!isdigit(b))c=b=='-'?-1:1,b=getchar();
	while(isdigit(b))a=a*10+b-'0',b=getchar();
	return a*c;
}
ll n,d,a,ans,sum,ab;
pii p[200005];
queue<pii> q;
int main(){
	n=read(),d=read()*2,a=read();
	for(int i=1;i<=n;i++)
		p[i].first=read(),p[i].second=read();
	sort(p+1,p+n+1);
	for(int i=1;i<=n;i++){
		while(!q.empty() and p[i].first>q.front().first)
			sum-=q.front().second,q.pop();
		ab=p[i].second-sum;
		if(ab<=0)continue;
		ab=(ab+a-1)/a;
		ans+=ab,sum+=ab*a;
		q.push(pii{p[i].first+d,ab*a});
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 4992