akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
using vi  = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;

int main() {
  vvi c(3, vi(3));
  rep(i, 3) {
    rep(j, 3) {
      cin >> c[i][j];
    }
  }
  int a, b;
  a = c[0][0] - c[0][1];
  b = c[0][1] - c[0][2];
  bool check = false;
  rep(i, 2) {
    if (c[i+1][0] - c[i+1][1] == a && c[i+1][1] - c[i+1][2] == b) {
      check = true;
    }
    else {
      check = false;
      break;
    }
  }
  if (check) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}


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

    int main()
    {
        int a,b,c,d,e;
        cin>>a>>b>>c>>d>>e;
        if (a==0){
            cout<<1;
        }
        else if (b==0){
            cout<<2;
        }
        else if (c==0){
            cout<<3;
        }
        else if (d==0){
            cout<<4;
        }
        else{
            cout<<5;
        }

    }


Measured memory_bytes: 3620
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <math.h>
#include <cassert>
#define rep(i,n) for(int i = 0; i < n; ++i )
using namespace std;
using ll = long long;
using P = pair<int,int>;

int inf = 1001001001;
int main() {
  int n,t;
  cin >> n >> t;
  vector<int> a(n);
  rep(i,n) cin >> a[i];
  vector<int> l(n+1,inf),r(n+1,0);
  rep(i,n) l[i+1] = min(l[i],a[i]);
  rep(i,n) r[n-1-i] = max(l[n-i],a[n-1-i]);
  map<int,int> m;
  rep(i,n-1){
    int d = r[i+1]-l[i+1];
    if(d>0) m[d]++;
  }
  int ans = m.rbegin()->second;
  cout << ans << endl;
}

Measured memory_bytes: 9004
#include<stdio.h>
#include<map>
using namespace std;
map<int,int> idx;
int q,lim;
int seg[1<<20];
int seg_size;
int data[400000];
int count;
void init(int size){
	seg_size=1;
	while(seg_size<size)seg_size*=2;
	for(int i=0;i<seg_size*2-1;i++)seg[i]=0;
}
void add(int i,int x){
	i+=seg_size-1;
	seg[i]+=x;
	while(i>0){
		i=(i-1)/2;
		seg[i]=seg[i*2+1]+seg[i*2+2];
	}
}
int query(int a,int b,int k,int l,int r){
	if(r<=a||b<=l)return 0;
	if(a<=l&&r<=b)return seg[k];
	int vl=query(a,b,k*2+1,l,(l+r)/2);
	int vr=query(a,b,k*2+2,(l+r)/2,r);
	return vl+vr;
}
int find(int x,int k,int l,int r){
	if(r==l+1)return l;
	int vl=seg[k*2+1];
	if(x<=vl)return find(x,k*2+1,l,(l+r)/2);
	return find(x-vl,k*2+2,(l+r)/2,r);
}
void enkan(int x){add(find(x,0,0,seg_size),-1);}
int incubate(int x){
	idx[x]=count;
	data[count]=x;
	add(count,1);
	count++;
	if(query(0,count,0,0,seg_size)>lim)enkan(1);
}
int main(){
	int i,j;
	while(1){
		scanf("%d %d",&q,&lim);
		if(q==0)return 0;
		idx.clear();
		init(q);
		count=0;
		for(i=0;i<q;i++){
			int type,x;
			scanf("%d %d",&type,&x);
			if(type==0)incubate(x);
			if(type==1)enkan(x);
			if(type==2)printf("%d\n",data[find(x,0,0,seg_size)]);
			if(type==3)add(idx[x],-1);
		}
		printf("end\n");
	}
}
	

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

