akhauriyash/Code-Regression huggingface dataset:
// #pragma GCC target("avx2")  // CPU 処理並列化
// #pragma GCC optimize("O3")  // CPU 処理並列化
// #pragma GCC optimize("unroll-loops")  // 条件処理の呼び出しを減らす
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
#include<numeric>
using namespace std;
const long long mod=998244353;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const double EPS=1e-10;
const double INF=1e+10;
const double PI=acos(-1.0);
const int C_SIZE = 3121000;
long long fact[C_SIZE];
long long finv[C_SIZE];
long long inv[C_SIZE];
long long Comb(int a,int b){
 	if(a<b||b<0)return 0;
 	return fact[a]*finv[b]%mod*finv[a-b]%mod;
}
void init_C(int n){
	fact[0]=finv[0]=inv[1]=1;
	for(int i=2;i<n;i++){
		inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
	}
	for(int i=1;i<n;i++){
		fact[i]=fact[i-1]*i%mod;
		finv[i]=finv[i-1]*inv[i]%mod;
	}
}
long long pw(long long a,long long b){
	if(a<0LL)return 0;
	if(b<0LL)return 0;
	long long ret=1;
	while(b){
		if(b%2)ret=ret*a%mod;
		a=a*a%mod;
		b/=2;
	}
	return ret;
}
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}
double ABS(double a){return max(a,-a);}
int sig(double r) { return (r < -EPS) ? -1 : (r > +EPS) ? +1 : 0; }
// ここから編集しろ
int x[210000];
int y[210000];
int bit[210000];
int sum(int a,int b){
	if(a>b)return 0;
	if(a)return sum(0,b)-sum(0,a-1);
	int ret=0;
	for(;b>=0;b=(b&(b+1))-1)ret+=bit[b];
	return ret;
}
void add(int a,int b){
	for(;a<210000;a|=a+1)bit[a]+=b;
}
int zx[210000];
int zy[210000];
pair<int,int>ev[210000];
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++)scanf("%d%d",x+i,y+i);

	long long ret=a*pw(2,a)%mod;

	for(int i=0;i<4;i++){
		for(int j=0;j<a;j++){
			zx[j]=x[j];
			zy[j]=y[j];
		}
		std::sort(zx,zx+a);
		std::sort(zy,zy+a);
		for(int j=0;j<210000;j++)bit[j]=0;
		for(int j=0;j<a;j++){
			ret=(ret+mod-pw(2,j))%mod;
		}
		for(int j=0;j<a;j++){
			int cx=lower_bound(zx,zx+a,x[j])-zx;
			int cy=lower_bound(zy,zy+a,y[j])-zy;
			ev[j]=make_pair(cx,cy);
		}
		std::sort(ev,ev+a);
		for(int j=0;j<a;j++){
			int cnt=sum(0,ev[j].second-1);
			ret=(ret+pw(2,cnt))%mod;
			add(ev[j].second,1);
		}
		for(int j=0;j<a;j++){
			int nx=y[j];
			int ny=-x[j];
			x[j]=nx;
			y[j]=ny;
		}
	//	printf("%lld\n",ret);
	}
	ret=(ret+mod-a)%mod;

	printf("%lld\n",ret);
}


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

//ofstream outputfile("test.txt");
int main(){
    //outputfile.close();
    int n;
    ll mm = 0;
    for(int i=1;i<1000;i++){
        if(i%3==0){
            mm += 20*10;
        }else{
            mm += 20*5 + 19*5;
        }
    }
    mm+=1;
    cin>>n;
    for(int i=0;i<n;i++){
        int y,m,d;
        ll sum=0;
        cin>>y>>m>>d;
        for(int i=1;i<y;i++){
            if(i%3==0){
                sum += 20*10;
            }else{
                sum += 19*5+20*5;
            }
        }
        if(y%3==0){
            sum += 20*(m-1) + d;
        }else{
            for(int i=1;i<m;i++){
                if(i%2==0){
                    sum+=19;
                }else{
                    sum += 20;
                }
            }
        sum += d; 
        }
        cout<<mm-sum<<endl;
    }
}


Measured memory_bytes: 3100
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>
#include <cstring>

#define rep(i, m, n) for(int i=int(m);i<int(n);i++)
#define all(c) begin(c),end(c)

template<typename T1, typename T2>
inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }

template<typename T1, typename T2>
inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }

//改造
typedef long long int ll;
using namespace std;
#define INF (1 << 30) - 1
#define INFl (ll)5e15
#define DEBUG 0 //デバッグする時1にしてね
#define dump(x)  cerr << #x << " = " << (x) << endl
#define MOD 1000000007


//ここから編集する
class Solve {
public:
    void input() {

    }

    void solve() {
        input();
        int N;
        cin >> N;
        string S;
        cin >> S;
        int K;
        cin >> K;
        char c = S[K - 1];

        for(auto e : S){
            if(e == c) cout << e;
            else cout << "*";
        }
        cout << endl;

    }
};


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

    Solve().solve();


    return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace Tasks
{
    public class C
    {
        static void Main(string[] args)
        {
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);
            Solve();
            Console.Out.Flush();
        }

        public static void Solve()
        {
            var (N, K) = Scanner.Scan<int, int>();
            var H = Scanner.ScanEnumerable<long>().ToArray();
            var answer = H.OrderByDescending(x => x).Skip(K).Sum();
            Console.WriteLine(answer);
        }

        public static class Scanner
        {
            private static Queue<string> queue = new Queue<string>();
            public static T Next<T>()
            {
                if (!queue.Any()) foreach (var item in Console.ReadLine().Trim().Split(" ")) queue.Enqueue(item);
                return (T)Convert.ChangeType(queue.Dequeue(), typeof(T));
            }
            public static T Scan<T>() => Next<T>();
            public static (T1, T2) Scan<T1, T2>() => (Next<T1>(), Next<T2>());
            public static (T1, T2, T3) Scan<T1, T2, T3>() => (Next<T1>(), Next<T2>(), Next<T3>());
            public static (T1, T2, T3, T4) Scan<T1, T2, T3, T4>() => (Next<T1>(), Next<T2>(), Next<T3>(), Next<T4>());
            public static (T1, T2, T3, T4, T5) Scan<T1, T2, T3, T4, T5>() => (Next<T1>(), Next<T2>(), Next<T3>(), Next<T4>(), Next<T5>());
            public static IEnumerable<T> ScanEnumerable<T>() => Console.ReadLine().Trim().Split(" ").Select(x => (T)Convert.ChangeType(x, typeof(T)));
        }
    }
}


