akhauriyash/Code-Regression huggingface dataset:
MOD = 10**9+7
N, M = gets.split.map(&:to_i)
if (N-M).abs > 1
  puts 0
  exit(0)
end

def fact(n)
  (1..n).inject(1){|r,i|r*i%MOD}
end

if N==M
  f = fact(N)
  puts f*f*2%MOD
else
  N, M = M, N if N < M
  f = fact(M)
  puts f*f*N%MOD
end


Measured memory_bytes: 1788
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
using ll = long long ;
using P = pair<int,int> ;
using pll = pair<long long,long long>;
constexpr int INF = 1e9;
constexpr long long LINF = 1e17;
constexpr int MOD = 1000000007;

int main(){
    int n;
    cin >> n;
    bool ok = false;
    int k = 0;
    for(int p=1;p*(p-1)<=2*n;p++){
        if(p*(p-1)==2*n){
            ok = true;
            k = p;
            break;
        }
    }
    if(!ok){
        cout << "No" << endl;
        return 0;
    }
    cout << "Yes" << endl;
    cout << k << endl;
    vector<vector<int>> ans(k);
    int i = 1;
    rep(j,k){
        for(int p=j+1;p<k;p++){
            ans[j].push_back(i);
            ans[p].push_back(i);
            ++i;
        }
    }
    rep(i,k){
        cout << k-1 << " ";
        rep(j,k-1){
            cout << ans[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

Measured memory_bytes: 2304
#include <algorithm>
#include <iostream>
#include <complex>
#include <cstdio>
#include <cmath>
#include <utility>
#include <vector>
#include <tuple>
using namespace std;
using W = double;
using P = complex<W>;
using L = pair<P,P>;
using C = pair<P,W>;
using Poly = vector<P>;
#define X real()
#define Y imag()
const W EPS = (1e-10), pi = acos(-1);

bool cmp_y(const P &a, const P &b){
  return a.Y != b.Y ? a.Y < b.Y : a.X < b.X;
}

double dot(P a, P b){ return a.X * b.X + a.Y * b.Y;}
W cross(P a, P b){ return a.X * b.Y - a.Y * b.X;}

Poly convex_hull(Poly v){
  int n = v.size(), k = 0;
  sort(v.begin(), v.end(), cmp_y);
  Poly r(2*n);
  for(int i = 0; i < n; i++){
    while(k>1 && cross(r[k-1]-r[k-2],v[i]-r[k-2]) < -EPS) k--;
    r[k++] = v[i];
  }
  for(int i = n-2, t = k; i >= 0; i--){
    while(k>t && cross(r[k-1]-r[k-2],v[i]-r[k-2]) < -EPS) k--;
    r[k++] = v[i];
  }
  r.resize(k-1);
  return r;
}

struct UnionFind{
private:
  vector<int> data;
public:
  int N;
  UnionFind(int n) : data(n, -1), N(n){}
  bool unite(int x, int y){
    x = find(x);
    y = find(y);
    if(x == y) return false;
    --N;
    if(data[y] < data[x]) swap(x,y);
    data[x] += data[y];
    data[y] = x;
    return true;
  }
  bool same(int x, int y){ return find(x) == find(y); }
  int find(int x){
    if(data[x] < 0) return x;
    return data[x] = find(data[x]);
  }
  int size(int x){ return -data[find(x)]; }
};

int main(){
  int V, R;
  cin >> V >> R;
  Poly ps;
  for(int i = 0; i < V; ++i){
    W x, y;
    cin >> x >> y;
    ps.emplace_back(x,y);
  }
  Poly ch = convex_hull(ps);
  vector<tuple<W,int,int>> E;
  for(int i = 0; i < R; ++i){
    int s, t;
    cin >> s >> t;
    --s,--t;
    E.emplace_back(abs(ps[s]-ps[t]),s,t);
  }
  sort(E.begin(), E.end());
  vector<int> h_idx;
  for(auto p : ch){
    for(int i = 0; i < V; ++i){
      if(abs(p-ps[i]) < EPS){
        h_idx.push_back(i);
        break;
      }
    }
  }
  UnionFind uf(V);
  W ans = 0;
  for(size_t i = 0; i < h_idx.size(); ++i){
    int u = h_idx[i], v = h_idx[(i+1)%h_idx.size()];
    ans += abs(ps[u]-ps[v]);
    uf.unite(u,v);
  }
  for(auto e : E){
    W d;
    int u, v;
    tie(d,u,v) = e;
    if(!uf.unite(u,v)) continue;
    ans += d;
  }
  printf("%.12f\n",ans);
}



Measured memory_bytes: 3412
#include <iostream>
#include <string>
#include <cstdio>
#include <cstdlib>

using namespace std;

int main(void){
    string input;
    
    while(getline(cin, input), !cin.eof()){
        int a, b, c;
        sscanf(input.c_str(), "%d %d %d", &a, &b, &c);
        
        if(a < b && b < c){
            printf("Yes\n");
        }
        else{
            printf("No\n");
        }
        
    }
    
    return(0);
}



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

int main(){
    int n,d;
    cin >> n >> d;
    vector <vector <int>> x(n, vector <int> (d));
    rep(i,n){
        rep(j,d){
            cin >> x[i][j];
        }
    }

    int ans;
    ans=0;
    
    double k;
    rep(i,n-1){
        rep(j,n-i-1){
            k=0;
            rep(l,d){
                k+=(x[i][l]-x[i+j+1][l])*(x[i][l]-x[i+j+1][l]);
            }
            k=pow(k,0.5);
            if(int(k)==k){
                ++ans;
            }
        }
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cctype>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <utility>
#include <string>
#include <functional>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <bitset>

#define PB push_back
#define MP make_pair
#define YES cout<<"YES"<<endl
#define Yes cout<<"Yes"<<endl
#define NO cout<<"NO"<<endl
#define No cout<<"No"<<endl
#define INF (1<<30)
#define LLINF (1LL<<60)
#define MOD 1000000007
#define REP(i, n) for(int i=0;i<n;i++)
using ll = long long;
using namespace std;

int main() {
    int n, a, x[51];
    ll dp[51][51][5000] = {};
    cin >> n >> a;
    for (int i = 1; i <= n; i++) {
        cin >> x[i];
    }
    for (int j = 0; j <= n; j++) {
        for (int k = 0; k <= n; k++) {
            for (ll s = 0; s <= 5000; s++) {
                if (j == 0 && k == 0 && s == 0)dp[j][k][s] = 1;
                else if (j >= 1 && s < x[j])dp[j][k][s] = dp[j - 1][k][s];
                else if (j >= 1 && k >= 1 && s >= x[j])dp[j][k][s] = dp[j - 1][k][s] + dp[j - 1][k - 1][s - x[j]];
                else dp[j][k][s] = 0;
            }
        }
    }
    ll ans = 0;
    for (ll k = 1; k <= n; k++) {
        ans += dp[n][k][k*a];
    }
    cout << ans << endl;
    return 0;
}


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

using namespace std;
int n;
const int INF = 1e9 + 5;
using ll = long long;

int main() {
    scanf("%d", &n);
    vector<int> h(n);
    for (int &x : h) {
        scanf("%d", &x);
    }

    vector<int> dp(n, INF);
    dp[0] = 0;
    for (int i = 0; i < n; ++i) {
        for (int j : {i + 1, i + 2}) {
            if (j < n) {
                dp[j] = min(dp[j], dp[i] + abs(h[i] - h[j]));
            }
        }
    }
    printf("%d\n", dp[n - 1]);

    return 0;
}


Measured memory_bytes: 4052
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; i++)
#define repr(i, n) for(int i=n; i>=0; i--)
#define reps(i, s, e) for(int i=s; i<e; i++)
#define inf 1e10
#define vsort(v) sort(v.begin(), v.end())
#define vsortr(v) sort(v.begin(), v.end(), greater<lli>())
#define sz(x) x.size()
#define ceil(a, b) (a+b-1)/b
#define ok cout << "ok" << endl;
using namespace std;
using lli = long long int;
template<typename T> bool chmax(T &a, T &b){ if(a<b) { a=b; return 1; }}
template<typename T> bool chmin(T &a, T &b){ if(b<a) { a=b; return 1; }}
template<typename T> T gcd(T a, T b){ if(b==0) return a; return gcd(b, a%b); }
template<typename T> T lcm(T a, T b){ return a*b/gcd(a, b); }
template<typename T> T vdebug(vector<T> v){ for(auto vv : v){ cout << vv << " "; } cout << endl; }
template<typename T> T arrdebug(T arr[], int n){ rep(i, n){ cout << arr[i] << " "; } cout << endl; }
void ans(bool b){ if(b) cout << "Yes" << endl; else cout << "No" << endl; }
void ans2(bool b){ if(b) cout << "YES" << endl; else cout << "NO" << endl; }
int dx[] = {1, -1, 0, 0, 1, -1, 1, -1};
int dy[] = {0, 0, 1, -1, 1, -1, -1, 1};


lli n, res=0;
 
void rec(lli num){
	if(num > n) return;
	
	lli tmp = num;
	vector<int> marker(10, 0);
	
	while(tmp > 0){
		marker[tmp%10] = 1;
		tmp/=10;
	}
	
	if(marker[3] && marker[5] && marker[7]) res++;
	
	//vdebug(marker);
	//cout << num << " " << res << endl;
	
	rec(num*10 + 3);
	rec(num*10 + 5);
	rec(num*10 + 7);
}
	
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n;
    
    rec(0);
    
    cout << res << endl;
    
  	return 0;
}

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

int binarySearch(vector<int>& S, int T)
{
	int right = S.size();
	int left = 0;

	while (left < right) {
		int mid = (left + right) / 2;

		if (S.at(mid) == T) return 1;
		else if (T < S.at(mid)) right = mid;
		else left = mid + 1;
	}
	return 0;
}


int main(void) {
	int N, Q, T;
	cin >> N;
	vector<int> S(N);
	for (int i = 0; i < N; i++) cin >> S.at(i);

	int ans = 0;
	cin >> Q;
	for (int i = 0; i < Q; i++)
	{
		cin >> T;
		if (binarySearch(S, T)) ans++;
	}

	cout << ans << endl;

	return 0;
}


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

int arr[100010];
int dp[100010];

int main (){
	int n,k;
	cin >> n >> k;
	for(int i = 1; i <= n; i++){
		cin >> arr[i];
	}
	dp[0] = 0;
	dp[1] = 0;
	dp[2] = abs(arr[1] - arr[2]);
	
	for(int i = 3; i <= n; i++){
		dp[i] = 2e9;
		for(int j = 1; j <= k; j++){
			if(i - j > 0) dp[i] = min(abs(arr[i] - arr[i - j]) + dp[i - j], dp[i]);
		}
		
	}
	
	cout << dp[n] << endl;
}

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

using namespace std;

int main(){
    
    int A, B, C, K;
    cin >> A >> B >> C >> K;

    int sum = 0;
    int taken = 0;

    if( K > A){
        taken += A;
        sum += A;
    }else{
        taken = K;
        sum+= K;
    }

    if(taken < K){
        int take = min( K - taken, B);
        taken += take;
        sum+= 0;
    }

    if(taken < K){
        int take = min(K-taken, C);
        taken += take;
        sum += take * -1;
    }

    cout << sum << endl;

}

Measured memory_bytes: 3676
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<cstring>
using namespace std;
typedef pair<int, int> P;
typedef pair<P, int> T;
#define INF (1 << 30)

vector<T> coner;
int ax, ay, bx, by, n, r, p;
int round, area, left_side, right_side, bottom, top;
int imos[3][10500];
int main(){
    while(cin >> n >> r, n | r){
	memset(imos, 0, sizeof(imos));
	round = area = 0;
	p = 0;
	left_side = bottom = 10500;
	right_side = top = 1;
	coner.clear();
	for(int i = 0;i < n;i++){
	    cin >> ax >> ay >> bx >> by;
	    left_side = min(left_side, ++ax);
	    right_side = max(right_side, ++bx);
	    bottom = min(bottom, ++ay);
	    top = max(top, ++by);
	    
	    coner.push_back(T(P(ax, ay), 1));
	    coner.push_back(T(P(ax, by), -1));
	    coner.push_back(T(P(bx, ay), -1));
	    coner.push_back(T(P(bx, by), 1));
	}
	coner.push_back(T(P(INF, INF), 0));
	sort(coner.begin(), coner.end());
	for(int i = left_side;i < right_side + 2;i++){
	    for(int j = bottom;j < top + 2;j++){
		imos[i % 3][j] = imos[i % 3][j - 1];
		while(coner[p].first == P(i, j)){
		    imos[i % 3][j] += coner[p++].second;
		}
	    }
	    for(int j = bottom;j < top + 2;j++){
		imos[i % 3][j] += imos[(i - 1) % 3][j];
		if(imos[i % 3][j])area++;
		if(!!imos[i % 3][j] != !!imos[i % 3][j - 1])round++;
		if(!!imos[i % 3][j] != !!imos[(i - 1) % 3][j])round++; 
	    }

	}
	cout << area << endl;
	if(r == 2)cout << round << endl;
    }
    return 0;
}

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

int main() {
  int n,p=0,w=0,g=0,y=0;
  cin >> n;
  
  string x;
  
  for (int i=0;i < n;i++) {
    cin >> x;
    
    if (x == "P")
      p++;
  
    if (x == "W")
      w++;
    
    if (x == "G")
      g++;
    
    if (x == "Y")
      y++;
  }
  
  if (p*w*g*y != 0)
    cout << "Four" << endl;
  
  else if(p*w*g != 0||p*w*y != 0||p*g*y != 0||g*w*y != 0)
    cout << "Three" << endl;
 
}

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

int n, a;
vector<int> x;
long long ans;
int z;
long long p[2510], m[2510];

int main(){
//	cin.tie(0);
//	ios::sync_with_stdio(false);
	cin >> n >> a;
	for(int i=0; i<n; ++i){
		int t;
		cin >> t;
		x.push_back(t);
	}
	sort(x.begin(), x.end());
	for(int i=0; i<n; ++i){
		x[i] -= a;
		if(x[i] == 0) ++z;
		else if(x[i] > 0){
			for(int j=2500; j>0; --j){
				if(j - x[i] > 0){
					p[j] += p[j-x[i]];
				}
			}
			++p[x[i]];
		}else{
			for(int j=2500; j>0; --j){
				if(j + x[i] > 0){
					m[j] += m[j+x[i]];
				}
			}
			++m[-x[i]];
		}
	}
/*	cout << z << "\n";
	for(int i=1; i<=10; ++i){
		cout << p[i] << " " << m[i] << "\n";
	}
*/	ans = (1ll << z) - 1;
	for(int i=1; i<=2500; ++i){
		ans += m[i] * p[i] * (1ll << z);
	}
	cout << ans << "\n";
}

Measured memory_bytes: 256
NM  = input().split()
A = input().split()
N = int(NM[0])
M = int(NM[1])

A = [int(i) for i in A]

# N = 3 
# M = 2
# A = [380,19,1]

total = sum(A)
# print(total)
cnt = 0
for i in range(N):
    if A[i]>= (1/(4*M))*total:
        cnt += 1


if cnt>= M:
    print('Yes')
else:
    print('No')




Measured memory_bytes: 3060
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>

using namespace std;

int main(void){
    int n;
    cin >> n;
    int no = 0;

    vector<pair<long long, long long>> ba(n);
    for(int i = 0;i < n;i++)    cin >> ba[i].second >> ba[i].first;

    sort(ba.begin(), ba.end());

    long long past_time = 0;

    for(int i = 0;i < n;i++){
        past_time += ba[i].second;
        if(past_time > ba[i].first){
            no = 1;
            break;
        }
    }

    if(no == 1) cout << "No" << endl;
    else        cout << "Yes" << endl;

    return 0;
}

Measured memory_bytes: 3328
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, [ $t:tt ]) => {
        {
            let len = read_value!($next, usize);
            (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
        }
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        s: chars,
        t: chars,
    }
    let mut count = 0;
    for i in 0..3 {
        if s[i] == t[i] {
            count += 1;
        }
    }
    println!("{}", count);
}


Measured memory_bytes: 4352
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <algorithm>
#include <iomanip>
#include <string.h>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define ALL(a)  (a).begin(),(a).end()

typedef long long lint;

using namespace std;

int main(){
  int N,R;
  cin>>N>>R;
  cout<<(N>=10?R:R+100*(10-N))<<endl;
  return 0;
}


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

int main(){
  int n;
  std::cin >> n;
  for (int i = 1; i <= 10; i++) {
    if(i*1000>=n){
      std::cout << i*1000-n << '\n';
      return 0;
    }
  }


  return 0;
}


Measured memory_bytes: 3636
/* ---------- STL Libraries ---------- */
// IO library
#include <cstdio>

#include <fstream>
#include <iomanip>
#include <ios>
#include <iostream>

// algorithm library
#include <algorithm>

#include <cmath>
#include <numeric>
#include <random>
#include <cstring>

// container library
#include <array>
#include <bitset>
#include <deque>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <vector>
#include <stack>

// type
#include <cstdint>

/* ---------- Namespace ---------- */
using namespace std;

/* ---------- Type ---------- */
using ll = long long;
#define int ll
#define P pair<ll, ll>

/* ---------- Constants  */
const double PI = 3.141592653589793238462643383279;
const ll MOD = 1e9 + 7;
const int INF = 1LL << 55;

/* v-v-v-v-v-v-v-v-v Main Part v-v-v-v-v-v-v-v-v */
signed main() {
    string str;
    cin >> str;
    auto N = (int) str.size();
    reverse(str.begin(), str.end());

    vector<vector<int>> dp(N+1, vector<int>(2, INF));
    dp[0][0] = 0;

    for (int i = 0; i < N; i++) {
        int n = str[i] - '0';

        for (int j = 0; j < 2; j++) {
            int num = n;
            if (j == 1) num++;

            if (num == 10) {
                dp[i+1][1] = min(dp[i+1][1], dp[i][j]);
            } else {
                dp[i+1][0] = min(dp[i+1][0], dp[i][j] + num);
                dp[i+1][1] = min(dp[i+1][1], dp[i][j] + (10 - num));
            }
        }
    }

    cout << min(dp[N][0], dp[N][1] + 1) << endl;
    return 0;
}

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

#define _GLIBCXX_DEBUG
#define all(v) (v).begin(),(v).end()

using ll=long long;
using ld=long double;
using pii=pair<int, int>;
using vi=vector<int>;
using vii=vector<vector<int>>;

const ll LINF=1LL<<60;
const int INF=1<<29;
const int MOD=1e9+7;

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



int main(){
    int N, K; cin >> N >> K;
    ld ans=0;
    for(int i=1; i<=N; i++){
        int p=1, cnt=0;
        while(i*p < K){
            p*=2;
            cnt++;
        }
        ans+=(ld)1/N*pow(0.5, cnt);
    }
    cout << fixed << setprecision(10); 
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4016
#include <stdio.h>

int main(void)
{
  char ans[4];
  for(int i = 0; i < 3; i++){
    char c[3][4];
    scanf("%s", c[i]);
    ans[i] = c[i][i];
  }
  ans[3] = '\0';
  printf("%s\n", ans);
  return 0;
}


Measured memory_bytes: 128
#include <stdio.h>

int main(){
    int a,b,c,n;
    
    scanf("%d", &n);
    while (n-- > 0) {
        scanf("%d %d %d", &a, &b, &c);
        if (a * a == b * b + c * c || b * b == a * a + c * c || c * c == a * a + b * b) printf("YES\n");
        else printf("NO\n");
    }
    
    return 0;
}

Measured memory_bytes: 580
use std::io::{stdin, Read};

fn main() {
    let mut input = String::new();
    stdin().read_to_string(&mut input).unwrap();
    let rows: Vec<&str> = input.split('\n').collect();
    let row1_list: Vec<&str> = rows[0].split(' ').collect();
    let n: i64 = row1_list[0].parse().unwrap();
    let k: i64 = row1_list[1].parse().unwrap();
    
    let quotient = n / k;
    
    let mut min: i64 = n - (k * quotient);
    loop {
        let diff = (min - k).abs();
        if diff < min {
            min = diff;
        } else {
            break;
        }
    }
    println!("{}", min);
}

Measured memory_bytes: 4352
#include <iostream>
#include <vector>
#include <string>
#include <set>
using namespace std;

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

int n, k;
vector<string> cards;
set<string> ans;

void dfs(vector<int> s, set<int> used)
{
    if (s.size() == k)
    {
        string str = "";
        for (int i : s)
        {
            str += cards[i];
        }
        ans.emplace(str);
        return;
    }
    rep(i, n)
    {
        if (used.count(i) == 0)
        {
            vector<int> s2 = s;
            s2.push_back(i);
            set<int> used2 = used;
            used2.emplace(i);
            dfs(s2, used2);
        }
    }
}

int main()
{
    while (true)
    {
        ans = {};
        cin >> n >> k;
        if (n + k == 0)
        {
            break;
        }
        cards.resize(n);
        rep(i, n)
        {
            cin >> cards[i];
        }

        dfs({}, {});
        cout << ans.size() << endl;
    }
}


Measured memory_bytes: 3404
N, M, C = map(int, input().split())
B_list = list(map(int, input().split()))
count = 0

for i in range(N):
	res = 0
	A_list = list(map(int, input().split()))
	for i in range(len(A_list)):
		res += A_list[i]*B_list[i]
	if res + C > 0:
		count += 1
print(count)

Measured memory_bytes: 3060
import java.util.Arrays;
import java.util.Scanner;

class Main{

	static long[] a;
	static	int N ;
	static	int M ;


	public static void main(String[] args) {


		Scanner scanner = new Scanner(System.in);
		N = scanner.nextInt();
		long ans = 0;
		a = new long[N];

		//int[] data = new int[Integer.MAX_VALUE];
		//M = scanner.nextInt();
		for(int i = 0;i < N;i++){
			a[i] = scanner.nextLong();
		}
		Arrays.sort(a);

		long k = a[0];					//現在の数値
		int c = 1;						//現在の数値の個数

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


			if(a[i] != k){
				if(c < k){
					ans += c;
				}else{
					ans += c -k;
				}
				c = 1;
				k =a[i]; 

			}else{
				c++;
			}
		}
		
		if(c < k){
			ans += c;
		}else{
			ans += c -k;
		}

		System.out.println(ans);
	}


}

class Pair implements Comparable{
	int from;
	int middle;
	int end;
	@Override
	public int compareTo(Object other) {
		Pair otherpair = (Pair)other;

		return end - otherpair.end;
	}
}





Measured memory_bytes: 50888
def main():
    mod=1000000007
    n=int(input())
    A=list(map(int,input().split()))
    D=[0]*61
    for i in range(61):
        for a in A:
            if a>>i&1:
                D[i]+=1
    ans=0
    for i,d in enumerate(D):
        ans+=(pow(2,i,mod)*(d*(n-d)))
        ans%=mod
    print(ans)
    
if __name__=='__main__':
    main()

Measured memory_bytes: 122808
using System.IO;
using System;

class a163
{
    
    static double Circle(int r){
        double PI = 3.141592653;
        return PI * 2 * r;
    }
    static void Main()
    {
        int r = Convert.ToInt32(Console.ReadLine());
        Console.WriteLine(Circle(r));
    }
}

Measured memory_bytes: 27640
import scala.io.StdIn.readLine
import scala.math.Pi

object Main {
	def main(args: Array[String]) = {
		val r = io.StdIn.readLine.split(" ").map(_.toDouble)
		printf("%.6f %.6f\n", r(0)*r(0)*math.Pi, 2*r(0)*math.Pi)
	}
}

Measured memory_bytes: 43824
N,X =  map(int, input().split())

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

a = a[::-1]

dp = [0 for i in range(N+1)]
for i in range(1,N+1):
    dp[i] = a[i-1] + dp[i-1]

ans = 10**100

for k in range(1,N+1):
    cur = (N+k) * X


    count = 1
    i = k
    while 1:
        first = i - k
        last = min(N,i)
        flag = False
        if i > N:
            flag = True

        if count == 1:
            cur += dp[last] * 5
        else:
            cur += (dp[last] - dp[first]) * (2*count + 1)

        count += 1
        i += k
        
        if flag:
            break


        
    ### print(dp, cur)
    ans = min(ans, cur)

print(ans)



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

#define lp(i,n) for(int i=0;i<n;i++)
#define lpin(a,i,n) for(int i=0;i<n;i++){cin>>a[i];}
using namespace std;

  int a[100001];
int main(){
  int n,t;
  cin>>n>>t;
  lp(i,n){
    int c,b;
    cin>>c>>b;
    a[c]+=1;
    a[b]-=1;
  }
  for(int i=1;i<100001;i++){
    a[i]+=a[i-1];
  }
  int max=0;
  lp(i,t+1){
    if(max<a[i])max=a[i];
  }
  cout<<max<<endl;
  return 0;
}



Measured memory_bytes: 3488
#include <stdio.h>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <list>
#include <iterator>
#pragma warning(disable:4996)
 
typedef long long ll;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF 9223300000000000000
#define INF 2140000000
#define MOD 1000000007
using namespace std;


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

    vector<vector<long> > z(n), w(n);
    vector<long> cnt(n);
    long i;
    for(i=0; i<n+m-1; i++) {
        long a, b;
        scanf("%ld%ld", &a, &b);
        z[a-1].push_back(b-1);    // par->child
        w[b-1].push_back(a-1);    // child->par
        cnt[b-1]++;
    }

    vector<long> topo(n);
    set<long> ss;
    for(i=0; i<n; i++) {
        if(cnt[i]==0) ss.insert(i);
    }
    long count=0;
    while(!ss.empty()) {
        auto it=ss.begin();
        topo[*it]=count;
        count++;

        long m;
        for(m=0; m<(long)z[*it].size(); m++) {
            cnt[z[*it][m]]--;
            if(cnt[z[*it][m]]==0) ss.insert(z[*it][m]);
        }
        ss.erase(it);
    }
    if(count!=n) return 12;

    for(i=0; i<n; i++) {
        long max=-1;
        long maxk=-1;
        long k;
        for(k=0; k<w[i].size(); k++) {
            if(max<topo[w[i][k]]) {
                max=topo[w[i][k]];
                maxk=w[i][k];
            }
        }
        printf("%ld\n", maxk+1);
    }

    return 0;
}


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

int main(){
	ios::sync_with_stdio(0);
	cout << setprecision(10) << fixed;
	string s;
	cin >> s;
	int q;
	bool rev = false;
	vector<char> fr, e;
	cin >> q;
	while (q--){
		int t, f;
		char c;
		cin >> t;
		t--;
		if (!t){
			rev ^= true;
		}
		else{
			cin >> f >> c;
			f--;
			if (rev){
				f = (f ? 0 : 1);
			}
			if (!f){
				fr.push_back(c);
			}
			else{
				e.push_back(c);
			}
		}
	}
	string ans = "";
	if (rev){
		swap(fr, e);
		reverse(s.begin(), s.end());
	}
	for (int i = fr.size() - 1; i >= 0; --i){
		ans += fr[i];
	}
	ans += s;
	for (int i = 0; i < e.size(); ++i){
		ans += e[i];
	}
	cout << ans;
	return 0;
}



Measured memory_bytes: 1448
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int const N = 1e5 + 41;

int ans, n, k, a[N], dp[N], was[N], sz;
bool haveK = false, ok = true;
vector<int> e[N];

void dfs(int u){
	if(was[u]){
		return;
	}
	was[u] = 1;
	dfs(a[u]);
	dp[u] = 1 + dp[a[u]];
}

void findSz(){
	int p = a[0];
	sz = 1;
	while(p != 0){
		++sz;
		p = a[p];
	}
}

void findDp(){
	was[0] = 1;
	dp[0] = 0;
	for(int i=1;i<n;++i){
		if(!was[i]){
			dfs(i);
		}
	}
}

void check0(){
	for(int i=0;i<n;++i){
		if(dp[i] <= k && sz == 0){
		}else{
			ok = false;
		}
	}
	if(ok){
		printf("0\n");
		exit(0);
	}
}

void pushEdges(){
	for(int i=1;i<n;++i){
		e[a[i]].push_back(i);
	}
}

pair<int, int> rec(int u, int p){
	pair<int, int> ret = make_pair(0, 0);
	for(int i=0;i<e[u].size();++i){
		int to = e[u][i];
		if(to == p){
			continue;
		}
		pair<int, int> rp = rec(to, u);
		ret.first += rp.first;
		if(rp.second + 1 == k && u != 0){
			++ret.first;
		}else{
			ret.second = max(ret.second, rp.second + 1);
		}
	}
	return ret;
}

int main(){
#ifdef _DEBUG
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
#endif
	scanf("%d %d",&n,&k);
	for(int i=0;i<n;++i){
		scanf("%d",&a[i]);
		--a[i];
	}

	findSz();
	findDp();
	check0();
	pushEdges();
	if(sz != 1){
		ans = 1;
	}

	ans += rec(0, 0).first;
	printf("%d\n",ans);


	return 0;
}

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

using namespace std;
typedef long long int ll;
int arr[22222222];
int a[22222222];

int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++) cin>>arr[i];
    ll sum=0;
    for(int i=0;i<n;i++)
    {
        sum+=arr[i];
        a[arr[i]]++;
    }
    int x;
    cin>>x;
    while(x--)
    {
        int b,c;
        cin>>b>>c;
        ll cur=a[b];
        sum-=cur*b;
        a[b]=0;
        sum+=cur*c;
        a[c]+=cur;
        cout<<sum<<endl;


    }
   return 0;
}


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

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
//#define int ll
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector< vi > vvi;
typedef vector< vvi > vvvi;
typedef vector<short> vs;
typedef vector<vs> vvs;
typedef vector<vvs> vvvs;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
typedef vector<ld> vld;
typedef vector<vld> vvld;
typedef vector<vvld> vvvld;
typedef vector<string> vst;
typedef vector<vst> vvst;
typedef pair<ld, ld> pld;
typedef complex<double> base;