int main(){
  int n,k;
  cin>> n >> k;
  vector<int> v(n);
  for (int i=0; i<n; i++){
    cin>> v.at(i);
  }
  
  int num=min(n,k)+1;
  vector<int> l(num),r(num); //l[i],r[i]は左、右からi回操作したときの最大価値(0<=i<=k)
  stack<vector<int>> ln,rn;
  for (int i=1; i<num; i++){
    int lv=v.at(i-1),rv=v.at(n-i);
    l.at(i)=l.at(i-1)+lv;
    r.at(i)=r.at(i-1)+rv;
    if (lv<0) ln.push({i,lv});
    if (rv<0) rn.push({i,rv});
  }
  while (!ln.empty()){ //同じ操作回数で負の価値の宝石を戻した方が価値が高くなるなら戻す
    int p=ln.top().at(0);
    int var=ln.top().at(1);
    for (int i=num-1; i>p; i--){
      l.at(i)=max(l.at(i),l.at(i-1)-var);
    }
    ln.pop();
  }
  while (!rn.empty()){
    int p=rn.top().at(0);
    int var=rn.top().at(1);
    for (int i=num-1; i>p; i--){
      r.at(i)=max(r.at(i),r.at(i-1)-var);
    }
    rn.pop();
  }
  
  int ans=0;
  for (int i=0; i<num; i++){
    for (int j=0; j<num; j++){
      if (i+j>k) break;
      ans=max(ans,l.at(i)+r.at(j));
    }
  }
  
  int max=0; //この解き方だとk>nの時同じ宝石を重複して数えることがあるので確認
  for (int i=0; i<n; i++) if (v.at(i)>0) max+=v.at(i);
  ans=min(ans,max);
  
  cout<< ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
char c;
int main()
{
 while(cin>>c)
 {
   if(c=='A') cout<<"T\n";
   if(c=='C') cout<<"G\n"; 
   if(c=='T') cout<<"A\n"; 
   if(c=='G') cout<<"C\n"; 
 }
  
}

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

using namespace std;
typedef long long ll;
typedef pair <ll, ll> l_l;
typedef pair<int, int> i_i;

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

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

# define EPS (1e-7)
# define INF (1e9)
# define PI (acos(-1))
//const ll mod = 1000000007;

int N;
map<string, int> memo;

int main() {
    cin >> N;
    for (int i = 0; i < N; ++i) {
        string s;
        cin >> s;
        memo[s] += 1;
    }
    int max_count = 0;
    for (auto &x : memo) {
        if (x.second > max_count) max_count = x.second;
    }
    for (auto it = memo.begin(); it != memo.end(); it++) {
        if (it->second == max_count) cout << it->first << endl;
    }
    return 0;
}

Measured memory_bytes: 25216
#include<iostream>
using namespace std;
typedef long long ll;

int main(){
	ll n, p; cin >> n >> p;
	ll dp[51][2];
	for(int i = 0; i <= 50; ++i){
		dp[i][0] = dp[i][1] = 0;
	}
	dp[0][0] = 1;
	for(int i = 1; i <= n; ++i){
		int a; cin >> a;
		dp[i][0] = dp[i - 1][0] + (a & 1 ? dp[i - 1][1] : dp[i - 1][0]);
		dp[i][1] = dp[i - 1][1] + (a & 1 ? dp[i - 1][0] : dp[i - 1][1]);
	}
	cout << dp[n][p] << endl;
	return 0;
}

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

const int INF = 1100000000;

int main() {
  int n, max, min;
  int a[101];
  cin >> n;
  max = -INF;
  min = INF;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    if (max < a[i]) {
      max = a[i];
    }
  }
  for (int i = 0; i < n; i++) {
    if (min > a[i]) {
      min= a[i];
    }
  }
  cout << max - min << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<sstream>
#include<iterator>
#include<list>

using namespace std;

typedef  long long int lint;

#define rep(i, n) for (lint i = 0; i < n; i++)
#define sort(v) sort((v).begin(), (v).end())
#define reverse(v) reverse((v).begin(), (v).end())
#define upper(v,hoge) upper_bound(v.begin(),v.end(),hoge)
#define lower(v,hoge) lower_bound(v.begin(),v.end(),hoge)
#define llower(v,hoge) *lower_bound(v.begin(), v.end(), hoge)
#define lupper(v,hoge) *upper_bound(v.begin(), v.end(), hoge)
#define mp make_pair
#define IP pair<int,int>
#define enld endl

int main() {
	vector<int>A(4);
	vector<int>B(4);
	while (cin >> A[0] >> A[1] >> A[2] >> A[3] >> B[0] >> B[1] >> B[2] >> B[3]) {
		int ans1 = 0;
		int ans2 = 0;
		rep(i, 4) {
			if (A[i] == B[i]) {
				ans1++;
			}
		}
		rep(i, 4) {
			rep(j, 4) {
				if (A[i] == B[j]) {
					ans2++;
				}
			}
		}
		cout << ans1 << ' ' << ans2 - ans1 << endl;
	}
}


Measured memory_bytes: 3096
#include <stdio.h>

int main()
{
	int n;
	double v, y;

	while(scanf("%lf", &v) != EOF){
		y = v*v/19.6;

		n = (int)((y+5)/5);

		if((double)n < (y+5)/5) n++;
	
		printf("%d\n", n);
	}

	return 0;
}

Measured memory_bytes: 1056
#include <bits/stdc++.h>
using namespace std;
//#include <boost/algorithm/string.hpp>
#define ll long long int
#define MOD 1000000007


int main()
{
    ll n,i,j,k,c=0,d=0,flag=0,max=0,min1=10000000000,max1=0,l,r,T,m,x,y,count1=0,q;
   /* freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);*/
	string s;
	cin>>s;
	for(i=0;i<s.size()/2;i++)
    {
      if(s[i]==s[s.size()-1-i])
      {
          continue;
      }
      else{
        count1++;
      }
    }
    cout<<count1<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
int N,M;
int dp[1<<12];
int C[1000],A[1000];
main()
{
	cin>>N>>M;
	for(int i=0;i<M;i++)
	{
		int b;cin>>A[i]>>b;
		for(;b--;)
		{
			int c;cin>>c;
			c--;
			C[i]|=1<<c;
		}
	}
	for(int i=1;i<1<<N;i++)dp[i]=1e9;
	for(int i=0;i<1<<N;i++)
	{
		for(int j=0;j<M;j++)
		{
			dp[i|C[j]]=min(dp[i|C[j]],dp[i]+A[j]);
		}
	}
	int ans=dp[(1<<N)-1];
	cout<<(ans<1e9?ans:-1)<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <map>
#include <cstdlib>
#include <math.h>

using namespace std;

typedef long long ll;
#define rep(i, n) for(long (i) = 0; (i) < (long) (n); (i)++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define rrep(i,a,b) for(long i=(a);i<(b);i++)
#define rrep1(i,a,b) for(long i=(a);i<=(b);i++)
#define rrrep(i,a,b) for(long i=(a);i>=(b);i--)
#define define pb push_back
#define ALL(obj) (obj).begin(), (obj).end()
#define X first
#define Y second
#define vi vector<int>
#define vl vector<ll>
#define vvi vector<vector<int> >
#define vpl vector<pair<long, long> >
#define vppl vector<pair<long, pair<long, long> > >

const int INF = 100100100;
const long LONG_INF = 2147483647;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;
const ll LINF = 1e18;


int pow(int x) {
	if (x == 0) {
		return 1;
	}
	else {
		return pow(x - 1) * 2;
	}
}

int main(int argc, char const *argv[])
{
	cin.tie(0);
	ios::sync_with_stdio(false);
    int a,b,c;
    cin >> a >> b >> c;
    int x = b / a;
    if (x > c) {
        cout << c << endl;
    } else
    {
        cout << x << endl;
    }
    
    
    return 0;
}


Measured memory_bytes: 256
/*~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=
*$* WRITER:kakitamasziru/OxOmisosiru *$*
~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=*/
#ifdef LOCAL_JUDGE
#define _GLIBCXX_DEBUG //FOR THE DEBUG! COMMENT OUT THIS WHEN SUBMITTING!
#endif
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <iomanip>
#include <limits>//setprecision
//#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
//#include <unordered_set> //unordered_set
#include <stack> // stack
#include <deque> // deque
#include <math.h>//pow,,,
#include <cmath>//abs,,,
#include <bitset> // bitset
#define endl "\n";
//It is so troublesome that I include bits/stdc++.h !
using namespace std;

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
const long long INF = 10010010010010;
const long long MOD = 1000000007;
typedef pair<int,int> P;

//Solve N^M. This, mod_pow use Iterative Square Method.
long long mod_pow(long long N, long long M) {
    if (M == 0) return 1;
    long long res = mod_pow((N * N) % MOD, M / 2);
    //最下位ビット(*N)が1の時は単独でNをかける
    if (M & 1) res = (res * N) % MOD;

    return res %= MOD;
}

long long gcd(long long a, long long b) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}
long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b ;
}

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

    char C;cin >> C;
    if(C-'A' >= 32) cout << "a" << endl;
    if(C-'A' < 32) cout << "A" << endl;

}


Measured memory_bytes: 3648
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <stdio.h>
#include <tuple>
#include <bitset>
#include <cfloat>
#include <fstream>
#include <limits.h>
#include <list>
#include <math.h>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <numeric>
#include <utility>
#include <sstream>

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

