akhauriyash/Code-Regression huggingface dataset:
import math
def getInt(): return int(input())
def getIntList(): return [int(x) for x in input().split()]
def zeros(n): return [0]*n
class Debug():
    def __init__(self):
        self.debug = True
 
    def off(self):
        self.debug = False
 
    def dmp(self, x, cmt=''):
        if self.debug:
            if cmt != '':
                w = cmt + ': ' + str(x)
            else:
                w = str(x)
            print(w)
        return x
def prob(): 
    d = Debug()
    d.off()
    N, K = getIntList()
    d.dmp((N, K), 'N, K')
    A = getIntList()
    d.dmp((A), 'A')
    if K == 0:
        x = 0
    else:
        lg = int(math.log2(K))
        mask = 1 << lg
        x = 0
        d.dmp(x,'x')
        lessK = False  # x<Kか否か
        while mask > 0:
            cz, co = 0, 0
            for i in range(N):
                if A[i] & mask == 0:
                    cz += 1
                else:
                    co += 1
            if cz > co:
                if K & mask or lessK:
                    x += mask
            if (x & mask == 0) and mask & K:
                lessK = True
            mask >>= 1
            d.dmp((mask,x),'mask,x')
    d.dmp((x),'x')
    ans = 0
    for i in range(N):
        d.dmp((x ^ A[i]),'x ^ A[i]')
        ans += x ^ A[i]
    return ans


ans = prob()
print(ans)


Measured memory_bytes: 14840
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <math.h>
#include <limits.h>

int main(void){
    int n,k,ans=0,a[11]={};
    scanf("%d%d",&n,&k);
    for (int i=0; i<11; i++){
        for (int j=1; j<6; j++){
            a[(((i*7)+j)*9+72)%11]++;
        }
    }
    ans+=(n-2)/11*a[k];
    
    //printf("%d\n",ans);
    
    for (long long i=(n-2)/11*11; i<n-2; i++){
        //printf("%lld\n",i);
        if ( (((i*7)+1)*9+72)%11==k || (((i*7)+2)*9+72)%11==k || (((i*7)+3)*9+72)%11==k || (((i*7)+4)*9+72)%11==k || (((i*7)+5)*9+72)%11==k){
            ans++;
        }
        //printf("%lld %lld %lld %lld %lld\n",(((i*7)+1)*9+72)%11,(((i*7)+2)*9+72)%11,(((i*7)+3)*9+72)%11,(((i*7)+4)*9+72)%11,(((i*7)+5)*9+72)%11);
    }
    printf("%d\n",ans);
	return 0 ;
}

Measured memory_bytes: 128
import java.util.Scanner;

public class Main{

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);

		String strArray[] = sc.next().split("/");

		int y = Integer.parseInt(strArray[0]);
		int m = Integer.parseInt(strArray[1]);
		int d = Integer.parseInt(strArray[2]);

		boolean tbd = false;

		if(m >= 5){
			tbd = true;
		}

		System.out.println(tbd ? "TBD" : "Heisei");
	}

}


Measured memory_bytes: 21716
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main(){
  int  A,B,C,X,Y;
  cin  >> A >> B >> C >> X >> Y;
  int t=1000000000;
  int a,b;
  for(int i=0; i<100001; i++){
    a=X-i;
    b=Y-i;
    if(a<0){a=0;}
    if(b<0){b=0;}
    if(A*a+B*b+C*2*i<=t){t=A*a+B*b+C*2*i;}
  }
  cout << t <<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<math.h>
#include<algorithm>
#include<vector>
#define rep(i,n) for(i = 0; i < n; i++)
using namespace std;
//無様なコード　2番めに多いものを探す方法はもっといいものが有るはず
int main2(), main();
const int arrlen = 100001;


int main(){
   int n,k,q,i,j;
   cin>> n>>k>>q;
   vector<int> a(q);
   vector<int> na(n,0);
   rep(i,q) cin>>a[i];
   rep(i,q) na[a[i]-1]++;

   int threadshold = q - k + 1;
   int ans = 0;
   
   //cout << "threadshold = " << threadshold << endl; 
   rep(i,n){
       if(na[i] >= threadshold) cout << "Yes" << endl;
       else cout <<"No" << endl;
   }

}

Measured memory_bytes: 1408
void main() {
	auto ip = readAs!(int[]), N = ip[0], M = ip[1];
	int k = N;
	while(k <= M/2) {
		auto r = M % k;
		if(r == 0) {
			writeln(M / k);
			return;
		}
		k++;
	}
	writeln(1);
}

// ===================================

import std.stdio;
import std.string;
import std.functional;
import std.algorithm;
import std.range;
import std.traits;
import std.math;
import std.container;
import std.bigint;
import std.numeric;
import std.conv;
import std.typecons;
import std.uni;
import std.ascii;
import std.bitmanip;
import core.bitop;

T readAs(T)() if (isBasicType!T) {
	return readln.chomp.to!T;
}
T readAs(T)() if (isArray!T) {
	return readln.split.to!T;
}

T[][] readMatrix(T)(uint height, uint width) if (!isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		res[i] = readAs!(T[]);
	}
	return res;
}

T[][] readMatrix(T)(uint height, uint width) if (isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		auto s = rs;
		foreach(j; 0..width) res[i][j] = s[j].to!T;
	}
	return res;
}

int ri() {
	return readAs!int;
}

double rd() {
	return readAs!double;
}

