akhauriyash/Code-Regression huggingface dataset:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;
import java.util.ArrayList;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        ABC116_B solver = new ABC116_B();
        solver.solve(1, in, out);
        out.close();
    }

    static class ABC116_B {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int n = in.nextInt();
            ArrayList<Integer> array = new ArrayList<Integer>();
            array.add(n);
            int a = n;

            while (true) {
                if (a % 2 == 0) {
                    a = a / 2;
                } else {
                    a = a * 3 + 1;
                }
                if (array.contains(a)) {
                    out.print(array.size() + 1);
                    break;
                }
                array.add(a);
            }
        }

    }
}



Measured memory_bytes: 21716
import std.algorithm, std.conv, std.range, std.stdio, std.string;

void main()
{
  auto h = readln.chomp.to!size_t;
  auto hi = readln.split.to!(int[]);
  hi = 0 ~ hi;

  buildMaxHeap(hi, h);

  foreach (i; 1..h+1)
    write(" ", hi[i]);
  writeln;
}

void maxHeapify(ref int[] ai, size_t h, size_t i)
{
  auto l = i * 2, r = l + 1;
  size_t largest;

  if (l <= h && ai[l] > ai[i])
    largest = l;
  else
    largest = i;
  if (r <= h && ai[r] > ai[largest])
    largest = r;

  if (largest != i) {
    swap(ai[i], ai[largest]);
    maxHeapify(ai, h, largest);
  }
}

void buildMaxHeap(ref int[] ai, size_t h)
{
  foreach_reverse(i; 1..h/2+1)
    maxHeapify(ai, h, i);
}

Measured memory_bytes: 26200
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <mutex>
#include <cmath>
#include <set>
#include <climits>
#include <bitset>

#define mod 1e9+7
#define mp make_pair
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

using namespace std;
using ll = long long;
using pii = pair<int, int>;

