akhauriyash/Code-Regression huggingface dataset:
cmp(int*a,int*b){return*a-*b;}
char x[9],buf[1100000];
sz;i;
T[1<<17];
N,C,K,k;
ans,id,pre;
main()
{
	read(0,buf,1100000);
	for(;;)
	{
		k=buf[sz++];
		if(k<'0')break;
		N=N*10+k-'0';
	}
	for(;;)
	{
		k=buf[sz++];
		if(k<'0')break;
		C=C*10+k-'0';
	}
	for(;;)
	{
		k=buf[sz++];
		if(k<'0')break;
		K=K*10+k-'0';
	}
	for(;i<N;++i)
	{
		for(;;)
		{
			k=buf[sz++];
			if(k<'0')break;
			T[i]=T[i]*10+k-'0';
		}
	}
	qsort(T,N,4,cmp);
	for(i=0;i<N;++i)
	{
		if(i-id>=C||pre<T[i])
		{
			ans+=1;
			pre=T[i]+K;
			id=i;
		}
	}
	sz=8;
	do
	{
		x[--sz]=ans%10+'0';
		ans/=10;
	}while(ans);
	write(1,x+sz,8-sz);
}


Measured memory_bytes: 1916
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<bitset>
#include<cstdio>
#include<cmath>
#include<map>
#include<numeric>
#include<set>
#include<sstream>
#include<string>
#include<utility>
#include<vector>

#define rep(i, a, n)  for(int i=a; i<n; ++i)
#define per(i, a, n)  for(int i=n-1; i>=a; --i)
#define fill0(n)  setfill('0') << right << setw(n)
#define all(x)  (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define INF 1000000007
using namespace std;
typedef long long ll;

int main(){
  const int N = 5;
  int antenna[N];
  int k;
  rep(i, 0, N){
    cin >> antenna[i];
  }
  cin >> k;
  rep(i, 0, N)  rep(j, i, N){
    if(antenna[j]-antenna[i]>k){
      cout << ":(" << endl;
      return 0;
    }
  }
  cout << "Yay!" << endl;
  return 0;
}

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

