akhauriyash/Code-Regression huggingface dataset:
//嘘っぽいのに通ってたやつでいこう

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

char cn[2000100], *ci = cn, c;

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


	fread(cn, 1, 2000100, stdin);
	int N = 0;
	while ((c = *ci++) >= '0') N = N * 10 + c - '0';
	int sL[1001] = {}, sR[1001] = {};
	pair<int, int> RR[500], LL[500];
	int rr = 0, ll = 0;
	int tot = 0;
	rep(i, N) {
		int l = 0, r = 0;
		while ((c = *ci++) >= '(') {
			if (c == '(') r++;
			else {
				if (r > 0) r--;
				else l++;
			}
		}
		tot += r - l;
		if (l < r) {
			if (l <= 1000) sR[l] += r;
			else RR[rr++] = { l,r };
		}
		else {
			if (r <= 1000) sL[r] += l;
			else LL[ll++] = { r,l };
		}
	}

	if (tot != 0) {
		printf("No");
		return 0;
	}

	sort(RR, RR + rr);
	sort(LL, LL + ll);

	int OK = 1;
	int k = 0;
	rep(i, 1001) {
		if (sR[i]) {
			if (k < i) OK = 0;
			k += sR[i];
		}
	}
	rep(i, rr) {
		if (k < RR[i].first) OK = 0;
		k += RR[i].second - RR[i].first;
	}
	k = 0;
	rep(i, 1001) {
		if (sL[i]) {
			if (k < i) OK = 0;
			k += sL[i];
		}
	}
	rep(i, ll) {
		if (k < LL[i].first) {
			OK = 0;
		}
		k += LL[i].second - LL[i].first;
	}

	if (OK) printf("Yes");
	else printf("No");

	Would you please return 0;
}

Measured memory_bytes: 3528
#line 1 "test/algebra/combination.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1501"

#include <bits/stdc++.h>
using namespace std;
using lint     = long long;
const lint mod = 100000007;

#line 1 "test/algebra/../../library/algebra/combination.cpp"
struct Combination {
    vector<lint> fac, finv, inv;
    Combination(lint maxN) : fac(maxN + 100), finv(maxN + 100), inv(maxN + 100) {
        maxN += 100; // for safety
        fac[0] = fac[1] = 1;
        finv[0] = finv[1] = 1;
        inv[1]            = 1;
        for (lint i = 2; i <= maxN; ++i) {
            fac[i]  = fac[i - 1] * i % mod;
            inv[i]  = mod - inv[mod % i] * (mod / i) % mod;
            finv[i] = finv[i - 1] * inv[i] % mod;
        }
    }
    lint operator()(lint n, lint k) {
        if (n < k)
            return 0;
        if (n < 0 || k < 0)
            return 0;
        return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
    }
};
#line 9 "test/algebra/combination.test.cpp"

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int r, c, a1, a2, b1, b2;
    cin >> r >> c >> a1 >> a2 >> b1 >> b2;
    if (a1 > b1)
        swap(a1, b1);
    if (a2 > b2)
        swap(a2, b2);
    int mult = 1;
    int h1   = b1 - a1;
    int w1   = b2 - a2;
    int h2   = a1 - b1 + r;
    int w2   = a2 - b2 + c;
    if (h1 == h2)
        mult *= 2;
    if (w1 == w2)
        mult *= 2;
    int h = min(h1, h2);
    int w = min(w1, w2);
    Combination nCk(2000);
    cout << (nCk(h + w, w) * mult) % mod << "\n";
    return 0;
}



Measured memory_bytes: 3268
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using pint = pair<int,int>;
ll mod = 1000000007,mod2 = 998244353;
int dx[8] = {1,0,-1,0,1,1,-1,-1};
int dy[8] = {0,1,0,-1,1,-1,1,-1};
void chmin(long long &a, long long b) { if (a > b) a = b; }
const long long INF = 1LL<<60;
ll gcd(ll a,ll b){
    if(b == 0) return a;
    else return gcd(b,a%b);
}
ll modpow(long long a, long long n, long long mod2) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod2;
        a = a * a % mod2;
        n >>= 1;
    }
    return res;
}

int main() {
    int n,ans = 0;
    cin >> n;
    vector<int> p(n);
    for (int i = 0; i < n; ++i) {
        cin >> p[i];
        ans += p[i];
    }
    sort(p.begin(),p.end(),greater<int>());
    ans -= p[0]/2;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
  int N, i;
  scanf("%d", &N);
  float A[N];
  for(i = 0; i < N; i ++){
    scanf("%f", &A[i]);
  }
  float con = 0;
  for(i = 0; i < N; i ++){
    con = con + 1/A[i];
  }
  printf("%f", 1/con);
  
  return 0;
}


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

int dfs(int i, int sum, int total){
	if(i <= 10 && sum == 0 && total == 0) return 1;
	if(i >= 10 || sum < 0 || total < 0) return 0;

	return dfs(i+1, sum-i, total-1) + dfs(i+1, sum, total);
}

int main(){
	int n, s, count;
	while(1){
		cin >> n >> s;
		if(n == 0 && s == 0) break;
		count = 0;
		count = dfs(0, s, n);
		cout << count << endl;
	}
}
	



Measured memory_bytes: 3092
from collections import Counter


N = int(input())
lst_A = list(map(int, input().split()))
set_A = set(lst_A)
cnt_A = Counter(lst_A)
ans = 0


for key in set_A:
    cnt_X = cnt_A[key - 1] + cnt_A[key] + cnt_A[key + 1]
    ans = max(ans, cnt_X)


print(ans)

Measured memory_bytes: 16612
# D - Bouquet
n,a,b = map(int,input().split())
MOD = 10**9+7

ans = pow(2,n,MOD)-1
a,b = min(a,b),max(a,b)

tmp = 1
for i in range(1,a+1):
    tmp = tmp*(n+1-i)*pow(i,-1,MOD)
    tmp %= MOD
ans = (ans-tmp)%MOD
for i in range(a+1,b+1):
    tmp = tmp*(n+1-i)*pow(i,-1,MOD)
    tmp %= MOD
ans = (ans-tmp)%MOD

print(ans)

Measured memory_bytes: 9216
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#include<iomanip>
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-7
#define mp(a1,a2) make_pair(a1,a2)
typedef long long ll;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=1e+18+1;
int INF=1e+9+1;
ll gcd(ll x,ll y){
	if(y==0) return x;
	return gcd(y,x%y);
}
int main(){
	int N,A[100001];
	ll ans;
	scan(N);
	rep(i,N){
		scan(A[i]);
		if(i==1) ans=gcd(A[0],A[1]);
		else if(i>=2) ans=gcd(ans,A[i]);
	}
	prin(ans);
	return 0;
}


