akhauriyash/Code-Regression huggingface dataset:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N = int(readline())
    
    n = (N + 999) // 1000
    ans = n * 1000 - N
    print(ans)
    
    return


if __name__ == '__main__':
    main()


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

int main(void) {
	// input
	int n;
	long long k;
	std::cin >> n >> k;
	std::vector<int> a(n), b(n);
	std::vector<std::pair<int, int>> c(n);
	for(int i = 0; i < n; ++i) {
		std::cin >> a[i] >> b[i];
		c[i] = std::make_pair(a[i], b[i]);
	}
	
	// sort
	std::sort(c.begin(), c.end(), [](std::pair<int, int> &lhs, std::pair<int, int> &rhs){ return lhs.first < rhs.first; });

	// for
	int ans = 0;
	long long sum_b = 0;
	for(int i = 0; i < n; ++i) {
		if(k > sum_b && k <= c[i].second + sum_b) {
			ans = c[i].first;
			break;
		}
		sum_b += c[i].second;
	}

	std::cout << ans << std::endl;

	return 0;
}


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

const string YES = "Yes";
const string NO = "No";

void solve(long long N, long long K, long long Q, std::vector<long long> A){
    vector<vector<ll> > myset(N);
    for(ll q=0; q< Q; q++){
        myset[A[q]-1].push_back(q+1);
    }
    for(ll i=0; i< N; i++){
        bool isDead = false;
        if(myset[i].empty()) {
            cout << (K>Q? YES: NO) << endl;
            continue;
        }
        else{
            ll pt, q;
            for(ll j = 0; j < myset[i].size(); j++){
                q = myset[i][j];
                if(q != 1){
                    pt = K+j-q+1;
                    if (pt <= 0) {
                        isDead = true;
                        break;
                    }
                }
            }
            //* final check
            pt = K + myset[i].size() - Q;
            if(pt <= 0) isDead = true;
        }
        if(isDead) cout << NO << endl;
        else cout << YES << endl;
    }
}

int main(){
    long long N;
    scanf("%lld",&N);
    long long K;
    scanf("%lld",&K);
    long long Q;
    scanf("%lld",&Q);
    std::vector<long long> A(Q);
    for(int i = 0 ; i < Q ; i++){
        scanf("%lld",&A[i]);
    }
    solve(N, K, Q, std::move(A));
    return 0;
}


Measured memory_bytes: 5888
s = int(input())
n = []
f = 0

while s > 0:
    n.append(s % 10)
    s = s // 10

n.reverse()
if(len(n) < 3):
    f = 1

for i in range(1,len(n)):
    if(n[i] == n[i -1]):
        f = 1
        break

if(f == 1):
    print('Bad')
else:
    print('Good')

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