using namespace std;
#define int long long
#define ll long long
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define FORR(i,a,b)for(ll i=(a);i<=(b);i++)
#define repr(i,n) for(ll i=n;i>=0;i--)
#define P pair<ll, ll>
#define sz(x) (ll)x.size()
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
#define VE vector<ll>
#define COUT(x) cout<<(x)<<endl
#define MA map<ll,ll>
#define SE set<ll>
#define PQ priority_queue<ll>
#define PQR priority_queue<ll,VE,greater<ll>>
#define COUT(x) cout<<(x)<<endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define EPS (1e-10)
ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0) return a;
	return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}
bool prime(ll n) {
	for (ll i = 2; i <= sqrt(n); i++) {
		if (n%i == 0)return false;
	}
	return n != 1;
}


const long long MOD = 1000000007;
const long long INF = 1LL << 60;


const int MAX_N = 100010;

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n; cin >> n;
	int a, b, c, d; cin >> a >> b >> c >> d;
	string s; cin >> s;
	s = '#' + s + '#';
	bool ok = true;
	for (int i = a; i <= c - 1; i++) {
		if (s[i] == '#'&&s[i + 1] == '#') {
			ok = false;
		}
	}
	for (int i = b; i <= d - 1; i++) {
		if (s[i] == '#'&&s[i + 1] == '#') {
			ok = false;
		}
	}
	if (!ok) {
		cout << "No" << endl; return 0;
	}
	if (c > d) {
		ok = false;
		
		for (int i = b; i <= d; i++) {
			if (s[i - 1] == '.'&&s[i] == '.'&&s[i + 1] == '.')ok = true;
		}
		if (!ok) {
			cout << "No" << endl; return 0;
		}
	}
	cout << "Yes" << endl;
	return 0;
}