Measured memory_bytes: 55880
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
using namespace std;
const long long num=1000000007;
int prim[100100];
long long  ans=1;
void judge(int N,int flag)
{
    int i=flag+1;
    for(int j=flag;j<N;j++)
    {
        if(prim[j++]==i&&prim[j]==i)
        {
            ans*=2;
            ans%=num;
            i+=2;
        }
        else
        {
            ans=0;
            return;
        }
    }
    return ;
}
int main()
{
    int N;
    scanf("%d",&N);
    for(int i=0;i<N;i++)
        scanf("%d",&prim[i]);
    sort(prim,prim+N);
    //for(int i=0;i<N;i++)
       // printf("%d ",prim[i]);
    //cout<<endl;

    if(N%2==1&&prim[0]==0)
    {
        judge(N,1);
    }
    else if(N%2==1&&prim[0]!=0)
    {
        printf("0\n");
    }
    else
    {
        judge(N,0);
    }
        printf("%lld\n",ans);
        return 0;
}


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

int main(){
    int H,W;
   while(true){
       cin >>H >>W;
       if(H == 0&&W ==0) break;
       for(int i =0;i<H;i++){
            for(int j = 0;j<W;j++){
                cout << '#';
            }
            cout << endl;
       }
       cout << "\n";
       



   }
    
}


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

using namespace std;

int n;
vector < int > b;
vector < int > ans;

int main()
{
	cin >> n;
	b.push_back( 1e9 );
	
	for ( int i = 1; i <= n; i++ ){
		int a; cin >> a;
		b.push_back(a);
	}
	
	for ( int i = n + 1; i >= 1; i -- ){
		if ( b.size() == 1 )
			break;
		
		vector < int > c;
		bool T = true;
		
		for ( int j = ( int )b.size() - 1; j >= 1; j -- ) {
			if ( b[j] == j && T){
				ans.push_back( b[j] );
				T = false;
			}
			else
				c.push_back( b[j] ); 
		}
		c.push_back( 1e9 );
		reverse( c.begin(), c.end() );
		
		
		if ( c.size() == b.size() ){
			cout << -1;
			return 0;
		}
		swap( c, b );
		
	}
	reverse( ans.begin(), ans.end() ); 
	for ( auto c: ans )
		cout << c << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
       
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
       

template <typename T>
class CumulativeSum2D {
  vector<vector<T>> S;

 public:
  CumulativeSum2D(const vector<vector<T>>& a) {
    int n = a.size(), m = a[0].size();
    S.resize(n + 1, vector<T>(m + 1, 0));
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        S[i + 1][j + 1] = S[i + 1][j] + S[i][j + 1] - S[i][j] + a[i][j];
      }
    }
  }
  T query(int i1, int j1, int i2, int j2) {
    return S[i2][j2] - S[i2][j1] - S[i1][j2] + S[i1][j1];
  }
};

