akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define eps 1e-10
#define MAXN 2005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;T f = 1;char c = getchar();
    while(c < '0' || c > '9') {
    	if(c == '-') f = -1;
    	c = getchar();
    }
    while(c >= '0' && c <= '9') {
    	res = res * 10 +c - '0';
    	c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) {
	out(x / 10);
    }
    putchar('0' + x % 10);
}
struct node {
    int to,next;
}E[MAXN * 2];
int N,M,sumE,head[MAXN],dis[MAXN][MAXN];
int fa[MAXN][MAXN];
bool vis[MAXN][MAXN];
bool g[MAXN][MAXN];
set<int> S[MAXN];
void add(int u,int v) {
    E[++sumE].to = v;
    E[sumE].next = head[u];
    head[u] = sumE;
}
void dfs(int id,int u) {
    for(int i = head[u] ; i ; i = E[i].next) {
        int v = E[i].to;
        if(v != fa[id][u]) {
            fa[id][v] = u;
            dis[id][v] = dis[id][u] + 1;
            dfs(id,v);
        }
    }
}
vector<int> getline(int a,int b) {
    vector<int> res;
    while(a != b) {
        res.pb(a);
        a = fa[b][a];
    }
    res.pb(b);
    return res;
}
void build(int a,int b) {
    vis[a][b] = vis[b][a] = 1;
    S[a].insert(b);S[b].insert(a);
}
void destroy(int a,int b) {
    vis[a][b] = vis[b][a] = 0;
    S[a].erase(b);S[b].erase(a);
}
void AddE(int a,int b) {
    if(vis[a][b]) return;
    vector<int> v = getline(a,b);
    int s = v.size() - 1;
    int f = a,t = b,q = 0;
    for(int i = 0 ; i < s ; ++i) {
        if(vis[f][v[i]]) {f = v[i];q = i;}
    }
    for(int i = s - 1 ; i >= q ; --i) {
        if(vis[t][v[i]]) t = v[i];
    }
    if(t == a) return;
    v.clear();
    if(vis[f][t]) return;

    vector<pii> E;
    for(auto k : S[f]) {
        if(dis[f][k] == dis[f][t] + dis[t][k]) {
            E.pb(mp(t,k));
            v.pb(k);
        }
    }
    for(auto k : v) destroy(k,f);
    v.clear();
    for(auto k : S[t]) {
        if(dis[t][k] == dis[t][f] + dis[f][k]) {
            E.pb(mp(f,k));
            v.pb(k);
        }
    }
    for(auto k : v) destroy(k,t);
    v.clear();
    build(f,t);
    for(auto k : E) {
        AddE(k.fi,k.se);
    }
}
void find(int id,int u) {
    g[id][u] = 1;
    for(auto t : S[u]) {
        if(g[id][t]) continue;
        if(dis[t][id] == dis[id][u] + dis[u][t]) find(id,t);
    }
}
void Solve() {
    read(N);read(M);
    int a,b;
    for(int i = 1 ; i < N ; ++i) {
        read(a);read(b);
        add(a,b);add(b,a);
    }
    for(int i = 1 ; i <= N ; ++i) dfs(i,i);
    for(int i = 1 ; i <= M ; ++i) {
        read(a);read(b);
        AddE(a,b);
    }
    int ans = 0;
    for(int i = 1 ; i <= N ; ++i) {
        find(i,i);
        for(int j = i + 1 ; j <= N ; ++j) if(g[i][j]) ++ans;
    }
    out(ans);enter;
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    Solve();
    return 0;
}


Measured memory_bytes: 39936
#include<bits/stdc++.h> 
using namespace std; 
#define M 1e9+7
#define int long long
#define lli long long int
#define I 10e5

int32_t main() 
{ 
   ios_base::sync_with_stdio(false);cin.tie(NULL); 
   
   #ifndef ONLINE_JUDGE 
   freopen("input.txt", "r", stdin);
   freopen("output.txt", "w", stdout); 
   #endif
   int n, w;
   cin>>n>>w;
   int sum = 0;
   int prev, curr;
   vector<int> wt(n), v(n);
   for(int i=0;i<n;i++)
   {
      cin>>wt[i]>>v[i];
   }
   int dp[n+1][w+1];
   for(int i=0;i<=n;i++)
   {
      dp[i][0] = 0;
   }
   for(int i=0;i<=w;i++)
   {
      dp[0][i] = 0;
   }
   for(int i=1;i<=n;i++)
   {
      for(int j=0;j<=w;j++)
      {
         if(wt[i-1]<=j)
         {
            dp[i][j] = max(dp[i-1][j], v[i-1] + dp[i-1][j-wt[i-1]]);
         }
         else
         {
            dp[i][j] = dp[i-1][j];
         }
      }
   }
   cout<<dp[n][w]<<endl;
   cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" secs"<<endl; 
   return 0; 
}

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


int main() {

  int N, K;
  cin >> N >> K;

  long long answer = 0;

  for (int b = 1; b <= N; b++) {
    int p = N / b;
    int r = N % b;
    answer += (long long) p * max(0, b - K);
    answer += max(0, (r - K + 1));
    if (K == 0) {
      answer -= 1;
    }
  }

  cout << answer << endl;

}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
    int N, M;
    cin >> N;
    cin >> M;
    int K[N];
    int A[N][M];
    for(int i=0; i<N; i++){
        cin >> K[i];
        for(int j=0; j<K[i]; j++){
            cin >> A[i][j];
        }
    }
    int r=0;
    int f=0;
    for(int i=1; i<=M; i++){
        for(int j=0; j<N; j++){
            f = 0;
            for(int l=0; l<K[j]; l++){
                if(A[j][l] == i){
                    f = 1;
                    break;
                }
            }
            if(f == 0) break;
        }
        if(f) r++;
    }
    cout << r << endl;
    return 0;
}

Measured memory_bytes: 256
using System;
using static System.Console;
using System.Collections;

namespace WalkOnMultiplicationTable
{
    class Program
    {
        static void Main(string[] args)
        {
            var n = long.Parse(ReadLine());
            var ans = n;
            for(int i = 1; i <= Math.Sqrt(n); i++){
                if(n % i == 0){
                    ans = i + n / i - 2; 
                }
            }
            WriteLine(ans);
        }
    }
}