Measured memory_bytes: 720
// inputに入力データ全体が入る
function Main(input) {
	// 1行目がinput[0], 2行目がinput[1], …に入る
	input = input.split("\n");
	//tmp = input[1].split(" ");
	//文字列から10進数に変換するときはparseIntを使います
	var n = parseInt(input[0], 10);
	
	
	 var tmp = input[1].split(" ");
     var i = 0;
   var a = [];
for (var i = 0; i < n ; i++){
  var r= parseInt(tmp[i], 10);
    a[i] = r;}
  
 // console.log(n);
 // console.log(a);
  
  var h = a[0];
  var cnt = 1;
  for (i =0;i<n;i++){
             if (h<=a[i+1]){var h = a[i+1]; 
                               cnt =cnt + 1;} 
                    }
      console.log(cnt);              
  
  
	
	//出力
	
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 7372
fun main() {
    val (n, k) = readLine()!!.split(' ').map { it.toInt() }
    val logs = readLine()!!.split(' ').map { it.toInt() }
    var l = 1
    var r = logs.max()!!
    while (l < r) {
        val x = l + (r - l) / 2
        val s = logs.sumBy { (it + x - 1) / x - 1 }
        if (s <= k) {
            r = x
        } else {
            l = x + 1
        }
    }
    println(l)
}


Measured memory_bytes: 65000
# include <bits/stdc++.h>
# define rep(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
# define reps(i, n) for(int i=1, i##_len=(n); i<=i##_len; ++i)
# define rrep(i, n) for(int i=((int)(n)-1); i>=0; --i)
# define rreps(i, n) for(int i=((int)(n)); i>0; --i)
# define ALL(x) (x).begin(), (x).end()
# define SZ(x) ((int)(x).size())
# define pb push_back
# define optimize_cin() cin.tie(0); ios::sync_with_stdio(false)
using namespace std;
using lint = long long;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

int main()
{
    lint N; cin >> N;
    lint K; cin >> K;

    lint ans = K * pow(K - 1, N - 1);

    cout << ans << "\n";

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define Khela ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long int
#define llu long long unsigned int
#define pf printf
#define sf scanf
#define f first
#define s second
#define pb push_back
#define mk make_pair
#define pii pair<int ,int>
#define PII pair<ll ,ll>
 
int dx8[] = {0, 0, 1, 1, 1, -1, -1, -1};
int dy8[] = {1,-1, 1, -1, 0, 0, -1, 1};
int dx4[] = {0, 0, 1, -1};
int dy4[] = {1, -1, 0, 0};
 
typedef tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
int Set(int N,int pos){return N=N | (1<<pos);}
int reset(int N,int pos){return N= N & ~(1<<pos);}
bool check(int N,int pos){return (bool)(N & (1<<pos));}
const int Max=1e9+100;
const ll  MAX=1e18+500;
const int sz=1e3+100;
int mark[sz];
int main()
{
    Khela
    int a,b,c,i,j,k,q,p,x,y,ct,ct1,m,l,r,x1,y1,mn,h,sum1,in,z,mid,n,mx;
    char ch;
    double d;
    string str1,str2,str;
    bool bl,bl1;
    int t,cs=1;
    while(cin>>n>>m)
    {

    vector<pair<int,pii>> edge;
    int dist[n+1][n+1];
    for(i=0;i<=n;i++)  for(j=0;j<=n;j++)  {
        if(i==j) dist[i][j]=0;
        else dist[i][j]=Max;
    }
    for(i=1;i<=m;i++){
        cin>>p>>q>>x;
        edge.push_back({x,{p,q}});
        dist[p][q]=dist[q][p]=x;
    } 

    for(k=1;k<=n;k++){
        for(i=1;i<=n;i++){
            for(j=1;j<=n;j++){
                if(dist[i][k]+dist[k][j]<dist[i][j]) dist[i][j]=dist[i][k]+dist[k][j];
            }
        }
    }

    int ans=m;
    for(auto xx: edge){
        bl=true;
        for(i=1;i<=n;i++){
           if(dist[i][xx.s.f]+xx.f==dist[i][xx.s.s]) {
               bl=false;
               break;
           }
        }
        if(!bl) --ans;
    }

    cout<<ans<<endl;
      
        
    }





}

Measured memory_bytes: 384
#include <iostream>
#include <string>
#include<iomanip>
#include <algorithm>
#include <map>
#include <vector>
#include<queue>
#include<math.h>
#include<cmath>
#include<sstream>
#include<set>
#include <map>
#include<string.h>
#include<sstream>
#include<stack>
#include <iostream>
#define ll long long
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int N = 2e5 + 5, inf = 1e9 + 7;
const double ep = 0.0000000001;
const double pi = 3.14159265359;


int main() {
	int n;
	cin >> n;
	if (n % 2 == 0)
		cout << n / 2;

	else
		cout << (n / 2) + 1;
	return 0;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define endl '\n'

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;

const int INF = 1e9 + 7, N = 1e5 + 8, M = 400;

vector<pair<int, pi>> G[N];
int d[N], p[20][N], pc[N], pd[N], n, q, dis[N];
unordered_map<int, int> s[N], ct[N];
bool yes[N];

void dfs(int u = 1, int pa = 1, int dp = 0, int c = -1, int pdp = 0) {
	d[u] = dp;
	p[0][u] = pa;
	pc[u] = c;
	pd[u] = pdp;
	dis[u] = dis[pa] + pdp;
	for(auto &e:G[u])
		if(e.F != pa)
			dfs(e.F, u, dp + 1, e.S.F, e.S.S);
	if(dp % M == 0) {
		int t = u;
		while(p[0][t] != t && !yes[t]) {
			s[pc[t]][u] += pd[t];
			ct[pc[t]][u] ++;
			t = p[0][t];
		}
		if(yes[t])
			for(int i=1;i<=n-1;i++)
				s[i][u] += s[i][t], ct[i][u] += ct[i][t];
		yes[u] = true;
	}
}

int lca(int x, int y) {
	if(d[x] < d[y]) swap(x, y);
	for(int i=19;i>=0;--i)
		if(d[p[i][x]] >= d[y])
			x = p[i][x];
	if(x == y) return x;
	for(int i=19;i>=0;--i) {
		if(p[i][x] != p[i][y]) {
			x = p[i][x];
			y = p[i][y];
		}
	}
	return p[0][x];
}

pi qry(int u, int x) {
	pi ret = {0, 0};
	while(p[0][u] != u && !yes[u]) {
		ret.F += (pc[u] == x) * pd[u];
		ret.S += (pc[u] == x);
		u = p[0][u];
	}
	if(yes[u]) ret.F += s[x][u], ret.S += ct[x][u];
	return ret;
}

int qry(int u, int x, int y) {
	int ret = dis[u];
	pi pp = qry(u, x);
	ret -= pp.F;
	ret += pp.S * y;
	return ret;
}

int main()
{
	IO_OP;
	cin >> n >> q;
	for(int i=0;i<n-1;i++) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		G[a].PB({b, {c, d}});
		G[b].PB({a, {c, d}});
	}
	dfs();
	for(int i=1;i<20;++i) {
		for(int j=1;j<=n;++j)
			p[i][j] = p[i-1][p[i-1][j]];
	}
	while(q--) {
		int x, y, u, v;
		cin >> x >> y >> u >> v;
		cout << qry(u, x, y) + qry(v, x, y) - 2 * qry(lca(u, v), x, y) << endl;
	}
}



Measured memory_bytes: 316032
#pragma region RegionDefs
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0,i##_len=(n);i<i##_len;++i)
#define reps(i,l,r) for(int i=(l),i##_len=(r);i<i##_len;++i)
#define all(x) begin(x),end(x)
using namespace std;
const int INF = 1e9;
template<class T=int> using V = vector<T>;
template<class T=int> using PQ = priority_queue<T>;
template<class T=int> using PQG = priority_queue<T, V<T>, greater<T>>;
typedef long long ll;
const ll MOD = 1000000007LL;
void in() {}
template<class Head, class... Tail>
void in(Head&& head, Tail&&... tail)
{
    cin >> head;
    in(move(tail)...);
}
#define IN(...) ll __VA_ARGS__; in(__VA_ARGS__)
#define INS(T, ...) T __VA_ARGS__; in(__VA_ARGS__)
#define VIN(T, v, n) V<T> v(n); for(auto& _elem:v)cin>>_elem
template<class T>bool chmax(T &a, const T &b) {if (a<b) {a=b; return 1;} return 0;}
template<class T>bool chmin(T &a, const T &b) {if (a>b) {a=b; return 1;} return 0;}
#define y0 y__0
#define y1 y__1
#define j0 j__0
#define j1 j__1
#define YN(e) cout << ((e) ? "YES" : "NO") << endl
#define yn(e) cout << ((e) ? "Yes" : "No") << endl
#pragma endregion RegionDefs

struct Doubling
{
    ll m = 0;
    vector<vector<ll>> next;

    // vはデータ。fは次を得る関数。kは最大の次の回数
    Doubling(vector<ll>& v, function<ll(ll)> f, ll k)
    {
        ll t = max((ll)v.size(), k);
        while (t >>= 1) ++m;
        next = vector<vector<ll>>(m+1, vector<ll>(v.size()));
        rep(j, v.size()) next[0][j] = f(v[j]);
        rep(i, m)
            rep(j, v.size())
                if (next[i][j] == -1)
                    next[i+1][j] = -1;
                else
                    next[i+1][j] = next[i][next[i][j]];
    }

    // p番目のq回先を求める。
    ll getValue(ll p, ll q)
    {
        for (int i = m; i >= 0; --i) {
            if (p == -1) {
                break;
            }
            if ((q >> i) & 1) {
                p = next[i][p];
            }
        }
        return p;
    }
};

void solve()
{
    IN(n, k);
    vector<ll> v(n);
    rep(i, n) {
        cin >> v[i]; --v[i];
    }
    vector<ll> a(n);
    rep(i, n)
        a[i] = i;
    Doubling d(a, [&](ll x) {return v[x];}, k);
    cout << d.getValue(0, k) + 1 << endl;
}

int main()
{
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(numeric_limits<double>::max_digits10);

    solve();

    return 0;
}

Measured memory_bytes: 101636
#include <iostream>
#include <vector>
#include <queue>

#define INF (1<<30)

using namespace std;
using p = pair<int, int>;
using Graph = vector<vector<p>>;

int dijkstra(Graph& g, int& s)
{
    priority_queue<p, vector<p>, greater<p>> q;
    vector<int> dist(g.size(), INF);
    dist[s]=0;
    q.push(p(0, s));

    while (!q.empty())
    {
        p pi = q.top(); q.pop();
        int v = pi.second;
        if (dist[v]<pi.first) continue;

        int to, cost;
        for (size_t k=0; k<g[v].size(); ++k)
        {
            p i (g[v][k]);
            to = i.second;
            cost = i.first;
            if (dist[to] > dist[v] + cost)
                dist[to] = dist[v] + cost, q.push(p(dist[to], to));
        }
    }

    for (size_t i=0; i<dist.size(); ++i)
        if (dist[i] < INF)
            cout << dist[i] << endl;
        else
            cout << "INF" << endl;
}

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

    int V, E, r;
    cin >> V >> E >> r;

    Graph g(V);
    for (int i=0; i<E; i++)
    {
        int a, b, c;
        cin >> a >> b >>c;
        g[a].emplace_back(c, b); 
    }

    dijkstra(g, r);
}





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

#define INF 0x3f3f3f3f // Constante do infinito

using namespace std;
int main() {
	
    vector<int> dishes(5);

    for(int i = 0; i < 5; i++) {
        cin >> dishes[i];
    }

    int min_value = INF;
    int q = 0;
    do {
        int aswers = 0;
        for(int i = 0; i < dishes.size(); i++) {
            while(aswers % 10 != 0) aswers++;
            aswers += dishes[i];
        }

        min_value = min(min_value, aswers);
    } while (next_permutation(dishes.begin(), dishes.end()));

    cout << min_value << endl;
	return 0;
}


Measured memory_bytes: 256
from collections import defaultdict, deque
n, m, k = map(int, input().split())
friends = defaultdict(set)
block = defaultdict(set)
for _ in range(m):
    a, b = map(int, input().split())
    friends[a].add(b)
    friends[b].add(a)
for _ in range(k):
    c, d = map(int, input().split())
    block[c].add(d)
    block[d].add(c)
#print(friends)
#print(block)

roopname = []
roop = defaultdict(set)
seen = [0]*n


for i in range(n):
    if not seen[i]==0:
        continue
    seen[i] = i+1
    roopname.append(i+1)
    roop[i+1].add(i+1)
    queue = deque(friends[i+1])
    while queue:
        p = queue.popleft()
        if  not seen[p-1]==0:continue
        seen[p-1] = i+1
        roop[i+1].add(p)
        for j in friends[p]:
            if seen[j-1]==0:
                queue.append(j)
#print(roopname)
#print(roop)
#print(seen)
ans = [len(roop[seen[i]])-len(roop[seen[i]]&friends[i+1])-len(roop[seen[i]]&block[i+1])-1 for i in range(n)]

    

L=[str(a) for a in ans]
L=" ".join(L)
print(L)

Measured memory_bytes: 127996
use std::io::{stdin, Read, StdinLock};
use std::str::FromStr;

struct Scanner<'a> {
    cin : StdinLock<'a>,
}

