akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define MAXN 	100001
#define LOGMAXN 18
#define int 	long long
using namespace std;

vector<int>adj[MAXN];
int height[MAXN];
int anc[LOGMAXN][MAXN];
int strength[MAXN];
int subtree_strength[MAXN];
void dfs(int u,int p){
	height[u]=height[p]+1;
	anc[0][u]=p;
	subtree_strength[u]=strength[u];
	for(int v:adj[u]){
		if(v==p)continue;
		dfs(v,u);
		subtree_strength[u]+=subtree_strength[v];
	}
}

int LCA(int u,int v){
	if(height[u]<height[v])swap(u,v);
	for(int i=LOGMAXN;i>=0;i--){
		if(height[u]-(1<<i)>=height[v]){
			u=anc[i][u];
		}
	}
	if(u==v)return u;
	for(int i=LOGMAXN;i>=0;i--){
		if(anc[i][u]!=anc[i][v])u=anc[i][u],v=anc[i][v];
	}
	return anc[0][u];
}

signed main(){
	int N;
	cin>>N;
	for(int i=1;i<=N;i++){
		// cin>>strength[i];
		strength[i]=1;
	}
	for(int i=1;i<N;i++){
		int a,b;
		cin>>a>>b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	dfs(1,0);
	for(int i=1;i<LOGMAXN;i++){
		for(int j=1;j<=N;j++){
			anc[i][j]=anc[i-1][anc[i-1][j]];
		}
	}
	int Q;
	// cin>>Q;
	Q=1;
	int A=0,B=0,C=0,D=0;
	while(Q--){
		int u,v;
		// cin>>u>>v;
		u=1,v=N;
		int lca=LCA(u,v);
		int moves=height[u]+height[v]-2*height[lca]-1;
		int u_moves=(moves+1)/2;
		int v_moves=moves/2;
		int u_score=0,v_score=0;
		if(height[u]-height[lca]>u_moves){
			int final_u=u;
			for(int i=LOGMAXN;i>=0;i--){
				if(u_moves>=(1<<i)){
					u_moves-=(1<<i);
					final_u=anc[i][final_u];
				}
			}
			u_score=subtree_strength[final_u];
			v_score=subtree_strength[1]-u_score;
		}
		else{
			int final_v=v;
			for(int i=LOGMAXN;i>=0;i--){
				if(v_moves>=(1<<i)){
					v_moves-=(1<<i);
					final_v=anc[i][final_v];
				}
			}
			v_score=subtree_strength[final_v];
			u_score=subtree_strength[1]-v_score;
		}
		// cerr<<u_score<<" "<<v_score<<endl;
		// if(u_score>=v_score)A++;
		// else C++;
		// B+=u_score;
		// D+=v_score;
		if(u_score>v_score)cout<<"Fennec\n";
		else cout<<"Snuke\n";
	}
	// cout<<A<<" "<<B<<" "<<C<<" "<<D;
	return 0;
}

Measured memory_bytes: 26752
h, w = gets.strip.split.map(&:to_i)
s = h.times.map { gets.strip.split('') }

(1..h).each do |i|
  a = []
  (1..w).each do |j|
    if s[i-1][j-1] != "#"
      bomb = 0
      (i-1..i+1).each do |p|
        (j-1..j+1).each do |q|
          if 1<=p && p<=h && 1<=q && q<=w
            bomb += 1 if s[p-1][q-1] == "#"
          end
        end
      end
      a.push(bomb.to_s)
    else
      a.push("#")
    end
  end
  puts a.join('')
end

Measured memory_bytes: 3964
#include <bits/stdc++.h>
using namespace std;
int a[4][4];
int main(){
  for(int i=0;i<3;i++){
    for(int j=0;j<3;j++){
      cin>>a[i][j];
    }
  }
  int sa_a12,sa_a23;
  sa_a12=a[1][0]-a[0][0];
  sa_a23=a[2][0]-a[1][0];
  if(a[1][1]-a[0][1]!=sa_a12){
    cout<<"No"<<endl;
    return 0;
  }
  if(a[1][2]-a[0][2]!=sa_a12){
    cout<<"No"<<endl;
    return 0;
  }
  if(a[2][1]-a[1][1]!=sa_a23){
    cout<<"No"<<endl;
    return 0;
  }
  if(a[2][2]-a[1][2]!=sa_a23){
    cout<<"No"<<endl;
    return 0;
  }
  int sa_b12,sa_b23;
  sa_b12=a[0][1]-a[0][0];
  sa_b23=a[0][2]-a[0][1];
  if(a[1][1]-a[1][0]!=sa_b12){
    cout<<"No"<<endl;
    return 0;
  }
  if(a[2][1]-a[2][0]!=sa_b12){
    cout<<"No"<<endl;
    return 0;
  }
  if(a[1][2]-a[1][1]!=sa_b23){
    cout<<"No"<<endl;
    return 0;
  }
  if(a[2][2]-a[2][1]!=sa_b23){
    cout<<"No"<<endl;
    return 0;
  }
  cout<<"Yes"<<endl;
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>
#include <string>
#include <map>
#include <deque>
#include <queue>
using namespace std;
typedef long long int lli;
#define urept(soeji, start, n) for (int soeji = start; soeji < n; soeji++)
#define drept(soeji, start, n) for (int soeji = start; soeji > n; soeji--)
int main(void)
{
    int N, T, A;
    cin >> N >> T >> A;
    vector<int> H;
    int tmp;
    for (int i = 0; i < N; i++)
    {
        cin >> tmp;
        H.push_back(tmp);
    }
    int t = 100000000;
    int ti = 0;
    int ans = 0;
    for (int i = 0; i < N; i++)
    {
        ti = 1000 * (T - H[i] * 0.006);
        t = min(t, abs(1000 * A - ti));
        if (t == abs(1000 * A - ti))
        {
            ans = i + 1;
        }
    }
    cout << ans << endl;
    return 0;
}

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

int main() {
  int N;
  cin >> N;
  vector<int> point(N);
  for (int i = 0;i < N; i++) {
    cin >> point.at(i);
  }
  int s = 0;
  sort(point.begin(), point.end());
  reverse(point.begin(), point.end());
  for (int i = 0;i < N; i++) {
    if (i % 2 == 0) s += point.at(i);
    else s -= point.at(i);
  }
  cout << s << endl;
}

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

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

#define FOR(i, n, m) for (ll(i) = (m); (i) < (n); ++(i))
#define REP(i, n) FOR(i, n, 0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll)1e15;

int main()
{
    ll N, K;
    cin >> N >> K;
    string S;
    cin >> S;

    ll L = 0, R = 0;
    ll sum = 0;
    REP(i, N)
    {
        if (i == 0 || S[i - 1] != S[i])
        {
            if (S[i] == 'L')
                L++;
            else
                R++;
        }
        else
        {
            sum++;
        }
    }

    ll f = std::min(L, R);
    ll ans = std::min(N - 1, sum + std::min(f, K) * 2);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 512
N=int(input())
Taro=0
Hanako=0
for i in range(N):
    T,H=map(str,input().split())
    if T<H:
        Hanako+=3
    elif H<T:
        Taro+=3
    else:
        Hanako+=1
        Taro+=1
print(Taro,Hanako)



Measured memory_bytes: 5596
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <cmath>
using namespace std;

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



int main() {
	string s;
	cin >> s;
	if (s[1] == 'B') {
		cout << "ARC";
	}
	else {
		cout << "ABC";
	}
}

Measured memory_bytes: 3572
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;

ulong[10^^5] AS;
int[40] BS;
bool[40] KS;

void main()
{
    auto nk = readln.split.to!(ulong[]);
    auto N = nk[0];
    auto K = nk[1];
    ulong o = 1;

    foreach (i, a; readln.split.to!(ulong[])) {
        AS[i] = a;
        foreach (j; 0..40) {
            BS[j] += ((o<<j) & a) ? 1 : 0;
        }
    }

    foreach (i; 0..40) {
        KS[i] = !!((o<<i) & K);
    }

    ulong ret;
    foreach (i; 0..40) {
        if (!KS[i]) continue;
        ulong x;
        foreach (j; 0..i) {
            if (BS[j] <= N / 2) {
                x |= (o<<j);
            }
        }
        foreach (j; i+1..40) {
            x |= ((o<<j) & K);
        }
        ulong r;
        foreach (a; AS[0..N]) {
            r += a ^ x;
        }
        ret = max(ret, r);
    }

    ulong r;
    foreach (a; AS[0..N]) {
        r += a ^ K;
    }
    ret = max(ret, r);

    writeln(ret);
}

Measured memory_bytes: 5628
import java.util.*;

 class Main {
     static boolean[][] graph = new boolean[8][8];

     public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        
        int a,b;
        for(int i=0;i<M;i++) {
        	a=sc.nextInt();
        	b=sc.nextInt();
        	graph[a-1][b-1]=true;
        	graph[b-1][a-1]=true;
        }
        
        boolean[] visited = new boolean[N];
		for(int i=0;i<N;i++) {
			visited[i]=false;
		}

        visited[0]=true;
        int result = dfs(0,N,visited);
        
        System.out.println(result);
    }
    
    static int dfs(int first, int max, boolean[] visited) {
    	int ret = 0;
    	boolean all_visited = true;
    	for(int i=0;i<max;i++) {
    		if(visited[i]==false) {
    			all_visited=false;    			
    		}
    	}
    	if (all_visited) {
    		return 1;
    	}
    	
    	for(int i=0;i<max;i++) {
    		if(graph[first][i]==false) {
    			continue;
    		}
    		if(visited[i]==true) {
    			continue;
    		}
    		visited[i]=true;
			ret += dfs(i,max,visited);
			visited[i] = false;
    	}
    	return ret;
    }
}

Measured memory_bytes: 23764
N = int(input())
max = 0
ans = 1

for i in reversed(range(0, N+1)):
  if i % 2 == 0:
    tmp = i
    cnt = 0
    for _ in range(N):
      if i % 2 == 0 and i != 0:
        i = i // 2
        cnt += 1
    if max < cnt:
      max = cnt
      ans = tmp
        
print(ans)

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

int main()
{
    string s;
    cin >> s;
    if (s == "SUN") cout << 7 << endl;
    if (s == "MON") cout << 6 << endl;
    if (s == "TUE") cout << 5 << endl;
    if (s == "WED") cout << 4 << endl;
    if (s == "THU") cout << 3 << endl;
    if (s == "FRI") cout << 2 << endl;
    if (s == "SAT") cout << 1 << endl;
    return 0;
}


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

#define rep(i,n) for(int i = 0; i < n; ++i)
#define X first
#define Y second
#define MP(x,y) make_pair(x,y)
using namespace std;

int main(void){
  int d, w;

  while (cin >> d >> w && d) {

    vector<int> vf(d);
    vector<int> vs(w);

    rep (i, d) cin >> vf[i];
    rep (i, w) cin >> vs[i];

    sort(vf.begin(), vf.end());
    sort(vs.begin(), vs.end());

    int vf_i = 0;
    int vs_i = 0;
    int ans = 0;

    while (vf_i < vf.size() && vs_i < vs.size()) {
      if (vf[vf_i] > vs[vs_i]) {
        ans += vs[vs_i];
        vs_i++;
      }
      else if (vf[vf_i] < vs[vs_i]) {
        ans += vf[vf_i];
        vf_i++;
      }
      else {
        ans += vs[vs_i];
        vs_i++;
        vf_i++;
      }
      // cout << vf_i << '-' << vs_i << endl;
    }
    // cout << "end" << endl;

    for (; vs_i<vs.size(); vs_i++) ans += vs[vs_i];
    for (; vf_i<vf.size(); vf_i++) ans += vf[vf_i];

    cout << ans << endl;
  }
}

Measured memory_bytes: 3044
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(v) v.begin(), v.end()
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; }

#include <bits/stdc++.h>
using namespace std;

int main(){
  int n;
  cin>>n;
  
  double x;
  string s;
  double ans=0;
  rep(i,n){
    cin>>x>>s;
    if(s=="JPY") ans+=x;
    else ans+=x*380000;
  }
  
  cout<< fixed << setprecision(15)<<ans<<endl;
    
  return 0;
}

Measured memory_bytes: 3796
class UnionFind():
    # 各要素の親要素の番号を格納するリスト
    # 要素が根（ルート）の場合は-(そのグループの要素数)を格納する
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    # 要素xが属するグループの根を返す
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    # 要素xが属するグループと要素yが属するグループとを併合する
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    # 要素xが属するグループのサイズ（要素数）を返す
    def size(self, x):
        return -self.parents[self.find(x)]

    # 要素x, yが同じグループに属するかどうかを返す
    def is_same(self, x, y):
        return self.find(x) == self.find(y)

    # 要素xが属するグループに属する要素をリストで返す
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    # すべての根の要素をリストで返す
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    # グループの数を返す
    def group_count(self):
        return len(self.roots())

    # {ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    # ルート要素: [そのグループに含まれる要素のリスト]を文字列で返す (print()での表示用)
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def resolve():
    N, M = map(int, input().split())
    E = [[int(x) - 1 for x in input().split()] for _ in range(M)]

    ans = 0
    for i in range(M):
        uf = UnionFind(N)
        # i番目の辺を除くすべての辺をつないぐ
        for j, e in enumerate(E):
            if i == j:
                continue
            uf.union(e[0], e[1])
        # i番目の辺を除くすべての辺をつないだあとで、i番目の辺(a, b)がつながるかを判定する
        # つながらないならば、そのi番目の辺は橋である
        a, b = E[i]
        if not uf.is_same(a, b):
            ans += 1
    print(ans)

if __name__ == "__main__":
    resolve()

Measured memory_bytes: 3188
import java.util.*;

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

		String s=sc.next();
		String t=sc.next();

		String a[]=s.split("");
		String b[]=t.split("");


		int count=0;
		for(int i=0;i<3;i++){
			if(a[i].equals(b[i])){
				count++;
			}
		}

		System.out.println(count);


	}
}


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