int main() {
  int H, W, K;
  cin >> H >> W >> K;

  vector<vector<int>> S(H, vector<int>(W));
  for (int i = 0; i < (int)(H); ++i) for (int j = 0; j < (int)(W); ++j) {
    char c;
    cin >> c;
    S[i][j] = (c == '1');
  }

  CumulativeSum2D<int> cum(S);

  int ans = 1e9;
  for (int s = 0; s < (int)(1 << (H - 1)); ++s) {
    int cost = 0;
    vector<int> r;
    r.push_back(0);
    for (int i = 0; i < (int)(H - 1); ++i) if ((s >> i) & 1) {
      r.push_back(i + 1);
      ++cost;
    }
    r.push_back(H);

    int R = r.size();
    int l = 0;
    for (int i = 0; i < W; ++i) {
      bool ok = true;
      for (int j = 0; j < (int)(R - 1); ++j) ok &= (cum.query(r[j], l, r[j + 1], i + 1) <= K);
      if (!ok) {
        ++cost;
        l = i;
      }
    }
    bool ok = true;
    for (int j = 0; j < (int)(R - 1); ++j) ok &= (cum.query(r[j], l, r[j + 1], W) <= K);
    if (!ok) continue;

    chmin(ans, cost);
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <cctype>
#include <stdio.h>
using namespace std;
int main(void){

    char ch;

    while(1){
        scanf("%c", &ch);
        
        if(islower(ch)){
            cout <<  static_cast<char>(toupper(ch));
        }else if(isupper(ch)){
            cout << static_cast<char>(tolower(ch));
        }else{
            cout << ch;
        }
        
        if ( ch == '\n' ) break;
    }
}

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

int main(void) {
ll n,d;
cin >> n >> d;
ll ans = 0;
rep(i,n) {
    ll a,b;
    cin >> a >> b;
    ll cnt = pow(a,2) + pow(b,2);
    if (cnt <= pow(d,2)) ans++;  
}
cout << ans << endl;

return 0;
}





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

int main(){
    int n,i,x;
    cin>>n;
    i=1;;
    while (i<=n){
        x=i;
        if (i%3==0){
            cout<<" "<<i;
        }else while (x>=1){ 
            if (x%10==3){
                cout<<" "<<i;
                break;
            }else{
                x/=10;
            }
            
        }
        i++;
    }
    cout<<endl;
    return 0;
}
    
    



Measured memory_bytes: 3096
n, m = map(int, input().split())
products = [int(s) for s in input().split()]
products.sort(reverse=True)

border = sum(products) / 4 / m

cnt = 0
ans = 'No'
for i in products:
    if border <= i:
        cnt += 1
        if cnt == m:
            ans = 'Yes'
            break

print(ans)

Measured memory_bytes: 3060
#!/usr/bin/env python

N = list(map(int, list(input())))

ans = "Yes"
for top in range(len(N)):
    last = len(N) - 1 - top
    
    if top >= last:
        break

    if N[top] != N[last]:
        ans = "No"
        break
    
print(ans)






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

int main()
{
	int input1,input2;
	int calcResult;
  	cin >> input1;
  	cin >> input2;
  
  	calcResult = input1 * input2;
  if (calcResult % 2 ==1)
  {
	cout << "Odd";    
  }else{
	cout << "Even";    
  }
  
}

Measured memory_bytes: 256
open System
open System.Collections.Generic

[<AutoOpen>]
module Cin =
    let read f = stdin.ReadLine() |> f
    let reada f = stdin.ReadLine().Split() |> Array.map f
    let readChars() = read string |> Seq.toArray
    let readInts() = readChars() |> Array.map (fun x -> Convert.ToInt32(x.ToString()))

[<AutoOpen>]
module Cout =
    let writer = new IO.StreamWriter(new IO.BufferedStream(Console.OpenStandardOutput()))
    let print (s: string) = writer.Write s
    let println (s: string) = writer.WriteLine s
    let inline puts (s: ^a) = string s |> println

// -----------------------------------------------------------------------------------------------------

// -----------------------------------------------------------------------------------------------------

let main() =
    let n = read int
    let bs = reada int |> Array.sort
    let mutable ok = true
    for i in 0 .. n - 2 do
        if bs.[i] = bs.[i + 1] then ok <- false

    if ok then "YES" else "NO"
    |> puts
    ()

// -----------------------------------------------------------------------------------------------------
main()
writer.Dispose()


Measured memory_bytes: 33180
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <bitset>
#include <string>
#include <cmath>
#include <set>
#include <map>
#define Rep(i, x, y) for (int i = x; i <= y; i ++)
#define Dwn(i, x, y) for (int i = x; i >= y; i --)
#define RepE(i, x) for (int i = pos[x]; i; i = g[i].nex)
#define ev g[i].y
using namespace std;
typedef long long ll;
typedef double db;
const int N = 100010;
int n, L, t, p, k;
struct arr { int x, id, t; } a[N];
bool cmp(arr a, arr b) { return a.x == b.x ? a.t > b.t : a.x < b.x; }
int main()
{
	scanf ("%d%d%d", &n, &L, &t);
	Rep(i, 1, n) {
		scanf ("%d%d", &a[i].x, &a[i].t);
		a[i].id = i;
		if (a[i].t == 1) k = i;
	}
	if (k) {
		p = 0;
		int y, z;
		Rep(i, 1, n) if (a[i].t == 2) {
			y = (a[i].x - a[k].x + L) % L;
			if (2 * t >= y) z = (2 * t - y) / L + 1;
			else z = 0;
			(p += z) %= n;
		}
		p = (k + p - 1) % n + 1;
		// cout << k<<" "<<p<<endl;
	}
	Rep(i, 1, n) {
		if (a[i].t == 1) a[i].x = (a[i].x + t) % L;
		else a[i].x = (a[i].x + L - t % L) % L;
	}
	if (!k) {
		Rep(i, 1, n) printf("%d\n", a[i].x);
		return 0;
	}
	sort(a + 1, a + n + 1, cmp);
	int x;
	Rep(i, 1, n) if (a[i].id == k) {
		x = (n - p + i) % n + 1;
		break ;
	}
	for(int i = x;;) {
		printf("%d\n", a[i].x);
		i = i % n + 1;
		if (i == x) break ;
	}

	return 0;
}

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

using ll = long long;
const ll amari = 1e9+7;
#define ben(a) a.begin(),a.end()
#define pb(a,b) a.push_back(b)

int main(){
	int a,b;
	cin >> a >> b;
	if(a + b >= 24)cout << a + b - 24 << endl;
	else cout << a + b << endl;
	return 0; 
}

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

using ll = long long;
using namespace std;

#define ALL(c) (c).begin(), (c).end()

int main() {
  while (true) {
    int n, x;
    int res = 0;
    cin >> n >> x;
    if ((n | x) == 0) break;
    for (int i = 1; i < n; i++)
      for (int k = i + 1; k < n; k++) {
        int t = x - i - k;
        if (i == k || k == t || t == i) continue;
        if (k < t && t <= n) res++;
      }
    cout << res << endl;
  }
}


Measured memory_bytes: 3100
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long ll;
typedef pair<ll,ll> P;
const ll mod=1000000007;
const ll LINF=1LL<<60;
const int INF=1<<30;

int main(){
	int a,b,c;
	cin >> a >> b >>c;
	if (a+b+c >= 22){
		cout << "bust" << endl;
	}
	else{
		cout << "win" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<climits>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<numeric>
#include<map>
#include<set>
#include<bitset>
using namespace std;
#define REP(i,m,n) for(int i = m; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a)  (a).rbegin(),(a).rend()
#define LL long long
template<class T> inline void chmax(T & a, T b) { if (a < b) { a = b; } }
template<class T> inline void chmin(T& a, T b) { if (a > b) { a = b; } }
template<class T> void print_vector(vector<T> vec) {
	cout << "[ ";
	for (int i = 0; i < vec.size(); i++) {
		cout << vec[i] << " ";
	}
	cout << "]" << endl;
}
template<class T> void print_pair_vector(vector<pair<T, T> > vec) {
	cout << "[ ";
	for (int i = 0; i < vec.size(); i++) {
		cout << "(" << vec[i].first << "," << vec[i].second << ") ";
	}
	cout << "]" << endl;
}

int main(void) {
	string S;
	cin >> S;
	S[3] = '8';
	cout << S << endl;
	return 0;
}


Measured memory_bytes: 256
a = list(map(int, input().split()))
s = ['402351', '152304', '310542', '215043']   
for _ in range(int(input())):
    b, c = map(int, input().split())
    t = []
    t.append(a)
    i = 0; j = 0
    while True:
        if t[i][0] == b and t[i][1] == c:
            print(t[i][2])
            break
        if i == len(t)-1: # add if it finishes searching all path
            for h in range(len(s)):
                t.append([ t[j][int(k)] for k in list(s[h]) ])
            j+=1
        i+=1



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

using namespace std;

#define vi vector<int>
#define pb push_back
#define ll long long
#define qi queue<int>
#define vll vector<long long>
#define si set<int>
#define mi map<int,int>
#define mod %
#define pow ^
#define frt(i,a,b) for(int i=a;i<b;i++)
#define fre(i,a,b) for(int i=a;i<=b;i++)
#define pair_int pair<int,int>
#define pair_ll pair<ll,ll>
#define pq priority_queue
#define N 200007




ll M = 1000000007;
int dp[N][3];

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

   int n;
   cin >> n;

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

   int dp[n+1];
   dp[0]=0;
   dp[1]=0;
   dp[2]=abs(a[2]-a[1]);

   for(int i=3;i<=n;i++)
   {
   	  dp[i] = min(dp[i-1]+abs(a[i]-a[i-1]), dp[i-2]+abs(a[i]-a[i-2]));
   }
   cout << dp[n] << endl;



   return 0;
}


  


Measured memory_bytes: 1024
from collections import Counter
from functools import lru_cache
import sys
sys.setrecursionlimit(2*10**5)

N, M, Q = map(int, input().split())
L, R = zip(*(map(int, input().split()) for _ in range(M)))
p, q = zip(*(map(int, input().split()) for _ in range(Q)))

c = Counter(zip(L, R))


@lru_cache(maxsize=None)
def f(x, y):
    return (
        0 if x > y else
        c[x, y] + f(x + 1, y) + f(x, y - 1) - f(x + 1, y - 1)
    )


ans = '\n'.join(map(str, (f(x, y) for x, y in zip(p, q))))
print(ans)


Measured memory_bytes: 105720
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <numeric>
#include <limits>
#include <cmath>
#include <iomanip>
 
#define ALL(a)  (a).begin(),(a).end()
 
using namespace std;
typedef long long int ll;
typedef pair <int,int> P;
 
int main() {
    ll ans = 0;
    ll n, k, s;
    ll m = 1000000000;
 
    cin >> n >> k >> s;

    for (int i = 0; i < k; i++) {
        cout << s << endl;
    }
    for (int i = 0; i < n - k; i++) {
        (s != m) ? (cout << m << endl) : (cout << m-1 << endl);
    }
 
 
    return 0;
}

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

vector<int> parent(100100, -1);

void init(int n)
{
  for (int i = 0; i < n; i++)
  {
    parent.at(i) = -1;
  }
}

int root(int X)
{
  if (parent.at(X) < 0) return X;
  return parent.at(X) = root(parent.at(X));
}

int size (int X)
{
  return -1 * parent.at(root(X));
}

void unite(int X, int Y)
{
  int x = root(X);
  int y = root(Y);
  if (x == y) return;
  
  if (size(x) < size(y)) swap(x, y);
  parent.at(x) += parent.at(y);
  parent.at(y) = x;
}

int main()
{
  int N, M;
  cin >> N >> M;
  vector<long long> A(M), B(M);
  for (int i = 0; i < M; i++) cin >> A.at(i) >> B.at(i);
  
  init(N);
  
  vector<long long> ans(M + 1, 0);
  for (int i = 1; i <= M; i++)
  {
    int a = A.at(M - i), b = B.at(M - i);
    
    ans.at(i) = ans.at(i - 1);
    if (root(a) != root(b)) ans.at(i) += size(a) * size(b);
    
    unite(a, b);
  }
  
  for (int i = M - 1; i >= 0; i--)
  {
    cout << ans.at(M) - ans.at(i) << endl;
  }
}

Measured memory_bytes: 4096
#include <bits/stdc++.h>
using namespace std;
#define int long long
string n;int ans,k;
int g(int a,int b){
  int res=1;
  for(int i=0;i<b;i++)res*=a-i;
  for(int i=1;i<=b;i++)res/=i;
  while(b--)res*=9;
  return res;
}
int f(int i,int a){
  int res=0,rem=n.size()-i;
  if(rem<a)return 0;
  if(!a)return 1;
  if(n[i]=='0')return f(i+1,a);
  return f(i+1,a-1)+(n[i]-'1')*g(rem-1,a-1)+g(rem-1,a);
}

signed main(){
  cin>>n>>k;
  cout<<f(0,k)<<endl;
}


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

int main() {
  int N, K;
  cin >> N >> K;
  
  vector<char> S(N);
  for (int i = 0; i < N; i++) cin >> S.at(i);
  
  if (S.at(K - 1) == 'A') S.at(K - 1) = 'a';
  if (S.at(K - 1) == 'B') S.at(K - 1) = 'b';
  if (S.at(K - 1) == 'C') S.at(K - 1) = 'c';
  
  for (int i = 0; i < N; i++) cout << S.at(i);
  cout << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int a[10005];
int main()
{
	int n,x,i,j,k;
	long long int c;
	cin>>n;
	x=sqrt(n-4);
	for(i=1;i<=x;i++)
	for(j=i;j<=x;j++)
	for(k=j;k<=x;k++)
	{
		c=i*i+j*j+k*k+i*k+i*j+j*k;
		if(c>10000)continue;
		else
		{
		if(i==j&&j==k)a[c]+=1;
		else if(i!=j&&j!=k&&i!=k)a[c]+=6;
		else a[c]+=3;
		}
		
	}
	for(i=1;i<=n;i++)
	cout<<a[i]<<endl;
} 

Measured memory_bytes: 3596
#include <cstdio>
const int MAXN = 366;

const int move[] = {0, 1, 2, -1, -2, 4, 8, -4, -8};
int Day;
int rain[MAXN+10][20];
int vis[MAXN][12][7][7][7][7], T;

int dfs(int D, int pos, int n1, int n4, int n13, int n16){
    if(pos==1) n1 = 0; //1  2  3  4
    if(pos==3) n4 = 0; //5  6  7  8
    if(pos==9) n13= 0; //9  10 11 12
    if(pos==11)n16= 0; //13 14 15 16
    if(n1>=7 || n4>=7 || n13>=7 || n16>=7) return 0;
    if(D==Day+1) return 1;
    if(rain[D][pos]) return 0;
    if(rain[D][pos+1]) return 0;
    if(rain[D][pos+4]) return 0;
    if(rain[D][pos+5]) return 0;
    if(vis[D][pos][n1][n4][n13][n16]==T) return 0;
    vis[D][pos][n1][n4][n13][n16] = T;
    for(int i=0;i<9;i++){
        int npos = pos + move[i];
        if(npos%4 != (pos%4)+(move[i]%4) )  continue;
        if(npos<1 || 11<npos || npos==4 || npos==8) continue;
        if(dfs(D+1, npos, n1+1, n4+1, n13+1, n16+1)) return 1;
    }
    return 0;
}

int main(){
    while(scanf("%d", &Day)){
        if(Day==0) break;
        for(int i=1;i<=Day;i++){
            for(int j=1;j<=16;j++){
                scanf("%d", &rain[i][j]);
            }
        }
        T++;
        printf("%d\n", dfs(1, 6, 1, 1, 1, 1));
    }
    return 0;
}

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

const int MAX_N = 2 * 1e5 + 10;

int A[MAX_N];
int left_max[MAX_N], right_max[MAX_N];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> A[i];
    for (int i = 1; i <= N; i++) {
        left_max[i] = max(left_max[i - 1], A[i]);
    }
    for (int i = N; i >= 1; i--) {
        right_max[i] = max(right_max[i + 1], A[i]);
    }
    for (int i = 1; i <= N; i++) {
        cout << max(left_max[i - 1], right_max[i + 1]) << endl;
    }
    return 0;
}

Measured memory_bytes: 4096
N,M=(int(x) for x in input().split())
T=[1]*N
H=list(map(int,(input().split())))
while 1:
    try:
        A,B=(int(x) for x in input().split())
    except:
        break
    if(H[A-1]<H[B-1]):
        T[A-1]=0
    elif(H[B-1]<H[A-1]):
        T[B-1]=0
    else:
        T[A-1]=0
        T[B-1]=0
print(T.count(1))

Measured memory_bytes: 20920
//#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
using LL = int_fast64_t;
const LL MOD = 1e9+7;
const int MAXN = 2e5+7;

LL n,m;
LL pre[MAXN],suf[MAXN];
int main(){
    ____();
    cin >> n >> m;
    LL ret = 0;
    for(int i = 1; i <= n; i++) pre[i] = pre[i-1] + i;
    for(int i = n; i >= 0; i--) suf[i] = suf[i+1] + i;
    for(int i = m; i <= n + 1; i++){
        LL l = pre[i-1], r = suf[n+1-i];
        ret = (ret + r - l + 1) % MOD;
    }
    cout << ret << endl;
    return 0;
}

Measured memory_bytes: 6708
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<Long> list = new ArrayList<>();
        for (int i = 0; i < n; i++) list.add(sc.nextLong());
        
        if (list.contains(0L)) {
            System.out.println(0);
            return;
        }

        long result = 1;
        long max = (long) Math.pow(10, 18);
        for (int i = 0; i < n; i++) {
            if (max / result >= list.get(i)) {
                result *= list.get(i);
            } else {
                System.out.println(-1);
                return;
            }
        }
        System.out.println(result);
    }
}


Measured memory_bytes: 53120
import java.util.Scanner;
import java.util.stream.IntStream;

public class Main {

	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			char[] s = scanner.next().toCharArray();
			char[] result = new char[(s.length + 1) / 2];
			IntStream.range(0, result.length).forEach(i -> result[i] = s[2 * i]);
			System.out.println(result);
		}
	}
}