#define inmin(a, b) a = min(a, (b))
#define inmax(a, b) a = max(a, (b))
#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()
#define sqr(x) ((x) * (x))
#define fori(i, n) for(int i = 0; i < int(n); ++i)
#define SZ(a) ((int)((a).size()))
#define triple(T) tuple<T, T, T>
#define quad(T) tuple<T, T, T, T>
#define watch(x) cout << (#x) << " = " << (x) << endl;

#ifdef MAX_HOME
#define cerr cout
#else
#define cerr if (false) cerr
#endif

const double PI = 2 * acos(0.0);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng_64(chrono::steady_clock::now().time_since_epoch().count());

const string DIGITS = "0123456789";
const string ALPH = "abcdefghijklmnopqrstuvwxyz";

template <class T0, class T1>
inline ostream & operator << (ostream &out, pair<T0, T1> &a) {
    return out << "{" << a.first << ", " << a.second << "}";
}

template <class T0, class T1, class T2>
inline ostream & operator << (ostream &out, tuple<T0, T1, T2> &a) {
    return out << "{" << get<0>(a) << ", " << get<1>(a) << ", " << get<2>(a) << "}";
}

template <class T0, class T1, class T2, class T3>
inline ostream & operator << (ostream &out, tuple<T0, T1, T2, T3> &a) {
    return out << "{" << get<0>(a) << ", " << get<1>(a) << ", " << get<2>(a) << ", " <<  get<3>(a) << "}";
}

