akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include<iomanip>
#include <map>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
#include <queue>
#define INF 1e9+7
#define rep(i,n) for(ll i=0;i<n;i++)
#define NO cout<<"NO"<<endl;
#define YES cout<< "YES"<<endl;
#define No cout<< "No"<<endl;
#define Yes cout<< "Yes"<<endl;
#define all(a) a.begin(),a.end()
#define P pair<int,int>
#define space ' '
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

//(int)'a'は97 (int)'A'は65 (int)'1'は49
//おまじない

const int maxn = 100000;
ll h,w,n;
map<pair<int,int>, int> m;
vector<pair<int,int> > v;
int dx[9]={-1,-1,-1,0,0,0,1,1,1};
int dy[9]={-1,0,1,-1,0,1,-1,0,1};
ll ans[10]={0};

int main(){
    
    cin >> h>>w>>n;
    rep(i,n){
        int s,t;
        cin >> s>>t;
        s--;t--;
        v.push_back(make_pair(s,t));
    }
    
    ans[0]=(h-2)*(w-2);
    
    rep(i,v.size()){
        rep(j,9){
            int x = v[i].second+dx[j];int y = v[i].first+dy[j];
            if(1<=x&&x<=w-2&&1<=y&&y<=h-2){
                ans[m[make_pair(y,x)]]--;
                m[make_pair(y,x)]++;
                ans[m[make_pair(y,x)]]++;
            }
        }
    }
    
    rep(i,10){
        cout << ans[i]<<endl;
    }
    
    return 0;
}


Measured memory_bytes: 57332
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define erep(i, n) for (ll i = 0; i <= (ll)(n); ++i)
#define FOR(i,a,b) for (ll i = (a); i < (ll)(b); ++i)
#define EFOR(i,a,b) for (ll i = (a); i <= (ll)(b); ++i)

void chmax(ll& a, ll b) { a = max(a, b); }
void chmin(ll& a, ll b) { a = min(a, b); }


int main() {
    int a,b; cin >> a >> b;
    string s; cin >> s;
    rep(i, s.size()) {
        if(i == a) {
            if(s[i] != '-') {
                cout << "No" << endl;
                return 0;
            }
        } else {
            if(s[i] - '0' >= 0 && s[i] - '0' <= 9) {

            } else {
                cout << "No" << endl;
                return 0;
            }
        }

    }

    cout << "Yes" << endl;
    return 0;

}


Measured memory_bytes: 256
N = int(input())
A = [int(i)-1 for i in input().split()]
B = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]

v = 0


for i in range(N):
    v += B[A[i]]
    if i >= 1:
        if A[i]-A[i-1]==1:
            v += C[A[i]-1]
print(v)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
//F6編譯，右上三角形執行，ctrl+c強制停止執行  F5開啟exe
#define ll long long
#define maxn 200005
#define mod 998244353
using namespace std;

int n, k;

int main()
{
	cin >> n >> k;
	if (k == 1)
		printf("0");
	else
		printf("%d", n - k);

	return 0;
}


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

int main () {
	string s;
	cin >> s;
	int front_number, back_number;

	for (int i = 0; i < s.size(); i++) {
		if (s[i] == 'A') {
			front_number = i;
			break;
		} 
	}

	for (int i = s.size() - 1; i >= 0; i--) {
		if (s[i] == 'Z') {
			back_number = i;
			break;
		} 
	} 
	
	cout << back_number - front_number + 1 << endl;

	return 0;
}

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


#define FOR(i, start, end) for(uint64_t i=start; i<end; i++)
#define REP(i, n) FOR(i, 0, n)

// 最大公約数gcd
// 最小公倍数lcm=m*n/gcd
uint64_t gcd(uint64_t m, uint64_t n) {
  uint64_t temp;
  while (m % n != 0){
    temp = n;
    n = m % n;
    m = temp;
  }
  return n;
}

uint64_t lcm(uint64_t m, uint64_t n) {
  return (m*n)/gcd(m,n);
}

void comb(vector<vector <uint64_t> > &v){
  for(uint64_t i = 0;i <v.size(); i++){
    v[i][0]=1;
    v[i][i]=1;
  }
  for(uint64_t k = 1;k <v.size();k++){
    for(uint64_t j = 1;j<k;j++){
      v[k][j]=(v[k-1][j-1]+v[k-1][j]);
    }
  }
}

// 掛け算オーバーフロー判定
bool is_product_overflow(uint64_t a, uint64_t b) {

	uint64_t prod = a * b;
	
	return (prod / b != a);
}

//素因数分解
void primeFactorization(uint64_t a, list<uint64_t> &factors){ //素因数分解を出力するプログラム
  long i,sq;
  if(a%2==0){ //偶数の場合
    factors.push_back(2);
    primeFactorization(a/2,factors); //2で割った値で再帰
    return;
  }
  sq = sqrt(a);
  for(i=3;i<=sq;i+=2){ //3以上√a以下の奇数の場合
	if(a%i==0){
	  factors.push_back(i);
      primeFactorization(a/i,factors); //割れた値で再帰
      return;
	}
  }
  //偶数でも3以上√a以下の奇数の場合でも割り切れない場合
  if(a!=1){ //aが1でないなら、a自身は素数
    factors.push_back(a);
  }
}

signed main() {
  uint64_t st;
  cin >> st;
  
  uint64_t h,m,s;
  h = st/3600;
  m = (st%3600)/60;
  s = st - h*3600 - m*60;
  cout << h << ":" << m << ":" << s << endl;
  return 0;
}


Measured memory_bytes: 3104
#include<bits/stdc++.h>
#define Rep(i,a,b) for(register int i=(a);i<=(b);++i)
#define Repe(i,a,b) for(register int i=(a);i>=(b);--i)
#define pb push_back
#define mp make_pair
typedef unsigned long long uint64;
typedef unsigned int uint32;
typedef long long ll;
using namespace std;

namespace IO
{
    const uint32 Buffsize=1<<15,Output=1<<24;
    static char Ch[Buffsize],*S=Ch,*T=Ch;
    inline char getc()
	{
		return((S==T)&&(T=(S=Ch)+fread(Ch,1,Buffsize,stdin),S==T)?0:*S++);
	}
    static char Out[Output],*nowps=Out;
    
    inline void flush(){fwrite(Out,1,nowps-Out,stdout);nowps=Out;}

