akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;

#define ll long long int
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define inf  1e18
#define mk(arr,n,type) type *arr=new type[n];
#define ti(arr,n) for(ll i=0;i<n;++i)cin>>a[i];
#define ot(arr,n) for(ll i=0;i<n;++i)cout<<a[i]<<" ";
#define str(a) string a;cin>>a;
#define w(x) int x;cin>>x;while(x--)
ll mod_pow(ll n, ll i)
{
	if (i == 0)
		return 1;
	ll res = mod_pow(n, i / 2) % mod;
	if (i % 2 == 0)
		return (res * res) % mod;
	else
		return (((res * res) % mod) * n) % mod;
}
int main()
{
	ll n; cin >> n;
	ll add = 0;
	add = (mod_pow(10, n) + mod_pow(8, n)) % mod;
	ll sub = (mod_pow(9, n) * 2) % mod;
	ll ans = (mod + add - sub) % mod;
	cout << ans;

}

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

int main() {
  long n,cx=0,cy=0,hh=0;
  cin >> n;
  vector<long> x(n);
  vector<long> y(n);
  vector<long> h(n);
  for(long i=0;i<n;i++) cin >> x[i] >> y[i] >> h[i];
  for(long i1=0;i1<=100;i1++) {
    for(long i2=0;i2<=100;i2++) {
      long k=100000000000;
      bool ika=true;
      for(long i3=0;i3<n;i3++) {
        if(ika) {
          if(h[i3]==0) {
            k=min(k,labs(i1-x[i3])+labs(i2-y[i3]));
          } else {
            if(k<labs(i1-x[i3])+labs(i2-y[i3])+h[i3]) break;
            k=labs(i1-x[i3])+labs(i2-y[i3])+h[i3];
            ika=false;
          }
        } else {
          if(h[i3]==0) {
            if(k>labs(i1-x[i3])+labs(i2-y[i3])) break;
          } else {
            if(h[i3]!=k-labs(i1-x[i3])-labs(i2-y[i3])) break;
          }
        }
        if(i3+1==n&&k!=0) cx=i1,cy=i2,hh=k;
      }
    }
  }
  cout << cx << " " << cy << " " << hh << endl;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {

    public static void main(String args[]) {

        // 入力
        Scanner sc = new Scanner(System.in);
        String s = sc.next();

        // 主処理
        String[] array = s.split("");

        List<String> list = new ArrayList<>();
        list.add(array[0]);

        String word = "";
        for (int i = 1; i < array.length; i++) {
            word += array[i];
            if (!word.equals(list.get(list.size() - 1))) {
                list.add(word);
                word = "";
            }
        }

        int result = list.size();

        // 出力
        System.out.println(result);
        sc.close();
    }
}


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

int main(void){
    int N,ans=0;
    string S;
    cin>>N>>S;

    for(int i=1;i<N-1;i++){
        string r=S.substr(i);
        string l=S.substr(0,i);
        int cnt=0;
        int rcnt[26]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
        int lcnt[26]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
        for(int j=0;j<r.size();j++){
            rcnt[r[j]-'a']++;
        }
        for(int j=0;j<l.size();j++){
            lcnt[l[j]-'a']++;
        }
        for(int j=0;j<26;j++){
            if(rcnt[j]>0&&lcnt[j]>0)
                cnt++;
        }
        if(ans<cnt)
            ans=cnt;
    }
    cout<<ans<<endl;
    return 0;
}


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



int main()
{
    //ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,x,t;
    cin >> n >> x >> t;
    if(n <= x)
    {
        cout << t;
    }
    else
    {
        if(n%x == 0)
        {
            cout << (n/x) * t;
        }
        else
        {
            cout << ((n/x) + 1) * t;
        }
    }
}


Measured memory_bytes: 3160
s=input()
k=int(input())

words=[]
for i in range(len(s)):words.append(s[i:])
words.sort()

record=[]
for i in words:
    for j in range(len(i)):
        word="".join(i[:j+1])
        if word not in record:
            record.append(word)
    if len(record)>=k:
        print(record[k-1]);exit()

Measured memory_bytes: 25204
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
typedef long long ll;
typedef pair<int, int> P;
const int INF = 100100100;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;
int main() {
  ll N;
  cin >> N;
  vector<ll> L(N);
  REP(i, N) cin >> L.at(i);
  sort(L.begin(), L.end());
  ll ans = 0;
  for (ll mid = N - 1; mid >= 0; mid--) {
    for (ll low = mid - 1; low >= 0; low--) {
      auto itr = lower_bound(L.begin(), L.end(), L[mid] + L[low]);
      ll ng = distance(itr, L.end());
      ans += (N - 1 - mid) - ng;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 384
#include<stdio.h>

int main(void){
  int n;
  scanf("%d",&n);
  if(n==1){
    printf("Hello World\n");
  }else{
    int a,b;
    scanf("%d\n%d\n",&a,&b);
    printf("%d\n",a+b);
  }
  
  return 0;
}
  

Measured memory_bytes: 1700
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;
struct var
{
    int b,c;
    var(int x, int y)
    {
        b=x,c=y;
    }
};
struct cmp
{
    bool operator() (var a, var b)  {return a.c<b.c;}
};
priority_queue< var, vector<var>, cmp > q;
vector<int> v;
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
    {
        int a;
        scanf("%d",&a);
        v.push_back(a);
    }
    sort(v.begin(),v.end());
    for(int i=1;i<=m;++i)
    {
        int b, c;
        scanf("%d%d",&b,&c);
        q.push(var(b,c));
    }
    long long s=0ll;
    int b=q.top().b, c=q.top().c,i=0;
    q.pop();
    for(;i<(int)v.size();++i)
    {
        if((q.empty()&&b==0)||v[i]>c)  break;
        else if(b==0) b=q.top().b, c=q.top().c,q.pop();
        s=s+max(v[i],c);
        --b;
    }
    for(;i<(int)v.size();++i)  s+=v[i];
    printf("%lld",s);
    return 0;
}


Measured memory_bytes: 1784
#include<bits/stdc++.h>
#define ll long long
#define  vi vector<int>
#define pb push_back
//#define int long long
#define boost ios_base::sync_with_stdio(false);	cin.tie(0);	cout.tie(0)
#define pi pair<int,int>
#define F first
#define S second
using namespace std;

int mod=(int)(1e9+7);

void solve()
{
 ll n,k;
 cin>>n>>k;

 vector<ll>v(n+2);
 for(int i=2;i<=n+1;i++)
 v[i]=v[i-1]+i-1;
ll ans=0;
 for(ll i=k;k<=n+1;k++)
 {
    ll x=0;
    x=(v[n+1]-v[n+1-k])-(v[k])+1;
    ans=(ans+x)%mod;
 }
cout<<ans;

}

signed main()
{ boost;
 //cout<<fixed<<setprecision(14 );
 // int t;cin>>t;
  //for(int i=1;i<=t;i++)
  solve();
 // cout<<"Case #"<<i<<": "<<solve()<<endl;

return 0;
}

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

int main(){
    string s;
    cin >> s;
    int n = s.size();
    if (s[n - 1] == 's') cout << s << "es" << endl;
    else cout << s << "s" << endl; 
}

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

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 = 1LL << 60;

int main(){

    int N;
    cin >> N;
    int a[N], b[N], c[N];
    for (int i = 0; i < N; ++i){
        cin >> a[i] >> b[i] >> c[i];
    }

    long long dp[N][3];// all initialized to value 0
    dp[0][0] = a[0];
    dp[0][1] = b[0];
    dp[0][2] = c[0];

    for (int i = 1; i < N; ++i){
        dp[i][0] = max(dp[i-1][1]+a[i], dp[i-1][2]+a[i]);
        dp[i][1] = max(dp[i-1][0]+b[i], dp[i-1][2]+b[i]);
        dp[i][2] = max(dp[i-1][0]+c[i], dp[i-1][1]+c[i]);
    }

    cout << max(max(dp[N-1][0], dp[N-1][1]), dp[N-1][2]) << endl;

    return 0;
}

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

int main() {
  double W,H,x,y;
    cin >> W >> H >> x >> y;
  cout << W*H/2 << " ";
  if ( W/2 == x && H/2 == y )
    cout << 1 << endl;
  else
    cout << 0 << endl;
}

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

int main() {
	long long n,k;
	cin>>n>>k;
	long long a[n];
	long long dp[n];
	for(long long i=0;i<n;i++){
	        cin>>a[i];
	}dp[0]=0;
	for(long long i=1;i<n;i++){
	    dp[i]=INT_MAX;
	    for(long long j=1;j<=k;j++){
	        if(i-j<0)
	            break;
	        dp[i]=min(dp[i-j]+abs(a[i]-a[i-j]),dp[i]);
	    }
	}cout<<dp[n-1];
	
}


Measured memory_bytes: 1792
N, M = map(int, input().split())
a_list = set([int(input()) for i in range(M)])
dp = [0]*(N+1)

dp[0] = 1
for i in range(1,N+1):
  dp[i] = (dp[i-1] + dp[i-2])%(10**9+7)
  if i in a_list:
    dp[i] = 0
print(dp[N])

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define REP(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, a, b) for(int i=(a); i<(b); ++i)
#define FORR(i, a, b) for(int i=(b)-1; i>=(a); --i)

#define DEBUG(x) cout<<#x<<": "<<x<<'\n'
#define DEBUG_VEC(v) cout<<#v<<":";REP(i, v.size())cout<<' '<<v[i];cout<<'\n'
#define ALL(a) (a).begin(), (a).end()

#define CHMIN(a, b) a=min((a), (b))
#define CHMAX(a, b) a=max((a), (b))

const ll MOD=1000000007ll;
// const ll MOD=998244353ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

const double EPS=1e-11;
#define EQ0(x) (abs((x))<EPS)
#define EQ(a, b) (abs((a)-(b))<EPS)

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin>>n;
	int ans=1<<30;
	REP(i, n+1){
		int cnt=0;
		int tmp=i;
		while(tmp>0){
			cnt+=tmp%6;
			tmp/=6;
		}
		tmp=n-i;
		while(tmp>0){
			cnt+=tmp%9;
			tmp/=9;
		}
		ans=min(ans, cnt);
	}
	cout<<ans<<'\n';
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<int> A(N+1), B(N);
    for (auto& a:A) {
        cin >> a;
    }
    for (auto& b:B) {
        cin >> b;
    }
    long long before = accumulate(A.begin(), A.end(), 0LL);
    int smaller;
    for (int i = 0; i<N; i++) {
        smaller = min(A[i], B[i]);
        A[i] -= smaller;
        B[i] -= smaller;
        smaller = min(A[i+1], B[i]);
        A[i+1] -= smaller;
        B[i] -= smaller;
    }
    printf("%lld\n", before-accumulate(A.begin(), A.end(), 0LL));
    return 0;
}

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

using ll = long long;
using pii = pair<int, int>; using pll = pair<ll, ll>;

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

template<class T> istream& operator >> (istream& s, vector<T>& v)
{ for (T& x: v) { s >> x; } return s;}
template<class F, class S> istream& operator >> (istream& s, pair<F, S>& p)
{ s >> p.first >> p.second; return s;}

template<class INT_T> vector<INT_T> divisors(INT_T n)
{
    vector<INT_T> divs;
    for (INT_T d=1; d*d <= n; d++) {
        if (n%d==0) {
            divs.push_back(d);
            INT_T q = n/d;
            if (q != d) divs.push_back(q);
        }
    }
    //sort(divs.begin(), divs.end());
    return divs;
}

#define D1(a) cerr<<#a<<":"<<a<<endl
#define D2(a,b) cerr<<#a<<":"<<a<<","<<#b<<":"<<b<<endl
#define D3(a,b,c) cerr<<#a<<":"<<a<<","<<#b<<":"<<b<<","<<#c<<":"<<c <<endl
#define D4(a,b,c,d) cerr<<#a<<":"<<a<<","<<#b<<":"<<b<<","<<#c<<":"<<c<<","<<#d<<":"<<d<<endl
#define DH(c) do{rep(__i, c.size())cerr<<c[__i]<<(__i==c.size()-1?'\n':' ');}while(0)

int main()
{
    cin.tie(nullptr); ios::sync_with_stdio(false);
    
    int N; cin >> N;
    map<int, int> m;
    rep(i, N) {
        int a; cin >> a;
        m[a]++;
    }
    // for (const auto& p : m) {
    //     D2(p.first, p.second);
    // }
    // if (m.size() == 1) {
    //     cout << 0 << endl;
    //     return 0;
    // }

    int ans = 0;
    set<int> s;
    for (const auto& p : m) {
        const int& a = p.first;
        const int& cnt = p.second;
        if (cnt == 1) {
            vector<int> divs = divisors(a);
            bool not_divisible = true;
            for (const int& d : divs) {
                if (s.count(d) != 0) {
                    not_divisible = false;
                    break;
                }
            }
            if (not_divisible) {
                D1(a);
                ans++;
            }
        }
        s.insert(a);
    }

    cout << ans << endl;
}


Measured memory_bytes: 22336
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define LLINF 9223372036854775807
#define MOD ll(1e9+7)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cerr<<#x<<": "<<x<<endl



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

    vector<vector<ll>> graph(n);
    for(int i = 0; i < n-1; i++){
        int a;
        cin >> a;
        a--;
        graph[a].push_back(i+1);
    }

    for(int i = 0; i < n; i++){
        cout << graph[i].size() << endl;
    }
    return 0;

}


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

int main(void){
  string x;
  getline(cin,x);
  int i = x.length();
  for(int n = 0; n < i; n++){
	if(isupper(x[n])){
	  x[n] += 32;
	}else if(islower(x[n])){
	  x[n] -= 32;
	}
  }
  
  cout << x << endl;

  return 0;
}
	  



Measured memory_bytes: 3140
#include <iostream>
using namespace std;
typedef long long ll;
ll n,m,a,b,s[100002],ans;
int main(void){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        cin>>a>>b;
        s[a]++;
        s[b+1]--;
    }
    for(int i=0;i<n;i++){
        s[i+1]+=s[i];
    }
    for(int i=1;i<=n;i++){
        if(s[i]==m)ans++;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
int main() {
    int N, M;
    cin >> N >> M;
    vector<int>c(N, -1);
    int s, t;
    int ans = 0;
    bool b = true;
    for (int i = 0; i < M; i++) {
        cin >> s;
        if (c[s - 1] == -1){
            cin >> c[s - 1];
        }else{
            cin >> t;
            if (c[s - 1] != t) {
                b = false;
                ans = -1;
                break;
            }
        }
    }
    if (c[0] == -1) {
        if (N > 1) {
            c[0] = 1;
        }else {
            c[0] = 0;
        }
        
    }else if (c[0] == 0 && N > 1){
        b = false;
        ans = -1;
    }
    for (int i = 1; i < N; i++) {
        if (c[i] == -1) {
            c[i] = 0;
        }
    }
    if (b) {
        int d = 1;
        for (int i = N - 1; i >= 0; i--) {
            ans += c[i]*d;
            d *= 10;
        }
        
    }
    //cout << c[0] << ',' << c[1] << ',' << c[2] << endl;
    cout << ans << endl;

}


Measured memory_bytes: 3620
use std::io;


fn main() {
    let (a, b) = {
        let i = read::<isize>();
        (i[0], i[1])
    };

    if a + b < 10 { println!("{}", a + b); }
    else { println!("error"); }
}


#[allow(dead_code)]
fn read<T>() -> Vec<T>
where T:
    std::str::FromStr,
    T::Err: std::fmt::Debug {

    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.split_whitespace()
        .map(|s| s.trim().parse().unwrap())
        .collect()
}

#[allow(dead_code)]
fn read_one<T>() -> T
where T:
    std::str::FromStr,
    T::Err: std::fmt::Debug {

    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.trim().parse().unwrap()
}

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

using namespace std;

int main() {
	int N, K, Q;
	cin >> N >> K >> Q;
	
	vector<int> answers(Q);
	for (int i = 0; i < Q; i++) {
		cin >> answers[i];
	}

	vector<int> answer_correct_number(N);	//回答者OK数
	for (int quesition_number = 0; quesition_number < Q; quesition_number++) {
		answer_correct_number[answers[quesition_number] - 1]++;
	}

	for (int answer_number = 0; answer_number < N; answer_number++) {
		if ( 1 <= K - Q + answer_correct_number[answer_number]) {
			cout << "Yes" << endl;
		} else {
			cout << "No" << endl;
		}
	}

	return 0;
}


Measured memory_bytes: 1408
import java.util.Scanner;

public class Main {
	  
	public static void main(String args[]) {
		    Scanner scanner = new Scanner(System.in);
		    
		    int N = scanner.nextInt();
		    String[] s = new String[N];
		    for(int i = 0; i < N; i++) 
		    {
		    	s[i] = scanner.next();
		    }
		    int M = scanner.nextInt();
		    String[] t = new String[M];
		    for(int i = 0; i < M; i++) 
		    {
		    	t[i] = scanner.next();
		    }
		    int[] count = new int[N];
		    
		    for( int i = 0; i < N; i++ ) 
		    {
		    	for( int j = 0; j < N; j++ ) 
		    	{
		    		if( s[i].equals(s[j]) ) 
		    		{
		    			count[i]++;
		    		}
		    	}
		    	for(int k = 0; k < M; k++) 
		    	{
		    		if( s[i].equals(t[k]) ) 
		    		{
		    			count[i]--;
		    		}
		    	}
		    }
		    int max = count[0];
		    for( int i = 0; i < N; i++ ) 
		    {
		    	if( max < count[i] ) 
		    	{
		    		max = count[i];
		    	}
		    }
		    if( max < 0 ) 
		    {
		    	System.out.println(0);
		    }
		    else 
		    {
		    	System.out.println(max);
		    }
		    scanner.close(); }
		  }

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

int charToInt(char c){
    char zero_num = '0';
    return (int)c - (int)zero_num;
}

int main(){
    int N; cin>>N;
    vec_ll A(N+1);
    vec_ll cumul_A(N+1);
    ll tot_A =0;
    rep(i,N+1){
     cin>>A.at(i);
     tot_A += A.at(i);
     cumul_A.at(i) = tot_A;
    }

    vec_ll avairable_edges(N+1); //たぶんここまでたくさんのノードのことは考えないでよいはず
    vec_ll avairable_nodes(N+1); //たぶんここまでたくさんのノードのことは考えないでよいはず

    if(A.at(0)==1 && N==0){
        cout<<1<<endl;
        return 0;
    }

    if(A.at(0)!=0){
        cout<<-1<<endl;
        return 0;
    }

    ll the_depth = 0;
    avairable_edges.at(0) = 2;
    avairable_nodes.at(0) = 1;

    ll total_nodes = 1; //1は深さ0の文
    for(int i=1;i<N+1;i++){
        /*
        cout<<"i:"<<i<<endl;
        cout<<"A[i]"<<A.at(i)<<endl;
        cout<<"the depth:"<<the_depth<<endl;
        cout<<"avairable_nodes:"<<avairable_nodes.at(the_depth)<<endl;
        */


        ll temp_val = A.at(i);
        ll temp2 = 0;
        while(true){
            //the_nodeのedgeの数をA(i)本減らす
            //the_nodeのedgeの数が足りなければ次の層に移す
            if(temp_val<=avairable_edges.at(the_depth)){
                avairable_edges.at(the_depth) -= temp_val;
                //the_depthからi層までノードが伸びてくるので、i-the_depth個ノードが加算される
                total_nodes += (i-the_depth)*temp_val;
                break;
            }else{
                //cout<<"go to next node"<<the_depth<<endl;
                //次の層に行く
                temp_val -=avairable_edges.at(the_depth);
                temp2 += avairable_edges.at(the_depth);
                //ノードの数を足す
                total_nodes += (i-the_depth)*avairable_edges.at(the_depth);
                avairable_edges.at(the_depth) = 0;
                //次の層で使えるエッジの数を数える
                the_depth++;
                if(the_depth>i-1){
                    //条件を満たせない
                    cout<<-1<<endl;
                    return 0;
                }
                //この時点ですでにこの階層でcumul_A(i) - cumul_A(the_depth)
                //だけedgeを使っている。
                //そもそも、子供を作れるノードの最大数は
                avairable_nodes.at(the_depth) = avairable_nodes.at(the_depth-1)*2 - A.at(the_depth);
                if(avairable_nodes.at(the_depth)<=0){
                    cout<<-1<<endl;
                    return 0;
                }
                //である。
                avairable_edges.at(the_depth) = avairable_nodes.at(the_depth)*2 - (cumul_A.at(i-1) - cumul_A.at(the_depth))-temp2;
                if(avairable_edges.at(the_depth)<=0){
                    cout<<-1<<endl;
                    return 0;
                }
 
            }
        }
    }
    cout<<total_nodes<<endl;

    return 0;
}

Measured memory_bytes: 6400
#include<bits/stdc++.h>
using namespace std;
template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }
typedef long long ll;
typedef vector<int> vint;
typedef pair<int, int> pint;
typedef vector<long long> vlong;
#define vpush(a,x) a.push_back(x);
#define rep(i, n) REP(i, 0, n)
#define all(v) v.begin(), v.end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define INF 2e9
signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    list<int> L;
    int a;
    string s;
    rep(i,n){
        cin>>s;
        if(s=="insert"){
            cin>>a;
            L.push_front(a);
        }
        if(s=="delete"){
            cin>>a;
            for(auto it=L.begin();it!=L.end();it++){
                if(*it==a){
                    L.erase(it);
                    break;
                }
            }
        }
        if(s=="deleteFirst"){
            L.pop_front();
        }
        if(s=="deleteLast"){
            L.pop_back();
        }
    }
    int i=0;
    for(auto it=L.begin();it!=L.end();it++){
        if(i++) cout<<' ';
        cout<<*it;
    }
    cout<<'\n';
    return(0);
}