Measured memory_bytes: 13140
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int a,b,c,d;
  int t;
  cin >> a >> b >> c >> d;
  if (b <= c || d <= a ){
     t = 0;

  }
  else {
    t = min(b,d) - max(a,c);
  }
  cout << t <<endl;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(){
    int m,f,r;
    while(true){
        scanf("%d %d %d",&m,&f,&r);
        int score = m + f;
        if(m == -1 && f == -1 && r == -1) break;
        else if(m == -1 || f == -1) printf("F\n");
        else if(score >= 80) printf("A\n");
        else if(score >= 65) printf("B\n");
        else if(score >= 50 || r >= 50) printf("C\n");
        else if(score >= 30) printf("D\n");
        else printf("F\n");
    }
}


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

int main(){
  string a,b;
  cin >> a >> b;
  
  if(a == b) cout << "EQUAL" << endl;
  else if(a.size() > b.size()) cout << "GREATER" << endl;
  else if(a.size() < b.size()) cout << "LESS" << endl;
  else {
    vector<string> c ={a,b};
    sort(c.begin(),c.end());
    if(c.at(0) == a) cout << "LESS" << endl;
    else cout << "GREATER";
  }
  
}

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


using namespace std;

vector<int> a(100001, 0);

int main(){
	int N;
	int l, r;
	int total = 0;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> l >> r;
		total += (r - l) + 1;
	}
	cout << total << endl;

	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
#include <iomanip>
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; }
const int INF=1001001001;
vector<pair<int64_t,int64_t>>pppp(int64_t x){
  vector<pair<int64_t,int64_t>>p;
  for(int64_t i=2;i*i<=x;i++){
    int cnt=0;
    if(x%i==0){
    while(x%i==0){cnt++;x/=i;}
    p.push_back(make_pair(i,cnt));
    }
  }
  if(x!=1){p.push_back(make_pair(x,1));}
  return p; 
}
 
int main() {
 int N;
 cin>>N;

 cout<<(N+999)/1000*1000-N<<endl;
 return 0;
}

Measured memory_bytes: 3640
from itertools import accumulate


N, *A = map(int, open(0).read().split())
MOD = 1_000_000_007
acc = list(accumulate(A, initial=0))

ans = 0
for i in range(N - 1):
    ans += A[i] * (acc[N] - acc[i + 1])
    ans %= MOD
print(ans)


Measured memory_bytes: 31724
#include<cstdio>

int main()
{
	int n;
	scanf("%d", &n);

	int ai[n];

	for (int i = 0; i < n; i++) 
		scanf("%d", &ai[i]);

	for (int i = n-1; i >= 0; i--) {

		printf("%d", ai[i]);
			
			if (i != 0)
				printf(" ");
	}

	printf("\n");

	return 0;
}


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

typedef vector<int> vi;
typedef pair<int, int> pi;

const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;

#define pb push_back
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REP2(i, b, e) for (int i = (b); i <= (int)(e); i++)
#define DEBUG(x) cout << #x << ": " << (x) << endl
#define DEBUGA(a) cout << #a << ": "; for (const auto& v: (a)) cout << v << endl

signed main() {
    int N; cin >> N;
    vi A(N);
    priority_queue<int> Q;
    REP(i, N) {
        cin >> A[i];
        Q.push(A[i]);
    }

    REP(i, N) {
        if (A[i] == Q.top()) {
            Q.pop();
            cout << Q.top() << endl;
            Q.push(A[i]);
        } else {
            cout << Q.top() << endl;
        }
    }

    return 0;
}


Measured memory_bytes: 3316
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long int
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define mem(x,y) memset(x,y,sizeof(x))//memset only use to initialize 0 or -1 no other number.
#define pii pair<int,int>
#define pll pair<ll,ll>
#define INF 1e9
#define INFL 1e18
#define mod 1000000007
//#define mod 998244353
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
using namespace __gnu_pbds; 
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> os;
typedef tree<pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update> os_pair;

ll power(ll x,ll n){ll res =1;while(n>0){if(n%2==1){res=res*x;}x=x*x;n=n/2;}return res;}
ll powm(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}

//cout<< fixed << setprecision(10)

int main(){

    fast;
    int n;
    cin>>n;
    cout<<n+n*n+n*n*n;
    
}

Measured memory_bytes: 3608
#include <bits/stdc++.h>
#define ll long long
#define li long int
#define ld long double
#define pl pair<long long, long long>
#define pi pair<int, int>
#define ppl pair<pl, ll>
#define ppi pair<int, pi>
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define LLFOR(i,a,b) for(ll i=a;i<b;i++)
#define fi first
#define se second
#define MOD 1000000007
#define M2 998244353
//std::cout <<setprecision(30) << av << endl;
using namespace std;
//int a[200000];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t=1;
    //cin >> t;
    while(t--){
        int n;
        cin >> n;
        vector<int> ch(n, 0);
        int f;
        FOR(i, 1, n){
            cin >> f;
            ch[f-1]++;
        }
        FOR(i, 0, n){
            cout << ch[i] << endl;
        }




    }
}


Measured memory_bytes: 3996
#include<bits/stdc++.h>
using namespace std;
int main() {
  long long n, k, q;
  cin >> n >> k >> q;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    a[i] = 0;
  }
  for (int i = 0; i < q; i++) {
    int j;
    cin >> j;
    a[j-1]++;
  }
  for (int i = 0; i < n; i++) {
    if (k <= q - a[i]) {
      cout << "No" << endl;
    } else {
      cout << "Yes" << endl;
    }
  }
}

Measured memory_bytes: 3788
import java.util.Scanner;
public class Main {
			  public static void main(String[]args){
			    Scanner sc = new Scanner(System.in);
			    while(true) {
			    int H = sc.nextInt();
			    int W = sc.nextInt();
			    if(H == 0 && W == 0) break;
		              for(int i = 0;i < H;++i) {
		            	 for(int j = 0;j < W;++j){
		            		 if(i%2 == 0 && j%2 == 0) {
		            		  System.out.print("#");
		            		  }
		            		 if(i%2 == 0 && j%2 == 1) {
		            		  System.out.print(".");
		            	  }
		            		 if(i%2 == 1 && j%2 == 0) {
		            	      System.out.print(".");
		            		 }
		            		 if(i%2 == 1 && j%2 == 1) {
		            	  System.out.print("#");
		            	  }
		            	 }
		        System.out.println("");
			    	  }
                        System.out.println("");
			    }
			    	sc.close();   
			    
			  }
			}
	


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