int main()
{
    string x;
    cin>>x;
    for(int i=0;i<x.size();i++)
    {
        if(x[i]=='9')
        cout<<1;
        else
        if(x[i]=='1')
        cout<<9;
        else
        cout<<x[i];
    }
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
  int ans;
  int su1;
  int su2=-1;
  char c;
  while(cin>>su1){
    if(su2==-1){
      cin >> c;
      ans = su1;
      su2 = 0;
      continue;
    }
    if(c=='+') ans += su1;
    else if(c=='-') ans -= su1;
    else if(c=='*') ans *= su1;
    else if(c=='/') ans /= su1;
    cin >> c;
    if(c=='=') break;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1160
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <string>
#include <vector>
#include <math.h>
#include <queue>
#include <deque>
#include <stack>
#include <map>
const int MOD = 1e9+7;
#define PI 3.14159265359
typedef long long ll;
using namespace std;


int main(){
	int n;
	cin >> n;
	cout << n/3 << endl;
	return  0;
}

Measured memory_bytes: 3584
import sys
sys.setrecursionlimit(10**6)

def InMap(): return list(map(int, sys.stdin.readline().split(' ')))
def In(): return int(sys.stdin.readline())
def InS(): return sys.stdin.readline()

N, K = InMap()
P = InMap()

tmp = sum(P[0:K])
Res = [0]*(N-K+1)
for i in range(K, N):
    Res[i - K] = tmp
    tmp -= P[i - K]
    tmp += P[i]
Res[-1] = tmp
print((max(Res) + K) / 2)

Measured memory_bytes: 24404
#include<bits/stdc++.h>
using namespace std;
#define re register
inline int read(){
	re int t=0;
	re char v=getchar();
	while(v<'0')v=getchar();
	while(v>='0')t=(t<<3)+(t<<1)+v-48,v=getchar();
	return t;
}
int n,a,b,dp[102][102],ans[102][102],m,dp1[102][102],ans1[102][102];
char mp[102][102];
int main(){
	n=read();m=read();
	for(re int i=1;i<=n;++i)scanf("%s",mp[i]+1);
	for(re int i=1;i<=n;++i)for(re int j=1;j<=m;++j)ans[i][j]=ans1[i][j]=1e9;
	ans[1][1]=0;
	for(re int i=1;i<=n;++i){
		for(re int j=1;j<=m;++j){
			for(re int k=0;k<=n;++k)for(re int l=0;l<=m;++l)dp[k][l]=dp1[k][l]=1e9;
			dp[i][j]=(mp[i][j]=='#'),dp1[i][j]=(mp[i][j]=='.');
			for(re int k=i;k<=n;++k){
				for(re int l=j;l<=m;++l){
					if(k==i&&l==j)continue;
					dp[k][l]=min(dp[k][l-1],dp[k-1][l]);
					
					dp1[k][l]=min(dp1[k][l-1],dp1[k-1][l]);
					
					ans[k][l]=min(ans[k][l],ans[i][j]+dp[k][l]);
					ans[k][l]=min(ans[k][l],ans[i][j]+dp1[k][l]+1);dp1[k][l]+=(mp[k][l]=='.');dp[k][l]+=(mp[k][l]=='#');
					ans1[k][l]=min(ans1[k][l],ans[i][j]+dp[k][l]);
					ans1[k][l]=min(ans1[k][l],ans[i][j]+dp1[k][l]+1);
				}
			}
		}
	}
	printf("%d",ans1[n][m]);
}

Measured memory_bytes: 384
#include <stdio.h>
#define N 10000
#define Q 500

int main(){
  int n, q, i, j, flag, flag2, flag3, count = 0;
  int s[N], t[Q];

  scanf("%d", &n);

  for(i = 0; i < n; i++){
    scanf("%d", &s[i]);
  }

  scanf("%d", &q);

  for(i = 0; i < q; i++){
    scanf("%d", &t[i]);
  }

  for(j = 0; j < q; j++){
    i = 0;
    flag = 0;
    flag2 = 0;
    flag3 = 0;
    s[n] = t[j];
    while(s[i] != s[n]){
      i++;
      if(i == n){
	flag2 = 1;
	break;
      }
      if(s[i] == s[n]){
	flag = 1;
      }
    }
    if(flag2 != 1 && flag == 0){
      flag3 = 1;
    }
    count += flag;
    count += flag3;
  }

  printf("%d\n", count);

  return 0;
}
  



Measured memory_bytes: 2108
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fast() ios_base::sync_with_stdio(0),cin.tie(0)
int INF=1e18;
int32_t main()
{int n,k,i,j,mn;
 cin>>n>>k;
 vector<int> v(n),dp(n);
 for(i=0;i<n;++i)
 cin>>v[i];
 dp[0]=0;
 dp[1]=abs(v[1]-v[0]);
 for(i=2;i<n;++i)
 {for(mn=INF,j=i-1;j>=0 && j>=i-k;--j)
  mn=min(mn,dp[j]+abs(v[i]-v[j]));
  dp[i]=mn;
 }
 //for(auto x:dp)
 //cout<<x<<" ";
 //cout<<"\n";
 cout<<dp[n-1];
 return 0;
}






Measured memory_bytes: 1792
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int main(){
  double x1,x2,x3,y1,y2,y3;
  int n;
  while(cin >> n){
    for(int i = 0 ; i < n ; i++){
      cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3; 
      double a = 2*(x2 - x1),b = 2*(y2 - y1),c = x1*x1 - x2*x2 + y1*y1 - y2*y2;
      double a2 = 2*(x3 - x1),b2 = 2*(y3 - y1),c2 = x1*x1 - x3*x3 + y1*y1 - y3*y3;
      double x = (b*c2 - b2*c)/(a*b2 - a2*b);
      double y = (c*a2 - c2*a)/(a*b2 - a2*b);
      double r = sqrt(pow(x-x1,2) + pow(y-y1,2));

      printf("%.3f %.3f %.3f\n",x,y,r);
    }
  }
  return 0;
}

Measured memory_bytes: 1244
#include <iostream>
#include <iomanip> //! for setprecision(10)
#include <math.h>
#include <algorithm>
#include <functional> 
#include <string>
#include <vector>

#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <utility>

using namespace std;

typedef long long LL;

#define dump(c) { for (auto it = c.begin(); it != c.end(); ++it) if (it == c.begin()) cout << *it; else cout << ' ' << *it; cout << endl; } 
#define rep(i,n) for (int i = 0; i < (n); ++i)

const int MOD = 1000000007;

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

    int N;
    LL D;
    cin >> N >> D;
    LL D2 = D*D;

    int ans = 0;
    rep(i, N) {
        LL X, Y;
        cin >> X >> Y;
        if (X*X+Y*Y <= D2) ++ans;
    }
    cout << ans << endl;

    return 0;
}


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

int main() {
	string S, d[4] = { "dream","dreamer","erase","eraser" };
	cin >> S;
	reverse(S.begin(), S.end());
	for (int i = 0; i < 4; i++) {
		reverse(d[i].begin(), d[i].end());
	}

	bool can = true;
	for (int i = 0; i < S.size();) {
		bool can2 = false;
		for (int j = 0; j < 4; j++) {
			if (S.substr(i, d[j].size()) == d[j]) {
				i += d[j].size();
				can2 = true;
			}
		}
		if (!can2) {
			can = false;
			break;
		}
	}

	if (can) {
		cout << "YES" << endl;
	}
	else {
		cout << "NO" << endl;
	}

	return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (n); i++)
#define MOD 1000000007
#define INF 1e9
#define All(x) (x).begin(), (x).end()
typedef long long ll;
using namespace std;

int main() {
  int H, M, h, m, k;
  cin >> H >> M >> h >> m >> k;

  int sa = h * 60 + m - H * 60 - M - k;
  cout << sa << endl;

  return 0;
}


Measured memory_bytes: 3636
def search(s, m, n, bridge):
    c = [1]
    d = [1]
    for k in range(n):
        cc = []
        for i, ci in enumerate(c):
            tmp = []
            for j in range(m):
                if j == bridge:
                    continue
                elif s[j][0] == ci and s[j][1] not in d:
                    tmp.append(s[j][1])
                elif s[j][1] == ci and s[j][0] not in d:
                    tmp.append(s[j][0])
            cc += tmp
            d += tmp
        if cc == []:
            break
        else:
            c = cc
    if len(d) == n:
        return 0
    else:
        return 1

n, m = map(int, input().split())
s = [list(map(int, input().split())) for _ in range(m)]
ans = 0
for i in range(m):
    ans += search(s, m, n, i)
print(ans)


Measured memory_bytes: 3064
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCorder
{
	public class Program
	{
		static void Main(string[] args)
		{
			long x = long.Parse(Console.ReadLine());
			
			long n = x / 11;
			long a = x % 11;
			long ans = n * 2;
			if (a > 0) {
				ans += a > 6 ? 2 : 1;
			}

			Console.WriteLine(ans);
		}
	}
}


Measured memory_bytes: 11092
#include<stdio.h>
#include<math.h>
#include<limits.h>
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define N 1000

int main(){
	int n,i,q,com,x,y,j;
	int a[N];
	int mini[N];
	int maxi[N];
	int b;
	int min=INT_MAX;
	int max=INT_MIN;
	
	scanf("%d",&n);
	b=sqrt(n);
	
	for(i=0;i<n;i++){
		scanf("%d",&a[i]);
		min=MIN(min,a[i]);
		max=MAX(max,a[i]);
		
		if(i%b==b-1){
			mini[i/b]=min;
			maxi[i/b]=max;
			min=INT_MAX;
			max=INT_MIN;
		}
	}
	
	scanf("%d",&q);
	for(i=0;i<q;i++){
		scanf("%d %d %d",&com,&x,&y);
		
		if(com){
			max=INT_MIN;
			if((y-1)/b-x/b <=1){
				for(j=x;j<=y-1;j++)max=MAX(max,a[j]);
			}
			else {
				for(j=x;j<=MIN(y-1,(x/b+1)*b-1);j++)max=MAX(max,a[j]);
				
				for(j=x/b+1;j<(y-1)/b;j++)max=MAX(max,maxi[j]);
			
				for(j=MAX(x,(y-1)/b*b);j<=y-1;j++)max=MAX(max,a[j]);
			}
			
			printf("%d\n",max);
		}
		
		else {
			min=INT_MAX;
			if((y-1)/b-x/b <=1){
				for(j=x;j<=y-1;j++)min=MIN(min,a[j]);
			}
			else {
				for(j=x;j<=MIN(y-1,(x/b+1)*b-1);j++)min=MIN(min,a[j]);
				
				for(j=x/b+1;j<(y-1)/b;j++)min=MIN(min,mini[j]);
			
				for(j=MAX(x,(y-1)/b*b);j<=y-1;j++)min=MIN(min,a[j]);
			}
			
			printf("%d\n",min);
		}
	}
	
	return 0;
}


Measured memory_bytes: 2104
/*s1190073  Rina Sato
File name: prog2a.c
This program is BubbleSort program.
*/

#include<stdio.h>
int main(void){
  int N,A[100],i,j,count=0,temp=0;
  
  scanf("%d",&N);
  for(i = 0 ; i < N ; i++){
    scanf("%d",&A[i]);
  }

  /*compare neighbor figures*/
  for(i = 0 ; i < N ; i++){
    for(j = N-1 ; j > i ; j--){
      if(A[j] < A[j-1]){ /*If left figure is smaller than right figure, change places*/
	temp = A[j]; 
	A[j] = A[j-1];
	A[j-1] = temp;
	count++; /*count a number of exchange*/
      }
    }
  }
  for(j = 0 ; j < N ; j++){
    printf("%d",A[j]);
    if(j < N-1){ /*make space between figures*/
      printf(" ");
    }  
  }
  printf("\n%d\n",count);
  return 0;
}

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

using namespace std;

#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define REV(i,n) for(ll (i) = (n) - 1;(i) >= 0;--i)
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {REP(WW,n)cerr << v[WW] << ' ';cerr << endl << endl;}
#define SHOW2d(v,WW,HH) {REP(W_,WW){REP(H_,HH)cerr << v[W_][H_] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 998244353

typedef long long ll;
typedef pair<ll,ll> P;

ll a[20];

ll dfs(int l, int r, int cl, int cr){
	if(r - l == 1){
		return 0;
	}
	ll ret = LLINF;
	for(int i = l + 1;i < r;i++){
		ret = min(ret, dfs(l, i, cl, cl + cr) + dfs(i, r, cl + cr, cr) + (cl + cr) * a[i]);
	}
	return ret;
}

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	int n;cin >> n;
	REP(i, n)cin >> a[i];
	cout << dfs(0, n-1, 1, 1) + a[0] + a[n-1] << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <map>
#define ull unsigned long long
#define ll long long
using namespace std;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int k,t,a[110];
    cin >> k >> t;
    for(int i=0;i<t;i++){
        cin >> a[i];
    }
    sort(a,a+t);
    cout << max(a[t-1]-1-(k-a[t-1]),0) << endl;

    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
using namespace std;
int main() {
	int N, K;
	scanf("%d %d", &N, &K);
	long long H[N], ans = 0;
	for (int i = 0; i < N; ++i) scanf("%lld", &H[i]);
	sort(H, H + N);
	for (int i = 0; i < N - K; ++i) ans += H[i];
	printf("%lld", ans);
	return 0;
}

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

struct UnionFind{
    //par[i] : iの親
    vector <int> par;
    //初期化（全てのノードが根）
    UnionFind(int N) : par(N){
        for(int i=0;i<N;i++)par[i]=i;
    }
    //xの根を見つける
    int root(int x){
        if(par[x]==x)return x;
        return par[x] = root(par[x]);
    }
    //x,yが同じ集合に属するか
    bool same(int x,int y){
        return root(x)==root(y);
    }
    //x,yが別の集合なら連結
    void unite(int x,int y){
        if(root(x)==root(y))return;
        par[root(x)]=root(y);
    }
};

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;
}
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define INF 999999999

    /*Solve*/