int main(){
	ll N, a;
	cin >> N;
	ll pivot = 1;
	ll ans = 0;
	rep(i, N){
		cin >> a;
		if(pivot == a){
			pivot++;
		}
		else ans++;
	}
	if(ans == N) cout << -1;
	else cout << ans;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
int main() {
  ll N;
  cin >> N;
  vector<ll> vecA(N);
  vector<ll> vecB(N-1);
  ll sum = 0;
  ll X;
  rep(i, N) {
    cin >> vecA.at(i);
  }
  rep(i, N) {
    cin >> X;
    sum += X;
  }
  rep(i, N - 1) {
    cin >> vecB.at(i);
  }
  X = 1000;
  rep(i, N) {
    if(vecA.at(i) == X + 1) {
      sum += vecB.at(X-1);
    }
    X = vecA.at(i);
  }
  cout << sum << endl;
}

Measured memory_bytes: 3616
#include<iostream>

using namespace std;

bool isprime[1000001];//false????´???°

int main() {
	isprime[1] = true;
	int n, x;
	int price[30];

	for (int i = 2; i <= 1000000; i++) {
		if (!isprime[i]) {
			for (int j = i * 2; j <= 1000000; j += i) {
				isprime[j] = true;
			}
		}
	}

	while (cin >> n >> x, n * x) {
		bool isprice[1000001] = {};//??????????????????????????????true
		for (int i = 0; i < n; i++) {
			cin >> price[i];
			isprice[price[i]] = true;
		}
		for (int i = 1; i <= x; i++) {
			if (isprice[i]) {
				for (int j = 0; j < n; j++) {
					if (i + price[j] <= x) {
						isprice[i + price[j]] = true;
					}
				}
			}
		}
		int ans = 99999999;
		for (int i = x;i >= 1; i--) {
			if (!isprime[i] && isprice[i]) {
				ans = i;
				break;
			}
		}
		if (ans == 99999999)cout << "NA" << endl;
		else cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 5016
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define ll long long int
#define pb push_back
#define mp make_pair
#define boost ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define forn(i, n) for(int i = 0; i < (int)(n); i++)
#define ford(i, n) for(int i = (int)(n) - 1; i >= 0; i--)
#define F first
#define S second
#define mset(x,v) memset(x, v, sizeof(x))
int main()
{
      boost;
            int n,m,x,p=0,q=0,w;
            cin>>n>>m>>x;
            map<int,int> m1;
            forn(i,m)
            {
                  cin>>w;
                  m1[w]=1;
            }
            int ans=0x3f;
            for(int i=x;i>=0;i--)
            {
                  if(m1[i])
                  p++;
            }
            ans=min(ans,p);
            for(int i=x+1;i<=n;i++)
            {
                  if(m1[i])
                  q++;
            }
            ans=min(ans,q);
            cout<<ans<<endl;
}


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int main(){
  ios::sync_with_stdio(false);
  int a, b, c;

  cin >> a >> b >> c;
  c -= a - b;
  if(c < 0)
    c = 0;
  cout << c << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(var,cnt) for(int (var)=0; (var)<(int)(cnt); ++(var))
#define Rep(var,init,cnt) for(int (var)=(init); (var)<(int)(cnt); ++(var))
#define ran(var,vec) for(auto &(var):(vec))
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define SORT(v) sort(all(v))
#define RSORT(v) sort(rall(v))
#define SUM(v) accumulate(all(v),0)
#define tget(tp,idx) get<idx>(tp)
#define TF(flag) ((flag)?1:0)
#define YN(flag) cout<<(flag?"YES":"NO")<<endl;
#define Yn(flag) cout<<(flag?"Yes":"No")<<endl;
#define yn(flag) cout<<(flag?"yes":"no")<<endl;
#define Cout(v) cout<<(v)<<endl
using namespace std;

using ll = long long;
using ull = unsigned long long;
using pi = pair<int,int>;
using pl = pair<ll,ll>;
using ti = tuple<int,int,int>;
using tl = tuple<ll,ll,ll>;

template<typename T>
using vec = vector<T>;
template<typename T>
using mat = vector<vec<T>>;
template<typename T>
using cub = vector<mat<T>>;
template<typename T>
using val = valarray<T>;

template<typename T>
using pq = priority_queue<T>;
template<typename T>
using rpq = priority_queue<T,vec<T>,greater<T>>;

template<typename T1,typename T2>
ostream &operator<<(ostream &os, const pair<T1,T2> &p){
  os<<"P("<<p.first<<", "<<p.second<<") ";
  return os;
}

template<typename T1,typename T2>
istream &operator>>(istream &is, pair<T1,T2> &p){
  is>>p.first>>p.second;
  return is;
}

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v){
  cout<<"V{";
  for(int i=0; i<(int)v.size(); ++i){
    os<<v[i]<<(i+1!=v.size()?" ":"");
  }
  cout<<"}";
  return os;
}

template<typename T>
istream &operator>>(istream &is, vector<T> &v){
  for(T &in:v) is>>in;
  return is;
}

template<typename T>
ostream &operator<<(ostream &os, const valarray<T> &v){
  cout<<"V{";
  for(int i=0; i<(int)v.size(); ++i){
    os<<v[i]<<(i+1!=v.size()?" ":"");
  }
  cout<<"}";
  return os;
}

template<typename T>
istream &operator>>(istream &is, valarray<T> &v){
  for(T &in:v) is>>in;
  return is;
}

// Usual Template End ===================

// Template End =========================

int main(void){
  int a,b,c; cin>>a>>b>>c;
  Cout(min(b/a,c));
}












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

int main(void){
    int N,M;
    cin >> N >> M;
    vector<vector<int>> G(N,vector<int>());
    for(int i=0;i<M;i++){
        int a,b;
        cin >> a >> b;
        G[a-1].push_back(b-1);
        G[b-1].push_back(a-1);
    }

    vector<int> v(N-1);
    vector<int> road(N-1);
    for(int i=0;i<N-1;i++) v[i] = i+1; //1,2,3,....,N-1

    int count=0;
    do{
        bool ok = true;
        int pos = 0,next = 0;
        while(pos!=v[N-2]){
            auto itr = find(G[pos].begin(),G[pos].end(),v[next]);
            if(itr==G[pos].end()){ok=false;break;}
            else{pos = v[next]; next++;}
        }
        if(ok) count++;

    }while(next_permutation(v.begin(),v.end()));

    cout << count << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
using namespace std;

const int INF = 1e8;

int m[33][33];
map<char,vector<vector<int>>> c;

/*
0: ?????´????????????
1: ??????????????????
2: ????????¢?????????
3: ??????????????????
4: ????????¢?????????
*/

struct Point{ int x, y; };
int dy[5] = {-1,0,1,0,-100}, dx[5] = {0,1,0,-1,-100};
char ch[5] = "nwse";
int mc[4];
int h, w;
int limit;

int direction(int com, char dis){
    if(com == 4) return com;
    if(dis == 'n') return com;
    else if(dis == 'w') return (com + 1) % 4;
    else if(dis == 's') return (com + 2) % 4;
    else if(dis == 'e') return (com + 3) % 4;
    return -1;
}

void dfs(int y, int x, char dis, int cost, int k){
    //cout << y << ' ' << x << endl;
    //show(m[y][x])
    //    show(dis)
    //if(k > w * h) return;
    if(cost > limit) return;

    rep(i,4){
        int p = direction(i,dis);
        int ny = y + dy[p];
        int nx = x + dx[p];
        int next_cost = cost + (i == m[y][x] ? 0 : mc[i]);

        if(nx < 0 || nx >= w || ny < 0 || ny >= h) continue;
        if(c[ch[p]][ny][nx] <= next_cost) continue;
        c[ch[p]][ny][nx] = next_cost;
        dfs(ny,nx,ch[p], next_cost, k + 1);
    }
}

int main(){
    while(scanf("%d%d",&w,&h),h){
        rep(k,4) c[ ch[k] ] = vector<vector<int>>(33,vector<int>(33));
        rep(k,4) rep(i,h) rep(j,w) c[ch[k]][i][j] = INF;
        c['w'][0][0] = 0;

        rep(i,h) rep(j,w) scanf("%d",&m[i][j]);
        rep(i,4) scanf("%d",&mc[i]);
        limit = mc[0] * (h + w) + min(mc[1],mc[3]);

        dfs(0, 0, 'w', 0, 0);

        //rep(i,h){ rep(j,w){ cout << c['w'][i][j] << ' '; } cout << endl; }

        int mini = INF;
        rep(i,4) mini = min(mini, c[ch[i]][h - 1][w - 1]);
        cout << mini << endl;
    }
}

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

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

    int t;
    if (a > b) {
        t = a;
        a = b;
        b = t;
    }
    if (b > c) {
        t = b;
        b = c;
        c = t;
    }
    if (a > b) {
        t = a;
        a = b;
        b = t;
    }

    cout << a << " " << b << " " << c << endl;

    return 0;
}

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

using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define a first
#define b second
#define sz(x) (ll)((x).size())
#define pb push_back
#define mp make_pair 
#define bg begin()
#define ed end()
#define all(x) (x).bg,(x).ed
#define rep(i,n) for(ll i=0;i<(n);i++)

int main(){
	ll x1,y1,x2,y2,x3,y3; cin>>x1>>y1>>x2>>y2>>x3>>y3;
	double L1=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)),L2=sqrt((x1-x3)*(x1-x3)+(y1-y3)*(y1-y3)),L3=sqrt((x2-x3)*(x2-x3)+(y2-y3)*(y2-y3));
	double maxL=max(max(L1,L2),L3);
	double s=(L1+L2+L3)/2;
	double r=2*sqrt(s*(s-L1)*(s-L2)*(s-L3))/(L1+L2+L3);

	double L=0.0,R=maxL;
	rep(k,100){
		double i=(L+R)/2;
		if((1-i/r)*maxL > 2*i) L=i;
		else R=i;
	}
	printf("%.12f",L);
}

Measured memory_bytes: 256
n, k = (int(i) for i in input().split())
ab = []
for i in range(0,n):
    ab.append([int(i) for i in input().split()])
sortab = sorted(ab, key=lambda x: x[0])

count = 0
for i in range(0,n):
    count = count + sortab[i][1]
    if count >= k:
        print(sortab[i][0])
        break


Measured memory_bytes: 23640
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		while(true) {
			int h = stdIn.nextInt();
			int w = stdIn.nextInt();
			if(h == 0 && w == 0) break;
			int diagonal = h * h + w * w;
			int mindiag = 999999999;
			int minh = 99999999;
			int minw = 99999999;
			for(int i = 1; i <= 150; i++) { //h
				for(int j = i+1; j <= 150; j++) { //w
					int diag = i * i + j * j;
					if(diag >= diagonal) {
						if(diag == diagonal && h >= i) {
							continue;
						}
						if(mindiag > diag) {
							mindiag = diag;
							minh = i;
							minw = j;
						}
					}
				}
			}
			System.out.println(minh + " " + minw);
		}
	}
}

Measured memory_bytes: 20380
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<vector>

using namespace std;

typedef long long LL;
const int MX=201;
const LL mxx=1000000000000000000LL,md=1000000007;
//int f[MX][MX];
typedef pair<LL,LL> pii;
#define mp make_pair
#define se second
#define fr first
vector<pii>S[MX];
typedef vector<pii>::iterator vit;