Measured memory_bytes: 34436
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
#define INF 1145141919810893364
typedef pair<int,int> PP;
typedef long long ll;
#define int ll
#define setdouble setprecision
#define REP(i,n) for(int i=0;i<(n);++i)
#define RREP(i,n) for(int i=(n)-1;i>=0;--i)
#define GOODBYE cout << -1 << endl;return 0
#define Endl endl

int K;
    
    
struct edge{int end;int cost;};
typedef pair<int,int> P;
int V,d[114514];
vector<edge> G[114514];

void dijkstra(int s){
    priority_queue<P,vector<P>,greater<P>> que;
    for(int i=0;i<114514;i++){d[i]=INF;}
    d[s]=0;
    que.push(P(0,s));
    while(!que.empty()){
        P p = que.top();
        que.pop();
        int v = p.second;
        if(d[v]<p.first)continue;
        for(int i=0;i<G[v].size();i++){
            edge e = G[v][i];
            if(d[e.end]>d[v]+e.cost){
                d[e.end] = d[v]+e.cost;
                que.push(P(d[e.end],e.end));
            }
        }
    }
}


signed main(void){
    cin >> K;
    V=K;
    edge h;
    REP(i,K){
        h.end=(i+1)%K;
        h.cost=1;
        G[i].push_back(h);
        
        h.end=(i*10)%K;
        h.cost=0;
        if(h.end!=i){
            G[i].push_back(h);
        }
    }
    dijkstra(1);
    cout << d[0]+1 << endl;
    
    return 0;
}



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