string rs() {
	return readln.chomp;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll =long long;
#define all(v) v.begin(),v.end()
 
int main() {
ll N,A,B;
  cin>>N>>A>>B;
  ll ans=0;
  for(ll i=1;i<=N;i++) {
string S=to_string(i);
    ll count=0;
    for(auto x:S) {
count+=x-'0';
    }
    if(count>=A&&count<=B) {
ans+=i;
    }
  }
  
  
  cout<<ans<<endl;
}


Measured memory_bytes: 3664
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;

public class Main {
    public static void main(String args[]){
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        try{
            String line;
            int recC=0,lozC=0;
            while((line=br.readLine())!=null){  if(line.equals(""))break;
                String[] splited = line.split(",");
                int n1 = Integer.parseInt(splited[0]);
                int n2 = Integer.parseInt(splited[1]);
                int n3 = Integer.parseInt(splited[2]);
                if(n1*n1+n2*n2==n3*n3)recC++;
                if(n1==n2)lozC++;
               
            }         
            System.out.println(recC);
            System.out.println(lozC);
        }catch(Exception e){e.printStackTrace();}
        
    }
    
}

Measured memory_bytes: 17036
#include<iostream>
using namespace std;
int main()
{
int n;
cin>>n;
if(n>=400&&n<=599)
cout<<8;
else if(n>=600&&n<=799)
cout<<7;
else if(n>=800&&n<=999)
cout<<6;
else if(n>=1000&&n<=1199)
cout<<5;
else if(n>=1200&&n<=1399)
cout<<4;
else if(n>=1400&&n<=1599)
cout<<3;
else if(n>=1600&&n<=1799)
cout<<2;
else if(n>=1800&&n<=1999)
cout<<1;
return 0;
}



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

int main()
{
    int n;
    cin>>n;
    int idx=1,cnt=0;
    while(n--)
    {
        int a;
        cin>>a;
        if(a%2==1&&idx%2==1)cnt++;
        idx++;
    }
    cout<<cnt<<endl;
}


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

int main(){
	string s; cin>>s;
	int ans=0;
	rep(i,4){
		if(s[i]=='+') ans++;
		else ans--;
	}
	cout << ans << endl;	
}

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

using namespace std;


int main()
{
	int N, K, Q;
	cin >> N >> K >> Q;

	vector<int> score(N,K-Q);

	for(int j = 0 ; j < Q; j++)
	{
		int pos;
		cin >> pos;
		pos -= 1;
		score[pos] = score[pos]+1;
	}
	
	for(int i = 0 ; i < score.size(); i++)
	{
		if(score[i] > 0) cout << "Yes" << endl;
		else cout << "No" << endl;
	}


    return 0;
}


Measured memory_bytes: 1024
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int mod=pow(10,9)+7;
int main(){
  ll n,k;
  cin>>n>>k;
  ll arr[n];
  for(ll i=0;i<n;i++){
    cin>>arr[i];
  }
  int dp[n+1][k+1];
  sort(arr,arr+n);
  for(int i=0;i<=k;i++)dp[0][i]=1;
  for(int i=0;i<=n;i++)dp[i][0]=1;
  for(int i=1;i<=n;i++){
    for(int j=1;j<=k;j++){
      int diff=(j-arr[i-1]);
      if(diff<=0)
        dp[i][j]=(dp[i][j-1] %mod +dp[i-1][j]%mod)%mod;
      else if(diff>0){
        int val=(dp[i-1][j] -dp[i-1][diff-1]);
        if(val<0)val=(val+mod)%mod;
        dp[i][j]=(val%mod +dp[i][j-1]%mod)%mod;
      }
    }
  }
  if(k==0)
    cout<<dp[n][k]<<endl;
  else{
    int val=dp[n][k]-dp[n][k-1];
    if(val<0)val=(val+mod)%mod;
    cout<<val<<endl;
  }
}

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

int main(){
	ll m,n;

	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	cin>>n>>m;

	ll k = n % m;
	if(abs(m-k) < k)
		k = abs(m-k);
	cout<<k<<endl;
	return 0;
}

Measured memory_bytes: 384
import sys
input = sys.stdin.readline

def main():
    K = int(input())
    
    if K%2==0:
        print(-1)
        return
    
    if K % 7:
        L = 9*K
    else:
        L = 9*K//7
    a = 1
    for i in range(1,K+10):
        a = (a * 10) % L
        if a == 1:
            print(i)
            return
    print(-1)
main()

Measured memory_bytes: 9192
//
//AtCoder Beginner Contest 169
//A - Multiplication 1
//

#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <ctime>
#include <queue>
#include <map>
#include <set>
#include <tuple>
#include <functional>
#include <cassert>

using namespace std;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()
#define SIZE(x) (int)(x).size()
#define SIZEL(x) (ll)(x).size()
#define MSG(a) cout << #a << " " << a << endl;

using ll = long long;
using ld = long double;

const double PI = 3.14159265358979323846;

ll gcd(ll x, ll y) { return (x % y)? gcd(y, x % y): y; }    //最大公約数
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }            //最小公倍数

int main()
{
    int a, b;
    cin >> a >> b;
    cout << a*b << endl;
    return 0;
}


Measured memory_bytes: 3604
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
#define chmax(x,y) x = max(x,y);
#define chmin(x,y) x = min(x,y);
const int di[] = {-1, 0, 1, 0};
const int dj[] = {0, -1, 0, 1};
const int INF = 1001001001;