int main(){
	S[1].push_back(mp(1,2));
	int it=1;
	while(S[it][0].fr<=mxx){
		++it;
		for(vit i=S[it-1].begin();i!=S[it-1].end();i++)
			S[it].push_back(mp(i->se,i->fr+i->se));
		S[it].push_back(mp(S[it-1][0].fr+S[it-1][0].se,S[it-1][0].fr*2+S[it-1][0].se));
	}
	int q;scanf("%d",&q);
	while(q--){
		LL x,y;scanf("%lld%lld",&x,&y);
		if(x>y)swap(x,y);
		if(x==1)printf("%d %lld\n",1,y%md);
		else if(x==2&&y==2)puts("1 4");
		else{
			int it=1;while(S[it][0].fr<=x&&S[it][0].se<=y)++it;
			--it;
			LL ans=0LL;
			for(vit i=S[it].begin();i!=S[it].end();i++){
				if(x>=i->fr&&y>=i->se)ans=(ans+(y-i->se)/i->fr+1)%md;
				if(x>=i->se&&y>=i->fr)ans=(ans+(x-i->se)/i->fr+1)%md;
			}
			printf("%d %lld\n",it,ans);
		}
	}
	return 0;
}


Measured memory_bytes: 4096
#include <bits/stdc++.h>
using namespace std;
#define r(i,n) for(auto i=0;i<n;i++)
#define s(c) static_cast<int>((c).size())

struct Node{
	int key;
	Node *l;
	Node *r;
	Node *p;
};
Node *nil = new Node{INT_MAX};

void insert(Node *T, int key){
	Node *z = new Node{key, nil, nil, nil};
	if(T->key == INT_MAX){
		*T = *z;
		return;
	}
	Node *x = T;
	Node *y = x->p;
	while(x != nil){
		y = x;
		x = (key < x->key) ? x->l : x->r;
	}
	z->p = y;
	if(key < y->key){
		y->l = z;
	}else{
		y->r = z;
	}
}

vector<int> pre, in;
void preorder(Node *node){
	pre.push_back(node->key);
	if(node->l != nil) preorder(node->l);
	if(node->r != nil) preorder(node->r);
}

void inorder(Node *node){
	if(node->l != nil) inorder(node->l);
	in.push_back(node->key);
	if(node->r != nil) inorder(node->r);
}

void print(vector<int> v){
	r(i, s(v))
		cout << ' ' << v[i];
	cout << endl;
}

void printPreorder(Node *node){
	preorder(node);
	print(pre);
	pre.clear();
}

void printInorder(Node *node){
	inorder(node);
	print(in);
	in.clear();
}

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

	Node *root = new Node{INT_MAX};
	string cmd;
	int arg;
	r(i, m){
		cin >> cmd;
		if(cmd[0] == 'i'){
			cin >> arg;
			insert(root, arg);
		}else{
			printInorder(root);
			printPreorder(root);
		}
	}

	return 0;
}


Measured memory_bytes: 32252
N = int(input())
#A = [int(i) for i in input().split()]
A = list(map(int,input().split()))

def gcp(a,b):
    if b == 0:
        return a
    else:
        return gcp(b,a%b)

a = A[0]
for i in range(1,N):
    a = gcp(a,A[i])
print(a)

Measured memory_bytes: 14252
int main()
{
  long a, b, k;
  scanf("%ld %ld %ld", &a, &b, &k);
  if (k <= a)
    printf("%ld %ld", a - k, b);
  else if (k <= a + b)
    printf("0 %ld", a + b - k);
  else
    printf("0 0");
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
struct fastio { fastio () { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); } } _io;
template<class T, class U> bool chmax(T& a, const U &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T, class U> bool chmin(T& a, const U &b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
	int n, k;
	std::cin >> n >> k;
	std::vector<long long> a(n);
	for (auto &e : a) std::cin >> e;
	
	for (int i = k; i < n; i++) {
		if (a[i - k] < a[i]) std::cout << "Yes" << '\n';
		else std::cout << "No" << '\n';
	}
}

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

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

    vector<int> dp(n,INT_MAX);
    int h[n];
    for(int i = 0; i < n; i++){
        cin>>h[i];
    }
    dp[0] = 0;

    for(int i = 0; i < n; i++){
        for(int j = 1; j < 3; j++){
            if(i + j < n){
                dp[i+j] = min(dp[i+j], dp[i] + abs(h[i] - h[i+j]));
            }
        }
    }
    cout<<dp[n-1];

    return 0;
}

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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define repe(i,n) rep(i,(n)+1)
#define per(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define pere(i,n) rep(i,(n)+1)
#define all(x) (x).begin(),(x).end()
#define SP <<" "<<
#define RET return 0
#define MOD 1000000007
#define IINF 1000000000
#define LINF 1000000000000000000

typedef long long LL;
typedef long double LD;

int main(){
  LL n,x;
  cin >> n >> x;
  LL ans=n;
  LL w=x,d=n-x;
  while(w%d){
    ans+=2*(w/d)*d+2*(w%d)*(d/(w%d));
    w=w%d;
    d=d%w;
    if(d==0){
      ans-=w;
      goto a;
    }
  }
  ans+=2*(w/d)*d-d;
  a:
  cout << ans << endl;
  return 0;
}

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



int main(){
    int A, B, Q;
    cin >> A >> B >> Q;
    set<ll>S, T;
    S.insert(-1000000000000);
    T.insert(-1000000000000);
    S.insert(1000000000000);
    T.insert(1000000000000);
    for(int a = 0; a < A; a++){
        ll x;
        cin >> x;
        S.insert(x);
    }
    for(int b = 0; b < B; b++){
        ll x;
        cin >> x;
        T.insert(x);
    }
    for(int q = 0; q < Q; q++){
        ll x;
        cin >> x;
        set<ll>::iterator it = S.lower_bound(x);
        ll s[2], t[2];
        s[1] = *it;
        it--;
        s[0] = *it;
        it = T.lower_bound(x);
        t[1] = *it;
        it--;
        t[0] = *it;
        ll ans = 10000000000000;
        for(int i = 0; i < 2; i++){
            for(int j = 0; j < 2; j++){
                chmin(ans, abs(x-s[i]) + abs(s[i] - t[j]));
                chmin(ans, abs(x-t[i]) + abs(t[i] - s[j]));
            }
        }
        cout << ans << endl;
    }
    
    return 0;
}

