akhauriyash/Code-Regression huggingface dataset:
//インクルード(アルファベット順)
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<chrono>//実行時間計測
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<iterator>//集合演算(積集合,和集合,差集合など)
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm,accumulate
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//順序保持しないmap
#include<unordered_set>//順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列

using namespace std;
typedef long long ll;

//マクロ
//forループ
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
//xにはvectorなどのコンテナ
#define ALL(x) x.begin(),x.end() 
#define SIZE(x) ll(x.size()) 
//定数
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange
//略記
#define PB push_back //挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素

#define int long long

template<typename A, size_t N, typename T>

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


//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//ここにグローバル変数宣言

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//ここに関数宣言



//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
signed main(){
    //入力の高速化用のコード
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////



int A[3][3];
bool B[3][3];

Fill(B,false);

REP(i,3)REP(j,3){cin>>A[i][j];}
int N;
cin>>N;

REP(i,N){

	int b;
	cin >>b;

	REP(i,3)REP(j,3){
		if (A[i][j]==b)
		{
			B[i][j]=true;
		}
	}
}


bool ok=false;

if ( (B[0][0]&&B[1][1]&&B[2][2] )|| ( B[0][2]&&B[1][1]&&B[2][0]) )
{
	ok=true;
}

REP(i,3){

	if( (B[0][i]&&B[1][i]&&B[2][i] )|| (B[i][0]&&B[i][1]&&B[i][2]) ){
		ok=true;
	}
}


if (ok)
{
	cout<<"Yes"<<endl;
	return 0;
}
cout <<"No"<<endl;





























return 0;

}

Measured memory_bytes: 3624
#define _USE_MAT_DEFINES
#include<iostream>
#include <iomanip>
#include<stdio.h>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include <queue>
#include <utility>
#include <map>
#include <set>
#include <stack>
#include <deque>
#include <numeric>
#include <functional>
using namespace std;

#define MOD 1000000007;//1e9+7

int main() {
    int N;
    cin >> N;
    vector<int>A(N + 1, 0), B(N + 1, 0);
    for (int i = 1; i <N ; i++)cin >> B[i];
    
    long long ans = B[1];
    for (int i = 2; i <=N ; i++) {
        ans += min(B[i], B[i - 1]);
    }
    ans += B[N - 1];

    cout << ans;
}

Measured memory_bytes: 256
N = int(input())
S = [input() for _ in range(N)]
import collections
c = collections.Counter(S)
A = sorted(c.items(), key=lambda x: x[1], reverse=True)
count = 0
B = []
for a, b in A:
    if b >= count:
        B.append(a)
        count = b
    else:
        break

C = sorted(B)
for a in C:
    print(a)

Measured memory_bytes: 49224
#include<stdio.h>
#include<algorithm>
#include<functional>
#include<cmath>
#include<numeric>
#include<queue>
#include<string>
#include<vector>
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
ll mod = 1000000007;
using namespace std;
priority_queue<ll int>A;//きゅー
int main(void)
{
	int N;
	long long int sum = 0, d[100010];
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%lld", &d[i]);
	}
	for (int i = 0;i<N-1; i++) {
		for (int j = i + 1; j <= N - 1; j++) {
			sum += d[i] * d[j];
		}
	}
	printf("%lld", sum);
	return 0;

}


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


int main() {
  int N;
  cin >> N;
  vector<pair<int,int>> p(N);
  rep(i,N){
      cin >> p[i].first;
      cin >> p[i].second;
  }
  double sum = 0;
  sort(p.begin(),p.end());
  int c = 0;
  do {
    double d = 0;
    /*for(pair<int,int> x : p){
      cout << x.first << " " << x.second <<" " ;
    }
    cout << endl;*/
    for(int i = 0;i<N-1;i++){
        d += sqrt((p[i].first-p[i+1].first)*(p[i].first-p[i+1].first)
         + (p[i].second-p[i+1].second)*(p[i].second-p[i+1].second));
    }
    c++;
    sum += d;
    //cout << d << endl;
  } while (next_permutation(p.begin(), p.end()));

  cout << fixed << setprecision(10);
  //cout << c << endl;
  cout << sum/c << endl;
  
}

Measured memory_bytes: 256
# 二項係数を"やるだけ"にしてくれるライブラリ
MAX = 1000005
MOD = 10**9+7
factrial = [0]*MAX
inverse = [0]*MAX
factrial_inverse = [0]*MAX


