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

int main()
{
    int n;cin>>n;
    if(~n&1)
    {
        int m=n*(n-1)/2-n/2;
        printf("%d\n",m);
        for(int i=1;i<=n;i++)
            for(int j=i+1;j<=n;j++)
            {
                if(i+j==n+1) continue;
                printf("%d %d\n",i,j);
            }
    }
    else
    {
        int m=(n-1)*(n-2)/2-(n-1)/2+(n-1);
        printf("%d\n",m);
        for(int i=1;i<n;i++)
            for(int j=i+1;j<n;j++)
            {
                if(i+j==n) continue;
                printf("%d %d\n",i,j);
            }
        for(int i=1;i<n;i++)
            printf("%d %d\n",i,n);
    }
    return 0;
}

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

char ss[20];
int main()
{
	scanf("%s",ss+1);int n=strlen(ss+1);
	if(ss[1]!='A')printf("WA\n");
	else
	{
		bool bk=false;
		for(int i=3;i<=n-1;i++)
			if(ss[i]=='C')
			{
				if(bk==false)bk=true;
				else {bk=false;break;}
			}
			else if('A'<=ss[i]&&ss[i]<='Z'){bk=false;break;}
		if(('A'<=ss[2]&&ss[2]<='Z'))bk=false;
		if(('A'<=ss[n]&&ss[n]<='Z'))bk=false;
		if(bk==false)printf("WA\n");
		else printf("AC\n");
	}
	return 0;
}

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

long long solve() {
  long long x, k, d;
  std::cin >> x >> k >> d;

  /* 最小値になるのに必要な回数 */
  long long need_num = std::abs(x) / d;  

  long long k_new = std::min(k, need_num); 

  /* 減らす回数は偶数回 */
  if (k_new != k && (k-k_new)%2==1) ++k_new;
  
  long long ans = std::abs(std::abs(x)-k_new*d);

  return ans;

}

int main() {
  std::cout << solve() << std::endl; 
  return 0;
}


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

int main() {
	int a = 0, b = 0;
	for (int c = 0; c < 4; c++) {
		int d;
		cin >> d;
		a += d;
	}
	for (int c = 0; c < 4; c++) {
		int d;
		cin >> d;
		b += d;
	}
	cout << max(a, b) << endl;
}

Measured memory_bytes: 3120
#include<bits/stdc++.h>
using namespace std;
long h,w,ans=0x7fffffffffffffff,a,b,c,d,e,i;
long f(long h,long w){
	for(i=0;i<=h/2;i++){
		a=w*i;b=w/2*(h-i);c=(h-i)/2*w;d=h*w-a-b;e=h*w-a-c;
		ans=min({ans,max({a,b,d})-min({a,b,d}),max({a,c,e})-min({a,c,e})});
	}
}
main(){cin>>h>>w;f(h,w);f(w,h);cout<<ans;}

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

int main(){
	string s;
	int i=0;
	getline(cin,s);
	while (1){
		if (s[i] == NULL)break;
		if (isupper(s[i])){
			s[i] = tolower(s[i]);
			cout << s[i];
		}
		else if (islower(s[i])){
			s[i] = toupper(s[i]);
			cout << s[i];
		}
		else{
			cout << s[i];
		}
		i++;
	}
	cout << endl;
	return 0;
}

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

using ll=long long;
const ll MOD=1000000007;

int main() {
  int a,b;
  cin >> a >> b;
  int d=a*b;
  if(d%2==1){
    cout << "Yes" << endl;
  }
  else
    cout << "No" << endl;
}


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

template<typename First, typename Second, typename Third>
struct triple {
   First first;
   Second second;
   Third third;
};
using namespace std;
void solve(){
    string s;
    cin>>s;
    int i;
   string r="";
    for( i=0;i<s.size();i++){
        if(s[i]=='/')
           break;
        r+=s[i];
    }
    int x=stoi(r); 
    x++;
   cout<<x<<s.substr(i,s.size());
}
int main(){
    std::ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    solve();
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std; 
int main()
    {
    int left,right,up,down,w,h,n,x,y,a;
    cin>>w>>h>>n;
    right=w;up=h;down=0;left=0;
	for(int i=1;i<=n;i++)
	{
		cin>>x>>y>>a;
		if(a==1)left=max(left,x);
		if(a==2)right=min(right,x);
		if(a==3)down=max(down,y); 
		if(a==4)up=min(up,y);
	   }   
	   if(left>right||down>up)cout<<0;
	   else
	   cout<<(right-left)*(up-down);
	   return 0;
} 


Measured memory_bytes: 256
n, k = map(int, input().split())
r,s,p = map(int, input().split())
t = list(input())

lis = []
for i in t:
    if i == 'r':
        lis.append('p')
    elif i == 's':
        lis.append('r')
    else:
        lis.append('s')

ans1 = 0
for i in range(k, len(lis)):
    if lis[i] == lis[i-k]:
        lis[i] = 'o'

rc = lis.count('r') * r
sc = lis.count('s') * s
pc = lis.count('p') * p

print(rc+sc+pc)

Measured memory_bytes: 10524
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long

int main() {
    string s ;
    ll k , i ;
    cin >> s >> k ;
    string t = s ;
    sort(t.begin(),t.end()) ;
    if (t[0]==t[t.size()-1]) {
        cout << (t.size()*k)/2 << endl ;
        return 0 ;
    }

    ll dif = 0 , dif1=0 ;
    for ( i = 1 ; i< s.size() ; i++) {
        if (s[i]==s[i-1]) {
            i++ , dif++ ;
        }
    }
    s= s+s ;
    if (k>1) {
        for ( i = 1 ; i< s.size() ; i++) {
        if (s[i]==s[i-1]) {
            i++ , dif1++ ;
        }
    }
    dif1-=dif ;
    }


    cout << dif+ (dif1 * (k-1) ) ;


}


Measured memory_bytes: 256
n, k = map(int, input().split())
a = list(map(int, input().split()))

c = [0] * 10000
for aa in a:
    ba = format(aa, 'b')
    ba = ba[::-1]
    for i in range(len(ba)):
        if ba[i] == '1':
            c[i] += 1
d = ''
for cc in c:
    if cc <= (n-1) //2:
        d += '1'
    else:
        d += '0'


kb = format(k, 'b')
can = False
kk = ''
d = d[:len(kb)]
d = d[::-1]
for i in range(len(kb)):
    tmp = kb[i]
    if tmp == '1' and d[i] == '0':
        tmp = '0'
        can = True
    elif tmp == '0' and d[i] == '1' and can:
        tmp = '1'
    kk += tmp
x = int(kk, 2)
ans = 0
for aa in a:
    ans += (x ^ aa)
print(ans)

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

int main(void){
  int N;
  bool ans = false;
  cin >> N;

  for(int i = 1; i <= 9; i++){
    for(int j = 1; j <= 9; j++){
      if(i * j == N){
	ans = true;
	break;
      }
    }
  }

  if(ans == true)
    printf("Yes\n");
  else
    printf("No\n");
  
  return 0;
}

Measured memory_bytes: 3572
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i=0; i<(int)(n); i++)
#define all(x) x.begin(), x.end()
#define mod 1000000007
typedef long long ll;