Measured memory_bytes: 10752
#include<bits/stdc++.h>
#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 fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
typedef vector<int> vi;
const int mod = 1e9 + 7;
const int maxn = 2e6 + 10;
int prime[maxn],len = 0;
bool q[maxn];
int main(){	
	ios::sync_with_stdio(false);
	cin.tie(0);
	rep(i,2,1e6+2){
		if(!q[i]){
			prime[++len] = i;
			for(ll j =ll(i)*i;j <= 1e6;j += i)
				q[j] = 1;
		}
	}
	ll n,ans = 0;
	cin >> n;
	rep(i,1,len+1){
		if(n < prime[i])break;
		ll p = 0,q = 1;
		while(n%prime[i] == 0)n /= prime[i],++p;
		while(p >= q)p-=q,++q,++ans;
	//	cout << ans << '\n';;
	}
	if(n != 1)++ans;
	cout << ans;
	return 0;
}


Measured memory_bytes: 4980
#include<stdio.h>
#include<math.h>

struct Point{double x,y;};

void koch(int n,Point a,Point b){
	if(n==0)return;

	Point s,t,u;
	double th = M_PI * 60.0/180.0;

	s.x=(2.0*a.x + 1.0*b.x)/3.0;
	s.y=(2.0*a.y + 1.0*b.y)/3.0;
	t.x=(1.0*a.x + 2.0*b.x)/3.0;
	t.y=(1.0*a.y + 2.0*b.y)/3.0;
	u.x=(t.x-s.x)*cos(th) - (t.y-s.y)*sin(th) + s.x;
	u.y=(t.x-s.x)*sin(th) + (t.y-s.y)*cos(th) + s.y;

	koch(n-1,a,s);
	printf("%.8f %.8f\n",s.x,s.y);
	koch(n-1,s,u);
	printf("%.8f %.8f\n",u.x,u.y);
	koch(n-1,u,t);
	printf("%.8f %.8f\n",t.x,t.y);
	koch(n-1,t,b);
}

int main(){
	Point a,b;
	int n;

	scanf("%d",&n);

	a.x=0;
	a.y=0;
	b.x=100;
	b.y=0;

	printf("%.8f %.8f\n",a.x,a.y);
	koch(n,a,b);
	printf("%.8f %.8f\n",b.x,b.y);

	return 0;
}

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

int main() {
    int n;
    cin >> n;
    int sum = 0;
    int seat[n][2];
    for (int i=0;i<n;i++){
        cin >> seat[i][0] >> seat[i][1];
    }
    for(int i=0;i<n;i++){
        sum += seat[i][1] - seat[i][0] + 1;
    }
    cout << sum << endl;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
 
const int INF = 1e9;
int n, m, dp[21][50010], c[21];
 
int main(void) {
    cin >> n >> m;
    for (int i = 0; i < m; i++)
        cin >> c[i];
     
    for (int i = 0; i < 50010; i++)
        dp[0][i] = INF;
 
    dp[0][0] = 0;
    for (int i = 0; i < m; i++)
        for (int j = 0; j <= n; j++) {
            if (j < c[i]) dp[i + 1][j] = dp[i][j];
            else dp[i + 1][j] = min(dp[i][j], dp[i + 1][j - c[i]] + 1);
        }//dp[i]で枚数 jが値段
     
    cout << dp[m][n] << endl;
 
    return 0;
}


Measured memory_bytes: 7180
program main
  implicit none

  integer::n,answer,i,j,k
  real(8),allocatable::L(:)
  real(8)::ans(3)

  read*,n
  allocate(L(n))
  read*,L

answer=0

  do i=1,n
   do j=i+1,n
    do k=j+1,n
    a:  if((L(i) /= L(j)) .and. (L(j) /= L(k)) .and. (L(k) /= L(i))) then
        ans(1)=L(i)
        ans(2)=L(j)
        ans(3)=L(k)

    b:     if((abs(ans(3)-ans(2)) < ans(1)) .and. ((ans(3)+ans(2)) > ans(1)) ) then
             answer=answer+1
           end if b
         
         end if a

     end do
    end do
   end do

  print*,answer
        
end program main


      

Measured memory_bytes: 2932
#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 - 1; 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)

ll mod = 1e09 + 7;

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

  ll n;
  cin >> n;
  ll a[n];
  REP(i, n) cin >> a[i];

  SORT(a, n);

  ll cnt = 1;
  vector<ll> l;
  REPR(i, n - 1){
    if(a[i] == a[i + 1]) cnt++;
    else cnt = 1;

    if(cnt % 2 == 0) l.pb(a[i]);

    if(l.size() == 2) break;
  }

  if(l.size() <= 1) cout << 0 << endl;
  else cout << (l[0] * l[1]) << endl;

  return 0;
}