impl<'a> Scanner<'a> {
    fn new(cin : StdinLock<'a>) -> Scanner<'a> {
        Scanner { cin: cin }
    }

    fn read1<T: FromStr>(&mut self) -> Option<T> {
        let token = self.cin.by_ref().bytes().map(|c| c.unwrap() as char)
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect::<String>();
        token.parse::<T>().ok()
    }

    fn read<T: FromStr>(&mut self) -> T {
        self.read1().unwrap()
    }
}

fn main(){
    let cin = stdin();
    let cin = cin.lock();
    let mut sc = Scanner::new(cin);
    loop {
        let n: usize = sc.read();
        if n == 0 { break; };
        let q: usize = sc.read();
        let mut g = vec![0; 101];
        for _ in 0..n {
            let m: usize = sc.read();
            for _ in 0..m {
                let v: usize = sc.read();
                g[v] += 1;
            }
        }
        let mut ans = 0;
        let mut cap = q - 1;
        for i in 0..101 {
            if g[i] > cap {
                ans = i;
                cap = g[i];
            }
        }
        println!("{}", ans);
    }
}



Measured memory_bytes: 5040
#include "iostream"
#include "algorithm"
#include "string"
#include "vector"
#include "cmath"
#define lp(n) for (int i = 0; i < n; i++)
#define lop(n,i) for (int i = 0; i < n; i++)
#define INT_MAX 2147483647
#define LLINT_MAX 9223372036854775807
#define mod 1000000007
#define ll long long int
using namespace std;

int n, m;
int cnt;
int a, b;
int g[8][8];
bool ck[8];
bool flag;

int f(int x) {
	ck[x] = true;
	flag = true;
	lp(n) {
		if (ck[i] == false) {
			flag = false;
			break;
		}
	}
	if (flag) {
		cnt++;
		return 0;
	}
	lp(n) {
		if (g[i][x]&&ck[i]==false) {
			f(i);
			ck[i] = false;
		}
	}
	return 0;
}

int main(){
	cin >> n >> m;
	cnt = 0;
	lp(8) {
		ck[i] = false;
		lop(8, j)
			g[i][j] = false;
	}
	lp(m) {
		cin >> a >> b;
		g[a - 1][b - 1] = true;
		g[b - 1][a - 1] = true;
	}
	f(0);
	cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 256
from collections import defaultdict as dd
dicLeft = dd(lambda: -1)
dicRight = dd(lambda: -1)
dicParent = dd(lambda: -1)

n = int(input())
for i in range(n):
  id, left, right = map(int, input().split())
  dicLeft[id] = left
  dicRight[id] = right
  dicParent[left] = id
  dicParent[right] = id

def depth(dicPar, id):
  if dicPar[id] == -1:
    return 0
  else:
    return depth(dicPar, dicPar[id]) + 1

def height(dicLeft, dicRight, id):
  left = dicLeft[id]
  right = dicRight[id]
  if left == -1 and right == -1:
    return 0
  elif left == -1:
    return height(dicLeft, dicRight, right) + 1
  elif right == -1:
    return height(dicLeft, dicRight, left) + 1
  else:
    return max(height(dicLeft, dicRight, left), height(dicLeft, dicRight, right)) + 1

def degree(dicLeft, dicRight, id):
  counter = 0
  if dicLeft[id] != -1:
    counter += 1
  if dicRight[id] != -1:
    counter += 1
  return counter

def sibling(dicParent, dicLeft, dicRight, id):
  parent = dicParent[id]
  if parent == -1:
    return -1
  else:
    if dicLeft[parent] == id:
      return dicRight[parent]
    elif dicRight[parent] == id:
      return dicLeft[parent]

def nodeType(dicPar, dicLeft, dicRight, id):
  if dicPar[id] == -1:
    return "root"
  elif dicLeft[id] == -1 and dicRight[id] == -1:
    return "leaf"
  else:
    return "internal node"

#print(depth(dicPar, 1))
for id in range(n):
  print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}".format(id, dicParent[id], sibling(dicParent, dicLeft, dicRight, id), degree(dicLeft, dicRight, id), depth(dicParent, id), height(dicLeft, dicRight, id), nodeType(dicParent, dicLeft, dicRight, id)))


Measured memory_bytes: 6008
import java.util.*;
 
public class Main {
 	public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
		String str1 = sc.next();
		String str2 = sc.next();