using namespace std;
using ll = long long;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  ll a, b, c;
  cin >> a >> b >> c;
  ll can = a - b;
  cout << max(0LL, c - can) << '\n';
  return 0;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-

INF = 999999999
n = int(input())

coins = [1]

s = 9
while s<=n:
    coins.append(s)
    s *= 9

s = 6
while s<=n:
    coins.append(s)
    s *= 6

coins.sort(reverse=True)

dp = [INF for _ in range(n+1)]
dp[0] = 0

for i in range(1,n+1):
    for c in coins:
        if i-c>=0:
            dp[i] = min(dp[i], dp[i-c]+1)

print(dp[-1])


Measured memory_bytes: 3864
import java.util.HashMap;
import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        String s = sc.next();
        String t = sc.next();
        
        HashMap<Character, Character> mapST = new HashMap<>();
        HashMap<Character, Character> mapTS = new HashMap<>();
        String ans = "Yes";
        for(int i = 0; i < s.length(); i++){
            if(mapST.containsKey(s.charAt(i))){
                if(mapST.get(s.charAt(i)) != t.charAt(i)){
                    ans = "No";
                    break;
                }
            }else{
                mapST.put(s.charAt(i), t.charAt(i));
            }
            if(mapTS.containsKey(t.charAt(i))){
                if(mapTS.get(t.charAt(i)) != s.charAt(i)){
                    ans = "No";
                    break;
                }
            }else{
                mapTS.put(t.charAt(i), s.charAt(i));
            }
        }
        System.out.println(ans);
    }
}

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

int main()
{
    ll N,M;
    cin >> N >> M;
    vector<ll> L(M),R(M);

    for(int i = 0; i < M; i++)
    {
        cin >> L.at(i) >> R.at(i);
    }

    sort(L.begin(),L.end());
    ll left = L.at(M-1);
    sort(R.begin(),R.end());
    ll right = R.at(0);

    if(right - left < 0)cout << 0 << endl;
    else cout << right - left + 1 << endl;
}

Measured memory_bytes: 1792
// abc104_b
#include <bits/stdc++.h>
#ifdef LOCAL
#include "../cxx-prettyprint/prettyprint.hpp"
#endif
using namespace std;

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

#define REP(i, n) for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n) for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define REP_REV(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (int (i) = (int)(n) - 1 ; (i) >= m ; --(i))
#define ALL(x) x.begin(), x.end()

#define INF ((1 << 29)-1)
#define MOD (1000000007)

#define print2D(h, w, arr) REP(i, h) { REP(j, w) cout << arr[i][j] << " "; cout << endl; }
#define print_line(vec, n) {for(int i=0;i<(n-1);i++) cout << (vec)[i] << " "; cout << (vec)[(n)-1] << endl;}
template<class T> void print(const T& x){cout << x << endl;}
template<class T, class... A> void print(const T& first, const A&... rest) { cout << first << " "; print(rest...); }
struct PreMain {PreMain(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(20);}} premain;

int main() {
#ifdef LOCAL
    ifstream in("../arg.txt"); cin.rdbuf(in.rdbuf());
#endif

    string S;
    cin >> S;

    int n = S.size();

    bool b1 = (S[0] == 'A');

    bool b2 = S[1] != 'C' && S[n-1] != 'C';

    int cnt = 0;
    REPN(i, 2, n-1){
        if (S[i] == 'C') cnt++;
    }

    bool b3 = cnt == 1;

    bool b4 = true;
    REP(i, n){
        if (S[i] == 'A' || S[i] == 'C') continue;
        if (isupper(S[i])){
            b4 = false;
        }
    }

    if (b1 && b2 && b3 && b4){
        print("AC");
    } else {
        print("WA");
    }

    return 0;
}





Measured memory_bytes: 256
#include <stdio.h>

int main(void){
   int i,n,totalkagami=0,b[101];

   scanf("%d",&n);
   int kagami[n];
   for(i=0;i<n;i++)
      scanf("%d",&kagami[i]);

   for(i=0;i<=101;i++)
      b[i]=0;

   for(i=0;i<n;i++)
      b[kagami[i]]=1;

   for(i=1;i<101;i++)
      totalkagami+=b[i];

   printf("%d\n",totalkagami);
   return 0;
}

Measured memory_bytes: 128
#include <algorithm>
#include <climits>
#include <iostream>
#include <string>
#include <utility>
#include <vector>
#include <set>
#include <map>
#include <queue>


using namespace std;
using ll = long long int;

template <class T> ostream &operator<<(ostream &os, vector<T> &v) {
  for (auto i = v.begin(); i != v.end(); i++) {
    os << *i << " ";
  }
  return os;
}


void solve(long long N, std::vector<long long> a, std::vector<long long> b, std::vector<long long> c, long long Q, long long K, std::vector<long long> x, std::vector<long long> y){
  map<ll, vector<pair<ll, ll>>> m;
  vector<ll> v(N+1, 0);
  queue<ll> q;
  set<ll> s;
  q.push(K);
  for(int i=0; i<N-1; i++) {
    m[a[i]].push_back(make_pair(b[i], c[i]));
    m[b[i]].push_back(make_pair(a[i], c[i]));
  }
  while(!q.empty()) {
    ll node = q.front();
    s.insert(node);
    q.pop();
    for(auto &x: m[node]) {
      if(s.find(x.first) == s.end()) {
	v[x.first]=v[node]+x.second;	
	q.push(x.first);
      }
    }
  }
  for(int i=0; i<Q; i++) {
    std::cout << v[x[i]]+v[y[i]] << std::endl;
  }
}

int main(){
  long long N;
  scanf("%lld",&N);
  std::vector<long long> a(N-1);
  std::vector<long long> b(N-1);
  std::vector<long long> c(N-1);
  for(int i = 0 ; i < N-1 ; i++){
    scanf("%lld",&a[i]);
    scanf("%lld",&b[i]);
    scanf("%lld",&c[i]);
  }
  long long Q;
  scanf("%lld",&Q);
  long long K;
  scanf("%lld",&K);
  std::vector<long long> x(Q);
  std::vector<long long> y(Q);
  for(int i = 0 ; i < Q ; i++){
    scanf("%lld",&x[i]);
    scanf("%lld",&y[i]);
  }
  solve(N, std::move(a), std::move(b), std::move(c), Q, K, std::move(x), std::move(y));
  return 0;
}



