akhauriyash/Code-Regression huggingface dataset:
#include <cassert>
#include <iostream>
#include <vector>
#include <utility>
#include <tuple>
using namespace std;

struct LCA {
private:
  vector<vector<int>> G;
  size_t n, m;
  vector<vector<int>> A;
  vector<int> D;
  void dfs(int v, int p){
    for(auto v_ : G[v]){
      if(v_ == p) continue;
      A[v_][0] = v;
      D[v_] = D[v]+1;
      dfs(v_,v);
    }
  }
  void build(int r){
    dfs(r,-1);
    A[r][0] = r;
    for(size_t i = 1; i < m; ++i){
      for(size_t j = 0; j < n; ++j){
        A[j][i] = A[A[j][i-1]][i-1];
      }
    }
  }
public:
  LCA(const vector<vector<int>>& Tree, int r) : G(Tree), n(Tree.size()), m(1), D(n,0) {
    size_t t = 1;
    while(t < n) ++m, t *= 2;
    A = vector<vector<int>>(n,vector<int>(m,-1));
    build(r);
  }
  size_t query(int u, int v){
    if(D[u] < D[v]) swap(u,v);

    for(size_t i = m-1; i < m; --i){
      size_t u_ = A[u][i];
      if(D[u_] < D[v]) continue;
      u = u_;
    }

    if(u == v) return u;
    assert(D[u] == D[v]);
    for(size_t i = m-1; i < m; --i){
      if(A[u][i] != A[v][i])
        u = A[u][i], v = A[v][i];
    }
    return A[u][0];
  }
};

void dfs(const vector<vector<pair<int,int>>> &G, int v, int p,
         const vector<int> &C, const vector<int> &D,
         const vector<vector<pair<int,int>>> &W, vector<long long> &A,
         const vector<int> &X, const vector<int> &Y,
         vector<int> &cnt, vector<long long> &dist, long long d){
  // cerr << v << endl;
  // for(auto e : cnt)
  //   cerr << e << " ";
  // cerr << endl;
  // for(auto e : dist)
  //   cerr << e << " ";
  // cerr << endl;
  for(auto q : W[v]){
    int idx, w;
    tie(idx,w) = q;
    // cerr << idx << " " << w << " " << X[idx] << " " << Y[idx] << endl;
    // cerr << d << " " << dist[X[idx]] << " " << cnt[X[idx]] << endl;
    long long a = d - dist[X[idx]] + Y[idx]*cnt[X[idx]];
    A[idx] += a*w;
  }
  for(auto e : G[v]){
    int v_, idx;
    tie(v_,idx) = e;
    if(v_ == p) continue;
    ++cnt[C[idx]];
    dist[C[idx]] += D[idx];
    d += D[idx];
    dfs(G,v_,v,C,D,W,A,X,Y,cnt,dist,d);
    --cnt[C[idx]];
    dist[C[idx]] -= D[idx];
    d -= D[idx];
  }
}

int main(){
  int N, Q;
  cin >> N >> Q;
  vector<int> C, D;
  vector<vector<pair<int,int>>> G(N);
  vector<vector<int>> T(N);
  for(int i = 0; i < N-1; ++i){
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    --a,--b,--c;
    G[a].emplace_back(b,i);
    G[b].emplace_back(a,i);
    T[a].push_back(b);
    T[b].push_back(a);
    C.push_back(c);
    D.push_back(d);
  }
  LCA lca(T,0);
  vector<vector<pair<int,int>>> W(N);
  vector<long long> A(Q,0);
  vector<int> X(Q), Y(Q);
  for(int i = 0; i < Q; ++i){
    int x, y, u, v;
    cin >> x >> y >> u >> v;
    --x,--u,--v;
    X[i] = x, Y[i] = y;
    W[u].emplace_back(i,1);
    W[v].emplace_back(i,1);
    int a = lca.query(u,v);
    W[a].emplace_back(i,-2);
  }
  // for(int i = 0; i < N; ++i){
  //   cerr << i << endl;
  //   for(auto e : W[i])
  //     cout << e.first << " " << e.second << endl;
  // }
  vector<int> cnt(N,0);
  vector<long long> dist(N,0);
  long long d = 0;
  dfs(G,0,-1,C,D,W,A,X,Y,cnt,dist,d);
  for(auto a : A)
    cout << a << endl;
}


Measured memory_bytes: 49264
require 'pp'

x, n = gets.split.map(&:to_i)
p_n = gets.split.map(&:to_i)
t = []
102.times do |i|
    t << 0
end

p_n.each do |i|
    t[i] = 1
end

#pp t

ans1 = 99999
i = 0
while x - i >= 0
    if t[x - i] == 0
        ans1 = x - i
        break
    end
    i += 1
end

tmp = i

ans2 = -1
i = 0
while x + i >= 0
    if t[x + i] == 0
        ans2 = x + i
        break
    end
    i += 1
end

if tmp <= i
    puts ans1
else
    puts ans2
end


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

using namespace std;

/*

        Bismillahir Rahmanir Rahim
        Problem :
        Problem Link :
        Topics :
        Solver : Masud Parves
        I Love Code More than Sharks Love Blood <3
*/

#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define SZ(a)           (int)a.size()
#define all(a)  a.begin(), a.end()
#define allr(a)  a.rbegin(), a.rend()


#define sf(a)           scanf("%d",&a)
#define sff(a,b)        scanf("%d %d",&a,&b)
#define sfff(a,b,c)     scanf("%d %d %d",&a,&b,&c)

#define f0(i,b) for(int i=0;i<(b);i++)
#define f1(i,b) for(int i=1;i<=(b);i++)
#define f2(i,a,b) for(int i=(a);i<=(b);i++)
#define fr(i,b,a) for(int i=(b);i>=(a);i--)

#define CIN ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
#define TEST_CASE(t) for(int zz=1 ; zz<=t ; zz++)
#define PRINT_CASE printf("Case %d: ",zz)
#define Debug(x)            cout<<#x " = "<<(x)<<endl
#define NOT_VISITED 0
#define IS_VISITED 1
#define WHITE 0
#define GRAY 1
#define BLACK 2

int fx[4]= {1,-1,0,0};
int fy[4]= {0,0,1,-1};

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N  (1<<pos);}
//int Reset(int N,int pos){return N= N & ~(1<<pos);}
//bool Check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

const double PI = acos(-1.0);
const double EPS = 1e-6;
const int MOD = (int)1e9+7;
const int maxn = (int)2e5+5;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, int> plli;
typedef pair<int, ll> pill;
ll a[maxn];
vector < int >g[maxn];

void dfs(int u, int p){

    for(int v:g[u]){
        if(v!=p){
            a[v]+=a[u];
            dfs(v,u);
        }

    }
}