int main(){
  ll n;
  cin >> n;
  vector<ll> vec(n+1);
  for(ll i=0; i<=n; i++) cin >> vec[i];
  ll res = 0;
  ll current = 0;
  vector<ll> mx(n+1);
  if(n == 0 && vec[0] != 1){
    cout << -1 << endl;
    return 0;
  }
  if(n != 0 && vec[0] != 0){
    cout << -1 << endl;
    return 0;
  }
  for(ll i=0; i<=n; i++){
    if(i == 0) mx[i] = 1;
    else{
      if((mx[i-1]-vec[i-1])*2 < vec[i]){
        cout << -1 << endl;
        return 0;
      }
      mx[i] = min((mx[i-1]-vec[i-1])*2, (ll)1000000000000000000);
    }
  }
  for(ll i=n; i>=0; i--){
    if(i == n){
      current += vec[i];
      res += current;
    }else{
      current = min(vec[i]+current, mx[i]);
      res += current;
    }
  }
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 4816
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
#define rep(i, n) for(int i=0;i<(int)n;i++)
#define PI acos(-1)
#define fast_io ios_base::sync_with_stdio(false) ; cin.tie(0); cout.tie(0);
ll mod=1e9+7;

ll rep_pow(ll a, ll b){//繰り返し2乗法
    if(b==0) return 1;
    else if(b%2==0){
        ll memo = rep_pow(a, b/2);
        return memo*memo%mod;
    }else{
        return rep_pow(a, b-1)*a%mod;
    }
}
ll nCr(ll n, ll r){//mod逆元　nCr
    ll ret=1;
    rep(i,r){
        ret *= n-i;//分子
        ret %= mod;
        ret *=rep_pow(r-i, mod-2);//mod逆元
        ret %= mod;
    }
    return ret;
}
ll gcd(ll a, ll b){if(b==0) return a; return gcd(b, a%b);}
bool isPrime(int x){
    if(x==1) return false;
    else if(x==2) return true;
    else if(x%2==0) return false;
    for(int i=3;i<=sqrt(x);i+=2){
        if(x%i==0){
            return false;
        }
    }
    return true;
}

int main(){
    fast_io

    int n;
    cin>>n;
    int s[n];
    rep(i,n) cin>>s[i];

    int five_min=10500;
    int ans=0;

    rep(i,n){
        ans+=s[i];
        if(s[i]%10!=0) five_min=min(s[i], five_min);
    }
    if(ans%10==0) cout<<max(ans-five_min, 0)<<endl;
    else cout<<ans<<endl;
    return 0;
}

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

using namespace std;

int main() {
	int k, t, m;
	cin >> k >> t;
	cin >> m;
	t--;
	while(t--){
		int num;
		cin >> num;
		m = max(m, num);
	}
	cout << max(0, m - (k + 1 - m));
	return 0;
}


Measured memory_bytes: 3592
import math
import string
import collections
from collections import Counter
from collections import deque
from decimal import Decimal
import sys
import fractions


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


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
c1 = input()
c2 = input()
if c2[2] == c1[0] and c1[1] == c2[1] and c1[2] == c2[0]:
    print('YES')
else:
    print('NO')


Measured memory_bytes: 60396
import Control.Monad
import Data.List
 
readInt = readLn :: IO Int
readInts = map read . words <$> getLine :: IO [Int]
readNInts = flip replicateM readInts

main :: IO ()
main = do
  [n, m] <- readInts
  a <- map tail <$> readNInts n
  print . length $ foldr1 intersect a

Measured memory_bytes: 1148
#include <cstdio>

int main(){
    long long int m, n, gcd, lcm, temp;
    while(scanf("%lld %lld", &m, &n) == 2){
        lcm = n * m;
        if( m < n ){
            temp = m;
            m = n;
            n = temp;
        }
       for(;;){
           if(n == 0) break;
           temp = n;
           n = m % n;
           m = temp;
       }
       gcd = m;
       lcm = lcm / gcd;
       printf("%lld %lld\n", gcd, lcm);
    }
    return 0;
}

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

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

    vector<int> a(n);
    rep(i, n) {
        cin >> a[i];
    }

    set<int> sum_set;
    rep(i, 1<<n) { // ありうる合計値の組み合わせは多くとも2^20=1048576通り
        bitset<20> bit = i;
        int sum = 0;
        rep(j, n) {
            if (bit.test(j)) sum += a[j];
        }
        sum_set.insert(sum); // 合計値の組み合わせを重複を避けてソート
    }

    int q;
    cin >> q;

    vector<int> m(q);
    vector<string> answer(q);
    rep(i, q) {
        cin >> m[i];
        if (binary_search(sum_set.begin(), sum_set.end(), m[i])) answer[i] = "yes";
        else answer[i] = "no";
    }
    
    rep(i, q) {
        cout << answer[i] << endl;
    }
}


Measured memory_bytes: 3224
I=lambda:map(int,input().split())
N,M=I()
*A,=I()
#A=sorted(A)[::-1]
BC=sorted([list(I()) for _ in [0]*M]+[[1,a]for a in A], key=lambda x:-x[1])
i=0
r=0
for b,c in BC:
    if i+b>=N:
        r+=(N-i)*c
        break
    else:
        i+=b
        r+=b*c
print(r)

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

int main(void) {
	int n;
	int a[100000] = { 0 };
	int min = INT_MAX, temp = -1;
	int min_id,temp_id;
	int flag = -1;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
		if (min > a[i]) min = a[i], min_id = i;
	}

	while (flag != n - 1) {
		flag = 0, temp = min, temp_id = min_id;
		for (int i = 0; i < n; i++) {			
			if (i != temp_id) {
				a[i] %= temp;
				if (min > a[i] && a[i] != 0)min = a[i], min_id = i;
			}
			if (a[i] == 0) flag++;
			//printf("a[%d]=%d\n", i, a[i]);
		}
		//printf("%d\n", temp);
	}
	printf("%d", temp);
	return 0;
}

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

// Shrotening
#define fst first
#define snd second
#define pb push_back