Measured memory_bytes: 24064
#include <bits/stdc++.h>
#define ll long long int
#define MOD 1000000007
#define INF 1e18

using namespace std;

int main(void){
  ll n, q;
  cin >> n >> q;
  
  string s;
  cin >> s;
  
  vector<char> t(q), d(q);
  for (int i = 0; i < q; i++){
    cin >> t[i] >> d[i];
  }

  ll ans = n;
  ll l, r, m;
  l = -1, r = n;
  while (l + 1 < r){
    m = (l + r) / 2;
    ll cur = m;
    for (int i = 0; i < q; i++){
      if (s[cur] == t[i]){
        cur += (d[i] == 'R' ? 1 : -1);
      }
      if (cur == n)
        break;
      if (cur == -1)
        break;
    }
    if (cur == n)
      r = m;
    else
      l = m;
  }
  ans -= n - r;
  
  l = -1, r = n;
  while (l + 1 < r){
    m = (l + r) / 2;
    ll cur = m;
    for (int i = 0; i < q; i++){
      if (s[cur] == t[i]){
        cur += (d[i] == 'R' ? 1 : -1);
      }
      if (cur == n)
        break;
      if (cur == -1)
        break;
    }
    if (cur == -1)
      l = m;
    else
      r = m;
  }
  ans -= l + 1;

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


Measured memory_bytes: 900
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<cmath>
#include<complex>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<ctype.h>
#include<cwchar>
#include<cwctype>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<math.h>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<stdio.h>
#include<stdlib.h>
#include<streambuf>
#include<string.h>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#define x first
#define y second
#define m_p make_pair
using namespace std;
inline int mini(int a,int b){
	return (a>b)?b:a;
}
bool lay[888][888];
int dist[888][888],sx,sy;
int main(void){
	int n,m,k;
	scanf("%d%d%d",&n,&m,&k);
	char c=getchar();
	for (int i=1;i<=n;i++){
		while(c==10||c==32){
			c=getchar();
		}
		for (int j=1;j<=m;j++){
			if (c=='S'){
				sx=i,sy=j;
				lay[i][j]=1;
			}
			if (c=='.'){
				lay[i][j]=1;
			}
			c=getchar();
		}
	}
	memset(dist,255,sizeof(dist));
	queue<pair<int,int> > q;
	q.push(m_p(sx,sy));
	dist[sx][sy]=0;
	int res=100000000;
	while(!q.empty()){
		int tx=q.front().x,ty=q.front().y;
		q.pop();
		res=mini(res,mini(mini(tx-1,ty-1),mini(n-tx,m-ty)));
		if (dist[tx][ty]==k) continue;
		if (dist[tx-1][ty]==-1&&lay[tx-1][ty]){
			dist[tx-1][ty]=dist[tx][ty]+1;
			q.push(m_p(tx-1,ty));
		}
		if (dist[tx+1][ty]==-1&&lay[tx+1][ty]){
			dist[tx+1][ty]=dist[tx][ty]+1;
			q.push(m_p(tx+1,ty));
		}
		if (dist[tx][ty-1]==-1&&lay[tx][ty-1]){
			dist[tx][ty-1]=dist[tx][ty]+1;
			q.push(m_p(tx,ty-1));
		}
		if (dist[tx][ty+1]==-1&&lay[tx][ty+1]){
			dist[tx][ty+1]=dist[tx][ty]+1;
			q.push(m_p(tx,ty+1));
		}
	}
	printf("%d",(res+k-1)/k+1);
	return 0;
}

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

int main(){
    int n;
    cin >> n;
    for(int i=0;i<n;i++){
        int base[3]={0,0,0},point=0, out=0;
        string getstr;
        while(1){
                cin >> getstr;
                if(getstr=="HIT"){
                    if(base[2]==1) point++;
                    base[2]=base[1];
                    base[1]=base[0];
                    base[0]=1;
                }else if(getstr=="HOMERUN"){
                    for(int j=0;j<3;j++){
                        if(base[j]==1){
                            point++;
                            base[j]=0;
                        }
                    }
                    point++;
                }else if(getstr=="OUT"){
                    out++;
                }
            if(out > 2) break;
            }
        cout << point << endl;
        }
    return 0;
}

Measured memory_bytes: 1212
#include<bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define vll vector<ll>
using namespace std;
void solve()
{
	int n,k;cin>>n>>k;
	vi dp(n,1e9),a(n);
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	dp[0]=0;
	for(int i=0;i<n;i++){
		for(int j=i+1;j<=(i+k);j++){
			if(j<n)
			dp[j]=min(dp[j],abs(a[j]-a[i])+dp[i]);
		}
	}
	cout<<dp[n-1];
}
int main()
{
	//int t;cin>>t;
	//while(t--)
	solve();
}

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

typedef long long ll;
using namespace std;

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

	int a,b; cin >> a >> b;
	bool flag[1005];
	memset(flag,0,sizeof(flag));
	int n; cin >> n;
	for (int i = 0;i < n;i++){
		int s,f; cin >> s >> f;
		for (int j = s;j < f;j++){
			flag[j] = true;
		}
	}

	for (int i = a;i < b;i++){
		if(flag[i]){
			cout << 1 << endl;
			return 0;
		}
	}

	cout << 0 << endl;

	return 0;

}




Measured memory_bytes: 3172
#include<stdio.h>
#include<string.h>
int main(void)
{
	int a,s,d[10],f,g,h,j,i;
	scanf("%d",&a);
	while(a!=0){
		for(i=0;i<10;i++){
			d[i]=0;
		}
		for(i=1;i<=a;i++){
			scanf("%d",&s);
			d[s]++;
		}
		for(i=0;i<10;i++){
			if(d[i]!=0){
				for(j=1;j<=d[i];j++){
					printf("*");
				}
			}
			if(d[i]==0){
				printf("-");
			}
			printf("\n");
		}
		scanf("%d",&a);
	}
	return 0;
}

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