Measured memory_bytes: 27092
import scala.annotation.tailrec

object Main extends App {

  import scala.io.StdIn._
  solve
  @tailrec def solve: Unit = {
    val h = readLine.trim.toInt
    if (h == 0) return
    else {
      val state = Array.tabulate(h){_ ⇒ readLine.trim.split(' ').map(_.toInt)}
      var isVanished = true
      var score = 0
      while (isVanished){
        isVanished = false
        for (line ← state){
          line.indices.filter{i ⇒
            line(i) != -1 &&(
            ((i - 2 to i).forall(line.indices.contains(_)) && (i - 2 to i).forall(line(_) == line(i))) ||
              ((i - 1 to i + 1).forall(line.indices.contains(_)) && (i - 1 to i + 1).forall(line(_) == line(i))) ||
                ((i to i + 2).forall(line.indices.contains(_)) && (i to i + 2).forall(line(_) == line(i))))
          }.foreach{i ⇒
            score += line(i)
            line(i) = -1
            isVanished = true
          }
        }
        for (i ← 0 until 5){
          var bottom = h - 1
          for (j ← state.indices.reverse){
            if (state(j)(i) != -1){
              if (state(bottom)(i) == -1) {
                state(bottom)(i) = state(j)(i)
                state(j)(i) = -1
              }
              bottom -= 1
            }
          }
        }
      }
      println(score)
      solve
    }
  }
}



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