int main(){
    int n,m;
    cin >> n >> m;
    int p[100010];
    rep(i,n)cin >> p[i];
    int x[100010];
    int y[100010];
    rep(i,m)cin >> x[i] >> y[i];
    UnionFind tree(n);  //初期化
    
    rep(i,m)tree.unite(x[i]-1,y[i]-1);  //グラフの連結
    int cnt=0;
    rep(i,n)if(tree.same(p[i]-1,i))cnt++;
    
    cout << cnt << endl;
    
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
int a[10],n,t;
int calc(int x)
{
	if(x<400) return 1;
	if(x<800) return 2;
	if(x<1200) return 3;
	if(x<1600) return 4;
	if(x<2000) return 5;
	if(x<2400) return 6;
	if(x<2800) return 7;
	if(x<3200) return 8;
	return 9;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&t);
		int x=calc(t);
		a[x]++;
	}
	int ans=0;
	for(int i=1;i<=8;i++)
	if(a[i]) ++ans;
	printf("%d %d",max(ans,1),ans+a[9]);
	return 0;
 } 

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>
using namespace std;

int main() {
	//string s[100], res = "";
	//int N, M;
	//int a[60], b[60], res[60] = { 0 };
	//string S;
	int A,B, X;
	//int m[110];

	cin >> A >> B >> X;

	//int y = 700;
	/*for (int i = 0; i < N; ++i) {
		cin >> m[i];
	}
	for (int i = 0; i < N; ++i) {
		X -= m[i];
	}
	sort(m, m + N);
	int res = N;
	res += X / m[0];
	*/

	string res = "NO";

	if (A <= X && X <= (A + B)) {
		res = "YES";
	}
	cout << res << endl;
	return 0;

}


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

int main(){
  int n,digit;
  cin >>n;
  int N = n;
  while(N>0){
    digit += N%10;
    N /= 10;
  }
  if(n%digit == 0) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 256
fn solve() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };
    let h: usize = sc.read();
    let w: usize = sc.read();
    let n: usize = sc.read();
    let result = if h >= w {
        (n + h - 1) / h
    } else {
        (n + w - 1) / w
    };
    println!("{}", result);
}

fn main() {
    std::thread::Builder::new()
        .stack_size(64 * 1024 * 1024) // 64MB
        .spawn(|| solve())
        .unwrap()
        .join()
        .unwrap();
}

//snippet from kenkoooo
pub struct Scanner<R> {
    stdin: R,
}

impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn read_line(&mut self) -> String {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b'\n' || b == b'\r')
            .take_while(|&b| b != b'\n' && b != b'\r')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }

    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


Measured memory_bytes: 8572
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
 string n;
 cin>>n;
 if(n[0]==n[1]&&n[1]==n[2])
 cout<<"Yes"<<endl;
 else if(n[1]==n[2]&&n[3]==n[2])
 cout <<"Yes"<<endl;
 else 
 cout<<"No"<<endl;
}


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

#define INF 0x7fffffff
#define ll	long long

int main() {
	ll		c,i,j,k,kk,n,m,x,y,ans = 0;

	cin >> n >> k;
	ans = n % k;
	ans = min(ans , k-ans);

	cout << ans << endl;


}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
const int mod=1e9+7;

long modpow(long x,long p){
    long res=1;
    while(p){
        if(p&1) res = res*x%mod;
        x=x*x%mod;
        p>>=1;
    }
    return res;
}

long C(int n, int r) {
    long mul=1;
    long div=1;
    for(int i=0;i<r;i++){
        mul = mul*(n-i)%mod;
        div = div*(i+1)%mod;
    }
    div = modpow(div,mod-2);
    return mul*div%mod;
}