#define task "test"
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define openfile  if (fopen(task ".inp","r")){freopen(task ".inp","r",stdin);freopen(task ".out","w",stdout);}
#define ll long long
#define pii pair <int, int>
#define pll pair <ll, ll>
#define all(c) c.begin(), c.end()
#define pb push_back
#define mp make_pair
#define X first
#define Y second

const int INF = 1E9;
const int MOD = 1E9 + 7;
const int N = 1000 + 10;

int t = 1;

ll n, a, b, c, d;
ll Fact[N], Inv[N], F[N][N];

ll POW(ll n, ll k)
{
    if (k == 1) return n;
    ll tmp = POW(n, k / 2);
    tmp = tmp * tmp % MOD;

    if (k & 1) return tmp * n % MOD;
    return tmp;
}

void Input()
{
    cin >> n >> a >> b >> c >> d;
}

void Prepare()
{
    Fact[0] = Inv[0] = Fact[1] = Inv[1] = 1;
    for (int i = 2; i <= n; i++) Fact[i] = Fact[i - 1] * (ll) (i) % MOD;
    for (int i = 2; i <= n; i++) Inv[i] = POW(Fact[i], MOD - 2);
}

ll Comb(ll n, ll k)
{
    if (n < k) return 0;
    return Fact[n] * Inv[k] % MOD * Inv[n - k] % MOD;
}

void Solve()
{
    F[a - 1][0] = 1;

    for (int i = a; i <= b; i++)
        for (int j = 0; j <= n; j++) {
            F[i][j] = F[i - 1][j];
            //cout << "Pre : " << F[i][j] <<" - > ";
            for (int k = c; k <= d && i * k <= j; k++) {
                F[i][j] += F[i - 1][j - i * k] * Comb(j, j - i * k) % MOD * Fact[i * k] % MOD * POW(Inv[i], k) % MOD * Inv[k] % MOD;
                F[i][j] %= MOD;
              //  if (i == 1 && j == 3) cout << F[i][j] << " " << k << endl;
            }
          //  cout << i << " " << j << " " << F[i][j] << endl;
        }
    cout << F[b][n];
}

int main()
{
    openfile;
    // cin >> t;
    while (t--) {
        Input();
        Prepare();
        Solve();
    }
}





Measured memory_bytes: 8192
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include <boost/multiprecision/cpp_ll.hpp>
//typedef boost::multiprecision::cpp_ll ll;
typedef long double dd;
#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_5 i_7-2
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
ll inf=(ll)1E16;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
string alp="abcdefghijklmnopqrstuvwxyz";
#define endl "\n"
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

struct edge{ ll to,cost; };
ll V;
vector<edge> G[500010];
ll d[500010];

void dijkstra(ll s){
    fill(d,d+500010,inf);
    d[s]=0;
    priority_queue<l_l,vector<l_l>,greater<l_l>> que;
    que.push(l_l(0,s));
    while(!que.empty()){
        l_l p=que.top();que.pop();
        ll v=p.second;
        if(d[v]<p.first)continue;
        if(G[v].size()>0){
            rep(i,0,G[v].size()-1){
                edge e=G[v][i];
                if(d[e.to]>d[v]+e.cost){
                    d[e.to]=d[v]+e.cost;
                    que.push(l_l(d[e.to],e.to));
                }
            }
        }
    }
}


int main(){fastio
    ll n;cin>>n;
    ll a,b,c;
    edge e;
    rep(i,0,n-2){
        cin>>a>>b>>c;
        e.cost=c;
        e.to=b;
        G[a].pb(e);
        e.to=a;
        G[b].pb(e);
    }
    ll q,k;
    cin>>q>>k;
    dijkstra(k);
    ll x,y;
    rep(i,0,q-1){
        cin>>x>>y;
        cout<<d[x]+d[y]<<endl;
    }
    
    return 0;
}