int main() {
    ll n, x, m;
    cin >> n >> x >> m;
    vector<ll> a;
    vector<int> q(100005);
    ll d = x;
    a.push_back(x);
    ll t = n;
    ll ans = 0;
    ll tot = 0;
    ll point = 0;
    bool ok = false;
    while (1) {
        t--;
        d = (d*d)%m;
        //cout << d << endl;
        if (d == 0) {
            rep(i,a.size()) ans += a[i];
            cout << ans << endl;
            return 0;
        }
        if (d == 1) {
            rep(i,a.size()) tot += a[i];
            ans = tot + n-ll(a.size());
            cout << ans << endl;
            return 0;
        }
        if (d == a.back()) {
            rep(i,a.size()) tot += a[i];
            ans = tot + (n-ll(a.size()))*d;
            cout << ans << endl;
            return 0;
        }
        if (q[d] == 1) {
            point = d;
            ok = true;
            break;
        }
        if (t == 0) break;
        a.push_back(d);
        q[d]++;
    }
    if (ok) {
        rep(i,a.size()) ans += a[i];
        n -= ll(a.size());
        ll po = 0;
        rep(i,a.size()) {
            if (a[i] == point) po = i;
        }
        ll loop = 0;
        for (int i = po; i < a.size(); i++) {
            loop += a[i];
        }
        ll ji = ll(a.size()) - po;
        ans += loop * (n/ji);
      n %= ji;
      for (int i = po; i <= po+n-1; i++) ans += a[i];
        cout << ans << endl;
        return 0;
    }
    if (t == 0) {
        rep(i,a.size()) ans += a[i];
    }
    else {
        ll p = a.size();
        //ll tot = 0;
        rep(i,a.size()) tot += a[i];
        ll y = n/p;
        //rep(i,y) ans += tot;
        ans += tot*y;
        n %= p;
        rep(i,n) ans += a[i];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4312
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <limits>
#include <queue>
#include <iomanip>
#include <set>
//#include <bits/stdc++.h>

template<typename T> bool chmax(T &a,T b){
    if(a<b){
        a=b;
        return true;
    }
    return false;
}

template<typename T> bool chmin(T &a,T b){
    if(a>b){
        a=b;
        return true;
    }
    return false;
}

using namespace std;
#define ALL(X) X.begin(),X.end()
using ll = long long int;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vvll> vvvll;
const int MOD=1000000007;
//const int MOD=998244353;
const int INTMAX=2147483647;
const ll LLMAX=9223372036854775807;

ll modadd(ll a,ll b,ll mod=MOD){
    return (a%mod+b%mod)%mod;
}

ll modsub(ll a,ll b,ll mod=MOD){
    a%=mod;
    b%=mod;
    if(a>=b) return a-b;
    else return mod-b+a;
}

ll modmul(ll a,ll b,ll mod=MOD){
    return ((a%mod)*(b%mod))%mod;
}

ll modpow(ll a, ll n,ll mod=MOD) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

ll moddiv(ll a,ll b,ll mod=MOD) {
    return modmul(a, modpow(b, mod-2));
}



int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    ll N;
    cin>>N;
    string S1,S2;
    cin>>S1>>S2;
    
    vector<bool> type;//vertical:true
    for(ll i=0;i<N;i++){
        if(S1[i]==S2[i])type.push_back(true);
        else{
            type.push_back(false);
            i++;
        }
    }
    
    ll ans=1;
    for(ll i=0;i<type.size();i++){
        if(i==0){
            if(type[i]){
                ans=3;
            }else{
                ans=6;
            }
        }else{
            if(type[i]){
                if(type[i-1]){
                    ans=modmul(ans,2);
                }else{
                    ans=modmul(ans,1);
                }
            }else{
                if(type[i-1]){
                    ans=modmul(ans,2);
                }else{
                    ans=modmul(ans,3);
                }
            }
        }
    }
    cout<<ans<<endl;
    
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;int x=0,y=0;int t=0;int a,b,c;
    for(int i=1;i<=n;i++){
        cin>>c>>a>>b;
        if(abs(x-a)+abs(y-b)>c-t){
            cout<<"No";return 0;
        }
        if((abs(x-a)+abs(y-b))%2==0 &&(c-t)%2==1){
            cout<<"No";return 0;
        }
        if((abs(x-a)+abs(y-b))%2==1 &&(c-t)%2==0){
            cout<<"No";return 0;
        }
        x=a;y=b;t=c;
    }
    cout<<"Yes";
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;
int ctoi(const char c){
  switch(c){
    case '0': return 0;
    case '1': return 1;
    case '2': return 2;
    case '3': return 3;
    case '4': return 4;
    case '5': return 5;
    case '6': return 6;
    case '7': return 7;
    case '8': return 8;
    case '9': return 9;
    default : return -1;
  }
}

int main() {
   string S;
   cin >> S;
   int ans = 999;
   for (int i = 0; i < (int)S.size() - 2; i++) {
      int tmp = ctoi(S[i]) * 100 + ctoi(S[i + 1]) * 10 + ctoi(S[i + 2]);
      tmp = abs(tmp - 753);
      if (tmp < ans) ans = tmp;
   }
   cout << ans << endl;
   return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <memory>
#include <queue>
#include <stack>
#include <unordered_set>
#include <utility>
#include <vector>
using std::cin;
using std::cout;
using std::endl;

int main(void) {
    cout << std::fixed << std::setprecision(10);
    cin.tie(0);
    std::ios::sync_with_stdio(false);
    int h, w, n;
    std::unique_ptr<int[]> barrier_mostsouth(new int[200010]);
    std::unique_ptr<std::unordered_set<int>[]> barrier(
        new std::unordered_set<int>[200010]);
    cin >> h >> w >> n;
    for (int i = 1; i <= h; i++) {
        barrier_mostsouth[i] = w + 1;
    }
    barrier_mostsouth[h + 1] = 1;
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        barrier[x].insert(y);
        if (barrier_mostsouth[x] > y) {
            barrier_mostsouth[x] = y;
        }
    }
    for (int i = 1; i <= h; i++) {
        barrier[i].insert(w + 1);
    }
    for (int i = 1; i <= w + 1; i++) {
        barrier[h + 1].insert(i);
    }

    int pos_x = 1, pos_y = 1;
    while (!(barrier_mostsouth[pos_x + 1] <= pos_y)) {

        pos_x++;
        // cout << "posx++: " << pos_x - 1 << " -> " << pos_x << endl;
        if (barrier[pos_x].find(pos_y + 1) == barrier[pos_x].end()) {
            pos_y++;
            // cout << "posy++: " << pos_y - 1 << " -> " << pos_y << endl;
        }
    }
    cout << pos_x << endl;

    return 0;
}


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

#define all(x) (x).begin(),(x).end()
#define rep(i,l,r) for(int i=(int)(l);i<(int)(r);i++)

typedef long long ll;
const ll MOD = 1e9 + 7;
const ll inf = 1LL<<60;
const double eps = 1e-9;


int main()
{
    ll n, k, q;
    cin >> n >> k >> q;
    vector <int> a(n, 0);
    for (int i = 0; i < q; i++) {
        ll tmp;
        cin >> tmp;
        a[tmp-1]++;
    }
    for (int i = 0; i < n; i++) {
        if (k - (q - a[i]) > 0) cout << "Yes" << endl;
        else cout << "No" << endl;
    }


    return 0;
}


Measured memory_bytes: 1024
#include <stdio.h>
#include <iostream>
#include <iomanip>
#include <limits>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <cmath>
#include <map>
#include <tuple>

#define INF 1001001001
#define rep(i,n) for(int i=0; i<(n); i++)
typedef long long ll;
using namespace std;
 



int main (){
    int n,k; cin >> n >> k;
    string s; cin >> s;
    
    if(s[k-1]=='A') s[k-1] = 'a';
    if(s[k-1]=='B') s[k-1] = 'b';
    if(s[k-1]=='C') s[k-1] = 'c';
    
    cout << s << endl;
    






}


Measured memory_bytes: 256
n,k,*h=map(int,open(0).read().split())
INF=float("inf")
dp=[INF]*n
dp[0]=0
dp[1]=abs(h[0]-h[1])
for i in range(2,n):
	width = k
	if i<k:
		width=i
	for j in range(1,width+1):
		dp[i] = min( dp[i] , dp[i-j]+abs(h[i-j]-h[i]) )
print(dp[-1])

Measured memory_bytes: 59948
#include <stdio.h>
int main(void){
  int a, b, c;
  scanf("%d %d %d", &a, &b, &c);
  if(c - (a - b) >= 0){
  printf("%d\n", c - (a - b));
  }else{
    printf("%d\n", 0);
  }
  return 0;
}

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

using namespace std;

int main()
{
   int n,k,val=0;
   cin>>n>>k;
  int p[1001];
  for(int i=0;i<n;i++)
    cin>>p[i];

   sort(p,p+n);
   for(int i=0;i<k;i++){
    val+=p[i];
   }
   cout<<val<<endl;
    return 0;
}


Measured memory_bytes: 3600
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.NoSuchElementException;
import java.util.Scanner;

public class Main {

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

	public void run() {
		Scanner sc = new Scanner();
		int N = sc.nextInt();
		int[] dp = new int[100001];
		Arrays.fill(dp, Integer.MAX_VALUE / 3);
		dp[0] = 0;
		for (int i = 0; i < dp.length; ++i) {
			long pow = 1;
			for (int j = 1; i + pow * 6 < dp.length; ++j) {
				dp[i + (int) pow * 6] = Math.min(dp[i] + 1, dp[i + (int) pow * 6]);
				pow *= 6;
			}
			pow = 1;
			for (int j = 1; i + pow * 9 < dp.length; ++j) {
				dp[i + (int) pow * 9] = Math.min(dp[i] + 1, dp[i + (int) pow * 9]);
				pow = pow * 9;
			}
			if (i + 1 < dp.length)
				dp[i + 1] = Math.min(dp[i] + 1, dp[i + 1]);
		}
		System.out.println(dp[N]);
	}

	long pow(long a, long n) {
		long ret = 1;
		for (; n > 0; n >>= 1, a = a * a) {
			if (n % 2 == 1)
				ret = ret * a;
		}
		return ret;
	}

	class Scanner {
		private final InputStream in = System.in;
		private final byte[] buffer = new byte[1024];
		private int ptr = 0;
		private int buflen = 0;

		private boolean hasNextByte() {
			if (ptr < buflen) {
				return true;
			} else {
				ptr = 0;
				try {
					buflen = in.read(buffer);
				} catch (IOException e) {
					e.printStackTrace();
				}
				if (buflen <= 0) {
					return false;
				}
			}
			return true;
		}

		private int readByte() {
			if (hasNextByte())
				return buffer[ptr++];
			else
				return -1;
		}

		private boolean isPrintableChar(int c) {
			return 33 <= c && c <= 126;
		}

		private void skipUnprintable() {
			while (hasNextByte() && !isPrintableChar(buffer[ptr]))
				ptr++;
		}

		public boolean hasNext() {
			skipUnprintable();
			return hasNextByte();
		}

		public String next() {
			if (!hasNext())
				throw new NoSuchElementException();
			StringBuilder sb = new StringBuilder();
			int b = readByte();
			while (isPrintableChar(b)) {
				sb.appendCodePoint(b);
				b = readByte();
			}
			return sb.toString();
		}

		public long nextLong() {
			if (!hasNext())
				throw new NoSuchElementException();
			long n = 0;
			boolean minus = false;
			int b = readByte();
			if (b == '-') {
				minus = true;
				b = readByte();
			}
			if (b < '0' || '9' < b) {
				throw new NumberFormatException();
			}
			while (true) {
				if ('0' <= b && b <= '9') {
					n *= 10;
					n += b - '0';
				} else if (b == -1 || !isPrintableChar(b)) {
					return minus ? -n : n;
				} else {
					throw new NumberFormatException();
				}
				b = readByte();
			}
		}

		int nextInt() {
			return (int) nextLong();
		}
	}

}


Measured memory_bytes: 21588
while True:
   n, x = map(int, input().split())
   if n == 0 and x == 0:
       break
   ans = 0
   for i in range(1, n + 1):
       for j in range(1, i):
           for k in range(1, j):
               if i + j + k == x:
                   ans += 1
   print(ans)


Measured memory_bytes: 5592
#include<cstdio>
#include<string>
#include<vector>
#include<iostream>
#include<algorithm>

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

using namespace std;

const int INF=1<<29;

int main(){
	for(int n;cin>>n,n;){
		vector<string> name[10];
		vector<int> price[10];
		rep(i,n){
			int m; cin>>m;
			name[i].resize(m);
			price[i].resize(m);
			rep(j,m) cin>>name[i][j]>>price[i][j];
		}

		int q; cin>>q;
		string want[15];
		rep(i,q) cin>>want[i];

		int m; cin>>m;
		int d[11][11];
		rep(u,n+1) rep(v,n+1) d[u][v]=(u==v?0:INF);
		rep(i,m){
			int u,v,dd; cin>>u>>v>>dd;
			d[u][v]=d[v][u]=min(d[u][v],dd);
		}
		rep(k,n+1) rep(i,n+1) rep(j,n+1) d[i][j]=min(d[i][j],d[i][k]+d[k][j]);

		int p[10][15];
		rep(i,n) rep(j,q) p[i][j]=INF;
		rep(i,n) rep(j,name[i].size()) rep(k,q) if(name[i][j]==want[k]) p[i][k]=min(p[i][k],price[i][j]);
		int p_ans=0;
		// 一番安い店のみ興味がある
		rep(j,q){
			int p_min=INF;
			rep(i,n) p_min=min(p_min,p[i][j]);
			rep(i,n) if(p[i][j]>p_min) p[i][j]=INF;
			p_ans=min(p_ans+p_min,INF);
		}
		if(p_ans==INF){ cout<<"impossible"<<endl; continue; }

		if(q==0){ cout<<"0 0"<<endl; continue; }

		// TSP
		int mask[11]={};
		rep(i,n) rep(j,q) if(p[i][j]<INF) mask[i+1]|=1<<j;

		int d_ans=INF;
		int perm[10]={1,2,3,4,5,6,7,8,9,10};
		do{
			int S=0,pos=0,d_now=d[0][perm[0]];
			rep(i,n){
				pos=perm[i];
				S|=mask[pos];
				if(S==(1<<q)-1){ d_now+=d[pos][0]; break; }
				d_now+=d[pos][perm[i+1]];
			}
			d_ans=min(d_ans,d_now);
		}while(next_permutation(perm,perm+n));

		cout<<p_ans<<" "<<d_ans<<endl;
	}

	return 0;
}

Measured memory_bytes: 1224
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <string>
using namespace std;
typedef pair<int,string> P;
typedef pair<pair<int,int> ,int> PP;

string digit6(int t){
    string out = to_string(t);
    int d = 0;
    while(t > 0){
        d++;
        t /= 10;
    }
    for(int i = 0; i < 6-d; i++)
    {
        out = "0" + out;
    }
    return out;
}

int main()
{
    int n, m;
    cin >> n >> m;
    vector<PP> vec(m);
    for(int i = 0; i < m; i++)
    {
        cin >> vec[i].first.first >> vec[i].first.second;
        vec[i].second = i;
    }
    sort(vec.begin(), vec.end());
    int indexP = 1, indexY = 1;;
    vector<P> ans(m);
    for(int i = 0; i < m; i++)
    {
        string tmp = "";
        if (vec[i].first.first == indexP) {
            tmp = digit6(indexP) + digit6(indexY);
        }
        else
        {
            indexP = vec[i].first.first;
            indexY = 1;
            tmp = digit6(indexP) + digit6(indexY);
        }
        indexY++;
        ans[i].first = vec[i].second;
        ans[i].second = tmp;
    }
    sort(ans.begin(),ans.end());
    for(int i = 0; i < m; i++)
    {
        cout << ans[i].second << endl;
    }
}

Measured memory_bytes: 8960
#include<iostream>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>

using namespace std;

#define int long long
#define rep(i,n) for(int i = 0; i < (n); i++)
#define INF ((long long)1e18)
#define MOD ((int)1e9+7)
#define endl "\n"

#define yn(f) ((f)?"Yes":"No")
#define YN(f) ((f)?"YES":"NO")

#define MAX

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);
	
	int a, b;
	int s;
	
	cin>>s;
	
	a = s/100;
	b = s%100;
	
	if(0 <= a  && a <= 99 && 1 <= b && b <= 12 && 0 <= b  && b <= 99 && 1 <= a && a <= 12){
		cout<<"AMBIGUOUS "<<endl;
	} else if(0 <= a  && a <= 99 && 1 <= b && b <= 12) {
		cout<<"YYMM"<<endl;
	} else if(0 <= b  && b <= 99 && 1 <= a && a <= 12){
		cout<<"MMYY"<<endl;
	} else {
		cout<<"NA"<<endl;
	}
	
	
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define mod 1000000007
using namespace std;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    string a="AC",b="WA",c="TLE",d="RE";
    ll n;
    cin>>n;
    string s;
  ll a1=0,a2=0,a3=0,a4=0;
    for(ll i=0;i<n;i++)
    {
        cin>>s;
        if(s==a)
        a1++;
        else if(s==b)
        a2++;
        else if(s==c)
        a3++;
        else if(s==d)
        a4++;
    }
    cout<<a<<" x "<<a1<<"\n"<<b<<" x "<<a2<<"\n"<<c<<" x "<<a3<<"\n"<<d<<" x "<<a4;
    return 0;
}