int main(){
    long n,m,k;
    cin >> n >> m >> k;

    long ans=0;
    for(int i=1;i<m;i++)
        ans=(ans+(m-i)*i%mod*n*n%mod)%mod;

    for(int i=1;i<n;i++)
        ans=(ans+(n-i)*i%mod*m*m%mod)%mod;
    
    ans*=C(n*m-2,k-2);
    ans%=mod;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define per(i, a, b) for (int i = a; i >= b; i--)
using namespace std;

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

template <typename _T>
inline void read(_T &f) {
	f = 0; _T fu = 1; char c = getchar();
	while (c < '0' || c > '9') { if (c == '-') { fu = -1; } c = getchar(); }
	while (c >= '0' && c <= '9') { f = (f << 3) + (f << 1) + (c & 15); c = getchar(); }
	f *= fu;
}

template <typename T>
void print(T x) {
	if (x < 0) putchar('-'), x = -x;
	if (x < 10) putchar(x + 48);
	else print(x / 10), putchar(x % 10 + 48);
}

template <typename T>
void print(T x, char t) {
	print(x); putchar(t);
}

const int N = 2005, md = 1e9 + 7;

inline int add(int x, int y) {
	x += y;
	if (x >= md) x -= md;
	return x;
}

inline void addx(int &x, int y) {
	x += y;
	if (x >= md) x -= md;
}

inline int sub(int x, int y) {
	x -= y;
	if (x < 0) x += md;
	return x;
}

inline void subx(int &x, int y) {
	x -= y;
	if (x < 0) x += md;
}

inline int mul(int x, int y) { return 1ll * x * y % md; }

inline int fpow(int x, int y) {
	int ans = 1;
	while (y) {
		if (y & 1) ans = mul(ans, x);
		y >>= 1; x = mul(x, x);
	}
	return ans;
}

int f[N * 2][N][2], s[N];
int n, m, k, ans;

int main() {
	read(n); read(m); read(k);
	f[0][0][0] = 1;
	for (int i = 1; i <= (n + m - 1) / (k - 1); i++) {
		for (int j = 0; j <= n; j++) f[i][j][0] = s[j] = add(f[i - 1][j][0], f[i - 1][j][1]);
		for (int j = 1; j <= n; j++) addx(s[j], s[j - 1]);
		for (int j = 0; j <= n; j++) {
			int det = 0;
			if (j >= k) det = s[j - k];
			if (j) f[i][j][1] = sub(s[j - 1], det);
		}
		int all = i * (k - 1) + 1;
		for (int j = 1; j <= n; j++) {
			if (j % (k - 1) == n % (k - 1) && (all - j) % (k - 1) == m % (k - 1) && all - j <= m) {
				addx(ans, f[i][j][1]);
			}
		}
	}
	print(ans, '\n');
	return 0;
}

Measured memory_bytes: 66160
#include <algorithm>
#include <functional>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <bitset>
#include <climits>

#define all(c) (c).begin(), (c).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define pb(e) push_back(e)
#define mp(a, b) make_pair(a, b)
#define fr first
#define sc second

const int INF=100000000;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
using namespace std;
typedef pair<int ,int > P;
typedef long long ll;

const int MAX_N = 1e9+9;
vector<int> ans;

bool ok(int a) {
    while(a) {
        if(a%10 == 4 || a%10 == 6) return false;
        a /= 10;
    }
    return true;
}

int n;
string s[] = {"0", "1","2","3","5","7","8","9"};
void hoge() {
    ans.reserve(100000);
    rep(i,101) {
        if(!i) continue;
        if(ok(i)) ans.pb(i);
        // if(log10(i) == floor(log10(i))) 
    }
    cout<<endl;
    rep(i,ans.size()) {
        // if((i+1)%8==0)
        cout<<i+1<<" "<<ans[i]<<endl;
    }

}

int main() {

    while(cin>>n) {
        if(!n) break;
        string ans;
        while(n) {
            ans += s[n%8];
            n>>=3;
        }
        reverse(all(ans));
        cout<<ans<<endl;


    }

    return 0;
}

Measured memory_bytes: 1204
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
MOD = 10**9+7

a,b,c = map(int,input().split())
s = set([a,b,c])
print(len(s))

Measured memory_bytes: 3316
from itertools import product
n=int(input())
fs=[list(map(int,input().split())) for _ in range(n)]
ps=[list(map(int,input().split())) for _ in range(n)]
ans=-float('inf')
for b in product((0,1),repeat=10):
    if sum(b)==0:
        continue
    v=0
    for f,p in zip(fs,ps):
        cnt=sum([a&b for a,b in zip(b,f)])
        v+=p[cnt]
    ans=max(ans,v)
print(ans)


Measured memory_bytes: 9188
#include<bits/stdc++.h>
using namespace std;
int n,b[105];
int ans;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n-1;++i)
	    scanf("%d",&b[i]);
	for(int i=2;i<=n-1;++i)
	    ans+=min(b[i-1],b[i]);
	ans+=b[1]+b[n-1];
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 3804
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = (0); i < (n); ++i)
#define ALL(obj) (obj).begin(), (obj).end()
#define DEBUG(val) cout << #val << " : " << val << endl
#define MOD 1000000007

int main() {
  int n;
  int a[10005];
  int b[10005];

  cin >> n;
  REP(i, n) { cin >> a[i]; }
  REP(i, n) { cin >> b[i]; }

  ll a_cnt = 0;
  ll b_cnt = 0;
  REP(i, n) {
    if (a[i] < b[i]) {
      int cnt = (b[i] - a[i] + 1) / 2;
      a_cnt += cnt;
      a[i] += 2 * cnt;
    }
  }
  REP(i, n) {
    if (b[i] < a[i]) {
      int cnt = a[i] - b[i];
      b_cnt += cnt;
    }
  }

  if (b_cnt <= a_cnt) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 3720
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N,M;cin >> N >> M;
  vector<int> a(60);
  vector<int> b(60);
  for(int i=0;i<M;++i){
		cin >> 	a.at(i) >> b.at(i);
      }
  for(int i=1;i<=N;++i){
    int count=0;
     for(int j=0;j<M;j++){
      if(a.at(j)==i){
      count++;
      }
      if(b.at(j)==i){
      count++;
      }
     }
    cout << count <<endl; 
  }
}