Measured memory_bytes: 1152
#include <bits/stdc++.h>
#define ll long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pil pair<int,ll>
#define pli pair<ll,int>
#define pll pair<ll,ll>
#define xh1(a,b) for(int i=a;i<b;i++)
#define xh2(a,b) for(int j=a;j<b;j++)
#define stlbl(a) for(it=a.begin();it!=a.end();it++)
#define dzkt int T;cin>>T;while(T--)
#define mst(a,i) memset(a,i,sizeof(a))
#define iosks std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int N=3e5+10,inf=1e9+10,mod=1e9+7;
const db pi=atan(1)*4;
ll pow2(ll a,ll b) {ll s=1; while(b) {if(b&1) s=(s*a)%mod; a=(a*a)%mod; b/=2; } return s;}
int gcd(int a,int b) {return b==0?a:gcd(b,a%b); }
int lcm(int a,int b) {return a/gcd(a,b)*b; }
ll prime(ll x) {for(ll i=2;i<=sqrt(x+0.5);i++) if(x%i==0) return 0; return 1; }
int read()
{
    int s=0,f=1;
    char ch=getchar();
    while(ch<'0'&&ch>'9') {if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {s=s*10+ch-'0'; ch=getchar();} return s*f;
}
set<ll> st;
vector<ll> vec;


int main()
{
    iosks;
    string s;
    cin>>s;
    cout<<s[0]<<s[1]<<s[2]<<endl;
    return 0;
}


Measured memory_bytes: 3640
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define loop(i, a, b) for(lli i=a; i<b; i++)
#define loopb(i, a, b) for(lli i=a; i>=b; i--)
#define fastio ios_base::sync_with_stdio(false); cin.tie(0)
#define pb push_back
typedef long long int lli;
typedef pair<lli, lli> pii;
typedef vector<lli> vll;
#define umap unordered_map
#define all(x) x.begin(), x.end()
// use to avoid collision
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
// for pair in unordered_map
struct hash_pair {
    template <class T1, class T2>
    size_t operator()(const pair<T1, T2>& p) const
    {
        auto hash1 = hash<T1>{}(p.first);
        auto hash2 = hash<T2>{}(p.second);
        return hash1 ^ hash2;
    }
};
lli M = 1e9 + 7;
lli power(lli x, lli y){
    lli res = 1;
    x = x%M ;
    while (y > 0) {
        if (y & 1)
            res = (res*x)%M ;
        y = y>>1;
        x = (x*x)%M ;
    }
    return res%M;
}
lli find_mex(vll& A){
    lli n = A.size();
    vll temp(n+2, 0);
    loop(i, 0, n)
        temp[A[i]] = 1;
    loop(i, 0, n+2){
        if(temp[i] == 0){
            return i;
        }
    }
    return n+2;
}
void print(vll& A){
    for(auto i : A)
        cout<<i<<" ";
    cout<<"\n";
}
lli solve(){
    // lli n;
    // cin>>n;
    // vll A(n);
    // loop(i, 0, n){
    //     cin>>A[i];
    // }
    // vll index;
    // lli curr_index = 0;
    // loop(k, 0, n){
    //     lli mn_index = k;
    //     lli mn_value = A[k];
    //     loop(i, k, n){
    //         if(mn_value > A[i]){
    //             mn_index = i;
    //             mn_value = A[i];
    //         }
    //     }
    //     if(A[k] == curr_index)
    //         continue;
    //     index.pb(mn_index);
    //     index.pb(k);
    //     A[mn_index] = find_mex(A);
    //     A[k] = curr_index;
    //     curr_index++;
    //     print(A);
    // }
    // lli cnt = index.size();
    // cout<<cnt<<"\n";
    // loop(i, 0, cnt)
    //     cout<<index[i]+1<<" ";
    // cout<<"\n";
    // return 0;
    lli n;
    cin>>n;
    vll A(n);
    loop(i, 0, n)
        cin>>A[i];
    lli ans = 0;
    if(n == 1){
        cout<<0<<"\n";
        return 0;
    }
    sort(A.begin(), A.end(), greater<lli>());
    ans += A[0];
    for(lli i=1; i<n/2; i++)
        ans += 2*A[i];
    if(n%2 == 1)
        ans += A[n/2];
    cout<<ans<<"\n";
    return 0;
}
int main(){
    fastio;
    lli t;
	// cin>>t;
    t = 1;
    while(t>0){ 
        t--;
        solve();
    }
}

Measured memory_bytes: 4752
H,W = map(int,(input().split()))
ans = [["#"]*(W+2) for _ in range(H+2)]
for i in range(H):
    a = list(input())
    ans[i+1][1:1+W] = a
for i in range(H+2):
    out = "".join(ans[i])
    print(out)

Measured memory_bytes: 38384
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
#include<bits/stdc++.h>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define pll pair<ll,ll>
#define pint pll
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

const int MAX = 510000;
const int MOD = 1e9+7;

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;
}

ll dp[200020],a[200020],aq[200020],ab[200020],q[200020],qb[200020],p[200020];

int main(){
  COMinit();
  string s;
  cin >> s;
  int n=s.size();
  ll Q=0;
  rep(i,n){
    if(i>0){
      a[i]=a[i-1];
    }
    if(s[i]=='A'){
      a[i]++;
    }
  }
  p[0]=1;
  rep(i,100010){
    p[i+1]=p[i];
    p[i+1]*=3;
    p[i+1]%=mod;
  }
  rep(i,n){
    if(i>0){
      q[i]=q[i-1];
    }
    if(s[i]=='?'){
      q[i]++;
    }
  }
  rep(i,n){
    if(i>0)ab[i]=ab[i-1];
    if(s[i]=='B'){
      ab[i]+=a[i];
      ab[i]%=mod;
    }
  }
  rep(i,n){
    if(i>0)qb[i]=qb[i-1];
    if(s[i]=='B'){
      qb[i]+=q[i];
      qb[i]%=mod;
    }
  }
  rep(i,n){
    if(i>0)aq[i]=aq[i-1];
    if(s[i]=='?'){
      aq[i]+=a[i];
      aq[i]%=mod;
    }
  }
  for(int i=2;i<n;i++){
    if(s[i]=='A' || s[i]=='B')dp[i]=dp[i-1];
    else if(s[i]=='C' || s[i]=='?'){
      if(s[i]=='C')dp[i]=dp[i-1];
      if(s[i]=='?')dp[i]=(3*dp[i-1])%mod;
      dp[i]%=mod;
      dp[i]+=(ab[i-1]*p[q[i-1]])%mod;
      dp[i]%=mod;
      if(q[i-1]-1>=0)dp[i]+=(p[q[i-1]-1]*aq[i-1])%mod;
      dp[i]%=mod;
      if(q[i-1]-1>=0)dp[i]+=(p[q[i-1]-1]*qb[i-1])%mod;
      dp[i]%=mod;
      if(q[i-1]>=2)dp[i]+=(COM(q[i-1],2)*p[q[i-1]-2])%mod;
      dp[i]%=mod;
    }
  }
  cout << dp[n-1] << endl;
return 0;}

Measured memory_bytes: 22528
using System;
using System.Text;
using System.Collections.Generic;
using System.Linq;
class Solve{
    public Solve(){}
    StringBuilder sb;
    public static int Main(){
        new Solve().Run();
        return 0;
    }
    void Run(){
        sb = new StringBuilder();
        Calc();
        Console.Write(sb.ToString());
    }
    void Calc(){
        int N = int.Parse(Console.ReadLine());
        double[,] DP = new double[N-1,N-1];
        double[] X = new double[N];
        double[] Y = new double[N];
        for(int i=0;i<N;i++){
            string[] str = Console.ReadLine().Split(' ');
            double x = int.Parse(str[0]);
            double y = int.Parse(str[1]);
            X[i] = x;
            Y[i] = y;
        }
        for(int i=1;i<N-1;i++){
            for(int j=0;j<i;j++){
                DP[i,j] = DP[i-1,j] + Distance(X[i-1],Y[i-1],X[i],Y[i]);
            }
            DP[i,i] = DP[i-1,0] + Distance(X[0],Y[0],X[i],Y[i]);
            for(int j=1;j<i;j++){
                DP[i,i] = Math.Min(DP[i,i],DP[i-1,j] + Distance(X[j-1],Y[j-1],X[i],Y[i]));
            }
        }
        double min = DP[N-2,0] + Distance(X[0],Y[0],X[N-1],Y[N-1]);
        for(int i=1;i<N-1;i++){
            min = Math.Min(min,DP[N-2,i]+Distance(X[i-1],Y[i-1],X[N-1],Y[N-1]));
        }
        min += Distance(X[N-2],Y[N-2],X[N-1],Y[N-1]);
        sb.Append(min+"\n");
    }
    double Distance(double x1,double y1,double x2,double y2){
        return Math.Sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
    }
}