int main()
{
    int n, d;
    int x, y;
    int count = 0;

    cin >> n >> d;

    for (int i = 0; i < n; i++)
    {
        cin >> x >> y;

        if (sqrt((double)x * x + (double)y * y) <= d)
        {
            count++;
        }
    }

    cout << count << endl;

    return 0;
}


Measured memory_bytes: 3656
#include<stdio.h>
int main(){
int d=0,b=0,c=0,a[2],i;
  for(i=0;i<2;i++){
  scanf("%d",&a[i]);
    if(a[i]==2)c++;
    else if(a[i]==4||a[i]==6||a[i]==9||a[i]==11)b++;
    else d++;
  }
  if(b==2||c==2||d==2)printf("Yes");
  else printf("No");
  return 0;
}


Measured memory_bytes: 128
N, K = list(map(int, input().split()))
P = list(map(int, input().split()))
E = [(1+p)/2.0 for p in P]

x = 0.0
SUM = [0.0]
for e in E:
    x += e
    SUM += [x]

MAX = 0
for i in range(N-K+1):
    a = SUM[i+K] - SUM[i]
    if a > MAX:
        MAX = a

print(MAX)

Measured memory_bytes: 25604
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vs = vector<string>;
using vvs = vector<vs>;
using pli = pair<long long, int>;
using vpli = vector<pli>;

int main() {
  ll A, B, ans, r, tmp;
  cin >> A >> B;
  
  ans = A * B;
  
  if(A < B) {
    tmp = A;
    A = B;
    B = tmp;
  }

  r = A % B;
  while(r != 0) {
    A = B;
    B = r;
    r = A % B;
  }

  ans /= B; 

  cout << ans << endl;
  
}

Measured memory_bytes: 256
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <iomanip>


using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;

#define rep(i, a, b) for (int i=a; i<(b); i++)
#define rp(i, a) for (int i=0; i<(a); i++)
#define repd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define rpd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define shandom_ruffle random_shuffle

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001; //check the limits, dummy


int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cout << std::setprecision(9);
    cout << std::fixed;

    ll x,y;
    cin >> x >> y;
    set<ll> a;
    set<ll> b;
    set<ll> c;
    a.insert(1);
    a.insert(3);
    a.insert(5);
    a.insert(7);
    a.insert(8);
    a.insert(10);
    a.insert(12);

    b.insert(4);
    b.insert(6);
    b.insert(9);
    b.insert(11);

    c.insert(2);

    if(a.find(x) != a.end() && a.find(y) != a.end()){
        cout << "Yes"<<endl; return 0;
    }
    if(b.find(x) != b.end() && b.find(y) != b.end()){
        cout << "Yes"<<endl; return 0;
    }
    if(c.find(x) != c.end() && c.find(y) != c.end()){
        cout << "Yes"<<endl; return 0;
    }
    cout << "No"<<endl;
    return 0;
}

// read the question correctly (ll vs int)
// template by super1 derived from bqi343


Measured memory_bytes: 256
from collections import deque
n = int(input())
G = [[] for i in range(n)]

for i in range(1, n):
    a, b = map(lambda z: int(z)-1, input().split())
    G[a].append(b)
    G[b].append(a)