# テーブルを作る前処理
def COMinit():
    global factrial, inverse, factrial_inverse
    factrial[0] = 1
    factrial[1] = 1
    inverse[1] = 1
    factrial_inverse[0] = 1
    factrial_inverse[1] = 1
    for i in range(2, MAX):
        factrial[i] = factrial[i-1] * i % MOD
        inverse[i] = MOD - inverse[MOD % i] * (MOD//i) % MOD
        factrial_inverse[i] = factrial_inverse[i-1] * inverse[i] % MOD


# 二項係数計算
def COM(n, k):
    global factrial, inverse, factrial_inverse
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return factrial[n] * (factrial_inverse[k] * factrial_inverse[n-k] % MOD) % MOD


# 前処理完了
COMinit()


def pow_r(x, n):
    """
    O(log n)
    """
    if n == 0:  # exit case
        return 1
    if n % 2 == 0:  # standard case ① n is even
        return pow_r((x ** 2) % MOD, n // 2) % MOD
    else:  # standard case ② n is odd
        return x * pow_r((x ** 2) % MOD, (n - 1) // 2) % MOD


N, A, B = map(int, input().split())
MOD = 1000000007
all_number = (pow_r(2, N)-1)
# nがさらに巨大な時
tmp_A = 1
for i in range(1, A+1):
    tmp_A %= MOD
    tmp_A *= (N-i+1)
    tmp_A *= inverse[i]

tmp_B = 1
for i in range(1, B+1):
    tmp_B %= MOD
    tmp_B *= (N-i+1)
    tmp_B *= inverse[i]
tmp_A %= MOD
tmp_B %= MOD
# print(all_number, tmp_A, tmp_B)
ans = (all_number - (tmp_A+tmp_B) + MOD)%MOD
print(ans % MOD)


Measured memory_bytes: 121716
#include <iostream>
#include <string>
#include <map>
#include <algorithm>
#define f first
#define s second
#define R PP(1,0,0)
#define C PP(0,1,0)
#define S PP(0,0,1)
using namespace std;
typedef pair <int,int> P;
typedef pair <int,P> iP;
int p,q;
string str[2][11];
map<iP,int> M;
iP PP(int a,int b,int c){return iP(a,P(b,c));}
iP E[]={R,C,S};

int gcd(int a,int b,int c,int d){
  a= a&&b? __gcd(a,b):max(a,b);
  c= c&&d? __gcd(c,d):max(c,d);
  a= a&&c? __gcd(a,c):max(a,c);
  return max(1,a);
}

void solve(){
  if(M.size()==2&&M.count(PP(1,1,1))) M[R]=M[C]=M[S]=M[PP(1,1,1)]/3;

  map<iP,int> ::iterator i,j;
  for(int k=0;k<3;k++){
    for(i=M.begin();i!=M.end();i++)
      for(j=M.begin();j!=M.end();j++){
	int A[]={i->f.f,i->f.s.f,i->f.s.s,i->s};
	int X[]={j->f.f,j->f.s.f,j->f.s.s,j->s};
	int D,l=A[k],r=X[k],f=1;
	D=gcd(l,r,0,0);
	for(int m=0;m<4;m++) if((A[m]=(A[m]*(r/D)-X[m]*(l/D)))<0)f=0;
	D=gcd(A[0],A[1],A[2],A[3]);
	for(int m=0;m<4;m++) A[m]/=D;
	if(f&&!M.count(PP(A[0],A[1],A[2])))M[PP(A[0],A[1],A[2])]=A[3];
      }
  }
}


int cal(int a,int b,int c){
  int d=gcd(a,b,c,0);
  a/=d,b/=d,c/=d;
  if(M.count(PP(a,b,c))) return M[PP(a,b,c)]*d;
  int fa=M.count(R),fb=M.count(C),fc=M.count(S),abc=fa+fb+fc;
  if(abc/3) return (M[R]*a+M[C]*b+M[S]*c)*d;
  if(abc/2&&!a==!fa&&!b==!fb&&!c==!fc) return (M[R]*a+M[C]*b+M[S]*c)*d;
  return -1;
}

void in(){
  M.clear();
  int cnt[3]={},d;
  for(int i=0;i<p;i++)
    for(int j=0,f=1,dot=0;j<str[0][i].size();j++){
      char ch=str[0][i][j];
      if(ch=='.')dot++;
      else if(f)f=0,d=gcd(cnt[0],cnt[1],cnt[2],dot),M[PP(cnt[0]/d,cnt[1]/d,cnt[2]/d)]=dot/d;
      if(ch=='('||ch=='['||ch=='{')cnt[ch/50]++;
      if(ch==')'||ch==']'||ch=='}')cnt[ch/50]--;
    }
}

void out(){
  int cnt[3]={},e[3];
  for(int i=0;i<3;i++)e[i]= M.count(E[i])? M[E[i]]:-1;

  for(int i=0;i<q;i++){
    for(int j=0;j<3;j++){
      M.erase(E[j]);
      if(e[j]!=-1)M[E[j]]=e[j];
    }
    if(i)cout <<" ";
    cout <<cal(cnt[0],cnt[1],cnt[2]);
    for(int j=0;j<str[1][i].size();j++){
      char ch=str[1][i][j];
      if(ch=='('||ch=='['||ch=='{')cnt[ch/50]++;
      if(ch==')'||ch==']'||ch=='}')cnt[ch/50]--;
    }
  }
  cout <<endl;
}

int main(){
  while(1){
    cin>>p>>q;
    if(!p&&!q) break;
    for(int i=0;i<p;i++)cin>>str[0][i];
    for(int i=0;i<q;i++)cin>>str[1][i];
    in();
    solve();
    out();
  }
  return 0;
}

Measured memory_bytes: 1228
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
#define loop(i,N) for(ll (i)=0; (i)<(N);++(i))
struct _OMAZINAI_ { _OMAZINAI_() { std::ios::sync_with_stdio(false); std::cin.tie(0); } } __omazinai_instance__;
#define INF (1LL<<61 + 1<<29)
#define YesNo(x) {std::cout << ((x)?"Yes":"No") << std::endl;}
#define YESNO(x) {std::cout << ((x)?"YES":"NO") << std::endl;}
#define OddEven(x) {std::cout << ((x)%2?"Odd":"Even") << std::endl;}
#define ODDEVEN(x) {std::cout << ((x)%2?"ODD":"EVEN") << std::endl;}
typedef long long int ll;
void _INPUT_IMPL_() {};
template <class T, class... Args> void _INPUT_IMPL_(T& dest, Args&... args) { cin >> dest; _INPUT_IMPL_(args...); }
#define cint(...) ll __VA_ARGS__; _INPUT_IMPL_(__VA_ARGS__);

int main() {
	cint(n, a, b);
	cout << min(a*n, b) << endl;
}

Measured memory_bytes: 256
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

def main():
    rr = []

    def f(n):
        _a = [n]
        while 1:
            s = S()
            if s == '.':
                break
            _a.append(s)
        _ks = {}
        _d = {}
        for _i in range(len(_a)):
            _s = _a[_i]
            if '=' in _s:
                try:
                    exec(_s,_d)
                    for _k in _ks.keys():
                        # print('_k',_k)
                        _kl = _d[_k].keys()
                        # print('_kl',_kl)
                        if _kl and max(_kl) >= _ks[_k]:
                            # print('mk', _s, _k,_kl)
                            return _i + 1
                except:
                    # print('except', _s)
                    # print('_d',_d.keys(),_d['z'])
                    return _i + 1
            else:
                _k = _s.split('[')[0]
                _n = int(_s.split('[')[1].split(']')[0])
                _ks[_k] = _n
                # print('tg', _k + ' = {}', _n)
                if _n < 1:
                    continue
                exec(_k+"={}",_d)
        return 0

    while 1:
        n = S()
        if n == '.':
            break
        rr.append(f(n))

    return '\n'.join(map(str,rr))


print(main())



Measured memory_bytes: 9188
#include<bits/stdc++.h>
#define Fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
int main()
{
    Fast;
    long long t,n,m,i,j,k,x=0,y=0,z;
    cin>>n>>m;
    long long a[m+5];
    for(i=0;i<m;i++){
        cin>>a[i];
        x=x+a[i];
    }
    if(x>=n){
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }
}


Measured memory_bytes: 1024
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef pair<int, int> Pi;
typedef long long ll;
#define pii Pi
#define pll PL
#define Fi first
#define Se second
#define pb(x) push_back(x)
//#define sz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<ll, ll> pll;
typedef long double ldouble;
typedef pair<double, double> pdd;

const double PI = acos(-1);
const double EPS = 1e-9;

const int MX = 200005;
const int MM = 1000000007;

pii D[MX];
vector<int> C[MX], G[MX];
ll I[MX], vst[MX], F[MX], FI[MX];;

void dfs(int x, map<int,int> &L){
	if( vst[x] ) return;
	vst[x] = 1;
	L[D[x].second] += 1;
	for(int c : G[x]){
		dfs(c, L);
	}
}

void make_edge(int a, int b){
	G[a].push_back(b);
	G[b].push_back(a);
}

int main()
{
	I[1] = F[0] = FI[0] = 1;
	for(int i = 2; i < MX; i++) I[i] = (MM - MM/i) * I[MM%i] % MM;
	for(int i = 1; i < MX; i++) F[i] = F[i-1] * i % MM;
	for(int i = 1; i < MX; i++) FI[i] = FI[i-1] * I[i] % MM;

	int N, X, Y;
	scanf("%d%d%d", &N, &X, &Y);
	for(int i = 1; i <= N; i++){
		scanf("%d%d", &D[i].second, &D[i].first);
	}
	sort(D+1, D+N+1);
	for(int i = 1; i <= N; i++){
		C[D[i].second].push_back(i);
	}
	for(int i = 1; i <= N; i++){
		sort(C[i].begin(), C[i].end());
		for(int j = 1; j < C[i].size(); j++){
			int a = C[i][0], b = C[i][j];
			if( D[b].first + D[a].first > X ) continue;
			make_edge(a, b);
		}
	}

	int c = D[1].second, se = 1;
	for(int i = 1; i <= N; i++){
		if( D[i].second != c && D[i].first + D[1].first <= Y ){
			make_edge(1, i);
		}
	}
	while(se <= N && D[se].second == c ) se++;
	if( se <= N ){
		for(int i = 1; i <= N; i++){
			if( D[i].second != D[se].second && D[i].first + D[se].first <= Y ){
				make_edge(se, i);
			}
		}
	}

	ll ans = 1;
	for(int i = 1; i <= N; i++){
		if( vst[i] ) continue;
		map<int,int> L;
		dfs(i, L);
		int tot = 0;
		for(auto e : L){
			tot += e.second;
			ans = ans * FI[e.second] % MM;
		}
		ans = ans * F[tot] % MM;
	}
	printf("%lld\n", ans);
}


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

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, mi = 55;
	int c[125][125];
	int m[125];
	string s, w, ans = "";

	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 97; j < 124; j++) {
			c[i][j] = 0;
		}
	}
	for (int i = 0; i < n; i++) {
		cin >> s;
		for (int j = 0; j < s.length(); j++) {
			w = s.substr(j, 1);
			char z = *w.c_str();
			c[i][z + 0]++;
		}
	}
	for (int i = 97; i < 124; i++) {
		for (int j = 0; j < n; j++) {
			mi = min(c[j][i], mi);
		}
		m[i] = mi;
		mi = 55;
	}
	for (int i = 97; i < 124; i++) {
		for (int j = 0; j < m[i]; j++) {
			cout << char(i);
		}
	}
	cout << endl;

	return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
int a[15][15],f[1<<15][15],g[1<<15];
int main(){
	int n,m,sum=0;
	scanf("%d%d\n",&n,&m);
	for (int i=1;i<=m;i++){
		int x,y,z;
		scanf("%d%d%d\n",&x,&y,&z);
		x--;y--;sum+=z;
		a[x][y]=a[y][x]=z;
	}
	int L=1<<n;
	for (int i=0;i<L;i++){
		for (int j=0;j<n;j++) f[i][j]=-1e9;
		for (int j=0;j<n;j++)
		if (i>>j&1){
			g[i]=g[1<<j^i];
			for (int k=j+1;k<n;k++)
				if (i>>k&1) g[i]+=a[j][k];
			break;
		}
	}
	f[1][0]=0;
	for (int i=1;i<L;i++)
		for (int j=0;j<n;j++)
		if (f[i][j]>=0){
			int x=(L-1)^i;
			for (int k=0;k<n;k++)
				if (!(i>>k&1) && a[j][k])
					f[i|1<<k][k]=std::max(f[i|1<<k][k],f[i][j]+a[j][k]);
			for (int k=x;k;k=(k-1)&x)
				f[i|k][j]=std::max(f[i|k][j],f[i][j]+g[k|1<<j]);
		}
	printf("%d\n",sum-f[L-1][n-1]);
}

Measured memory_bytes: 2176
# coding:utf-8

import sys
# from collections import Counter, defaultdict

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


n = II()

u = set([n])
cnt = 2
while True:
    if n % 2:
        n = 3 * n + 1
    else:
        n //= 2
    if n in u:
        print(cnt)
        exit()
    u.add(n)
    cnt += 1


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

int main(void)
{
    long long N;
    cin >> N;

    long long ans = 0;
    for (long long i = 1; i <= N; i++)
    {
        if (N % i == 0)
        {
            ans += (N / i) - 1;
        }
        else
        {
            ans += N / i;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3628
N = gets.to_i
# 人ごとの証言の数
a = []
# 証言
s = {}
N.times do |i|
  a[i] = gets.to_i
  # 人iの証言
  s[i+1] = []
  a[i].times do |j|
    # 人iのj番目の証言
    s[i+1][j] = gets.split.map(&:to_i)
  end
end

ans = 0
(1<<N).times do |i|
  # puts "i=#{i.to_s(2)}"
  cnt = 0
  # 一人ずつ矛盾がないかチェック
  continue = false
  s.each do |key, t|
    t.each do |u|
      # puts "証言：人#{u[0]}=#{u[1]==i[key-1] ? 1 : 0}"
      # 正直者と仮定してるやつに矛盾がないか見ていく
      if i[key-1] == 1
        # u[0]は言及されている人
        if not i[u[0]-1] == u[1]
          # 正直者と仮定してる奴が間違ってた場合，次のiに行く
          # puts "矛盾\n"
          continue = true
          break
        end
      end
    end
    if continue
      break
    end
  end
  # 矛盾がなかった場合
  if continue == false
    cnt = i.to_s(2).count('1')
    ans = [cnt, ans].max
    # puts "#{ans}\n"
  end
end

puts ans


Measured memory_bytes: 1788
def cmb(n, r, mod):#コンビネーションの高速計算　
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 2*10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

def function(i,k):
    return -((k*(k+1)*(2*k+1))//3)+k*(k+1)*(N+i-M)+2*N*(k+1)*(M-i)

N,M,K=map(int,input().split())
if M>N:
    N,M=M,N
ans=0
for i in range(1,N+M-1):
    if M-1>=i:
        ans+=i*(function(i,i)-N*(M-i)-M*(N-i))
        ans=ans%mod
    if i>=M and N-1>=i:
        ans+=i*(function(i,i)-function(i,i-M)-M*(N-i))
        ans=ans%mod
    if i>=N:
        ans+=i*(function(i,N-1)-function(i,i-M))
        ans=ans%mod

ans=ans*cmb(N*M-2,K-2,mod)
ans=ans%mod
print(ans)

Measured memory_bytes: 80880
#include<bits/stdc++.h>
using namespace std;
long long ans=0;
void doto(long long h,long long a){
	if(h==1){
		ans+=a;
		return ;
	}
	ans+=a;
	a*=2;h/=2;
	doto(h,a);
}
int main(){
	long long h;
	scanf("%lld",&h);
	doto(h,1);	
	printf("%lld",ans);
	return 0;
} 

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

int main(){
    int N, M, a, b;
    cin >> N >> M;
    vector<int> city(N);
    for(int i = 0;i < M;i++){
        cin >> a >> b;
        city.at(a-1)++;
        city.at(b-1)++;
    }
    for(int i = 0;i < N;i++){
        cout << city.at(i) << endl;
    }
}

Measured memory_bytes: 256
N = gets.to_i
A = gets.split.map &:to_i
Q = gets.to_i
BC = Q.times.map { gets.split.map &:to_i }

A_count = A.tally
A_count.default = 0
s = A.sum

BC.each do |b, c|
    p s = s + (c - b) * A_count[b]
    A_count[c] += A_count[b]
    A_count[b] = 0
end

Measured memory_bytes: 28680
import std.stdio;
import std.string;
import std.conv;
import std.typecons;
import std.algorithm;
import std.functional;
import std.bigint;
import std.numeric;
import std.array;
import std.math;
import std.range;
import std.container;
import std.ascii;
void times(alias pred)(int n) {
    foreach(i; 0..n) pred();
}
auto rep(alias pred, T = typeof(pred()))(int n) {
    T[] res = new T[n];
    foreach(ref e; res) e = pred();
    return res;
}

long INF = long.max/3;
void main() {
    int W, H;
    readf("%d %d\n", &W, &H);
    long[] ary1 = (W.rep!(() => readln.chomp.to!long)~INF).sort!((a, b) => a<b).array;
    long[] ary2 = (H.rep!(() => readln.chomp.to!long)~INF).sort!((a, b) => a<b).array;

    int i, j;
    long ans = 0;
    while(i+j<W+H) {
        if (ary1[i]<ary2[j]) {
            ans += ary1[i]*(H+1-j);
            i++;
        } else if (ary2[j]<ary1[i]) {
            ans += ary2[j]*(W+1-i);
            j++;
        } else {
            if (i<j) {
                ans += ary1[i]*(H+1-j);
                i++;
            } else {
                ans += ary2[j]*(W+1-i);
                j++;
            }
        }
    }
    ans.writeln;
}


Measured memory_bytes: 5244
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <string>
#include <cmath>
using namespace std;

#define rep(i,n) for(int i=0;i<int(n);++i)
#define PI 6*asin(0.5)

int main(){
	double x=0,y=0;
	int a,b;
	char t;
	int spin=90;
	//cout<<cos(90/180)<<" "<<sin(90/180)<<endl;
	cin>>a>>t>>b;
	while(!(a==0&&b==0)){
		x+=a*cos(spin*PI/180.0);
		y+=a*sin(spin*PI/180.0);
		spin-=b;
		//cout<<cos(spin/180.0)<<" "<<sin(spin/180.0)<<endl;
		cin>>a>>t>>b;
		//cout<<x<<" "<<y<<endl;
	}
	printf("%d\n%d\n",(int)x,(int)y);
	return 0;
}

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

#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
typedef long long ll;

const long long INF = 1LL << 60;

int main()
{
    string X, Y;
    cin >> X >> Y;

    int Xs, Ys;
    Xs = (int)X.size() + 1;
    Ys = (int)Y.size() + 1;

    vector<vector<int>> dp(Xs, vector<int>(Ys, 0));

    rep(i, Xs) dp[i][0] = i;
    rep(i, Ys) dp[0][i] = i;

    rep(i, Xs - 1) {
        rep(j, Ys - 1) {
            int x = 1;
            if (X[i] == Y[j]) {
                x = 0;
            }
            dp[i + 1][j + 1] = min(min(dp[i][j] + x, dp[i][j + 1] + 1), dp[i + 1][j] + 1);
        }
    }
    
    cout << dp[Xs - 1][Ys - 1] << endl;

    return 0;
}


Measured memory_bytes: 6904
using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.Linq;
using System.Numerics;

namespace AtCoderWorkspace
{
    public class Solver
    {
        public void Solve()
        {
            var cin = new Scanner();
            var s = cin.next();
            var t = cin.next();

            var ans = long.MaxValue;
            for (int i = 0; i <= s.Length-t.Length; i++)
            {
                var count = 0L;
                for (int j = 0; j < t.Length; j++)
                {
                    if (s[i + j] != t[j]) count++;
                }
                ans = Math.Min(ans, count);
            }
            Console.WriteLine(ans);
        }
    }

    class Scanner
    {
        string[] s;
        int i;

        char[] cs = new char[] { ' ' };

        public Scanner()
        {
            s = new string[0];
            i = 0;
        }

        public string next()
        {
            if (i < s.Length) return s[i++];
            string st = Console.ReadLine();
            while (st == "") st = Console.ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            if (s.Length == 0) return next();
            i = 0;
            return s[i++];
        }

        public int nextInt()
        {
            return int.Parse(next());
        }
        public int[] ArrayInt(int N, int add = 0)
        {
            int[] Array = new int[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextInt() + add;
            }
            return Array;
        }

        public int[] DPArrayInt(int N, int ex)
        {
            int[] Array = new int[N + ex];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextInt();
            }
            return Array;
        }

        public long nextLong()
        {
            return long.Parse(next());
        }

        public long[] ArrayLong(int N, long add = 0)
        {
            long[] Array = new long[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextLong() + add;
            }
            return Array;
        }

        public long[] DPArrayLong(int N, int ex)
        {
            long[] Array = new long[N + ex];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextLong();
            }
            return Array;
        }

        public double nextDouble()
        {
            return double.Parse(next());
        }


        public double[] ArrayDouble(int N, double add = 0)
        {
            double[] Array = new double[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextDouble() + add;
            }
            return Array;
        }
    }

    class Program
    {
        static void Main(string[] s) => new Solver().Solve();
    }
}


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

using namespace std;

typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<bool> vb;
typedef vector<string> vst;
typedef pair<ll,ll> pll;
typedef vector<pll> vpll;


const ll mod=(1e+9)+7;
const ll inf=1e+16; 

#define rep(i,m,n) for(ll i=m;i<n;i++)
#define repr(i,m,n) for(ll i=m;i>=n;i--)

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

 ll n;
  cin >> n;
 ll res=0,m=0;
 vll a(n);
  rep(i,0,n) {
    cin >> a[i];
    m=max(a[i],m);
  }
  
  ll index=0;
  while(m>0){
   m/=2;
    index++;
  }
  
  ll pow=1;
  rep(j,0,index+1){
    
    ll one=0;
   rep(i,0,n) {
     if(((a[i]>>j)&1)) one++;
   }
   res+=(((one*(n-one))%mod)*pow);
    res%=mod;
    pow*=2;
    pow%=mod;
  }
  
  cout << res << endl;
  
}


Measured memory_bytes: 2560
#include<bits/stdc++.h>
#define ll long long 
#define pb push_back
#define mod 1000000007
#define all(v) v.begin(),v.end()
#define MP make_pair
#define F first
#define S second
#define inf 10000000000000
#define vll vector<ll>
using namespace std;
const int N=200005;

void solve()
{
	
	ll x,y;

	cin>>x>>y;
	cout<<(double)x/y;
}
 
int main() {
    
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
    ll t=1;
    //cin>>t;
    while(t--)
        solve();
 
    
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cmath>
#include <set>
#include <queue>
#include <vector>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
#include <stack>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;

struct EdgeD
{
	int to;
	ll cost;
};

void calcShortestD(vector<vector<EdgeD>>& G, int s, int maxV, vector<ll>& d)
{
	for (auto i = 0; i < maxV; ++i)
	{
		d.push_back(LLONG_MAX);
	}
	d[s] = 0;

	priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q;
	q.push({ 0, s });

	while (!q.empty())
	{
		auto p = q.top();
		q.pop();
		auto v = p.second;
		if (d[v] < p.first)
		{
			continue;
		}

		for (auto& e : G[v])
		{
			if (d[e.to] > d[v] + e.cost)
			{
				d[e.to] = d[v] + e.cost;
				q.push({ d[e.to], e.to });
			}
		}
	}
}


int main()
{
	int n, m, s, t;
	cin >> n >> m >> s >> t;
	--s;
	--t;

	vector<vector<EdgeD>> GY(n);
	vector<vector<EdgeD>> GS(n);
	for (auto i = 0; i < m; ++i)
	{
		int u, v;
		ll a, b;
		cin >> u >> v >> a >> b;
		
		--u;
		--v;
		GY[u].push_back({ v, a });
		GY[v].push_back({ u, a });
		GS[u].push_back({ v, b });
		GS[v].push_back({ u, b });
	}

	vector<ll> dY;
	calcShortestD(GY, s, n, dY);
	vector<ll> dS;
	calcShortestD(GS, t, n, dS);

	priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q;
	for (auto i = 0; i < n; ++i)
	{
		q.push({ dY[i] + dS[i], i });
	}

	for (auto i = 0; i < n; ++i)
	{
		auto init = (ll)1e15;
		auto p = q.top();
		while (p.second < i)
		{
			q.pop();
			p = q.top();
		}
		cout << init - p.first << endl;
	}

	return 0;
}

Measured memory_bytes: 21692
<?php
$s=trim(fgets(STDIN));
$ans=0;
$i=0;
while($i<3){
  if($s[$i]=="R"){
    ++$ans;
  }
  ++$i;
}
if($ans==2){
  if($s[1]=="S"){
    --$ans;
  }
}
echo $ans;

Measured memory_bytes: 16152
#include<bits/stdc++.h>
#define MOD 1000000007
#define MAX 1000000
using namespace std;
int v[MAX+1];
bool criba[MAX+1];
bool check(int n)
{
	for(int i=2;i<=MAX;++i)
	{
		if(!criba[i])
		{
			long long j = i;
			int cnt = 0;
			while(j<=MAX)
			{
				criba[j] = true;
				cnt += v[j];
				if(cnt>=2)
					return false;
				j += 1LL*i;
			}
		}
	}
	return true;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin>>n;
	int gcd;
	for(int i=1,x;i<=n;++i)
	{
		cin>>x;
		++v[x];
		if(i==1)
			gcd = x;
		else gcd = __gcd(gcd,x);	
	}
	if(check(n))
		cout<<"pairwise coprime"<<endl;
	else if(gcd==1)
		cout<<"setwise coprime"<<endl;
	else
		cout<<"not coprime"<<endl;
	return 0;
}

Measured memory_bytes: 8528
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,x,n) for(int i=x; i<(n); i++)
#define all(n) begin(n),end(n)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
const long long INF = numeric_limits<long long>::max();
typedef long long ll;
typedef vector<int> vint;
typedef vector<char> vchar;
typedef vector<vector<int>> vvint;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;

int main()
{
    ll A,B,C,D;
    cin>>A>>B>>C>>D;
    ll g = (C*D)/__gcd(C,D);
    ll k = (A-1)-(A-1)/C - (A-1)/D+(A-1)/(g);
    ll t = B-B/C-B/D+B/g;
    cout<<t-k;
    return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
typedef long long ll;

using namespace std;


int main()
{
    ll n;
    cin >> n;
    for (int q = (int)(sqrt(n)); q >= 1; q--)
    {
        if (n % q == 0)
        {
            cout << n/q+q-2;
            return 0;
        }
    }
    return 0;
}


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

using namespace std;
int main()
{
	string s;
	cin>>s;
	vector<int> cnt;
	cnt.resize(26);
	int i;
	for(i=0;i<4;i++)
	{
		int val = (int)s[i] - (int)'A';
		cnt[val] += 1;
	}
	int cnt2=0;
	for(i=0;i<26;i++)
	{
		if(cnt[i]==2)
			cnt2++;
	}
	if(cnt2==2)
		cout<<"Yes\n";
	else
		cout<<"No\n";
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <algorithm>
typedef long long ll;

int main(void) {
  ll i, j, k, n, m, v, p, ans, now;
  scanf("%lld%lld%lld%lld", &n, &m, &v, &p);
  ll a[n], sum[n];
  sum[0] = 0;
  ans = p;
  for(i = 0; i < n; ++i) scanf("%lld", &a[i]);
  std::sort(a, a + n);
  sum[0] = a[0];
  for(i = 1; i < n; ++i) sum[i] = sum[i - 1] + a[i];
  for(i = 0; i < n - p; ++i) {
    if(a[i] + m < a[n - p]) continue;
    if(v < p + i) ++ans;
    else {
      now = sum[n - p] - sum[i];
      if((a[i] + m) * (n - p - i) - now >= m * (v - p - i)) ++ans;
    }
  }
  printf("%lld", ans);
  return 0;
}

Measured memory_bytes: 1664
import java.util.*;
class Main{
public static void main(String[]args){
Scanner sc=new Scanner(System.in);
  long a=sc.nextLong(),b=sc.nextLong(),c=sc.nextLong();
  System.out.println((4*a*b<(a+b-c)*(a+b-c)&&a+b<c)?"Yes":"No");
}
}


Measured memory_bytes: 23764
#include <bits/stdc++.h>
#define repr(i,from,to) for(int (i)=(from);(i)<(to);(i)++)
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
// const bool debug=true;
const bool debug=false;
#define DEBUG if(debug==true)
#define vprint(x) for(auto a:(x)) cout << x << endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MOD = 1000000007;
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) { a = b; return true;}
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) { a = b; return true;}
    return false;
}
int main(void) {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,k,q;cin>>n>>k>>q;
    ll a[q];rep(i,q){cin>>a[i];}
    ll cnt[n]={};
    rep(i,q){
        cnt[a[i]-1]++;
    }
    rep(i,n){
        if(k-q+cnt[i]>0){
            cout << "Yes" << endl;
        }else{
            cout << "No" << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 2176
use proconio::fastout;
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::*;
use std::collections::VecDeque;

#[fastout]
fn main() {
    input! {
        n: usize,
        m: usize,
        ab: [(Usize1, Usize1); m],
    }
    let mut g = vec![vec![]; n];
    for (a, b) in ab {
        g[a].push(b);
        g[b].push(a);
    }

    let mut q = VecDeque::new();
    q.push_back(0);
    let mut ans = vec![n; n];
    while let Some(now) = q.pop_front() {
        for &next in g[now].iter() {
            if ans[next] != n {
                continue;
            }
            ans[next] = now;
            q.push_back(next);
        }
    }

    if ans.iter().any(|a| *a == n) {
        println!("{}", "No");
        return;
    }
    println!("{}", "Yes");
    for a in ans[1..].iter() {
        println!("{}", a + 1);
    }
}


Measured memory_bytes: 15956
def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    B.append(0)
    ans = 0
    for i in range(N):
        if B[i] > A[i]:
            ans += A[i]
            if B[i] - A[i] > A[i + 1]:
                ans += A[i + 1]
                A[i + 1] = 0
            else:
                ans += B[i] - A[i]
                A[i + 1] -= B[i] - A[i]
        else:
            ans += B[i]
    print(ans)


main()


Measured memory_bytes: 18476
#include <bits/stdc++.h>
#define LOCAL
using namespace std;
template <typename A, typename B>
ostream& operator <<(ostream& out, const pair<A, B>& a) {
out << "(" << a.first << "," << a.second << ")";
return out;
}
template <typename T, size_t N>
ostream& operator <<(ostream& out, const array<T, N>& a) {
out << "["; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T>
ostream& operator <<(ostream& out, const vector<T>& a) {
out << "["; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const set<T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
return out;
}
template <typename U, typename T, class Cmp>
ostream& operator <<(ostream& out, const map<U, T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& p : a) { out << (first ? "" : ", "); out << p.first << ":" << p.second; first = 0;} out << "}";
return out;
}
#ifdef LOCAL
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define trace(...) 42
#endif
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');
cerr.write(names, comma - names) << ": " << arg1 << " |";
__f(comma + 1, args...);
}
#define rep(i,n) for(int i=0; i<(n); i++)
using ll = long long;
#define int long long
using P = pair<int,int>;
//#########################################
const int INF = 1e18;

void wf(vector<vector<int>> dist,int n){
	rep(i,n)rep(j,n)rep(k,n){
		dist[j][k] = min(dist[j][k],dist[j][i] + dist[i][k]);
	}
}
signed main(){
	int n,m,l;cin >> n >> m >> l;
	vector<vector<int>> dist1(n,vector<int> (n,INF));
	rep(i,n)dist1[i][i] = 0;
	rep(i,m){
		int a,b,c;cin >> a >> b >> c;
		a--;b--;
		dist1[a][b] = dist1[b][a] = c;
	}
	// wf(dist1,n);
	rep(i,n)rep(j,n)rep(k,n){
		dist1[j][k] = min(dist1[j][k],dist1[j][i] + dist1[i][k]);
	}
	vector<vector<int>> dist2(n,vector<int>(n,INF));
	rep(i,n)dist2[i][i] = 0;
	rep(j,n)rep(i,j){
		trace(i,j,dist1[i][j]);
		if(dist1[i][j] <= l){
			dist2[i][j] = dist2[j][i] = 1;
		}
	}
	// wf(dist2,n);
	rep(i,n)rep(j,n)rep(k,n){
		dist2[j][k] = min(dist2[j][k],dist2[j][i] + dist2[i][k]);
	}
	int q;cin >> q;
	while(q--){
		int s,t;cin >> s >> t;
		s--;t--;
		int ret = dist2[s][t];
		if(ret == INF)cout << -1 << endl;
		else cout << ret-1 << endl;
	}
	

	return 0;
}

Measured memory_bytes: 5052
//#include "pch.h"
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>

#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <utility>
#include <queue>
#include <algorithm>
#include <functional>
#include <string>
#include <bitset>

#define ll long long
#define fri(n) for(i=0;i<(n);i++)
#define frj(n) for(j=0;j<(n);i++)
#define min(p,q) ((p)<(q)?(p):(q))
#define max(p,q) ((p)>(q)?(p):(q))
#define INF 1000000000000000000//10^18
#define INFINT 2000000001//2*10^9+1
#define MOD 1000000007
#define MODANOTHER 998244353
#define PI acos(-1)

using namespace std;


int main(void)
{
	//変数の宣言
	int n;
	int a[2010];
	static bitset<2000010> dp[2010];

	//よく使う変数
	int i,j,k,l;
	int flag=0;
	int ans=0;
	int count=0;
	ll int temp,temp1,temp2;
	int max,min;
	int len;
	int sum=0;
	int ok,ng;
	int r;


	//データの読み込み


	scanf("%d",&n);
//	scanf_s("%d",&n);

	for(i=0;i<n;i++){
		scanf("%d",&a[i]);
//		scanf_s("%d",&a[i]);
	}


	//	printf("nは%dです\n", n);
	//	printf("データの読み込み終了\n");
	//実際の処理

	for(i=0;i<n;i++){
		sum=sum+a[i];
	}
	
	temp=sum/2;

	dp[0]=1;
	for(i=0;i<n;i++){
		dp[i+1]=(dp[i]|(dp[i]<<a[i]));
	}

	while(temp){
		if(dp[n][temp]==1){
			break;
		}
		temp--;
	}

	//	printf("計算部分終了\n");

	//出力

	

	printf("%lld",sum-temp);


	//	printf("結果の出力終了\n");


	return 0;
}



Measured memory_bytes: 490496
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef tuple<ll,ll,ll> T;
const long long INF = 1LL<<60;
const int MOD = 1000000000+7;
#define rev(s) (string((s).rbegin(), (s).rend()))
template < typename T > inline string toString( const T &a ) { ostringstream oss; oss << a; return oss.str(); };
// cout << fixed << setprecision(10) << ans << endl;
// *min_element(c + l, c + r) *max_element(c + l, c + r)
// int dx[8]={1,1,0,-1,-1,-1,0,1};
// int dy[8]={0,1,1,1,0,-1,-1,-1};
// int dx[4]={1,0,-1,0};
// int dy[4]={0,1,0,-1};
// struct Edge {
//   int to, id;
//   Edge(int to, int id): to(to), id(id) {}
// };

int nxt[65][200010];

int main() {
    ll n,k;cin>>n>>k;
    rep(i,n) {
        cin>>nxt[0][i];
        nxt[0][i]--;
    }
    rep(i,60) {
        rep(j,n) {
            nxt[i+1][j]=nxt[i][nxt[i][j]];
        }
    }
    int goal = 0;
    rep(i,60) {
        if(k&(1LL<<i)) goal = nxt[i][goal];
    }
    cout<<goal+1<<endl;
}

Measured memory_bytes: 51184
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons;

void main()
{
    auto N = readln.chomp.to!int;
    int cnt;
    foreach (n; 1..N+1) {
        if (n % 2 == 0) continue;
        int y;
        foreach (x; 1..n+1) {
            if (n % x == 0) ++y;
        }
        if (y == 8) ++cnt;
    }
    writeln(cnt);
}

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

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

    }
}




Measured memory_bytes: 3620
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define init(a) memset((a),0,sizeof(a))
using namespace std;
typedef double D;
typedef vector<D> P;
const D EPS = 1e-8;

int n,m,R;
P sp[2020],tp[20],ep;
D sr[2020],tb[20],p[20];
vector<int> rm[20];

inline P mul(P p, const D &d){
  rep(i,p.size())p[i] *= d;
  return p;
}

inline P add(P a, const P &b){
  rep(i,a.size())a[i] += b[i];
  return a;
}

inline D dis2(const P &a, const P &b){
  D x = a[0]-b[0], y = a[1]-b[1], z = a[2]-b[2];
  return x*x+y*y+z*z;
}

inline D score(const int &i){
  return tb[i]/dis2(ep,tp[i]);
}

inline int intersect(const int &p, const int &c){
  P l = ep, r = tp[p];
  D r2 = sr[c]*sr[c];
  bool f1 = (dis2(sp[c],l)<r2+EPS), f2 = (dis2(sp[c],r)<r2+EPS);
  if(f1&&f2)return 0;
  if(f1||f2)return 1;

  rep(i,20){
    P m1 = mul(add(mul(l,2),r),1.0/3), m2 = mul(add(l,mul(r,2)),1.0/3);
    D d1 = dis2(sp[c],m1), d2 = dis2(sp[c],m2);
    if(d1<d2)r = m2;
    else l = m1;
  }
  if(dis2(sp[c],l)<r2+EPS)return 1;
  return 0;
}


D rec(int d,int num, D sum, vector<int> &use){
  if(d==m)return sum;
  D res = rec(d+1,num,sum,use);
  vector<int> tmp = use;
  rep(i,rm[d].size()){
    if(!use[rm[d][i]]){
      num++;
      use[rm[d][i]] = 1;
    }
  }
  if(num<=R)res = max(res,rec(d+1,num,sum+p[d],use));
  use = tmp;
  return res;
}
		    
int main(){
  while(scanf("%d%d%d",&n,&m,&R),n){
    rep(i,n){
      sp[i].resize(3);
      rep(j,3)scanf("%lf",&sp[i][j]);
      scanf("%lf",&sr[i]);
    }
    rep(i,m){
      tp[i].resize(3);
      rep(j,3)scanf("%lf",&tp[i][j]);
      scanf("%lf",&tb[i]);
    }
    ep.resize(3);
    rep(i,3)scanf("%lf",&ep[i]);

    rep(i,m){
      rm[i].clear();
      rep(j,n){
	if(intersect(i,j))rm[i].push_back(j);
      }
    }

    rep(i,m)p[i] = score(i);
    vector<int> use(n,0);
    cout << fixed << setprecision(10) << rec(0,0,0,use) << endl;
  }
}

Measured memory_bytes: 1644
N = int(input())
data = {}
bits = 0
bit_table = [set() for _ in range(31)]
for a in map(int, input().split()):
	bits |= a
	if a in data:
		data[a] += 1
	else:
		data[a] = 1
	i = 0
	b = a
	while b:
		if b % 2 == 1:
			bit_table[i].add(a)
		b //= 2
		i += 1

def pop(data, a):
	if a in data:
		if data[a] == 1:
			del data[a]
		else:
			data[a] -= 1
		return a
	else:
		return None

def check2(data0, a1, a2):
	if (a1 | a2) != bits:
		return False
	
	data = { k: data0[k] for k in data0 }
	a0 = a1
	pop(data, a1)
	pop(data, a2)
	
	while data:
		a3 = a1 ^ a2
		a4 = pop(data, a3)
		if a4 == None:
			return False
		a1 = a2
		a2 = a3
	return a0 == (a1 ^ a2)

def check(data):
	keys = list(data.keys())
	a1 = keys[0]
	b = bits & (~a1)
	cands = set(keys)
	i = 0
	while b:
		if b % 2 == 1:
			cands &= bit_table[i]
		b //= 2
		i += 1
	
	for a2 in cands:
		if a1 != a2 or data[a1] > 1:
			if check2(data, a1, a2):
				return True
	return False

if check(data):
	print("Yes")
else:
	print("No")


Measured memory_bytes: 79772
#include <iostream>
#include <algorithm>
#include <vector>
#include <array>
#include <string>
#include <queue>
#include <cmath>
#include <iterator>
#include <math.h>
#include <cstdio>
#include <map>

using namespace std;
using lli = long long int;
using ulli = unsigned long long int;

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


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

using namespace std;
typedef long long ll;

int main() {
  ll N; cin >> N;
  ll X; cin >> X;
  vector<ll> L(N);
  for (ll j=0; j < N; ++j) cin >> L[j];
  ll ans = 1, d = 0;
  for (ll j=0; j < N; ++j) {
    d += L[j];
    if (d <= X) {
      ans += 1;
    } else {
      break;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
def BldIn(n):
  Name = [0] * n
  Pos = [0] * n
  segment = {}
  for i in range(n):
    bi, xi, yi = map(int, raw_input().split())
    Name[i] = bi
    Pos[i] = [xi, yi]
    for j in range(i):
      xj, yj = Pos[j]
      tmp = ((xi - xj) ** 2 + (yi - yj) ** 2) ** .5
      segment[(i, j)] = tmp
      segment[(j, i)] = tmp
  return Name, segment

def solve(distance, g):
  for i1, e1 in enumerate(distance):
    d1, p1 = e1
    if d1 != inf and p1 == g:
      return 1
    x1=[]
    x2=[]
    for i2, e2 in enumerate(distance):
      d2, p2 = e2
      if i1==i2: continue
      dd = segment[(p1, p2)]
      if dd > 50:
        x2.append(e2)
        continue
      if d1 + dd < d2:
        distance[i2][0] = d1 + dd
        Path[p2] = p1
      x1.append(distance[i2])
    if x1:
      return solve(sorted(x1)+x2, g)
  return 0

def PathOut(g, s):
  x = [Name[g]]
  while g != s:
    g = Path[g]
    x.append(Name[g])
  for e in x[1:][::-1]:
    print e,
  print x[0]
  return

inf = 1e9
while 1:
  n = int(raw_input())
  if n == 0:
    break
  Name, segment = BldIn(n)

  m = int(raw_input())
  for _ in [0] * m:
    Path = {}
    s, g = map(Name.index, map(int, raw_input().split()))
    distance = [[inf, i] for i in range(n)]
    distance[s][0] = 0
    if solve(sorted(distance), g):
      PathOut(g, s)
    else:
      print "NA"

Measured memory_bytes: 5916
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mod 1000000007
main()
{
    char s[5];
    int a=0,b=0,i;
    cin>>s;
    for(i=0;i<=2;i++)
    {
        if(s[i]=='A')
        {
            a=1;
        }
        else
        {
            b=1;
        }
    }
    if(a==1 && b==1)
    {
        printf("Yes\n");
    }
    else
    {
        printf("No\n");
    }
}



Measured memory_bytes: 256
/*
    Author: Alam Khan
    AUST CSE 40th Batch

*/

#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
typedef deque<ll> dl;
typedef stack<ll> stl;
typedef set<ll> sl;
typedef map<string, ll> msl;
typedef map<ll,ll> mll;
typedef tree<ll,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
#define sf(n)     scanf("%lld",&n)
#define sff(n,m)     scanf("%lld %lld",&n,&m)
#define sfff(n,m,r)     scanf("%lld %lld %lld",&n,&m,&r)
#define sfs(n)     scanf("%s",n)
#define pf(n)     printf("%lld\n",n)
#define pff(n,m)     printf("%lld %lld\n",n,m)
#define pfff(n,m,r)     printf("%lld %lld %lld\n",n,m,r)
#define pfs(n)     printf("%s\n",n)
#define pfcs(i,n)     printf("Case %lld: %lld\n",i,n)
#define pb     push_back
#define prf     printf
#define inf     2e18
#define low     -1000000000000
#define PI        acos(-1.0)
#define rep1(i,n) for(i=1;i<n;i++)
#define rep0(i,n) for(i=0;i<n;i++)
#define rep(i,a,n) for(i=a;i<n;i++)
#define repe1(i,n) for(i=1;i<=n;i++)
#define repe0(i,n) for(i=0;i<=n;i++)
#define repe(i,a,n) for(i=a;i<=n;i++)
#define endl  "\n"
#define FAST  ios_base::sync_with_stdio(false);cin.tie(NULL);
#define fr freopen("input.txt","r",stdin)
#define fw freopen("output.txt","w",stdout)
ll a[100009];
int main()
{
    ll i,n,t,k,j,x=0,y=0,m;
    cin>>n>>k>>m;
    for(i=1;i<=m;i++)
    {
        cin>>x;
        a[x]++;
    }
    for(i=1;i<=n;i++)
    {
        y= m-a[i];
        a[i] = -y;
        a[i]+= k;

    }
    for(i=1;i<=n;i++)
    {
        if(a[i]>0)
            cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}



Measured memory_bytes: 4340
/**
 * @author      : cromarmot (yexiaorain@gmail.com)
 * @license     : GPL
 * @created     : 星期六 11月 23, 2019 20:06:40 CST
 */

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

typedef long long ll;
#define ten5 100000+10
#define MOD 1000000007
#define rep(i,a,n) for (int i=a;i<n;i++)
#define iif(c,t,f) ((c)?(t):(f))
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
const double pi = acos(-1.0);


// a[i] , a[i]
//
//

ll a[200010];
ll pre[200010];
ll suffix[200010];
int n;


int main(){
  cin>>n;
  ll sum = 0;
  rep(i,0,n){
    scanf("%lld",a+i);
    sum+=a[i];
  }
  pre[0]=a[0];
  rep(i,1,n){
    pre[i]=pre[i-1]+a[i];
  }
  ll ans = abs(sum-2*pre[0]);
  rep(i,1,n){
    ans=min(ans,abs(sum-2*pre[i]));
  }
  cout<<ans<<endl;
  return 0;
}

/*
 *
 * hash prime
   61,83,113,151,211,281,379,509683,911
   1217,1627,2179,2909,3881,6907,9209
   12281,16381,21841,29123,38833,51787,69061,92083
   122777,163729,218357,291143,388211,517619,690163,999983
   1226959,1635947,2181271,2908361,3877817,5170427,6893911,9191891
   12255871,16341163,21788233,29050993,38734667,51646229,68861641,91815541
   122420729,163227661,217636919,290182597,386910137,515880193,687840301,917120411
   1000000007,1000000009
 * */



Measured memory_bytes: 3328