int main(){
	ll n;cin>>n;
	ll prime[10010]={0};
	ll arr[100100]={0};
	prime[1] = 1;
	for(int i=2; i<=n; i++){
		if(!prime[i]){
			for(int j=i; j<=n; j+=i){
				ll temp =j ;
				ll cnt = 0;
				while(temp%i == 0){
					temp/=i;
					cnt++;
				}
				arr[i]+=cnt;
				prime[j] = 1;
			}
			prime[i] = 0;
		}
	}
	ll ans = 1;
	for(int i=1; i<=n; i++){
		arr[i] = (arr[i]+1)%MOD;
		ans = (ans*arr[i])%MOD;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1152
fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    val a = readLine()!!.split(" ").map { it.toLong() }

    val leftGcd = Array(n + 1) { 0L }
    val rightGcd = Array(n + 1) { 0L }

    for (i in 0 until n) {
        leftGcd[i + 1] = gcd(leftGcd[i], a[i])
    }

    for (i in n - 1 downTo 0) {
        rightGcd[i] = gcd(rightGcd[i + 1], a[i])
    }

    var ans = 0L
    for (i in 0 until n) {
        val left = leftGcd[i]
        val right = rightGcd[i + 1]
        ans = Math.max(ans, gcd(left, right))
    }

    println(ans)
}

fun gcd(a: Long, b: Long): Long {
    if (b == 0L) return a

    return gcd(b, a % b)
}

Measured memory_bytes: 60132
#include <iostream>
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
#include <cctype>
#include <string>
#include <map>
#include <set>
#include <math.h>
#include <cmath>
#define ll long long

using namespace std;
using P = pair<int,int>;

int main(){

  int D, N;
  cin >> D >> N;

  if(D == 0){
    if(N == 100) cout << 101 << endl;
    else cout <<  N << endl;
  } else if (D == 1){
    if(N == 100) cout << 101*100 << endl;
    else cout <<  N*100 << endl;
  } else if (D == 2){
    if(N == 100) cout << 101*10000 << endl;
    else cout <<  N*10000 << endl;
  }


  return 0;
}

Measured memory_bytes: 3636
S = input()
d,m = len(S)//2,len(S)%2
A = '01'*d+'0'*m
B = '10'*d+'1'*m
count_a = 0
count_b = 0
for s,a,b in zip(S,A,B):
    if s != a:
        count_a += 1
    if s != b:
        count_b += 1
print(min(count_a, count_b))

Measured memory_bytes: 3316
n,k = gets.chomp.split().map(&:to_i)
s = gets.chomp.split(//)

array = []
current = s.first
count = 0
array.push 0 if s.first == '0'
s.each do |c|
  if c == current
    count += 1
  else
    array.push count
    current = c
    count = 1
  end
end
if count > 0
  array.push count
end
array.push 0 if s.last == '0'

#p ['ar', array]

if array.size/2 - k < 0
  puts array.inject(:+)
  exit
end


ans = 0
tmpans = 0
(array.size).times do |i|
  if i <= k * 2
    ans += array[i]
    tmpans = ans
  else
    if i.even?
      #p [i-1, i, i-k*2-2, i-k*2-1]
      #p [tmpans, array[i-1], array[i], array[i-k*2-2], array[i-k*2-1]]
      tmpans = tmpans + array[i-1] + array[i] - array[i-k*2-2] - array[i-k*2-1]
      ans = [ans, tmpans].max
    end
  end
  #p ['tm', tmpans, 'ans', ans]
end

puts ans


Measured memory_bytes: 10236
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define mset(x,y) memset(x,y,sizeof(x))
#define rep(i,n) for(int i=0;i<int(n);i++)
#define per(i,n) for(int i=int(n)-1;i>=0;i--)
#define rng(i,a,b) for(int i=int(a);i<=int(b);i++)
#define gnr(i,b,a) for(int i=int(b);i>=int(a);i--)
using namespace std;
using namespace __gnu_pbds;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
#ifdef LOCAL
#define dmp(...) _dmp(#__VA_ARGS__, __VA_ARGS__)
#else
#define dmp(...) (__VA_ARGS__)
#endif
template<class T> using vt=vector<T>;
template<class T> using vvt=vt<vt<T>>;
template<class TA,class TB> void chmax(TA&a,TB b){if(a<b)a=b;}
template<class TA,class TB> void chmin(TA&a,TB b){if(b<a)a=b;}
template<class TA,class TB>
ostream& operator<<(ostream& os,const pair<TA,TB>& p){
	return os<<"{"<<p.fi<<","<<p.se<<"}";
}
template<class T> ostream& operator<<(ostream& os,const vt<T>& v){
	os<<"{";for(auto& e:v)os<<e<<",";return os<<"}";
}
template<class TH> void _dmp(const char *sdbg, TH h){cout<<sdbg<<"="<<h<<endl;}
template<class TH, class... TA> void _dmp(const char *sdbg, TH h, TA...a){
while(*sdbg!=',')cout<<*sdbg++;cout<<"="<<h<<","; _dmp(sdbg+1, a...);
}
template<class T> void make_unique(vt<T>& v) {
	sort(all(v));v.erase(unique(all(v)),v.end());
}
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
int ri(){int x;cin>>x;return x;}
ll rll(){ll x;cin>>x;return x;}
vi rvi(int n){vi v;rep(i,n)v.pb(ri());return v;}
int n,K,C;
int D[200010],E[200010],F[200010];
char s[200010];
void MAIN() {
	cin>>n>>K>>C>>s;
	rep(i,n) {
		if(i>=1)D[i]=max(D[i],D[i-1]);
		if(i>=C&&s[i-C]=='o')D[i]=max(D[i],(i>=C+1?D[i-C-1]:0)+1);
	}
	per(i,n) {
		E[i]=max(E[i],E[i+1]);
		if(s[i]=='o')E[i]=max(E[i],E[i+C+1]+1);
	}
	rep(i,n) {
		if(s[i]=='o') {
			F[i]=1;
			if(i>=1)F[i]+=D[i-1];
			if(i+C+1<n)F[i]+=E[i+C+1];
		}
	}
	vi v;
	deque<int> dq;
	rep(i,n) {
		while(!dq.empty()&&dq.front()<i-C)dq.pop_front();
		int val=0;
		if(i)val+=D[i-1];
		if(i+1<n)val+=E[i+1];
		if(!dq.empty())val=max(val,F[dq.front()]);
		if(val<K)v.pb(i);
		while(!dq.empty()&&F[dq.back()]<F[i])dq.pop_back();
		dq.push_back(i);
	}
	for(auto& it:v)cout<<it+1<<'\n';
}
int main() {
	ios::sync_with_stdio(false);cin.tie(0);
	int T=1;
	//cin>>T;
	for(int tt=1;tt<=T;tt++) {
		MAIN();
	}
	return 0;
}

Measured memory_bytes: 4980
#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
int main(){
    int N,i=0;
    string S;
    cin>>N>>S;
    if(N%2==1){
        cout<<"No"<<endl;
    }else{
        while(i<N/2){
            if(S[i]!=S[N/2+i]){
                cout<<"No"<<endl;
                break;
            }
            i+=1;
        }
        if(i==N/2){
            cout<<"Yes"<<endl;
        }
    }
    
}


Measured memory_bytes: 888
#include <stdio.h>
//question: how to deal with the duplicate elemets
int binary_search(int target, int b[], int left, int right){
    // nofinding
    if(left>=right) return ((target==b[left])?left:-1);
    int middle = (left+right)/2;    
    if(target == b[middle]) return middle;
    else if(target < b[middle]) return binary_search(target, b, left, middle);
    else return binary_search(target, b, middle+1, right);
}

//binary search
int main()
{
    int n, q;
    scanf("%d", &n);
    int a[n+1];
    for(int i = 0; i<n; i++){
        scanf("%d", &a[i]);
    }
    scanf("%d", &q);
    int b[q+1];
    for(int i = 0; i<q; i++){
        scanf("%d", &b[i]);
    }

    int count = 0;
    for(int i = 0; i<q; i++){
        //printf("%d\n",binary_search(b[i], a, 0, q-1));
        if(binary_search(b[i], a, 0, n-1)>=0){
            count++;
        }
        
    }
    printf("%d\n", count);
    return 0;
}


Measured memory_bytes: 3256
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <memory>
#include <complex>
#include <numeric>
#include <cstdio>
#include <iomanip>

#define REP(i,m,n) for(int i=int(m);i<int(n);i++)
#define RREP(i,m,n) for(int i=int(n)-1;i>=int(m);--i)
#define EACH(i,c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

#ifdef LOCAL
#define DEBUG(s) cout << (s) << endl
#define dump(x)  cerr << #x << " = " << (x) << endl
#define BR cout << endl;
#else
#define DEBUG(s) do{}while(0)
#define dump(x) do{}while(0)
#define BR 
#endif
using namespace std;

using UI = unsigned int;
using UL = unsigned long;
using LL = long long int;
using ULL = unsigned long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VS = vector<string>;
using PII = pair<int,int>;
using VP = vector<PII>;

//struct edge {int from, to, cost;};

constexpr double EPS = 1e-10;
constexpr double PI  = acos(-1.0);
//constexpr int INF = INT_MAX;

template<class T> inline T sqr(T x) {return x*x;}

void solve() {
    int a,b,c,d,e,f;
    cin >> a >> b >> c >> d >> e >> f;
    bool dp[3001][3001] = {};
    dp[0][0] = true;
    REP(i,0,3000) REP(j,0,3000) {
        if (!dp[i][j]) continue;
        if (i + j + 100 * a <= f) dp[i+100*a][j] = true;
        if (i + j + 100 * b <= f) dp[i+100*b][j] = true;
        if (i + j + c <= f) dp[i][j+c] = true;
        if (i + j + d <= f) dp[i][j+d] = true;
    }
    double ans = 0;
    int w = 0, s = 0;
    REP(i,1,3001) REP(j,0,3001) {
        if (!dp[i][j]) continue;
        if (i + j > f) continue;
        if (i * e < j * 100) continue;
        if (ans <= 100.0 * j / (i + j)) {
            ans = 100.0 * j / (i + j);
            w = i;
            s = j;
        }
    }
    cout << w + s << " " << s << endl;
}

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

Measured memory_bytes: 9088
#include<bits/stdc++.h>
#define rep(i,n) for (int i=0; i<(n); ++i)
using namespace std;
typedef long long ll;
int main(){
  int n,x;
  cin >> n >> x;
  int l[n];
  rep(i,n) cin >> l[i];
  int d=0;
  int ans = 1;
  rep(i,n){
    d = d+l[i];
    if (d<=x){
      ans++;
    }
  }
  cout << ans << endl;
}

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

int main() {
    int n, q;
    std::string s;
    std::cin >> n >> q;
    std::cin >> s;
    std::vector<int> vec(n+1, 0);
    for (int i = 1; i < n; ++i) {
        if (s[i-1] == 'A' && s[i] == 'C') {
            vec[i] = vec[i-1] + 1;
        }
        else {
            vec[i] = vec[i-1];
        }
    }
    int l, r;
    for (int i = 0; i < q; ++i) {
        std::cin >> l >> r;
        std::cout << vec[r-1] - vec[l-1] << std::endl;
    }

}


Measured memory_bytes: 1408
#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
#define f(i, n) for(int i = 0; i < n; ++i)
#define pb push_back
typedef long long int ll;

void input(){
   ll n;
   cin >> n;
   cout << ((n) * (n - 1)) / 2 << endl;
}
int main()
{
 input();
 return 0;
}


Measured memory_bytes: 256
import javax.xml.crypto.Data;
import java.util.*;
import java.io.*;

public class Main {
    static int n;
    static int[] A = new int[50];

    public static void main(String[] args) throws IOException{

        //??\???
        /*
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        */

        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for(int i = 0; i < n; i++){
            A[i] = sc.nextInt();
        }
        int q = sc.nextInt();
        int[] m = new int[q];
        for(int i = 0; i < q; i++){
            m[i] = sc.nextInt();
        }

        // ??????
        for(int i = 0; i < q; i++){
            if(solve(0, m[i])) System.out.println("yes");
            else System.out.println("no");
        }

    }

    public static boolean solve(int i, int m){
        if(m == 0) return true;
        if(i >= n) return false;
        return solve(i + 1, m) || solve(i + 1, m - A[i]);
    }

}

Measured memory_bytes: 26872
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define FOR(i,l,r) for(ll i=(l); i<(r); i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const ll INF = 1LL << 60;
const int inf = 1001001001;
const ll mod = 1000000007;
using pp=pair<ll,ll>;
 
// union by size + path having
class UnionFind {
public:
   vector <ll> par; // 各元の親を表す配列
   vector <ll> siz; // 素集合のサイズを表す配列(1 で初期化)
 
   // Constructor
   UnionFind(ll sz_): par(sz_), siz(sz_, 1LL) {
       for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
   }
   void init(ll sz_) {
       par.resize(sz_);
       siz.assign(sz_, 1LL);  // resize だとなぜか初期化されなかった
       for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
  }
 
   // Member Function
   // Find
   ll root(ll x) { // 根の検索
      while (par[x] != x) {
           x = par[x] = par[par[x]]; // x の親の親を x の親とする
       }
       return x;
  }
 
   // Union(Unite, Merge)
   bool unite(ll x, ll y) {
       x = root(x);
       y = root(y);
       if (x == y) return false;
       // merge technique（データ構造をマージするテク．小を大にくっつける)
       if (siz[x] < siz[y]) swap(x, y);
       siz[x] += siz[y];
       par[y] = x;
       return true;
  }
 
  bool same(ll x, ll y) { // 連結判定
       return root(x) == root(y);
  }
 
  ll size(ll x) { // 素集合のサイズ
      return siz[root(x)];
  }
};
 
ll modpow(ll x, ll n) {
   x = x%mod;
   if(n==0) return 1;  //再帰の終了条件
 
   else if(n%2==1) {
       return (x*modpow(x, n-1))%mod;  //nが奇数ならnを1ずらす
   }
   else return modpow((x*x)%mod, n/2)%mod;  //nが偶数ならnが半分になる
}
 
ll com(ll n, ll k) {
   ll x = 1;
   for(int i=n-k+1; i<=n; i++) {
      x = x*i%mod;
   }
 
   ll y = 1;
   for(int i=1; i<=k; i++) {
       y = y*i%mod;
   }
   y = modpow(y, mod-2);
 
   return x*y%mod;
}
 
bool is_prime(const unsigned n){
   switch(n){
       case 0: // fall-through
       case 1: return false;
       case 2: // fall-through
       case 3: return true;
  } // n > 3 が保証された
 
   if(n % 2 == 0 || n % 3 == 0) return false;
   // n は 2 と 3 のいずれの倍数でもないことが保証された
   // これより n は (6の倍数)-1 か (6の倍数)+1 である
 
   // 6の倍数前後の数を使って試し割りをする
   for(unsigned i = 5; i * i <= n; i += 6) {
       if(n % i     == 0) return false; // (6の倍数)-1
       if(n % (i+2) == 0) return false; // (6の倍数)+1
   }
 
   return true;
}
 
int digsum(int n) {
   int res = 0;
   while(n > 0) {
       res += n%10; //ここをres++;に変えたら桁数を求める関数になる
       n /= 10;
   }
   return res;
}
vector<ll> divisor(ll n){
   vector<ll> ret;
   for(ll i = 1 ; i*i <= n ; i++){
       if(n%i == 0){
           ret.push_back(i);
           if(i*i != n) ret.push_back(n/i);
       }
   }
   sort(ret.begin(),ret.end());
   return ret;
}
 
int main(){

    ll n;
    cin >> n;
    ll ans=0;
    for(ll x: divisor(n)){
        if(x==1) continue;
        ll tmp=n;
        while(tmp%x==0) tmp/=x;
        tmp%=x;
        if(tmp==1) ans++;
    }
    ans+=divisor(n-1).size();
    ans--;
    cout << ans << endl;
}

Measured memory_bytes: 3720
n, m = STDIN.gets.split(' ').map(&:to_i)

requests = m.times.map do
  STDIN.gets.split(' ').map(&:to_i)
end

requests.sort_by! {|r| [r[1], r[0]]}

split = 0

target = requests.shift
while (target)
  # p target
  requests.select! {|r| r[0] >= target[1]}
  target = requests.shift
  split += 1
end

puts split

Measured memory_bytes: 14072
l = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
k = int(input())
print(l[k-1])

Measured memory_bytes: 3060
S = input()
N = len(S)
V = [0 for _ in range(len(S))]
Vi = V[:]
def move(S, v):
    next = [0 for _ in range(len(S))]
    for i in range(len(S)):
        if S[i] == 'R':
            next[i + 1] += v[i]
        else:
            next[i - 1] += v[i]
    return next

nearestL = V[:]
nearestR = V[:]
lastL = N - 1
lastR = 0

for i in range(N - 1, -1, -1):
    if S[i] == 'L':
        lastL = i
    else:
        nearestL[i] = lastL
for i in range(N):
    if S[i] == 'R':
        lastR = i
    else:
        nearestR[i] = lastR

count = 0

maxTurn = 0
for i in range(N):
    if S[i] == 'R':
        dist = abs(i - nearestL[i])
        vec = V if dist % 2 == 0 else Vi
        vec[nearestL[i]] += 1
        maxTurn = max(maxTurn, dist)
    else:
        dist = abs(i - nearestR[i])
        vec = V if dist % 2 == 0 else Vi
        vec[nearestR[i]] += 1
        maxTurn = max(maxTurn, dist)
# print(maxTurn)
# print(' '.join(S))
# print(' '.join([str(i) for i in V]))
# print(' '.join([str(i) for i in Vi]))

Vi = move(S, Vi)
for i in range(N):
    V[i] += Vi[i]

# if (maxTurn % 2 == 1):
#     V = move(S, V)
print(' '.join([str(i) for i in V]))


Measured memory_bytes: 16792
n = int(input())
G = []
for i in range(n):
    T = [0]*n
    G.append(T)
for i in range(n):
    L = list(map(int,input().split()))
    for j in range(2,len(L)):
        G[i][L[j]-1] += 1
for i in range(n):
  print(' '.join(map(str,G[i])))


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

int N;
double dp[302][302][302];
vector<int> a;

double calc(int i, int j, int k){
    if(dp[i][j][k]>=0){return dp[i][j][k];}
    if(i==0 && j==0 && k==0){return 0.0;}
    double v = (double)N;
    if(i){v+=i*calc(i-1,j,k);}
    if(j){v+=j*calc(i+1,j-1,k);}
    if(k){v+=k*calc(i,j+1,k-1);}
    dp[i][j][k] = v / (double)(i+j+k);
    return dp[i][j][k];
}

int main(){
    int i;
    int I=0,J=0,K=0;
    
    cin >> N;
    a.resize(N);
    
    for(i=0;i<N;i++){
        cin >> a[i];
        if(a[i]==1){
            I++;
        }
        else if(a[i]==2){
            J++;
        }
        else{
            K++;
        }
    }
    
    memset(dp,-1,sizeof(dp));
    cout << fixed << setprecision(10) << calc(I,J,K) << endl;
    
    return 0;
}


Measured memory_bytes: 215552
#include <iostream>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cassert>
#include <algorithm>
#include <iterator>
#include <string>
#include <vector>
#include <list>
#include <deque>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <tuple>
#include <queue>
#include <stack>
#include <functional>
#include <utility>
#include <complex>
#include <bitset>
#include <numeric>
using namespace std;

#define REP(i,n) for(int (i)=0; (i)<(n) ;++(i))
#define REPN(i,a,n) FOR((i),(a),(a)+(n))
#define FOR(i,a,b) for(int (i)=(a); (i)<(b) ;++(i))
#define PB push_back
#define MP make_pair
#define SE second
#define FI first
#define DBG(a) cerr<<(a)<<endl;
#define ALL(v) (v).begin(),(v).end()
typedef long long LL;  typedef pair<LL, LL> PLL; typedef vector<LL> VLL;
const LL LINF=334ll<<53; const int INF=15<<26; const LL MOD=1E9+7;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    int ans=0;
    FOR(i,1,s.length()){
        if(s[i]!=s[i-1]) ++ans;
    }
    cout << ans <<endl;


    return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <random>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define repp(i,n,m) for (int i = m; i < (n); ++i)
#define repl(i,n) for (long long i = 0; i < (n); ++i)
#define reppl(i,n,m) for (long long i = m; i < (n); ++i)
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using PL = pair<long long, long long>;
using Pxy = pair<double, double>;
using T = tuple<int, int, bool>;
const int INF = 1001001007;
const int mod = 1000000007;
//const int MOD = 998244353;
const ll inf = 1e18;
template <typename AT>
void printvec(vector<AT> &ar){
    rep(i,ar.size()-1) cout << ar[i] << " ";
    cout << ar[ar.size()-1] << endl;
}
template <typename Q>
void printvvec(vector<vector<Q>> &ar){
    rep(i,ar.size()){
        rep(j,ar[0].size()-1) cout << ar[i][j] << " ";
        cout << ar[i][ar[0].size()-1] << endl;
    }
}
template <typename S>
bool range(S a, S b, S x){
    return (a <= x && x < b);
}

int main() {
    int x; cin >> x;
    repp(i,361,1){
        if (x * i % 360 == 0){
            cout << i << endl;
            break;
        }
    }
}

Measured memory_bytes: 3592
#include<bits/stdc++.h>
using namespace std;
int n1,n2;
char a[20],b[20];
int main()
{
	scanf("%s",a+1);
	n1=strlen(a+1);
	scanf("%s",b+1);
	n2=strlen(b+1);
	for(int i=1;i<=n1;i++)
	{
		if(a[i]!=b[i])
		{
			cout<<"No";
			return 0;
		}
	}
	cout<<"Yes";
}

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

void func144b() {
  int n;
  cin >> n;
  if (n > 81) {
    cout << "No";
    return;
  }
  for (int i = 1; i <= 9; i++) {
    for (int j = 1; j <= 9; j++) {
      if (n == i*j) {
        cout << "Yes" << endl;
        return;
      }
    }
  }
  cout << "No" << endl;
}

int main() {
  func144b();
  return 0;
}

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

int main(){
  long n,m,p[1001];
  while(cin>>n>>m,n||m){
    for(int i=1;i<=n;++i) cin>>p[i];
    p[0]=0;
    vector<long> s(0),t(0);
    for(int i=0;i<=n;++i){
      for(int j=0;j<=n;++j) s.push_back(p[i]+p[j]);
    }
    sort(s.begin(),s.end());
    long a=0;
    for(vector<long>::iterator it=s.begin();it!=s.end();++it){
      if(*it*2>m) break;
      a=max(a,*it+*(upper_bound(s.begin(),s.end(),m-*it)-1));
    }
    cout<<a<<endl;
  }
  return 0;
}

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

anss = [0] * (N+1)
for x in range(1, 101):
    for y in range(1, 101):
        for z in range(1, 101):
            a = x*x + y*y + z*z + x*y + y*z + z*x
            if a <= N:
                anss[a] += 1

print('\n'.join(map(str, anss[1:])))


Measured memory_bytes: 67844
#include <bits/stdc++.h>
using namespace std;
template<typename T = int, T mod = 1'000'000'007, typename U = long long>
struct umod{
        T val;
        umod(): val(0){}
        umod(U x){ x %= mod; if(x < 0) x += mod; val = x;}
        umod& operator += (umod oth){ val += oth.val; if(val >= mod) val -= mod; return *this; }
	umod& operator -= (umod oth){ val -= oth.val; if(val < 0) val += mod; return *this; }
	umod& operator *= (umod oth){ val = ((U)val) * oth.val % mod; return *this; }
	umod& operator /= (umod oth){ return *this *= oth.inverse(); }
        umod& operator ^= (U oth){ return *this = pwr(*this, oth); }
	umod operator + (umod oth) const { return umod(*this) += oth; }
	umod operator - (umod oth) const { return umod(*this) -= oth; }
	umod operator * (umod oth) const { return umod(*this) *= oth; }
	umod operator / (umod oth) const { return umod(*this) /= oth; }
        umod operator ^ (long long oth) const { return umod(*this) ^= oth; }
	bool operator < (umod oth) const { return val < oth.val; }
	bool operator > (umod oth) const { return val > oth.val; }
	bool operator <= (umod oth) const { return val <= oth.val; }
	bool operator >= (umod oth) const { return val >= oth.val; }
	bool operator == (umod oth) const { return val == oth.val; }
	bool operator != (umod oth) const { return val != oth.val; }
        umod pwr(umod a, U b) const { umod r = 1; for(; b; a *= a, b >>= 1) if(b&1) r *= a; return r; }
        umod inverse() const {
		U a = val, b = mod, u = 1, v = 0;
		while(b){
			U t = a/b;
			a -= t * b; swap(a, b);
			u -= t * v; swap(u, v);
		}
		if(u < 0)
			u += mod;
		return u;
        }
};
using U = umod<>;
const int maxn = 100100;
U f[maxn];
int main(){
	map<int, int> cnt;
	cnt[-1] = 3;
	f[0] = 1;
	int n; cin >> n;
	int q0 = 0;
	for(int i = 1; i <= n; i++){
		int x; cin >> x;
		f[i] = f[i - 1] * (cnt[x - 1] - cnt[x]);
		cnt[x]++;
		q0 += (x == 0);
	}
	cout << f[n].val << endl;
	return 0;
}


Measured memory_bytes: 5376
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;

#define rep(i,a) for(int i = 0 ; i < a ; i ++)
#define vi vector<int>

int main(void){
  string s;
  cin>>s;
  int cnt = 0;
  string ss = "CODEFESTIVAL2016";
  rep(i,s.size()){
    if(ss[i] != s[i])cnt++;
  }
  cout<<cnt<<endl;

}

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

int n,ans=0,a[2005];

bool cmp(int a,int b)
{
	return a<b;
}

signed main()
{
	cin>>n;
	for (int i=1;i<=n;i++)  cin>>a[i];
	
	sort(a+1,a+n+1,cmp);
	
	for (int i=n;i>=3;i--)
	{
		for (int j=i-1;j>=2;j--)
		{
			int k=upper_bound(a+1,a+j,a[i]-a[j])-a;
			ans+=(j-k);
		}
	}
	cout<<ans<<endl;
	
	return 0;
}

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

using namespace std;

typedef long long ll;

const int INF = 1e9;

int main()
{
  int n;
  cin >> n;
  int taro = 0, hanako = 0;
  for (int i = 0; i < n; ++i) {
    string s1, s2;
    cin >> s1 >> s2;
    if (s1 == s2) { ++taro, ++hanako; }
    else if (s1 > s2) { taro += 3; }
    else { hanako += 3; }
  }
  fprintf(stdout, "%d %d\n", taro, hanako);
  return 0;
}

Measured memory_bytes: 1212
A, B, C = map(int, raw_input().split())
count_5 = 0
count_7 = 0
for n in [A, B, C]:
    if n == 5:
        count_5 += 1
    elif n == 7:
        count_7 += 1
if count_5 == 2 and count_7 == 1:
    print 'YES'
else:
    print 'NO'

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

inline int read()
{
	int sum=0,ff=1; char ch=getchar();
	while(!isdigit(ch))
	{
		if(ch=='-') ff=-1;
		ch=getchar();
	}
	while(isdigit(ch))
		sum=sum*10+(ch^48),ch=getchar();
	return sum*ff;
}

int n,x,y,dis[100005];

int main()
{
	n=read();
	x=read();
	y=read();
	for ( int i=1;i<=n;i++ ) 
		for ( int j=i+1;j<=n;j++ ) 
		{
			int d=min(j-i,abs(i-x)+abs(j-y)+1);
			dis[d]++;
		}
	for ( int i=1;i<n;i++ ) printf("%d\n",dis[i]);
	return 0;
}
				
				
		
		

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

int main(){
  int group[] = {0, 0, 2, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0};
  int x, y; cin >> x >> y;

  cout << ((group[x]==group[y])? "Yes": "No") << endl;

  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

  int main(void)
{
  int W,H,x,y,r;
   scanf("%d %d %d %d %d", &W, &H, &x, &y, &r);

 if(x >= r && W-r >= x && y >= r && H-r >= y){
   printf("Yes\n");
 } else {
   printf("No\n");
}

  return 0;
}

Measured memory_bytes: 584
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
const int mxn = 2e5 + 1;
ll arr[mxn], dp[mxn], pref[mxn];
 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n;cin>>n;
	for(int i = 1; i<=n; ++i) cin>>arr[i];
	dp[0] = 0;
	pref[0] = 0;
	pref[1] = arr[1];
	for(int i = 2; i <=n; ++i) pref[i] = pref[i-2] + arr[i];
	dp[1] = 0;
	for(int i = 2; i <=n; ++i){
		if(i&1){
			dp[i] = max(dp[i-1], dp[i-2] + arr[i]);
		} else{
			dp[i] = max(dp[i-2] + arr[i], pref[i-1]);
		}
	}
	cout<<dp[n]<<endl;
	return 0;
}
 

Measured memory_bytes: 8336
#include <bits/stdc++.h>
using namespace std ;
void Read ( int &x, char c = getchar() ) {
	for ( x = 0 ; !isdigit(c) ; c = getchar() ) ;
	for ( ; isdigit(c) ; c = getchar() ) x = 10*x + c - '0' ;
}
int main() {
	int n, i, x, y, t, ct, cx, cy, dt, dd ;
	ct = cx = cy = 0 ;
	bool fg = 1 ;
	Read(n) ;
	for ( i = 1 ; i <= n ; i ++ ) {
		Read(t) ; Read(x) ; Read(y) ;
		dt = t-ct ;
		dd = abs(x - cx) + abs(y - cy) ;
		if (dd <= dt && (dd - dt)%2 == 0) ;
		else fg = 0 ;
		ct = t, cx = x, cy = y ;
	}
	if (fg) puts("Yes") ;
	else puts("No") ;
	return 0 ;
}

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

using namespace std;
typedef long long ll;
typedef long double ld;
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i,n) for(int i=n; i>-1; --i)
#define ALL(a) (a).begin(),(a).end()
#define FILL(a,n,x); REP(i,(n)){ (a)[i]=(x); }
#define CINA(a,n); REP(i,(n)){ cin >> (a)[i]; }
#define FILL2(a,n,m,x); REP(i,(n)){ REP(j,(m)){(a)[i][j]=(x);} }
#define CINA2(a,n,m); REP(i,(n)){ REP(j,(m)){cin >> (a)[i][j];} }
#define Liny "Yes\n"
#define Linn "No\n"
#define LINY "YES\n"
#define LINN "NO\n"

//cout << setfill('0') << right << setw(4) << 12; // "0012"
int keta(ll x){ if(x<10){return 1;} else{return keta(x/10) + 1;}}
int keta_wa(ll x){ if(x<10){return x;} else{return keta_wa(x/10) + x%10;} }
int ctoi(char c){ return ( (c>='0' && c<='9')? c - '0': 0 );}
int __stoi(string s){ return atoi(s.c_str()); }
ll sum(ll a[],ll N){ return accumulate(a,a+N,0LL);}
ll gcd(ll a,ll b){if(a<b)swap(a,b); return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){if(a<b){swap(a,b);} return a/gcd(a,b)*b;}
template<class T> void chmax(T& a, T b){ if(a<b){a=b;} }
template<class T> void chmin(T& a, T b){ if(a>b){a=b;} }
template<class T> bool isIn(T a,vector<T> v){ for(T x:v){ if(a==x){return true;}} return false;}
string strReplace(string s,string target, string replacement){
    if (!target.empty()) {
      std::string::size_type pos = 0;
      while ((pos = s.find(target, pos)) != std::string::npos) {
        s.replace(pos, target.length(), replacement);
        pos += replacement.length();
      }
    }
    return s;
}
const ll MOD = 1e9+7;
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MP make_pair

int main(){
    int A,B; cin>>A>>B;
    cout << A*B << "\n";
}

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

int main() {
	int A, B;
	int max;
	cin >> A >> B;
	max = A + B;
	if (max < A - B) {
		max = A - B;
	}
	if (max < A*B) {
		max = A*B;
	}
	cout << max << "\n";
}

Measured memory_bytes: 256
#include<iostream>
#include<math.h>
using namespace std;
int main()
{
	int n,i,x,y,f,s,t,l,ti;
	scanf("%d",&n);
	s=t=l=f=0;
	for(i = 1;i<=n;i++)
	{
		scanf("%d%d%d",&ti,&x,&y);
		if((abs(x-s)+abs(y-t))>(ti-l))
		f=1;
		if((abs(x-s)+abs(y-t))<(ti-l))
		if(((ti-l)%2)!=((abs(x-s)+abs(y-t))%2))
		f=1;
		s=x;t=y;l=ti;
		//printf("%d%d\n",s,t);
	 } 
	 if(f) printf("No\n");
	 else printf("Yes\n");
 } 

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

int main() {
	
	int n, d;
	cin >> n >> d;
	d = 2*d + 1;
	int ans = (n+d-1)/d;
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void){
    int a=9,b=9,c=9,d=9,n,i,j,m,t,k,l;
    while(scanf("%d",&n)!=EOF){
    t=0;
    for(i=0;i<10;i++){
        for(j=0;j<10;j++){
            for(k=0;k<10;k++){
                for(l=0;l<10;l++){
                    if(n==i+j+k+l){
                        t++;
                    }
                }
            }
        }
    }
    printf("%d\n",t);
    }
return 0;
}

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

int main(void){
    char s[5];
    cin >> s;
    
    int cost = 700;
    int i;
    for(i = 0; i <= 2; i++){
        if(s[i] == 'o'){
            cost += 100;
        }
    }
    
    cout << cost << endl;
    
    return 0;
}


Measured memory_bytes: 256
class Main{

	public static void main (String[] args) {

		Main main = new Main();

		java.util.Scanner sc = new java.util.Scanner(System.in);

		String weather = sc.next();

		int count = 0;
		int max = 0;

		for (int index=0; index<weather.length(); index++) {
			if (weather.charAt(index)=='R') {
				count++;
			} else {
				if (count>max) {
					max = count;
				}
				count=0;
			}
		}
		if (count>max) {
			max = count;
		}
		System.out.println(max);
		sc.close();
	}
}

Measured memory_bytes: 35576
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from pprint import pprint
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, W, WV):
    items = defaultdict(list)
    for w, v in WV:
        items[w].append(v)

    for w in items:
        items[w].sort(reverse=True)

    for i in range(4-len(items)):
        items[-i] = []
    ws = list(items.keys())

    @lru_cache(maxsize=None)
    def f(rw, i, j, k, l):
        ret = 0
        if ws[0] <= rw and i < len(items[ws[0]]):
            ret = max(ret, f(rw - ws[0], i+1, j, k, l) + items[ws[0]][i])
        if ws[1] <= rw and j < len(items[ws[1]]):
            ret = max(ret, f(rw - ws[1], i, j+1, k, l) + items[ws[1]][j])
        if ws[2] <= rw and k < len(items[ws[2]]):
            ret = max(ret, f(rw - ws[2], i, j, k+1, l) + items[ws[2]][k])
        if ws[3] <= rw and l < len(items[ws[3]]):
            ret = max(ret, f(rw - ws[3], i, j, k, l+1) + items[ws[3]][l])

        return ret

    return f(W, 0, 0, 0, 0)


def main():
    N, W = read_int_n()
    WV = [read_int_n() for _ in range(N)]

    print(slv(N, W, WV))


if __name__ == '__main__':
    main()


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

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("maxflow.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll x,y;
    cin>>x>>y;
    ll cnt=0;
    while(x<=y){
        cnt++;
        x*=2;
    }
    cout<<cnt<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<typename T> using gpp_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename L> using gpp_map = tree<T, L, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using gpp_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;*/
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define Sort(v) sort(v.begin(), v.end())
#define Reverse(v) reverse(v.begin(), v.end())
#define all(v) v.begin(),v.end()
#define SZ(v) ((int)v.size())
#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))
#define Max(a, b) a = max(a, b)
#define Min(a, b) a = min(a, b)
#define bit(n) (1LL<<(n))
#define bit_exist(x, n) ((x >> n) & 1)
#define debug(x) cout << #x << "=" << x << endl;
#define vdebug(v) { cout << #v << "=" << endl; REP(i_debug, v.size()){ cout << v[i_debug] << ","; } cout << endl; }
#define mdebug(m) { cout << #m << "=" << endl; REP(i_debug, m.size()){ REP(j_debug, m[i_debug].size()){ cout << m[i_debug][j_debug] << ","; } cout << endl;} }
#define Return(ans) { cout << (ans) << endl; return 0; }
#define pb push_back
#define f first
#define s second
#define int long long
#define INF 1000000000000000000
template<typename T> istream &operator>>(istream &is, vector<T> &v){ for (auto &x : v) is >> x; return is; }
template<typename T> ostream &operator<<(ostream &os, vector<T> &v){ for(int i = 0; i < v.size(); i++) { cout << v[i]; if(i != v.size() - 1) cout << endl; }; return os; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, pair<T1, T2> p){ cout << '(' << p.first << ',' << p.second << ')'; return os; }
template<typename T> void Out(T x) { cout << x << endl; }
template<typename T1, typename T2> void Ans(bool f, T1 y, T2 n) { if(f) Out(y); else Out(n); }
 
using vec = vector<int>;
using mat = vector<vec>;
using Pii = pair<int, int>;
using PiP = pair<int, Pii>;
using PPi = pair<Pii, int>;
using bools = vector<bool>;
using pairs = vector<Pii>;
 
//int dx[4] = {1,0,-1,0};
//int dy[4] = {0,1,0,-1};
//char d[4] = {'D','R','U','L'};
 
const int mod = 1000000007;
//const int mod = 998244353;
//#define Add(x, y) x = (x + (y)) % mod
//#define Mult(x, y) x = (x * (y)) % mod


#include <bits/stdc++.h>
using namespace std;
bool solve(string S){
    map<char,int> MAP;
    REP(i,S.size()){
        if(MAP.count(S[i])) MAP[S[i]]=1;
        else MAP[S[i]] = 1;
    }
    if(MAP['N']!=MAP['S']) return false;
    if(MAP['W']!=MAP['E']) return false;
    return true;
}

signed main(){
    string S; cin>>S;
    if(solve(S)) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}


Measured memory_bytes: 256
class TopologicalSort

  class Node
    attr_accessor :id, :indeg, :to, :color
    def initialize(id)
      @id = id
      @indeg = 0
      @to = []
      @color = "WHITE"
    end
  end

  def initialize
    v, e = gets.split.map &:to_i
    @nodes = Array.new(v).map.with_index { |n, i| Node.new(i) }
    @result = []
    @q = []
    e.times do
      s, t = gets.split.map &:to_i
      @nodes[t].indeg += 1
      @nodes[s].to << @nodes[t]
    end
  end

  def bfs(s)
    @q.push s
    s.color = "GRAY"
    while !@q.empty?
      u = @q.shift
      @result.push u.id
      u.to.each do |v|
        v.indeg -= 1
        if v.indeg == 0 && v.color == "WHITE"
          v.color = "GRAY"
          @q.push v
        end
      end
    end
  end

  def solve
    @nodes.each do |n|
      bfs(n) if n.indeg == 0 && n.color == "WHITE"
    end
  end

  def dump
    @result.each do |o|
      puts o
    end
  end
end

# main
t = TopologicalSort.new
t.solve
t.dump

Measured memory_bytes: 11172
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>

using namespace std;

struct Union_find{
	vector<int> par;
	vector<int> rank;
	Union_find(int p){
		par = vector<int>(p + 1);
		rank = vector<int>(p + 1);
		for(int i = 1; i <= p; i++){
			par[i] = i;
		}
	}
	int find(int x){
		if(par[x] == x)
			return x;
		else{
			return par[x] = find(par[x]);
		}
	}
	void unite(int x, int y){
		x = find(x);
		y = find(y);
		if(x == y) return;
		if(rank[x] < rank[y]){
			par[x] = y;
		} else{
			par[y] = x;
			if(rank[x] == rank[y]) rank[x]++;
		}
	}
	bool same(int x, int y){
		return find(x) == find(y);
	}
};

int main(){
	int n, m, ans = 0;
	cin >> n >> m;
	vector<vector<int>> l(m + 1);
	for(int i = 1; i <= n; i++){
		int k;
		cin >> k;
		for(int j = 0; j < k; j++){
			int x;
			cin >> x;
			l[x].emplace_back(i);
		}
	}
	Union_find uf(n);
	for(int i = 1; i <= m; i++){
		if(l[i].size() < 2) continue;
		for(int j = 1; j < l[i].size(); j++){
			uf.unite(l[i][0], l[i][j]);
		}
	}
	bool f = true;
	for(int i = 2; i <= n; i++){
		if(!uf.same(1, i)){
			f = false;
			break;
		}
	}
	cout << (f? "YES" : "NO") << endl;
	return 0;
}


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

int main(){
    int A, B, M;
    cin >> A >> B >> M;

    vector<int> a(A), b(B), x(M), y(M), c(M), k(M);
    for(int lp=0; lp<A; lp++) cin >> a[lp];
    for(int lp=0; lp<B; lp++) cin >> b[lp];
    for(int lp=0; lp<M; lp++){
        cin >> x[lp] >> y[lp] >> c[lp];
        k[lp] = a[x[lp]-1] + b[y[lp]-1] - c[lp];
    }

    int u = *min_element(a.begin(), a.end()) + *min_element(b.begin(), b.end());

    int j = *min_element(k.begin(), k.end());

    cout << (j > u ? u : j) << endl;
}

Measured memory_bytes: 2560
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int[][] a = new int[n][m];
		int[] numoflover = new int[m];
		int answer = 0;
		for(int i = 0; i < n; i++) {
			int num = sc.nextInt();
			for(int j = 0; j < num; j++) {
				a[i][j] = sc.nextInt();
				for(int k = 0; k < m; k++)
					if(a[i][j] == k+1)
						numoflover[k] += 1;
			}
		}
		for(int j = 0; j < m; j++)
			if(numoflover[j] == n) answer += 1;
		System.out.println(answer);
	}

}