// Loop
#define FOR(i,a,b) for(auto i=(a);i<(b);++i)
#define RFOR(i,a,b) for(auto i=(a);i>=(b);--i)

#define REP(i,a) for(long i=0;i<(a);++i)
#define RREP(i,a) for(long i=(a);i>=0;--i)

#define EACH(i,a) for(auto (i)=(a).begin(),_END=(a).end();i!=_END;++i)
#define REACH(i,a) for(auto (i)=(a).rbegin(),_END=(a).rend();i!=_END;++i)

//Algorithm
#define ALL(a) (a).begin(), a.end()
#define RALL(a) (a).rbegin(), a.rend()
#define EXIST(a,x) ((a).find(x)!=(a).end())
#define SORT(a) std::sort((a).begin(), (a).end())
#define UNIQUE(a) std::sort((a).begin(), a.end()), a.erase(std::unique((a).begin(), a.end()), a.end());
#define SUM(a) std::accumulate((a).begin(), (a).end(), 0);

//Setting
#define OPT std::cin.tie(0);std::ios::sync_with_stdio(false);

//debug message
bool debug = true;
#define MSG(s)   if(debug){std::cout << s << std::endl;}
#define DEBUG(x) if(debug){std::cout << "debug(" << #x << "): " << x << std::endl;}

//alias
typedef long long LL;
typedef std::vector<char> VC;
typedef std::vector<int>  VI;
typedef std::vector<long> VL;
typedef std::vector<long long> VLL;

typedef std::vector< VC > VC2;
typedef std::vector< VI > VI2;
typedef std::vector< VL > VL2;
typedef std::vector< VLL > VLL2;

typedef std::pair<int,int> PII;

int N, t;
std::vector< PII > h;

int main() {
    std::cin >> N >> t;
    h.resize(N);
    REP(i, N) {
        std::cin >> h[i].fst >> h[i].snd;
    }

    SORT(h);

    long double maxRad = 0.0;
    int prevHight = 0;
    for(auto it: h) {
        if(it.snd <= prevHight) continue;
        long double rad = std::atan2(it.snd, it.fst);
        maxRad = std::max(maxRad, rad);
        prevHight = it.snd;
    }
    
    std::cout << std::fixed << std::setprecision(5) << std::tan(maxRad) * t << std::endl;
}



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

int ch_to_int(char c){
	return (int)c - '0';
}

int get_num(string s){
	int num = 0;
	int count = 1;
	string::iterator iter = s.begin();
	while(iter != s.end()){
		if(isdigit(*iter)) count = ch_to_int(*iter);
		else if(*iter == 'm'){
			num += count * 1000;
			count = 1;
		}else if(*iter == 'c'){
			num += count * 100;
			count = 1;
		}else if(*iter == 'x'){
			num += count * 10;
			count = 1;
		}else {
			num += count;
			count = 1;
		}
		iter++;
	}
	return num;
}

void print_mcxi(int num){
	int c[4];
	char chs[] = {
		'm', 'c', 'x', 'i'
	};
	c[0] = num / 1000;
	c[1] = (num % 1000) / 100;
	c[2] = (num % 100) / 10;
	c[3] = num % 10;
	for(int i = 0; i < 4; i++){
		if(c[i] == 0) continue;
		if(c[i] == 1) cout << chs[i];
		else cout << c[i] << chs[i];
	}
	cout << endl;
}

int main(){
	int n;
	cin >> n;
	string s1, s2;
	for(int i = 0; i < n; i++){
		cin >> s1 >> s2;
		int num = get_num(s1) + get_num(s2);
		print_mcxi(num);
	}
	return 0;
}

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

using namespace std;

int n, k;
int a[100011];
int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a%b);
}
int main()
{
    scanf("%d%d",&n, &k);
    for (int i=1;i<=n;i++) scanf("%d", &a[i]);
    int mx = 0;
    for (int i=1;i<=n;i++) mx = max(mx, a[i]);
    if (mx < k)
    {
        printf("IMPOSSIBLE");
        return 0;
    }
    if (n == 1)
    {
        if (a[1] == k) printf("POSSIBLE");
        else printf("IMPOSSIBLE");
        return 0;
    }
    int res = gcd(a[1], a[2]);
    for (int i=3;i<=n;i++) res = gcd(res, a[i]);
    if (k % res == 0)
    {
        printf("POSSIBLE");
    }
    else
    {
        printf("IMPOSSIBLE");
    }
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n) for(int i = 0; i < n; i++)
const ll N = 1e3 + 200;
const ll INF = 0x3f3f3f;
const ll Mode = 1e9 + 7;
int main(){
	ll n;
	cin>>n;
	vector<ll> a(n);
	int t = 0;
	int flag = 0;
	rep(i,n){
		int x;
		cin>>x;
		if(x != i+1 && t == 0){
			t = x;
		}else if(x != i+1){
			if(t != i+1){
				flag = 1;
			}
		}
	}
	if(flag){
		cout<<"NO"<<endl;
	}else{
		cout<<"YES"<<endl;
	}
	return 0;
}



Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
using namespace std;
#define mod 1000000007
#define N 130
int qpow(int base,int n)
{
	if (!n) return 1;
	int ans=base;--n;
	while(n)
	{
		if (n&1) ans=1ll*ans*base%mod;
		base=1ll*base*base%mod;
		n>>=1;
	}
	return ans;
}
int f[N][N][2],g[N];
int main()
{
	int H,W,K;
	scanf("%d%d%d",&H,&W,&K);
	g[0]=1;g[1]=2;g[2]=3;for (int i=3;i<=W;++i) g[i]=(g[i-2]+g[i-1])%mod;
	f[1][0][1]=1;
	for (int j=1;j<=H+1;++j)
	{
		for (int i=1;i<=W;++i)
			f[i][j][1]=((j==1?f[i][j-1][1]:1ll*f[i][j-1][1]*g[max(i-2,0)]%mod*g[max(W-i-1,0)]%mod)+f[i][j-1][0])%mod;
		for (int i=1;i<=W;++i)
			f[i][j][0]=(((i-1)?1ll*f[i-1][j][1]*g[max(i-3,0)]%mod*g[max(W-i-1,0)]%mod:0)+((i==W)?0:1ll*f[i+1][j][1]*g[max(i-2,0)]%mod*g[max(0,W-i-2)]%mod))%mod;
	}
	printf("%d",f[K][H+1][1]);
	return 0;
}

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

void printArray(int* A, int N){

  for (int i = 0; i < N; i++) {
    std::cout << A[i];
    if (i!=N-1) {
      std::cout << " ";
    }
  }
  std::cout <<'\n';
}