Measured memory_bytes: 3656
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
#include<memory>
using namespace std;
using namespace std::chrono;
typedef long long int llint;
typedef double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase

/*
cout<<fixed<<setprecision(20);
cin.tie(0);
ios::sync_with_stdio(false);
*/
const llint mod=1000000007;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
int main(void){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(20);
	int i,j,n,K;cin>>n>>K;
	vector<int>A(n);
	for(i=0;i<n;i++){cin>>A[i];}
	SO(A);
	vector<bool>dp(K+1);
	for(i=1;i<=K;i++){
		for(j=0;j<n&&A[j]<=i;j++){
			if(!dp[i-A[j]]){dp[i]=1;break;}
		}
	}
	cout<<(dp[K]?"First":"Second")<<endl;
	return 0;
}


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

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);
    
    int n,k;
    cin>>n>>k;
    string s;
    cin>>s;
    int ans = n-1;
    for(int i=1;i<n;i++){
        if(s[i]!=s[i-1])ans--;
    }
    ans += k*2;
    ans = min(ans,n-1);
    cout << ans << endl;
}

Measured memory_bytes: 512
N, M = map(int, input().split())

road = [[] for _ in range(N)]

for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    road[a].append(b)
    road[b].append(a)

counter = 0
    
def search(pointStack):
    global counter
    if len(pointStack) == N:
        counter += 1
        pointStack.pop()
        return
    
    currentNode = pointStack[-1]
    for nextNode in road[currentNode]:
        if nextNode in pointStack:
            continue
        pointStack.append(nextNode)
        search(pointStack)

    pointStack.pop()