template<class T>
inline ostream & operator << (ostream &out, vector<T> &a) {
    out << "[";
    fori (i, a.size())
        out << a[i] << vector<string>{", ", "]  "}[i + 1 == a.size()];
    return out;
}



void smain();

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

#ifdef MAX_HOME
    freopen("input.txt", "r", stdin);
    clock_t start = clock();
#endif
    cout << setprecision(12) << fixed;
    smain();
#ifdef MAX_HOME
    cout << "\n\n\n\nTOTAL EXECUTION TIME: " << float( clock () - start ) /  CLOCKS_PER_SEC << endl;
#endif
}

void test() {
    cout << "TEST: " << endl;


    exit(0);
}
const int N = 4;
int mat[N][N];

void smain() {


    fori (i, 3) {
        int u, v;
        cin >> u >> v;
        --v, --u;
        mat[u][v] = mat[v][u] = 1;
    }

    vi a = {0, 1, 2, 3};

    do {
        bool ok = true;
        fori (i, 3) {
            if (!mat[a[i]][a[i + 1]]) {
                ok = false;
                break;
            }
        }
        if (ok) {
            cout << "YES";
            return;;
        }
    } while (next_permutation(ALL(a)));
    cout << "NO";
}


Measured memory_bytes: 256
{-# LANGUAGE BangPatterns #-}
import           Control.Exception           (assert)
import           Control.Monad
import           Control.Monad.Primitive
import qualified Control.Monad.ST            as ST
import qualified Data.Array.IO               as IO
import qualified Data.Array.ST               as ST
import qualified Data.Array.Unboxed          as A
import           Data.Bits
import qualified Data.ByteString.Char8       as BS
import           Data.Char
import           Data.Foldable
import           Data.List
import qualified Data.Map.Strict             as Map
import           Data.Maybe
import qualified Data.Sequence               as Seq
import qualified Data.Set                    as Set
import qualified Data.Vector                 as VB
import qualified Data.Vector.Mutable         as VBM
import qualified Data.Vector.Unboxed         as V
import qualified Data.Vector.Unboxed.Mutable as VM
import           Debug.Trace

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine
getIntVec n = V.unfoldrN n (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine

readInteger = fst . fromJust . BS.readInteger
readIntegerList = map readInteger . BS.words
getInteger = readInteger <$> BS.getLine
getIntegerList = readIntegerList <$> BS.getLine

inf :: Int
inf = 10^18

main = do
  n <- getInt
  as <- getIntList

  let solve [] maxh res = res
      solve (a:as) maxh res = let hstep = max 0 (maxh - a)
                                  maxh' = max maxh a
                                  res' = res + hstep
                              in solve as maxh' res'

  print $ solve as 0 0


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

using namespace std;

int main(void){

    string alpha = "abcdefghijklmnopqrstuvwxyz";
    int count[26] = {0};
    
    string s;
    cin >> s;
    
    for(int i=0; i<s.size(); i++) {
        string::size_type pos = alpha.find(s[i]);
        if(pos != string::npos) {
            count[(int)pos]++;
        }
    }

    bool isNone = true;
    int min = 10000000;
    int index = 0;
    for(int i=0; i<26; i++) {
        if(min>count[i]) {
            min = count[i];
            index = i;
        }
        if(isNone && !count[i]) {
            isNone = false;
        }
    }
    if(isNone) cout << "None" << endl;
    else cout << alpha.substr(index,1) << endl;

    return 0;
    
}


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

typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, n) for(int (i)=0; (i)<(n); (i)++)
#define FOR1(i, n) for(int (i)=1; (i)<=(n); (i)++)
#define FORI(i, n) for(int (i)=n-1; (i)>=0; (i)--)

int main(int argc, char** argv) {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout << setprecision(15);
    if (argc == 2 && atoi(argv[1]) == 123456789) freopen("d:\\code\\cpp\\contests\\stdin", "r", stdin);

    ll N;
    cin >> N;

    ll sol = 0;
    ll p = 2;
    while(p*p<=N){
        if(N%p == 0){
            int cnt = 0;
            while(N%p == 0){
                N /= p;
                cnt++;
            }
            int d = 0;
            while((d+1)*(d+2)/2 <= cnt) d++;
            sol += d;
        }
        p++;
    }
    if (N > 1)
        sol++;


    cout << sol << endl;

    if (argc == 2 && atoi(argv[1]) == 123456789) cout << clock()*1.0/CLOCKS_PER_SEC << " sec\n";
    return 0;
}

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

int main()
{
	int n; cin >> n;
	
	int ans = 0;
	for (int i = 1; i <= n; i += 2) {
		int cnt = 0;
		for (int j = 3; j < i; j += 2) {
			if (i % j == 0) cnt++;
		}
		if (cnt == 6) ans++;
	}

	cout << ans << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
string S,T,U;
ll A,B;




int main(){
    cin >> S;
    A = S.size();
    for (int i=0;i<A;i++){
    cout <<'x';
    }
}




Measured memory_bytes: 256
#include <bits/stdc++.h>
#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()
#define rall(a) (a).rbegin(),(a).rend()
#define maxs(a, b) a = max(a, b)
#define mins(a, b) a = min(a, b)
using namespace std;
template<class T> inline istream& operator >> (istream & c, vector<T> & A) {rep(i, A.size()) c >> A[i];return c;}
template<class T> void vout(vector<T> A) {rep(i, A.size()) cout << A[i] << endl;}
template<class T> void vout_(vector<T> A) { rep(i, A.size()) cout << A[i] << (i == A.size() ? "\n" : " "); }
typedef long long ll;
typedef pair<int, int> P;
const ll linf = (1ll << 61);
const int inf = 1001001001;
const int mod = 1000000007;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	map<int, int> mp;
	for (int i = 1; i <= n; ++i) {
		int x = i;
		for (int j = 2; j * j <= x; ++j) {
			while (x % j == 0) {
				x /= j;
				mp[j]++;
			}
		}
		if (x != 1) mp[x]++;
	}
	int cnt4 = 0, cnt2 = 0, cnt24 = 0, cnt14 = 0, cnt74 = 0;
	for (auto c : mp) {
		if (c.second >= 74) cnt74++;
		if (c.second >= 24) cnt24++;
		if (c.second >= 14) cnt14++;
		if (c.second >= 4) cnt4++;
		if (c.second >= 2) cnt2++;
	}
	int ans = cnt24 * (cnt2 - 1) + cnt74;
	ans += cnt14 * (cnt4 - 1);
	ans += cnt4 * (cnt4 - 1) / 2 * (cnt2 - 2);
	cout << ans << endl;
	return 0;
}

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

int main() {
  string s;
  while(cin >> s) {
    int x=0,y=0;
    for(int i=0; i<s.size()-2; i++) {
      if(s[i+1]=='O' && s[i+2]=='I') {
	if(s[i]=='J') x++;
	if(s[i]=='I') y++;
      }
    }
    cout << x << endl << y << endl;
  }
  return 0;
}


Measured memory_bytes: 1196
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const ll MOD=1000000007;
int main(void){
    int n;
    cin>>n;
    int ans=0;
    int a;
    set<int> s;
    while(n--){
        cin>>a;
        auto itr=s.lower_bound(a);
        if(a==(*itr)){
            ans--;
            s.erase(a);
        }else{
            ans++;
            s.insert(a);
        }
    }
    cout<<ans<<endl;
    
}


Measured memory_bytes: 8248
from collections import Counter

N = int(input())
A=list(map(int,input().split()))
c=dict(Counter(A))
#print(c)
e=[]
f=[]

for i in c:
  if c[i]>1:
    e.append(i)
  if c[i]>=4:
    f.append(i)

e.sort(reverse=True)
f.sort(reverse=True)
if len(f)>=1:
  if f[0]>=e[0]:
    print(f[0]**2)
  else:
    if len(e)>=2:
      print(e[0]*e[1])
    else:
      print(0)
else:
  if len(e)>=2:
    print(e[0]*e[1])
  else:
    print(0)  

Measured memory_bytes: 21668
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
typedef int64_t ll;
typedef long double ld;
using namespace std;
const ll mod=1000000007;
const ll INF=(1LL<<62);
const int dx[4]={0,1,0,-1};
const int dy[4]={1,0,-1,0};
const int ddx[8]={1,0,-1,-1,-1,0,1,1};
const int ddy[8]={1,1,1,0,-1,-1,-1,0};
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
void init(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
}

int main(){
  init();
  ll n,d,x;
  cin>>n>>d>>x;
  vector<ll>A(n);
  ll ans=0;
  rep(i,n){
    ll a;cin>>a;
    ans+=(d-1)/a+1;
  }
  cout<<ans+x<<endl;



}

Measured memory_bytes: 256
N=int(input())
A=input().split()
count=0
i=0
output=0

while True:
  for i in range(N):
    if int(A[i])%2==0:
      count+=1
      A[i]=int(A[i])/2
    if count == N:
      output+=1
  if count != N:
    count=0
    i=0
    break
  count=0

print(output)



Measured memory_bytes: 3060
s=gets.chomp.chars
a=s.size.times.select{|i| (s[i] == '0' && i % 2 == 0) || (s[i] == '1' && i % 2 == 1)}.size
b=s.size.times.select{|i| (s[i] == '1' && i % 2 == 0) || (s[i] == '0' && i % 2 == 1)}.size
p [a,b].min

Measured memory_bytes: 10492
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <cassert>
#include <cfloat>
#include <complex>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define Sort(v) sort(v.begin(), v.end())
#define Reverse(v) reverse(v.begin(), v.end())
#define Lower_bound(v, x) \
  distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) \
  distance(v.begin(), upper_bound(v.begin(), v.end(), x))