Measured memory_bytes: 256
// I SELL YOU...! 
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<chrono>
#include<iomanip>
#include<map>
#include<set>
#define MAX_N 1100
#define INF 1000000000000
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
vector<ll> G[MAX_N];
bool used[MAX_N];
bool can;
int nx[MAX_N];
ll d[MAX_N][MAX_N];
ll pre[MAX_N][MAX_N];
void init_io(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << setprecision(10);
}
void f(int s){
  priority_queue<P,vector<P>,greater<P>> que;
  que.push(P(0,s));
  d[s][s] = 0;
  while(!que.empty()){
    P tmp = que.top();
    que.pop();
    ll v=tmp.second,dis=tmp.first;
    if(d[s][v]<dis){
      continue;
    }
    d[s][v] = dis;
    for(auto nv:G[v]){
      if(d[s][nv]>d[s][v]+1){
        d[s][nv] = d[s][v]+1;
        pre[s][nv] = v;
        que.push(P(d[s][nv],nv));
      }
    }
  }
}
vector<ll> path(int s,int t){
  vector<ll> res;
  for(;t!=-1;t=pre[s][t]){
    res.push_back(t);
  }
  reverse(res.begin(),res.end());
  return res;
}
signed main(){
  init_io();
  ll n,m,a,b,best=INF,st=0,en=0;
  vector<ll> ans0,ans1;
  cin >> n >> m;
  can = false;
  for(int i=0;i<m;i++){
    cin >> a >> b;
    a--;
    b--;
    G[a].push_back(b);
  }
  fill(d[0],d[MAX_N],INF);
  fill(pre[0],pre[MAX_N],-1);
  for(int i=0;i<n;i++){
    f(i);
  }
  for(int i=0;i<n;i++){
    for(int j=i+1;j<n;j++){
      if(d[i][j]+d[j][i]<best){
        st = i;
        en = j;
        best = d[i][j]+d[j][i];
      }
    }
  }
  if(best==INF){
    cout << "-1\n";
  }else{
    ans0 = path(st,en);
    ans1 = path(en,st);
    ll size = ans0.size()+ans1.size();
    size-=2;
    cout << size<<endl;
    for(int i=0;i<ans0.size();i++){
      cout << ans0[i]+1<<endl;
    }
    for(int i=1;i<(ll)ans1.size()-1;i++){
      cout << ans1[i]+1<<endl;
    }
  }
}


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

using namespace std;
int result(int arr[3][3],int b[],int n)
{
  	if(n<3)
      	return 0;
    for(int k=0;k<n;k++)
     for(int i=0;i<3;i++)
      for(int j=0;j<3;j++)
        if(b[k]==arr[i][j])
            arr[i][j]=0;
         
    for(int i=0;i<3;i++) //row
        if(arr[i][0]==0 && arr[i][1]==0 && arr[i][2]==0)
            return 1;
    for(int i=0;i<3;i++) //column
        if(arr[0][i]==0 && arr[1][i]==0 && arr[2][i]==0)
           	return 1;
    if(arr[0][0]==0 && arr[1][1]==0 && arr[2][2]==0)
            return 1;
    else if(arr[0][2]==0 && arr[1][1]==0 && arr[2][0]==0)
            return 1;
 	return 0;
}
int main()
{
    int arr[3][3];
    int flag=0;
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            cin >> arr[i][j];
        
    int n=1;
    cin >> n;
    int b[n];
    for(int i=0;i<n;i++)
        cin >> b[i];
  	flag = result(arr,b,n);
    
    if(flag==1)
        cout << "Yes";
    else
        cout << "No";
        
    return 0;
        
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <iomanip>
#include <queue>
#include <climits>

int main(){
    long a;
    std::cin >> a;
    std::cout << a+a*a+a*a*a << std::endl;
    return 0;
}

Measured memory_bytes: 3624
#include<stdio.h>

int main(void){
	int m,f,r=0;
	
	while(1){
		scanf("%d %d %d",&m,&f,&r);
		if((m==-1)&&(f==-1)&&(r==-1))break;
		if((m==-1)||(f==-1))printf("F\n");
		else if((m+f)>=80)printf("A\n");
		else if(((m+f)>=65)&&((m+f)<80))printf("B\n");
		else if(((m+f)>=50)&&((m+f)<65))printf("C\n");
		else if(((m+f)>=30)&&((m+f)<50)){
			if(r>=50)printf("C\n");
			else printf("D\n");
		}else printf("F\n");
	}
	return 0;
}



Measured memory_bytes: 2032
gets
card_set = []

for i in ["S","H","C","D"] do
    for j in 1..13 do
        s = [i,j.to_s].join(" ")
        card_set.push(s)
    end
end

while line=gets do
    card_set.delete(line.chomp)
end

for i in card_set do
    puts i
end


Measured memory_bytes: 6868
#include <bits/stdc++.h>
typedef long long LL;
#define SORT(c) sort((c).begin(),(c).end())

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

using namespace std;
int main(void)
{
  REP(i,3){
    int h[2],m[2],s[2];
    REP(j,2) cin >> h[j] >> m[j] >> s[j];
    REP(j,2){
      m[j]+=h[j]*60;
      s[j]+=m[j]*60;
    }
    s[1]-=s[0];
    cout << s[1]/60/60 << ' ' << s[1]/60%60 << ' ' << s[1]%60 << endl;
  }
  return 0;
}

Measured memory_bytes: 3040
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;

namespace MyProject
{
    class Program
    {
        static void Main(string[] args)
        {
#if Local
            var sw = new Stopwatch();
            sw.Start();
            Console.SetIn(new StreamReader("input.in"));
#endif

            var solver = new Solver();
            solver.Solve();
#if Local
            Console.WriteLine($"{sw.ElapsedMilliseconds}ms");
#endif
        }
    }

    class Solver
    {
        public void Solve()
        {
            var S = Console.ReadLine();
            var ans = S.Select(x => 'x').ToArray();
            Console.WriteLine(ans);
        }
    }
}


Measured memory_bytes: 13396
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

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

P A[500005];

bool compare_y(P a, P b) {
	return a.second < b.second;
}

int closest_pair(P *a, int n) {
	if(n <= 1) return INF;
	int m = n / 2;

	int x = a[m].first;
	int d = min(closest_pair(a, m), closest_pair(a + m, n - m));
	inplace_merge(a, a + m, a + n, compare_y);

	vector<P> b;
	rep(i, n) {
		if(abs(a[i].first - x) >= d) continue;

		rep(j, b.size()) {
			int x = a[i].first - b[b.size() - 1 - j].first;
			int y = a[i].second - b[b.size() - 1 - j].second;

			if(y >= d) break;
			d = min(d, x * x + y * y);
		}
		b.push_back(a[i]);
	}

	return d;
}

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

	rep(i, n) {
		cin >> A[i].first >> A[i].second;
	}

	cout << closest_pair(A, n) << endl;

	return 0;
}