using namespace std;

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

int main(){
  int n;
  cin >> n;
  cout << ((n % 10 == 7 || n / 10 % 10 == 7 || n / 100 == 7) ? "Yes" : "No") << endl;
  return 0;
}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < n; i++)
typedef long long ll;
int n, q, a, b, c, d, kk = 1;
vector<vector<tuple<int,int,int>>> G, cl;
vector<int> in, head, par, dis;
int dfs1(int p, int u){
	int ret = 1, tmax = 0, temp;
	par[u] = p;
	for(auto &nx: G[u])if(get<0>(nx) != p){
		dis[get<0>(nx)] = dis[u] + get<2>(nx);
		ret += temp = dfs1(u,get<0>(nx));
		if(temp > tmax){
			swap(G[u][0], nx);
			tmax = temp;
		}
	}
	return ret;
}
void dfs2(int p, int u){
	in[u] = kk++;
	head[u] = p != -1 && get<0>(G[p][0]) == u ? head[p] : u;
	for(auto &nx: G[u])if(get<0>(nx) != p){
		cl[get<1>(nx)].push_back(make_tuple(kk,1,get<2>(nx)));
		dfs2(u,get<0>(nx));
		cl[get<1>(nx)].push_back(make_tuple(kk-1,-1,-get<2>(nx)));
	}
	kk++;
}
void color(){
	for(auto &it: cl){
		for(int i = 1; i < it.size(); i++){
			get<1>(it[i]) += get<1>(it[i-1]);
			get<2>(it[i]) += get<2>(it[i-1]);
		}
	}
}
int lca(int a, int b){
	while(head[a] != head[b]){
		if(in[a] < in[b]) swap(a,b);
		a = par[head[a]];
	}
	return in[a] < in[b] ? a : b;
}
int query(int a, int b, int c, int d){
	int e = lca(c,d), ret = dis[c] + dis[d] - dis[e]*2;
	int u[3] = {c,d,e};
	rep(i,3){
		int cc, dd;
		tie(ignore, cc, dd) = *--lower_bound(cl[a].begin(), cl[a].end(), make_tuple(in[u[i]]+1,0,0));
		ret += (cc*b - dd) * (i == 2 ? -2 : 1);
	}
	return ret;
}
int main(){
	scanf("%d%d", &n, &q);
	G.resize(n); cl.assign(n,{make_tuple(0,0,0)}); in.resize(n); head.resize(n); par.resize(n); dis.resize(n);
	rep(i,n-1){
		scanf("%d%d%d%d", &a, &b, &c, &d);
		a--;b--;c--;
		G[a].push_back(make_tuple(b,c,d));
		G[b].push_back(make_tuple(a,c,d));
	}
	dis[0] = 0; dfs1(-1,0); dfs2(-1,0);
	color();
	rep(i,q){
		scanf("%d%d%d%d", &a, &b, &c, &d);
		a--;c--;d--;
		printf("%d\n", query(a,b,c,d));
	}
}