		if(str1.equals("H")){
			if(str2.equals("H")){
				System.out.println("H");
			}else{
				System.out.println("D");
			}
		}else{
			if(str2.equals("H")){
				System.out.println("D");
			}else{
				System.out.println("H");
			}
		}
	}
}


Measured memory_bytes: 19796
#include <algorithm>
#include <climits>
#include <cmath>
#include <iostream>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <vector>

const int mod = 1e9 + 7;
const int kmax = 510000;

long long fact[kmax], fact_inv[kmax], inv[kmax];

int gcd(int a, int b)
{
    if (!b) {
        return a;
    }

    return gcd(b, a % b);
}

void init_comb()
{
    fact[0] = fact[1] = 1;
    fact_inv[0] = fact_inv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < kmax; i++) {
        fact[i] = fact[i - 1] * i % mod;
        inv[i] = mod - inv[mod % i] * (mod / i) % mod;
        fact_inv[i] = fact_inv[i - 1] * inv[i] % mod;
    }
}

long long comb(int n, int r)
{
    if (n < r) {
        return 0;
    }

    if (n < 0 || r < 0) {
        return 0;
    }

    return fact[n] * (fact_inv[r] * fact_inv[n - r] % mod) % mod;
}

template <typename T, T N>
class UnionFind {
    T parent_[N];
    T rank_[N];
    T size_[N];

public:
    UnionFind();
    T Root(T idx);
    bool IsSame(T x, T y);
    void Unite(T x, T y);
    T GetSize(T idx);
};

template <typename T, T N>
UnionFind<T, N>::UnionFind()
{
    for (T i = 0; i < N; i++) {
        parent_[i] = i;
        rank_[i] = 0;
        size_[i] = 1;
    }
}

template <typename T, T N>
T UnionFind<T, N>::Root(T idx)
{
    return parent_[idx] == idx ? idx : parent_[idx] = Root(parent_[idx]);
}

template <typename T, T N>
bool UnionFind<T, N>::IsSame(T x, T y)
{
    return Root(x) == Root(y);
}

template <typename T, T N>
void UnionFind<T, N>::Unite(T x, T y)
{
    x = Root(x);
    y = Root(y);
    if (x == y) {
        return;
    }

    if (rank_[x] < rank_[y]) {
        parent_[x] = y;
        size_[y] += size_[x];
    } else {
        parent_[y] = x;
        size_[x] += size_[y];
        if (rank_[x] == rank_[y]) {
            rank_[x]++;
        }
    }
}

template <typename T, T N>
T UnionFind<T, N>::GetSize(T idx)
{
    return size_[Root(idx)];
}

int main()
{
    int n;
    std::cin >> n;

    std::vector<int> a(n - 1);
    for (int i = 0; i < n - 1; i++) {
        std::cin >> a[i];
    }

    std::vector<int> parent(n);
    for (auto idx : a) {
        parent[idx - 1]++;
    }

    for (auto val : parent) {
        std::cout << val << std::endl;
    }
}


Measured memory_bytes: 4844
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
	Scanner scan = new Scanner(System.in);

	int a = scan.nextInt();
	int b = scan.nextInt();

	int seki = a * b;

	if(seki % 2 == 0){
	    System.out.println("Even");
	}else{
	    System.out.println("Odd");
	}
    }
}


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

C = []
S = []
F = []
for i in range(N-1):
    c, s, f = list(map(int, input().split()))
    C.append(c)
    S.append(s)
    F.append(f)

for i in range(N):
    t = 0
    for j in range(i, N-1):
        if t < S[j]:
            t = S[j]
        elif t % F[j] == 0:
            pass
        else:
             t +=  F[j] - t % F[j]
        t += C[j]
    print(t)


Measured memory_bytes: 3188
N, P = map(int, input().split())
S = input()

ans = 0

if P in (2, 5):
    for i, s in enumerate(S):
        if int(s) % P == 0:
            ans += i + 1
else:
    count = [0] * P
    count[0] = 1
    u = 0
    for i, s in enumerate(reversed(S)):
        u = (int(s) * pow(10, i, P) + u) % P
        ans += count[u]
        count[u] += 1

print(ans)


Measured memory_bytes: 3500
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
int main(){
	int n,a,b;
	scanf("%d%d%d",&n,&a,&b);
	if((b-a)%2==0) printf("Alice\n");
	else printf("Borys\n");
}

Measured memory_bytes: 764
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define STRMAX 256

int main(void)
{
	char str[STRMAX];
	char out[STRMAX];
	int		num;
	int		num2;
	int		i,j,k;

	while (1) {
		memset(str, '\0', sizeof(str));
		scanf("%s", str);
		if (str[0] == '-') {
			break;
		}
		else {
			scanf("%d", &num);

			for (i=0; i<num; i++) {
				scanf("%d", &num2);
				j = num2;
				k = 0;
				memset(out, '\0', sizeof(out));
				while (str[j] != '\0') {
					out[k] = str[j];
					k++;
					j++;
				}
				for (j=0; j<num2; j++) {
					out[k] = str[j];
					k++;
				}
				out[k] = '\0';
				strcpy(str, out);
			}
			printf("%s\n", str);
		}
	}
	return 0;
}




Measured memory_bytes: 2760
# coding: utf-8
import sys