Measured memory_bytes: 21844
#include <bits/stdc++.h>
#define pb          emplace_back
#define ll          long long
#define fi          first
#define se          second
#define mp          make_pair

using namespace std;

typedef pair<int, int> pii;
const int N = 1001;
const int inf = int(1e9);

int n, x[N], p;
vector<int> a[N];

pii DFS(int u) {
    if(a[u].empty()) return mp(x[u], 0);
    bitset<5001> f; int sum = 0;
    f.set(0);
    for(int v: a[u]) {
        pii res = DFS(v);
        f = (f << res.fi | f << res.se);
        sum += res.fi + res.se;
    }
    for(int i = x[u]; i >= 0; --i) if(f[i]) return mp(x[u], sum - i);
    cout << "IMPOSSIBLE"; exit(0);
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define Task        "test"
    if(fopen(Task".inp", "r")) {
        freopen(Task".inp", "r", stdin);
        freopen(Task".out", "w", stdout);
    }
    cin >> n;
    for(int i = 2; i <= n; ++i) cin >> p, a[p].pb(i);
    for(int i = 1; i <= n; ++i) cin >> x[i];
    DFS(1);
    cout << "POSSIBLE";
}


Measured memory_bytes: 1664
from collections import deque

if __name__ == '__main__':
    res = deque([])
    n_order = int(input())
    for i in range(n_order):
        order = input().split()
        if 'insert' == order[0]: 
            res.appendleft(order[1])
        elif 'delete' == order[0]:
            if order[1] in res:
                res.remove(order[1])
        elif 'deleteFirst' == order[0]:
            res.popleft()
        elif 'deleteLast' == order[0]: 
            res.pop()
    print(' '.join(res))


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