Measured memory_bytes: 640
#include <cassert>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>

using namespace std;
using lint = long long;
constexpr int MOD = 1000000007, INF = 1111111111;

template <class T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
	for (const auto &e : vec) os << e << (&e == &vec.back() ? "" : " ");
	return os;
}

template <class T1, class T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
	os << p.first << " " << p.second;
	return os;
}

template <class T1, class T2>
ostream &operator<<(ostream &os, const map<T1, T2> &mp) {
	for (const auto &e : mp) os << "[" << e << "] ";
	return os;
}

#ifdef _DEBUG
template <class T>
void dump(const char* str, T &&h) { cerr << str << " = " << h << "\n"; };
template <class Head, class... Tail>
void dump(const char* str, Head &&h, Tail &&... t) {
	while (*str != ',') cerr << *str++; cerr << " = " << h << "\n";
	dump(str + (*(str + 1) == ' ' ? 2 : 1), t...);
}
#define DMP(...) dump(#__VA_ARGS__, __VA_ARGS__)
#else 
#define DMP(...) ((void)0)
#endif

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;

	vector<int> v(N);
	for (int i = 0; i < N; i++) cin >> v[i];
	sort(v.begin(), v.end());

	double ans = v[0];
	for (int i = 1; i < N; i++) {
		ans += v[i];
		ans /= 2.0;
	}

	cout << setprecision(30) << ans << "\n";

	return 0;
}

Measured memory_bytes: 256
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


class BaseF2:
    def  __init__(self, vs=None):
        """vs: list of vecotr in F2
        """
        self.base = []
        if vs is not None:
            for v in vs:
                tmp = v
                for u in self.base:
                    tmp = min(tmp, tmp^u)
                if tmp>0:
                    self.base.append(tmp)
    def insert(self, v):
        for u in self.base:
            v = min(v, v^u)
        if v>0:
            self.base.append(v)
    def check(self, v):
        for u in self.base:
            v = min(v, v^u)
        return v==0
    def clear(self):
        self.base = []
    
    
t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    s = input()
    b0 = BaseF2()
    b1 = BaseF2()
    done = False
    for i in range(n-1, -1, -1):
        if s[i]=="1":
            b1.insert(a[i])
        else:
            b0.insert(a[i])
        for item in b1.base:
            if not b0.check(item):
                print(1)
                done = True
                break
        if done:
            break
    else:
        print(0)

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