int main() {
    CIN
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    //cout << "Fi Amanillah" << endl;

    int n,q;
    cin >> n >> q;

    int u,v;
    f0(i,n-1){
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }


    int node,val;
    f1(i,q){
        cin >> node >> val;
        a[node]+=val;
    }

    dfs(1,1);

    f1(i,n){
        cout << a[i] <<" ";
    }


    return 0;
}




Measured memory_bytes: 24320
PROGRAM ATCODER

implicit none
integer :: n, i
integer,allocatable :: l(:)

read(*,*) n
allocate(l(n))

read(*,*) (l(i),i=1,n)

if ( maxval(l) < sum(l)-maxval(l) ) then
	write(*,'(a)') 'Yes'
else
	write(*,'(a)') 'No'
end if

END PROGRAM ATCODER

Measured memory_bytes: 256
x1, y1, x2, y2 = map(int, input().split())
x3, y3 = y1 - y2, -(x1 - x2)
x4, y4 = -(y2 - y1), x2 - x1

print(x3 + x2, y3 + y2, x4 + x1, y4 + y1)

Measured memory_bytes: 2940
import java.util.Scanner;

public class Main {

    private void execute() throws Exception {
        Scanner sc = new Scanner(System.in);
        String ab = sc.nextLine();
        String[] abs = ab.split(" ");
        int a = Integer.parseInt(abs[0]);
        int b = Integer.parseInt(abs[1]);
        if (a >= 10 || b >= 10) {
            System.out.println(-1);
            return;
        }
        System.out.println(a * b);
    }

    public static void main(String[] args) {
        try {
            new Main().execute();
        } catch (Exception ex) {
            ex.printStackTrace();
        }
    }

}


Measured memory_bytes: 25044
#include<iostream>
#include<map>
#include<vector>
#include<cstdio>

using namespace std;

const int M=3009;
const int N=1e5+9;

typedef long long ll;
typedef map<ll,int>::iterator it;

bool npri[M];
ll n,a[N];
vector<ll> pri;
map<ll,int> ha;

inline void init()
{
	for(int i=2;i<M;i++)
	{
		if(!npri[i])
			pri.push_back(i);
		for(int j=0,ed=pri.size();j<ed && i*pri[j]<M;j++)
		{
			npri[i*pri[j]]=1;
			if(!(i%pri[j]))
				break;
		}
	}
	for(int i=0,ed=pri.size();i<ed;i++)
		pri[i]=pri[i]*pri[i]*pri[i];
}

inline ll div(ll val)
{
	for(int i=0,ed=pri.size();i<ed;i++)
		while(!(val%pri[i]))
			val/=pri[i];
	return val;
}

int main()
{
	init();
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		ha[a[i]=div(a[i])]++;
	}

	ll ans=0;
	for(it i=ha.begin();i!=ha.end();i++)
	{
		ll val=i->first;
		if(val==1)continue;
		val=div(val*val);
		ans+=max(i->second,ha[val]);
		i->second=0;
		ha[val]=0;
	}
	if(ha[1]>0)
		ans++;

	printf("%lld\n",ans);
	return 0;
}


Measured memory_bytes: 21504
#include<stdio.h>
int main(void){
  int n;
  long long a[200002];
  long long xor = 0;
  
  scanf("%d",&n);
  int i;
  for(i=0;i<n;i++){
   scanf("%lld",&a[i]); 
    xor = xor ^ a[i];
  }
 
  for(i=0;i<n;i++){
    printf("%d ",xor ^ a[i]);   
  }
  return 0;
}

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