Measured memory_bytes: 10696
import java.util.Iterator;
import java.util.Map.Entry;
import java.util.Scanner;
import java.util.SortedMap;
import java.util.SortedSet;
import java.util.TreeMap;
import java.util.TreeSet;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		SortedMap<String, SortedSet<Integer>> index = new TreeMap<String, SortedSet<Integer>>();
		while (in.hasNext()) {
			String str = in.next();
			SortedSet<Integer> pages;
			if (index.containsKey(str)) {
				pages = index.get(str);
			} else {
				pages = new TreeSet<Integer>();
			}
			int page = in.nextInt();
			pages.add(page);
			index.put(str, pages);
		}
		for (Entry<String, SortedSet<Integer>> idx : index.entrySet()) {
			System.out.println(idx.getKey());
			Iterator<Integer> iterator = idx.getValue().iterator();
			while (iterator.hasNext()) {
				System.out.print(iterator.next());
				if (iterator.hasNext()) {
					System.out.print(' ');
				}
			}
			System.out.println();
		}
	}
}

Measured memory_bytes: 12000
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()

for i in range(1, int(N**0.5 + 4)):
	if i**2 > N:
		print((i-1)**2)
		break


Measured memory_bytes: 5200
//  cout << char(i+48) << endl;//なぜかaは47と得る時がある。+48で出力もaにできる。
//  cout << char(97) << endl;//アスキーコードでaを出力
// sort(b.begin(), b.end());//bという配列を小さい方からソート
// reverse(b.begin(), b.end());//bという配列をリターン
// 10桁でdouble出力するパターン１ 
// printf("%.10f\n", ma);
// 10桁でdouble出力するパターン２
//cout << fixed << setprecision(10);
//  cout << ma << endl;

/*01 02 03 12 13 23　と６回見ていくパターン 
for(int i=0;i<n-1;i++){
  for(int j=i+1;j<n;j++){
    }
  }
*///vector<vector<int>> data(3, vector<int>(4));//int型の2次元配列(3×4要素の)の宣言
//int64_t a;
//10のi乗pow(10, i);
/*string s; stringでの文字列を数字型に変える方法
  cin >> s;
  rep(i,s.size()-2) {
  int a= (s.at(i)-'0')*100 + (s.at(i+1)-'0')*10+ s.at(i+2) -'0';
    */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main(){
  int a,b,c,x;
  cin >> a >> b >> c >> x;
  int count = 0;
  for(int i=0;i<=a;i++){
    for(int j=0;j<=b;j++){
      for(int k=0;k<=c;k++){
        if(500*i + 100*j + 50*k == x)count++;
      }
    }
  }
  cout << count << endl;
}

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

using int32 = int_fast32_t;
using int64 = int_fast64_t;

const int32 INF = 1e9;
const int32 MOD = 1e9+7;
const int64 LLINF = 1e18;

#define YES(n) cout << ((n) ? "YES\n" : "NO\n"  )
#define Yes(n) cout << ((n) ? "Yes\n" : "No\n"  )
#define ANS(n) cout << (n) << "\n"
#define REP(i,n) for(int64 i=0;i<(n);++i)
#define FOR(i,a,b) for(int64 i=(a);i<(b);i++)
#define FORR(i,a,b) for(int64 i=(a);i>=(b);i--)
#define ALL(obj) (obj).begin(),(obj).end()
#define pii pair<int32,int32>
#define pll pair<int64,int64>
#define pb(a) push_back(a)
#define mp make_pair

vector< int64 > divisor(int64 n) {
  vector< int64 > ret;
  for(int64 i = 1; i * i <= n; i++) {
    if(n % i == 0) {
      ret.push_back(i);
      if(i * i != n) ret.push_back(n / i);
    }
  }
  sort(begin(ret), end(ret));
  return (ret);
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int64 n;
  cin >> n;
  int64 ans = divisor(n-1).size() - 1;
  for(int64 d : divisor(n)){
    if(d == 1)continue;
    int64 m = n;
    while(m % d == 0){
      m /= d;
      if((m - 1) % d == 0)ans++;
    }
  }
  ANS(ans);
  return 0;
}

Measured memory_bytes: 384
#include <iostream>
using namespace std;
int main()
{
	int a , b ,c ;
	
	cin>>a>>b>>c ;
	if (a == b )
		cout<<c<<"\n";
	else if (b == c)
		cout<<a<<"\n";
	else if (a == c)
		cout<<b<<"\n";


return 0;
}

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

using lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((lint)(x).size())
#define POW2(n) (1LL << (n))
#define FOR(i, begin, end) for (int i = (begin), i##_end_ = (end); i < i##_end_; i++)
#define IFOR(i, begin, end) for (int i = (end)-1, i##_begin_ = (begin); i >= i##_begin_; i--)
#define REP(i, n) FOR(i, 0, n)
#define IREP(i, n) IFOR(i, 0, n)

int main()
{
    vector<vector<int>> a(3, vector<int>(3)), v(3, vector<int>(3));
    REP(i, 3) {
        REP(j,3){
            cin >> a[i][j];
        }
    }

    lint n;
    cin >> n;
    lint ans=0;
    REP(k,n){
        lint b;
        cin >> b;
        REP(i, 3)
        {
            REP(j, 3)
            {
                if(a[i][j]==b){
                    v[i][j] = 1;
                }
            }
        }
    }

    REP(i, 3)
    {
        REP(j, 3)
        {
            //cout << v[i][j] << " ";
        }
        //cout << "\n";
    }

    REP(i, 3)
    {
        lint sum = 0,sum2=0;
        REP(j, 3)
        {
            sum+=v[i][j];
            sum2 += v[j][i];
        }
        if(sum==3||sum2==3){
            cout << "Yes" << "\n";
            return 0;
        }
    }
    REP(i,3){
        if(v[i][i]==0){
            break;
        }
        if(i==2){
            cout << "Yes"
                 << "\n";
            return 0;
        }
    }
    REP(i, 3)
    {
        if (v[2-i][i] == 0)
        {
            break;
        }
        if (i == 2)
        {
            cout << "Yes"
                 << "\n";
            return 0;
        }
    }

    cout << "No" <<"\n";

    return 0;
}

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

void calc(void){
  while(1){
    int a, b; char op; int o;
    cin >> a >> op >> b;
    switch(op){
      case '+':
        o = a + b;
        break;
      case '-':
        o = a - b;
        break;
      case '*':
        o = a * b;
        break;
      case '/':
        o = a / b;
        break;
      case '?':
        return;
    }
    cout << o << endl;
  }
}

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



Measured memory_bytes: 3068
import java.util.* ;
class Main {
  public static void main(String[] args) {
    
    Scanner scan = new Scanner(System.in);

    String s = scan.next();
    
    int s1 = Integer.parseInt(s.substring(5,7));
   // int s2 =Integer.parseInt(s.substring(8,10));
    if(s1>4){
      System.out.println("TBD");
    }else{
      System.out.println("Heisei");
    }
    
    
    
  }
}

Measured memory_bytes: 22612
#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <string>