Measured memory_bytes: 22532
require 'set'

class Hash
  def push(key, value)
    self[key] = [] if self[key] == nil
    self[key].push(value)
  end
end

class Array
  def lower_bound(value)
    left = -1;
    right = self.length;
    while left + 1 < right
      mid = left + (right - left) / 2;
      if self[mid] >= value
        right = mid
      else
        left = mid
      end
    end
    right
  end

  def unique
    res = [self.first]
    each_cons(2) do |a, b|
      if a != b
        res.push(b)
      end
    end
    res
  end
end

def get_ints
  gets.split.map(&:to_i)
end

def get_ints_minus_one
  get_ints.map { |x| x - 1 }
end

def get_int
  gets.chomp.to_i
end

A, B, N = get_ints

if N >= B
  puts (((B - 1.0)/B) * A).to_i
else
  puts ((1.0 * N)/B * A).to_i
end



Measured memory_bytes: 14476
h, w, m = map(int, input().split())

# 行、列ごとの爆破数
H = [0] * h
W = [0] * w

L = [(0, 0)] * m

for i in range(m):
    a, b = map(int, input().split())
    L[i] = (a, b)
    H[a-1] += 1
    W[b-1] += 1
h_max = max(H)
w_max = max(W)
ans = h_max + w_max

cnt = 0
for l in L:
    # 爆破対象のマスに爆弾を設置しているかの判定
    if H[l[0]-1] == h_max and W[l[1]-1] == w_max:
        cnt += 1