Measured memory_bytes: 17144
#include <bits/stdc++.h>
#define N 13
using namespace std;
typedef long long ll;
bool used[N];
  
ll SumD(ll a,ll d,ll n){return (n*(2*a+(n-1)*d))/2;}
  
bool mark(ll n){
  bool res=1;
  for(ll i=1;i*i<=N;i++)res&=!used[i],used[i]=1;
  return res;
}
  
int main(){
  while(1){
    ll n,m,p[21];
    cin>>n>>m;
    if(!n&&!m)break;
    for(int i=0;i<m;i++)cin>>p[i];
    sort(p,p+m);
    
    ll sum=0,cnt=0;
    for(int i=0;i<m;i++){
      sum+=SumD(p[i],p[i],n/p[i]);
      cnt+=n/p[i];
      memset(used,0,sizeof(used));
      for(int j=0;j<i;j++){
    ll lcm=(p[i]/__gcd(p[i],p[j]))*p[j];
    if(!mark(lcm))continue;
    sum-=SumD(lcm,lcm,n/lcm);
    cnt-=(n/lcm);
      }
    }
    printf("%.8f\n",(1.0*SumD(1,1,n)-sum)/max(1LL,(n-cnt)));
  }
  return 0;
}

Measured memory_bytes: 3172
#include "bits/stdc++.h"
using namespace std;
using ll     = long long;
using pii    = pair<int, int>;
using pll    = pair<ll, ll>;
using vi     = vector<int>;
using vl     = vector<ll>;
using vvi    = vector<vi>;
using vvl    = vector<vl>;
const ll INF = 1LL << 60;
const ll MOD = 1000000007;
template <class T>
bool chmax(T &a, const T &b) {
    return (a < b) ? (a = b, 1) : 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    return (b < a) ? (a = b, 1) : 0;
}
template <class C>
void print(const C &c, std::ostream &os = std::cout) {
    std::copy(std::begin(c), std::end(c), std::ostream_iterator<typename C::value_type>(os, " "));
    os << std::endl;
}

int main() {
    ll n, k;
    cin >> n >> k;
    vl a(n);
    ll ret = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        ret += a[i];
    }
    vi bits(41, 0);
    for (int i = 0; i < n; ++i) {
        ll t    = a[i];
        int idx = 0;
        while (t != 0) {
            bits[idx] += t % 2;
            t >>= 1;
            idx++;
        }
    }
    bool ok = false;
    for (int i = 40; i >= 0; --i) {
        if (bits[i] < n / 2 || (n % 2 != 0 && bits[i] == n / 2)) {
            if (((1LL << i) & k) || ok) {
                ret += (1LL << i) * (n - 2 * bits[i]);
            }
        } else {
            if ((1LL << i) & k)
                ok = true;
        }
    }
    cout << ret << "\n";
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;