color = [-1] * n  # 木は二分グラフなので彩色

queue = deque([0])
color[0] = 0
red_blue = [1, 0]  # 色毎に塗った数を記録

while queue:
    now = queue.popleft()
    for to in G[now]:
        if color[to] == -1:
            color[to] = 1 - color[now]
            red_blue[color[to]] += 1
            queue.append(to)

ans = [-1] * n  # 異なる色が塗られたもの同士の数字がmod3で同じにならなければ十分
if 3*red_blue[0] < n:
    one, two, three = 0, 0, 0
    for i in range(n):
        if color[i] == 0:
            ans[i] = 3 * three + 3
            three += 1
        else:
            if 3*one + 1 <= n:
                ans[i] = 3 * one + 1
                one += 1
            elif 3*two+2 <= n:
                ans[i] = 3 * two + 2
                two += 1
            else:
                ans[i] = 3 * three + 3
                three += 1
elif 3*red_blue[1] < n:
    one, two, three = 0, 0, 0
    for i in range(n):
        if color[i] == 1:
            ans[i] = 3 * three + 3
            three += 1
        else:
            if 3 * one + 1 <= n:
                ans[i] = 3 * one + 1
                one += 1
            elif 3 * two + 2 <= n:
                ans[i] = 3 * two + 2
                two += 1
            else:
                ans[i] = 3 * three + 3
                three += 1
else:
    one, two, three = 0, 0, 0
    for i in range(n):
        if color[i] == 0:
            if 3*one+1 <= n:
                ans[i] = 3*one+1
                one += 1
            else:
                ans[i] = 3*three+3
                three += 1
        else:
            if 3*two+2 <= n:
                ans[i] = 3*two+2
                two += 1
            else:
                ans[i] = 3*three+3
                three += 1
                
print(*ans)


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

using namespace std;
 
#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

typedef int64_t ll; typedef vector<int> VI; typedef pair<ll,ll> pii;
const int MD = 1e9+7; typedef vector<ll> VL;

void dbg(){ cerr << "\n"; }  
template <typename T,typename ...T2>
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }


int main()
{
	
	//cin.tie(0); ios_base::sync_with_stdio(false);
	int n, c;
	cin >>n >>c;
	vector<VI> cl(c, VI(c));
	vector<VI> ba(n, VI(n));
	
	rep(i, c) rep(j, c) cin >>cl[i][j];
	rep(i, n) rep(j, n) cin >>ba[i][j], ba[i][j]--;
	
	vector<VI> sk(3, VI(c));
	rep(i,n) rep(j,n) sk[(i+j)%3][ba[i][j]]++;
	
	//for(auto xl: sk){for(auto x :xl) printf("%d ",x); puts("");}
	int ans = MD;
	rep(i,c) rep(j,c) rep(k,c) if(i!=j && i!=k && j!=k){
		int sm = 0;
		rep(p, c){
			sm += cl[p][i] * sk[0][p] + cl[p][j] * sk[1][p] + cl[p][k] * sk[2][p];
		}
		ans = min(ans, sm);
	}
	cout << ans <<"\n";
	return 0;
}


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

int main(){
  int n,k;
  string s;
  cin >> n >> s >> k;
  for(int i = 0; i < n; i++){
    if(s[i] != s[k-1]){
      s[i] = '*';
    }
  }
  cout << s << endl;
}

Measured memory_bytes: 3600
//author:Deshansh Garg
#include<bits/stdc++.h>
typedef long long int lli;
using namespace std;

    
int main()
{
 lli N,k;
 cin>>N>>k;
 lli arr[N];
 for(lli i=0;i<N;i++)
    cin>>arr[i];

  lli a[N]={0},x;
  for(lli i=1;i<N;i++)
  { lli mn=INT_MAX;
    for(lli j=i-1;j>=0 && j>=i-k;j--)
    {
         x=(a[j]+abs(arr[i]-arr[j])); 
         mn=min(x,mn);
    }
    a[i]=mn;
        /*
    if(i==1)
    {
        a[i]=abs(arr[1]-arr[0]);
    }
    else
    {
        a[i]=min(a[i-1]+abs(arr[i]-arr[i-1]),a[i-2]+abs(arr[i]-arr[i-2]));
    }*/
   
    
  } 
  cout<<a[N-1]<<endl;
 return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
    int n, k;
    cin >> n >> k;
    vector<int> v;
    for(int i = 0; i < n; ++i){
        int tmp_v;
        cin >> tmp_v;
        v.push_back(tmp_v);
    }
    int max = 0;
    vector<int> minus;
    for(int i = 0; i <= k; ++i){
        //operation A
        for(int j = 0; j <= (k-i); ++j){
            //operation B
            if(i+j > v.size()){
                break;
            }
            int sum = 0;
            for(int cnt = 0; cnt < i; ++cnt){
                sum += v[cnt];
                if(v[cnt] < 0){
                    minus.push_back(v[cnt]);
                }
            }
            for(int cnt = 0; cnt < j; ++cnt){
                sum += v[v.size()-cnt-1];
                if(v[v.size()-cnt-1] < 0){
                    minus.push_back(v[v.size()-cnt-1]);
                }
            }
            int back = k-i-j;
            if(back > minus.size()){
                for(int cnt = 0; cnt < minus.size(); ++cnt){
                    sum -= minus[cnt];
                }
            }else{
                sort(minus.begin(), minus.end());
                for(int cnt = 0; cnt < back; ++cnt){
                    sum -= minus[cnt];
                }
            }
            if(sum > max){
                max = sum;
            }
            minus.clear();
            //cout << i << ' ' << j << ' ' << back << ' ' << minus.size() << ' ' <<sum << endl;
        }
    }
    cout << max << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include <bits/stdc++.h>
#include<vector>
#include <algorithm>
#include <functional>
using namespace std;

int main(){
  long long a,b,c,k;
  cin >> a >> b >> c >> k;

  if(a>k){
    cout << k << endl;
  }else if((k>=a) && (a+b>=k)){
    cout << a << endl;
  }else if(k>a+b){
    cout << a-(k-(a+b)) << endl;
  }
}


Measured memory_bytes: 3580
import java.util.Scanner;

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

        int a = sc.nextInt();
        int b = sc.nextInt();
        sc.close();

        if(a <= b) {
            System.out.println(a);
        } else {
            System.out.println(a-1);
        }
    }
}


Measured memory_bytes: 21844
#include <iostream>
#define REP(i, n) for (int i = 0; i < (n); i++)
using namespace std;