#define pb push_back
#define mp make_pair

typedef long long ll;
typedef pair<int, int> pii;

const int inf = 1e9;
const ll linf = 1e18;
const ll mod = 1e9 + 7;

int main()
{
  int a, b, c, d, e, f;
  cin >> a >> b >> c >> d >> e >> f;

  double ans = -1.0;
  int answ, anss;
  for(int i = 0; 100*a*i <= f; i++){
    for(int j = 0; 100*a*i+100*b*j <= f; j++){
      for(int k = 0; 100*a*i+100*b*j+c*k <= f; k++){
        for(int l = 0; 100*a*i+100*b*j+c*k+d*l <= f; l++){
          int w = 100*a*i + 100*b*j;
          int s = c*k + d*l;

          if(w+s == 0) continue; 
          if(w+s > f) continue;
          if(w*e < s*100) continue;

          double x = 100.0*s/(w+s);
          if(ans < x){
            ans = x;
            answ = w;
            anss = s;
          }
        }
      }
    }
  }

  cout << answ+anss << " " << anss << endl;

  return 0;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include"bits/stdc++.h"
#ifdef _DEBUG
#define DBG(n) n
#else
#define DBG(n)
#endif
#define INF          1e9
#define INFLL        1e18
#define EPS          1e-9
#define MOD          1000000007
#define REP(i,n)     for(ll i=0,i##_len=(n);i<i##_len;++i)
#define REP1(i,n)    for(ll i=1,i##_len=(n);i<=i##_len;++i)
#define REPR(i,n)    for(ll i=(n)-1;i>=0;--i)
#define REPR1(i,n)   for(ll i=(n);i>0;--i)
#define REPC(i,obj)  for(auto i:obj)
#define ALL(obj)     (obj).begin(),(obj).end()
#define SETP(n)      cout<<fixed<<setprecision(n)
#define VV(T,h,w)    move(vector<vector<T>>(h,move(vector<T>(w))))
#define VVI(T,h,w,i) move(vector<vector<T>>(h,move(vector<T>(w,i))))
using namespace std;
using ll = long long;
template<typename T = ll>inline T in() { T ret; cin >> ret; return ret; }

int main()
{
	ll n = in(), m = in();
	cout << (n - 1) * (m - 1) << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <chrono>
#include <random>
#include <functional>

using namespace std;

typedef long double ld;

const ld pi = acos(-1);

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);	

	int a, b;
	cin >> a >> b;
	int h, m;
	cin >> h >> m;
	ld ah = -((60 * h + m) / ((ld)12 * (ld)60));
	ld am = -(m / (ld)60);
	// cerr << ah <<
	ah *= 2 * pi;
	am *= 2 * pi;
	ld dx = (a * cos(ah) - b * cos(am));
	ld dy = (a * sin(ah) - b * sin(am));
	// cerr << dx << ' ' << dy << endl;
	cout << fixed << setprecision(16);
	cout << sqrt(dx * dx + dy * dy) << endl;
}