Measured memory_bytes: 23664
#include <bits/stdc++.h>
#define repl(i,l,r)for(long long i=(l);i<(r);i++)
#define rep(i,n) for (long long i = 0; i < (n); ++i)
#define per(i,n) for (long long i = (n); i >= 0; --i)
const int INF = 2147483647;//int max
const long long int MOD = 1000000007;
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
//ミョ(-ω- ?)
int main() {
    ll n;
    cin >> n;
    vector<ll> a(n,0);
    rep(i,n)cin >> a[i];
    unordered_map<ll,ll> um;
    rep(i,n)um[i+a[i]]++;
    ll res = 0;
    rep(i,n)res += um[i-a[i]];
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 20072
/*
                        Author: Ankit Kaul
**********************Code Belongs to Respective Author Only************************************
*/
/*#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")*/
#include <bits/stdc++.h>
#define endl       '\n'
#define PI          3.141592653589
#define jaldi       ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define M           1000000007
#define int         long long int
#define pb          emplace_back
#define pf          emplace_front
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define rall(a)     (a).rbegin(),(a).rend()
using namespace std;
int gcd(int a,int b) { return b == 0 ? a : gcd(b, a % b); }
int power(int x,int n){
    int result=1;
    while(n>0)
        {   if(n % 2 ==1)
            result=(result * x)%M;
            x=(x*x)%M;
            n=n/2;
        }
    return result%M;
}      
bool isPrime(int n)
    {
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;
    if (n % 2 == 0 || n % 3 == 0)
        return false;
    for (int i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    return true;
    }
int inv(int a,int m)
{   return power(a,m-2);
}
int lcm(int a,int b)
{   return a*b/(gcd(a,b));
}
signed main()
{   jaldi
    int n;
    cin>>n;
    int sum=0,i=1;
    while(n)
    {   if(i%3!=0 && i%5!=0)
        sum+=i;
        i++;
        n--;
    }
    cout<<sum;
}


Measured memory_bytes: 3640
import sys

n = int(input())
a = list(map(int,input().split()))
s = ((sum(a))//n)+1
t = sum(a)//n
u = ((sum(a))//n)-1
l = []
l.append(s)
l.append(t)
l.append(u)
ans = []
ans2 = []
aa = set(a)

if len(aa) == 1:
    print(0)
    sys.exit()

for j in range(len(l)):
    ans = []
    for i in range(n):
        if a[i] == l[j]:
            continue
        else:
            b = (a[i]-l[j])**2
            ans.append(b)
    ans2.append(sum(ans))


print(min(ans2))


Measured memory_bytes: 9088
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<stack>
#include<map>
using namespace std;

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

int main() {
	int N;
	int a[100005];
	cin >> N;
	REP(i, N) {
		cin >> a[i];
	}

	map<int, int> mp;

	REP(i, N) {
		mp[a[i]]++;
		mp[a[i] - 1]++;
		mp[a[i] + 1]++;
	}

	int maxv = 0;
	for (int i = 0;i <= 100000;i++) {
		maxv = max(maxv, mp[i]);
	}

	cout << maxv << endl;
	return 0;
}

Measured memory_bytes: 5376
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ll q,h,s,d;cin>>q>>h>>s>>d;
  ll n;cin>>n;
  h=min(h,2*q);
  s=min(s,2*h);
  d=min(d,2*s);
  ll ans=(n/2)*d+(n%2)*s;
  cout<<ans<<endl;
}

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

// 1 21
int main() {
  string a, b;
  cin >> a >> b;

  string ab = a + b;
  int num = stoi(ab);

  int i = 0;

  while (i*i<=num) {
    i++;
    if (i * i == num) {
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;
}

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

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
using std::bitset;

#define rep(i,n)    for(int i=0; i<(int)n; i++)
#define reps(i,s,e) for(int i=s; i<(int)e; i++)
#define coutd(i) cout << std::fixed << std::setprecision(i)
typedef long double ld;
typedef long long ll;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef std::pair<int, int> pii;
typedef std::pair<ll, ll> pll;

template<class T>
using Set = std::set<T>;
template<class T, class U>
using Map = std::map<T, U>;

template<class T>
using Graph = vector<vector<T>>;

const int INT_BIG = 1<<28;

int main() {
    int D;
    cin >> D;
    vint downrate(26);
    Graph<int> uppoint(D, vint(26));
    rep(i, 26) {
        cin >> downrate[i];
    }

    rep(i, D) {
        rep(j, 26) {
            cin >> uppoint[i][j];
        }
    }

    vint lastDay(26, -1);

    ll satisfy = 0;
    vint schedule(D);
    rep(i, D) {
        cin >> schedule[i];
        schedule[i]--;
        satisfy += uppoint[i][schedule[i]];
        lastDay[schedule[i]] = i;
        rep(j, 26) {
            satisfy -= (i - lastDay[j]) * downrate[j];
        }
        cout << satisfy << endl;
    }
    
}

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

int main(){
  int n; cin >> n;
  set<int> s;
  for(int i=0; i<n; i++){
    int a;cin >> a;
    s.insert(a);
  }
  if(s.size() == n){
    cout << "YES" << endl;
  }else{
    cout << "NO" << endl;
  }
}


Measured memory_bytes: 12940
# ALDS1_7_C: Tree Walk

class BinaryTree

  class Node
    attr_reader :id, :parent, :left, :right

    def initialize(id)
      @id = id
    end

    def set_children(left, right)
      @left  = left
      @right = right
      @left.set_parent self
      @right.set_parent self
    end

    def root?
      @parent.nil?
    end

    def nil_node?
      self == NIL
    end

    protected
      def set_parent(parent)
        @parent = parent
      end
  end

  NIL = Node.new(-1)

  def initialize(data)
    nodes = Array.new(data.size).map.with_index do |_, i|
      Node.new(i)
    end

    data.each do |id, left_id, right_id|
      left  = left_id  == -1 ? NIL : nodes[left_id]
      right = right_id == -1 ? NIL : nodes[right_id]
      bind nodes[id], left, right
    end

    @root = nodes.find { |n| n.root? }
  end

  def preorder_walk(node = @root)
    return [] if node.nil_node?
    [node] + preorder_walk(node.left) + preorder_walk(node.right)
  end

  def inorder_walk(node = @root)
    return [] if node.nil_node?
    inorder_walk(node.left) + [node] + inorder_walk(node.right)
  end

  def postorder_walk(node = @root)
    return [] if node.nil_node?
    postorder_walk(node.left) + postorder_walk(node.right) + [node]
  end

  private
    def bind(parent, left, right)
      parent.set_children left, right
    end
end

def nodes_to_s(nodes)
  nodes.inject '' do |s, node|
    s << ' ' << node.id.to_s
  end
end

n_nodes = gets.to_i
node_data = n_nodes.times.map do
  gets.split.map &:to_i
end

tree = BinaryTree.new node_data

puts 'Preorder'
puts nodes_to_s(tree.preorder_walk)
puts 'Inorder'
puts nodes_to_s(tree.inorder_walk)
puts 'Postorder'
puts nodes_to_s(tree.postorder_walk)

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

int main(){
    int N,K;
    cin >> N >> K;
    vector<int> h(N);
    for(int i = 0;i < N;i++) {
        cin >> h.at(i);
    }
    sort(h.begin(),h.end());
    int min = h.at(K - 1) - h.at(0);
    for(int i = 1;i <= N - K;i++) {
        int d = h.at(i + K - 1) - h.at(i);
        if(min > d) min = d;
    }
    cout << min << endl;
}


Measured memory_bytes: 640
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<map>
#include<functional>
#include<set>

#pragma region
using namespace std;
#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)
#define ALL(x) x.begin(),x.end()
#define RALL(x) x.rbegin(),x.rend()
#define INF 9223372036854775807
#define MOD 1000000007
#define pb push_back
#define F first
#define S second
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef pair<ll, ll> pll;
ll n = 0, m = 0, ans = 0, sum = 0, cnt = 0, tmp = 0;
string s;
bool flag;
#pragma endregion

ll x[111111], v[111111], sm1[111111], smx1[111111], sm2[111111], smx2[111111];

int main(void) {
  ll c;
  cin >> n >> c;
  FOR(i, 1, n + 1) {
	cin >> x[i] >> v[i];
  }

  FOR(i, 1, n + 1) {
	sm1[i] = sm1[i - 1] + v[i] - (x[i] - x[i - 1]);
	if (smx1[i - 1] < sm1[i]) {
	  smx1[i] = sm1[i];
	}
	else {
	  smx1[i] = smx1[i - 1];
	}
	ans = max(ans, sm1[i]);
  }

  x[n + 1] = c;
  FOR(i, 1, n + 1) {
	sm2[i] = sm2[i - 1] + v[n - i + 1] - (x[n - i + 2] - x[n - i + 1]);
	if (smx2[i - 1] < sm2[i]) {
	  smx2[i] = sm2[i];
	}
	else {
	  smx2[i] = smx2[i - 1];
	}
	ans = max(ans, sm2[i]);
  }

  FOR(i, 1, n + 1) {
	ans = max(ans, sm1[i] + smx2[n - i] - x[i]);
	ans = max(ans, sm2[i] + smx1[n - i] - (c - x[n - i + 1]));
  }
  cout << ans << endl;

  return 0;
}

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


Measured memory_bytes: 1152
import std.algorithm;
import std.array;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

T read(T)() { return readln.chomp.to!T; }
T[] reads(T)() { return readln.split.to!(T[]); }
alias readint = read!int;
alias readints = reads!int;

long calc(int[] a) {
    a.sort();
    auto n = a.length / 3;
    long ans = 0;
    long p = a.length - 2;
    for (int i = 0; i < n; i++) {
        ans += a[p];
        p -= 2;
    }
    return ans;
}

void main() {
    readint;
    auto a = readints;
    writeln(calc(a));
}


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

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


#define rep(i,n) for(ll (i)=0; (i)<(ll)(n); (i)++)
#define frep(i,m,n) for(ll (i)=(m); (i)<=(ll)(n); (i)++)
#define rrep(i,n) for(ll (i)=(n)-1; (i)>-1; (i)--)
#define frrep(i,m,n) for(ll (i)=(n); (i)>(ll)(m); (i)--)
#define ALL(x) (x).begin(), (x).end()

const ll INF = 100100100100100100;
const ll MOD = 1000000007;

// get abs
ll my_abs(ll a);
// a^n
ll a_n(ll a, ll n);
// get gcd
ll my_gcd(ll a, ll b);
// a^(-1) % MOD 
ll inv(ll a);

int main() {
    ll n, m, c;
    cin >> n >> m >> c;
    vector<ll> b(m);
    rep(i, m) cin >> b[i];
    ll ans = 0;
    rep(i, n) {
        ll tmp = 0;
        rep(j, m) {
            ll a;
            cin >> a;
            tmp += b[j]*a;
        }
        if(tmp+c>0) ans++;
    }
    cout << ans << endl;
    return 0;
}

ll my_abs(ll a) {
    if(a >= 0) return a;
    else return -1 *a;
}

ll a_n(ll a, ll n) { 
    if(n == 0) return 1;
    
    ll ret = a, count = 1;
    while(count * 2 < n) {
        ret *= ret;
        count *= 2;
    }
    if(count == n) return ret;
    else return (ret * a_n(a, n-count));
}

ll my_gcd(ll a, ll b) {
    if(b == 0) return a;
    return my_gcd(b, a%b);
}

ll inv(ll a) {
    return a_n(a, MOD-2);
}



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

using namespace std;

typedef long long LL;

vector<int> d[2];
vector<int> v[100000];

void dfs(int x, int y, int dist, int s) {
    d[s][x] = dist;
    for (int i = 0; i < v[x].size(); i++) {
        if (v[x][i] != y) {
            dfs(v[x][i], x, dist + 1, s);
        }
    }
}

int main() {
    int n;
    cin >> n;
    d[0].resize(n);
    d[1].resize(n);

    int a, b;
    for (int i = 0; i < n - 1; i++) {
        cin >> a >> b;
        a--; b--;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    dfs(0, -1, 0, 0);
    dfs(n - 1, -1, 0, 1);

    int f = 0, ss = 0;
    for (int i = 0; i < n; i++) {
        if (d[0][i] <= d[1][i]) {
            f++;
        } else {
            ss++;
        }
    }

    if (f > ss) {
        cout << "Fennec" << endl;
    } else {
        cout << "Snuke" << endl;
    }

    return 0;
}


Measured memory_bytes: 14336
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define ALL(x) (x).begin(), (x).end()
#define dump(x) cout << (x) << endl
#define LMAX 9223372036854775807LL
#define LMIN -9223372036854775807LL
using ll = long long;
template<typename T>
using vec = vector<T>;
using P = pair<ll, ll>;
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
	fill((T *)array, (T *)(array + N), val);
}

const ll INF = 1e16;
const ll MOD = 1e9 + 7;
//int dx[4] = {1,0,-1,0};
//int dy[4] = {0,1,0,-1};
//ll pas[51][52];

template <class Abel> struct UnionFind {
	vector<ll> par, rank;
	vector<Abel> dif_weight;
	UnionFind(int n = 1, Abel SUM_UNIT = 0){
		par.resize(n);rank.resize(n);dif_weight.resize(n);
		for(int i = 0;i < n;i++){
			par[i] = i;rank[i] = 0;
			dif_weight[i] = SUM_UNIT;
		}
	}
	Abel weight(int i){
		root(i);
		return dif_weight[i];
	}
	bool merge(int x, int y, Abel w) {
		w += dif_weight[x]; w-= dif_weight[y];
		x = root(x), y = root(y);
		if(x == y)return false;
		if(rank[x] < rank[y])swap(x, y), w = -w;
		if(rank[x] == rank[y])++rank[x];
		par[y] = x;
		dif_weight[y] = w;
		return true;
	}
	bool isSame(int x, int y) {
		return root(x) == root(y);
	}
	int root(int x) {
		if(x == par[x])return x;
		else {
			int r = root(par[x]);
			dif_weight[x] += dif_weight[par[x]];
			return par[x] = r;
		}
	}
	Abel dif(int x, int y){
		return dif_weight[y] - dif_weight[x];
	}
};

int main(){
	IOS;
	ll n;
	cin >> n;
	vec<P> vx(n),vy(n);
	REP(i,n){
		ll x, y;
		cin >> x >> y;
		vx[i] = make_pair(x,i);
		vy[i] = make_pair(y,i);
	}
	sort(ALL(vx));
	sort(ALL(vy));
	vec<tuple<ll,ll,ll>> g;
	REP(i,n - 1){
		ll cost = abs(vx[i + 1].first - vx[i].first);
		ll from = vx[i].second;
		ll to = vx[i + 1].second;
		g.push_back(make_tuple(cost,from,to));
		cost = abs(vy[i + 1].first - vy[i].first);
		from = vy[i].second;
		to = vy[i + 1].second;
		g.push_back(make_tuple(cost,from,to));
	}
	sort(ALL(g));
	ll m = g.size();
	UnionFind<ll> uf(n);
	ll ans = 0;
	REP(i,m){
		ll cost = get<0>(g[i]);
		ll from = get<1>(g[i]);
		ll to = get<2>(g[i]);
		if(!uf.isSame(from,to)){
			uf.merge(from,to,0);
			ans += cost;
		}
	}
	dump(ans);
}

Measured memory_bytes: 11756
//    _____ _     _                _           _     _ _     _     
//    \_   \ |_  (_)___  __      _| |__   __ _| |_  (_) |_  (_)___ 
//     / /\/ __| | / __| \ \ /\ / / '_ \ / _` | __| | | __| | / __|
//  /\/ /_ | |_  | \__ \  \ V  V /| | | | (_| | |_  | | |_  | \__ \
//  \____/  \__| |_|___/   \_/\_/ |_| |_|\__,_|\__| |_|\__| |_|___/
//                                                                 
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

ll div_floor(ll a, ll b) {
	// use when ret <= a/b, (a and b can be -ve)
	return a / b - (((a ^ b) < 0) and a % b);
}
ll div_ceil(ll a, ll b) { 
	// use when ret >= a/b, (a and b can be -ve)
	return a / b + (((a ^ b) >= 0) and a % b);
}
const int sz=1e6+9;
string s;



int main(){
	cin>>s;
	for(auto u:s) cout<<'x';
	return 0;
}

Measured memory_bytes: 256
// 基本テンプレート
 
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
using namespace std;
 
#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++)
#define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define int long long int
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
typedef pair<int, int> pii;
typedef long long ll;
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1001001001001001LL;
const ll MOD = 1000000007LL;

int N;
using Graph = vector< vector<int> >;

pair<int, int> solve(Graph &G, vector<int> roots) {
    vector<int> visited(N);
    for(auto x : roots) visited[x] = true;

    int sum = roots.size(), depth = 1;
    vector<int> cur = roots;
    for(; ; depth++) {
        /*
        fprintf(stderr, "cur: ");
        for(auto x : cur) cerr << x+1 << " ";
        cerr << endl;
        */

        int max_children = 0;
        vector<int> nxt;
        for(auto x : cur) {
            int cnt = 0;

            // fprintf(stderr, "vertex %lld: ", x+1);
            for(auto to : G[x]) {
                if(visited[to]) continue;
                visited[to] = true;
                // cerr << to + 1 << " ";
                cnt++;
                nxt.push_back(to);
            }
            // cerr << endl;
            chmax(max_children, cnt);
        }

        if(max_children == 0) break;
        sum *= max_children;
        swap(cur, nxt);
    }
    return make_pair(depth, sum);
}
 
signed main() {
    cin >> N;
    Graph G(N);
    for(int i=0; i<N-1; i++) {
        int u, v; cin >> u >> v;
        u--; v--;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    if(N == 2) {
        printf("1 2\n");
        return 0;
    }
    pii ans = make_pair(INF, INF);
    for(int i=0; i<N; i++) {
        // root is i
        if(G[i].size() < 2) continue;
        chmin(ans, solve(G, vector<int>{i}));

        for(auto to : G[i]) {
            int u = i, v = to;
            chmin(ans, solve(G, vector<int>{u, v}));
        }
    }
    printf("%lld %lld\n", ans.first, ans.second);
    return 0;
}

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

using namespace std;

int main() {
	int s; cin >> s;
	vector<int> a(1001001);
	a[0] = s;
	int m = 0;

	for (int i = 1; i < 1001001; i++) {
		if (a[i - 1] % 2) {
			a[i] = 3 * a[i - 1] + 1;
		}
		else {
			a[i] = a[i - 1] / 2;
		}
		for (int j = 0; j < i; j++) {
			if (a[i] == a[j]) {
				m = i;
				cout << m+1 << endl;
				return 0;
			}
		}

	}

	return 0;
}

Measured memory_bytes: 4096
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string>
#include<math.h>
#include<vector>
#include<iomanip>
using namespace std;

long long int gcd(long long int x, long long int y)
{
	if (y == 0) { return x; }
	return gcd(y, x % y);
}

int main(void)
{
	int n,ans = 1,min,hoge;
	vector<int> p;
	cin >> n;
	for (int i = 0; i < n; i++) { cin >> hoge; p.push_back(hoge); }
	min = p[0];
	for (int i = 1; i < n; i++)
	{
		if (p[i] <= min) { min = p[i]; ans++; }
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 1400
#include <iostream>
#define TEST cout << "test" << endl;
using namespace std;

int main(void){
  int n,h[101],zerocount = 0,watercount = 0;
  cin >> n;
  h[0] = 0;
  for(int i = 1; i < n + 1; i++){
    cin >> h[i];
    if(h[i] == 0)zerocount++;
  }
  h[n + 1] = 0;
  
  while(zerocount != n){
    for(int i = 0; i < n + 1; i++){
      if(h[i] == 0 && h[i + 1] != 0){
        //cout << i << endl;
        watercount++;
      }
      if(h[i] != 0){
        if(h[i] == 1){
          zerocount++;
        }
        h[i]--;
      }
    }
  }
  cout << watercount << endl;
  return 0;
}

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

int main(void) {
	int sx, sy, tx, ty;
	while(cin >> sx >> sy >> tx >> ty) {
		for(int i = sy; i < ty; i++)
			cout << 'U';
		for(int i = sx; i < tx; i++)
			cout << 'R';
		for(int i = ty; i > sy; i--)
			cout << 'D';
		for(int i = tx; i > sx; i--)
			cout << 'L';
		cout << 'L';
		for(int i = sy; i <= ty; i++)
			cout << 'U';
		for(int i = sx; i <= tx; i++)
			cout << 'R';
		cout << 'D';
		cout << 'R';
		for(int i = ty; i >= sy; i--)
			cout << 'D';
		for(int i = tx; i >= sx; i--)
			cout << 'L';
		cout << 'U' << endl;
	}
	return 0;
}

Measured memory_bytes: 256