void bubbleSort(int* A, int n){
  int flag=1;
  int cnt=0;
  while (flag) {
    flag=0;
    for (int i = n-1; i >= 0; i--) {
      if(A[i-1] > A[i]){
        std::swap(A[i-1], A[i]);
        cnt++;
        flag=1;
      }
    }
  }

  printArray(A,n);
  std::cout << cnt << '\n';
  
}

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

  int* A = new int[n];
  for (int i = 0; i < n; i++) {
    std::cin >> A[i];
  }

  bubbleSort(A,n);

  return 0;
}



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

long long N;

#define BAK 1
#define FRONT 2

int main(){
	cin >> N;

	deque<long long> dq;
	for(long long i = 0; i < 100 && N; i++){
		//cout << "N = " << N << endl;
		if((N - 1)%2 == 0){
			//cout << "bak" << endl;
			N = (N-1)/2;
			dq.push_front(BAK);
		}else{
			//cout << "fron" << endl;
			N--;
			dq.push_front(FRONT);
		}
	}

	deque<long long> ansdq;

	for(long long i = 0; i < dq.size(); i++){
		if(dq[i] == BAK){
			ansdq.push_back(i+1);
		}else{
			ansdq.push_front(i+1);
		}
	}


	cout << 2 * dq.size() << endl;
	for(long long i = 1; i <= dq.size(); i++){
		cout << i << " ";
	}

	for(long long i = 0; i < dq.size(); i++){
		cout << ansdq[i];
		if(i != ansdq.size() - 1){
			cout << " ";
		}
	}
	cout << endl;
}



Measured memory_bytes: 256
N = int(input())
from collections import defaultdict
G = defaultdict(list)
EdaNum = {}
Ki = [[float('inf')]*(N+1) for i in range(N+1)]
for i in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
    EdaNum[(min(a,b),max(a,b))] = i
    Ki[a][b] = 1
    Ki[b][a] = 1

Next = [[-1]*(N+1) for i in range(N+1)]
for i in range(1,N+1):
    for j in range(1,N+1):
        Next[i][j] = j

        
for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            if Ki[i][k] + Ki[k][j] < Ki[i][j]:
                Ki[i][j] = Ki[i][k] + Ki[k][j]
                Next[i][j] = Next[i][k]

M = int(input())
MM = [set() for i in range(M)]
#print(EdaNum)
#print(Next)
for i in range(M):
    u,v = map(int,input().split())
    now = u
    while now != v:
        nex = Next[now][v]
        MM[i].add(EdaNum[(min(now,nex),max(now,nex))])
        now = nex
        
#print(MM)
import itertools
zero1 = [0,1]
ans = 0

for i in itertools.product(zero1,repeat = M):
    #print(ans)
    count = 0
    root = set()
    for j in range(M):
        if i[j] == 0:
            count += 1
        else:
            root |= MM[j]
    #print(i,len(root),count)
    if (M-count)%2 ==0:
        ans += pow(2,N-1-len(root))
    else:
        ans -= pow(2,N-1-len(root))
        
print(ans)

Measured memory_bytes: 47516
'''
辺のコストをmin(Ax, By)とする代わりに、
辺のコストをAxもしくはByの好きな方にしてよいとしたときの最小値を求める

各頂点vについて、
１．Av, Bvともに選ばれる
２．Avのみ選ばれる
３．Bvのみ選ばれる
４．Av, Bvとも選ばれない

すべてタイプ2のときはsum(A), すべてタイプ3のときはsum(B)
それ以外は、タイプ1 = タイプ4 
2...2 4141..4 3...3 1
と構成すればよい
A, Bを合併したリストから小さい順にN個取る
この時に、最初のN個に同じ頂点由来のAv, Bvが両方含まれていたら上のように構成してしまえばよい
明らかにこれが最小値
含まれていないときは, 最初のn項についてそれぞれ取り除いたときにどうなるかを考える
Aw/Bwを取り除いたとすると, N+1番目の項がBw/AwでなければN+1番目の項を追加
Bw/Awの時はN+2番目の項を追加
（最初のN項が頂点について被りがないという条件から、これにより必ずあるvについてAv, Bv両方が含まれることになる
'''

n = int(input())
x = []
for i in range(n):
    ai, bi = map(int, input().split())
    x += [[i, ai, 0], [i, bi, 1]]
s1 = sum([x[2 * i][1] for i in range(n)])
s2 = sum([x[2 * i + 1][1] for i in range(n)])


x.sort(key = lambda x: x[1])
s3 = sum([x[i][1] for i in range(n)])
if len(set([x[i][0] for i in range(n)])) != n:
    print(min(s1, s2, s3))
else:
    if x[n - 1][0] == x[n][0]:
        s4 = min(s3 - x[n - 1][1] + x[n + 1][1], s3 - x[n - 2][1] + x[n][1])
    else:
        s4 = s3 - x[n - 1][1] + x[n][1]
    print(min(s1, s2, s4))


Measured memory_bytes: 40640
#include <iostream>
#include <array>
#include <map>
#include <algorithm>
#include <cmath>
#include <vector>
#include <fstream>
#include <string>
#include <random>
#include <queue>
#include <iomanip>
#include <functional>
#include <climits>
#include <tuple>
#include <unordered_map>
#include <limits>
#include <functional>
#include <cassert>
#include <numeric>
#include <bitset>

#define FOR(x,n) for(int x = 0; x < n; x++)
#define INPUT(x) scanf("%d",&x);
#define PUT(x) cout << x << endl
#define DPUT(x) printf("%.15lf\n",x)
#define GET(x,y) std::get<x>(y)
#define CHMAX(x,y) x = std::max(x,y)
#define CHMIN(x,y) x = std::min(x,y)
#define SP_END (i != n - 1 ? ' ' : '\n') ;

using namespace std;

using ll = long long int;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vll = std::vector<ll>;
using vpll = std::vector<pll>;
using vpii = std::vector<pii>;
using vi = std::vector<int>;
using vvi = std::vector<vi>;
using vvpii = std::vector<vpii>;
using vch = std::vector<char>;
using vvch = std::vector<vch>;
using tiii = std::tuple<int, int, int>;

const ll mod197 = 1000000007LL;
const ll INF = 10000000000LL;

const double PI11 = 3.14159265359;

const int dis[5] = { 0,1,0,-1,0 };

const int disD[4] = { 0,1,1,0 };

ll a[10000] = {};
ll b[10000] = {};

int main(void)
{
	ll n,answer = 0;
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}

	for (int i = 0; i < n; i++) {
		cin >> b[i];
	}

	for (int i = 0; i < n; i++) {
		if (a[i] < b[i]) {
			answer += (b[i] - a[i]) / 2;
		}
		else if(a[i] > b[i]){
			answer -= (a[i] - b[i]);
		}
	}

	if (answer >= 0) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}

	return 0;
}

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