int main() {
    using namespace std;
    string S;
    cin >> S;
    if(S.size() & 1)return 0 & puts("No");
    for(unsigned long i{0}; i < S.size(); ++i)if((S[i] ^ (i & 1)) != 'h')return 0 & puts("No");
    puts("Yes");
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
//#include <math.h>
//#include <algorithm>
#include <vector>

#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))

using namespace std;

int main(int argc, char* argv[])
{
    long n, ww;
    scanf("%ld %ld", &n, &ww);

    vector<long> w(n);
    vector<long> v(n);

    long MAXJ = 0;
    long i, j;
    for(i=0; i<n; i++) {
        scanf("%ld %ld", &(w[i]), &(v[i]));
        MAXJ += v[i];
    }

    vector<vector<long long> > aa(n+1, vector<long long>(MAXJ+1, 0));

    aa[n][0]=0;
    for(j=1; j<=MAXJ; j++) {
        aa[n][j]=-1;
    }
    for(i=n-1; i>=0; i--) {
        for(j=1; j<=MAXJ; j++) {
            aa[i][j] = aa[i+1][j];
            if(j>=v[i] && aa[i+1][j-v[i]]>=0) {
                long long tmp = aa[i+1][j-v[i]]+w[i];
                aa[i][j] = (aa[i][j]<0? tmp: MIN(aa[i][j], tmp));
            }
        }
    }

    long long ans = 0;
    for(j=0; j<=MAXJ; j++) {
        if(aa[0][j]>=0 && aa[0][j]<=ww) {
            ans = j;
        }
    }

    printf("%lld\n", ans);

    return 0;
}


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

int main(){
	string tmp;
	cin >> tmp;
	int N = tmp.size();
	int x[N+5];
	for(int i=1;i<=N;i++) x[i] = (int)(tmp[i-1]-'0');
	int kiri = 1,kanan = N;
	set<int> st1,st2;
	for(int i=1;i<=N;i++){
		if(x[i] == 0) st1.insert(i);
		else st2.insert(i);
	}
	while(kiri <= kanan){
		int piv = (kiri + kanan) >> 1;
		bool ok = 0;
		int y[N+5];
		for(int i=1;i<=N;i++) y[i] = x[i];
		
		int pref[2*N+5];
		memset(pref,0,sizeof pref);
		int cnt = 0;
		for(int i=1;i<=N;i++){
			cnt += pref[i];
			cnt %=2;
			y[i] += cnt;
			y[i] %= 2;
			//cout << x[i] << " " << i << " " <<  piv << " " << i + piv << "\n";
			if(i + piv <= N+1) 
			if(!y[i]){
				pref[i+piv] = 1;
				cnt++;
				y[i] = 1;
			} 
		}
		int zz = 0;
		for(int i=1;i<=N;i++) if(y[i] == 0) {
			zz = i-1;
			break;
		}
	//	cout << zz << "\n";
		if(zz == 0 || zz >= piv) {
			kiri = piv+1;
		} 
		else kanan = piv-1;
	}
	cout << kiri-1 << "\n";
}


Measured memory_bytes: 6656
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i,s,n) for(int i = (s); i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
int main(){
   int n;
   cin >> n;
   vector<string> v;
   rep(i, n) { 
       string s;
       cin >> s;
       v.push_back(s);
   }
   sort(v.begin(), v.end());

   int count = 0;
   int max = 0;
   vector<pair<string, int>> d;
   rep(i, n-1) {
       if(v[i] == v[i + 1]) {
           count++;
       } else {
           count++;
           d.push_back(make_pair(v[i], count));
           if(count>max)
               max = count;
           count = 0;
       }
       if(i == n - 2){
           if(v[i]==v[i+1]){
               count++;
               d.push_back(make_pair(v[i], count));
               if(count > max)
                   max = count;
           } else {
               d.push_back(make_pair(v[i], count));
               if(count > max)
                   max = count;
               d.push_back(make_pair(v[i+1], 1));
           }
       }
   }
   rep(i, d.size()) {
       if(d[i].second == max)
           cout << d[i].first << endl;
    }
   return 0;
}

Measured memory_bytes: 18800
#include <iostream>
inline int gcd(int a, int b){int c; while( a != 0 ) c=a,a=b%a,b=c;return b;}
int A, B, C;
int main(void){
    std::cin >> A >> B >> C;
    std::cout << ( !(C%gcd(A,B)) ? "YES" : "NO" ) << std::endl;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;
using static System.Console;
using static System.Math;


namespace AtCodeeeer
{
    class AtCOOOOOOOOOOOder
    {
        static void Main(string[] args)
        {
            int[] s = ReadLine().Split(' ').Select(int.Parse).ToArray();
            int n = s[0];
            int m = s[1];

            var ls = new List<int>();

            for (int i = 0; i < n; i++)
            {
                ls.Add(0);
            }

            for (int i = 0; i < m; i++)
            {
                int[] input = ReadLine().Split(' ').Select(int.Parse).ToArray();
                int a = input[0];
                int b = input[1];
                ls[a-1] = ls[a-1] + 1;
                ls[b-1] = ls[b-1] + 1;
            }

            for (int i = 0; i < n; i++)
            {
                WriteLine(ls[i]);
            }
        }
    }
}


Measured memory_bytes: 13396
#include <bits/stdc++.h>
#define REP(i, e) for(int (i) = 0; (i) < (e); ++(i))
#define FOR(i, b, e) for(int (i) = (b); (i) < (e); ++(i))
#define ALL(c) (c).begin(), (c).end()
#define PRINT(x) cout << (x) << "\n"
using namespace std;
using ll = long long; using pint = pair<int, int>; using pll = pair<ll, ll>;
const long long MOD = 1000000007;

ll N, K;
ll num[100001];
map<ll, ll> powN;

ll powll(ll x){
    vector<ll> v;
    v.push_back(x);
    for(ll i = 1; (1 << i) <= N; i++){
        v.push_back(v[i - 1] * v[i - 1] % MOD);
    }
    ll ret = 1;
    for(ll i = 0; (1 << i) <= N; i++){
        if((1 << i) & N) ret = ret * v[i] % MOD;
    }
    return ret;
}

signed main(){
    cin >> N >> K;
    ll ans = 0;
    for(ll i = K; i >= 1; i--){
        num[i] = powll(K / i);
        for(ll j = 2; i * j <= K; j++) num[i] = (num[i] + MOD - num[i * j]) % MOD;
        ans = (ans + i * num[i] % MOD) % MOD;
    }
    PRINT(ans);
    return 0;
}

Measured memory_bytes: 4396
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30

def main():
    h = int(input().strip())
    w = int(input().strip())
    n = int(input().strip())
    print((n + max(h, w) - 1) // max(h, w))

if __name__ == '__main__':
    main()


Measured memory_bytes: 38384
N=int(input())
S,T=input().split()
S_list=[c  for c in S]
T_list=[c  for c in T]

answer_list=[]
mojiretu=""
for i in range(N):
    answer_list.append(S_list[i])
    answer_list.append(T_list[i])
for x in answer_list:
    mojiretu += x
    
print(mojiretu)

Measured memory_bytes: 3064
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip> 
#include <complex> 
#include <string>
#include <vector> 
#include <list>
#include <deque> 
#include <stack> 
#include <queue> 
#include <set>
#include <map>
#include <bitset>
#include <functional>
#include <utility>
#include <algorithm> 
#include <numeric> 
#include <typeinfo> 
#include <cstdio>
#include <cstdlib> 
#include <cstring>
#include <cmath>
#include <climits> 
#include <ctime>

using namespace std;
char maps[12][12]; 

void saiki(int y,int x){ 
	if(maps[y][x]!='0'){      
		maps[y][x]='0';        
		if(y+1<12)saiki(y+1,x); 
		if(y-1>=0)saiki(y-1,x);   
		if(x+1<12)saiki(y,x+1);     
		if(x-1>=0)saiki(y,x-1);   
	}     return; 
}        
int main(){   
	while(1){  
		int ret = 0;   
		for(int i=0;i<12;i++)for(int j=0;j<12;j++)if(!(cin >> maps[i][j]))return 0;  
		for(int i=0;i<12;i++)for(int j=0;j<12;j++)if(maps[i][j]=='1'){     
			ret++;             
			saiki(i,j);    
		}   
		cout << ret << endl;    
	}
	return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <string.h>
#include <cstdio>
#include <tuple>
#include <numeric>
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define CST(x) cout<<fixed<<setprecision(x)//小数点以下の桁数指定
#define ct(a) cout<<a<<endl
static const double pi = 3.141592653589793;
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll INF = 1e9 + 7;
const ll mod = 1e9 + 7;


ll N, ans = 1;
ll A[200001], B[200001];
map<pair<ll,ll>, ll> mp1;
map<pair<ll,ll>, ll> mp2;


ll mod_pow(ll x, ll n) {
	if (n == 0) return 1;
	ll res = mod_pow(x*x % mod, n / 2);
	if (n & 1) res = res * x % mod;
	return (res + mod) % mod;
}

ll Gcd(ll x, ll y) {
	if (y > x) swap(x, y);
	while (x%y != 0) {
		ll m = x % y;
		x = y;
		y = m;
	}
	return y;
}

ll cnt;
ll mz, az;

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


	cin >> N;
	FOR(i, 0, N) {
		ll a, b;
		cin >> a >> b;

		

		
		if (a == 0 && b == 0)cnt++;
		else if (a == 0)mz++;
		else if (b == 0)az++;
		else {
			ll m = Gcd(a, b);
			a /= m; b /= m;
			A[i] = a; B[i] = b;
			mp1[make_pair(a,b)]++;
			mp2[make_pair(b,a)]++;
		}
	}
	FOR(i, 0, N) {
		ll a, b;
		a = A[i]; b = B[i];

		if (a == 0 || b == 0)continue;


		if (mp1[make_pair(a,b)] > 0) {


			ans = (ans * ((mod_pow(2, mp1[make_pair(a,b)]+mp1[make_pair(-a,-b)]) + mod_pow(2, mp2[make_pair(-a,b)]+mp2[make_pair(a,-b)])) % mod - 1) + mod) % mod;
			mp1[make_pair(a,b)] = -1;
			mp1[make_pair(-a, -b)] = -1;
			mp1[make_pair(-b,a)] = -1;
			mp1[make_pair(b, -a)] = -1;
		}

	}
	ans = (ans*((mod_pow(2, mz) + mod_pow(2, az)) % mod - 1) + mod) % mod;

	cout << (ans - 1 + cnt + 100 * mod) % mod << endl;


	return 0;
}

Measured memory_bytes: 94108
#include<stdio.h>
int main(){
    int n,k,i;
    scanf("%d%d",&n,&k);
    int h[n],ans=0;
    for(i=0;i<n;i++){
        scanf("%d",&h[i]);
        if(h[i]>=k)
            ans++;
    }
    printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 512
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		//
		int height = 0;
		int width = 0;

		// 表の縦、横を決める入力値を持ってくる
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			height = sc.nextInt();
			width = sc.nextInt();
			break;
		}

		// シートのインスタンスを作る
		excel ex = new excel();

		// 入力値から表を作る
		ex.setSheet(height, width);

		// 表に入力する値を持ってくる
		while (sc.hasNext()) {

			// 入力された値を表のそれぞれの場所に入れる
			for (int i = 0; i < height; i++) {
				for (int s = 0; s < width; s++) {
					int input_number = sc.nextInt();
					ex.setSell(input_number, i, s);
				}
			}
			break;
		}
		// 表の最後の列に行の計算結果を挿入
		ex.sum_row();
		// 表の最後の行に列の計算結果を挿入
		ex.sum_column();

		// 表全体を出力
		ex.out_sheet();

	}
}

class excel {

	// フィールド
	int[][] sheet;

	// 入力値から表(2次元配列)を作るメソッド
	public void setSheet(int height, int width) {

		// 最後に合計値を出す列を用意
		sheet = new int[height + 1][width + 1];
	}

	// 入力値をセルに入れる
	public void setSell(int input_number, int height, int width) {
		sheet[height][width] = input_number;
	}

	// 行の合計値を最後のセルに追加
	public void sum_row() {
		// 行の数だけ回す
		for (int i = 0; i < sheet.length; i++) {

			// 列の数だけ回す
			int sum = 0;
			for (int s = 0; s < sheet[0].length; s++) {

				// 行の合計値
				sum = sheet[i][s] + sum;
			}
			// 最後に追加
			sheet[i][(sheet[0].length - 1)] = sum;
		}
	}

	// 列の合計値を最後のセルに追加
	public void sum_column() {
		// 列の数だけ回す
		for (int c = 0; c < sheet[0].length; c++) {

			// 行の数だけ回す
			int sum = 0;
			for (int s = 0; s < sheet.length; s++) {

				// 行の合計値
				sum = sheet[s][c] + sum;
			}
			// 最後に追加
			sheet[sheet.length - 1][c] = sum;
		}
	}

	// 表全体を出力
	public void out_sheet() {

		// 行の回数
		for (int i = 0; i < sheet.length; i++) {

			// 列の回数
			for (int s = 0; s < sheet[0].length - 1; s++) {
				// 空白を一つ空けて表示
				System.out.print(sheet[i][s] + " ");
			}
			// 最後の行を改行
			System.out.println(sheet[i][(sheet[0].length - 1)]);
		}
	}
}

Measured memory_bytes: 39572
n,m = map(int,input().split())
A = []
B = []
for i in range(n):
    a,b = map(int,input().split())
    A.append([a,b])
for i in range(m):
    c,d = map(int,input().split())
    B.append([c,d])
for i in range(n):
    d = []
    for j in range(m):
        d.append(abs(A[i][0]-B[j][0])+abs(A[i][1]-B[j][1]))
    print(d.index(min(d))+1)

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

ll solve(vector<int>arr,int i,int a,int b,int c,ll sa,ll sb,ll sc)
{
	if(i==arr.size())
	{
		if(!sa||!sb||!sc)
			return INT_MAX;
		return abs(a-sa)+abs(b-sb)+abs(c-sc);
	}

	ll op1=solve(arr,i+1,a,b,c,sa,sb,sc);
	ll op2=solve(arr,i+1,a,b,c,sa+arr[i],sb,sc)+(sa?10:0);
	ll op3=solve(arr,i+1,a,b,c,sa,sb+arr[i],sc)+(sb?10:0);
	ll op4=solve(arr,i+1,a,b,c,sa,sb,sc+arr[i])+(sc?10:0);
	return min(op1,min(op2,min(op3,op4)));
}

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

	vector<int>arr(n);
	for(int i=0;i<n;i++)
		cin>>arr[i];
    cout<<solve(arr,0,a,b,c,0,0,0);
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,ans=0;
	string s;
	cin>>n>>s;
	for(int i=0;i<n;i++){
		if(s[i]!=s[i+1])
		    ans++;
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 512
use std::io::stdin;
use std::time::SystemTime;

#[allow(dead_code)]
fn read_line() -> String {
    let mut s = String::new();
    stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

#[allow(dead_code)]
fn read<T>() -> T
where T: std::str::FromStr
{
    read_line().parse::<T>().ok().unwrap()
}

#[allow(dead_code)]
fn read_vec<T>() -> Vec<T>
where T: std::str::FromStr
{
    read_line().split(" ").map(|n| n.parse::<T>().ok().unwrap()).collect()
}

#[allow(dead_code)]
fn read_chars() -> Vec<char>
{
    read_line().chars().collect()
}

#[allow(dead_code)]
fn print_time() -> () {
    println!("{:?}", SystemTime::now());
}

trait BinarySearchLeft<T> {
    fn binary_search_left(&self, x: &T) -> Result<usize, usize>;
}

impl<T> BinarySearchLeft<T> for Vec<T>
where T: std::cmp::Ord + std::fmt::Debug
{
    fn binary_search_left(&self, x: &T) -> Result<usize, usize> {
        let index = self.binary_search(x);
        match index {
            Ok(index) => {
                for i in (1..index+1).rev() {
                    if self[i] != self[i - 1] {
                        return Ok(i - 1)
                    }
                }
                
                Ok(index)
            },
            _ => index,
        }
    }
}

#[allow(unused_variables)]
fn main() {
    let NQ: Vec<usize> = read_vec();
    let mut A: Vec<Vec<usize>> = vec![];
    let mut B: Vec<Vec<usize>> = vec![];
    for _ in 0..NQ[0]-1 {
        A.push(read_vec());
    }

    for _ in 0..NQ[1] {
        B.push(read_vec());
    }

    B.sort();

    let mut d: Vec<Vec<usize>> = vec![Vec::new(); NQ[0]];
    for v in A {
        d[v[0] - 1].push(v[1] - 1);
    }

    let mut score: Vec<usize> = vec![0; NQ[0]];
    for v in B {
        score[v[0] - 1] += v[1];
    }

    let mut ans: Vec<usize> = vec![0; NQ[0]];

    dfs(&d, &score, 0, 0, &mut ans);

    println!("{}", ans.iter().map(|n| format!("{}", n)).collect::<Vec<_>>().join(" "));
}

fn dfs(d: &Vec<Vec<usize>>, score: &Vec<usize>, i: usize, c: usize, ans : &mut Vec<usize>) {
    ans[i] = c + score[i];
    for v in &d[i] {
        dfs(d, score, *v, c + score[i], ans);
    }
}

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

#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL);
#define ll long long
#define vi vector< int > 
#define pii pair< int, int >
#define mii map< int , int > 
#define F(start,stop) for(int i=start; i<stop; i++)
#define FRev(start,stop) for(int i=start; i>=stop; i--)
#define MOD1 1000000007
#define MOD2 998244353

int main()
{

	#ifndef ONLINE_JUDGE
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif

	IOS

	char c;
	cin >> c;

	if(c >= 'A' && c <= 'Z')
		cout << 'A' << endl;
	else
		cout << 'a' << endl;
}

Measured memory_bytes: 3596
/*
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
*/
#include <bits/stdc++.h>

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

int main()
{
  string s;
  cin >> s;
  for(int i=0; i < s.length(); i++){
    s[i] = 'x';
  }
  cout << s;
  return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        HashSet<String> hashSet = new HashSet<>();
        for (int i = 0; i < n; i++) {
            String sp = bf.readLine();
            if (sp.charAt(0)=='i'){
                hashSet.add(sp.substring(7));
            }else {
                System.out.println(hashSet.contains(sp.substring(5))?"yes":"no");
            }
        }
    }
}


Measured memory_bytes: 121120
from math import sqrt
N, D = map(int,input().split())
X = []
for i in range(N):
  X.append(list(map(int,input().split())))
ans = 0  
for i in range(N):
  for j in range(i, N):
    length = 0
    for k in range(D):
      length += (X[j][k] - X[i][k]) ** 2
    if int(sqrt(length)) ** 2 == length: ans += 1
print(ans - N)      

Measured memory_bytes: 38512
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <unordered_map>
#include <vector>

using namespace std;

typedef long long lint;

const int maxn = 100;

vector<int> adj[maxn];
int parent[maxn], dist[maxn];

pair<int, int> dfs(int v, int p, int d) {
  pair<int, int> result{0, v};
  parent[v] = p;
  dist[v] = d;
  for (int u : adj[v])
    if (u != p) {
      pair<int, int> res = dfs(u, v, d + 1);
      ++res.first;
      result = max(result, res);
    }
  return result;
}

const int base = 999983, mod = 1013095777;

pair<lint, lint> solve(int n, bool center_edge) {
  lint result_a = 0, result_b = center_edge ? 2 : 1;

  vector<pair<int, int>> dist_and_node(n);
  for (int i = 0; i < n; ++i)
    dist_and_node[i] = make_pair(dist[i], i);
  sort(dist_and_node.begin(), dist_and_node.end(), greater<pair<int, int>>());
  for (int j = 0, i = j; i < n; i = j) {
    while (j < n && dist_and_node[j].first == dist_and_node[i].first) ++j;

    ++result_a;

    int max_children_count = 0;
    for (int k = i; k < j; ++k) {
      int v = dist_and_node[k].second;
      int children_count = 0;
      for (int u : adj[v])
        if (dist[u] > dist[v])
          ++children_count;
      max_children_count = max(max_children_count, children_count);
    }

    if (max_children_count > 1) {
      if (max_children_count > LLONG_MAX / result_b)
        result_b = LLONG_MAX;
      else
        result_b *= max_children_count;
    }
  }

  return {result_a, result_b};
}

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n - 1; ++i) {
    int a, b;
    scanf("%d %d", &a, &b), --a, --b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  int diam_a;
  tie(ignore, diam_a) = dfs(0, -1, 0);
  int diam, diam_b;
  tie(diam, diam_b) = dfs(diam_a, -1, 0);
  pair<lint, lint> result;
  if (diam % 2 == 0) {
    int center = diam_b;
    for (int rep = 0; rep < diam / 2; ++rep)
      center = parent[center];
    dfs(center, -1, 0);
    result = solve(n, false);
    for (int u : adj[center]) {
      dfs(u, center, 0);
      dfs(center, u, 0);
      result = min(result, solve(n, true));
    }
  } else {
    int center_b = diam_b;
    for (int rep = 0; rep < (diam - 1) / 2; ++rep)
      center_b = parent[center_b];
    int center_a = parent[center_b];
    dfs(center_a, center_b, 0);
    dfs(center_b, center_a, 0);
    result = solve(n, true);
  }
  printf("%lld %lld\n", result.first, result.second);
  return 0;
}


Measured memory_bytes: 256
var
 x,y,z,s,sum:longint;
begin
 readln(x,y,z);
 s:=x-z;
 while s-z>0 do
  begin
   if s-y-z<0 then break
    else s:=s-y-z;
   inc(sum);
  end;
 writeln(sum);
end.

Measured memory_bytes: 128
#include<iostream>
#include<string>
#include<vector>
#include<utility>
#include<algorithm>
#include<map>
#include<cstdlib>
#include<cmath>
#include<numeric>
#include<iomanip>
using namespace std;
using ll =long long;
const int MOD = 1000000007;

//////検証する数,超えられない数////
/*
long long cine(long long a, long long b) {
	if (a <= b) {
		return a;
	}
	else {
		return b;
	}
};*/
//vector型の初期化
/*
void vec_initialize(vector<ll>& a, const ll N) {
	ll c;

	for (int i = 0; i < N; i++) {

		cin >> c;
		a.push_back(c);

	}

};
void vec_pair_initialize(vector<pair<ll, ll>>& a, const ll N) {
	ll c, d;
	for (int i = 0; i < N; i++) {
		cin >> c >> d;
		a.push_back(make_pair(c, d));
	}
};
*/
int main() {
	ll N, C;
	vector<ll>s, t, c;
	cin >> N >> C;
	ll x,y,z;
	map<ll, ll>chanel;
	for (ll i = 0; i < N; i++) {
		cin >> x>>y>>z;
		s.push_back(2*x-1);
		t.push_back(2*y);
		c.push_back(z);
	}
	
	map<ll,ll>tmpc;
	
	for (ll i = 1; i <=C; i++) {
		vector<ll> tmps;
		vector<ll> tmpt;
		
		for (ll j = 0; j < N; j++) {
			if (c[j] == i) {
				tmps.push_back(s[j]);
				tmpt.push_back(t[j]);
				
				tmpc[i-1]++;
			}
		}
		sort(tmps.begin(), tmps.end());
		sort(tmpt.begin(), tmpt.end());
		for (ll j = 0; j < tmpc[i - 1]; j++) {
			if (j+1!=tmpc[i-1]&&tmps[j+1] < tmpt[j]) {
				tmps[j + 1] += 2;
			}
		}
		for (ll j = 0; j < tmpc[i - 1]; j++) {
			for (ll k = tmps[j]; k <= tmpt[j]; k++) {

				chanel[k]++;

			}
		}


	}
	ll big=0;
	for (auto i : chanel) {
		if (i.second > big) {

			big = i.second;
		}

	}

	cout <<big;


}

Measured memory_bytes: 16648
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    A,B,N=map(int,input().split())
    f=lambda x:(A*x)//B-A*(x//B)
    print(f(min(B-1,N)))
    

if __name__ == '__main__':
    main()


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

using namespace std;

#define SZ(x) (int)(x.size())

using ll = long long;
using ld = long double;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const double eps = 1e-10;
const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<50;

template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);

  int a, b; cin >> a >> b;
  int ans = a-1;
  if(a <= b) ans++;
  cout << ans << endl;
}