void solve(long long K, long long X){
    int start = X - K + 1;
    int count = K * 2 - 1;
    for (int i = 0; i < count; i++) {
        cout << i + start;
        if (i != count - 1) cout << ' ';
        else cout << '\n';
    }
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    long long K;
    scanf("%lld",&K);
    long long X;
    scanf("%lld",&X);
    solve(K, X);
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
void solve(){
	int n;cin>>n;
	int near;
	if(n%1000==0)
	near=n;
	else
	near=(n/1000)*1000+1000;
	cout<<near-n;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);	 
	int T=1;
	//cin>>T;
	while(T--){
		solve();
	}
	return 0;
}

Measured memory_bytes: 3616
// Copyright 2020 yaito3014
#include <bits/stdc++.h>
using namespace std;

int main() {
	cin.tie(nullptr); ios::sync_with_stdio(false);
	int N, u, v;
	cin >> N >> u >> v, --u, --v;
	vector<deque<int>> edge_list(N);
	for(int i = 0; i < N - 1; ++i) {
		int A, B;
		cin >> A >> B, --A, --B;
		edge_list[A].push_back(B);
		edge_list[B].push_back(A);
	}
	constexpr int INF = INT_MAX;
	vector<int> u_cost(N, INF), v_cost(N, INF);
	u_cost[u] = v_cost[v] = 0;
	queue<int> que;
	deque<int> leaves;
	que.push(u);
	while(!que.empty()) {
		int cur = que.front();
		que.pop();
		for(int nxt : edge_list[cur])
			if(u_cost[nxt] == INF)
				que.push(nxt), u_cost[nxt] = u_cost[cur] + 1;
	}
	que.push(v);
	while(!que.empty()) {
		int cur = que.front();
		que.pop();
		if(edge_list[cur].size() == 1)
			leaves.push_back(cur);
		for(int nxt : edge_list[cur])
			if(v_cost[nxt] == INF)
				que.push(nxt), v_cost[nxt] = v_cost[cur] + 1;
	}
	int ans = 0;
	for(int i : leaves)
		if(u_cost[i] < v_cost[i])
			ans = max(ans, v_cost[i] - 1);
	cout << ans << endl;
}


Measured memory_bytes: 68480
# coding: utf-8
# Your code here!
x=0
n=str(input())
l=n.lower()
m=n.upper()
o=list(l)
S=[]
p=list(m)
T=[]
for i in range (len(o)):
    o[i]=o[i].upper()
    o[i-1]=o[i-1].lower()
    s = ''.join(o)
    S.append(s)
for j in range (len(o)):
    p[j]=p[j].lower()
    p[j-1]=p[j-1].upper()
    t=''.join(p)
    T.append(t)
while True:
    try:
        a=list(input().split())
        x+=a.count(l)
        x+=a.count(m)
        if len(S)>=2:
            for b in range (len(S)):
                x+=a.count(S[b])
        if len(T)>=2:
            for c in range (len(T)):
                x+=a.count(T[c])


    except:
        break;
print(x)


Measured memory_bytes: 5580
N = int(input())
v_list = list(map(int, input().split()))
v_list.sort()
ans = 0
ans = (v_list[0] + v_list[1]) / 2
if len(v_list) != 2:
    for v in v_list[2:]:
        ans = (v + ans) / 2
print(ans)

Measured memory_bytes: 3060
#include <stdio.h>

int main()
{ int s,m,h,i,x;
    scanf("%d",&s);
    h=s/3600;
    x=s%3600;
    m=x/60;
    i=x%60;
    printf("%d:%d:%d\n",h,m,i);
    return 0;
    
}



Measured memory_bytes: 2148
using System;
using System.Linq;
using System.Collections.Generic;
using System.IO;

namespace atcorder2
{
    class Program
    {
        public static long Read()
        {
            return long.Parse(Console.ReadLine());
        }

        public static long[] Reads()
        {

            return Console.ReadLine().Split().Select(long.Parse).ToArray();
        }






        static void Main(string[] args)
        {
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);


            var x = Read();
            double a = x;

            long ans = 0;
            for (int i = 1; i * (i + 1) < 2 * x; i++) ans=i;
            Console.WriteLine(ans + 1);
         
            Console.Out.Flush();
        }
    }
}




Measured memory_bytes: 13140
#include <stdio.h>

int main(void){
  int h,m,s,S;
  scanf("%d",&S);
  m = S / 60;
  s = S % 60;
  h = m / 60;
  m = m % 60;
  printf("%d:%d:%d\n",h,m,s);
  return 0;
}