search([0])

print(counter)

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

int main(){
    int n;
    cin >> n;
    int r = 0;
    int s = 0;
    for (int i = 0; i < n; i++) {
        char sss; cin >> sss;
        if (sss == 'R') {
            r++;
        } else {
            s++;
        }
    }
    if (r > s) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O0")
typedef long long int ll;
typedef long double ld;
#define rep(i,n) for (ll i = 0; i < (n); ++i)
const ll mod = 1e9+7;
const ll INF = 1e18;
#define All(a) (a).begin(),(a).end()
#define Pi acos(-1)

class mint {
public:
    long long x;
    constexpr mint(long long x=0) : x((x%mod+mod)%mod) {}
    constexpr mint operator-() const { 
      return mint(-x);
    }
    constexpr mint& operator+=(const mint& a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    constexpr mint& operator-=(const mint& a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    constexpr mint& operator*=(const mint& a) {
        (x *= a.x) %= mod;
        return *this;
    }
    constexpr mint operator+(const mint& a) const {
        mint res(*this);
        return res+=a;
    }
    constexpr mint operator-(const mint& a) const {
        mint res(*this);
        return res-=a;
    }
    constexpr mint operator*(const mint& a) const {
        mint res(*this);
        return res*=a;
    }
    constexpr mint pow(long long t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }

    // for prime mod
    constexpr mint inv() const {
        return pow(mod-2);
    }
    constexpr mint& operator/=(const mint& a) {
        return (*this) *= a.inv();
    }
    constexpr mint operator/(const mint& a) const {
        mint res(*this);
        return res/=a;
    }
};
ostream& operator<<(ostream& os, const mint& m){
    os << m.x;
    return os;
}

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << setprecision(15) << fixed;
  chrono::system_clock::time_point start,end;
  start = chrono::system_clock::now();

  ll n;
  cin >> n;
  vector<ll> a(n);
  vector<mint> b(n);
  rep(i,n) {
    cin >> a[i];
    if (i == 0) b[i] = a[i];
    else b[i] = b[i-1]+a[i];
  }
  mint ans = 0;
  rep(i,n) {
    ans += (b[n-1]-b[i]) * a[i];
  }
  cout << ans << '\n';

  end = chrono::system_clock::now();
  auto elapsed = chrono::duration_cast< chrono::milliseconds >(end - start).count();
  cerr << elapsed << "ms" << '\n';
}

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

const int N = 1e5 + 5;
int n, a[N];

main()
{
    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    int pre = -2105;
    for(int i = 1; i <= n; ++i)
    {
        if(pre <= a[i] - 1)
        {
            pre = a[i] - 1;
        }
        else if(pre <= a[i]) pre = a[i];
        else return cout << "No", 0;
    }
    cout << "Yes";
}


Measured memory_bytes: 640
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

int x[4] = { -1,0,1,0 };
int y[4] = { 0,1,0,-1 };
int g[4][4];
int m = 0;

int h1() {
    int c = 0;
    for (int i=0;i<4;i++) {
        for (int j=0;j<4;j++) {
            if (g[i][j] != 0) {
                int t = g[i][j]-1;
                c += abs(t / 4 - i) + abs(t % 4 - j);
            }
        }
    }
    return c;
}

bool solve(int depth, int t, int zx, int zy) {
    int c = h1();
    if (c+depth>m) return false;
    if (c==0) return true;
    int dx,dy;
    for(int i=0;i<4;i++) {
        if (i != (t^2)) {
            dx = zx+x[i];
            dy = zy+y[i];
            if (dx < 0 || dx == 4 || dy < 0 || dy == 4) continue;
            swap(g[dx][dy], g[zx][zy]);
            if (solve(depth + 1, i, dx, dy)) return true;
            swap(g[dx][dy], g[zx][zy]);

        }
    }
    return false;
}

int main() {
    int zx,zy;
    for (int i=0;i<4;i++) {
        for (int j=0;j<4;j++) {
            cin>>g[i][j];
            if (g[i][j]==0) {
                zx=i;zy=j;
            }
        }
    }
    for (m=h1();;m+=2) {
        if (solve(0,9,zx,zy)) {
            cout<<m<<endl;
            return 0;
        }
    }


    return 0;
}



Measured memory_bytes: 3124
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    int a[100][100];
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++) cin>>a[i][j];
    
    int b[100];
    for(int i=0;i<m;i++) cin>>b[i];
    
    int c[100]={};
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++) c[i]+=a[i][j]*b[j];
    
    for(int i=0;i<n;i++) cout<<c[i]<<endl;
    return 0;
}