Measured memory_bytes: 256
import scala.math.min

object Main {
    def main(args: Array[String]) {
        var input = io.Source.stdin.getLines().mkString("\n");
        var xs = input.split("\n").toList;
        var ys = xs(0).split(" ").map(_.toInt).toList;
        val n = ys(0);
        val a = ys(1);
        val b = ys(2);
        val res = min(b, n * a);
        println(res);
    }
}


Measured memory_bytes: 25544
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define yesno(flg) if(flg){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define MAX_N 1002
#define i197 1000000007

using namespace std;

typedef long long ll;
typedef pair<ll,ll> P1;
typedef pair<int,int> Pi;
typedef pair<double,Pi> Pdi;
typedef pair<ll,int>Pli;
typedef pair<P1,ll> P2;
const ll INF=1000000000000000001;
struct edge{int to,cost;};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
struct Road{double cost;int a,b;};

ll a[100001],b[100001];
ll x=0,y[100001]={};
int main() {

	int n;
	int total=0;
	int d=0;
	ll y2=0;

	cin>>n;

	rep(i,n){
		cin>>a[i];
	}
	rep(i,n){
		cin>>b[i];
		if(b[i]>a[i]){
			x+=b[i]-a[i];
			total++;
		}else{
			y[d+1]=a[i]-b[i];
			y2+=y[d+1];
			d++;
		}
	}
	if(x==0){
		cout<<"0"<<endl;
		return 0;
	}
	if(x>y2){
		cout<<"-1"<<endl;
		return 0;
	}
	sort(y,y+d+1);
	ll r=0;
	for(int j=d; j>=1; j--){
		if(r+y[j]>=x){
			cout<<total+1<<endl;
			return 0;
		}else{
			r+=y[j];
			total++;
		}
	}

	return 0;
}


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


int main() {
  string S;
  cin >> S;
  bool flag = true;
  for (int i = 1; i < S.size(); i += 2) {
    if (S[i] != 'L' && S[i] != 'U' && S[i] != 'D') flag = false;
  }
  for (int i = 0; i < S.size(); i += 2) {
    if (S[i] != 'R' && S[i] != 'U' && S[i] != 'D') flag = false;
  }
  if (flag) cout << "Yes" << endl;
  else cout << "No" << endl;
}


Measured memory_bytes: 256
fn read_stdin() -> String {
    use std::io::Read;
    let mut input = String::new();
    std::io::stdin().read_to_string(&mut input).unwrap();
    input
}

fn scan<'a, I: Iterator<Item = &'a str>, T: std::str::FromStr>(tokens: &mut I) -> T {
    tokens.next().unwrap().parse().ok().unwrap()
}

const MODULO: usize = 1_000_000_007;

fn main() {
    let input = read_stdin();
    let tokens = &mut input.split_whitespace();
    let l: usize = scan(tokens);
    let r: usize = scan(tokens);
    println!("{}", f(l, r));
}

fn f(l: usize, r: usize) -> usize {
    // #{ (x, y) | l <= x <= y <= r, p(x, y) }
    if l == r {
        1
    } else if l % 2 == 1 {
        (g(l, r) + f(l + 1, r)) % MODULO
    } else if r % 2 == 0 {
        (f(l, r - 1) + h(l, r)) % MODULO
    } else {
        3 * f(l / 2, r / 2) % MODULO
    }
}

fn g(l: usize, r: usize) -> usize {
    // #{ y | l <= y <= r, p(l, y) }
    if l == r {
        1
    } else if r % 2 == 0 {
        (g(l, r - 1) + p(l, r)) % MODULO
    } else if l == 1 {
        1
    } else if l % 2 == 1 {
        g(l / 2, r / 2)
    } else {
        2 * g(l / 2, r / 2) % MODULO
    }
}

fn h(l: usize, r: usize) -> usize {
    // #{ x | l <= x <= r, p(x, r) }
    if l == r {
        1
    } else if l % 2 == 1 {
        (p(l, r) + h(l + 1, r)) % MODULO
    } else if r % 2 == 0 {
        h(l / 2, r / 2)
    } else {
        2 * h(l / 2, r / 2) % MODULO
    }
}

fn p(x: usize, y: usize) -> usize {
    if y % x == y ^ x {
        1
    } else {
        0
    }
}


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

using namespace std;

typedef long long ll;

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

	int n;
	cin >> n;

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

	int sm = 0;
	rep(i, n) sm += a[i];

	int mn = INT_MAX / 10;
	int mi = -1;
	rep(i, n){
		int val = abs(a[i] * n - sm);
		if(val < mn){
			mn = val;
			mi = i;
		}
	}

	cout << mi << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
const long long MOD = 1e9 + 7;
using namespace std;
typedef long long ll;

map<ll, int> mp;
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	int ans = 0;
	for (int i = 0; i < n; i++) {
		ans++;
		while (i + 1 < n && a[i] == a[i + 1]) i++;
		if (i == n - 1) break;
		if (a[i] < a[i + 1]) {
			while (i + 1 < n && a[i] <= a[i + 1]) i++;
		}
		else {
			while (i + 1 < n && a[i] >= a[i + 1]) i++;

		}
	}
	cout << ans << endl;
	return 0;
}

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