if H.count(h_max) * W.count(w_max) == cnt:
    ans -= 1
print(ans)

Measured memory_bytes: 54052
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using p = pair<int, int>;
using P = pair<ll, ll>;
using V = vector<int>;
using VV = vector<vector<int>>;
using VVV = vector<vector<vector<int>>>;
using VL = vector<ll>;
using VVL = vector<vector<ll>>;
using VVVL = vector<vector<vector<ll>>>;
using Graph = VV;
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(a) (a).begin(),(a).end()
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; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
int Inf = (1 << 30);
ll inf = (1LL << 60);
const int MOD = 1e9 + 7;
int main() {
	ll a, b, c;
	cin >> a >> b >> c;
	if (!(a % 2) || !(b % 2) || !(c % 2)) {
		cout << 0 << endl;
	}
	else {
		ll mini = inf;
		chmin(mini, a * b);
		chmin(mini, b * c);
		chmin(mini, a * c);
		cout << mini << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REP2(i, a, b) for(int i = a;i <= b;i++)
#define REPR(i, a, b) for(int i = a; i >= b; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define MOD 1000000007
#define PI 3.14159265358979323846
#define vi vector<int>
#define vll vector<ll>
#define vi2 vector<vector<int>>
#define eb emplace_back
#define fi first
#define se second
#define ALL(v) v.begin(), v.end()
#define sz(x) int(x.size())
using namespace std;
using P = pair<ll,ll>;
const int dx[]{0, 1, 0, -1, -1, -1, 1, 1}, dy[]{1, 0, -1, 0, -1, 1, -1, 1};
#define INT(name) int name;cin >> name;
#define VEC(type,name,n) vector<type> name(n);REP(i,n) cin >> name[i];

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

int main()
{
  INT(N);
  vector<string> A(N);
  REP(i, N) cin >> A[i];
  
  
  int flag = 0;
  int MAX=1;
  REP(i,N){
    queue<int> que;
    que.push(i);
    vector<int> dist(N,-1);
    dist[i]=1;
    while(!que.empty()){
      int v = que.front();
      que.pop();
      REP(j,N){
        if(A[v][j]=='0') continue;
        if(dist[j]==dist[v]&&dist[j]!=-1){
          flag=1;
        }
        if(dist[j]!=-1) continue;
        que.push(j);
        dist[j]=dist[v]+1;
        MAX=max(MAX,dist[j]);
      }
    }
  }

  if(flag==0){
    cout << MAX << endl;
  }else{
    cout << -1 << endl;
  }
}

Measured memory_bytes: 3664
//Author : Prakhar Asaiya
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(int i=a;i<b;++i)
#define REPN(i,a,b) for(int i=a;i<=b;++i)
#define REPV(i,a,b) for(int i = a; i>= b; --i)
#define db1(x) cout<<#x<<"="<<x<<'\n'
#define db2(x,y) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<'\n'
#define db3(x,y,z) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<","<<#z<<"="<<z<<'\n'
#define ll long long
#define INF 100000
#define ff first
#define ss second
const int M=1e9+7;
const int N = 500005;
struct query{
	int l, r, i;
};
const int BLK = 800;
query Q[N];
int A[N], ans[N], freq[N];
int cnt = 0;

bool cmp(query a, query b)
{
	if(a.l/BLK != b.l/BLK)
	return a.l/BLK < b.l/BLK;
	
	return a.r < b.r;
}

void add(int pos)
{
	++freq[A[pos]];
	if(freq[A[pos]] == 1)
	++cnt;
}

void remove(int pos)
{
	--freq[A[pos]];
	if(freq[A[pos]] == 0)
	--cnt;
}

void solve()
{
	int n, q;
	cin>>n>>q;
	REP(i,0,n)
	cin>>A[i];
	REP(i,0,q)
	{
		cin>>Q[i].l>>Q[i].r;
		--Q[i].l, --Q[i].r;
		Q[i].i = i;
	}
	sort(Q, Q + q, cmp);
	int ml = 0, mr = -1;
	REP(i,0,q)
	{
		int l = Q[i].l;
		int r = Q[i].r;
		
		while(ml > l)
		{
			--ml;
			add(ml);
		}
		
		while(mr < r)
		{
			++mr;
			add(mr);
		}
		
		while(ml < l)
		{
			remove(ml);
			++ml;
		}
		
		while(mr > r)
		{
			remove(mr);
			--mr;
		}
		
		ans[Q[i].i] = cnt;
	}
	REP(i,0,q)
	{
		cout<<ans[i]<<"\n";
	}
}


int main()
{/*
#ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
#*/
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  
  	solve();
  
  return 0;
}


Measured memory_bytes: 15412
<?php
$ary = [];
for ($i=0; $i <= 100; $i++) { 
    $ary[] = 0;
}

// while ($a = intval(fgets(STDIN))) { 
//     $ary[$a]++;
// }

while (!feof(STDIN)) { 
    $a = intval(fgets(STDIN));
    $ary[$a]++;
}

$max = max($ary);

for ($i=1; $i <= 100; $i++) { 
    if ($ary[$i] == $max){
        print $i;
        print PHP_EOL;
    }
}


Measured memory_bytes: 9280
i = 1
n = gets.to_i
while i <= n
  x = i
  if x % 3 == 0
    print " #{i}"
  else
    while x > 0
      if x % 10 == 3
        print " #{i}"
        break
      else
        x /= 10
      end
    end
  end
  i += 1
end
puts ''


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

using namespace std;

int As, Ae;
int Bs, Be;

int main()
{
	cin >> As >> Ae >> Bs >> Be;

	int result = 0;

	result = min(Ae, Be) - max(As, Bs);
	if (result < 0) result = 0;

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

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

using namespace std;
 
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL)
#define ll long long
#define pii pair<int, int>
#define PB push_back
#define MP make_pair
#define MT make_tuple
#define tiii tuple<ll, ll, ll>
#define INF 1e18
#define MOD 1000000007


int main(){
	fast;

	string S, T;
	cin >> S >> T;
	vector<int> v(26, 0);
	int ans = 0;
	for (int i = 0; i < T.length(); i++) {
		if (S[i] != T[i]) {
			ans++;
		}
	}
	cout << ans << "\n";

	return 0;
}

Measured memory_bytes: 3884
#include <bits/stdc++.h>
using namespace std;
int main(){
    int i, n, sum=0, cnt=0;
    vector <int> a;
    cin >>n;
    for(i=1;i<=n;i++){
        sum=sum+i;
        a.push_back(i);
        cnt++;
        if(sum>=n) break;
    }
    for(auto ans : a){
        if(sum-n!=ans) cout << ans <<endl;
    }
    return 0;
}

Measured memory_bytes: 384
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<cmath>
using namespace std;
typedef long long ll;
ll mod = 1e9+7;
#define rep(i,n) for(int i = 0; i < (n); ++i)
ll gcd ( ll a, ll b ) {
    if ( a % b == 0 ) return b;
    return gcd( b, a % b );
}
ll lcd ( ll a, ll b ) {
    return a / gcd(a, b) * b;
}
int main() {
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    ll lcd_num = lcd(c, d);
    ll anum = ( a - 1 ) - ( a - 1 ) / c - ( a - 1 ) / d + ( a - 1 ) / lcd_num;
    ll bnum = b - ( b / c ) - ( b / d ) + ( b / lcd_num );
    if ( a == 1 ) {
        cout << bnum << endl;
    }
    else {
        cout << bnum - anum << endl;
    }
    return 0;
}


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

#define rep(i,n) for(long long int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(long long int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(long long int i=(a);i>(b);i--)

long long int n,cnt=0,ans=0,a,b,c,cmp[100000];

string s,w;

int main(void){
      cin >> a >> b;
      if(2*a>=b){
          cout << b/2 << endl;
          return 0;
      }
      else{
          cnt+=a;
           b-=a*2;
          cnt+=b/4;
      }
      cout << cnt << endl;
return 0;
}


Measured memory_bytes: 256
import copy
n, m = [int(i) for i in input().split() ]
x = list([])
k = list([])
for i in range(n):
    a = [int(i) for i in input().split() ]
    k.append(a.pop(0))
    x.append(a)

p = copy.deepcopy(x[0])
for i in range(n-1):
    p.extend(x[i+1])
    p = [z  for z in set(p) if p.count(z) > 1]
print(len(p))

Measured memory_bytes: 3444
#include<bits/stdc++.h>
#include<numeric>
#include<cassert>
//#include <boost/multiprecision/cpp_int.hpp>
#define ll long long int
#define CON 100010
const long long mod=1e9+7;
const int INF=1001001001;
const int inf=100000;
//const ll inf=1e9+7;
//const ll ful=1e18;
using namespace std;
//namespace mp = boost::multiprecision;
int main() 
{
	int a;
	cin>>a;
	int ans=a;
	while(ans>0)
	{
		ans-=1000;
	}
	ans=abs(ans);
	cout<<ans<<endl;
	return 0;
}



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

using lint = long long int;

struct Edge {
	int to;
	lint a, b;
};

struct State {
	int v;
	lint dst;
	bool operator > (const State& obj) const { return dst > obj.dst; }
};

int N, M, S, G;
vector< vector< Edge > > edge;

lint dst[200005];

lint eval(lint x, lint t, lint a, lint b) {
	return (lint)ceil((double)b / (a + t + x)) + t + x;
}

lint getBestDst(lint t, lint a, lint b) {
	lint lb = 0, ub = 1e16;
	for (int i=0; i<200; ++i) {
		lint lft = (2 * lb + ub) / 3;
		lint rgt = (lb + 2 * ub) / 3;
		if (eval(lft, t, a, b) > eval(rgt, t, a, b)) lb = lft;
		else ub = rgt;
	}
	lint ret = eval(0, t, a, b);
	for (lint s=max(0LL,lb-10); s<=ub+10; ++s) ret = min(ret, eval(s, t, a, b));
	//cerr << "gbd: " << lb << " " << ub << " " << ret << endl;
	return ret;
}

void solve() {
	memset(dst, -1, sizeof(dst));
	
	priority_queue< State, vector< State >, greater< State > > que;
	que.push(State{S, 0});
	dst[S] = 0;
	
	while (!que.empty()) {
		State s = que.top(); que.pop();
		if (dst[s.v] < s.dst) continue;
		
		//cerr << "cur: " << s.v << " " << s.dst << endl;
		for (const Edge& e : edge[s.v]) {
			lint nxt_dst = getBestDst(s.dst, e.a, e.b);
			if (dst[e.to] == -1 || dst[e.to] > nxt_dst) {
				dst[e.to] = nxt_dst;
				que.push(State{e.to, nxt_dst});
			}
		}
	}
	
	cout << dst[G] << endl;
}

int main() {
	cin >> N >> M >> S >> G;
	--S; --G;

	edge.assign(N, vector< Edge >());
	
	for (int i=0; i<M; ++i) {
		int u, v;
		lint a, b;
		cin >> u >> v >> a >> b;
		--u; --v;
		
		edge[u].push_back(Edge{v, a, b});
		edge[v].push_back(Edge{u, a, b});
	}
	
	solve();
}


Measured memory_bytes: 26584
#include <bits/stdc++.h> 
using namespace std; 
int main(){
    int D;
    cin >> D;
    if (D == 22) {
        cout << "Christmas Eve Eve Eve";
    }
    if (D == 23) {
        cout << "Christmas Eve Eve";
    }
    if (D == 24) {
        cout << "Christmas Eve";
    }
    if (D == 25) {
        cout << "Christmas";
    }
} 

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

using namespace std;

int main(void)
{

  long long N, K;
  cin >> N >> K;

  long long count = N;
  count = N / K;
  long long tmp = N - K * count;
  long long minus = tmp - K;
  if (minus < 0)
  {
    minus = -minus;
  }
  if (minus < tmp)
  {
    cout << minus << endl;
  }
  else
  {
    cout << tmp << endl;
  }
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){
	int N,M;
	scanf("%d %d",&N,&M);
	int A[1001],i;
	for(i=1;i<=N;i++){
		scanf("%d",&A[i]);
	}

	int max=0,min=100,iM,i_check,range_sum=0;
	for(i=1;;i++){
		for(iM=1;iM<=M;iM++){
			i_check=i+iM-1;
			if(i_check>N)i_check-=N;
			if(A[i_check]>max)max=A[i_check];
			if(A[i_check]<min)min=A[i_check];
		}

		i=i_check;
		
		range_sum=range_sum+max-min;
		max=0;
		min=100;

		if(i_check==N)break;
	}

	printf("%d\n",range_sum);
}

Measured memory_bytes: 2748
#include <bits/stdc++.h>
#include <string>
#include <vector>
/* 変数i を n回繰り返すマクロ */
#define rep(i,n) for (int i = 0;i < (n);i++)
typedef long long ll;
using namespace std;
using Graph = vector<vector<int>>;
int main()
{
    cout << fixed << setprecision(10);//小数点以下10桁出力
    char s[60];
    int n;
    cin >> n;
    rep(i,n){
        char in;
        cin >> in;
        s[i] = in;
    }
    int cnt = 0;
    rep(i,n - 2){
        if(s[i] == 'A' && s[i + 1] == 'B' && s[i + 2] == 'C'){
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}

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

using namespace std;

int main() {
	int n;
	cin >> n;
	vector<int> h(n);
	for (int i=0; i<n; ++i) {
		cin >> h[i];
	}
	int sum = 1;
	for (int i=1; i<n; ++i) {
		bool see = true;
		for (int j=0; j<i; ++j) {
			if (h[j] > h[i]) {
				see = false;
				break;
			}
		}
		if (see) {
			sum += 1;
		}
	}
	cout << sum << endl;
	return 0;
}

Measured memory_bytes: 256
N = int(input())
s = [input() for i in range(N)]
M = int(input())
t = [input() for i in range(M)]

dic={}
for i in range(N):
    if s[i] in dic:
        dic[s[i]]+=1
    else:
        dic[s[i]]=1

for i in range(M):
    if t[i] in dic:
        dic[t[i]]-=1
    else:
        dic[t[i]]=-1

print(max(0,max(dic.values())))

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);  
	
	string s;
	cin >> s;
	if(s[0] != 'A') {
		cout << "WA" << endl;
		return 0;
	}
	int n = s.size();
	bool c = false;
	for(int i = 1; i < n; i++) {
		if(s[i] < 'a' || s[i] > 'z') {
			if(s[i] == 'C') {
				if(c && i >= 2 && i <= n - 2) {
					cout << "WA" << endl;
					return 0;
				} else if (!c && i >= 2 && i <= n - 2) {
					c = true;
				} else {
					cout << "WA" << endl;
					return 0;
				}
			} else {
				cout << "WA" << endl;
				return 0;
			}
		}
	}
	if(!c) cout << "WA" << endl;
	else cout << "AC" << endl;
	return 0;	
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll L,A,B,M;
mat mult(mat &A,mat &B){
	mat C(A.size(),vec(B[0].size()));
	for(int i=0;i<A.size();i++){
		for(int k=0;k<B.size();k++){
			for(int j=0;j<B[0].size();j++){
				(C[i][j] += A[i][k]*B[k][j]%M)%=M;
			}
		}
	}
	return C;
}

mat pow(mat A, ll n){
	if(n==1) return A;
	else if(n%2==0){
		mat B = pow(A,n/2);
		return mult(B,B);
	}else{
		mat B = pow(A,n-1);
		return mult(A,B);
	}
}

ll cnt[20] = {};
ll cnt2[20] = {};
ll p[19] = {1};

int main(){
    cin >> L >> A >> B >> M;
    for(int i=1;i<=18;i++) p[i] = 10*p[i-1];
    /*ll now = A;
    for(int i=0;i<L;i++){
        for(int j=1;j<=18;j++){
            if(now<p[j]){
                cnt2[j]++;
                break;
            }
        }
        now += B;
    }
    for(int i=1;i<=18;i++) cerr << cnt2[i] << " ";
    cerr << endl;
    */for(int i=1;i<=18;i++){
        if(p[i]-1<A) continue;
        if(A+(L-1)*B<p[i-1]) continue;
        cnt[i] = (min(p[i]-1,A+(L-1)*B)-A)/B+1;
        if(i>1 && p[i-1]-1>A) cnt[i] -= max((p[i-1]-1-A)/B+1,0LL);
    }
    ll ans = 0;
    mat res(3,vec(3,0));
    res[0][0] = res[1][1] = res[2][2] = 1;
   /* for(int i=1;i<=18;i++) cerr << cnt[i] << " ";
    cerr << endl;
   */ for(int i=1;i<=18;i++){
        if(cnt[i]==0) continue;
        mat A(3,vec(3,0));
        A[0][0] = p[i]%M; A[0][1] = A[1][1] = A[2][2] = 1;
        A[1][2] = B;
        mat a = pow(A,cnt[i]);
        res = mult(a,res);
    }
    cout << (res[0][2]+A%M*res[0][1]%M)%M << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
// rep(i, 1, 4) --> {1,2,3,4}
// rep(i, 4, 1) --> {4,3,2,1}
// rep(it, end(v), begin(v)) --> *it

using namespace std;

int main()
{
    int x, y, z;
    cin >> x >> y >> z;
    cout << (x-z)/(y+z);
    return 0;
}

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

#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef complex<double> point;
#define xx real()
#define yy imag()

#define REP(i, a, b) for(int i = (a); i < (int)(b); i++)
#define REPN(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FA(it, x) for(__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
#define SZ(x) (int)(x).size()
#define BE(x) (x).begin(), (x).end()
#define SORT(x) sort(BE(x))
#define _1 first
#define _2 second

#define x1 gray_cat_x1
#define y1 gray_cat_y1

template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define file "I1"

const double EPS = 1e-9;
const double PI = acos(-1.);
const int INF = 1e9;
const ll MOD = 1e9 + 7;

const int MAXN = 2e5 + 5;

vi g[MAXN];

int dp[MAXN][3];
int prv[MAXN];

void dfs(int s) {
	int cnt = 0;
	REP(i, 0, SZ(g[s])) {
		int to = g[s][i];
		if (to != prv[s]) {
			prv[to] = s;
			dfs(to);
			cnt++;
		}
	}
	if (cnt == 0) {
		dp[s][0] = 0;
		dp[s][1] = INF;
		dp[s][2] = 1;
	} else if (cnt == 1) {
		REP(i, 0, SZ(g[s])) {
			int to = g[s][i];
			if (to != prv[s]) {
				dp[s][0] = dp[to][0];
				dp[s][1] = dp[to][1];
				dp[s][2] = dp[to][2];
			}
		}
	} else {
		ll sum = 0;
		int mn = 0;
		REP(i, 0, SZ(g[s])) {
			int to = g[s][i];
			if (to != prv[s]) {
				int add = min(dp[to][1], dp[to][2]);
				sum = sum + add;
				mn = min(mn, dp[to][0] - add);
			}
		}
		dp[s][0] = INF;
		dp[s][1] = min((ll)INF, sum + mn);
		dp[s][2] = min((ll)INF, sum);
	}
}

void solve(){
	int n;
	scanf("%d", &n);
	REP(i, 0, n - 1) {
		int a, b;
		scanf("%d%d", &a, &b);
		g[a].pb(b);
		g[b].pb(a);
	}
	int root = -1;
	REP(i, 0, n) {
		if (SZ(g[i]) == 1) {
			root = i;
			break;
		}
	}
	prv[root] = -1;
	dfs(root);
	int ans = min(dp[root][2], min(dp[root][0], dp[root][1]) + 1);
	printf("%d\n", ans);
}   

int main(){

    //freopen(file".in", "r", stdin); freopen(file".out", "w", stdout);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();    
    }
}


Measured memory_bytes: 20096
try while 0=0do Scanf.scanf"%f %f %f %f %f %f
"(fun a b c d e f->let s=a*.e-.b*.d in Printf.printf"%.3f %.3f
"((e*.c-.b*.f)/.s+.0.)((a*.f-.d*.c)/.s+.0.))done with _->()

Measured memory_bytes: 2228
package main

import (
	"fmt"
	"math"
)

func main() {
	var n, d int
	fmt.Scan(&n, &d)
	cordinates := ScanCordinates(n, d)
	ans := 0
	for i := 0; i < len(cordinates)-1; i++ {
		for j := i + 1; j < len(cordinates); j++ {
			n := 0.0
			for k := 0; k < d; k++ {
				n += math.Pow(math.Abs(float64(cordinates[i][k]-cordinates[j][k])), 2)
			}
			if math.Sqrt(n) == math.Trunc(math.Sqrt(n)) {
				ans++
			}
		}
	}
	fmt.Println(ans)
}

func ScanCordinates(n int, d int) (cordinates [][]int) {
	for i := 0; i < n; i++ {
		cordinates = append(cordinates, ScanNums(d))
	}
	return cordinates
}

func ScanNums(len int) (nums []int) {
	var num int
	for i := 0; i < len; i++ {
		fmt.Scan(&num)
		nums = append(nums, num)
	}
	return
}


Measured memory_bytes: 512
import java.util.*;

public class Main {
  static long MOD = (long)Math.pow(10, 9) + 7;
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    long n = sc.nextLong();
    long k = sc.nextLong();
    long[] kai = new long[(int)(n + 1)];
    kai[0] = 1;
    for(long i = 1; i <= n; i++) {
      kai[(int)i] = (kai[(int)(i - 1)] * i) % MOD;
    }
    for(long i = 1; i <= k; i++) {
      long s1 = kai[(int)(n - k + 1)];
      long s2 = kai[(int)i];
      long s3 = 1;
      if((n - k + 1 - i) >= 0) {
        s3 = kai[(int)(n - k + 1 - i)];
      } else {
        s3 = 0;
      }
      s2 = func(s2, MOD - 2);
      s3 = func(s3, MOD - 2);
      long ans1 = (s1 * s2) % MOD;
      ans1 = (ans1 * s3) % MOD;

      long t1 = kai[(int)(k - 1)];
      long t2 = kai[(int)(i - 1)];
      long t3 = kai[(int)(k - i)];
      t2 = func(t2, MOD - 2);
      t3 = func(t3, MOD - 2);
      long ans2 = (t1 * t2) % MOD;
      ans2 = (ans2 * t3) % MOD;

      System.out.println((ans1 * ans2) % MOD);
    }
  }

  public static long func(long a, long x) {
    if(x == 0) return 1;
    if(x % 2 == 0) {
      long t = func(a, x / 2);
      return (t * t) % MOD;
    } else {
      long t = func(a, x / 2);
      t = (t * t) % MOD;
      return (a * t) % MOD;
    }
  }
}


Measured memory_bytes: 23764
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<string> VS;
typedef vector< vector<int> > VVI;
typedef vector< vector<ll> > VVL;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(a) (a).begin(),(a).end()
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
 
int main(){
  string S,T;
  cin>>S>>T;
  int X[26][26]={};
  int N=S.size();
  rep(i,N){
    if(X[S[i]-'a'][T[i]-'a']==0){
      X[S[i]-'a'][T[i]-'a']=1;
    }
  }
  rep(i,26){
    int cnt=0;
    rep(j,26) cnt+=X[i][j];
    if(cnt>1){
      cout<<"No"<<endl;
      return 0;
    }
  }
  rep(i,26){
    int cnt=0;
    rep(j,26) cnt+=X[j][i];
    if(cnt>1){
      cout<<"No"<<endl;
      return 0;
    }
  }
  cout<<"Yes"<<endl;
}

Measured memory_bytes: 776
using System;

class Program
{
	static void Main(string[] args)
	{
		// スペース区切りの整数の入力
		int[] ab = Array.ConvertAll(Console.ReadLine().Split(' '),i=>int.Parse(i));
        int a = ab[0];
        int b = ab[1];

        int max = a+b;
        max = max > a-b ? max : a-b;
        max = max > a*b ? max : a*b;

        Console.WriteLine(max);
    }
}

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

#define rep(i,n) for(i = 0;i < n;++i)
#define all(v) v.begin(), v.end()
using ll = long long;

int main()
{
    ll i,j;
    ll n,k;
    cin >> n >> k;
    vector<ll> a(n);
    for(i = 0;i < n;++i){
        cin >> a.at(i);
    }
    ll bit;
    ll ans = 1e14;
    for(bit = 1;bit < (1 << n);++bit){
        vector<ll> b;
        for(i = 0;i < n;++i){
            if(bit & (1 << i)) b.push_back(i);
        }
        if(b.size() < k) continue;
        ll tmp = 0;
        ll tmpans = 0;
        j = 0;
        for(i = 0;i < n;++i){
            if(i < b.at(j)) tmp = max(tmp, a.at(i));
            else if(i == b.at(j)){
                if(tmp >= a.at(b.at(j))){
                    tmpans += tmp - a.at(b.at(j)) + 1;
                    tmp += 1;
                }else{
                    tmp = a.at(b.at(j));
                }
                ++j;
                if(j == b.size()) break;
            }
        }
        ans = min(ans, tmpans);
    }
    cout << ans << endl;
    return 0;
}

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

int a[1000010];

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    int n;
    cin >> n;
    int a = 0, b = 0, c = 0, d = 0;
    for(int i=0;i<n;i++){
        string s;
        cin >> s;
        if(s[0] == 'A') a++;
        else if(s[0] == 'W') b++;
        else if(s[0] == 'T') c++;
        else d++;
    }
    printf("AC x %d\n", a);
    printf("WA x %d\n", b);
    printf("TLE x %d\n", c);
    printf("RE x %d\n", d);
}

Measured memory_bytes: 3748
N=int(input())
A=list(map(int, input().split()))
B=list(map(int, input().split()))
nega=0
posi=0
yoyu=[]
ans=0
for i in range(N):
  tmp=A[i]-B[i]
  if tmp>=0:
    posi+=tmp
    yoyu.append(tmp)
  else:
    nega+=-1*tmp
    ans+=1
if posi<nega:
  print(-1)
  exit()
elif nega==0:
  print(0)
  exit()

yoyu.sort(reverse=True)
S=0
i=0
while (1):
  S+=yoyu[i]
  if nega<=S:
    ans+=i+1
    print(ans)
    break
  else:
    i+=1

Measured memory_bytes: 24236