using ll = long long;
using ull = unsigned long long;
using P = pair<ll, ll>;
using T = tuple<ll, ll, ll>;
using vll = vector<ll>;
using vP = vector<P>;
using vT = vector<T>;
using vvll = vector<vector<ll>>;
using vvP = vector<vector<P>>;
using dqll = deque<ll>;

ll dx[9] = {-1, 1, 0, 0, -1, -1, 1, 1, 0};
ll dy[9] = {0, 0, -1, 1, -1, 1, -1, 1, 0};

const ll INF = 1LL << 50;

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

  string str = "";
  rep(i, n) str += "?";

  rep(i, m) {
    ll s;
    char c;
    cin >> s >> c;
    s--;
    bool cond = (str[s] == '?') || (str[s] == c);
    if (cond) {
      str[s] = c;
    } else {
      puts("-1");
      return 0;
    }
  }
  if (n >= 2 && str[0] == '0') {
    puts("-1");
    return 0;
  }
  if (str[0] == '?') {
    if (n == 1)
      str[0] = '0';
    else
      str[0] = '1';
  }
  for (ll i = 1; i < n; i++) {
    if (str[i] == '?') str[i] = '0';
  }

  cout << str << endl;

  return 0;
}


Measured memory_bytes: 256
N = int(input())