int main()
{
	int n; cin >> n;
	string s; cin >> s;
	int c = 0;
	for (int i = 0; i < n; ++i)
		if (s.substr(i, 3) == "ABC")
			c++, i+=2;
	cout << c << endl;
}


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

int main(void)
{
    string S, a;
    cin >> S;
    int i;
    int ans, temp, like = 753;
    for(i=0;i<S.length()-2;i++){
        a = S.substr(i,3);
        temp = atoi(a.c_str());
        if(i==0){ans = abs(temp-like);}
        //printf("%d\n",temp);
        if(ans > abs(temp-like)) ans = abs(temp-like);
        //printf("%d\n",ans);
    }
    printf("%d\n", ans);
}

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

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

    int a, b;
    cin >> a >> b;

    int ans = 0;
    if(a >= 13) ans = b;
    else if(a >= 6) ans = b / 2;
    
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void){
  int input = 0;
  int hh,mm,ss = 0;

  scanf("%d", &input);

  hh = input/3600;
  mm = input%3600/60;
  ss = input - hh*3600-mm*60;

  printf("%d:%d:%d\n", hh, mm, ss);

  return 0;
}

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

#define DEBUG(x) cerr << #x << ": " << x << endl;
#define ll long long

int main() {
    int n;
    cin >> n;
    vector<ll> v(n);
    for (ll& x : v) {
        cin >> x;
    }
    vector<ll> r1 = v;
    for (ll i = 1; i < n; i++) {
        r1[i] = r1[i-1] + r1[i];
    }
    vector<ll> r2 = v;
    for (ll i = n-2; i >= 0; i--) {
        r2[i] = r2[i+1] + r2[i];
    }

    ll Min = abs(r1[0] - r2[1]);
    for (int i = 0; i < n-1; i++) {
        Min = min(Min, abs(r1[i] - r2[i+1]));
    }

    cout << Min << endl;

    return 0;
}