Measured memory_bytes: 3104
a = gets.to_i
b = gets.to_i
c = gets.to_i
x = gets.to_i
def b_coins(a,b,c,x)
  counter = 0
  (0..a).each do | n |
    (0..b).each do | m |
      (0..c).each do | l |
        counter += 1 if (n*500 + m*100 + l*50) == x
      end
    end
  end
  puts counter
end
b_coins(a,b,c,x)

Measured memory_bytes: 1788
#include <stdio.h>

int main() {
  int x, y;
  while(1){
    scanf("%d %d", &x, &y);
    if(x == 0 && y == 0) break;
    else if(x < y){
      printf("%d %d\n", x, y);
    }
    else{
      printf("%d %d\n", y, x);
    }
  }

  return 0;
}

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

using namespace std;


string S;
int main(){
	cin >> S;
	if(S.size()<4){
		printf("No\n");
		return 0;
	}
	if(S[0]=='Y'&&S[1]=='A'&&S[2]=='K'&&S[3]=='I'){
		printf("Yes\n");
		return 0;
	}
	else{
		printf("No\n");
		return 0;
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
constexpr int M = 1000000007;

long long modexp(int x, long long e, int m) {
    long long ans = 1, p = x % m;
    while (e > 0) {
        if (e % 2 != 0) ans = (ans * p) % m;
        p = (p * p) % m;
        e >>= 1;
    }
    return ans;
}

int main() {
    string s; cin >> s;
    long long ans = 0, acc = 1;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '1') {
            ans += acc * modexp(3, s.size() - i - 1, M) % M;
            acc = acc * 2 % M;
        }
    }
    cout << (ans + acc) % M << endl;
}


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

#define int long long

using namespace std;

const int N = 200005;
const int mod = 1e9 + 7;

int fact[N], inv_fact[N];

int binPow (int x, int y) {
    int ans = 1;
    while (y) {
        if (y & 1) ans = (ans * x) % mod;
        x = (x * x) % mod;
        y >>= 1;
    }

    return ans;
}

int C (int n, int k) {
    if (k > n) return 0;
    int ans = 1;
    ans *= fact[n]; ans %= mod;
    ans *= inv_fact[k]; ans %= mod;
    ans *= inv_fact[n - k]; ans %= mod;

    return ans;
}

signed main(){
    int n, m, a, b;
    scanf("%lld %lld %lld %lld", &n, &m, &a, &b);

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

    int ans = 0;
    for (int i = 1; i <= n - a; i++) ans = (ans + C(i + b - 2, i - 1) * C(n - i + m - b - 1, n - i)) % mod;

    printf("%lld", ans);
    return 0;
}

Measured memory_bytes: 3328
#encoding:utf-8
def make_bottommost ary
 if ary.length == 1
  return ary
 else
  i = 0
  ary2 = []
  while i+1 < ary.length
   ary2.push (ary[i]+ary[i+1])%10
   i += 1
  end
  make_bottommost ary2
 end
end

num_ary = []

while gets
 num = $_.chomp.chars
 num.length.times do |i|
  num[i] = num[i].to_i
 end
 num_ary.push num
end

num_ary.length.times do |i|
 puts make_bottommost num_ary[i]
end

Measured memory_bytes: 6104
#include <stdio.h>
#include <stdlib.h>
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)