int main(void)
{
	char number[104730] = {0};
	int i, j, n;
	long sum;

	for (i = 3; i <= 104729; i += 2) number[i] = 1;
	number[2] = 1;
	for (i = 3; i * i <= 104729; i += 2){
		if (number[i] == 1){
			for (j = 2; i * j <= 104729; j++){
				number[i * j] = 0;
			}
		}
	}
	
	while (1){
		scanf("%d", &n);
		
		if (n == 0) break;
		
		sum = 0;
		j = 2;
		while (n != 0){
			if (number[j] == 1){
				sum += (long)j;
				n--;
			}
			j++;
		}
		
		printf("%ld\n", sum);
	}
	return (0);
}

Measured memory_bytes: 0
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <math.h>
#include <cassert>
#define rep(i,n) for(int i = 0; i < n; ++i )
using namespace std;
using ll = long long;
using P = pair<int,int>;

// auto mod int
const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {if ((x += a.x) >= mod) x -= mod; return *this;}
  mint& operator-=(const mint a) {if ((x += mod-a.x) >= mod) x -= mod; return *this;}
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

int main() {
  int n;
  cin >> n;
  vector<ll> bit0(65), bit1(65);
  rep(ni,n) {
    ll a;
    cin >> a;
    rep(i,65){
      if(a&1){
        bit1[i]++;
      } else {
        bit0[i]++;
      }
      a /= 2;
    }
  }
  mint ans(0);
  rep(i,65){
    mint bit = bit0[i]*bit1[i];
    if(bit.x!=0){
      ll num = 1;
      num <<= i;
      bit *= num;
      ans += bit;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
#include <algorithm>
#include <limits.h>
using namespace std;
int n,i,j;
int main(int argc,char const* argv[])
{
  cin >> n;
  vector <int> c(n,0);
  vector <int> s(n,0);
  vector <int> f(n,0);
  vector <int> tmpf(n,0);
  vector<long long> ans(n,0);
  for(i=0;i<n-1;i++)

    {
      cin >> c[i] >> s[i] >> f[i];
      tmpf[i]=f[i];
    }
  ans[n-1]=0;
  for(i=0;i<n-1;i++)
    {
      ans[i]+=s[i]+c[i];
    }
  for(i=0;i<n-1;i++)
    {
      for(j=i+1;j<n-1;j++)
	{
	  if(ans[i]<=s[j]) ans[i]+=(s[j]-ans[i])+c[j];
	  else if(ans[i]>s[j])
	    {
	      if(ans[i]>s[j]+tmpf[j])
		{
		  if((ans[i]-s[j])%f[j]==0)
		    {
		      tmpf[j]=f[j]*(((ans[i]-s[j])/f[j]));
		    }
		  else
		    {
		      tmpf[j]=f[j]*(((ans[i]-s[j])/f[j])+1);
		    }
		}
	      ans[i]+=(s[j]+tmpf[j]-ans[i])+c[j];
	      tmpf[j]=f[j];
	    }
	}
    }
  for(i=0;i<n;i++)
    {
      cout << ans[i] << endl;
    }
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline ll read() {
    ll x=0,f=1; char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())
        if(ch=='-')f=-f;
    for(;ch>='0'&&ch<='9';ch=getchar())
        x=x*10+ch-'0';
    return x*f;
}
inline void chkmin( int &a,int b ) { if(a>b) a=b; }
inline void chkmax( int &a,int b ) { if(a<b) a=b; }
#define _ read()
string s;
int n;
ll ans=1ll,cnt[26];
const int mod = 1e9+7;
int main() {
	n=_;
	cin>>s; 
	for( int i=0;i<n;i++ ) 
		cnt[s[i]-'a']++;
	for( int i=0;i<26;i++ ) ans=ans*(cnt[i]+1)%mod;
	cout<<(ans-1+mod)%mod<<"\n";
}
/*
a b
a  
 */

Measured memory_bytes: 512
import sys

def strongness(x):
    return (x + 11) % 13

a, b = map(int, sys.stdin.readline().split())
a = strongness(a)
b = strongness(b)

def main():
    if a > b: ans = 'Alice'
    elif a == b: ans = 'Draw'
    else: ans = 'Bob'
    print(ans)

if __name__ ==  '__main__':
    main()

Measured memory_bytes: 3060
#include<string>
#include<iostream>
int main(){
  int n;
  std::string s;
  std::cin>>n>>s;
  if(s.size()<=n){
    std::cout<<s<<std::endl;
    return 0;
  }
  std::string s1="";
  for(int i=0;i<n;++i){
    s1+=s[i];
  }
  s1+="...";
  std::cout<<s1<<std::endl;
  return 0;
}

Measured memory_bytes: 3628
#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define maxv 114
stack<pint> S;//辺を追加するスタック
vector<vector<pint> > bc;//二重頂点成分
vector<int> art;//関節点集合
vector<int> gr[maxv];//隣接リストで持つグラフ
int low[maxv],num[maxv];//numは行きがけ順。必ず-1で初期化すること
int it=0;//行きがけ順の頂点番号
int zi[114];

void dfs(int v,int u){
	low[v]=num[v]=it++;
	rep(i,gr[v].size()){
		int w=gr[v][i];
		if(w==u) continue;
		if(num[w]<num[v]) S.push(mp(v,w));//二重頂点成分のために辺をスタックに追加
		if(num[w]<0){
			dfs(w,v);
			low[v]=min(low[v],low[w]);
			if((num[v]==0 && num[w]>1) || (num[v]>0 && low[w]>=num[v])) art.pb(v);//関節点をartに追加
			if(low[w]>=num[v]){//二重頂点成分をbcompに追加
				vector<pint> ed;
				while(1){
					pint p=S.top();S.pop();ed.pb(p);if(p.fi==v && p.se==w) break;
				}
				if(ed.size()>0) bc.pb(ed);
			}
		}
		else low[v]=min(low[v],num[w]);
	}
}

lint mo=1000000007;
lint co[222][222];
lint extgcd(lint a, lint b, lint &x, lint &y) {
  lint g = a; x = 1; y = 0;
  if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x;
  return g;
}
lint invMod(lint a, lint m) {
  lint x, y;
  if (extgcd(a, m, x, y) == 1) return (x + m) % m;return 0;
}
int gcd( int m, int n )
{
	int a=max(m,n),b=min(m,n);
	if(m==0) return n;if(n==0) return m;
	if(a%b==0) return b;
	return gcd(b,a-b*(a/b));
}
lint zyo(lint x,lint y){
    lint ret=1,a=x;
    while(y>0){
    	if(y%2==1) ret=(ret*a)%mo;
    	a=(a*a)%mo;y/=2;
    }
    return ret;
}
lint cal(int a,lint K){
	lint out=0;
	REP(i,1,a+1){
		out+=zyo(K,gcd(a,i));
		out%=mo;
	}
	out*=invMod(a,mo);
	//cout<<out%mo<<endl;
	return out%mo;
}
int main()
{
	rep(i,214){
		co[i][0]=co[i][i]=1;
		REP(j,1,i) co[i][j]=(co[i-1][j-1]+co[i-1][j])%mo;
	}
	
	int n,m,K,a,b;lint out=1;
	cin>>n>>m>>K;
	memset(zi,0,sizeof(zi));
	rep(i,m){
		cin>>a>>b;a--;b--;
		gr[a].pb(b);gr[b].pb(a);
		zi[a]++;zi[b]++;
	}
	memset(num,-1,sizeof(num));//初期化を忘れない！！！！
	rep(i,n){
		if(num[i]>=0 || zi[i]<1) continue;
		dfs(i,-1);
	}
	
	/*rep(i,art.size()) cout<<art[i]<<endl;cout<<endl;
	rep(i,bc.size()){
		rep(j,bc[i].size()) cout<<bc[i][j].fi<<' '<<bc[i][j].se<<endl;cout<<endl;
	}*/
	//cout<<(co[57][10]*48*48)%mo<<endl;
	
	rep(i,bc.size()){
		int N=bc[i].size();
		if(N<1) continue;
		set<int> s;
		rep(j,N) s.insert(bc[i][j].fi),s.insert(bc[i][j].se);
		int e=s.size();
		//cout<<e<<' '<<N<<endl;
		if(e==N) out*=cal(e,K);
		else if(e==N+1) out*=zyo(K,N);
		else out*=co[N+K-1][N];
		out%=mo;
	}
	cout<<out%mo<<endl;
}


Measured memory_bytes: 768
#include <algorithm>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
using LL = long long;
#define eps 1e-8
#define fi first
#define se second
#define eb emplace_back
#define close \
    std::ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define FOR(i, x, y) for (LL i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (LL i = (x), _##i = (y); i > _##i; --i)
#define SORT_UNIQUE(c)         \
    (sort(c.begin(), c.end()), \
     c.resize(distance(c.begin(), unique(c.begin(), c.end()))))
#define CASET           \
    int ___T;           \
    scanf("%d", &___T); \
    for (int __CS = 1; __CS <= ___T; __CS++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
mt19937 dlsrand(random_device{}());
mt19937 mrand(std::chrono::system_clock::now().time_since_epoch().count());
int rnd(int x) { return mrand() % x; }
LL bin(LL x, LL n, LL MOD) {
    LL ret = MOD != 1;
    for (x %= MOD; n; n >>= 1, x = x * x % MOD)
        if (n & 1) ret = ret * x % MOD;
    return ret;
}
inline LL get_inv(LL x, LL p) { return bin(x, p - 2, p); }
const double PI = acos(-1.0);
constexpr int maxn = 1e6 + 10;
constexpr int INF = 0x3f3f3f3f;
constexpr ll linf = 0x3f3f3f3f3f3f3f3f;
constexpr int mod = 998244353;
void add(int &a, int b) {
    a += b;
    if (a >= mod) a -= mod;
}
void dec(int &a, int b) {
    a -= b;
    if (a < 0) a += mod;
}
int n, s, a[maxn], dp[maxn];

int main() {
    cin >> n >> s;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        for (int j = s; j >= a[i]; j--) {
            dp[j] = (dp[j] + dp[j - a[i]]) % mod;
        }
        add(dp[a[i]], i);
        add(ans, dp[s]);
    }
    cout << ans << endl;
}

Measured memory_bytes: 2432
n = int(input())
tree = [0] * n
root = set(range(n))
def type(i, parent, sibling, depth):
    if i == -1:
        return -1
    node = tree[i]
    l, r = node[0], node[1]
    node[2], node[3], node[5] = parent, sibling, depth
    node[4] = (l != -1) + (r != -1)
    h = node[6] = max(type(l, i, r, depth + 1), type(r, i, l, depth + 1)) + 1
    return h
 
while n:
    i, l, r = list(map(int, input().split()))
    tree[i] = [l, r] + [0] * 5
    root -= {l, r}
    n -= 1
type(root.pop(), -1, -1, 0)
for i, node in enumerate(tree):
    l, r, p, s, deg, dep, h = node
    print('node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.format(i, p, s, deg, dep, h,
    'root' if not dep else 'internal node' if deg else 'leaf'))



Measured memory_bytes: 5604
N = int(input())
L_L = [int(x) for x in input().split()]

L_L.sort()
ans = 0

for i in range(N):
    _li = L_L[i]
    for j in range(i+1, N):
        _lj = L_L[j]
        if _li == _lj:
            continue
        for k in range(j+1, N):
            _lk = L_L[k]
            if _li == _lk or _lj == _lk:
                continue
            if _li + _lj > _lk:
                ans += 1


print(ans)


Measured memory_bytes: 9096
#include <bits/stdc++.h>
using namespace std;
#define all(c) (c).begin(),(c).end()
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define REP(i,m,n) for(int i=(int)(m);i<(int)(n);i++)
#define rep(i,n) REP(i,0,n)
#define iter(c) __typeof((c).begin())
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
#define pb(a) push_back(a)
#define pr(a) cout<<(a)<<endl
#define PR(a,b) cout<<(a)<<" "<<(b)<<endl
#define F first
#define S second
#define ll long long
bool check(int n,int m,int x,int y){return (x<0||x>=n||y<0||y>=m)?false:true;}
const ll MAX=1000000007,MAXL=1LL<<60,dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
typedef pair<int,int> P;

int main() {
  int n,m,k;
  while(cin >> n >> m >> k && (n||m||k)) {
    int a,b,t;
    string s;
    int w[n+1][m+1],p[n+1][m+1],c[n+1];
    memset(w,0,sizeof(w));
    memset(p,0,sizeof(p));
    memset(c,0,sizeof(c));
    while(k--) {
      cin >> a >> b >> t >> s;
      if(s[0]=='W') w[a][b]++;
      else {
	p[a][b]+=t;
	c[a]++;
      }
    }
    map<int,vector<P> > x;
    x.clear();
    REP(i,1,n+1) {
      int d=0;
      REP(j,1,m+1) {
	if(p[i][j]) d+=p[i][j]+w[i][j]*1200;
      }
      x[c[i]].pb(P(d,i));
    }
    for(map<int,vector<P> >::reverse_iterator it=x.rbegin(); it!=x.rend(); it++) {
      vector<P> v=it->S;
      sort(all(v));
      rep(i,v.size()) cout << v[i].S << " " << it->F << " " << v[i].F << endl; 
    }
  }
  return 0;
}


Measured memory_bytes: 1228
import java.util.*;

public class Main {
	private static List<Integer>[] g;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		g = new ArrayList[n];
		for (int i = 0; i < n; i++) {
			g[i] = new ArrayList<>();
		}
		for (int i = 0; i < m; i++) {
			int a = sc.nextInt() - 1;
			int b = sc.nextInt() - 1;
			g[a].add(b);
			g[b].add(a);
		}

		System.out.println(dfs(0, new HashSet<>()));
	}

	private static int dfs(int v, Set<Integer> visited) {
		if (visited.contains(v)) {
			return 0;
		}

		if (visited.size() == g.length - 1) {
			return 1;
		}

		visited.add(v);

		int a = 0;
		for (int i = 0; i < g[v].size(); i++) {
			int next = g[v].get(i);
			if (!visited.contains(next)) {
				a += dfs(next, visited);
			}
		}

		visited.remove(v);
		return a;
	}
}


Measured memory_bytes: 22228
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;

constexpr int MOD = 1e9 + 7;

string t, b;
int N, M;
int memo[1010][1010];

int dfs(int t_i = 0, int b_i = 0) {
  if (b_i >= M) return 1;
  if (t_i >= N) return 0;

  if (memo[t_i][b_i] != -1) return memo[t_i][b_i];

  int ret = dfs(t_i + 1, b_i) % MOD;
  if (t[t_i] == b[b_i]) {
    (ret += dfs(t_i + 1, b_i + 1)) %= MOD;
  }
  return memo[t_i][b_i] = ret;
}

int main() {
  cin >> t >> b;
  N = t.size();
  M = b.size();
  memset(memo, -1, sizeof(memo));
  cout << dfs() << endl;
}

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

int main(){
    int l, ans;
    bool a = true;
    cin >> l;
    vector<int> c(l);
    vector<int> ana(0);
    for (int i = 0; i < l; ++i){
        cin >> c[i];
    }
    for (int i = 0; i < l; ++i){
        int last;
        if (c[i] > 0){
            for (int j = 0; j < ana.size(); ++j){
                if (ana[j] == c[i]){
                    ans = i + 1;
                    a = false;
                    break;
                }
            }
            ana.push_back(c[i]);
            last = ana.back();
        }
        else {
            if (last + c[i] != 0){
                a = false;
                ans = i + 1;
                break;
            } else {
                ana.pop_back();
                last = ana.back();
            }
        }
        if(!a) break;
    }
    if(!a) cout << ans << endl;
    else cout << "OK" << endl;
    return 0;
}


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

const ll mod = 998244353;

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

    ll dp[200005], sum[200005];
    dp[1] = 1;
    sum[1] = 1;
    for(int i=2;i<=n;i++){
        for(int j=0;j<k;j++){
            if(i-l[j] > 0) dp[i] += sum[i-l[j]];
            if(i-r[j]-1 > 0) dp[i] -= sum[i-r[j]-1];
            dp[i] %= mod;
        }
        sum[i] = sum[i-1] + dp[i];
    }

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

Measured memory_bytes: 6752
#define _USE_MATH_DEFINES

#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <utility>
#include <climits>
#include <vector>
#include <map>
using namespace std;

#define ll long long
const int MOD = 1000000007;//10^9+7

int max(int a, int b) {

	if (a > b)return a;
	else return b;

}
//aとbの大きい方

int min(int a, int b) {

	if (a < b)return a;
	else return b;

}
//aとbの小さい方

int avd_i(int a, int b) {

	if (a > b)return a - b;
	else return b - a;

}
double avd_d(double a, double b) {

	double re;
	if (a > b)re = a - b;
	else re = b - a;
	return re;

}
//aとbの差の絶対値

ll powsur(ll a, ll b, ll p) {

	if (b == 0) {

		return 1;

	}
	else if (b % 2 == 0) {

		ll d = powsur(a, b / 2, p);
		return ((d%p)*(d%p)) % p;

	}
	else {

		return ((a%p)*powsur(a, b - 1, p) % p) % p;

	}

}
//pは素数,aのb乗をpで割った余り

ll CMOD(ll n, ll r, ll p) {

	ll a = 1, b = 1, c = 1, re;
	for (int i = 1; i <= n; i++) {

		a *= i;
		a = a%p;

	}
	for (int i = 1; i <= r; i++) {

		b *= i;
		b = b%p;

	}
	for (int i = 1; i <= n - r; i++) {

		c *= i;
		c = c%p;

	}
	b = powsur(b, p - 2, p);
	c = powsur(c, p - 2, p);
	re = ((a%p)*(b%p)) % p;
	re = ((re%p)*c%p) % p;

	return re;

}
//pは素数,(nCr)%p

int main() {

	int N;

	cin >> N;

	if (N % 10 == 9 || N / 10 == 9)cout << "Yes" << endl;
	else cout << "No" << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using Graph= vector<vector<ll>>;
struct edge{ll to ; ll cost ;} ;
using graph =vector<vector<edge>> ;
#define rep(i,n) for (ll i=0; i < (n); ++i)
#define rep2(i,n,m) for(ll i=n;i<=m;i++)
#define rep3(i,n,m) for(ll i=n;i>=m;i--)
#define pb push_back
#define eb emplace_back
#define ppb pop_back
#define mpa make_pair
#define fi first
#define se second 
#define set20 cout<<fixed<<setprecision(20) ;
const ll INF=1e18 ;
inline void chmax(ll& a,ll b){a=max(a,b);}
inline void chmin(ll& a,ll b){a=min(a,b);}
double pi=acos(-1) ;
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}
 
 int main(){
 ll n,m ; cin>>n>>m ;
 vector<ll> A(n) ;
 rep(i,n) cin>>A[i] ;
 ll now=0 ;
 map<ll,ll> mp ;
 mp[now]++ ;
 rep(i,n){
 now= (now+A[i])%m ;
 mp[now]++ ;
 }
 ll ans=0 ;
 for(auto u : mp){
  ans+= u.se*(u.se-1) ;
 }
 cout<< ans/2 <<endl ;
   return 0 ;
}



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

int main() {
	int n, a[50];
	cin >> n;

	for(int i=0; i<n; i++)
		scanf("%d", &a[i]);

	int ans=0;
	for(int i=0; i<n-1; i++) {
		for(int j=i+1; j<n; j++) {
			ans += a[i]*a[j];
		}
	}
	printf("%d\n", ans);

	return 0;
}

Measured memory_bytes: 256
import itertools
N = int(input())
dic = [0 for _ in range(5)]
for i in range(N):
    S = input()
    data = S[0]
    if data == "M":  dic[0] += 1
    if data == "A":  dic[1] += 1
    if data == "R":  dic[2] += 1
    if data == "C":  dic[3] += 1
    if data == "H":  dic[4] += 1
    
a = range(5)
comb = list(itertools.combinations(a, 3))

ans = 0
for c in comb:
    ans += dic[c[0]] * dic[c[1]] * dic[c[2]]
print(ans)

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

using namespace std;

const int N = 1e5+5;
const int MaxN = 2e5+5;
typedef long long ll;
typedef long double ld;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int sum = 0;
    for (int i = 0; i < 5; i++){
        int x;
        cin >> x;
        sum+= x;

    }
    cout << (15-sum) << endl;
}


Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
int main(){
	int b[3][3],a[3][3]={0},n;
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++)
			cin>>b[i][j];
	}
	cin>>n;
	int tmp;
	for(int k=0;k<n;k++){
		int f1=1;
		cin>>tmp;
		for(int i=0;i<3;i++){
			for(int j=0;j<3;j++){
				if(tmp==b[i][j]){
					a[i][j]=1;
				}
			}
		}
	}
	int f2=0,f3=0,f4=0;
	for(int i=0;i<3;i++){
		if(a[i][0]==a[i][2]&&a[i][0]==a[i][1]&&a[i][0]==1){
			f2=1;
			break;
		}
	}
	if(!f2){
		for(int i=0;i<3;i++){
			if(a[0][i]==a[2][i]&&a[0][i]==a[1][i]&&a[0][i]==1){
			f3=1;
			break;
			}
		}
	}
	if(!f3&&!f2){
		if((a[0][0]==a[1][1]&&a[0][0]==a[2][2]&&a[0][0]==1)||(a[2][0]==a[1][1]&&a[2][0]==a[0][2]&&a[0][2]==1)){
			f4=1;
		}
	}
	if(f2||f3||f4)cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0;
}

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