S = input()
T = input()

MODN = 1000000007

# t:tate, y;yoko
pat = []
i = 0
while i < N:
  if S[i] == T[i]:
    pat.append('t')
    i += 1
  else:
    pat.append('y')
    i += 2

#print("".join(pat))

cnt = 3 if pat[0] == 't' else 6

for i in range(1,len(pat)):
  if (pat[i-1], pat[i]) == ('t', 't'):
    cnt = cnt * 2 % MODN
  elif (pat[i-1], pat[i]) == ('t', 'y'):
    cnt = cnt * 2 % MODN
  elif (pat[i-1], pat[i]) == ('y', 't'):
    cnt = cnt
  elif (pat[i-1], pat[i]) == ('y', 'y'):
    cnt = cnt * 3 % MODN
  else:
    print("Error") # impossible

print(cnt)

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

int main(){
  string S;
  cin >> S;
  int N = S.size();
  int ans = 0;
  for(int i=0;i<N/2;i++){
    if(S[i] != S[N-1-i]){
      ans ++;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pint;

struct rect{int ht;int pos;};
int tb[6][6];
int area_rect(int size,int buf[]){
    stack<rect> st;
    int mx=0;
    buf[size]=0;
    rep(i,size+1){
        rect r;
        r.ht=buf[i];
        r.pos=i;
        if(st.empty()) st.push(r);
        else{
            if(st.top().ht<r.ht) st.push(r);
            else if (st.top().ht>r.ht){
                int ti=i;
                while(!st.empty()&&st.top().ht>=r.ht){
                    rect pre=st.top();st.pop();
                    int area=pre.ht*(i-pre.pos);
                    mx=max(mx,area);
                    ti=pre.pos;
                }
                r.pos = ti;
                st.push(r);
            }
        }
    }
    return mx;
}
int main(){
    int n,t;
    cin>>n;
    while(n--){
        rep(i,5){
            rep(j,5){
                cin>>t;
                if(i==0||t==0) tb[i][j]=t;
                else tb[i][j]=tb[i-1][j]+t;
            }
        }
        int mx=0;
        rep(i,5) mx=max(mx,area_rect(5,tb[i]));
        cout<<mx<<endl;
    }
    return 0;
}

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<29;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-11;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};


int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	while(1){
		int n,m;
		cin>>n>>m;
		if(n==0) break;
		vi a(n),b(n);
		for(int i=0;i<m;i++){
			int x,k;
			cin>>x>>k;
			for(int j=0;j<k;j++){
				int id;
				cin>>id;
				id--;
				if(k==1) b[id]+=x;
				a[id]+=x;
			}
		}
		vi c(n),d(n);
		int res=0;
		c[0]=d[n-1]=inf;
		for(int i=1;i<n;i++) c[i]=min(c[i-1],b[i-1]);
		for(int i=n-2;i>=0;i--) d[i]=min(d[i+1],b[i+1]);
		for(int i=0;i<n;i++){
			res=max(res,a[i]-min(c[i],d[i]));
		}
		cout<<res+1<<endl;
	}
}


Measured memory_bytes: 3296
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        n: usize,
        s: chars
    }
    let mut countr = 0;
    let mut countb = 0;
    for c in s {
        if c == 'R' {
            countr += 1
        } else if c == 'B' {
            countb += 1;
        }
    }
    if countr > countb {
        println!("Yes")
    } else {
        println!("No")
    }
}