int main()
{
	int n;
	std::cin >> n;
	std::vector<std::vector<int>> a(2,std::vector<int>(n));
	for(int i = 0; i < 2; i++){
		for(int j = 0; j < n; j++)std::cin >> a[i][j];
	}
	int max = 0;
	//どこで曲がるか
	for(int i = 0; i < n; i++){
		int tmp = 0;
		//どこで曲がるか
		for(int j = 0; j <= i; j++){
			tmp += a[0][j];
		}
		for(int j = i; j < n; j++){
			tmp += a[1][j];
		}
		max = std::max(tmp,max);
	}
	std::cout << max << std::endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 998244353;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
typedef pair<ld, ld> LDP;
int n, m;
int bs;string b[12];
string in,s;

queue<int> q;
bool used[1 << 12];
int len[1 << 12];
bool ok[12][5000];

bool valid(int le) {
	rep(i, (1 << n)) {
		used[i] = false;
	}
	q.push(0); used[0] = true;
	while (!q.empty()) {
		int p = q.front(); q.pop();
		rep(i, n) {
			if (p&(1 << i))continue;
			if (ok[i][le+len[p]]) {
				int np = p ^ (1 << i);
				if (!used[np]) {
					used[np] = true; q.push(np);
				}
			}
		}
	}
	return used[(1<<n)-1];
}
void init() {
	bs = 0; s.clear();
	rep(i, 1 << n) {
		len[i] = 0;
	}
}
int main() {
	while (cin >> n >> m,n) {
		init();
		rep(i, n) {
			cin >> in; bs += in.length(); b[i] = in;
		}
		rep(i, (1 << n)) {
			rep(j, n) {
				if (i&(1 << j)) {
					len[i] += b[j].length();
				}
			}
		}
		rep(i, m) {
			cin >> in; s += in;
		}
		rep(i, n) {
			rep(j, s.length() - b[i].length() + 1) {
				ok[i][j] = (b[i] == s.substr(j, b[i].length()));
			}
		}
		int ans = 0;
		rep(i, s.length() - bs + 1) {
			if (valid(i))ans++;
		}
		cout << ans << endl;
	}
	return 0;
}



Measured memory_bytes: 3152
#include<stdio.h>
#define MAX 30
#define NIL -1
struct Node_struct{int p, l, r, s;}; 
typedef struct Node_struct Node;
Node T[MAX];
int D[MAX];
int Deg[MAX];
int H[MAX];

void print(int u){
 int i, c;
 printf("node %d: parent = %d, sibling = %d, degree = %d, depth = %d, height = %d", u, T[u].p, T[u].s, Deg[u], D[u], H[u]);

 if(D[u] == 0) printf(", root");
 else if(H[u] == 0) printf(", leaf");
 else printf(", internal node");

 printf("\n");

}

void calcDegree(int u){
  if(T[u].r != NIL){
    Deg[u]++;
    calcDegree(T[u].r);
  }
  if(T[u].l != NIL){
    Deg[u]++;
    calcDegree(T[u].l);
  }
}

void calcDepth(int u, int p){
 D[u] = p;
 if(T[u].r != NIL) calcDepth(T[u].r,p+1);
 if(T[u].l != NIL) calcDepth(T[u].l,p+1);
}

int calcHeight(int u){
  int l=0,r=0;
  if(T[u].r == NIL && T[u].l == NIL){
    H[u] = 0;
    return 0;
  }
  if(T[u].r != NIL)r = calcHeight(T[u].r)+1;
  if(T[u].l != NIL)l = calcHeight(T[u].l)+1;
  if(l>r)H[u] = l;
  else H[u] = r;
  return H[u];
}

int main(){
 int i, j, k;
 int n;
 int id, child;
 int root = NIL;
 scanf("%d", &n);
 for(i=0; i<n; i++) T[i].p = T[i].l = T[i].r = T[i].s = NIL;

 for(i=0; i<n; i++){
   scanf("%d", &id);
   for(j = 0; j<2; j++){ //子を入力する (input children)
     scanf("%d", &child);
     T[child].p = id;
     if(j == 0) T[id].l = child; //idの一番左の子 (the most left child of id)
     else{
       T[id].r = child;
       T[T[id].r].s = T[id].l;
       T[T[id].l].s = T[id].r;
     } //左の兄弟に繋げる (connect to left sibling)
     //次の子供の左の兄弟 (the left sibling of the next child)
   }
 }

 //根を求める (find the root)
 for(i=0; i<n; i++){
   if(T[i].p == -1) root = i;
 }

 calcDegree(root);

 //それぞれのノードの深さを求める (find depth of each node)
 calcDepth(root, 0);

 calcHeight(root);

 //出力 (output)
 for(i=0; i<n; i++) print(i);

 return 0;
}



Measured memory_bytes: 2100
s = input()
n = len(s)
flg = 0
for i in range(1,n):
  if s[i-1] != s[i]:
    flg += 1
if flg == 0:
  print(1)
  exit()
par = (s.count("a")+s.count("b")*2+2)%3
dp = [[0 for i in range(9)] for j in range(n)]
mod = 998244353
dp[0][0] = 1
dp[0][4] = 1
dp[0][8] = 1
for i in range(1,n):
  dp[i][0] = dp[i-1][5]+dp[i-1][8]
  dp[i][1] = dp[i-1][3]+dp[i-1][6]
  dp[i][2] = dp[i-1][4]+dp[i-1][7]
  dp[i][3] = dp[i-1][1]+dp[i-1][7]
  dp[i][4] = dp[i-1][2]+dp[i-1][8]
  dp[i][5] = dp[i-1][0]+dp[i-1][6]
  dp[i][6] = dp[i-1][0]+dp[i-1][3]
  dp[i][7] = dp[i-1][1]+dp[i-1][4]
  dp[i][8] = dp[i-1][2]+dp[i-1][5]
  for j in range(9):
    dp[i][j] %= mod
ans = pow(3,n-1,mod)-dp[-1][par]-dp[-1][par+3]-dp[-1][par+6]
if flg == n-1:
  ans += 1
if n == 3 and flg == n-1 and par == 2:
  ans -= 1
print(ans%mod)

Measured memory_bytes: 121824
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

n = int(input())
a = list(map(int, input().split()))

import heapq

ans = 0
heapq.heapify(a)
while a:
    t = heapq.heappop(a)
    if ans == 0:
        ans = t
        continue
    else:
        big = max(ans, t)
        small = min(ans, t)
        if big % small != 0:
            ans = big % small
            heapq.heappush(a, small)

print(ans)


Measured memory_bytes: 85776
#include <bits/stdc++.h>
#define ll long long int
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define pb emplace_back
#define vi vector<int>
#define all(x) (x).begin(), (x).end()
#define pb emplace_back
#define deb(x) cout << #x << " - " << x << endl;

using namespace std;


vector<ll>v(1000001);
queue<ll>q;
ll ptr = 9;

void showq(queue <int> gq)
{
	queue <int> g = gq;
	while (!g.empty())
	{
		cout << '\t' << g.front();
		g.pop();
	}
	cout << '\n';
}

int main()
{	IOS;
//#ifndef ONLINE_JUDGE
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
//#endif
	for (ll i = 1; i <= 9; i++) {
		v[i - 1] = i;
		q.push(i);
	}
	while (!q.empty()) {
		ll n = q.front();
		//showq(q);
		q.pop();
		ll rem = n % 10;
		ll start = n * 10 + rem - 1;
		ll end = start + 2;

		if (ptr == 1000001 ) break;
		if (rem == 9) end--;
		if (rem == 0) start++;
		for (ll i = start; i <= end; i++) {
			if (ptr == 1000001) break;
			v[ptr++] = i;
			q.push(i);
		}
	}
	ll n; cin >> n;
	cout << v[n - 1];
	return 0;
}

Measured memory_bytes: 13440
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using Pll = pair<ll, ll>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(v) v.begin(), v.end()
#define sz(x) ((int) x.size())
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define F first
#define S second
const int MOD = 1000000007;
template<class T> void print(const T& t){ cout << t << endl; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(){
  string s, t;
  cin >> s >> t;
  sort(all(s));
  sort(all(t));
  reverse(all(t));
  if(s<t){
    print("Yes");
  }
  else{
    print("No");
  }
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iomanip>
typedef long long ll;
using namespace std;

int main () {
    ll N;
    cin >> N;
    vector<ll> A(N);
    for(auto &a:A) {
        cin >> a;
    }

    // 奇数を+
    ll a1 = 0, s1 = 0;
    // 奇数を-
    ll a2 = 0, s2 = 0;
    
    for (int i = 0; i < N; i++)
    {
        s1 += A[i];
        if(i % 2 == 0 ){
            if(s1 >= 0) {
                a1 += abs(s1) + 1;
                s1 = -1;
            }
        }else {
            if(s1 <= 0) {
                a1 += abs(s1) + 1;
                s1 = 1;
            }
        }
        s2 += A[i];
        if(i % 2 == 0 ){
            if(s2 <= 0) {
                a2 += abs(s2) + 1;
                s2 = 1;
            }
        }else {
            if(s2 >= 0) {
                a2 += abs(s2) + 1;
                s2 = -1;
            }
        }
    }
    cout << min(a1, a2) << endl;
}


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

long long n;

int main(){

	char ans[100002];
	long long cnt=0ll;

	cin>>n;
	n--;
	while(true){
		ans[cnt++] = ('a')+(n%26);
		if(n<26)break;
		else n=(n/26)-1;
	}
	for(int i=cnt-1;i>=0;i--){
		cout<<ans[i];
	}
	cout<<endl;

	return(0);
}

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

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

      int h = 0;

      for (int i = 0; i < b - a; i++) {
         h = h + i;
      }

      h = h - a;

      System.out.println(h);
   }
}

Measured memory_bytes: 23892
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <string>
#include <sstream>
#include <vector>
#include <map>
#include <deque>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <list>
#include <unordered_map>
#include <bitset>

typedef  long long ll;
#define mop 1000000007
using namespace std;

ll sumbit[50] = {};

struct TMP{
    ll sub, bit, score0;
};
bool asc( const TMP& left, const TMP& right ) {
    return left.sub == right.sub ? left.bit < right.bit : left.sub < right.sub;
}

int main() {
    

    ll n,k;
    cin >> n >> k;
    for (ll i=0;i<n;i++){
        ll a;
        cin >> a;
        ll j = 0;
        while(j < 50){
            sumbit[j] += a%2;
            a /= 2;
            j++;
        }
    }
    ll score1[50] = {};
    ll score0[50] = {};
    ll scoresub[50] = {};
    ll ansnum = 0;
    vector <TMP> lis;
    for (ll i=0;i<50;i++){
        ll j = 1;
        for (ll l=0;l<i;l++){
            j *= 2;
        }
        score0[i] = j * sumbit[i];
        score1[i] = j * (n-sumbit[i]);
        scoresub[i] = score1[i] - score0[i];
        TMP x;
        x.sub = scoresub[i];
        x.score0 = score0[i];
        x.bit = j;
        lis.push_back(x);
    }
    sort(lis.begin(), lis.end(), asc);
    reverse(lis.begin(), lis.end());
//    for (ll i=0;i<50;i++){
//        cout << i << " " << score0[i] << endl;
//    }
    ll ans = 0;
    for (ll i=0;i<lis.size();i++){
        if(ansnum + lis[i].bit <= k and lis[i].sub > 0){
            ansnum += lis[i].bit;
            ans += lis[i].sub + lis[i].score0;
        }else{
            ans += lis[i].score0;
        }
    }
//    cout << ansnum << endl;
    cout << ans << endl;




}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 60;
#define rep(i, a, n) for (ll i = (a); i < (n); i++)
#define debug(x) cerr << #x << ": " << x << endl;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

int main() {
    ll n;
    cin >> n;
    ll ans = 0;
    for (ll i = 1; i <= (ll)sqrt(n); i++) {
        if (n % i != 0) continue;
        ll a = n / i;
        if (i < a-1) ans += a-1;
        else if (a < i - 1) ans += i-1;
    }   
    cout << ans << endl;
}

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

int main(){
	int N,num;
	double A,T,H,min=99999.99;
	cin >> N;
	cin >> T >> A;
	for(int i=0;i<N;i++){
		cin >> H;
		if(min>abs(A-(T-H*0.006))){
			min=abs(A-(T-H*0.006));
			num=i+1;
		}
	}
	cout << num << endl;
	return 0;
}

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

namespace TOPSIC
{
	public class Program
	{
		public static void Main()
		{
			int n = int.Parse(ReadLine());
			var list = ReadLine().Split().Select(x => int.Parse(x))
				.ToList();

			// 累積和を使う
			var sum = new List<double>();
			sum.Add(list[0]);
			for (int i = 1; i < n; i++)
			{
				sum.Add(sum[i - 1] + list[i]);
			}

			var ans = double.MaxValue;
			var list2 = new double[4];

			// 中央の区切りは全探索
			// 中央の区切りが移動した場合は、計算済みの左区切りと右区切りを利用する
			int left = 0;
			int right = 2;
			for (int i = 1; i < n - 2; i++)
			{
				// 左区間の区切り
				while (left < i &&
					 // sum[left + 1] - (sum[i] - sum[left + 1]) = 2 * sum[left + 1] - sum[i]
					 // sum[left] - (sum[i] - sum[left]) = sum[left] - sum[i] + sum[left] = 2 * sum[left] - sum[i]
					 // 境界を求める。一つ先が減っているなら、次へ移動する。
					 Math.Abs(2 * sum[left + 1] - sum[i]) < Math.Abs(2 * sum[left] - sum[i]))
				{
					left++;
				}

				// 右区間の区切り
				while (right < n &&
					// (sum[right] - sum[i]) - (sum[n-1] - sum[right]) = sum[right] - sum[i] - sum[n-1] - sum[right] = 2 * sum[right] - sum[i] - sum[n-1]
					Math.Abs(2 * sum[right + 1] - sum[i] - sum[n - 1]) < Math.Abs(2 * sum[right] - sum[i] - sum[n - 1]))
				{
					right++;
				}

				list2[0] = sum[left];
				list2[1] = sum[i] - sum[left];
				list2[2] = sum[right] - sum[i];
				list2[3] = sum[n - 1] - sum[right];
				ans = Math.Min(ans, list2.Max() - list2.Min());
			}

			WriteLine(ans);
		}
	}
}


Measured memory_bytes: 34892
/* ex2_3
	kanon */

#include <stdio.h>

int main(void) {
  //与えられる値を入れる変数を宣言
  int Number,Area;
  
  //変数に値を入力する
  scanf("%d",&Number);
  scanf("%d",&Area);
  
  //Number×NumberーArea（答え）を出力
  printf("%d\n",Number*Number-Area);
  
  return 0;
}


Measured memory_bytes: 128
#include <malloc.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

//ABC166D
//ABC166C
//ABC166B
//ABC166A
int main(void) {
  int n, k, i, cou=0, tmp;
  char a[3];
  scanf("%s", a);
  if(a[1]=='B') printf("ARC");
  else printf("ABC");

}


Measured memory_bytes: 1680
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;

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

    for(int i=0; i<4; ++i){
        string ans(n, ' ');
        ans[0] = (i&1) ? 'S' : 'W';
        ans[1] = (i&2) ? 'S' : 'W';

        for(int j=1; j<n-1; ++j){
            if((ans[j] == 'W') ^ (s[j] == 'x'))
                ans[j+1] = 'S' + 'W' - ans[j-1];
            else
                ans[j+1] = ans[j-1];
        }

        if((ans[0] == 'W') ^ (s[0] == 'x') ^ (ans[n-1] != ans[1]))
            continue;
        if((ans[n-1] == 'W') ^ (s[n-1] == 'x') ^ (ans[n-2] != ans[0]))
            continue;

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

    cout << -1 << endl;
    return 0;
}


Measured memory_bytes: 512
<?php
/*
・２つの値が同じなら1と1を足す操作が最短
・1 5 4の場合　２を２回足して 5 5 4 
・435 455 655 666
・263 663 665 667 777

・まず２つ以上の値が同値でないか見る
・まず２を一つの値に足して残りの２つどちらかと重ねる
・重なったら三つ目に２を足して２つの値よりおおきくなったら止める
・最後に1 1を足す

・2奇数があった場合、２つ偶数だった場合 ２つあるほうに２をたす

*/
  

//fscanf(STDIN,"%d%d%d",$a,$b,$c);
$abc=explode(" ",trim(fgets(STDIN)));

sort($abc);


$re_c=0;
$gu_c=0;
$ki_c=0;
for($i=0;$i<3;$i++){
 if($abc[$i]%2==0){
   $gu_c++;
 }else{
   $ki_c++;
 }
}

//全部偶数or奇数の時
if($gu_c==3 || $ki_c==3){
  $re_c+=(end($abc)-$abc[0])/2;
  $re_c+=($abc[2]-$abc[1])/2;
}

//2つ奇数or偶数の時
if($ki_c==2 || $gu_c==2){
  //値を揃えた
  if(($abc[1]-$abc[0])%2==0){
    $re_c+=abs(($abc[1]-$abc[0]))/2;
    $same_val=max($abc[1],$abc[0]);
    $the_other=$abc[2];
  }elseif(($abc[2]-$abc[0])%2==0){
    $re_c+=abs($abc[2]-$abc[0])/2;
    $same_val=max($abc[2],$abc[0]);
    $the_other=$abc[1];
  }else{
    $re_c+=abs($abc[2]-$abc[1])/2;
    $same_val=max($abc[2],$abc[1]);
    $the_other=$abc[0];
  }
  
  //３つ目を揃える
  if($same_val<$the_other){
    $re_c+=$the_other-$same_val;
  }else{
    $re_c+=ceil(abs($the_other-$same_val)/2);
    $re_c++;
  }
  

}

//5回 41-5=36/2=18
echo $re_c."\n";

Measured memory_bytes: 4604
#include<bits/stdc++.h>
#define maxn 105
#define ll long long
using namespace std;
inline ll read(){
	ll x=0,c;while(!isdigit(c=getchar()));
	while(x=x*10+c-'0',isdigit(c=getchar()));
	return x;
}
char a[maxn],b[maxn],c[maxn];
int n;
int main(){
	n=read();
	scanf("%s",a+1);scanf("%s",b+1);scanf("%s",c+1);
	int ans=0;
	for(int i=1;i<=n;i++){
		if(a[i]==b[i]&&b[i]!=c[i])ans++;
		else if(a[i]!=b[i]&&b[i]==c[i])ans++;
		else if(b[i]!=c[i]&&a[i]==c[i])ans++;
		else if(a[i]!=b[i]&&b[i]!=c[i])ans+=2;
	}printf("%d\n",ans);return 0;
}

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

int main() {
  int n;
  cin >> n;
  vector<pair<int, int>> x(n);
  vector<int> o(n);
  for(int i = 0; i < n; i++) {
    cin >> x.at(i).first;
    x.at(i).second = i;
  }
  sort(x.begin(), x.end());
  for(int i = 0; i < n; i++) {
    if(i < n / 2)
      o.at(x.at(i).second) = x.at(n / 2).first;
    else
      o.at(x.at(i).second) = x.at(n / 2 - 1).first;
  }
  for(int i = 0; i < n; i++)
    cout << o.at(i) << endl;
}

Measured memory_bytes: 4480
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define E "\n"

using namespace std;
const long long MOD = (long long)1e9 + 7;

int cnt;
string s, t;

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> s >> t;
    for (int i = 0; i < 3; i++) {
        if (s[i] == t[i]) cnt++;
    }
    cout << cnt << E;
    //system("pause");
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define lper(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[4]={1,0,-1,0};
const ll dx[4]={0,-1,0,1};
int main(){
    double a,b,x;
    cin >> a >> b >> x;
    double k = x/a;
    double ans, t;
    t = b*b/2/k;
    CST(7);
    if(b/t<=a){
        ans = atan(t)*180/3.141592653589;
        cout << ans << endl;
        return 0;
    }
    else{
        t = 2/a/a*(a*b-k);
        ans = atan(t)*180/3.141592653589;
        cout << ans << endl;
    }
}

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

int gcd(int x, int y);

const int INF = 1001001001;

/*struct mint {
    ll x; // typedef long long ll;
    mint(ll x = 0) :x((x% mod + mod) % mod) {}
    mint operator-() const { return mint(-x); }
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod - a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this; }
    mint operator+(const mint a) const { return mint(*this) += a; }
    mint operator-(const mint a) const { return mint(*this) -= a; }
    mint operator*(const mint a) const { return mint(*this) *= a; }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const { return pow(mod - 2); }
    mint& operator/=(const mint a) { return *this *= a.inv(); }
    mint operator/(const mint a) const { return mint(*this) /= a; }
};
istream& operator>>(istream & is, const mint & a) { return is >> a.x; }
ostream& operator<<(ostream & os, const mint & a) { return os << a.x; }*/


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

    if (r < 1200)
        cout << "ABC" << endl;
    else if (r < 2800)
        cout << "ARC" << endl;
    else
        cout << "AGC" << endl;

    return 0;
}

/*���C�u�����ő����*/
//���[�O���b�h�̌ݏ��@
int gcd(int x, int y) {
    int num[3];
    num[0] = (x > y) ? x : y;
    num[1] = (x <= y) ? x : y;
    num[2] = num[0] % num[1];

    while (num[2]) {
        num[0] = num[1];
        num[1] = num[2];
        num[2] = num[0] % num[1];
    }

    return num[1];
}

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

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

const int INF = 1000000007;

int main(void){
	int n, m; cin>>n>>m;
	vector<P> a, b;
	for(int i=0;i<m;i++) {
		int p, y; cin>>p>>y;
		a.push_back(make_pair(p, y));
		b.push_back(make_pair(p, y));
	}


	map<P, int> mp;
	sort(b.begin(), b.end());
	int city = b[0].first;
	int cnt = 1;
	for(int i=0;i<m;i++) {
		if(city == b[i].first) {
			mp[b[i]] = cnt;
			cnt++;
		}
		else {
			city = b[i].first;
			cnt = 1;
			i--;
		}
	}

	cout<<endl<<endl;

	for(int i=0;i<m;i++) {
		printf("%06d%06d\n", a[i].first, mp[a[i]]);
	}
	
	return 0;
}

Measured memory_bytes: 9324
#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++)
#define rep1(i,n) for(ll i=1;i<=(n);i++)
#define rrep1(i,n) for(ll i=(n);i>=1;i--)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)

int main(){
	ll H,W; cin>>H>>W;
	char field[50][50];
	ll ans[50][50];
	rep(i,H){
		string tmp; cin>>tmp;
		rep(j,W) field[i][j]=tmp[j];
	}
	rep(i,H)rep(j,W){
		if(field[i][j]=='#'){
			ans[i][j]=10;
			continue;
		}
		ll tmp=0;
		for(ll dx=-1;dx<=1;dx++)for(ll dy=-1;dy<=1;dy++){
			ll nx=i+dx,ny=j+dy;
			if(0<=nx && nx<H && 0<=ny && ny<W && field[nx][ny]=='#') tmp++;
		}
		ans[i][j]=tmp;
	}
	rep(i,H){
		rep(j,W){
			if(ans[i][j]==10) cout<<"#";
			else cout<<ans[i][j];
		}
		cout<<endl;
	}
}

Measured memory_bytes: 256
_dog_no = int(input())
_letter = [chr(i) for i in range(97,97+26)]
_dog_name = ""
for _i in range(11):
  _dog_no -= 1
  _dog_name = _letter[_dog_no % 26] + _dog_name
  _dog_no = _dog_no // 26
  if _dog_no < 1:
    break
print(_dog_name)

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

int main() {
    ll n;
    cin>>n;
    ll sum=0;
    ll keta=-1;
    while(true){
        keta+=2;
        ll ma=pow(10,keta);
        for(ll i=pow(10,keta-1);i<ma;i++){
            if(i>n){
                cout<<sum<<endl;
                return 0;
            }
            sum++;
        }
    }
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for (int i = (a); i <= (b); ++i)
#define REPD(i,a,b) for (int i = (a); i >= (b); --i)
#define FORI(i,n) REP(i,1,n)
#define FOR(i,n) REP(i,0,int(n)-1)
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define vi vector<int>
#define ll long long
#define SZ(x) int((x).size())
#define DBG(v) cerr << #v << " = " << (v) << endl;
#define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++)
#define fi first
#define se second

const int N = 100100;
int n,k;
int a[N], p[N], vis[N], dep[N];
vi g[N];
int res;

void dfs(int u) {
	if (u==0) return;
	vis[u] = 1;
	if (dep[u] == k-1 && a[u] != 0) {
		res++;
	} else {
		dep[a[u]] = max(dep[a[u]], dep[u]+1);
	}
	p[a[u]]--;
	if (p[a[u]]==0) dfs(a[u]);
}

int main() {
	scanf("%d%d", &n, &k);
	FOR(i,n) scanf("%d", &a[i]);
	FOR(i,n) a[i]--;
	if (a[0] != 0) res++;
	a[0]=-1;
	FORI(i,n-1) g[a[i]].pb(i);
	FORI(i,n-1) p[a[i]]++;
	FOR(i,n) if (vis[i]==0 && p[i]==0) dfs(i);
	printf("%d\n", res);
	return 0;
}


Measured memory_bytes: 7296
n, m = gets.split.map(&:to_i)

@par = Array.new(n+1) {|i| i}
@count = Array.new(n+1, 1)

find =->(x){@par[x] = @par[x] == x ? x : find.(@par[x])}
union =->(x, y) {
    x = find.(x)
    y = find.(y)
    return if x == y
    @par[x] = y
    @count[y] += @count[x]
}

m.times do
    a, b = gets.split.map(&:to_i)
    union.(a, b)
end

puts @count.max

Measured memory_bytes: 17452
#include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(a)-1;i>=b;i--)
#define chmin(a,b) (a)=min((a),(b));
#define chmax(a,b) (a)=max((a),(b));
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define printV(v) cerr<<(#v)<<":";for(auto(x):(v)){cerr<<" "<<(x);}cerr<<endl;
#define printVS(vs) cerr<<(#vs)<<":"<<endl;for(auto(s):(vs)){cerr<<(s)<< endl;}
#define printVV(vv) cerr<<(#vv)<<":"<<endl;for(auto(v):(vv)){for(auto(x):(v)){cerr<<" "<<(x);}cerr<<endl;}
#define printP(p) cerr<<(#p)<<(p).first<<" "<<(p).second<<endl;
#define printVP(vp) cerr<<(#vp)<<":"<<endl;for(auto(p):(vp)){cerr<<(p).first<<" "<<(p).second<<endl;}

inline void output(){ cerr << endl; }
template<typename First, typename... Rest>
inline void output(const First& first, const Rest&... rest) {
    cerr << first << " "; output(rest...);
}

using ll = long long;
using Pii = pair<int, int>;
using TUPLE = tuple<int, int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
const int inf = 1ll << 60;
const int mod = 1e9 + 7;
using Graph = vector<vector<int>>;

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

    int n;
    cin >> n;
    string s;
    cin >> s;
    int x = 0;
    int ans = 0;
    for (auto c : s) {
        if (c == 'I') {
            x++;
        }
        else {
            x--;
        }
        chmax(ans, x);
    }
    cout << ans << endl;
}


Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <vector>
#include <regex>
#include <map>
#include <set>
using namespace std;
using ll = long long;

int main() {
    int N;
    cin >> N;
    
    int H[N];
    for(int i=0;i<N;i++){
        cin >> H[i];
    }
    
    if(N==1){
        cout << "Yes" << endl;
        return 0;
    }
    
    for(int i=N-2;i>=0;i--){
        if(H[i]-1==H[i+1]){
            H[i] -= 1;
        }
    }
    
    int cnt=0;
    for(int i=1;i<N;i++){
        if(H[i-1]>H[i]){
            cnt++;
        }
    }
    if(cnt==0){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}



Measured memory_bytes: 640
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque




def main():
    num = int(input())
    data = list(map(int, input().split()))

    for i in range(num):
        data[i] = (data[i], i + 1)
    data.sort(key=lambda x: x[0])

    left = [0, 0] + [i + 1 for i in range(num)]
    right = [i + 1 for i in range(num)] + [num + 1, num + 1]
    ans = 0
    for i in range(num):
        ori_num, ori_ind = data[i]
        l1 = left[ori_ind]
        l2 = left[l1]
        r1 = right[ori_ind]
        r2 = right[r1]

        ans += ((l1 - l2) * (r1 - ori_ind) + (ori_ind - l1) * (r2 - r1)) * ori_num

        right[l1] = r1
        left[r1] = l1

    print(ans)


if __name__ == '__main__':
    main()



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

int main() {
  int N;
  cin >> N;
  
  int pos = 1;
  vector<bool> been(N, false);
  been.at(0) = true;
  
  vector<int> a(N);
  for (int i = 0; i < N; i++) cin >> a.at(i);
  
  bool fin = false;
  
  int i = 0;
  
  while (!fin) {
    
    pos = a.at(pos - 1);
    
    if (pos == 2) {
      fin = true;
    }
    else if (been.at(pos -1)) {
      cout << -1 << endl;
      break;
    }
    
    been.at(pos - 1) = true;
    
    i++;
  }
  
  if (fin) cout << i << endl;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int main(){
	string s; cin>>s;
	int cnt=0;
	for(int i=0;i<s.size();i++){
		if(s[i]=='?') {
			s[i]='D';
		}
	}
	cout<<s<<endl;
	return 0;
}

Measured memory_bytes: 3756
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int main(void)
{
    long long ans = 0;
    string s;

    cin >> s;
    
    if (s == "Sunny") cout << "Cloudy" << endl;
    else if (s== "Cloudy") cout << "Rainy" << endl;
    else cout << "Sunny" << endl;

    return 0;
}


Measured memory_bytes: 760
from collections import deque

z=list(input())
Q=deque()
for i in z:
  Q.append(i)
q=int(input())

cnt=0

for i in range(q):
  x=input()
  if x[0]=='1':
    cnt+=1
    cnt%=2
    
  elif x[0]=='2':
    if x[2]=='1':
        if cnt%2==0:
            Q.appendleft(x[4])
        else:
            Q.append(x[4])

    else:
        if cnt%2==0:
            Q.append(x[4])
        else:
            Q.appendleft(x[4])
      
if cnt%2==1:
  Q.reverse()


print(''.join(Q))

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



int main(){
    int N;
    string s;
    cin>>N>>s;
    
    int count=0;
    
    for(int i=1;i<N;i++){
        if(s.at(i-1)==s.at(i)){
            continue;
        }else{
            count++;
        }
    }
    
    cout<<(count+1)<<endl;
    
    return 0;
}



Measured memory_bytes: 512
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int lld;

const lld N = 200043;
const lld MOD = 1000000007;

lld add(lld x, lld y)
{
    x =((x%MOD)+(y%MOD))%MOD;
    while(x >= MOD) x -= MOD;
    while(x < 0) x += MOD;
    return x;
}

lld mul(lld x, lld y)
{
    return ((x%MOD)*(y%MOD))% MOD;
}

lld binpow(lld x, lld y)
{
    lld z = 1;
    while(y)
    {
        if(y & 1) z = mul(z, x);
        x = mul(x, x);
        y >>= 1;
    }
    return z;
}

lld inv(lld x)
{
    return binpow(x, MOD - 2);
}

lld divide(lld x, lld y)
{
    return mul(x, inv(y));
}

// Combinations

/*
lld fact[N];

void precalc()
{
    fact[0] = 1;
    for(lld i = 1; i < N; i++)
        fact[i] = mul(fact[i - 1], i);
}

lld C(lld n, lld k)
{
    return divide(fact[n], mul(fact[k], fact[n - k]));
}
*/
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    lld t,i,j;
    //cin>>t;
    t=1;
    while(t--)
    {
        lld n;
        cin>>n;
        vector<lld>ar;
        vector<lld>br;
        for(i=0;i<n;i++)
        {
            lld a,b;
            cin>>a>>b;
            ar.push_back(a+b);
            br.push_back(a-b);
        }
        sort(ar.begin(),ar.end());
        sort(br.begin(),br.end());
        lld a=ar[ar.size()-1]-ar[0];
        lld b=br[br.size()-1]-br[0];
        cout<<max(a,b)<<endl;
    }
}





Measured memory_bytes: 6696
#include <bits/stdc++.h>
using namespace std;
int main(){
    long long N, K;
    cin >> N >> K;
    vector<long long> A(N);
    for(int i = 0; i < N; i++) cin >> A[i];
    sort(A.begin(), A.end());
    if(K == 0) {
        cout << A[N - 1] << endl;
        return 0;
    }
    long long lb = 0, ub = A[N - 1];
    while(ub - lb > 1){
        long long mid = (ub + lb) / 2;
        long long cnt = 0;
        for(int i = 0; i < N; i++){
            long long syo = A[i] / mid;
            if(A[i] % mid == 0) syo--;
            cnt += syo;
        }
        if(cnt > K) lb = mid;
        else ub = mid;
    }
    cout << ub << endl;
}

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

typedef long long ll; 
#define inf 1000*1000*1000+9
#define infl (ll)inf*inf
#define sz(x) ((int) x.size())
#define all(a) a.begin(),a.end()
const int mod=1e9+7; 

const int nax=1e6+6; 
vector<ll> tr[nax<<2]; 
ll sum[nax<<2]; 
vector<ll> ss[nax<<2]; 
ll a[nax]; 

void build(int p, int l, int r){
	if(l==r){
		tr[p].push_back(a[l]); 
		sum[p]=a[l]; 
		ss[p].push_back(a[l]); 
	}	
	else {
		int m=(l+r)>>1, c1=p<<1, c2=p<<1|1 ; 	
		build(c1,l,m); 
		build(c2,m+1,r); 
		int i=0, j=0; 
		ll cur=0; 
		while(i< sz(tr[c1]) && j<sz(tr[c2])){
			if(tr[c1][i]<tr[c2][j]){
				tr[p].push_back(tr[c1][i]); i++; 
				ss[p].push_back(cur+tr[p].back()); 
				cur=ss[p].back(); 
			}	
			else {
				tr[p].push_back(tr[c2][j]); j++; 
				ss[p].push_back(cur+tr[p].back()); 
				cur=ss[p].back(); 
			}
		}
		while(i<sz(tr[c1])){
			tr[p].push_back(tr[c1][i]); i++; 
			ss[p].push_back(cur+tr[p].back()); 
			cur=ss[p].back(); 
		}
		while(j<sz(tr[c2])){
			tr[p].push_back(tr[c2][j]); j++; 
			ss[p].push_back(cur+tr[p].back()); 
			cur=ss[p].back(); 
		}
		for(int i:tr[p]){
			sum[p]+=i; 
		}
	}
}
ll agg=0; 
int mm; 
void query(int p, int l, int r, int i, int j, ll y){
	//if(agg>=y) return; 
	// cout<<p<<" " <<l<<" " <<r<<" " <<i<<" " <<j<<endl; 
	if(r<i || l>j) return; 
	if(i<=l && r<=j){
		int pos=upper_bound(all(tr[p]),mm)-tr[p].begin(); 	
		// for(int j:tr[p]) cout<<j<<" " ;  cout<<endl; 
		pos--; 
		if(pos>=0){
			agg+=ss[p][pos]; 	
		}
		return; 
	}
	int m=(l+r)>>1, c1=p<<1, c2=p<<1|1; 	
	query(c1,l,m,i,j,y); 
	query(c2,m+1,r,i,j,y); 
}

void solve(){
	int n; cin>>n; 
	for(int i=0;i<n;i++) cin>>a[i]; 
	build(1,0,n-1); 
	// int p=0; 
	// int j=1; 
	// while(p<4){
	// 	for(int i=0;i<(1<<p);i++){
	// 		cout<<sum[j+i]<<" " ; 
	// 	}
	// 	cout<<endl; 
	// 	j+=(1<<p); 
	// 	p++; 
	// }	
	int q; cin>>q; 
	while(q--){
		ll l,r,y;  
		cin>>l>>r>>y; 
		agg=0; 
		l--; r--; 
		int lo=0, hi=mod; 
		while((hi-lo)>1){
			mm=(lo+hi)>>1; 	
			agg=0; 
			query(1,0,n-1,l,r,y); 
			// cout<<mm<<" " <<agg<<endl; 
			// break; 
			if(agg>=y){
				hi=mm; 
			}
			else {
				lo=mm; 
			}
		}
		agg=0; 
		mm=hi; 
		query(1,0,n-1,l,r,y); 
		if(agg<y){
			cout<<-1<<endl; 
		}
		else {
			cout<<agg<<endl; 
		}
	}	
}

void pre(){
	int n; cin>>n; 
	string s; cin>>s; 
	if(n%2==0 && s.substr(0,n/2) == s.substr(n/2)){
		cout<<"Yes"<<endl; 
	}
	else {
		cout<<"No"<<endl; 
	}
}

int main(){
	pre(); 
}

Measured memory_bytes: 192000
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<climits>
#include<iostream>
#include<sstream>
#include<utility>
#include<map>
#include<vector>
#include<queue>
#include<algorithm>
#include<set>
#include<stack>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
int N,A[105];
ll res=1000000000;
int main()
{
	scanf("%d",&N);
	for(int i=0;i<N;i++)scanf("%d",&A[i]);
	for(int k=-100;k<=100;k++)
	{
		ll tmp=0;
		for(int i=0;i<N;i++)
			tmp+=(A[i]-k)*(A[i]-k);
		res=min(tmp,res);
	}
	printf("%ld\n",res);
	return 0;
}


Measured memory_bytes: 256
#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>>prime_factorize(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;
  vector<int>A(N),B(N),C(N-1);
  for(int i=0;i<N;i++){
    cin>>A[i];
  }
  for(int i=0;i<N;i++){
    cin>>B[i];
  }
  for(int i=0;i<N-1;i++){
    cin>>C[i];
  }
  int sum=0;
  for(int i=0;i<N;i++){
    sum+=B[A[i]-1];
    if(A[i+1]-A[i]==1){sum+=C[A[i]-1];}
  }
  cout<<sum<<endl;
  return 0;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
using ll = long long;
int main(void){
   string S;
   cin>>S;
   bool easy=true;
   int len=S.size();
   
   rep(i,len){
       if(i%2==0&&S[i]=='L'){
           easy=false;
           break;
       }
       else if(i%2==1&&S[i]=='R'){
           easy=false;
           break;
       }
   }
   if(easy==true){
       cout<<"Yes"<<endl;
   }
   else{
       cout<<"No"<<endl;
   }
    

}


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

int main() {
  ll k,cnt=0,a;
  cin >> k;
  queue<ll> lunlun;
  for(int i=1;i<=9;i++) lunlun.push(i);
  while(cnt<k){
    a = lunlun.front();lunlun.pop();cnt++;
    if (a%10==0){lunlun.push(a*10);lunlun.push(a*10+1);}
    else if(a%10==9){lunlun.push(a*10+8);lunlun.push(a*10+9);}
    else{lunlun.push(a*10+(a%10)-1);lunlun.push(a*10+(a%10));lunlun.push(a*10+(a%10)+1);}
  }
  cout << a << endl;
}


Measured memory_bytes: 1792
# 631

h, w = map(int, input().split())
a = [str(input()) for _ in range(h)]
jud = [[] for _ in range(h)]

for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            jud[i].append(j)

# print(jud)

flag = True

for k in range(len(jud) - 1):
    if max(jud[k]) in jud[k + 1] and jud[k][-1] == jud[k + 1][0]:
        continue
    else:
        flag = False

if flag:
    print("Possible")
else:
    print('Impossible')

Measured memory_bytes: 9208
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, j) for(int i = 0; i < (int)(j); i++)
constexpr int INF = 1 << 28;
using EdgeList = vector<vector<int>>;
 
// ?????£?????????????????°?????? E ????????£????????????????§£(Tarjan's algorithm)
// O(N + M) N: ????????°, M: ?????°
vector<vector<int>> strongly_connected_components(const EdgeList &E) {
    int N = E.size();
    vector<int> ord(N, -1), low(N);
    int cnt = 0;
    stack<int> stk;
    vector<bool> on_stack(N);
    vector<vector<int>> scc;    
    function<void(int, int)> dfs = [&] (int now, int pre) {
        stk.push(now);
        on_stack[now] = true;
        ord[now] = cnt++;
        low[now] = ord[now];
        for(int nxt : E[now]) {
            if(ord[nxt] < 0) {
                // not visited
                dfs(nxt, now);
                low[now] = min(low[now], low[nxt]);
            } else if(on_stack[nxt]) {
                // visited
                low[now] = min(low[now], ord[nxt]);
            } 
        }
        if(ord[now] == low[now]) {
            scc.push_back({});
            while(true) {
                int v = stk.top(); stk.pop();
                scc.back().push_back(v);
                on_stack[v] = false;
                if(v == now) break;
            }
        }
    };
    // ??£?????°????????????dfs(0)????????§OK
    rep(i, N) if(ord[i] < 0) dfs(i, -1);
    return scc;
}
#define all(v) v.begin(),v.end()
struct UnionFind{
    int n;
    vector<int> p;
    UnionFind(int nn):n(nn) {
        p.resize(n);
        rep(i, n) p[i] = i;
    }
    int root(int x) {
        return p[x] == x ? x : (p[x] = root(p[x]));
    }
    void unite(int x,int y) {
        x = root(x); y = root(y);
        if(x != y) p[y] = x;
    }
    bool query(int x,int y){
        return root(x) == root(y);
    }
};
int main() {
    int N, M; cin >> N >> M;
    EdgeList E(N);
    rep(i, M) {
        int a, b; cin >> a >> b;
        E[a].push_back(b);
    }
    auto scc = strongly_connected_components(E);
    
    UnionFind uf(N);
    for(auto &group : scc) for(int v : group) uf.unite(group.front(), v);
    
    int Q; cin >> Q;    
    rep(i, Q) {
        int u, v; cin >> u >> v;
        cout << uf.query(u, v) << endl;
    }
    return 0;
}

Measured memory_bytes: 4904