namespace AtCorder_173A
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            int ans = (1000 - (N % 1000)) % 1000;
            Console.WriteLine(ans);
            //Console.ReadKey();
                
        }
    }
}


Measured memory_bytes: 27388
object Main extends App {
  val n = readInt
  implicit val S: Array[Int] = readLine.split(" ").map(_.toInt)
  val q = readInt
  val T = readLine.split(" ").map(_.toInt)

  def binarySearch(key: Int, leftIdx: Int, rightIdx: Int)(list: Array[Int]): Boolean = {
    val centerIdx = (rightIdx + leftIdx) / 2
    val centerElem = list(centerIdx)
    if (leftIdx > rightIdx) false
    else if (leftIdx == rightIdx && key != centerElem) false
    else {
      if (key == centerElem) true
      else if (key > centerElem) binarySearch(key, centerIdx + 1, rightIdx)(list)
      else binarySearch(key, leftIdx, centerIdx - 1)(list)
    }
  }
  println(T.count(t => binarySearch(t, 0, S.length)(S)))
}


Measured memory_bytes: 75540
def g(i,j):
    if i+j<10:
        return 1,i+j
    else:
        a = i+j
        b = a%10+a//10
        return 2,b
def f(c,d):
    if d==1:
        return 0,c
    if d==2:
        return g(c,c)
    if d%2==0:
        a,b = f(c,d//2)
        x,y = g(b,b)
        return 2*a+x,y
    else:
        a,b = f(c,(d-1)//2)
        x1,y1 = g(b,b)
        x2,y2 = g(c,y1)
        return 2*a+x1+x2,y2
M = int(input())
A = [list(map(int,input().split())) for _ in range(M)]
cnt = 0
B = []
for i in range(M):
    c,d = A[i][0],A[i][1]
    a,b = f(c,d)
    cnt += a
    B.append(b)
b = B[0]
for i in range(1,M):
    a,b = g(b,B[i])
    cnt += a
print(cnt)   


Measured memory_bytes: 107296
#include<bits/stdc++.h> //ABC 165_a
#define ll long long
using namespace std;
int k,a,b,t;
int main(){
	cin>>k>>a>>b;
	for(int i=0;i<=b-a;i++){
		t=a+i;
		if(t%k==0){
			cout<<"OK";
			return 0;
		}
	}
	cout<<"NG";
	return 0;
}

Measured memory_bytes: 3604
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <queue>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <stdio.h>
#include <complex>
#include <cstdint>
#include <tuple>

#define M_PI       3.14159265358979323846

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }
inline int readInt() { int x; scanf("%d", &x); return x; }

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<int, PII> TIII;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;

//container util

//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SQ(a) (a*a)
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,s,n) for(int i=s;i<(int)n;++i)
#define REP(i,n) FOR(i,0,n)
#define MOD 1000000007