Measured memory_bytes: 4992
#include <cstdio>
#include <iostream>
#include <string>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;

int main()
{
	string s, ans;
	cin >> s;
	for (int i = 0; i < s.size(); i++) {
		if (s.at(i) == '0') ans += '0';
		if (s.at(i) == '1') ans += '1';
		if (s.at(i) == 'B' && ans.size() >= 1) ans = ans.substr(0, ans.size() - 1);
	}
	cout << ans << endl;
}

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

#define INF 1.1e9
#define LINF 1.1e18
#define FOR(i,a,b) for (long long i = (a); i < (b); ++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(), (v).end()
#define pb push_back
#define fi first
#define se second

typedef long long ll;
typedef pair<int, int> P;
typedef pair<int, P> PP;

int n,k;
set<string> st;
string s[10];
bool used[10];

void dfs(int depth,string num) {
	if(depth==0) {
		st.insert(num);
		return;
	}
	REP(i,n) {
		if(used[i]) continue;
		used[i]=true;
		dfs(depth-1,num+s[i]);
		used[i]=false;
	}
}

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

    while(true) { 
	cin>>n>>k;
	if(n==0&&k==0) break;
	st.clear();
	REP(i,n) {
		cin>>s[i];
	}
	REP(i,n) {
		REP(i,10) used[i]=false;
		used[i]=true;
		dfs(k-1,s[i]);
	}

	cout<<st.size()<<endl;
    }

	return 0;
}