// fn main() {
//     input! {
//         n: usize,
//         k: usize,
//     }
//     println!("{}", k * (k - 1).pow(n as u32 - 1))
// }

// fn main() {
//     input! {
//         h: usize,
//         w: usize,
//         s: [chars; h]
//     }
//     let xy = [
//         // [-1i32, 1i32],
//         [0i32, 1i32],
//         // [1i32, 1i32],
//         [-1i32, 0i32],
//         [1i32, 0i32],
//         // [-1i32, -1i32],
//         [0i32, -1i32],
//         // [1i32, -1i32],
//     ];
//     let mut s = s;
//     for y in 0..h {
//         for x in 0..w {
//             if s[y][x] == '.' {
//                 continue;
//             }
//             let mut b = false;
//             for i in 0..4 {
//                 let xx = x as i32 + xy[i][0] as i32;
//                 let yy = y as i32 + xy[i][1] as i32;
//                 if xx < 0 || w as i32 <= xx {
//                     continue;
//                 }
//                 if yy < 0 || h as i32 <= yy {
//                     continue;
//                 }
//                 if s[yy as usize][xx as usize] == '#' {
//                     b = true;
//                 }
//             }
//             if !b {
//                 println!("No");
//                 return;
//             }
//         }
//     }
//     println!("Yes")
// }