def main():
  n = int(input())
  a = int(input())
  
  if n % 500 != 0 and a == 0:
    print('No')
  
  elif (n - (n // 500) * 500) <= a:
    print('Yes')
    
  else:
    print('No')
  
  return 0


if __name__ == '__main__':
  main()

Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> l_l;
const ll INF=-10010010010000;
int main(){
    ll N,M;cin >> N >> M;
    vector<ll> A(M),B(M),C(M);
    for(int i=0; i<M; i++){
        cin >> A[i] >> B[i] >> C[i];
    }
    vector<ll> d(N+1,INF);
    d[1]=0;
    for(int i=0; i<=N-2; i++){
        for(int j=0; j<M; j++){
            if(d[A[j]]==INF) continue;
            else if(d[B[j]]<d[A[j]]+C[j]){
                d[B[j]]=d[A[j]]+C[j];
            }
        }
    }
    vector<bool> ng(N+1,false);
    for(int i=0; i<=N-1; i++){
        for(int j=0; j<M; j++){
            if(d[B[j]]<d[A[j]]+C[j]){
                d[B[j]]=d[A[j]]+C[j];
                ng[B[j]]=true;
                ng[A[j]]=true;
            }
        }
    }
    if(ng[N]) cout << "inf" << endl;
    else cout << d[N] << endl;
    return 0;
}

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

road = []
for _ in range(N):
  road.append(0)

for i in range(M):
   a = ab[i][0]
   b = ab[i][1]
   road[a - 1] += 1
   road[b - 1] += 1

for j in road:
  print(j)

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

using namespace std;
using namespace atcoder;

int main()
{
    int K;
    string s;

    cin>>K;
    for (int i = 0; i < K; i++)
    {
        s += "ACL";
    }
    cout<<s<<endl;

    return 0;
}

Measured memory_bytes: 3660
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

const int INF = 10101010;

int n,x[3];
int l[8];

int dfs(int d, vector<int> v){
    if(d==n){
        rep(i,3)if(v[i]==0) return INF;

        int res = 0;
        rep(i,3) res += abs(x[i]-v[i]);
        return res;
    }

    // not use
    int ret = dfs(d+1,v);

    // use
    rep(i,3){
        v[i] += l[d];
        ret = min(ret, dfs(d+1,v)+10);
        v[i] -= l[d];
    }

    return ret;
}

int main(){
    cin >>n;
    rep(i,3) cin >>x[i];
    rep(i,n) cin >>l[i];

    vector<int> v(3);
    cout << dfs(0,v)-30 << "\n";
    return 0;
}


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

using namespace std;

int n;
string s[50];
int c[50][26];

int main(){
    cin >> n;
    for(int i=0;i<n;i++) cin >> s[i];
    for(int i=0;i<n;i++){
        for(int j=0;j<26;j++){
            c[i][j] = 0;
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<s[i].size();j++){
            c[i][s[i][j]-'a']++;
        }
    }
    for(int i=0;i<26;i++){
        for(int j=1;j<n;j++){
            if(c[0][i] > c[j][i]){
                c[0][i] = c[j][i];
            }
        }
    }
    for(int i=0;i<26;i++){
        for(int j=0;j<c[0][i];j++){
            cout << (char)(i+'a');
        }
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
a = int(input())
b = int(input())
c = int(input())
x = int(input())

cnt = 0
for i in range(a+1):
  for j in range(b+1):
    for k in range(c+1):
      if i*500 + j*100 + k*50 ==x:
        cnt +=1
print(cnt)

Measured memory_bytes: 3060
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>

using namespace std;

int main()
{
	int n, a, b, c1=0, c2=0;
	long long int v,v1, vsum=0, vmax, ans=1;
	double ave;
	scanf("%d %d %d", &n, &a, &b);
	multiset<long long int> vs;
	for(int i=0; i<n; i++){
		scanf("%lld", &v);
		vs.insert(v);
	}
	auto itr=vs.end();
	for(int i=0; i<a; i++){
		itr--;
		v=*itr;
		if(i==0){
			vmax=v;
		}
		vsum=vsum+v;
	}
	ave=(double)vsum/(double)a;
	printf("%f\n", ave);
	if(v!=vmax){
		itr=vs.end();
		for(int i=0; i<n; i++){
			itr--;
			v1=*itr;
			if(v1>v){
				c1++;
			}
			if(v1==v){
				c2++;
			}
		}
		for(int j=1; j<=a-c1; j++){
			ans=ans*(c2+1-j)/j;
		}
		printf("%lld\n", ans);
	}else{
		itr=vs.end();
		for(int i=0; i<n; i++){
			itr--;
			v1=*itr;
			if(v1==vmax){
				c1++;
			}
		}
		ans=0;
		for(int i=a; i<=b && i<=c1; i++){
			long long int ans1=1;
			for(int j=1; j<=i; j++){
				ans1=ans1*(c1+1-j)/j;
			}
          
			ans=ans+ans1;
		}
		printf("%lld\n", ans);
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
const int N=5005;
int i,j,k,l,n,m,mo,f[2][N][N],g[N][N],nw,ans;
inline void add(int&x,const int&y){x+=y-mo;x+=x>>31&mo;}
int main(){
	scanf("%d%d",&n,&mo);
	if(n==2){printf("%d\n",3%mo);return 0;}
	m=n-1>>1;
	for(i=0;i*m<n-i;++i)f[0][i][i]=(n-1)&1?i+1:1;
	for(i=m;i>1;){
		--i;
		for(j=0;i*j<=n;++j)//for(k=j;i*j+k<n;++k)
			memset(f[!nw][j]+j,0,n-i*j<<2),
			memset(g[j]+j,0,n-i*j<<2);
//			f[!nw][j][k]=0,g[j][k]=0;
		++i;
		for(j=0;i*j<=n;++j)for(k=j;i*j+k<n;++k){
			f[!nw][j][k+j]=f[nw][j][k];
//			g[j][k+j]=1ll*f[nw][j][k]*(mo-j+1)%mo;
		}
		--i;
		for(k=0;k<=n;++k)for(j=1;j*i+k<=n;++j)
			add(f[!nw][j][k+j],f[!nw][j-1][k+j-1]);//,add(g[j][k+j],g[j-1][k+j-1]);
		for(j=1;i*j<=n;++j)for(k=j;i*j+k<n;++k)
			add(f[!nw][j][k],f[!nw][j-1][k-1]);
//			f[!nw][j][k]=(g[j][k]+1ll*f[!nw][j][k]*j)%mo;
		nw^=1;
	}
	for(j=0;j<=n;++j)for(k=j;k<=n;++k)if(k+1<=n-j){
		ans=(ans+1ll*((n-j-(k+1)+1)*(n-j+1)-(n-j-(k+1)+1)*(n-j+k+1)/2)*f[nw][j][k])%mo;
	//	for(int a=k+1;a<=n-j;++a)ans=(ans+1ll*(n-a-j+1)*f[nw][j][k])%mo;
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 246144
#include <iostream>
#include <string>
#include <cassert>
#include <cctype>
using namespace std;

string S;
size_t cur = 0;
int expression();
int digit();
int number();
int parse();
int term();
int factor();

int main(){
  int n;
  cin >> n;
  for (int i=0; i<n; i++){
    cin >> S;
    int a = parse();
    //  assert (a == 15);
    assert (cur == S.size()-1);
    cout << a << endl;
    cur = 0;
  }
}

int digit(){
  assert (isdigit(S[cur]));
  int n = S[cur] - '0';
  cur = cur+1;
  return n;
}

int number(){
  int n = digit();
  while(cur < S.size()-1 && isdigit(S[cur]))
    n = n*10 + digit();
  return n;
}

int expression(){
  int sum = term();
  while (S[cur] == '+' || S[cur] == '-'){
    char op = S[cur];
    cur += 1;
    int b = term();
    assert(op == '+' || op == '-');
    if (op == '+')  sum += b;
    else sum -= b;
  }
  return sum;
}

int term(){
  int a = factor();
  while ( cur < S.size()-1 && (S[cur] == '*' || S[cur] == '/') ){
    char op = S[cur++];
    int b = factor();
    if (op == '*') a *= b; else a /= b;
  }
  return a;
}

int factor(){
  if (S[cur] != '(') return number();
  cur += 1;
  int n = expression();
  assert(S[cur] == ')');
  cur += 1;
  return n;
}

int parse(){
  return expression();
}

Measured memory_bytes: 1208
#import string,itertools,fractions,heapq,re,array,bisect
#from math import *
#from collections import Counter
def rl(s): return xrange(len(s))

INF = 2147483647


import sys
stdin = sys.stdin

from copy import deepcopy
def makeTable(init, *dims):
    if 0 == len(dims): return deepcopy(init)
    return [makeTable(init, *dims[1:]) for i in xrange(dims[0])]


pascal = makeTable(None, 200, 200)

def choose(n, k):
    if k < 0 or k > n:
        return 0
    if 0 == k or n == k:
        return 1
    if None is not pascal[n][k]:
        return pascal[n][k]

    rr = choose(n-1, k-1) + choose(n-1, k)
    pascal[n][k] = rr

    return rr



N =        int( stdin.readline().strip() )


rr = []

basis = []
for i in range(2, 30):
    here = (1 << (i-1)) - 1
    basis.append((here, [1] * i))

    for second in range(1, i+1):
        here = (1 << (i + second - 1)) - 1
        extra = 0
        for length in range(1, second+1):
            extra += choose(second, length) * choose(i, length)
        for bs in range(1, 15):
            mult = 0
            for bl in range(1, bs+1):
                mult += choose(bs, bl)**2
            basis.append((here+extra*mult + (1 << (bs*2-1))-1, [1] * i + [2]*bs + [1] * second + [2]*bs))


basis.sort()
basis.reverse()
offset = 0
for h, pattern in basis:
    while h <= N:
        N -= h
        rr.extend([p+offset for p in pattern])
        offset += 2

print len(rr)
print ' '.join(map(str, rr))


Measured memory_bytes: 6524
#include <bits/stdc++.h>
#include <atcoder/fenwicktree>
using namespace std;
using namespace atcoder;
typedef long long ll;
const double pi=3.141592653589793;
typedef unsigned long long ull;
typedef long double ldouble;
const ll INF=1e18;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define rep2(i, s, n) for (ll i = (s); i < (ll)(n); 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; }

//　ローカルでの実行方法は g++ main.cpp -std=c++14 -I .

int main(){
    int n, q;
    cin >> n >> q;

    fenwick_tree<ll> fw(n);
    rep(i, n) {
        int a;
        cin >> a;
        fw.add(i, a);
    }

    rep(i, q) {
        int t, a, b;
        cin >> t >> a >> b;
        if(t == 0) {
            fw.add(a, b);
        }
        else {
            cout << fw.sum(a, b) << endl;
        }
    }
}


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

#define ll long long int
#define vll vector<ll>

int main() {

    int N;
    cin >> N;

    ll a, b;
    vll A, B;
    for (int i = 0; i < N; i++) {
        cin >> a >> b;
        A.push_back(a);
        B.push_back(b);
    }

    ll ans = 0;
    for (int i = N-1; i >= 0; i--) {
        A[i] += ans;
        if (A[i] % B[i] == 0) continue;
        ans += (B[i] * (A[i] / B[i] + 1) - A[i]);
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 2036
import java.util.*;
import java.io.*;

class Main{
  static int n;
  static int num[],nums[];
  static char mark[],marks[];
  static String s = "Stable";
  public static void main(String[] args){
      int i,j=1,k=0;
      try{
          InputStreamReader ir = new InputStreamReader(System.in);
           BufferedReader buffer = new BufferedReader (ir);
           String str1 = buffer.readLine();
           n = Integer.parseInt(str1);
           String str2 = buffer.readLine();
      num = new int[n];
      nums = new int[n];
      mark = new char[n];
      marks = new char[n];
      for(i=0;i<n;i++){
        mark[i] = str2.charAt(k);
        num[i] = Character.getNumericValue(str2.charAt(j));
        k+=3;
        j+=3;
      }
    }catch(IOException e){
        System.out.println("error1");
    }

    System.arraycopy(num,0,nums,0,n);
    System.arraycopy(mark,0,marks,0,n);

    BubbleSort();
    for(i=0;i<n;i++){
      if(i==n-1){
        System.out.println(mark[i]+""+num[i]);
        System.out.println(s);
        break;
      }
      System.out.print(mark[i]+""+num[i]+" ");
    }
   SelectionSort();
    if(Arrays.equals(mark,marks)!=true){
      s = "Not stable";
    }
    for(i=0;i<n;i++){
      if(i==n-1){
        System.out.println(marks[i]+""+nums[i]);
        System.out.println(s);
        break;
      }
      System.out.print(marks[i]+""+nums[i]+" ");
    }
  }

static void BubbleSort(){
  int i,j,temp;
  char temps;
  for(i=0;i<n;i++){
    for(j=n-1;j>i;j--){
      if(num[j]<num[j-1]){
        temp = num[j];
        num[j] = num[j-1];
        num[j-1] = temp;
        temps = mark[j];
        mark[j] = mark[j-1];
        mark[j-1] = temps;
      }
    }
  }
}

static void SelectionSort(){
  int i,j,temp,minj;
  char temps;
  for(i=0;i<n;i++){
    minj = i;
    for(j=i;j<n;j++){
      if(nums[j]<nums[minj]){
        minj = j;
      }
    }
    if(i!=minj){
        temp = nums[i];
        nums[i] = nums[minj];
        nums[minj] = temp;
        temps = marks[i];
        marks[i] = marks[minj];
        marks[minj] = temps;
      }
    }
  }


}



Measured memory_bytes: 24324
while true
    n, a, b = gets.chomp.split.map(&:to_i)
    break if [n, a, b] == [0, 0, 0]
    count, m, h = n / a, 1, {0=>true}
    while b * m <= n
        r = (b * m) % a
        break if h[r]
        h[r] = true
        count += (n % a >= r) ? n / a + 1 : n / a
        count -= b * m / a
        m += 1
    end
    puts n - count
end


Measured memory_bytes: 6888