using namespace std;
// template for creating 2d vector
template<typename T>
vector<vector<T>> make_2d_vector(size_t rows, size_t cols, T init)
{ return vector< vector<T> >(rows, vector<T>(cols, init)); }


#define debug(x) cout << #x << "==" << x << endl;

const int inf = 2147483647;     // 2^31 - 1

typedef long long ll;


template<typename T>
struct SqrtTree {

  vector<T> data;
  vector<T> bucket;
  T sq;
  T const init = inf;

  SqrtTree( vector<T> const& v) : data(v) {
    int d_size = data.size();
    sq = sqrt( d_size );
    bucket.resize( (d_size + sq - 1) / sq);
    for(int i = 0; i < d_size; i++) {
      if(i % sq == 0) {bucket[i / sq] = data[i]; }
      bucket[i / sq] = min(bucket[i / sq], data[i]);
    }
  }

  // [l, r]
  T query(int l, int r) {
    T res = init; // change here!
    int i = l;
    while(i <= r) {
      if(i % sq == 0 && i + sq <= r) {
        // change here!
        res = min(res,  bucket[ i / sq ]);
        i += sq;
      } else {
        // change here!
        res = min(res, data[i]);
        i++;
      }
    }
    return res;
  }

  void update(int i, T x) {
    // change here!
    data[i] = x;
    // bucket ?????´??°
    bucket[i / sq] = init;
    for(int k = 0; k < sq; k++) {
      int cur_i = (i / sq) * sq + k;
      if( (int)data.size() <= cur_i) { break; }
      bucket[i / sq] = min(bucket[i / sq], data[ cur_i ]);
    }
  }

  void print() {

    int tab = 5;

    for(int i = 0; i < (int)bucket.size(); i++ ) {
      string x;
      if(bucket[i] == init) { x = "I"; }
      else                 { x = to_string(bucket[i]); }
      cout << setw(tab*sq) << x;
    }

    cout << "\n";

    for(int i = 0; i < (int)data.size(); i++ ) {
      string x;
      if(data[i] == init) { x = "I"; }
      else                 { x = to_string(data[i]); }
      cout << setw(tab) << x;
    }

    cout << "\n";
  }

};



int main() {
  ios::sync_with_stdio(false);

  int N, Q;
  cin >> N >> Q;

  vector<ll> data(N, (ll)inf);
  SqrtTree<ll> sqtree(data);

  for(int i = 0; i < Q; i++) {
    ll com, x, y;
    cin >> com >> x >> y;
    // add
    if(com == 0) {
      sqtree.update(x, y);
      // sqtree.print();
    }
    if(com == 1) {
      cout << sqtree.query(x, y) << "\n";
    }

  }

  return 0;
}

Measured memory_bytes: 4388
object Main {
  def main(args: Array[String]): Unit = {
    solve
  }

  def solve(): Unit = {
    val sc = new java.util.Scanner(System.in)

    var n, k = sc.nextInt()
    var ans = 0
    while (n > 0) {
      ans += 1
      n = n / k
    }
    println(ans)
  }
}


Measured memory_bytes: 27336
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define MOD 1000000007
int kaijo[222222];
void init_fact(int x){
	kaijo[0]=1;
	for(int i=1;i<=x;i++){
		kaijo[i]=kaijo[i-1]*i;
		kaijo[i]%=MOD;
	}
}
int modpow(int a,int b){
	if(b==0)return 1;
	if(b%2)return modpow(a,b-1)*a%MOD;
	int memo=modpow(a,b/2);
	return memo*memo%MOD;
}
int comb(int a,int b){
	return kaijo[a]*modpow(kaijo[a-b],MOD-2)%MOD*modpow(kaijo[b],MOD-2)%MOD;
}
int g(int x){
	x=modpow(x,MOD-2);
	return x;
}
signed main(){
    int n,a,b,c,ans=0;
	cin>>n>>a>>b>>c;
	init_fact(200010);
	int A=a*g(a+b)%MOD;
	int B=b*g(a+b)%MOD;
	c=100*g(100-c)%MOD;
	rep(i,n){
		int memo=(modpow(A,n)*modpow(B,i)%MOD+modpow(A,i)*modpow(B,n)%MOD)%MOD*comb(n+i-1,n-1)%MOD;
		ans+=memo*(i+n)%MOD;
		ans%=MOD;
	}
	cout<<ans*c%MOD<<endl;
	return 0;
}


Measured memory_bytes: 1792
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func main() {
	sc.Split(bufio.ScanWords)

	d := nextInt()
	clist := make([]int, 26)
	for i := 0; i < 26; i++ {
		clist[i] = nextInt()
	}
	var slist [366][26]int
	for i := 0; i < d; i++ {
		for j := 0; j < 26; j++ {
			tmp := nextInt()
			//fmt.Println(tmp)
			slist[i][j] = tmp
		}
	}

	tlist := make([]int, d) // Answer
	last := map[int]int{}
	vlist := make([]int, d)

	// 貪欲法
	for i := 0; i < d; i++ {
		bestc := 0
		bestm := 0

		// 26タイプ全て実施
		for todaytype := 0; todaytype < 26; todaytype++ {
			lastbak := last[todaytype]
			last[todaytype] = i + 1

			// 基礎満足度増加計算
			basem := 0
			if i == 0 {
				basem = slist[i][todaytype]
			} else {
				basem = vlist[i-1] + slist[i][todaytype]
			}

			// 満足度低下計算
			teika := 0
			for j := 0; j < 26; j++ {
				teika += clist[j] * (i + 1 - last[j])
			}

			// チャンピオン計算
			basem -= teika
			if bestm < basem {
				//fmt.Printf("Camp Changed: %d at type%d\n", basem, todaytype)
				bestm = basem
				bestc = todaytype
			}

			// 初期化
			last[todaytype] = lastbak
		}

		vlist[i] += bestm
		last[bestc] = i + 1

		tlist[i] = bestc
		//fmt.Printf("--- Day End bestm,bestc = %d,%d\n", bestm, bestc)
	}

	// 出力
	for i := 0; i < d; i++ {
		fmt.Printf("%d\n", tlist[i]+1)
	}

}

// ---- readfunc
func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}
func nextStr() string {
	sc.Scan()
	return sc.Text()
}


Measured memory_bytes: 2068
#include <bits/stdc++.h>
using namespace std;
int arr[25];
int main()
{
 cin.sync_with_stdio(false);
    cin.tie(NULL);

   int t;cin>>t;

   for(int i=0;i<t;i++)
   {
       cin>>arr[i];
   }int cnt=0;
   for(int i=1;i<t-1;i++)
   {
       if(arr[i]>arr[i-1]&&arr[i]<arr[i+1])
        cnt++;
        if(arr[i]<arr[i-1]&&arr[i]>arr[i+1])
        cnt++;

   }
   cout<<cnt;

         return 0;
}