    template<typename T>inline void read(T&x)
	{
		x=0;static char ch;T f=1;
		for(ch=getc();!isdigit(ch);ch=getc())if(ch=='-')f=-1;
		for(;isdigit(ch);ch=getc())x=x*10+(ch^48);
		x*=f;
	}

	template<typename T>inline void write(T x,char ch='\n')
	{
		if(!x)*nowps++='0';
		if(x<0)*nowps++='-',x=-x;
		static uint32 sta[111],tp;
		for(tp=0;x;x/=10)sta[++tp]=x%10;
		for(;tp;*nowps++=sta[tp--]^48);
		*nowps++=ch;
	}
}
using namespace IO;

inline void file()
{
#ifndef ONLINE_JUDGE
	FILE*WA=freopen("water.in","r",stdin);
	FILE*TER=freopen("water.out","w",stdout);
#endif
}

const int MAXN=2e5+7;

static int n;

multiset<int,greater<int> >G;
multiset<int,greater<int> >::iterator it;

inline void init()
{
	read(n);
	static int x;
	Rep(i,1,n)read(x),G.insert(x);
}

static int ans;



inline void solve()
{
	while(!G.empty())
	{
		int u=*G.begin(),pr;G.erase(G.begin());
		for(pr=1;pr<=u;pr<<=1);
		if((it=G.find(pr-u))!=G.end())++ans,G.erase(it);
	}
	cout<<ans<<endl;
}

int main()
{
    init();
    solve();
    return 0;
}

Measured memory_bytes: 9600
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define FOR(I,A,B) for(ll I = (A); I < (B); ++I)
#define FORR(I,A,B) for(ll I = (B-1);I >= (A); --I)
const ll INF=1e18+3;
const ll MOD=1e9+7;

class comb{
	vector<ll> f,fr;
	ll MOD;
	public:
	//a^(p-1) = 1 (mod p)(p->Prime numbers)
	//a^(p-2) = a^(-1)
	ll calc(ll a,ll b,ll p){//a^(b) mod p   
		if(b==0)return 1;
		ll y = calc(a,b/2,p);y=(y*y)%p;
		if(b & 1) y = (y * a) % p;
		return y;
	}
	void init(ll n,ll mod){//input max_n
		MOD = mod;
		f.resize(n+1);
		fr.resize(n+1);
		f[0]=fr[0]=1;
		for(ll i=1;i<n+1;i++){
			f[i] = (f[i-1] * i) % mod;
			fr[i] = calc(f[i],mod-2,mod);
		}
	}
	ll nCr(ll n,ll r){
		return f[n] * fr[r] % MOD * fr[n-r] % MOD;
	}
};

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll h,w,a,b;
	cin>>h>>w>>a>>b;
	comb co;
	co.init(h+w+1,MOD);
	ll ans = 0;
	FOR(i,b,w){
		ll k = co.nCr(h-a-1+i,h-a-1)%MOD;
		k *= co.nCr(a+w-i-2,a-1);
		k %= MOD;
		ans += k;
		ans %= MOD;
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 3328
#include <atcoder/all>
#include <bits/stdc++.h>

#define repd(i, a, b) for (ll i = (a); i < (b); i++)
#define repb(i, n) for (ll i = (n)-1; i >= 0; i--)
#define rep(i, n) repd(i, 0, n)

using namespace std;

using ll = long long;
using ul = unsigned long long;
using ld = long double;
const ul mod = 1000000007;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n, q;
    cin >> n >> q;
    vector<ll> a(n);

    vector<ll> output;

    atcoder::fenwick_tree<ll> fw(n);
    rep(i, n) {
        ll x;
        cin >> x;
        fw.add(i, x);
    }
    rep(i, q) {
        bool num;
        cin >> num;
        if (!num) {
            ll p, x;
            cin >> p >> x;
            fw.add(p, x);
        } else {
            ll l, r;
            cin >> l >> r;
            output.push_back(fw.sum(l, r));
        }
    }

    for (auto elem : output) {
        cout << elem << endl;
    }
    return 0;
}



Measured memory_bytes: 14252
#include<iostream>
using namespace std;