int main() {
	int N; cin >> N;
	vector<int> cnt(N);
	fill(cnt.begin(), cnt.end(), 0);
	for (int i = 0; i < N; i++) {
		int a;   cin >> a;
		cnt[a]++;
	}

	bool possible = true;
	if (N % 2 == 0) {
		for (int i = 1; i < N; i += 2) {
			if (cnt[i] != 2) {
				possible = false;
				break;
			}
		}
	} else {
		if (cnt[0] != 1) {
			possible = false;
		} else {
			for (int i = 2; i < N; i += 2) {
				if (cnt[i] != 2) {
					possible = false;
					break;
				}
			}
		}
	}

	if (!possible) {
		cout << 0 << endl;
		return 0;
	}

	ll ans = 1;
	for (int i = 1; i <= N / 2; i++) {
		ans = (ans * 2) % mod;
	}

	cout << ans << endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
 
using namespace std;
 
#define endl '\n'
#define f first
#define s second
#define pb push_back
#define all(c) (c).begin(), (c).end()
#define sz(x) (int)(x).size()
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define debug(...) cout << " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] " << endl

using ld = long double;
using ll = long long;
using pii = pair <int,int>;
using pll = pair <ll,ll>;
using vi = vector <int>;
using vll = vector <ll>;
using vpii = vector <pii>;
using vpll = vector<pll>;
using vs = vector <string>;


int main(){
  fastio;

  ll a,b,c,d;
  cin >> a  >> b >> c >> d;

  cout << max({a*c,a*d,b*c,b*d}) << endl;
  return 0;
}

Measured memory_bytes: 3648
#include<iostream>
using namespace std;
const long mod=1e9+7;
long power(long a,long b){return b?power(a*a%mod,b/2)*(b%2?a:1)%mod:1;}
int N;
int A[1<<17];
int ex[1<<17];
long F[1<<17],I[1<<17];
long comb(int a,int b){return a<0||b<0||a<b?0L:F[a]*I[b]%mod*I[a-b]%mod;}
main()
{
	cin>>N;
	int w;
	for(int i=0;i<=N;i++)
	{
		cin>>A[i];
		if(ex[A[i]]==0)ex[A[i]]=i+1;
		else
		{
			w=i-(ex[A[i]]-1)+1;
		}
	}
	F[0]=1;
	for(int i=1;i<1<<17;i++)F[i]=F[i-1]*i%mod;
	I[(1<<17)-1]=power(F[(1<<17)-1],mod-2);
	for(int i=(1<<17)-1;i--;)I[i]=I[i+1]*(i+1)%mod;
	for(int k=1;k<=N+1;k++)
	{
		cout<<(comb(N+1,k)-comb(N+1-w,k-1)+mod)%mod<<endl;
	}
}


Measured memory_bytes: 4096
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <ctime>
#include <cstring>
#include <functional>
#include <iostream>
#include <iomanip>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <regex>
#include <vector>

#define fix(n)          cout<<fixed<<setprecision(n)
#define rep(i,n)        for (int i = 0; i < (n); ++i)
#define all(a)          (a).begin(), (a).end()
#define sort(a)         sort(all(a))
#define uniq(a)         sort(a);(a).erase(unique(all(a), (a).end())
#define reverse(a)      reverse(all(a))
#define ctos(c)         string(1, (c))
#define out(d)          cout << (d)
#define outl(d)         std::cout<<(d)<<"\n"
#define YES()           cout << "YES" << endl
#define NO()            cout << "NO" << endl
#define Yes()           cout << "Yes" << endl
#define No()            cout << "No" << endl
#define ceil(x, y)      ((x + y - 1) / (y))
#define debug(x)        cerr << #x << ": " << (x) << '\n'
#define debug2(x, y)    cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << '\n'
#define debug3(x, y, z) cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << ", " << #z << ": " << (z) << '\n'
#define dbg(v)          for (size_t _ = 0; _ < v.size(); ++_){ cerr << #v << "[" << _ << "] : " << v[_] << '\n'; }
#define pb              push_back
#define fst             first
#define int             long long

using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll,ll>;

const ll MOD = 1000000007; // 10^9 + 7
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

void solve() {
  string s, t; cin >> s >> t;

  if (t.size() > s.size()) {
    outl("UNRESTORABLE");
    return;
  }

  for (int i = s.size() - t.size(); i >= 0; i--) {
    bool ok = true;
    for (int j = 0; j < t.size(); j++) {
      if (s[i + j] == '?') continue;
      if (s[i + j] != t[j]) {
        ok = false;
        break;
      }
    }
    if (ok) {
      for (int j = 0; j < t.size(); j++) {
        // debug2(i, j);
        s[i + j] = t[j];
      }
      for (int j = 0; j < s.size(); j++) {
        if (s[j] == '?') {
          // debug(j);
          s[j] = 'a';
        }
      }
      outl(s);
      return;
    }
  }
  outl("UNRESTORABLE");
}

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  srand((unsigned)time(NULL));
  fix(12);

  solve();
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct Node {
	Node() {
		c = -1;
		for (int i = 0; i < 26; ++i) {
			nxt[i] = nullptr;
			cnt[i] = 0;
		}
		isend = false;
		tot = 0;
	}

	int c;
	Node* nxt[26];
	int cnt[26];
	bool isend;
	int tot;
};

void add(Node* root, const string& s) {
	Node* cur = root;
	for (int i = 0; i < s.length(); ++i) {
		int c = s[i] - 'a';
		if (cur->nxt[c]) {
			cur = cur->nxt[c];
		} else {
			Node* p = new Node();
			cur->nxt[c] = p;
			cur = cur->nxt[c];
		}
		cur->c = c;
	}
	cur->isend = true;
}

void dfs(Node* v, string& path) {
	if (!v) {
		return;
	}
	if (v->isend) {
		v->tot = 1;
	}
	for (int i = 0; i < 26; ++i) {
		if (v->nxt[i]) {
			path += 'a' + v->nxt[i]->c;
			dfs(v->nxt[i], path);
			path.pop_back();
			v->tot += v->nxt[i]->tot;
			for (int j = 0; j < 26; ++j) {
				if (i != j) {
					v->cnt[j] += v->nxt[i]->cnt[j];
				}
			}
			v->cnt[i] += v->nxt[i]->tot;
		}
	}
}

long long res = 0;

void dfs2(Node* cur, Node* prev = nullptr) {
	if (!cur) {
		return;
	}

	if (prev && cur->isend) {
		res += (cur->tot - 1);

		res += (prev->cnt[cur->c] - cur->tot);
	}

	for (int i = 0; i < 26; ++i) {
		if (cur->nxt[i]) {
			dfs2(cur->nxt[i], cur);
		}
	}
}

void solve() {
	int n;
	cin >> n;
	Node* root = new Node();

	for (int i = 0; i < n; ++i) {
		string s;
		cin >> s;
		reverse(s.begin(), s.end());
		add(root, s);
	}

	string curs;
	dfs(root, curs);
	dfs2(root);
	cout << res << endl;
}

int main() {
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	ios_base::sync_with_stdio(false);

	int t;
	//cin >> t;
	t = 1;

	for (int tt = 0; tt < t; ++tt) {
		solve();
	}


	return 0;
}

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

long long GCD(long long x, long long y) {
    if(y == 0) return x;
    else return GCD(y, x % y);
}
long long NUM(long long n, long long c, long long d) {
    long long G = GCD(c, d);
    long long L = c / G * d;
    
    return n - n / c - n / d + n / L;
}

int main() {
    long long a, b, c, d;
    cin >> a >> b >> c >> d;
    
    cout << NUM(b, c, d) - NUM(a-1, c, d) << endl;
}


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

int main()
{
  int n;
  cin>>n;
  while(true)
  {
    if(n>1000)
      n-=1000;
    else
    {
      n=1000-n;
      break;
    }
  }
  cout<<n<<endl;
}

Measured memory_bytes: 3568
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<vector>
#include<list>
#include<functional>
#include<algorithm>
#include<string>
#include<cmath>
#include<complex>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<tuple>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;



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

	int N;
	cin >> N;
	vector<int> a(N);
	REP(i, N) cin >> a[i];
	sort(a.begin(), a.end(), greater<int>());
	int res = 0;
	REP(i, N) {
		if (i % 2 == 0) res += a[i];
		else res -= a[i];
	}
	cout << res << "\n";

	return 0;
}

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