Measured memory_bytes: 256
A, B, C, D = list(map(int, input().split()))
c1 = (A - 1) // C
c2 = B // C
d1 = (A - 1) // D
d2 = B //D
import math
E = (C * D) // math.gcd(C, D)
e1 = (A - 1) // E
e2 = B //E

print(B - A + 1 -(c2 - c1 + d2 - d1 - (e2 - e1)))


Measured memory_bytes: 9148
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)

int main() {
  int n;
  string s;
  cin >> n >> s;

  int ans = 0;

  REP(i, n){
    int cnt = 0;

    for (char c = 'a'; c <= 'z'; ++c) {
      int left = 0, right = 0;

      REP(j, i) {
        if (s[j] == c) left = 1;
      }

      FOR(j, i, n) {
        if (s[j] == c) right = 1;
      }

      if (left && right) cnt++;
    }

    if (ans < cnt) ans = cnt;
  }

  cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
	int n,m,oi=0;
	cin>>n>>m;
	int a[m+1];
	for(int i=1;i<=m;i++){
		cin>>a[i];
		oi+=a[i];
	}
	int sp=n-oi;
	if(sp>=0) cout<<sp<<endl;
	else cout<<"-1"<<endl;
	return 0;
}

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

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

typedef long long ll;

int main() {
	int n;
	while (cin >> n, n) {
		vector<ll> dp(n + 1, 0);
		dp[0] = 1;
		REP(i, n) {
			FOR(j, 1, 3 + 1) {
				if (i + j > n) continue;
				dp[i + j] += dp[i];
			}
		}
		dp[n] = dp[n] % 10 == 0 ? dp[n] / 10 : dp[n] / 10 + 1;
		cout << (dp[n] % 365 == 0 ? dp[n] / 365 : dp[n] / 365 + 1) << endl;
	}
	return 0;
}

Measured memory_bytes: 1192
#define _CRT_SECURE_NO_WARNINGS
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<functional>
#include<iomanip>
#include<iostream>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<utility>
#include<vector>

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

using namespace std;

int main() {
	int N, x[100], y[100], h[100], key;
	map<int, vector<pair<int, int>>> data;
	cin >> N;
	REP(i, N) {
		cin >> x[i] >> y[i] >> h[i];
		if (h[i] != 0) {
			key = i;
		}
	}

	int Cx, Cy, H, ansH;
	bool f = true;
	REP(i, 101) {
		REP(j, 101) {
			f = true;
			H = h[key] + abs(x[key] - i) + abs(y[key] - j);
			FOR(k, 0, N) {
				if (h[k] != max(0, H - abs(x[k] - i) - abs(y[k] - j))) {
					f = false;
				}
			}
			if (f) {
				Cx = i;
				Cy = j;
				ansH = H;
				break;
			}
		}
	}

	cout << Cx << " " << Cy << " " << ansH << endl;

	return 0;
}

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

int main() {
	ll n;
	cin >> n;
	vector<ll> a(n,0), l(n,0), r(n,0);
	rep(i,n) cin >> a[i];
	rep(i,n) {
		ll p = (i+1) + a[i];
		ll q = (i+1) - a[i];
		if (p>=0 && p<=n-1LL) l[p]++;
		if (q>=0 && q<=n-1LL) r[q]++;
	}
	ll ans = 0;
	rep(i,n) ans += l[i]*r[i];
	cout << ans << endl;
	return 0;
}


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

string a[200002];
typedef struct node
{
	string a;
	int b;
}node;
node A[200002];

bool cmp(node x,node y)
{
	if(x.b==y.b) return x.a<y.a;
	return x.b>y.b;
}
int main()
{
	int n; cin>>n;
	map<string,int>Map;
	for(int i=0;i<n;++i)
	{
		cin>>a[i]; 
		Map[a[i]]++;
	}
	auto it = Map.begin();
	int pos = 0;
	for(;it!=Map.end();it++)
	{
		A[pos].a = it->first;
		A[pos].b = it->second;
		pos++;
	}
	sort(A,A+pos,cmp);
	int tmp = A[0].b;
	for(int i=0;i<pos;++i)
	{
		if(A[i].b!=tmp) break;
		cout<<A[i].a<<"\n";
	}
}

Measured memory_bytes: 29952
n = int(input())
V_list = list(map(int, input().split()))

Vdic = [{}, {}]
# 0: even 1: odd
for i in range(len(V_list)):
    v = V_list[i]

    tmp = (i + 1) % 2
    Vdic[tmp][v] = Vdic[tmp].get(v, 0) + 1

even = sorted(Vdic[0].values())
odd = sorted(Vdic[1].values())

ans_even = [(-1, 0)]
ans_odd = [(-2, 0)]
if(len(even) == 1):
    t = max(Vdic[0], key=Vdic[0].get)
    ans_even.append((t, even[0]))
else:
    n1 = even[-1]
    n2 = even[-2]

    f1 = True
    f2 = True
    if(n1 == n2):
        for k, v in Vdic[0].items():
            if(v == n1):
                if(f1 is False and f2 is False):
                    continue
                if(f1 is False):
                    f2 = False
                f1 = False
                ans_even.append((k, v))
    else:
        for k, v in Vdic[0].items():
            if(v == n1 and f1 is True):
                f1 = False
                ans_even.append((k, v))
            if(v == n2 and f2 is True):
                f2 = False
                ans_even.append((k, v))

if(len(odd) == 1):
    t = max(Vdic[1], key=Vdic[1].get)
    ans_odd.append((t, odd[0]))
else:
    n1 = odd[-1]
    n2 = odd[-2]

    f1 = True
    f2 = True
    if(n1 == n2):
        for k, v in Vdic[1].items():
            if(v == n1):
                if(f1 is False and f2 is False):
                    continue
                if(f1 is False):
                    f2 = False
                f1 = False
                ans_odd.append((k, v))
    else:
        for k, v in Vdic[1].items():
            if(v == n1 and f1 is True):
                f1 = False
                ans_odd.append((k, v))
            if(v == n2 and f2 is True):
                f2 = False
                ans_odd.append((k, v))


# print(ans_even, ans_odd)

ans = []
for ke, ve in ans_even:
    for ko, vo in ans_odd:
        if(ke != ko):
            ans.append(n - ve - vo)

print(min(ans))

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

int main(){
  vector<char> a(3);
  vector<char> b(3);
  for(int i = 0; i < 3; i++){
    cin >> a.at(i);
  }
  for(int i = 0; i < 3; i++){
    cin >> b.at(i);
  }
  reverse(a.begin(), a.end());
  if(a == b){
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }
}

Measured memory_bytes: 256