const int N = 305;
int d[N][N];
int d2[N][N];

int main() {
	int n;
	scanf("%d", &n);
	REP(i, n)REP(j, n)scanf("%d", &d[i][j]);
	memcpy(d2, d, sizeof(d));
	REP(k, n) {
		REP(j, n) {
			FOR(i, j+1, n) {
				if (k == i || k == j)continue;
				if (d[i][j] > d[i][k] + d[k][j]) {
					cout << -1 << endl;
					return 0;
				}
				if (d[i][j] == d[i][k] + d[k][j]) {
					d2[j][i] = d2[i][j] = 0;
				}
			}
		}
	}
	LL ret = 0;
	REP(i, n)FOR(j, i + 1, n)ret += d2[i][j];
	cout << ret << endl;
	return 0;
}

Measured memory_bytes: 1024
package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	fmt.Println(solve(ReadInt(), ReadInt()))
}

func solve(n, m int) int {
	n, m = MinMax(n, m)

	if n == 1 && m == 1 {
		return 1
	}

	if n == 1 {
		return m - 2
	}

	if n == 2 {
		return 0
	}

	return (n - 2) * (m - 2)
}

func MinMax(slice ...int) (int, int) {
	min, max := slice[0], slice[0]
	for _, v := range slice[1:] {
		if min > v {
			min = v
		} else if max < v {
			max = v
		}
	}
	return min, max
}

var reader = bufio.NewReader(os.Stdin)

func Scan(a ...interface{}) {
	if _, err := fmt.Fscan(reader, a...); err != nil {
		panic(err)
	}
}
func ReadInt() (i int)       { Scan(&i); return }
func ReadString() (s string) { Scan(&s); return }


Measured memory_bytes: 1840