int main(){
  int n, m;
  cin >> n >> m;
  vector<int> s(n, 0);
  int k;
  rep(i, m){
    cin >> k;
    rep(j, k){
      int a;
      cin >> a;
      s[a-1] |= (1 << i);
    }
  }
  int p;
  rep(i, m){
    int b;
    cin >> b;
    p |= (b << i);
  }
  int ans = 0;
  int l = 0;
  rep(i, (1 << n)){
    l = 0;
    rep(j, n){
      if (i & (1 << j)){
        l ^= s[j];
      }
    }
    if (l == p) ans++;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define PI 3.14159265358979323846
#define int long long
constexpr long long INF = numeric_limits<long long>::max() / 2;
constexpr int MOD = 1000000007;
//constexpr int MOD = 998244353;
using Graph = vector<vector<int>>;


int op(int a,int b){
    return max(a,b);
}
int e(){
    return -1;
}
int target;

bool f(int v){
    return v<target;
}

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

    int N,Q;
    cin>>N>>Q;
    int A[N];
    segtree<int,op,e> seg(N);
    rep(i,N){
        cin>>A[i];
        seg.set(i,A[i]);
    }

    rep(i,Q){
        int t,x,v;
        cin>>t>>x>>v;
        if(t==1){
            x--;
            seg.set(x,v);
        }else if(t==2){
            x--;
            int ans=seg.prod(x,v);
            cout<<ans<<endl;
        }else{
            x--;
            target=v;
            cout<<seg.max_right<f>(x)+1<<endl;

        }
    }


}


Measured memory_bytes: 9028
#include <stdio.h>

int main(){
    int N, K, x, i, n1, n2, ans=0;

    scanf("%d %d", &N, &K);

    for(i=0; i<N; i++){
        scanf("%d", &x);
        
        n1 = x * 2;
        n2 = (K-x) * 2;
        if(n1 < n2)
            ans += n1;
        else
            ans += n2;
    }

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

    return 0;
}

Measured memory_bytes: 128
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <iostream>
#include <algorithm>
#include <set>

using namespace std;

const int INF = (int)1e9;
const int SIZE = 1000000;

int s[SIZE],s_sort[SIZE];
multiset<int> leader;
int n,q;

int calc(int x){
  int l=0,r=1000000100,mid;
  int p,last;

  while(l<r){
    p = 0;
    mid = (l+r)/2;
    multiset<int>::iterator it = leader.begin(),it2;
    it2 = it;
    last = -1;
    
    for(;it!=leader.end();it++){
      if(last == *it) continue;
      p += (int)(upper_bound(s_sort,s_sort+n,*it)
		 -lower_bound(s_sort,s_sort+n,max(*it-mid,last+1)));
      //cerr << *it << "-" << max(*it-mid,last+1) << ":" << p <<  endl;
      last = *it;
    }

    //cerr << mid << ":" << x << " " <<  n-p << endl;
    if(n-p <= x){
      r = mid;
    }else{
      l = mid+1;
    }
  }

  return l;

}

int main(){

  scanf("%d%d",&n,&q);

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

  sort(s_sort,s_sort+n);

  for(int i=0;i<q;i++){
    string str;
    int a;

    cin >> str >> a;
    a--;

    if(str[0]=='A'){
      leader.insert(s[a]);
    }else if(str[0]=='R'){
      for(multiset<int>::iterator it = leader.begin();it!=leader.end();it++){
	if(*it == s[a]){
	  leader.erase(it);
	  break;
	}
      }
    }else{
      int ans = calc(a+1);
      if(ans <= 1000000000)
	cout << ans << endl;
      else
	cout << "NA" << endl;
    }
  }
  
  return 0;
}

Measured memory_bytes: 9088
#include <bits/stdc++.h>
using namespace std;
#define GET_MACRO(_1, _2, _3, NAME, ...) NAME
#define _repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define _rep(i,n) _repl(i,0,n)
#define rep(...) GET_MACRO(__VA_ARGS__, _repl, _rep)(__VA_ARGS__)
#define mp(a,b) make_pair((a),(b))
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#define fi first
#define se second
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
void _dbg(string){cout<<endl;}
template<class H,class... T> void _dbg(string s,H h,T... t){int l=s.find(',');cout<<s.substr(0,l)<<" = "<<h<<", ";_dbg(s.substr(l+1),t...);}
template<class T,class U> ostream& operator<<(ostream &o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream &o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

#define INF 1120000000

int main(){
  int n,k;
  cin>>n>>k;
  vector<long> a(n),b(n);
  rep(i,n) cin>>a[i]>>b[i];

  long ans = 0;
  rep(i,n) if( (a[i]|k) == k ) ans += b[i];

  rep(i,30) if( (k>>i) % 2){
    int mask = ((k>>(i+1))<<(i+1)) + (1<<i)-1;//dbg(bitset<20>(mask),i);
    long tmp = 0;
    rep(j,n) if( (a[j]|mask)==mask )tmp += b[j];
    ans = max(ans, tmp);
  }

  cout << ans << endl;

  return 0;
}


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

#define mms(a,n) memset(a,0,sizeof((a)[0])*(n))
#define mmp(a,b,n) memcpy(a,b,sizeof((b)[0])*(n))
#define lowbit(x) ((x)&-(x))
#define pb push_back
#define fi first
#define se second
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define fo(i,l,r) for(register int i=l,_lim_=r;i<=_lim_;i++)
#define fd(i,r,l) for(register int i=r,_lim_=l;i>=_lim_;i--)
#define fos(i,l,r,d) for(register int i=l,_lim_=r;i<=r;i+=d)
#define fol(i,l,r) for(register ll i=l,_lim_=r;i<=_lim_;i++)
#define fdl(i,r,l) for(register ll i=r,_lim_=l;i>=_lim_;i--)
#define fosl(i,l,r,d) for(register ll i=l,_lim_=r;i<=r;i+=d)
#define Clear(a) memset(a,0,sizeof(a))
#define Copy(a,b) memcpy(a,b,sizeof(b))
#define ALL(v) v.begin(),v.end()
#define SZ(v) ((int)v.size())

using namespace std;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ldb;
typedef double db;
typedef pair<int,int> pi;
typedef vector<int> VI;
typedef vector<VI> VII;

const int N=16666,P=998244353;

struct Div{
	ull m,x;
	int s;
	Div(){}
	Div(ull mo):m(mo){
		s=__lg(mo-1);
		x=((__uint128_t(1)<<(s+64))+m-1)/m;
	}
	friend ull operator/(ull a,Div d){
		return ((__uint128_t(a)*d.x)>>d.s)>>64;
	}
	friend ull operator%(ull a,Div d){
		return a-a/d*d.m;
	}
}mod(P);

uint fpow(uint a,int t){
	uint r(1);
	for(;t;t>>=1,a=(ull)a*a%mod)if(t&1)r=(ull)r*a%mod;
	return r;
}

int n,m,k;
uint fac[N],ifac[N],inv[N],tx[N],ty[N],tz[N],dp[N],ret;
uint *ww[20],*iww[20],pol[N<<2],*pl=pol;
void init(int n){
	int i,p,l;uint w;
	for(l=2,p=0;l<=n;l<<=1,p++){
		ww[p]=pl;w=fpow(3,(P-1)/l);
		for(i=*pl=1;i<l>>1;i++)pl[i]=(ull)pl[i-1]*w%mod;pl+=l>>1;
		iww[p]=pl;w=fpow(w,P-2);
		for(i=*pl=1;i<l>>1;i++)pl[i]=(ull)pl[i-1]*w%mod;pl+=l>>1;
	}
}
void fft(uint a[],int n,int dft){
	int i,j,k,l,p;uint t,*w;
	for(i=1,j=n>>1;i<n-1;i++){
		if(i<j)swap(a[i],a[j]);
		for(k=n>>1;(j^=k)<k;k>>=1);
	}
	for(l=2,p=0;l<=n;l<<=1,p++){
		w=dft==1?ww[p]:iww[p];
		for(j=0,i=l>>1;j<n;j+=l)for(k=0;k<i;k++){
			uint&y=a[j+k];
			t=(ull)a[j+k+i]*w[k]%mod;
			(a[j+k+i]=y+P-t)<P?:a[j+k+i]-=P; 
			(y+=t)<P?:y-=P;
		}
	}
	if(dft==-1)for(i=0,t=fpow(n,P-2);i<n;i++)a[i]=(ull)a[i]*t%mod;
}

uint C(int n,int m){
	if(n<m)return 0;
	return (ull)fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
 
int main(){
	scanf("%d%d",&n,&m);
	fac[0]=fac[1]=ifac[0]=ifac[1]=inv[1]=1;
	fo(i,2,(n<<1)+2){
		fac[i]=(ull)fac[i-1]*i%mod;
		inv[i]=P-(ull)(P/i)*inv[P%i]%mod;
		ifac[i]=(ull)ifac[i-1]*inv[i]%mod;
	}
	dp[0]=1;
	for(k=1;k<=n<<1;k<<=1);
	init(k);
	fo(i,1,m){
		mms(tx,k);mms(ty,k);
		fo(j,0,n)tx[j]=(ull)dp[j]*ifac[j]%mod;
		fo(j,1,n)ty[j]=ifac[j+2];
		fft(tx,k,1);fft(ty,k,1);
		fo(j,0,k-1)tz[j]=(ull)tx[j]*ty[j]%mod;
		fft(tz,k,-1);
		fo(j,0,k-1)dp[j]=((ull)dp[j]*((j+1)*j/2+1)+(ull)tz[j]*fac[j+2])%mod;
	}
	fo(i,0,n)ret=(ret+(ll)dp[i]*C(n,i))%mod;
	printf("%u\n",ret);
	return 0;
}

Measured memory_bytes: 896
#include <stdio.h>

#define MAXMATRIX 100

//シグマの計算(Σ[j = 0 → m] array_a[i][j] * column_b[j])
int sigma(int i, int j, int m, int matrix_a[MAXMATRIX][MAXMATRIX], int column_b[MAXMATRIX]);

int main(void)
{
    int matrix_a[MAXMATRIX][MAXMATRIX];
    int column_b[MAXMATRIX];
    int i, j, n, m;

    scanf("%d %d", &n, &m);

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

    for(i = 0; i < n; i++){
        printf("%d\n", sigma(i, j, m, matrix_a, column_b));
    }
    return 0;
}

int sigma(int i, int j, int m, int matrix_a[MAXMATRIX][MAXMATRIX], int column_b[MAXMATRIX])
{
    int ans;

    ans = 0;

    for(j = 0; j < m; j++){
        ans += matrix_a[i][j] * column_b[j];
    }

    return ans;
}


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

std::vector<int> ToOctalNumber(int n){
	std::vector<int> res;
	while(n){
		res.push_back((n&7)<4?n&7:(n&7)==4?5:(n&7)+2);
		n >>= 3;
	}
	std::reverse(res.begin(), res.end());
	return res;
}

int main(){
	int n;
	while(std::cin >> n, n){
		std::vector<int> sample = ToOctalNumber(n);
		for(int i=0;i<sample.size();i++){
			std::cout << sample[i];
		}
		std::cout << "\n";
	}
}

Measured memory_bytes: 1212
#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define dd(x) cout << #x << " = " << x << ", "
#define de(x) cout << #x << " = " << x << endl
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define per(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    pii p[55];
    rep(i,0,n){
        int x,y;
        scanf("%d%d",&x,&y);
        p[i]=mp(x,y);
    }
    sort(p,p+n);
   // rep(i,0,n) cout<<p[i].fi<<' '<<p[i].se<<endl;
    ll ans=4e18+3;
    rep(i,0,n-k+1){
        rep(j,i+k,n+1){
            vi yy;
            yy.clear();
            rep(o,i,j){
                yy.pb(p[o].se);
            }
            sort(all(yy));
           // rep(t,0,j-i) cout<<yy[t]<<' ';
            //cout<<endl;
            ll miny=2e9+2;
            rep(o,0,j-i-k+1){
            //de(o);
           // dd(yy[o]),dd(yy[o+k-1]);
                miny=min((ll)yy[o+k-1]-(ll)yy[o],miny);
              //  de(miny);
            }
            //dd(i),dd(j),dd(p[j].fi),de(p[i].fi);
            ans=min(ans,miny*(p[j-1].fi-p[i].fi));
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
x=int(input())
first=list(map(int,input().split()))
drink_count=int(input())
count=0
Total=sum(first)
drink=[list(map(int,input().split())) for i in range(drink_count)]
for T in range(drink_count):
    change_num = drink[count][0]
    score = first[change_num-1]-drink[count][1]
    print(Total-score)
    count+=1

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin >> n;
  vector<int> A(n),ans(n,0);
  for(int i=0;i<n-1;i++){
    cin >> A[i];
    ans[A[i]-1]++;
  }
  for(int i=0;i<n;i++)cout << ans[i] << endl;
  return 0;
}


Measured memory_bytes: 4840
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <climits>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
 
#define REP(i,n) for(long long i=0;i<n;++i)
#define REPR(i,n) for(long long i=n;i>=0;--i)
#define REPI(itr,v) for(auto itr=v.begin();itr!=v.end();++itr)
#define REPIR(itr,v) for(auto itr=v.rbegin();itr!=v.rend();++itr)
#define FOR(i,a,b) for(long long i=a;i<b;++i)
#define SORT(v,n) sort(v, v+n)
#define SORTV(v) sort(v.begin(), v.end())
#define ALL(v) v.begin(),v.end()
#define llong long long
#define INF 999999999
#define SUR 1000000007
#define pb push_back
#define pf push_front
#define MP make_pair
#define SV(v) {for(long long sitr=0;sitr<v.size();++sitr){cin>>v[sitr];}}
 
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};
 
using namespace std;
 
typedef pair<int,int> pii;
 
#define MAX 100000
 
int par1[MAX], rank1[MAX], n_size1[MAX];
 
void init(int par[], int n_size[], int V){
  for(int i = 0; i < V; ++i){
    par[i] = i;
    n_size[i] = 1;
  }
}
 
int find(int x, int par[]){
  if(par[x] == x){
    return x;
  }else{
    return par[x] = find(par[x], par);
  }
}
 
void unite(int x, int y, int par[], int rank[], int n_size[]){
  x = find(x, par);
  y = find(y, par);
  //n_size[x]++; n_size[y]++;
  llong sum = n_size[x] + n_size[y];
  if(x == y)
    return;
 
  if(rank[x] > rank[y]){
    par[y] = x;
  }else{
    par[x] = y;
    if(rank[x] == rank[y])
      rank[y]++;
  }
  n_size[par[x]] = sum;
  //par[y] = sum;
}
 
int same(int x, int y, int par[]){
  return find(x, par) == find(y, par);
}
 
llong get_size(int x, int par[], int n_size[]){
  return n_size[par[x]];
}
 
int main(){
 
  llong n, m;
  cin >> n >> m;
 
  vector<llong> a(m), b(m);
  REP(i,m){
    cin >> a[i] >> b[i];
    a[i]--; b[i]--;
  }
 
  init(par1, n_size1, n);
  vector<llong> ans(m+1);
 
  llong incon = n * (n-1) / 2;
  //incon = 0;
  ans[m] = incon;
  REP(i,m){
    int idx = m - i - 1;
    if(same(a[idx], b[idx], par1)){
      unite(a[idx], b[idx], par1, rank1, n_size1);
    }else{
      incon -= get_size(a[idx], par1, n_size1) * get_size(b[idx], par1, n_size1);
      unite(a[idx], b[idx], par1, rank1, n_size1);
    }
    ans[idx] = incon;
  }
 
  REP(i,m){
    cout << ans[i+1] << endl;
  }
 
  return 0;
}
 


Measured memory_bytes: 4864
class Tree:
    def __init__(self, N):
        self.N = N # #vertices
        self.D = (self.N-1).bit_length() # #iterations in doubling
        self.E = [{} for _ in range(N)]
    
    def add_edge(self, init, end, weight, undirected=False):
        self.E[init][end] = weight
        if undirected: self.E[end][init] = weight
    
    def lca_initialize(self):
        self.dfs(0)
        self.doubling()
    
    def dfs(self, root):
        # parents[v]: the parent of the vertex v
        # depth[v]: the depth of the vertex v from the root
        # dist[v]: the distance of the vertex v from the root.
        self.parent = [None] * self.N
        self.depth = [None] * self.N
        self.dist = [float('inf')] * self.N
        self.parent[root] = -1; self.depth[root] = 0; self.dist[root] = 0;
        stack = [root]
        while stack:
            v = stack.pop()
            for u, d in self.E[v].items():
                if self.depth[u] is not None: continue
                self.parent[u] = v
                self.depth[u] = self.depth[v] + 1
                self.dist[u] = self.dist[v] + d
                stack.append(u)
    
    def doubling(self):
        # O(N log N) time
        self.next = [[-1] * self.N for _ in range(self.D)]
        for v in range(self.N):
            self.next[0][v] = self.parent[v]
        for d in range(self.D - 1):
            for v in range(self.N):
                if self.next[d][v] != -1:
                    self.next[d + 1][v] = self.next[d][self.next[d][v]]
    
    def lca(self, u, v):
        # O(log N) time
        # the depth of v is set to be no less than that of u
        if self.depth[u] > self.depth[v]: u, v = v, u
        # find the ancestor of v with the same depth as that of u
        diff = self.depth[v] - self.depth[u]
        for i in range(diff.bit_length()):
            if diff & (1 << i): v = self.next[i][v]
        if u == v: return u
        for i in range(self.depth[u].bit_length() - 1, -1, -1):
            pu, pv = self.next[i][u], self.next[i][v]
            if pu != pv: u, v = pu, pv
        return self.next[0][u]

N = int(input())
tr = Tree(N)
for _ in range(N-1):
    a, b = map(int, input().split())
    tr.add_edge(a-1, b-1, 1, undirected=True)
tr.dfs(0)
d_odd, d_even = [], []
rem = [[] for _ in range(3)]
for i in range(N):
    if tr.depth[i] % 2 == 0: d_even.append(i)
    else: d_odd.append(i)
    rem[(i+1)%3].append(i+1)
P = [0] * N
if len(d_odd) < len(d_even):
    if len(d_odd) <= len(rem[0]):
        for i in d_odd: P[i] = rem[0].pop()
    else:
        for i in d_odd:
            if rem[2]:
                P[i] = rem[2].pop()
            else:
                P[i] = rem[0].pop()
    temp = rem[2] + rem[0] + rem[1]
    for i in d_even: P[i] = temp.pop()
else:
    if len(d_even) <= len(rem[0]):
        for i in d_even: P[i] = rem[0].pop()
    else:
        for i in d_even:
            if rem[2]:
                P[i] = rem[2].pop()
            else:
                P[i] = rem[0].pop()
    temp = rem[2] + rem[0] + rem[1]
    for i in d_odd: P[i] = temp.pop()
print(*P)

Measured memory_bytes: 113120
class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N
        self.count = 0
        self.size = [1] * N
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self.rank[ra] < self.rank[rb]:
            
            # rbが所属するユニオンのノード数をraと合算する。
            # ノード数合算 → 親の張替え　の順
            self.size[self.root(rb)] += self.size[self.root(ra)]
            self.parent[ra] = self.root(rb)

            
        else:
            # 上と同じ
            self.size[self.root(ra)] += self.size[self.root(rb)]
            self.parent[rb] = self.root(ra)

            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count += 1
    # aノードの所属するユニオンに所属しているノード数を戻す
    def nodes_in_same_union(self, a):
        return self.size[self.root(a)]

"""
繋がった状態から橋を落としていくと毎回どれが繋がって居るか計算するのが大変なので、
最後の端から順に繋いでいって逆順で表示することで答えにする
毎回 UnionFind.root を使うので遅い
"""

N,M = map(int, input().split())

AB = [tuple(map(int, input().split())) for _ in range(M)]

uf = UnionFind(N)
ans = [N*(N-1)//2]

#一番目を繋いでいるときの情報はいらないので最初以外
for a,b in list(reversed(AB))[:-1]:
    a,b = a-1, b-1
    if uf.is_same(a,b):
        tmp = 0
    else:
        tmp = uf.nodes_in_same_union(a) * uf.nodes_in_same_union(b)

    uf.unite(a,b)
    ans.append(max(ans[-1] - tmp, 0))

ans.reverse()
# sepでセパレータの指定
print(*ans, sep="\n")




Measured memory_bytes: 27052
#include <bits/stdc++.h>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
using namespace std;
const long long INF = 1LL << 60;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(){
    string S, T;
    cin >> S >> T;
    int ans = 0;
    rep(i, S.size()){
        if(S.at(i) != T.at(i)) ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3812
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <climits>
#include <queue>
#include <cstring>
#include <stack>
#include <map>
using namespace std;
#define rep(i,a,b) for(int i=a; i<=b; i++)
#define ii pair <int, int>
#define fi first
#define se second
#define ll unsigned long long
int n, w;
ll f[101][100001];
ii a[101];

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0);
//	freopen("Test.inp", "r", stdin);
//    freopen("Test.out", "w", stdout);
    rep(i,0,100) rep(j,0,100000) f[i][j]=LLONG_MAX;
    cin>>n>>w;
    rep(i,1,n) cin>>a[i].fi>>a[i].se;
    f[0][0]=0;
    rep(i,1,n){
        rep(j,0,n*1000){
            f[i][j]=f[i-1][j];
            if(a[i].se<=j) f[i][j] = min(f[i][j], f[i-1][j-a[i].se] + a[i].fi);
        }
    }
    int ans=0;
    rep(i,1,n) rep(j,ans+1,100000) if(f[i][j]<=w) ans=j;
    cout<<ans;
	return 0;
}


Measured memory_bytes: 79232
import java.util.Scanner;

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

		int a,b,t,gcd,lcm;
		
		while(cin.hasNext())
		{
			a=lcm=cin.nextInt();
			b=gcd=cin.nextInt();
			
			while(gcd!=0)
			{
				lcm=lcm%gcd;
				t=lcm; lcm=gcd; gcd=t;	
			}
			gcd = a/lcm*b;

			System.out.println(lcm+" "+gcd);
		}
	}
}

Measured memory_bytes: 12000
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <set>
#include <queue>
#include <map>
#include <numeric>
#include <functional>
#include <math.h>

using namespace std;

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

#define INF ((int)1e9)
#define INFLL ((ll)1e18)
#define MOD (1000000007LL)


int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(false);
    string S;
    cin >> S;
    char ac[4];
    for (int i = 0; i < S.length(); ++i) {
        ac[i] = S[i];
    }
    sort(ac, ac + 4);
    if (ac[0] == ac[1] && ac[1] != ac[2] && ac[2] == ac[3]) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}


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

using namespace std;

#define EACH(i,a) for (auto& i : a)
#define FOR(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define RFOR(i,a,b) for(int i=(int)b-1;i>=(int)a;--i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(a) (a).begin(),(a).end()
#define debug(x) cerr << #x << ":" << x << endl;
#define OK(ok) cout << (ok ? "Yes" : "No") << endl;
typedef long long ll;

void CINT(){}
template <class Head,class... Tail>
void CINT(Head&& head,Tail&&... tail) {
  cin >> head; CINT(move(tail)...);
}
#define CIN(...) int __VA_ARGS__;CINT(__VA_ARGS__)
#define LCIN(...) ll __VA_ARGS__;CINT(__VA_ARGS__)
#define SCIN(...) string __VA_ARGS__;CINT(__VA_ARGS__)

const int INF = 1e9 + 1;
const int MOD = 1e9 + 7;
const int MAX_N = 1e5 + 1;

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

  CIN(N);
  vector< int > a(N);
  REP(i, N) {
    cin >> a[i];
  }

  int ans = 0;
  REP(i, N - 1) {
    if (a[i] == a[i + 1]) {
      ans++;
      i++;
    }
  }

  int tmp = 0;
  RFOR(i, 1, N) {
    if (a[i] == a[i - 1]) {
      tmp++;
      i--;
    }
  }

  ans = min(ans, tmp);
  cout << ans << endl;

  return 0;
}



Measured memory_bytes: 256
using System;
using System.Collections.Generic;
namespace 令和{
    class ABC{
        static void Main(){
            int n = int.Parse(Console.ReadLine());
            //bool[] isEven = new bool[n-1];
            List<int[]>[] tonari = new List<int[]>[n+1];
            int[] ans = new int[n+1];
            for(int i=0;i<n+1;i++){
                tonari[i] = new List<int[]>();
                tonari[i] = new List<int[]>();
                ans[i] = -1;
            }
            int u,v,w;
            for(int i=1;i<n;i++){
               var rrrr =  Console.ReadLine();
                string[] uvw = rrrr.Split();
uvw = rrrr.Split();
                u = int.Parse(uvw[0]);
                v = int.Parse(uvw[1]);
                w = int.Parse(uvw[2]);
                u = int.Parse(uvw[0]);
                v = int.Parse(uvw[1]);
                w = int.Parse(uvw[2]);
                tonari[u].Add(new int[2]{v,w});
                tonari[v].Add(new int[2]{u,w});
            }
            Queue<int> q = new Queue<int>();
            q.Enqueue(1);
            ans[1] = 0;
            while(q.Count!=0){
                int p = q.Dequeue();
                foreach(int[] tnr in tonari[p]){
                    if(ans[tnr[0]]==-1){
                        ans[tnr[0]] = (tnr[1]+ans[p])%2;
                        q.Enqueue(tnr[0]);
                    }
                }
            }
            for(int i=0;i<n;i++){
                Console.WriteLine(ans[i+1]);
            }
 
 
        }
    }
}

Measured memory_bytes: 38904
using System;

namespace QQ
{
    class Program
    {
        static void Main(string[] args)
        {
            for (int i = 1; i < 10; i++)
            {
                for (int j = 1; j < 10; j++)
                {
                    Console.WriteLine("{0}x{1}={2}", i, j, i * j);
                }
            }
            Console.ReadKey();
        }
    }
}

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

const int INF=0x3f3f3f3f;

//RangeAdd+RangeMax
struct Segtree{
	int N;
	vector<int>dat,lazy;
	Segtree(int n){
		N=1;while(N<n)N<<=1;
		dat=lazy=vector<int>(2*N);
	}
	inline void push(int k){
		if(lazy[k]==0)return;
		dat[k]+=lazy[k];
		if(k<N){
			lazy[k*2]+=lazy[k];
			lazy[k*2+1]+=lazy[k];
		}
		lazy[k]=0;
	}
	inline void upnode(int k){
		dat[k]=max(dat[k*2],dat[k*2+1]);
	}
	inline void update(int a,int b,int x,int k,int l,int r){
		push(k);
		if(b<=l||r<=a)return;
		if(a<=l&&r<=b){
			lazy[k]+=x;push(k);return;
		}
		update(a,b,x,k*2,l,(l+r)/2);
		update(a,b,x,k*2+1,(l+r)/2,r);
		upnode(k);
	}
	inline int query(int a,int b,int k,int l,int r){
		push(k);
		if(b<=l||r<=a)return -INF;
		if(a<=l&&r<=b)return dat[k];
		int lb=query(a,b,k*2,l,(l+r)/2);
		int rb=query(a,b,k*2+1,(l+r)/2,r);
		upnode(k);
		return max(lb,rb);
	}
	inline void update(int a,int b,int x){
		update(a,b,x,1,0,N);
	}
	inline int query(int a,int b){
		return query(a,b,1,0,N);
	}
};

P p[300000];

int main(){
	int n,m;cin>>n>>m;
	rep(i,n)scanf("%d%d",&p[i].first,&p[i].second);
	Segtree seg(m+5);
	sort(p,p+n);
	for(int i=1;i<=m;i++)seg.update(0,i+1,-1);
	int Max=n-m;
	rep(i,n){
		seg.update(0,p[i].second+1,1);
		Max=max(Max,seg.query(p[i].first+1,m+2)-p[i].first);
	}
	cout<<max(0,Max)<<endl;
}

Measured memory_bytes: 5888
import java.io.*
import java.util.*

const val S = 0
const val W = 1
fun solve(N: Int, s: String){
    // animals[0]が W, Sの二通り, animals[1]がW, Sの二通り 2つ決めたら一意に決まる

    val animalsPattern = Array(4){ IntArray(N) }
    animalsPattern[0][0] = S
    animalsPattern[1][0] = S
    animalsPattern[2][0] = W
    animalsPattern[3][0] = W
    animalsPattern[0][1] = S
    animalsPattern[1][1] = W
    animalsPattern[2][1] = S
    animalsPattern[3][1] = W
    for (i in 2 until N){
        for(j in 0..3){
            // same
            if ((animalsPattern[j][i-1] == S && s[i-1] == 'o') || (animalsPattern[j][i-1] == W && s[i-1]=='x')){
                animalsPattern[j][i] = animalsPattern[j][i-2]
            }else{
                animalsPattern[j][i] = animalsPattern[j][i-2] xor 1
            }
        }
    }
    for(j in 0..3){
        // same
        val lastFromHead = if ((animalsPattern[j][0] == S && s[0] == 'o') || (animalsPattern[j][0] == W && s[0]=='x')) animalsPattern[j][1] else animalsPattern[j][1] xor 1
        val firstFromTail= if ((animalsPattern[j][N-1] == S && s[N-1] == 'o') || (animalsPattern[j][N-1] == W && s[N-1]=='x')) animalsPattern[j][N-2] else animalsPattern[j][N-2] xor 1
        if (lastFromHead == animalsPattern[j][N-1] && firstFromTail == animalsPattern[j][0]){
            animalsPattern[j].map{ if (it==S) 'S' else 'W' }.joinToString(separator="").let{ println(it) }
            return
        }
    }
    println(-1)
    return
}


fun main(args: Array<String>) {
    fun StringArray(size: Int, init: (Int) -> String = { "\u0000" }): Array<String> {
        return Array<String>(size, init)
    }
    class Scanner(stream: InputStream) {
        private val reader = BufferedInputStream(stream).bufferedReader()
        private var st: StringTokenizer? = null
        fun next(): String {
            while (!(st?.hasMoreTokens() ?: false)) st = StringTokenizer(reader.readLine())
            return st!!.nextToken()
        }
    }
    val sc = Scanner(System.`in`)
    val N = sc.next().toInt()
    val s = sc.next()
    solve(N, s)
}



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

int main()
{
	string S;
	cin >> S;

	int N = S.size();
	int n = 0;
	int w = 0;
	int s = 0;
	int e = 0;
	for( int i = 0; i < N; i++ ) {
		if( S[i] == 'N' ) n++;
		else if( S[i] == 'W' ) w++;
		else if( S[i] == 'S' ) s++;
		else if( S[i] == 'E' ) e++;
	}
	string ans = "Yes";
	if( n && s == 0 || n == 0 && s ) ans = "No";
	if( w && e == 0 || w == 0 && e ) ans = "No";

	cout << ans << endl;
}


Measured memory_bytes: 3636
#include<bits/stdc++.h>
#define ll long long
#define REP(i, n) for (int i=0; i<n; ++i)
#define print(x) cout << x << endl;

using namespace std;

void solve() {
    int N, K;
    cin >> N >> K;
    vector<int> h(N);
    REP(i, N) {
        cin >> h[i];
    }

    vector<ll> dp(N+1, 1e9);
    dp[1] = 0;
    for (int i = 2; i <= N; ++i) {
        for (int j = 1; j <= K; ++j) {
            if (i - j < 1) break;
            ll diff = abs(h[i-1] - h[i-1-j]);
            dp[i] = min(dp[i], dp[i-j] + diff);
        }
    }
    print(dp[N]);
}

int main() {

    solve();
    return 0;
}


Measured memory_bytes: 1408
///                                                     ببِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيم
#include <bits/stdc++.h>
#define off  exit( 0 )
#define cn   continue
#define rt   return
#define sc   scanf
#define pr   printf
#define pb   push_back
#define pf   push_front
#define p_f  pop_front
#define p_b  pop_back
#define ff   first
#define ss   second
#define vec  vector
#define gcd  __gcd
#define pi   acos( -1 )
#define ll   long long
#define ld   long double
#define N    30256
#define M    998244353
#define I    1000000000000000000
#define pdd  pair < ld, ld >
#define pll  pair < ll, ll >
#define pii  pair < int, int >
#define rep( a, b, c, d )  for( int a = b; a <= c; a += d )
#define rvv( a, b, c, d )  for( int a = b; a >= c; a -= d )
#define en                 printf( "\n" )
#define sqr( a )           a * a
#define all( c )           c.begin(), c.end()
#define srt( c )           sort( all( c ) )
#define rev( c )           reverse( all( c ) )
#define srtr( c )          sort( c.rbegin(), c.rend() )
#define numcounts          __builtin_popcount
#define mxn( x, y, z )     max( x, min( y, z ) )
#define mnx( x, y, z )     min( x, max( y, z ) )
const int dx[ ] = { 1, -1, 0, 0 };
const int dy[ ] = { 0, 0, -1, 1 };
using namespace std;
ll ttt = 1;
ll n, ans, cur;
string s;
void solve()
{
    cin >> n >> s;
    for(char i = '0'; i <= '9'; i ++)
        for(char j = '0'; j <= '9'; j ++)
            for(char k = '0'; k <= '9'; k ++)
            {
                cur = 0;
                for(int pos = 0; pos < n; pos ++)
                {
                    if(cur == 2 && s[pos] == k)
                    {
                        cur ++;
                        break;
                    }
                    if(cur == 1 && s[pos] == j)cur ++;
                    if(!cur && s[pos]== i)cur ++;
                    //cout << i << " " << j << " " << k << " " << cur << endl;
                }
                ans += (cur == 3);
            }

    cout << ans;
}

int main()
{

   // sc( "%I64d", &tests );
    for(int i = 0; i < ttt; i ++ )
        solve();
}






Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); ++i)
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)
using namespace std;
using Graph = vector<vector<int>>;
typedef long long ll;
typedef pair<int, int> P;
const int inf = 1<<21;
const ll INF = 1LL << 60;
const ll mod = 1e9+7;