int main(){
  
 	int L, R, d;
  	cin >> L >> R >> d;
  	
  	int count = 0;
  	
  	for(int i = L; i <= R; i++)
      if(i%d == 0) count++;
  	
  	cout << count << endl;
  
}

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


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

    ll n;
    cin>>n;
    ll p[n];
    for(int i=0;i<n;i++){
        cin>>p[i];
    }
    ll ans=0;
    for(int i=1;i<n-1;i++){
        if(p[i]<p[i+1] && p[i-1] < p[i] ) ans++;
        else if(p[i]>p[i+1] && p[i]<p[i-1]) ans++;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
def main():
  N = int(input())
  T, A = map(lambda i: int(i), input().split(' '))
  H = list(map(lambda i: int(i), input().split(' ')))
  diff = -1
  answer = 0
  for i in range(N):
    t = T - H[i] * 0.006
    if diff == -1 or abs(A - t) < diff:
      diff = abs(A - t)
      answer = i + 1
  print(answer)

main()


Measured memory_bytes: 3064
<?php
$input = trim(fgets(STDIN));
$input = str_replace(array("\r\n","\r","\n"), '', $input);
$array = explode(" ", $input);

$result1 = $array[0] * $array[1];
$result2 = $array[2] * $array[3];

if( $result1 > $result2 ) {
  echo $result1."\n";
} else {
  echo $result2."\n";
}

?>

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

using namespace std;

const int INF = 1 << 30;

int main()
{
  int N, W;
  cin >> N >> W;

  int dp[10001];
  fill_n(dp, 10001, INF);
  dp[0] = 0;

  for(int i = 0; i < N; i++) {
    int v, w;
    cin >> v >> w;
    for(int j = 10000; j >= v; j--) {
      dp[j] = min(dp[j], dp[j - v] + w);
    }
  }

  int ret = 0;
  for(int i = 0; i < 10001; i++) {
    if(dp[i] <= W) ret = max(ret, i);
  }
  cout << ret << endl;
}

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

int main() {
  int n;
  cin>>n;
  long long x1=0;
  vector<long long> a(n+1);
  for(int i=1;i<n+1;i++){
    cin>>a[i];
    x1+=a[i];
    if(i%2==0)x1-=2*a[i];
  }
  cout<<x1<<" ";
  for(int i=2;i<n;i++){
    x1=2*a[i-1]-x1;
    cout<<x1<<" ";
  }
  cout<<2*a[n-1]-x1;
  return 0;
}


Measured memory_bytes: 2048
#include <cstdio>
long long int mod = 1000000007;
long long int big(long long int b, long long int p){
	if (p == 1){
		return b;
	}
	long long int h = big(b, p / 2);
	if (p % 2 == 0){
		return (h * h) % mod;
	}else{
		return (((h * h) % mod) * b) % mod;
	}
}
int main(){
	int x, y;
	scanf("%d %d", &x, &y);
	if ((x + y) % 3 != 0){
		printf("0\n");
		return 0;
	}
	int n = (x + y) / 3;
	if (x < n || x > n * 2){
		printf("0\n");
		return 0;
	}
	int r = x - n;
	long long int ans = 1;
	while (r > 0){
		ans *= n;
		ans %= mod;
		ans *= big(r, mod - 2);
		ans %= mod;
		n--;
		r--;
	}
	printf("%lld\n", ans);
}

Measured memory_bytes: 256
import itertools
import math
k = int(input())
cnt = (k*(k+1))//2
b = [int(i) for i in range(1,k+1)]
for i in itertools.combinations(b,3):
    n = list(i)
    cnt += (math.gcd(math.gcd(n[0],n[1]),n[2]))*6
for t in itertools.combinations(b,2):
    m = list(t)
    cnt += (math.gcd(m[0],m[1]))*6

print(cnt)

Measured memory_bytes: 9244
#include<bits/stdc++.h>
#define LL long long
using namespace std;
int ws(LL n)
{
    int s=0;
    while(n>0)
        {
            s+=n%10;
            n/=10;
        }
        return s;
        }
int main()
{
    LL n,qaq,cnt=1;
    cin>>n;
    int ans=ws(n);qaq=n;
    while(qaq>=10)
    {
        qaq/=10;
        cnt*=10;
    }
    ans = max(ans,ws(n/cnt*cnt - 1));
    printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
#define ll long long
#define MOD (ll)1e9+7
#define REP(i,b,e) for(int (i)=b;(i)<e;(i)++)
const ll INF= 1LL << 60;
 
class UnionFind {
	vector<int> data;
public:
	UnionFind(int size) : data(size, -1) { }
	bool unionSet(int x, int y) {
		x = root(x); y = root(y);
		if (x != y) {
			if (data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
		return x != y;
	}
	bool findSet(int x, int y) {
		return root(x) == root(y);
	}
	int root(int x) {
		return data[x] < 0 ? x : data[x] = root(data[x]);
	}
	int size(int x) {
		return -data[root(x)];
	}
};
 
 
//入力
ll N;
ll C[30];
ll V[30];
ll dp[30][110];

int main(){
  cin >> N;
  for(int i=0;i<N;i++) cin >> V[i];
  for(int i=0;i<N;i++) cin >> C[i];
  ll ans=0;
  for(int i=0;i<N;i++){
    if(V[i]-C[i]>0)ans+=V[i]-C[i];
  }
  cout<<ans<<endl;
  
  return 0;
}

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

using namespace std;

#define lp(i,n) for(int i = 0; i <n;i++)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define MP make_pair
#define SZ(v) ((int)((v).size()))
typedef long long ll;

const ll MOD = 1e9 + 7;
const int OO = (int)1e6;
const int N = (int)1e7;

void init(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

double solve(int n,int k){

}
int main() {
	#   ifdef LOCAL_PROJECT
        freopen("in.txt", "r", stdin);
    #   endif
    int n,k;
    scanf("%d%d",&n,&k);
    double res =0.0;
    for(int i=1;i<=n;i++){
        int score_so_far=i;
        double prob  = 1.0/(double)n;
        while(score_so_far<k){
            score_so_far*=2;
            prob*=0.5;
        }
        res+=prob;
    }
    printf("%.12lf",res);
    return 0;
}

Measured memory_bytes: 256
def main():

    from collections import Counter
    import sys
    input = sys.stdin.buffer.readline

    N = int(input())
    a = list(map(int, input().split()))

    dp = [[[0]*(N+1) for _ in range(N+1)] for _ in range(N+1)]
    c = Counter(a)

    # メモ化再帰ではpypy3でもTLEするのでforループを使う
    # j==k==0の場合を計算 → k==0の場合を計算 → 一般の場合を計算
    for k in range(c[3]+1):
        for j in range(c[3]+c[2]-k+1):
            for i in range(N-j-k+1):
                if i == j == k == 0:
                    continue
                else:
                    tmp = N
                    if i > 0: # IndexError防止
                        tmp += dp[i-1][j][k]*i
                    if j > 0:
                        tmp += dp[i+1][j-1][k]*j
                    if k > 0:
                        tmp += dp[i][j+1][k-1]*k
                    dp[i][j][k] = tmp/(i+j+k) # 割り算をまとめないとTLE

    print(dp[c[1]][c[2]][c[3]])

if __name__ == '__main__':
    main()

Measured memory_bytes: 599560
#include <algorithm>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdint>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>


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

using namespace std;

template <class T, class U>
istream& operator>>(istream& is, pair<T, U>& pair)
{
    is >> pair.first >> pair.second;
    return is;
}

template <class T>
istream& operator>>(istream& is, T& collection)
{
    for (auto& item : collection)
        is >> item;
    return is;
}

template <class T>
T peak_and_pop(std::queue<T>& q)
{
    assert(!q.empty());
    T t = move(q.front());
    q.pop();
    return t;
};

struct edge_t {
    int color = 0;
    int a = 0;
    int b = 0;
    int next_node(int x) {
        assert(x == a || x == b);
        return x == a ? b : a;
    }
};

struct node_t {
    bool visited = false;
    vector<edge_t*> edges;
};

void solution()
{
    int N;
    cin >> N;
    vector<node_t> nodes(N);
    vector<edge_t> edges(N - 1);
    for (auto& e : edges) {
        cin >> e.a >> e.b;
        e.a -= 1;
        e.b -= 1;
        nodes[e.a].edges.push_back(&e);
        nodes[e.b].edges.push_back(&e);
    }
    queue<int> visit_queue;
    visit_queue.push(0);
    int max_color = 0;
    while (!visit_queue.empty()) {
        const int cur = peak_and_pop(visit_queue);
        int color = 1;
        int used_color = 0;
        for (auto* e : nodes[cur].edges) {
            if (e->color != 0) {
                used_color = e->color;
                break;
            }
        }
        for (auto* e : nodes[cur].edges) {
            if (e->color == 0) {
                if (color == used_color) {
                    color++;
                }
                e->color = color++;
                max_color = max(max_color, e->color);
                visit_queue.push(e->next_node(cur));
            }
        }
    }
    cout << max_color << '\n';
    for (auto& e : edges) {
        cout << e.color << '\n';
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solution();
    return 0;
}


Measured memory_bytes: 8576
g = Array.new(5){[]}
3.times do 
  a,b = gets.split.map(&:to_i)
  g[a] << b
  g[b] << a
end

t = []
1.upto(4) do |i| 
  if g[i].length == 1
    t << i
  end
end
a,b = g[t[0]][0],g[t[1]][0]
puts (a != b && g[a].length == 2 && g[b].length == 2) ? "YES" : "NO"

Measured memory_bytes: 1788
#include<bits/stdc++.h>
using namespace std;
long long f[2001][2001][2];
int n;
struct node{
	long long w;
	int id;
}a[2001];
inline bool mycmp(node x,node y){
	return x.w>y.w;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;++i) a[i].id=i,scanf("%lld",&a[i].w);
	sort(a+1,a+n+1,mycmp);
	for(int i=1;i<=n;++i){
		for(int j=0;j<i;++j){
			f[i][j+1][0]=max(f[i][j+1][0],f[i-1][j][1]+a[i].w*abs(a[i].id-j-1));
			if(j) f[i][j+1][0]=max(f[i][j+1][0],f[i-1][j][0]+a[i].w*abs(a[i].id-j-1));
			f[i][j][1]=max(f[i][j][1],f[i-1][j][1]+a[i].w*abs(a[i].id-n+(i-j)-1));
			if(j) f[i][j][1]=max(f[i][j][1],f[i-1][j][0]+a[i].w*abs(a[i].id-n+i-j-1));
		}
	}
	long long ans=0;
	for(int i=n;i<=n;++i)
		for(int j=1;j<=n;++j)
			ans=max(ans,max(f[i][j][0],f[i][j][1]));
	cout<<ans;
	return 0;
}

Measured memory_bytes: 42576
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for (ll i = 0; i < (n); ++i)
#define rrep(i,n) for (ll i = (n)-1; i >=0; --i)
#define ALL(a) a.begin(),a.end()
#define pb push_back
#define dame { puts("-1"); return 0;}
#define show(x) cerr<<#x<<" = "<<x<<endl;

using namespace std;
using ll = long long;
using ld = long double;
using pl = pair<ll, ll>;

typedef vector<ll> vl;
typedef vector<pl> vp;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }


// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const ll mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}
// combination mod prime
// https://www.youtube.com/watch?v=8uowVvQ_-Mo&feature=youtu.be&t=1619
struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
} c(200005);


int main() {
  ll k, n;
  cin >> n >> k;

  rep(i, k){
    ll j = i+1;
    mint ans = c(k-1, j-1) ;
    show(ans.x);
    ans *= c(n-k+1, j);
    show(ans.x);
    cout << ans.x << endl;
  }

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


Measured memory_bytes: 3328
while True:
    H,W = map(int,input().split())
    if H == 0 and W == 0:
        break

    for i in range(H):
        if i == 0 or i == H-1:
            print("#" * W)
        else:
            print("%s%s%s" %("#", "."*(W-2),"#"))

    print()


Measured memory_bytes: 5620
#include<bits/stdc++.h>
using namespace std;
#define MAX_N 200005
int N;
vector<int> G[MAX_N];
vector<int> rG[MAX_N];
int cnt[MAX_N];
int A[MAX_N];
int ans[MAX_N];

int main(){
  memset(ans, -1, sizeof(ans));
  
  cin>>N;
  for(int i=0;i<N;i++){
    int x;
    cin>>x;
    x--;
    G[x].push_back(i);
    rG[i].push_back(x);
    cnt[x]++;
    A[i]=x;
  }
  
  queue<int> Q;
  for(int i=0;i<N;i++){
    if(cnt[i]==0){
      Q.push(i);
      ans[i]=0;
    }
  }
  
  while(!Q.empty()){
    int pos=Q.front();
    Q.pop();

    if(ans[pos]==-1){
      set<int> st;
      for(int to:G[pos])st.insert(ans[to]);
      for(int i=0;;i++){
        if(st.count(i)==0){
          ans[pos]=i;
          break;
        }
      }
    }
    
    for(int to:rG[pos]){
      cnt[to]--;
      if(cnt[to]==0){
        Q.push(to);
      }
    }
  }
  

  map<int,bool> visited;
  for(int i=0;i<N;i++){
    if(visited[i])continue;
    if(cnt[i]==0)continue;
    int pos=i, cc=0;
    int maxm=-1,id=-1;
    
    while(!visited[pos]){
      visited[pos]=true;     cc++;
      set<int> st;
      for(int to:G[pos])
        if(ans[to]!=-1)
          st.insert(ans[to]);

      int u=0;
      while(st.count(u)==1)u++;
      
      if(maxm<u){
        maxm=u;
        id=pos;
      }
      pos=A[pos];
    }

    ans[id]=maxm;
    for(int j=0;j<cc*2;j++){
      id=A[id];
      set<int> st;
      for(int to:G[id])
        if(ans[to]!=-1)
          st.insert(ans[to]);
      for(int k=0;;k++){
        if(st.count(k)==0){
          ans[id]=k;
          break;
        }
      }
    }
    
  }

  for(int i=0;i<N;i++){
    if(ans[i]==-1){
      cout<<"IMPOSSIBLE"<<endl;
      return 0;
    }
    
    set<int> st;
    for(int to:G[i])st.insert(ans[to]);
    int f=0;
    while(st.count(f)>0)f++;
    if(f!=ans[i]){
      cout<<"IMPOSSIBLE"<<endl;
      return 0;
    }
  }
  cout<<"POSSIBLE"<<endl;
  return 0;
}


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

int main()
{
    int N, M; cin >> N >> M;
    int a, b, c, d;
    a = 1;
    b = (M+1)/2*2;
    c = b + 1;
    d = c + M/2*2;
    for (int i = 0; i < (M+1)/2; i++) {
        cout << a << " " << b << endl;
        a++; b--;
    }
    for (int i = 0; i < M/2; i++) {
        cout << c << " " << d << endl;
        c++; d--;
    }
}

Measured memory_bytes: 3624
/*
  AUTHOR:SOURABH
  CREATED:22:07:19
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ordered_set tree<pair<int, int> , null_type, less< pair<int, int> >, rb_tree_tag, tree_order_statistics_node_update>
#define ll long long int
#define ld long double
#define fi first
#define se second
#define pb push_back
#define pob pop_back
#define W while
#define fn(i,x) for(i=0;i<x;i++)
#define fs(i,s,x) for(i=s;i<x;i++)
#define fr(i,x) for(i=x;i>=0;i--)
#define fit(it,s) for(it=s.begin();it!=s.end();it++)
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vii vector<int>
#define vll vector<ll>
#define mii map<int,int>
#define mll map<ll,ll>
#define mod 1000000007
#define MAX 100005
#define M 32

using namespace std;
using namespace __gnu_pbds;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);

    ll i,c=0;
    string s,t;
    cin>>s>>t;
    c=0;
    fn(i,3)
    if(s[i]==t[i])c++;
    cout<<c;
    return 0;
}





















Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
static const int N = 100000;
int getComDiv(int x,int y){
	if(y==0)
		return x;
	if(x>=y)
		getComDiv(y,x%y); //x%y<=y
	else
		getComDiv(x,y%x);
}
int main(){
	int x,y;
	cin>>x>>y;
	cout<<getComDiv(x,y)<<endl;
	return 0;
} 


Measured memory_bytes: 3096
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <utility>
using namespace std;
using ll = long long;

struct UnionFind {
    vector<int> par;
    UnionFind(int n) : par(n,-1) {}
    void unite(int x, int y, int w = 0) {
        x = root(x); y = root(y);
        if (x == y) return;
        if (par[x] > par[y]) swap(x, y), w = -w;
        par[x] += par[y];
        par[y] = x;
        return;
    }
    bool same(int x, int y) { return root(x) == root(y); }
    int root(int x) {
        if(par[x] < 0) return x;
        int r = root(par[x]);
        return par[x] = r;
    }
    int sizeOf(int x) { return -par[root(x)]; }
};

int main() {
    cin.tie(0); ios_base::sync_with_stdio(false);
    int N,x,y;cin >> N;

    int MAX = 100010;
    UnionFind uf(MAX*2);
    for(int i=0;i<N;++i){
        cin >> x >> y;
        uf.unite(x, y + MAX);
    }

    map<int,long long> mx, my;
    for(x = 0; x < MAX; ++x) ++mx[uf.root(x)];
    for(y = MAX; y < MAX*2; ++y) ++my[uf.root(y)];
    long long ans = 0;
    for(int i=0; i < MAX*2; ++i) ans += mx[i] * my[i];
    cout << ans - N << '\n';
    return 0;
}

Measured memory_bytes: 26112
n,m=map(int,input().split())
p=[True]*n
y=[0]*n
i=0
l=0
for  _ in range(m):
    k,o=input().split()
    k=int(k)-1
    if p[k]==True:
        if o=="AC":
            i+=1
            p[k]=False
        else:
            y[k]+=1
for e in range(n):
    if p[e]==False:
        l+=y[e]
print(i,l)


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

using namespace std;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	string s, t;
	cin >> s >> t;
	int ans = t.size();
	for (int i = 0; i <= s.size() - t.size(); i++){
		int dif = 0;
		for (int j = 0; j < t.size(); j++){
			if (s[i + j] != t[j])dif++;
		}
		ans = min(ans, dif);
	}
	cout << ans;
	//system("pause");
	return 0;
}


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

int main(){
	
	long n,m; cin>>n>>m;
	long long arr[n]; long long co = 0; long long sum = 0;
	for(int i = 0; i < n; i++) { cin>>arr[i]; sum += arr[i]; }
	double need = ((double)sum/(4.0*(double)m));
	for(int i = 0; i < n; i++){
		if(arr[i] >= ceil(need)) co++;
	}
	if(co >= m) cout<<"Yes"<<"\n";
	else cout<<"No"<<"\n";
	
	
	
	
}

Measured memory_bytes: 256
N,X = map(int,input().split())
m = [int(input()) for i in range(N)]
m.sort()
ans = 0
for i in range(N):
    X -= m[i]
    if X < 0:
        break
    ans += 1
if X > 0:
    ans += X // min(m)
print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
#include <stack>
#include <functional>

#ifdef LOCAL
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
    #define eprintf(...) 42
#endif

#define rep_(i, a_, b_, a, b, ...) for (int i = (a), i##_len = (b); i < i##_len; ++i)
#define rep(i, ...) rep_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define reprev_(i, a_, b_, a, b, ...) for (int i = (b-1), i##_min = (a); i >= i##_min; --i)
#define reprev(i, ...) reprev_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define all(x) (x).begin(), (x).end()
template <class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template <class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
// template <class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair <int,int> P;
typedef long double ld;

constexpr int MOD = 998244353;

// + - * / ^
int mod(int a)
{
    int res = a % MOD;
    if(res < 0) {
        return res + MOD;
    }
    return res;
}
int mul_mod(int a, int b)
{
    ll res = ((ll)a * (ll)b) % MOD;
    return mod((int)res);
}
int pow_mod(int a, int b)
{
    ll res = 1;
    while (b > 0) {
        if(b & 1) {
            res = res * (ll)a % (ll)MOD;
        }
        a = mul_mod(a, a);
        b >>= 1;
    }
    return (int)res;
}
int inv_mod(int a)
{
    return pow_mod(a, MOD - 2);
}
int div_mod(int a, int b)
{
    return mul_mod(a, inv_mod(b));
}

// ! C
constexpr int FAC_MAX = 3000001;
ll fac[FAC_MAX], finv[FAC_MAX], inv[FAC_MAX];
void com_init()
{
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < FAC_MAX; 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;
    }
}
ll com_mod(int a, int b){
    if (a < b) return 0;
    if (a < 0 || b < 0) return 0;
    return fac[a] * (finv[b] * finv[a - b] % MOD) % MOD;
}


int main (void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, s;  cin >> n >> s;
    vector<int> a(n); rep (i, n) cin >> a[i];
    sort(all(a));
    vector<vector<ll>> dp(n + 1, vector<ll>(s + 3001));
    dp[0][0] = pow_mod(2, n);
    rep (i, n) {
        rep (j, s + 1) {
            dp[i + 1][j + a[i]] = mod(dp[i + 1][j + a[i]] + div_mod(dp[i][j], 2));
            dp[i + 1][j] = mod(dp[i + 1][j] + dp[i][j]);
            // dp[i + 1][j] = mod(dp[i + 1][j] + div_mod(dp[i][j], 2));
        }
    }
    ll ans = 0;
    // rep (i, 1, n + 1) ans = mod(ans + dp[i][s]);
    // cout << ans << "\n";
    rep (i, n + 1) {
        rep (j, s + 1) eprintf("%d ", dp[i][j]); eprintf("\n");
    }
    cout << dp[n][s] << "\n";
    return 0;
}

Measured memory_bytes: 144148
#include <iostream>

using namespace std;

int main() {
    int day[2][13] = { { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 },
    { 0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 } };
    int y1, m1, d1, y2, m2, d2;
    while (cin >> y1 >> m1 >> d1 >> y2 >> m2 >> d2) {
        if (y1 < 0 || m1 < 0 || d1 < 0 || y2 < 0 || m2 < 0 || d2 < 0) {
            break;
        }
        int ans = 0;
        for (int i = y1, j = m1, k = d1; i <= y2; i++) {
            for (; j <= 12; j++) {
                for (; k <= day[(i % 4 == 0 && i % 100 != 0) || i % 400 == 0][j]; k++) {
                    if (i == y2 && j == m2 && k == d2) {
                        goto Fin;
                    }
                    ans++;
                }
                k = 1;
            }
            j = 1;
        }
    Fin:;
        cout << ans << endl;
    }
    return 0;
}

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

using namespace std;
typedef long long int ll;

#define INF 1 << 30
#define REP(i,n) for(ll i=0; i<(ll)(n); i++)
#define FOR(i,k,n) for(ll i=(k);i<(ll)(n);i++)



vector<bool> gen_sosuu(vector<bool> sosuu){
  ll size = sosuu.size();
  REP(i,size){
    sosuu[i] = true;
  }
  sosuu[0] = false;
  sosuu[1] = false;
  sosuu[2] = true;
  FOR(i,2,sqrt(size)+1){
    if(sosuu[i] == false) continue;
    for(ll j = 2; i*j<size;j++){
      sosuu[i*j] =false;
    }
  }
  return sosuu;
}

int n;
ll cnt = 0;
int f[200000];

int main(){
  cin >> n;
  REP(i,n){
    int x;
    cin >> x;
    x--;
    f[x] = i;
  }
  ll ans = 0;
  int prev = f[0];
  cnt++;
  FOR(i,1,n){
    if(prev < f[i]) cnt++;
    else{
      ans = max(ans,cnt);
      cnt = 1;
    }
    prev = f[i];
  }
  ans = max(ans,cnt);
  cout << n-ans << endl;
}


/*
ll n;
ll cnt = 0;
map<ll,ll> mp;
int main(){
  cin >> n;
  REP(i,n){
    ll k;
    cin >> k;
    k--;
    mp[k] = i;
  }
  ll l,r;
  if(n%2==1){
    l = r = mp[n/2];
  }else{
    l = mp[n/2-1];
    r = mp[n/2];
  }
  if(l>r){
    cnt++;
    l = -1;
  }
  FOR(i,1,n/2+(n%2==1)){
    if(mp[n/2-1-i+(n%2==1)] > l){
      cnt++;
      l = -1;
    }
    //cout << n/2-1-i+(n%2==1) << endl;
    if(mp[n/2+i-(n%2==1)] < r){
      cnt++;
      r = INF;
    }
    l = min(l,mp[n/2-1-i+(n%2==1)]);
    r = max(r,mp[n/2+i-(n%2==1)]);
  }
  ll ans = cnt;
  cnt = 0ll;

  if(n%2==1){
    l = r = mp[n/2];
  }else{
    l = mp[n/2-1];
    r = mp[n/2];
  }
  if(l>r){
    cnt++;
    r = INF;
  }
  FOR(i,1,n/2+(n%2==1)){
    if(mp[n/2-1-i+(n%2==1)] > l){
      cnt++;
      l = -1;
    }
    if(mp[n/2+i-(n%2==1)] < r){
      cnt++;
      r = INF;
    }
    l = min(l,mp[n/2-1-i+(n%2==1)]);
    r = max(r,mp[n/2+i-(n%2==1)]);
  }
  cout << min(cnt,ans) << endl;
}
*/


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

int main(){
  vector<int> v(5);
  int k;
  for(auto& x:v)
    cin >> x;
  cin >> k;
  string ans = "Yay!";
  for(int i=0;i<5;i++){
    for(int j=0;j<i;j++){
      if(v.at(i)-v.at(j) > k)
        ans = ":(";
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
package main

import "fmt"

func main() {
	var n, a, b int
	fmt.Scan(&n, &a, &b)

	res := n / (a + b) * a
	r := n % (a + b)
	if r > a {
		res += a
	} else {
		res += r
	}
	fmt.Println(res)
}


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

#define ll long long
#define INF_LL 1LL << 60
#define INF 99999999
#define MOD (ll)1000000007
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define REP(i, a, n) for(int i = a; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

void put_double(double obj){printf("%.12f\n",obj);};

template < typename T > std::string to_string( const T& n )
{
    std::ostringstream stm ;
    stm << n ;
    return stm.str() ;
}

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }


int main()
{
    int N,A;
    cin >> N >> A;

    cout << N*N-A << endl;
}


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

using namespace std;

int main() {
    int a[3];
    cin >> a[0] >> a[1] >> a[2];

    int b[] = { abs(a[0] - a[1]), abs(a[1] - a[2]), abs(a[2] - a[0]) };
    sort(b, b + 3);

    cout << b[0] + b[1] << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 1000000
using namespace std;
int n,m;
int a[N];
int gcd(int x,int y){return !y?x:gcd(y,x%y);}
int main(){
	scanf("%d %d",&n,&m);
	for (int i=1;i<=n;i++)scanf("%d",&a[i]);
	int x=a[1];
	for (int i=2;i<=n;i++)x=gcd(x,a[i]);
	for (int i=1;i<=n;i++)
		if (m<=a[i]){
			if (!((a[i]-m)%x)){
				printf("POSSIBLE\n");
				return 0;
			}
		}
	printf("IMPOSSIBLE\n");
	return 0;
}

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




ll N, M;

struct job{
	ll day;
	ll reward;
};

class Comp {
public:
	bool operator() ( const job &l, const job &r ){
		return l.reward < r.reward;
	};
};


int main(){
	cin >> N >> M;
	
	vector<job> v(N);
	for ( int i = 0; i < N; i++ ){
		cin >> v[i].day >> v[i].reward;
	}
	sort(v.begin(),v.end(),[](const job &l, const job &r){
		return l.day < r.day;
	});
	
	ll total_reward = 0;
	auto it = v.begin();
	
	// 最終日から、その日にすべき仕事を計算する
	priority_queue<job,vector<job>,Comp> q;
	for ( int day = M-1; day >= 0; day-- ){
		while ( it != v.end() && day + it->day <= M ){
			q.push(*it);
			it++;
		}
		
		if ( !q.empty() ){
			total_reward += q.top().reward;
			//cout << day << " " << q.top().day << " " << q.top().reward << endl;
			q.pop();
		}
	}
	
	
	
	cout << total_reward << endl;
	
	return 0;
}



Measured memory_bytes: 3956
#include <iostream>
#include <vector>

#define ll long long
using namespace std;

ll mod = 1e9 + 7;

ll calc_pow(ll x, ll pow) {
    if (pow <= 0) return 1;
    long a = calc_pow(x, pow / 2);
    a = a * a % mod;
    if (pow % 2 == 1) a *= x;
    return a % mod;
}

int main() {
    string s;
    cin >> s;
    ll c = 0;
    ll cq = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == 'C')c++;
        if (s[i] == '?')cq++;
    }
    ll a = 0;
    ll aq = 0;
    vector<ll> q(4);
    for (int i = 0; i < 4; i++)q[i] = calc_pow(3, cq - i);
    ll ret = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == 'C')c--;
        if (s[i] == '?')cq--;

        if (s[i] == 'B') {
            ret += a * c * q[0];
            ret %= mod;
            ret += (a * cq + aq * c) * q[1];
            ret %= mod;
            ret += aq * cq * q[2];
            ret %= mod;
        }
        if (s[i] == '?') {
            ret += a * c * q[1];
            ret %= mod;
            ret += (a * cq + aq * c) * q[2];
            ret %= mod;
            ret += aq * cq * q[3];
            ret %= mod;
        }

        if (s[i] == 'A')a++;
        if (s[i] == '?')aq++;
    }
    cout << ret << endl;
    return 0;
}

Measured memory_bytes: 512
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		try(Scanner sc = new Scanner(System.in)) {

			// 人数
			int n = sc.nextInt();
			List<Map<Integer, Integer>> list = new ArrayList<>();
			for(int i = 0 ; i < n ; i++) {
				Map<Integer, Integer> map = new HashMap<>();
				int a = sc.nextInt();
				for(int j = 0 ; j < a ; j++) {
					map.put(sc.nextInt(), sc.nextInt());
				}
				list.add(map);
			}
			// 全検索
			int ans = 0;
			ONE: for(int i = 0 ; i < 1 << n ; i++) {
				// 正直判定
				Integer[] judge = new Integer[n];
				int sum = 0;
				for(int j = 0 ; j < n ; j++) {
					if((1 & i >> j) == 1 || (judge[j] != null && judge[j] == 1)) {
						judge = isHonest(judge, list, j);
						if(judge == null) continue ONE;
					}
				}
				for(Integer j : judge) {
					if(j != null && j.intValue() == 1) {
						sum++;
					}
				}
				ans = Math.max(ans, sum);
			}

			System.out.println(ans);

		}

	}

	private static Integer[] isHonest(Integer[] judge, List<Map<Integer, Integer>> list, int listIndex) {
		for(Map.Entry<Integer, Integer> entry : list.get(listIndex).entrySet()) {
			if(judge[entry.getKey() - 1] == null && entry.getValue() == 1) {
				judge[entry.getKey() - 1] = entry.getValue();
				judge = isHonest(judge, list, entry.getKey() - 1);
				if(judge == null) {
					return null;
				}
			}
			else if(judge[entry.getKey() - 1] == null && entry.getValue() == 0) {
				judge[entry.getKey() - 1] = entry.getValue();
			}
			else if(judge[entry.getKey() - 1].intValue() != entry.getValue()) {
				return null;
			}
		}
		if(judge != null) {
			if(judge[listIndex] == null || judge[listIndex] != 0) {
				judge[listIndex] = 1;
			} else {
				return null;
			}
		}
		return judge;
	}

}


Measured memory_bytes: 34920
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod = 1e9 + 7;

int gcd(int x, int y) {
    if (x < y) swap(x, y);
    int r = x%y;
    if (r == 0) {
        return y;
    }
    return gcd(y, r);
}

ll mypow(ll x, ll n) {
    if (n == 0) return 1;
    if (n%2 == 0) return mypow(((x%mod)*(x%mod))%mod, n/2);
    else return ((x%mod) * mypow(((x%mod)*(x%mod))%mod, (n-1)/2))%mod;
}

int main(){
    vector<vector<int>> c(3, vector<int>(3));
    for (int i=0; i<3; i++) {
        for (int j=0; j<3; j++) {
            cin >> c.at(i).at(j);
        }
    }
    vector<int> a(3);
    vector<int> b(3);
    bool ans = false;
    for (a.at(0)=0; a.at(0)<=c.at(0).at(0); a.at(0)++) {
        ans = true;
        for (int i=0; i<3; i++) {
            b.at(i) = c.at(0).at(i) - a.at(0);
            if (b.at(i) < 0) {
                ans = false;
                break;
            }
            for (int j=1; j<3; j++) {
                if (i == 0) {
                    a.at(j) = c.at(j).at(i) - b.at(i);
                    if (a.at(j) < 0) {
                        ans = false;
                        break;
                    }
                }
                else {
                    if (a.at(j) + b.at(i) != c.at(j).at(i)) {
                        ans = false;
                        break;
                    }
                }
            }
        }
        if (ans) break;
    }
    if (ans) cout << "Yes" << endl;
    else cout << "No" << endl;
}

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

using namespace std;
#ifdef _DEBUG
#define _GLIBCXX_DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

#define int long long
typedef __int128_t Int;
#define DBG 1
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define rrep(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define loop(n) rep(loop, (0), (n))
#define all(c) begin(c), end(c)
const int INF =
    sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
const double PI = acos(-1);
const double EPS = 1e-9;
#define fi first
#define se second
#define eb emplace_back
using pii = pair<int, int>;
// template<class T> ostream &operator<<(ostream &os,T &t){dump(t);return os;}
template <typename T, typename S>
istream &operator>>(istream &is, pair<T, S> &p) {
  is >> p.first >> p.second;
  return is;
}
template <typename T> void printvv(const vector<vector<T>> &v) {
  cerr << endl;
  rep(i, 0, v.size()) rep(j, 0, v[i].size()) {
    if (typeid(v[i][j]) == typeid(INF) and v[i][j] == INF) {
      cerr << "INF";
    } else
      cerr << v[i][j];
    cerr << (j == v[i].size() - 1 ? '\n' : ' ');
  }
  cerr << endl;
}

#ifndef _DEBUG
#define printvv(...)
#endif
void YES(bool f) { cout << (f ? "YES" : "NO") << endl; }
void Yes(bool f) { cout << (f ? "Yes" : "No") << endl; }
template <class T> bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class T> bool chmin(T &a, const T &b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}

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

  int N, x;
  cin >> N >> x;
  vector<int> a(N);
  rep(i, 0, N) { cin >> a[i]; }
  sort(all(a));
  int ans = 0;
  int sum = 0;
  while (ans < N and x>0) {
    if(a[ans]<=x){
      x-=a[ans++];
    }
    else break;
  }
  if(x>0 and ans==N)ans--;
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(void)
{
	int x;
	
	cin>>x;
	
	int h=x/3600;
	x=x%3600;
	
	int m=x/60;
	x=x%60;
	
	int s=x;
	
	cout<<h<<":"<<m<<":"<<s<<endl;
	
	return 0;
}


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

int main() {
	ios_base::sync_with_stdio( false );

	int N;
	cin >> N;

	vector<int> a( N+1 );
	for( int i = 1; i <= N; ++i ) {
		cin >> a[i];
	}

	vector<bool> b( N+1 );
	int result = 0;

	for( int i = 1; i != 2; i = a[i] ) {
		if( b[a[i]] ) {
			result = -1;
			break;
		}

		b[a[i]] = true;
		result += 1;
	}

	cout << result << endl;
	return 0;
}


Measured memory_bytes: 640
def Base_10_to_n(X, n):
    if (int(X/n)):
        return Base_10_to_n(int(X/n), n)+str(X%n)
    return (str(X%n))

X,n=map(int,input().split())
k = Base_10_to_n(X,n)
print(len(k))

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef set<int> S;
typedef queue<int> Q;
typedef queue<P> QP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int MOD = 1000000007;
#define dame { puts("-1"); return 0;}
#define yn {puts("YES");}else{puts("NO");}
  
int main() {
  int N;
  cin >> N;
  int K = -1;

  srep(k,1,1000) {
    if(k*(k-1)/2 == N) {
      K = k;
      break;
    }
  }
  if(K == -1) {
    cout << "No" << endl;
    return 0;
  }
  vvi ans(K);
  int k = 1;
  rep(i,K){
    srep(j,i+1,K) {
      ans[i].push_back(k);
      ans[j].push_back(k);
      k++;
    }
  }
  cout << "Yes" << endl;
  cout << K << endl;
  rep(i,K) {
    cout << sz(ans[i]) << " ";
    rep(j,sz(ans[i])){
      cout << ans[i][j] << " ";
    }
    cout << endl;
  }
  return 0;
}

Measured memory_bytes: 2304
#include<iostream>
#include<string>
#include<algorithm>
#include<functional>
#include<bitset>
#include<vector>
#include<set>
#include<map>
#include<list>
#include<stack>
#include<queue>
#include<deque>
#include<cstdio>
#include<cstdlib>
#include<cmath>
using namespace std;

int main(){
    string a, b;
    cin >> a >> b;
    a += a;
    if(a.find(b)!=-1)cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}




Measured memory_bytes: 3200
#import <stdio.h>
int main(){
    long long W,H,X,Y;
    scanf("%lld %lld %lld %lld",&W,&H,&X,&Y);
    printf("%Lf ", (long double)W*H/2);
    puts(W%2==0&&H%2==0&&X==W/2&&Y==H/2 ? "1" : "0");
}


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

int main() {

    int a, b, c, d;
    cin >> a >> b >> c >> d;
    if ( a + b < c + d) {
        cout << "Right" << endl;
    }
    else if ( a + b > c + d) {
        cout << "Left" << endl;

    }
    else {
        cout << "Balanced" << endl;
    }

}

//ぽっぽよポーランド





Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n) for(int i = 0; i < n; i++)
#define CloseIO std::ios::sync_with_stdio(false)
const int N = 4000 + 200;
const ll Mod = 100;
const ll INF = pow(2,32)-1;
int main(){
  int n;
  cin>>n;
  vector<pair<int,int> > a(n);
  rep(i,n){
    int x,y;
    cin>>x>>y;
    a[i] = {x,y};
  }
  int sum = 0;
  sort(a.begin(),a.end());
  map<pair<int,int>,int> mp;
  int mx = 0;
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n && j != i; j++){
      pair<int,int> p;
      p = {a[i].first - a[j].first, a[i].second - a[j].second};
      mp[p]++;
      if(mp[p] > mx) mx = mp[p];
    }
  }
  cout<<n-mx<<endl;
  return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
#define forr(i, a, b) for(int i = (a); i < (b); i++)
#define rep(i,n) for(int i = 0; i < (n); i++)
#define rrep(i,n) for(int i = 1; i <= (n); i++)
#define ALL(a) (a.begin()),(a.end())
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll, ll> LP;
const ll LINF = 1LL<<60;
const int INF = 1001001001;

/* --------------------------------------------------- */

int main() {
    int n;
    cin >> n;
    int ans = 10000 - n;
    ans %= 1000;
    cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 3624
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
 
#define rep(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define all(v) (v).begin(), (v).end()
#define rev(s) (s).rbegin(), (s).rend()
#define MP make_pair
#define X first
#define Y second
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;

int main(){
	int n, m;
	while(cin >> n >> m, n|m){
		vector<int> v(n);
		rep(i, n) cin >> v[i];
		sort(rev(v));
		int sum = 0;
		rep(i, n){
			if((i+1)%m) sum += v[i];
		}
		cout << sum << endl;
	}
	return 0;
}

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

int main() {
  int H, N;
  cin >> H >> N;
  vector<int> DP(H + 1, 1e9);
  DP.at(0) = 0;
  for (int i = 0, A, B; i < N && cin >> A >> B; i++)
    for (int j = 0; j < H; j++)
      DP.at(min(j + A, H)) = min(DP.at(min(j + A, H)), DP.at(j) + B);
  cout << DP.at(H) << "\n";
}

Measured memory_bytes: 256