//block linked list
#define Bsize 700 /*2sqrt(n)*/
typedef struct block{
	int cnt;
	ll a[Bsize+1];
	struct block*pre;
	struct block*nxt;
}block;
void Bpush(block*b,ll x){
	//リストにxを追加する
	if((*b).nxt&&(*(*b).nxt).a[0]<x){
		//次へ
		Bpush((*b).nxt,x);
		return;
	}
	int i=(*b).cnt;
	for(;i>0&&(*b).a[i-1]>x;i--)(*b).a[i]=(*b).a[i-1];
	(*b).a[i]=x;
	(*b).cnt++;
	if((*b).cnt>=Bsize){
		//分割
		block*nn=(block*)malloc(sizeof(block));
		(*nn).cnt=Bsize-Bsize/2;
		rep(i,0,Bsize-Bsize/2)(*nn).a[i]=(*b).a[i+Bsize/2];
		(*nn).pre=b;
		(*nn).nxt=(*b).nxt;
		if((*b).nxt)(*(*b).nxt).pre=nn;
		(*b).cnt=Bsize/2;
		(*b).nxt=nn;
	}
}
void con(block*p,block*q){
	//qをpにマージしてqを消す
	rep(i,0,(*q).cnt)(*p).a[(*p).cnt+i]=(*q).a[i];
	(*p).cnt+=(*q).cnt;
	(*p).nxt=(*q).nxt;
	if((*q).nxt)(*(*q).nxt).pre=p;
	free(q);
}
void Bdel(block*b,int idx){
	//idx番目を削除する(必ずidx個以上ある)
	for(;idx<(*b).cnt-1;idx++)(*b).a[idx]=(*b).a[idx+1];
	(*b).cnt--;
	
	if((*b).cnt==0&&(*b).pre){
		(*(*b).pre).nxt=(*b).nxt;
		if((*b).nxt)(*(*b).nxt).pre=(*b).pre;
		free(b);
	}else if((*b).pre&&(*(*b).pre).cnt+(*b).cnt<Bsize/4)con((*b).pre,b);
	else if((*b).nxt&&(*(*b).nxt).cnt+(*b).cnt<Bsize/4)con(b,(*b).nxt);
}

ll Bans(block*b,int k,int flag){
	//リストのk番目を返す
	//リストにk個未満しかなければ適当に返す
	//flagがtrueなら削除する
	if((*b).cnt<=k){
		if((*b).nxt)return Bans((*b).nxt,k-(*b).cnt,flag);
		else return -1;//<-例外
	}
	ll ans=(*b).a[k];
	if(flag)Bdel(b,k);
	return ans;
}
int Bfind(block*b,ll k,int flag){
	//リストにkが存在すれか答える
	//flagがtrueなら削除する
	if((*b).cnt==0||(*b).a[(*b).cnt-1]<k){
		if((*b).nxt)return Bfind((*b).nxt,k,flag);
		else return 0;
	}
	int i=0;
	for(;(*b).a[i]<k;i++);
	if((*b).a[i]!=k)return 0;
	if(flag)Bdel(b,i);
	return 1;
}
#undef Bsize


block*b;
int main(){
	b=calloc(1,sizeof(block));
	int q;
	scanf("%d",&q);
	int cnt=0;
	while(q--){
		int t,x;
		scanf("%d%d",&t,&x);
		if(t==0){
			if(!Bfind(b,x,0)){
				Bpush(b,x);
				cnt++;
			}
			printf("%d\n",cnt);
		}else if(t==1){
			printf("%d\n",Bfind(b,x,0));
		}else{
			if(Bfind(b,x,1))cnt--;
		}
	}
}



Measured memory_bytes: 4848
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    
    int X;
    cin >> X;
    
    while(true){
        
        for(int i = 2; i <= X; i++){
            if(i == X){
                cout << X << endl;
                return 0;
            }
            
            else if(X % i == 0) break;
        }
        
        X++;
    }
    
}


Measured memory_bytes: 256
#答えが0や101になりうる点に注意が必要
x,n = map(int,input().split())
if n != 0:
    p = list(map(int,input().split()))
    tmp_p = [0] * 102
if n == 0:
    print(x)
else:
    for i in range(n):
        tmp_p[p[i]] += 1
    if tmp_p[x] == 0:
        print(x)
    else:
        j = 1
        stop_min = 0
        stop_max = 0
        while stop_min == 0 or stop_max == 0:
            if x-j >= 0:
                if tmp_p[x-j] == 0:
                    print(x-j)
                    break
            else:
                stop_min += 1
            if x+j <= 101:
                if tmp_p[x+j] == 0:
                    print(x+j)
                    break
            else:
                stop_max += 1
            j += 1