//{ START
using namespace std;
#define int int64_t
#define rep(i, a, n) for (int i = (a); i < (n); ++i)
#define reps(i, a, n) for (int i = (a); i > (n); --i)
#define arep(i, x) for (auto &&i : (x))
#define irep(i, x) for (auto i = (x).begin(); i != (x).end(); ++i)
//降順はgreater<T>()
#define all(x) (x).begin(), (x).end()
#define rv(s) reverse((s).begin(), (s).end())
// gcd lcmはそのままok
#define gcd(a, b) __gcd(a, b)
#define bits(n) (1LL << (n))
#define pcnt(x) __builtin_popcountll(x)
//配列内等要素削除
#define unique(x) (x).erase(unique((x).begin(), (x).end()), (x).end())
#define Fixed(n) fixed << setprecision(n)
//総和
#define sowa(n) ((n) * ((n) + 1)) / 2
#define pb(x, a) (x).push_back(a)
#define fb(x, a) (x).push_front(a)
#define eb(x, a) (x).emplace_back(a)
#define F first
#define S second
#define cauto const auto &
using P = pair<int, int>;
using Graph = vector<vector<P>>;
template <class T>  //昇順
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template <class T>  //降順
using max_heap = priority_queue<T>;
template <class A, class B>
using umap = unordered_map<A, B>;
template <class A>
using uset = unordered_set<A>;
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val) {  //多次元初期化
  std::fill((T *)array, (T *)(array + N), val);
}
template <class T>
bool chmax(T &a, const T &b) {  //最大値更新 返り値はbool
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
bool chmin(T &a, const T &b) {  //最小値更新 返り値はbool
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
constexpr int INF = 0x3f3f3f3f;
constexpr int LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int mod1 = 1e9 + 7;
constexpr int mod2 = 998244353;
//} END

/* BIT: 区間和の更新や計算を行う構造体
初期値は a_1 = a_2 = ... = a_n = 0
add(i,x): a_i += x とする
sum(i): a_1 + a_2 + ... + a_i を計算する
計算量は全て O(logn)
*/
template <typename T>
struct BIT {
  int n;          // 配列の要素数(数列の要素数+1)
  vector<T> bit;  // データの格納先
  BIT(int n_) : n(n_ + 1), bit(n, 0) {}

  void add(int i, T x) {
    for (int idx = i; idx < n; idx += (idx & -idx)) bit[idx] += x;
  }

  T sum(int i) {
    T s(0);
    for (int idx = i; idx > 0; idx -= (idx & -idx)) s += bit[idx];
    return s;
  }
};

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

  int n,q;
  cin>>n>>q;
  BIT<int> bit(n);

  rep(i,0,q){
    int c,x,y;
    cin>>c>>x>>y;
    if(c==1){
      cout<<bit.sum(y)-bit.sum(x-1)<<'\n';
    }else{
      bit.add(x,y);
    }
  }

  return 0;
}


Measured memory_bytes: 3612
/**
 *    author:  tourist
 *    created: 02.06.2019 15:53:37       
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, a, b, c, d;
  cin >> n >> a >> b >> c >> d;
  a--; b--; c--; d--;
  string s;
  cin >> s;
  function<bool(int, int)> CanGo = [&](int from, int to) {
    while (from < to) {
      if (s[from + 1] == '.') {
        ++from;
      } else {
        if (s[from + 2] == '.') {
          from += 2;
        } else {
          return false;
        }
      }
    }
    return true;
  };
  auto HasGoodPos = [&](int from, int to) {
    for (int i = from; i <= to; i++) {
      if (s[i] == '.' && s[i - 1] == '.' && s[i + 1] == '.') {
        return true;
      }
    }
    return false;
  };
  if (CanGo(a, c) && CanGo(b, d)) {
    if (c < d || HasGoodPos(b, d)) {
      cout << "Yes" << '\n';
      return 0;
    }
  }
  cout << "No" << '\n';
  return 0;
}


Measured memory_bytes: 592
dic = {"0":0,"1":1,"2":2}
while 1:
	worm = raw_input()
	if worm == "0": break
	worm = worm.replace("r","0").replace("g","1").replace("b","2")
	n = len(worm)
	ref = ["0"*n,"1"*n,"2"*n]
	done = [1]*(3**n)
	done[int(worm,3)] = 0
	cnt = flag = 0
	nxtque = [worm]
	while 1:
		que = nxtque
		nxtque = []
		for Worm in que:
			if Worm in ref:
				flag = 1
				break
			for i in range(n-1):
				if Worm[i] != Worm[i+1]:
					nextclr = "012"[3-dic[Worm[i]]-dic[Worm[i+1]]]
					worm = Worm[:i] + 2*nextclr + Worm[i+2:]
					num = int(worm,3)
					if done[num]:
						done[num] = 0
						nxtque.append(worm)
		if flag or len(nxtque) == 0: break
		cnt += 1
	print cnt if flag else "NA"

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

void print(string str, int a,int b) 
{
	for (int i = a; i <= b; i++)
		cout << str[i];

	cout << '\n';
}

string reverse(string str, int a, int b)
{
	string buff;
	for (int i = a; i <= b; i++)
		buff[i-a] = str[i];


	char buff2;
	for (int i = 0; i < (int)(b-a+1)/2; i++) {
		buff2 = buff[i];
		buff[i] = buff[(b-a)-i];
		buff[(b-a)-i] = buff2;
	}

	for (int i = a; i <= b; i++)
		str[i] = buff[i-a];


	return str;

}

string replace(string str, string p_str, int a, int b)
{
	for (int i = a; i <= b; i++)
		str[i] = p_str[i-a];

	return str;

}

int main()
{
	string str;
	int m;
	int count = 0;

	cin >> str;
	cin >> m;

	while (count != m) {
		string order;
		cin >> order;

		if (order == "print") {
			int a,b;
			cin >> a >> b;
			print(str, a, b);
			count++;
		} else if (order == "reverse") {
			int c,d;
			cin >> c >> d;
			str = reverse(str, c, d);
			count++;
		} else if (order == "replace") {
			int e,f;
			cin >> e >> f;
			string p_str;
			cin >> p_str;
			str = replace(str, p_str, e, f);
			count++;
		}
	}
	return 0;
}


Measured memory_bytes: 3240
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define bit(n) (1<<(n))
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<bool> vb;
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; }
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}
int const INF = 1001001001;


// modint: mod 計算を int を扱うように扱える構造体
template<int MOD> struct Fp {
long long val;
constexpr Fp(long long v = 0) noexcept : val(v % MOD) {
if (val < 0) val += MOD;
}
constexpr int getmod() { return MOD; }
constexpr Fp operator - () const noexcept {
return val ? MOD - val : 0;
}
constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
constexpr Fp& operator += (const Fp& r) noexcept {
val += r.val;
if (val >= MOD) val -= MOD;
return *this;
}
constexpr Fp& operator -= (const Fp& r) noexcept {
val -= r.val;
if (val < 0) val += MOD;
return *this;
}
constexpr Fp& operator *= (const Fp& r) noexcept {
val = val * r.val % MOD;
return *this;
}
constexpr Fp& operator /= (const Fp& r) noexcept {
long long a = r.val, b = MOD, u = 1, v = 0;
while (b) {
long long t = a / b;
a -= t * b; swap(a, b);
u -= t * v; swap(u, v);
}
val = val * u % MOD;
if (val < 0) val += MOD;
return *this;
}
constexpr bool operator == (const Fp& r) const noexcept {
return this->val == r.val;
}
constexpr bool operator != (const Fp& r) const noexcept {
return this->val != r.val;
}
friend constexpr ostream& operator << (ostream &os, const Fp<MOD>& x) noexcept {
return os << x.val;
}
friend constexpr Fp<MOD> modpow(const Fp<MOD> &a, long long n) noexcept {
if (n == 0) return 1;
auto t = modpow(a, n / 2);
t = t * t;
if (n & 1) t = t * a;
return t;
}
};

const int MOD = 1000000007;
using mint = Fp<MOD>;

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

ll N; cin >> N;
string s,t;
cin >> s >> t;

string v = "";

int i = 0;
while(i < N) {
    if(s[i] == t[i]) {
        v.push_back('1');
        i += 1;
    }
    else {
        v.push_back('2');
        i += 2;
    }
}

int L = SZ(v);
mint ans;
if(v[0] == '1') ans = 3;
else ans = 6;

for(int i = 1; i < L; ++i) {
    if(v[i-1] == '1') ans *= 2;
    else if(v[i] == '2') ans *= 3;
}

cout << ans << endl;
return 0;
}

Measured memory_bytes: 256