Measured memory_bytes: 3368
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.List;
import java.util.Scanner;
import java.util.Collections;
import java.util.ArrayList;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Tenka1_2018_C solver = new Tenka1_2018_C();
        solver.solve(1, in, out);
        out.close();
    }

    static class Tenka1_2018_C {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int n = in.nextInt();
            List<Integer> list = new ArrayList<Integer>();
            List<Integer> maxlist = new ArrayList<Integer>();
            long ans = 0;
            for (int i = 0; i < n; i++) {
                list.add(in.nextInt());
            }
            Collections.sort(list);

            maxlist.add(list.get(0));
            maxlist.add(list.get(list.size() - 1));
            list.remove(0);
            list.remove(list.size() - 1);


            while (list.size() > 0) {
                if (list.size() < 2) break;
                maxlist.add(0, list.get(list.size() - 1));
                list.remove(list.size() - 1);

                maxlist.add(list.get(0));
                list.remove(0);

                if (list.size() < 2) break;
                maxlist.add(list.get(list.size() - 1));
                list.remove(list.size() - 1);

                maxlist.add(0, list.get(0));
                list.remove(0);

            }

            if (list.size() == 1) {
                int last = list.get(0);

                if (Math.abs(last - maxlist.get(0)) > Math.abs(last - maxlist.get(maxlist.size() - 1))) {
                    maxlist.add(0, list.get(0));
                } else {
                    maxlist.add(list.get(0));
                }
            }

            for (int i = 0; i < maxlist.size() - 1; i++) {
                ans += Math.abs(maxlist.get(i) - maxlist.get(i + 1));
            }

            out.print(ans);
        }

    }
}



Measured memory_bytes: 63020
# frozen_string_literal: true

n, m, x = gets.split.map(&:to_i)
ca = n.times.map { gets.split.map(&:to_i) }
INFTY = 10**12
min = INFTY
(1..(2**n - 1)).each do |b|
  sum = 0
  d = Array.new(m) { 0 }
  ca.each_with_index do |e, i|
    next if b[i].zero?

    c = e[0]
    as = e[1..-1]
    as.each_with_index do |f, j|
      d[j] += f
    end
    sum += c
  end
  min = sum if sum < min && d.all? { |e| e >= x }
end

if min < INFTY
  puts min
else
  puts '-1'
end


Measured memory_bytes: 14364
'use strict';
const p = s => console.log(s);
// let a,b,c,d;
// [a,b,c,d] = input[0].trim().split(" ").map(i => parseInt(i));