Measured memory_bytes: 9216
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MOD=1e9+7;
ll mod_pow(int x,int y){//x^yを返す//計算量は0(log(y))
    ll tmp=x,res=1;
    while(y){
        if(y%2){
            res=res*tmp%MOD;
        }
        y>>=1;
        tmp=tmp*tmp%MOD;
    }
    return res;
}
int main(){
    int N,K;
    cin>>N>>K;
    unordered_map<int,ll> mp;
    for(int i=K;i>=1;i--){
        if(2*i>K){mp[i]=1;}
        else{
            int a=mod_pow(K/i,N);
            for(int j=2*i;j<=K;j+=i){
                a-=mp[j]-MOD;
                a%=MOD;
            }
            mp[i]=a;
        }
    }
    ll ans=0;
    for(int i=1;i<=K;i++){
        ans+=mp[i]*i;
        ans%=MOD;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 7328
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int main()
{
	char s[30],t[30];
	scanf("%s",s);
	int n=strlen(s);
	if(n==26)
	{
		copy(s,s+n,t);
		if(!next_permutation(s,s+n))
			puts("-1");
		else
		{
			for(int i=0;i<n;i++)
				if(s[i]!=t[i])
				{
					s[i+1]=0;
					break;
				}
			puts(s);
		}
	}
	else
	{
		printf(s);
		bool vis[30]={false};
		for(int i=0;i<n;i++)
			vis[s[i]-'a']=true;
		for(int i=0;i<26;i++)
			if(!vis[i])
			{
				printf("%c\n",i+'a');
				break;
			}
	}
	return 0;
}


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

int main() {
  int N, M;
//  int s, t;
  int64_t K;
  cin >> N >> M >> K;
  vector<int64_t> A(N+1);
  A.at(0)=0;
  for (int i = 1; i < N+1; i++) {
    cin >> A.at(i);
    A.at(i) += A.at(i-1);
  }
  vector<int64_t> B(M+1);
  B.at(0)=0;
  for (int i = 1; i < M+1; i++) {
    cin >> B.at(i);
    B.at(i) += B.at(i-1);
  }
  int max=0;
  int best=M;
  bool f=false;
  for (int i=0; i<N+1; i++){
//    cout << "i=" << i << endl;
    for (int j=best; j>=0; j--){
//          cout << "j=" << j << endl;
      if(A.at(i)+B.at(j) <= K){
//        cout << A.at(i) << " " << i << " " << B.at(j) << " " << j << " " << K << endl;
        best=j;
        f=true;
        break;
      }
    }
    if (f && i+best > max){
      max=i+best;
//      s=i;
//      t=best;
//      cout << s << " " << t << endl;
    }
    f=false;
  }
  cout << max << endl;
}


Measured memory_bytes: 6400
#include<iostream>
#include<algorithm>
#include<string>
#include<math.h>
#include<vector>
#include<iomanip>
using namespace std;

int main(void)
{
    char n;
    cin >> n;
    switch(n)
    {
        case 'A':
        cout << 'T' << endl;
        break;
        case 'T':
        cout << 'A' << endl;
        break;
        case 'C':
        cout << 'G' << endl;
        break;
        case 'G':
        cout << 'C' << endl;
        break; 
    }
    return 0;
}

Measured memory_bytes: 256
H,W = map(int,input().split())
s = [list(input()) for _ in range(H)]

jougesayuu = [(-1,0),(1,0),(0,-1),(0,1)]

check = True
for i in range(H):
  for j in range(W):
    if s[i][j] == "#":
      flag = False
      for (n,m) in jougesayuu:
        ni, nj = i + n, j + m
        if ni < 0 or H <= ni or nj < 0 or W <= nj:
          continue
        if s[ni][nj] == "#":
          flag = True
      if not flag:
        check = False
        
print("Yes" if check else "No")

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

int main(){
  int n;
  cin>> n;
  vector<tuple<string,int,int>> t(n);
  string s;
  int p;
  for (int i=0; i<n; i++){
    cin>> s >> p;
    t.at(i)=make_tuple(s,100-p,i+1);
  }
  
  sort(t.begin(),t.end());
  for (int i=0; i<n; i++) cout<< get<2>(t.at(i)) <<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long n,q,b,c,i,k,sum=0;
    long long a[100001];
    cin>>n;
    for(i=1; i<=100000; i++)
        a[i]=0;
    for(i=1; i<=n; i++)
    {
        cin>>k;
        a[k]++;
        sum+=k;
    }
    cin>>q;
    while(q--)
    {
        cin>>b>>c;
        if(a[b]==0)
            cout<<sum<<endl;
        else
        {
            a[c]+=a[b];
            sum=sum+c*a[b]-b*a[b];
            a[b]=0;
            cout<<sum<<endl;
        }
    }
    return 0;
}


Measured memory_bytes: 4396
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>  // std::swap()
using namespace std;
using ll = long long;

#define REP(i, n) for (ll i=0; i < n; i++)  // 0 ~ n-1
#define pll pair<ll, ll>
#define F first
#define S second

class UnionFind {
public:
    vector <ll> par; // 各元の親を表す配列
    vector <ll> siz; // 素集合のサイズを表す配列(1 で初期化)

    // Constructor
    UnionFind(ll sz_): par(sz_), siz(sz_, 1LL) {
        for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
    }
    void init(ll sz_) {
        par.resize(sz_);
        siz.assign(sz_, 1LL);
        for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
    }

    // Member Function
    // Find
    ll root(ll x) { // 根の検索
        while (par[x] != x) {
            x = par[x] = par[par[x]]; // x の親の親を x の親とする
        }
        return x;
    }

    // Union(Unite, Merge)
    bool merge(ll x, ll y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        // merge technique（データ構造をマージするテク．小を大にくっつける）
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }

    bool issame(ll x, ll y) { // 連結判定
        return root(x) == root(y);
    }

    ll size(ll x) { // 素集合のサイズ
        return siz[root(x)];
    }
};

int main() {
    // input(sunippets: inpv, inpn, inps)
    ll N, M, a, b;
    cin >> N >> M;
    vector<pll> vec(M);
    REP(i, M) {
        cin >> a >> b; --a, --b;
        vec[i].F = a;
        vec[i].S = b;
    }

    // calculation
    UnionFind uf(N);
    ll res = 0;
    REP(i, M) {
        uf.init(N);
        REP(j, M) {
            if (j == i) continue;
            uf.merge(vec[j].F, vec[j].S);
        }
        if (uf.size(0) < N) res++;
    }

    cout << res << "\n";

    return 0;
}

Measured memory_bytes: 3612
#include<iostream>
using namespace std;
int main(){
	int n;
	while(true){
	cin>>n;
	if(n==0)return 0;
	for(int pm,pe,pj;n>=1;n--){
		cin>>pm>>pe>>pj;
		if(pm==100||pe==100||pj==100)cout<<"A\n";
		else if(pm+pe>=180)cout<<"A\n";
		else if(pm+pe+pj>=240)cout<<"A\n";
		else if(pm+pe+pj>=210)cout<<"B\n";
		else if(pm+pe+pj>=150&&pm>=80||pe>=80)cout<<"B\n";
		else cout<<"C\n";
	}
	}
}

Measured memory_bytes: 0
H, W , N = map(int,input().split())
from bisect import bisect_left
from bisect import bisect_right
matrix = []
for _ in range(N):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    matrix.append([x,y])
matrix.sort()
ans = [0 for _ in range(10)]
cand = {}
for l in matrix:
    for x_r in [-2, -1 , 0]:
        for y_r in [-2, -1 , 0]:
            nowx = l[0] + x_r
            nowy = l[1] + y_r
            if nowx < 0 or nowy < 0 or nowx + 2>= H or nowy+ 2 >= W:
                continue
            #ここで起点(左上)nowx, nowy として　 9マスに着目する
            name = str(nowx) + ' '  +str(nowy)
            try: cand[name] += 1
            except: cand[name] = 1
tmp = ((H - 2) * (W - 2))
for x in cand.values():
    ans[x] += 1
    tmp -= 1
ans[0] = tmp
for x in ans:
    print(x)


Measured memory_bytes: 143380