Measured memory_bytes: 4352
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]

# Aが価格、Bが本数の制限

AB = sorted(AB)

cnt = 0
ans = 0
for ab in AB:
    a, b = ab[0], ab[1]
    if M >= b:
        ans += a*b
        M -= b
    else:
        ans += a*M
        M -= M
    if M == 0:
        break

print(ans)

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

#define xy fabs(x[j]-y[j])

int main(void)
{
    int i,j,n;
    double x[1010]={0},y[1010]={0},max=0,p1,p2,p3;
    
    scanf("%d",&n);
    for(j=0;j<n*2;j++){
        if(j<n) scanf("%lf",&x[j]);
        else scanf("%lf",&y[j-n]);
    }
    
    for(j=0;j<n;j++){
        p1+=xy;
        p2+=pow(xy,2);
        p3+=pow(xy,3);
        if(xy>max)max=xy;
    }
    p2=sqrt(p2);
    p3=cbrt(p3);
    printf("%f\n%f\n%f\n%f\n",p1,p2,p3,max);
    
    return 0;
}


Measured memory_bytes: 2036
N = int(input())
number_list=list(map(int ,input().split()))
dif = sum(number_list)
dif_list = [dif]
for i in range(N-1):
    dif -= 2*number_list[i]
    dif_list.append(abs(dif))
dif_min = min(dif_list)
print(dif_min)

Measured memory_bytes: 3060
#include<iostream>
#include<vector>
#include<algorithm>
#include<numeric>

int main()
{
	int n;
	std::cin >> n;
	std::vector<long> vec;
	for (int i = 0; i < n; i++) {
		long x;
		std::cin >> x;
		vec.push_back(x);
	}
	std::cout << *std::min_element(vec.begin(), vec.end()) << " ";
	std::cout << *std::max_element(vec.begin(), vec.end()) << " ";
	std::cout << std::accumulate(vec.begin(), vec.end(), 0L) << std::endl;
}

Measured memory_bytes: 1344