function main(input) {
  let N = input[0].trim().split(" ")[0];
  let K = input[0].trim().split(" ")[1];
  let A = [];
  let B = [];
  let sum = 0;
  let map = {};

  for(let i =1; i < 2 * K; i+=2) {
    A.push(input[i + 1].trim().split(" "));
  }


  for(let i =0; i < A.length; i++) {
    for(let j =0; j< A[i].length; j++) {
      map[A[i][j]] = 1;
    }
  }
  p(N - Object.keys(map).length);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8').trim().split("\n"));


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

int main(){
  int n, l, r, A[100], j;


  while(1){
    int count = 0;
    cin>>n>>l>>r;

    if(n == 0 && l == 0 && r ==0) break;

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

    for(int i = l; i <= r; i++){//cout<<i<<endl;
      int f = 0;
      for(j = 1; j <= n; j++){
        if(i%A[j] == 0){
          if(j%2 == 1){
            f = 1;
          } else {
            f = 0;
          }
          break;
          }
      }
      if(j == n+1){
        if(n%2 == 0) f = 1;
        else  f = 0;
      }
      if(f == 1) count++;

    }

    cout<<count<<endl;
  }


  return 0;
}



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

int main()
{
    int n, q, t, a, x;
    cin >> n >> q;

    stack<int> s[n];

    while (q--)
    {
        cin >> t;
        if (t == 0)
        {
            cin >> a >> x;
            s[a].push(x);
        }
        if (t == 1)
        {
            cin >> a;
            if (s[a].size() != 0)
                cout << s[a].top() << endl;
        }
        if (t == 2)
        {
            cin >> a;
            if (s[a].size() != 0)
                s[a].pop();
        }
    }
}



Measured memory_bytes: 4300
using System;
using System.Collections.Generic;
using System.Text;

class TEST{
	static void Main(){
		while(true){
			var d=Array.ConvertAll(Console.ReadLine().Split(' '),elem=>int.Parse(elem));
			if(d[0]==0 && d[1]==0)break;
			Sol mySol=new Sol(d);
			Console.WriteLine(mySol.Ans);
		}
	}
}


class Mark{
	public uint state;
	public uint route;
	public int rem(){
		uint i=state;
		
		i=(i&0x55555555)+((i>>1)&0x55555555);
		i=(i&0x33333333)+((i>>2)&0x33333333);
		i=(i&0x0F0F0F0F)+((i>>4)&0x0F0F0F0F);
		i=(i&0x00FF00FF)+((i>>8)&0x00FF00FF);
		i=(i&0x0000FFFF)+((i>>16)&0x0000FFFF);
		
		return (int)i;
		
	}
	public int depth(){
		uint i=route;
		
		i=(i&0x55555555)+((i>>1)&0x55555555);
		i=(i&0x33333333)+((i>>2)&0x33333333);
		i=(i&0x0F0F0F0F)+((i>>4)&0x0F0F0F0F);
		i=(i&0x00FF00FF)+((i>>8)&0x00FF00FF);
		i=(i&0x0000FFFF)+((i>>16)&0x0000FFFF);
		
		return (int)i;
	}
}


class Sol{
	int ans;
	public int Ans{
		get{return ans;}
	}
	int n;
	int e;
	bool[,] ARR_ADJ;
	public Sol(int[] d){
		n=d[0];
		e=d[1];
		ARR_ADJ=new bool[n,n];
		for(int i=0;i<n;i++)for(int j=0;j<n;j++)ARR_ADJ[i,j]=false;
		for(int i=0;i<n;i++)ARR_ADJ[i,i]=true;
		
		for(int i=0;i<e;i++){
			var arr=Array.ConvertAll(Console.ReadLine().Split(' '),elem=>int.Parse(elem));
			ARR_ADJ[arr[0],arr[1]]=ARR_ADJ[arr[1],arr[0]]=true;
		}
		Mark INI=new Mark();
		INI.route=0;
		INI.state=0;
		for(int i=0;i<n;i++)INI.state=INI.state|(uint)(0x1<<i);


		Mark[] Put=new Mark[n];
		for(int i=0;i<n;i++){
			Put[i]=new Mark();
			Put[i].state=INI.state;
			Put[i].route=INI.route;
			Put[i].route=Put[i].route|(uint)(0x1<<i);
			for(int j=0;j<n;j++){
				if(ARR_ADJ[i,j])Put[i].state=Put[i].state&~(uint)(0x1<<j);
			}
		}
		ans=0;
		for(int i=0;i<n;i++)if(Put[i].state==0){ans=1;return;}

		Dictionary<uint,Mark>[] DP =new Dictionary<uint,Mark>[n];
		Mark K=new Mark();K.state=INI.state;K.route=INI.route;
		DP[0]=new Dictionary<uint,Mark>();
		DP[0].Add(K.state,K);
		for(int dd=0;dd<n;dd++){
			DP[dd+1]=new Dictionary<uint,Mark>();
			foreach(KeyValuePair<uint,Mark> kvp in DP[dd]){
				for(int k=0;k<n;k++){
					Mark M=Sum(kvp.Value,Put[k]);
					if(M.state==0){ans=M.depth();return;}
					if(DP[dd+1].ContainsKey(M.state)==false)DP[dd+1].Add(M.state,M);
				}
			}
		}
	}
	
	Mark Sum(Mark A,Mark B){
		Mark ANS=new Mark();
		ANS.state=A.state&B.state;
		ANS.route=A.route|B.route;
		return ANS;
	}



}

Measured memory_bytes: 33588
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <set>
#include <cmath>
#include <tuple>
#include <cstring>
#include <map>
#include <iomanip>
#include <ctime>
#include <complex>
#include <cassert>
#include <climits>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define _ << " " <<
#define all(X) (X).begin(), (X).end()
#define len(X) (X).size()
#define Pii pair<int, int>
#define Pll pair<ll, ll>
#define Tiii tuple<int, int, int>
#define Tlll tuple<ll, ll, ll>

int main() {
    ll n;
    cin >> n;
    vector<ll> a(3*n);
    priority_queue<int> small;
    priority_queue<int, vector<int>, greater<int>> large;

    vector<ll> p(3*n), q(3*n);
    ll sm = 0;
    for (int i = 0; i < 3*n; i++) {
        cin >> a[i];
        if (i < n) {
            large.push(a[i]);
            sm += a[i];
        }
    }
    p[n] = sm;
    for (int i = n; i < 2*n; i++) {
        ll kth = large.top();
        if (kth < a[i]) {
            large.pop();
            large.push(a[i]);
            sm += a[i] - kth;
        }
        p[i + 1] = sm;
    }
    reverse(all(a));
    sm = 0;
    for (int i = 0; i < n; i++) {
        small.push(a[i]);
        sm += a[i];
    }
    q[n] = sm;
    for (int i = n; i < 2*n; i++) {
        ll kth = small.top();
        if (kth > a[i]) {
            small.pop();
            small.push(a[i]);
            sm += a[i] - kth;
        }
        q[i + 1] = sm;
    }

    ll ans = -1e18;
    for (int i = n; i <= 2*n; i++) {
        ans = max(ans, p[i] - q[3*n - i]);
    }
    cout << ans << endl;

    /*for (int i = n; i <= 2*n; i++) {
        cerr << i _ p[i] _ q[3*n-i] << endl;
    }*/

}


Measured memory_bytes: 8440