Measured memory_bytes: 3608
n=int(input())
l=[list(map(int, input().split())) for i in range(n)]
for i in range(n-1):
    a=1
    b=1
    if l[i+1][0]<l[i][0]:
        a=-(-l[i][0]//l[i+1][0])
    if l[i+1][1]<l[i][1]:
        b=-(-l[i][1]//l[i+1][1])
    l[i+1][0]*=max(a,b)
    l[i+1][1]*=max(a,b)
print(sum(l[-1]))

Measured memory_bytes: 3188
/*
 * https://atcoder.jp/contests/abc152/tasks/abc152_e
 * Flatten.
 */

# include<iostream>
# include<vector>
# include<algorithm>

const long long MOD = 1e9+7;
const long long MAX_N = 1e6+5;

long long gcd(long long a, long long b)
{
    if(b == 0) return a;
    return gcd(b, a % b);
}

long long inverse(long long a, long long b, long long& x, long long& y)
{
    if( b == 0)
    {
        x = 1;
        y = 0;

        return a;
    }
    
    long long x1, y1;
    long long d = inverse(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);

    return d;
}


long long modpow(long long a, long long n, long long mod=MOD)
{
    long long res = 1;
    while (n > 0)
    {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

long long modinv(long long a, long long mod=MOD)
{
    return modpow(a, mod - 2, mod);
}

std::vector<std::pair<long long, long long>> prime_devisor(long long n)
{
    std::vector<std::pair<long long, long long>> res;
    for(long long p = 2; p * p <= n; p++)
    {
        if(n % p != 0) continue;
        
        long long num = 0;
        while(n % p == 0)
        {
            ++num;
            n /= p;
        }
        res.push_back(std::make_pair(p, num));
    }
    if(n != 1) res.push_back(std::make_pair(n, 1));

    return res;
}

long long solve(std::vector<long long>& a)
{
    std::vector<long long> mem(MAX_N, 0);

    for(int i = 0; i < a.size(); i++)
    {
        auto pd = prime_devisor(a[i]);
        for(auto p: pd) mem[p.first] = std::max(mem[p.first], p.second);
    }

    long long lcm = 1;
    for(int i = 2; i < MAX_N; i++) lcm = lcm*modpow(i, mem[i]) % MOD;

    long long ans = 0;
    for(int i = 0; i < a.size(); i++)
    {
        ans += lcm*modinv(a[i])%MOD;
    }

    return ans % MOD;
}

int main()
{
    int n;
    long long num, index = 0;
    std::cin>>n;

    std::vector<long long> a(n);
    while(n--)
    {
        std::cin>>num;
        a[index++] = num;
    }
    std::cout<<solve(a)<<std::endl;
    //std::cout<<MOD<<" "<<MAX_N;

    return 0;
}


Measured memory_bytes: 11152