// DAME:
// 場合の数

const int MAX = 3000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main() {
    COMinit();
    int n, k;
    cin >> n >> k;
    rep(i, k){
        cout << COM(n-k+1, i+1) * COM(k-1, i) % mod << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>

#define rep(i, a, b) for ( int i = (a); i < (b); i++ )
#define per(i, a, b) for ( int i = (b)-1; i >= (a); i--)
#define pb push_back
#define bg begin()
#define en end()

#define pr_arr(name, a, b) \
  for (int i = (a); i < (b); i++) { \
    for (int j = (a); j < (b); j++) {\
      if (j > (a)) printf(" "); \
      printf("%lld", name[i][j]); \
    }\
    printf("\n");\
  }\

#define YES puts("YES")
#define NO  puts("NO")
#define Yes puts("Yes")
#define No  puts("No")

using namespace std;

typedef long long ll;

int ans;
ll A, B;

template <class Type>
Type gcd(Type x, Type y) {
	if ( y == 0 ) return x;
	return gcd(y, x % y);
}

template <class Type>
Type lcm(Type x, Type y) {
	return (x * y) / gcd(x, y);
}

int main(void) {
    scanf("%d %d", &A, &B);
  
    printf("%lld\n", lcm<ll>(A, B));

	return 0;
}


Measured memory_bytes: 256
N,Y=map(int,input().split())
ans=0

nax=Y//1000

if N==nax:
    print(0,0,nax)
    exit()
elif N>nax:
    print(-1,-1,-1)
    exit()
else:
    for i in range(nax//10+1):
        for j in range(nax//5+1):
            if nax-10*i-5*j>=0 and nax-9*i-4*j==N:
                print(i,j,nax-10*i-5*j)
                exit()
print(-1,-1,-1)

Measured memory_bytes: 65784
N,M=map(int,input().split())
sc=[list(map(int,input().split())) for m in range(M)]
for i in range(10**N):
    if len(str(i))==N and all(str(i)[s-1]==str(c) for s,c in sc):
        print(i)
        break
else:
    print(-1)

Measured memory_bytes: 9192
#include <cstdio>
#include <vector>

using namespace std;

void Get_Val(int &Ret)
{
	Ret = 0;
	char ch;
	while (ch = getchar(), ch > '9' || ch < '0')
		;
	do
	{
		(Ret *= 10) += ch - '0';
	}
	while (ch = getchar(), ch >= '0' && ch <= '9');
}

const int Max_M(100050);

int N, M, BIT[Max_M];
vector< pair<int, int> > V[Max_M];

inline int lowbit(const int &x)
{
	return x & -x;
}

void insert(int i, const int &v)
{
	while (i <= M)
		BIT[i] += v, i += lowbit(i);
}

int query(int i)
{
	int Ret(0);
	while (i)
		Ret += BIT[i], i -= lowbit(i);
	return Ret;
}

inline void Add(const int &l, const int &r)
{
	insert(l, +1), insert(r + 1, -1);
}

int main()
{
	int Ans(0), Tmp;
	Get_Val(N), Get_Val(M);
	for (int i = 1, l, r;i <= N;++i)
		Get_Val(l), Get_Val(r), V[r - l + 1].push_back(make_pair(l, r)), ++Ans;
	for (int i = 1;i <= M;++i)
	{
		Tmp = Ans;
		for (int j = i;j <= M;j += i)
			Tmp += query(j);
		for (int j = 0;j != V[i].size();++j)
		{
			--Ans;
			Add(V[i][j].first, V[i][j].second);
		}
		printf("%d\n", Tmp);
	}
	return 0;
}

Measured memory_bytes: 7936
#include<iostream>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>
#include<utility>

using namespace std;

#define int __int128
#define endl "\n"

constexpr long long INF = (long long)1e18;
constexpr long long MOD = 1'000'000'007; 

struct fast_io {
	fast_io(){
		std::cin.tie(nullptr);
		std::ios::sync_with_stdio(false);
	};
} ;
// } fio;

int P(int a){
	return a * a * a * a * a;
}

void solve(int X){
	
	for(int i = -2000; i <= 2000; i++){
		for(int j = -2000; j <= 2000; j++){
			if(P(i) - P(j) == X) {
				cout<<(long long)i<<" "<<(long long)j<<endl;
				return;
			}
		}
	}
}

signed main(){
	cout<<fixed<<setprecision(10);
	
	
	
	long long X;
	
	// cin>>X;
	
	// for(int i = 0; i < X; i++){
		// cout<<"i = "<<(long long)i<<" "<<(long long)P(i)<<" "<<(long long)(P(i+1)-P(i))<<endl;
	// }
	
	cin>>X;
	
	solve(X);
	
	return 0;
}

Measured memory_bytes: 3624
import java.util.Scanner;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    Long n = sc.nextLong();
    Long money = 100L;
    int y = 0;
    while(money < n){
      money += money/100;
      y++;
    }
    System.out.println(y);
  }
}

Measured memory_bytes: 35840