Measured memory_bytes: 592
#include<bits/stdc++.h>
using namespace std;
#define REP(i,st,ed) for(register int i=st,i##end=ed;i<=i##end;++i)
#define DREP(i,st,ed) for(register int i=st,i##end=ed;i>=i##end;--i)
template<typename T>inline bool chkmin(T &x,T y){return (y<x)?(x=y,1):0;}
template<typename T>inline bool chkmax(T &x,T y){return (y>x)?(x=y,1):0;}
typedef long long ll;
inline int read(){
    int x;
    char c;
    int f=1;
    while((c=getchar())!='-' && (c>'9' || c<'0'));
    if(c=='-') f=-1,c=getchar();
    x=c^'0';
    while((c=getchar())>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0');
    return x*f;
}
inline ll readll(){
    ll x;
    char c;
    int f=1;
    while((c=getchar())!='-' && (c>'9' || c<'0'));
    if(c=='-') f=-1,c=getchar();
    x=c^'0';
    while((c=getchar())>='0' && c<='9') x=(x<<1ll)+(x<<3ll)+(c^'0');
    return x*f;
}
const int maxn=2e5+10;
int a[maxn],n,stk[maxn],top,num[maxn];
bool check(int x){
	top=0;
	memset(num,0,sizeof(num));
	REP(i,1,n){
		if(a[i]>a[i-1]) continue;
		while(a[i]<=stk[top-1]) --top;
		stk[++top]=a[i];
		if(a[i]>60) continue;
		else{
			num[a[i]]++;
			REP(j,a[i]+1,60) num[j]=0;
			if(num[a[i]]==x){
				int u=a[i];
				while(num[u]==x){
					num[u]=0,num[u-1]++;
					--u;
					if(u==0) return 0;
				}
			}
		}
	}
	return 1;
}
int main(){
	n=read();
	bool flag=0;
	REP(i,1,n) a[i]=read();
	REP(i,1,n) if(a[i]<=a[i-1]) flag=1;
	if(flag==0) return printf("1\n"),0;
	int L=2,R=n;
	while(L<=R){
		int Mid=(L+R)>>1;
		if(check(Mid)) R=Mid-1;
		else L=Mid+1;
	}
	printf("%d\n",R+1);
	return 0;
}

Measured memory_bytes: 1792
import static java.util.Arrays.deepToString;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

import org.omg.PortableServer.POAManagerPackage.State;

public class Main {
	public static void main(String[] args) {
		new Main().run();
	}
	void tr(Object... os) {
		System.err.println(deepToString(os));
	}

	Scanner sc = new Scanner(System.in);
	public void run() {
		for (;sc.hasNext();) {
			int R = sc.nextInt();
			int C = sc.nextInt();
			if ((C | R) == 0) break;
			int D = sc.nextInt();
			
			int[][] signals = new int[R][C];
			boolean[][][][] cannot = new boolean[R][C][R][C];
			int[][][][] jam = new int[R][C][R][C];
			
			int ns = sc.nextInt();
			for (int i = 0; i < ns; i++) {
				int[] rc = par(sc.next());
				int k = sc.nextInt();
				signals[rc[0]][rc[1]] = k;
			}
			
			int nc = sc.nextInt();
			for (int i = 0; i < nc; i++) {
				int[] rcf = par(sc.next());
				int[] rct = par(sc.next());
				cannot[rcf[0]][rcf[1]][rct[0]][rct[1]] = true;
				cannot[rct[0]][rct[1]][rcf[0]][rcf[1]] = true;
			}
			
			int nj = sc.nextInt();
			for (int i = 0; i < nj; i++) {
				int[] rcf = par(sc.next());
				int[] rct = par(sc.next());
				int d = sc.nextInt();
				jam[rcf[0]][rcf[1]][rct[0]][rct[1]] = d;
				jam[rct[0]][rct[1]][rcf[0]][rcf[1]] = d;
			}
			int[] start = par(sc.next());
			int[] goal = par(sc.next());
			
			// dir = 向いている方向, 0->, 1^, 2<-, 3v 
			boolean[][][][] possible = new boolean[R][C][102][4];
			possible[start[0]][start[1]][0][0] = true;
			
			int[] dr = {0, -1, 0, 1};
			int[] dc = {1, 0, -1, 0};
			
			for (int k = 0; k <= 100; k++) for (int d = 0; d < 4; d++) for (int r1 = 0; r1 < R; r1++) for (int c1 = 0; c1 < C; c1++) 
			if (possible[r1][c1][k][d])
			{
				for (int nd = 0; nd < 4; nd++) if (Math.abs(d - nd) != 2) {
					int r2 = r1 + dr[nd];
					int c2 = c1 + dc[nd];
					if (0 <= r2 && r2 < R && 0 <= c2 && c2 < C && !cannot[r1][c1][r2][c2]) {
						int nk = k + D + jam[r1][c1][r2][c2];
						if (nk > 101) nk = 101;
						if (signals[r2][c2] > 0) {
							int which = (nk / signals[r2][c2]) % 2;
							if ((which == 0 && (nd == 1 || nd == 3)) ||
								(which == 1 && (nd == 0 || nd == 2))) { //ok
								;
							} else {
								nk = 101;
							}
						}
						possible[r2][c2][nk][nd] = true;
					}
				}
			}
			
			int ans = 101;
			outer:
			for (int k = 0; k <= 100; k++) for (int d = 0; d < 4; d++)
				if (possible[goal[0]][goal[1]][k][d]) 
				{
					ans = k;
					break outer;
				}
			System.out.println(ans);
		}
	}
	
	int[] par(String s) {
		String[] ss = s.split("-");
		int r = (int)(ss[0].charAt(0) - 'a');
		int c = Integer.parseInt(ss[1]) - 1;
		return new int[]{r, c};
	}
}

Measured memory_bytes: 34332
#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
const long long LINF = 1e18;
#define dump(x)  cout << 'x' << ' = ' << (x) << ` `;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOREACH(x,a) for(auto& (x) : (a) )
typedef long long ll;
using namespace std;
int main(int argc, char const *argv[]) {
    string s;
    cin >> s;
    int n = s.size();
    string sans1, sans2;
    REP(i,n) {
        if (i%2 == 0) {
            sans1.push_back('0');
            sans2.push_back('1');
        }
        else {
            sans1.push_back('1');
            sans2.push_back('0');
        }
    }
    int ans1 = 0;
    int ans2 = 0;
    REP(i,n) {
        if (sans1[i] != s[i]) ans1++;
    }
    REP(i,n) {
        if (sans2[i] != s[i]) ans2++;
    }
    int ans = min(ans1, ans2);
    cout << ans << endl;
    return 0;
}

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

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    
    int n;
    cin >> n;
    
    vector<int> vec(n);
    for (int i = 0; i < n; ++i) {
        cin >> vec[i];
    }
    
    vector<int> D(n);
    D[0] = 0;
    D[1] = abs(vec[1] - vec[0]);
    for (int i = 2; i < n; ++i) {
        D[i] = min(D[i-1] + abs(vec[i-1] - vec[i]), D[i-2] + abs(vec[i-2] - vec[i]));
    }
    
    cout << D.back();
    
    return 0;
}

Measured memory_bytes: 1024
import itertools
import math
I = [int(_) for _ in open(0).read().split()]
N = I[0]
X, Y = I[1::2], I[2::2]
ans = 0
for root in itertools.permutations(range(N), N):
    for a, b in zip(root, root[1:]):
        ans += ((X[a] - X[b])**2 + (Y[a] - Y[b])**2)**0.5
ans /= math.factorial(N)
print(ans)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for(int i=0;i<(n);i++)
#define MOD 1000000007
#define all(n) (n).begin(),(n).end()
typedef long long ll;
template <class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}else{return 0;}}
template <class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}else{return 0;}}
template <class T> inline T GCD(T a,T b){T c;while(b!=0){c=a%b;a=b;b=c;}return a;}
template <class T> inline T LCM(T a,T b){return a*b/GCD(a,b);}

int main(){
	ll x;
	cin >> x;
	ll sum=0;
	sum+=(x/500)*1000;
	x%=500;
	sum+=(x/5)*5;
	cout << sum << endl;
}

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

int main() {
  int N;
  string S;
  cin >> N;
  cin >> S;
  int a = 0;
  for(int i = 0;i< S.size()-1;i++) {
  if( S.at(i) == S.at(i+1)){
    a++;
  }
  }
    cout << N - a << endl;

}

Measured memory_bytes: 512