akhauriyash/Code-Regression huggingface dataset:
class UnionFind:
    def __init__(self,n):
        self.par = [i for i in range(n+1)]  #親のノード番号
        self.rank = [0]*(n+1)
    def find(self,x):  #xの根のノード番号
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def same_check(self,x,y):  #x,yが同じグループか否か
        return self.find(x) == self.find(y)
    def union(self,x,y):  #x,yの属するグループの併合
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        elif self.rank[x] > self.rank[y]:
            self.par[y] = x
        else:
            self.par[y] = x
            self.rank[x] += 1

N,K,L = map(int,input().split())
A = [list(map(int,input().split())) for i in range(K)]
B = [list(map(int,input().split())) for i in range(L)]

road = UnionFind(N)
train = UnionFind(N)

for i in range(K):
    road.union(A[i][0],A[i][1])
for i in range(L):
    train.union(B[i][0],B[i][1])

pair = [(road.find(i),train.find(i)) for i in range(1,N+1)]

from collections import Counter

#根が同じなら道路or鉄道でつなげる

c = Counter(pair)
print(*[c[i] for i in pair])

Measured memory_bytes: 103840
// * It's time to PLAY !

#include <bits/stdc++.h>

using namespace std;

#ifdef EXILE
#include "prettyprint.hpp"
#define debug(args) cerr << #args << " = " << args << endl;
#else
#define debug(args) 20040119
#endif

#define fastio ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define int long long
void OPEN(string str)
{
    freopen((str + ".inp").c_str(), "r", stdin);
    freopen((str + ".out").c_str(), "w", stdout);
}

void PLAY()
{
    int n;
    cin >> n;
    int a[n];
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
        a[i] -= i + 1;
    }
    int ans = 0;
    sort(a, a + n);
    for (int i = 0; i < n; ++i)
    {
        ans += abs(a[i] - a[n / 2]);
    }
    cout << ans;
}

signed main()
{
    fastio;
    PLAY();
    return 0;
}

Measured memory_bytes: 1792
N, M = map(int,input().split())
ab = []
cd = []
for _ in range(N): ab.append(list(map(int,input().split())))
for _ in range(M): cd.append(list(map(int,input().split())))

def distance(x1, x2, y1, y2):
    return abs(x1 - x2) + abs(y1 - y2)

ans_distance = [float('inf')] * N
ans = [float('inf')] * N
for i in range(N):
    for j in range(M):
        #print(distance(ab[i][0], cd[j][0], ab[i][1], cd[j][1]))
        if ans_distance[i] > distance(ab[i][0], cd[j][0], ab[i][1], cd[j][1]):
            ans_distance[i] = distance(ab[i][0], cd[j][0], ab[i][1], cd[j][1])
            ans[i] = j+1

for i in range(N):
    print(ans[i])

Measured memory_bytes: 3064
N,M = map(int,input().split())
KA = [list(map(int,input().split())) for i in range(N)]

unko = []
for j in range(1,M+1):
     unko.append(j)

count = 0
ans = 0

for k in range(M):
    for l in range(N):
        if unko[k] in KA[l][1:]:
            count += 1
    if count == N:
        ans += 1
    count = 0
        
          
print(ans)

Measured memory_bytes: 3064
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cerrno>
#include <clocale>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <limits>
#include <list>
#include <map>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <utility>
#include <vector>
#include <cwchar>
#include <cwctype>
#define fi first
#define se second
#define pb push_back
//#define mp make_pair
#define rep(i,n) for(register int (i)=0;(i)<(n);(i)++)
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int INF=0x3f3f3f3f;
const int dx[]={0,1,-1,0},dy[]={1,0,0,-1};
const int MOD=10009;
const int N=1e5+10;
const int h1=1009;
const int h2=101;

inline int read(){
	int ww=1,xx=0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-') ww=-ww;ch=getchar();}
	while(isdigit(ch)){xx=(xx<<1)+(xx<<3)+(ch^48);ch=getchar();}
	return ww*xx;
}

int Hash1(string s){
	int tmp=0;
	for(int i=0;i<s.size();i++) {tmp=h1*tmp+s[i]-'a'; tmp%=MOD;}
	return tmp;
}

int Hash2(string s){
	int tmp=0;
	for(int i=0;i<s.size();i++) {tmp=h2*tmp+s[i]-'a';tmp%=MOD;}
	return tmp;
}

int n;
string str[N];
LL ans;
map<pii,LL>mp;

string ch(string s){
	int c[26];
	for(int i=0;i<26;i++) c[i]=0;
	string T="";
	for(int i=0;i<s.size();i++) c[s[i]-'a']++;
	for(int i=0;i<26;i++) for(int j=0;j<c[i];j++) T+=(char)('a'+i);
	return T; 
}

signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
//	cout<<ch("bcacb")<<endl;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>str[i];
	for(int i=1;i<=n;i++)
		str[i]=ch(str[i]);
	sort(str+1,str+n+1);
	LL tmp=1;
	for(int i=1;i<=n;i++){
		if(str[i]==str[i-1]) tmp++;
		else {
			ans+=tmp*(tmp-1)/2LL;
			tmp=1LL;
		}
	}
	ans+=tmp*(tmp-1)/2LL;
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 7296
int main(){
  int i,j,k,minj,swap,count=0,temp;
  int a[10000];
  scanf("%d",&k);
  for(i=0;i<k;i++){
    scanf("%d",&a[i]);
  }
  for(i=0;i<k;i++){
    minj = i;
    swap = 0;
    for(j=i;j<k;j++){
      if(a[j] < a[minj]){
	        minj = j;
	        swap = 1;
      }
    }
    if(swap == 1){
        temp = a[minj];
        a[minj] = a[i];
        a[i] = temp;
        count++;
    }
  }
  for(i=0;i<k;i++){
    if(i == k -1){
        printf("%d\n",a[i]);
        break;
    }
    printf("%d ",a[i]);
  }
  printf("%d\n",count);
  return 0;
}



Measured memory_bytes: 2108
import java.util.*;
import java.lang.*;
import java.io.*;


public class Main{
	public static void main (String[] args) throws java.lang.Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		String[] s = br.readLine().split("\\s");
		int[] arr = new int[N];
		for(int i=0;i<N;++i) arr[i] = Integer.parseInt(s[i]);
		System.out.println(solve(arr,N));
	}
	
	private static int solve(int[] arr,int N){
		int[] dp = new int[N];
		dp[N-2] = Math.abs(arr[N-1] - arr[N-2]);
		for(int i=N-3;i>=0;--i){
			dp[i] = Math.min(dp[i+1] + Math.abs(arr[i] - arr[i+1]),dp[i+2] + Math.abs(arr[i] - arr[i+2]));
		}
		
		return dp[0];
	}
}

Measured memory_bytes: 33872
import bisect
n = int(input())
a = sorted(list(map(int,input().split())))
b = sorted(list(map(int,input().split())))
c = sorted(list(map(int,input().split())))
ans = 0
for i in range(n):
  ans += bisect.bisect_left(a,b[i])*(n-bisect.bisect_right(c,b[i]))
print(ans)

Measured memory_bytes: 107108
#include<cstdio>
#include<cmath>
#include<math.h> 
#include<cstring>
#include<iostream>
#include<algorithm>
#define pi acos(-1);
#define MAX 1e5;
using namespace std;
typedef long long ll;
int main()
{
	ll N;
	float a;
	ll b;
	cin >> N;
	int n = sqrt(N)+1;
	ll ans=0;
	//cout << n;
	for(ll i=1;i<=n;i++){
		a = N / (i*1.0);
		b = N / i;
		if (N % i==0) {
			if (ans == 0)ans = (i + b - 2);
			else ans = (ans > (i + b - 2)) ? (i + b - 2) : ans;
		}
	}
	cout << ans;
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = Integer.parseInt(sc.next());
        int b = Integer.parseInt(sc.next());
        int area = a * b;
        int perimeter = a*2 + b*2;
        System.out.println(area + " " + perimeter);
    }
}


Measured memory_bytes: 26020
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);++i)
constexpr int mod=1000000007;
constexpr int mod1=998244353;
vector<int> dx={0,1,0,-1},dy={-1,0,1,0};
bool inside(int y,int x,int h,int w){
	if(y<h && y>=0 && x<w && x>=0) return true;
	return false;
}





int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int h,w;cin >> h >> w;
	vector<vector<int>> c(10,vector<int>(10));
	rep(i,10){
		rep(j,10){
			cin >> c[i][j];
		}
	}
	vector<int> cnt(10);
	rep(i,h){
		rep(j,w){
			int a;cin >> a;
			if(a >= 0) cnt.at(a)++;
		}
	}
	rep(k,10){
		rep(i,10){
			rep(j,10){
				c[i][j] = min(c[i][j], c[i][k] + c[k][j]);
			}
		}
	}
	ll ans = 0;
	rep(i,10){
		ans += cnt.at(i) * c[i][1];
	}
	cout << ans << endl;
}


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

namespace AtCorder
{
    class Program
    {
        static void Main(string[] args)
        {
            string num = Console.ReadLine();
            string[] line = Console.ReadLine().Split(' ');
            string StrA = line[0];
            string StrB = line[1];

            var result =string.Join("", Enumerable.Zip(StrA, StrB, (a, b) => a.ToString() + b.ToString()));

            Console.WriteLine(result);
        }
    }
}

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

typedef long long ll;
typedef unsigned int ui;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<long long> vll;

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

    int ans = 0, n;
    cin >> n;

    ans += min(n, 9);
    ans += min(max(n - 99, 0), 900);
    ans += min(max(n - 9999, 0), 90000);
    cout << ans << '\n';

    return 0;
}

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

int N;
vector<vector<pair<int, int> > > E;
vector<int> ans;
void DFS(int n, int c){
  stack<int> st;
  st.push(n);
  ans[n] = c;
  while(!st.empty()){
    int cur = st.top(); st.pop();
    for(auto i : E[cur]){
      if(ans[i.first] >= 0) continue;
      st.push(i.first);
      if(i.second%2 == 0){
        ans[i.first] = ans[cur];
      }else{
        ans[i.first] = (ans[cur]+1)%2;
      }
    }
  }
  return;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> N;
  E.assign(N, vector<pair<int, int> >());
  ans.assign(N, -1);
  REP(i, N-1){
    int u, v, w; cin >> u >> v >> w; u--; v--;
    E[u].push_back({v, w});
    E[v].push_back({u, w});
  }
  DFS(0, 0);
  REP(i, N){
    cout << ans[i] << endl;
  }
}

Measured memory_bytes: 6784
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long int ll;
#define rep(i,n) for(int i=0;i<(int)n;i++)
int Min(int a, int b, int c) {
	if (a <= b) { return std::min(a, c); }
	else return std::min(b, c);
}
int main(void) {
	string str; cin >> str;
	if (str.at(0) == str.at(2))cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
N, W = map(int, input().split())
Wl = []; Vl = []
for i in range(N):
    w, v = map(int, input().split())
    Wl.append(w); Vl.append(v)
# dp[i番目までの品物を使用][wを超えない]
dp = [[0]*(W+10) for _ in range(N+10)]

for i in range(N):
    w, v = Wl[i], Vl[i]
    for j in range(W+1):
        if j+w < W+1: dp[i+1][j+w] = max(dp[i+1][j+w], dp[i][j]+v)
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])
print(max(dp[N]))

Measured memory_bytes: 120728
#ABC172C.rb
n,m,k = gets.split.map(&:to_i)
ar = gets.split.map(&:to_i)
br = gets.split.map(&:to_i)

max_count = 0
asum = 0
bsum = br.sum
j = m

(0..n).each do |i|
  if i == 0
    asum = 0
  else
    asum += ar[i-1]
  end
  
  if asum > k
    break
  end
  
  while bsum > k - asum
    j -= 1
    bsum -= br[j]
  end

  count = i + j

  if max_count < count
    max_count = count
  end
end

puts max_count


Measured memory_bytes: 41700
#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <random>
#include <functional>
#include <stack>
#include <iomanip>
#include <cassert>
//#include <boost/multiprecision/cpp_int.hpp>
#include <complex>
#include <cstdio>
#include <list>

//< in.txt > out.txt
using namespace std;
//std::ios::sync_with_stdio(false);
//std::cin.tie(0);
const long long MOD = 1e9 + 7;
typedef long long LL;
typedef long double LD;
typedef pair<LL, LL> PLL;
typedef pair<LD, LL> PDL;
typedef pair<LD, LD> PDD;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
//typedef boost::multiprecision::cpp_int bigint;

template<class T>
void in(T& x) {
	cin >> x;
}

template<class T1, class T2>
void in(pair<T1, T2>& p) {
	in(p.first);
	in(p.second);
}

template<class T>
void in(vector<T>& v, LL st = -1, LL en = -1) {
	if (st == -1) {
		st = 0;
		en = v.size() - 1;
	}
	for (LL n = st; n <= en; n++) {
		in(v[n]);
	}
}

typedef complex<LD> Point;
const LD eps = 1e-8;
const LD pi = acos(-1.0);

template<>
void in(Point& p) {
	LD r, i;
	cin >> r >> i;
	p = { r,i };
}

LL N;
vector<Point> points(N);

LD getsum(LD X, LD Y) {
	LD temp = 0;
	for (LL n = 0; n < N; n++) {
		temp = max(temp, (points[n].real() - X) * (points[n].real() - X) + (points[n].imag() - Y) * (points[n].imag() - Y));
	}
	return temp;
}

LD gety(LD X) {
	LD left = 0;
	LD right = 1000;
	for (LL t = 0; t < 100; t++) {
		LD c1 = getsum(X, (left * 2 + right) / 3);
		LD c2 = getsum(X, (left + right * 2) / 3);
		if (c1 > c2)left = (left * 2 + right) / 3;
		else right = (left + right*2) / 3;
	}
	return getsum(X, (left + right) / 2);
}

LD getx() {
	LD left = 0;
	LD right = 1000;
	for (LL t = 0; t < 100; t++) {
		LD c1 = gety((left * 2 + right) / 3);
		LD c2 = gety((left + right * 2) / 3);
		if (c1 > c2)left = (left * 2 + right) / 3;
		else right = (left + right * 2) / 3;
	}
	return gety(left);
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	cin >> N;
	points.resize(N);
	in(points);
	cout << setprecision(12) << sqrtf(getx()) << "\n";
	return 0;
}


Measured memory_bytes: 256
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>

using namespace std;

#define MAX 100000
#define INF 2140000000
#define MOD 1000000007

int main() {
	long long w, h, x, y;
	cin >> w >> h >> x >> y;

	long double area = (w * h) / (long double) 2;

	if (w % 2 == 0 && h % 2 == 0 && x == w / 2 && y == h / 2) {
		cout <<  area << " " << 1 << endl;
	}
	else {
		cout <<  area << " " << 0 << endl;
	}
	

	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>

main()
{
  int a,b;
  char c[10];
    while(scanf("%d %d",&a,&b)!=EOF)
    {
      sprintf(c,"%d",a+b);
      printf("%d\n",strlen(c));
    }

  return(0);
}


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

namespace ABC147
{
    class Program
    {
        static void Main(string[] args)
        {
            b();
        }

        public static void b()
        {
            string s = Console.ReadLine();
            int j = s.Length - 1;
            int ans = 0;
            for (int i = 0; i < s.Length; i++)
            {
                if(s[i] != s[j])
                { ans++; }
                j--;
            }
            Console.WriteLine(ans / 2);
        }
    }
}


Measured memory_bytes: 11092
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
using namespace std;
string a,b;
bool cmp(char ch,char ch2)
{
	return ch>ch2;
}
int main()
{
	while(cin>>a>>b)
	{
		sort(a.begin(),a.end());
		sort(b.begin(),b.end(),cmp);
		if(a>=b)
		{
			puts("No");
		}
		else 
		{
			puts("Yes");
		}
	}
}

Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
#include<iomanip>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
#include<string>
#include<math.h>
using namespace std;
 
int main(){
    int N,H,W;
    int ans = 0;

    cin >> N >> H >> W;

    for(int i = 0;i < N;i++){
        int h,w;
        cin >> h >> w;
        if(h >= H && w >= W)ans++;
    }

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

Measured memory_bytes: 256
N, W = map(int, input().split())
wv = []
for _ in range(N):
    wv.append(tuple(map(int, input().split())))

INF = 10**10
dp = [INF]*(10**5+1)
dp[0] = 0
for w, v in wv:
    newdp = dp[:]
    for vv in range(10**5):
        if v+vv>10**5:
            break
        newdp[v+vv] = min(dp[v+vv], dp[vv]+w)
    dp = newdp
for v, w in enumerate(reversed(dp)):
    if w<=W:
        print(10**5-v)
        break

Measured memory_bytes: 67084
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner input1 = new Scanner(System.in);
		int len = input1.nextInt();
		int total = 0;
		int num;
		boolean isPrime;

		for (int i = 0; i < len; i++) {
			num = input1.nextInt();
			isPrime = true;

			// check the base case
			if (num == 2 || num == 3 || num == 5 || num == 7 || num == 11) {
				isPrime = true;
				;
			}
			// if numbers can be divided by 2,3,5,7,11, it is not a prime number
			else if (num % 2 == 0 || num % 3 == 0 || num % 5 == 0 || num % 7 == 0 || num % 11 == 0) {
				isPrime = false;
			} else {
				// a final check
				for (int j = 3; j <= Math.sqrt(num); j++) {
					if (num % j == 0) {
						isPrime = false;
						break;
					}
				}
			}
			if (isPrime) {
				total++;
			}
		}
		System.out.println(total);
	}
}



Measured memory_bytes: 41216
#include<bits/stdc++.h>
using namespace std;//10 32 -1


inline int read()
{
	int ret=0,f=1; char c=getchar();
	while(c<48||c>57)
	{
		if(c=='-')f=-1;
	    c=getchar();
	}
	while(c>=48&&c<=57)ret=ret*10+c-48,c=getchar();
	return f*ret;
}
int n,a[105][105];
int main()
{
	n=read();
	for(int i=1; i<=2; ++i)
	for(int j=1; j<=n; ++j)a[i][j]=read();
	for(int i=2; i; --i)
	for(int j=n; j; --j)
	//ll i //i ll//no //_.. ///chafenyushu //xitong
	a[i][j]=a[i][j]+max(a[i+1][j],a[i][j+1]);
	printf("%d\n",a[1][1]);
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void) {
    int w, n;
    int *out, *hline;
    int i, j;
    char buf[8];
    int p;

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

    out   = (int *)calloc(w+1, sizeof(int));
    hline = (int *)calloc(2*n, sizeof(int));

    for (i=0; i<2*n; i+=2) {
        scanf("%s", buf);
        hline[i] = atoi(strtok(buf, ","));
        hline[i+1] = atoi(strtok(NULL, ","));
    }
    //for (i=0; i<4*n; i+=4) printf("%d %d\n", hline[i], hline[i+1]);

    for (i=1; i<=w; i++) {
        p = i;
        for (j = 0; j<2*n; j+=2) {
            if (p == hline[j]) p = hline[j+1];
            else if (p == hline[j+1]) p = hline[j];
        }
        out[p] = i;
    }

    for (i=1; i<=w; i++) printf("%d\n", out[i]);

    free(out);
    free(hline);

    return 0;
}


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

using namespace std;
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define sz size
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define FORN(i,a,b) for(int i=a;i<=b;i++)
#define FORRN(i,a,b) for (int i=(a);i>=(b);i--)
#define FORR(i,a,b) for (int i=(a);i>(b);i--)
typedef unsigned long long ull;
typedef long long ll;

int n;
int x[100005],y[100005];
vector<pair<int,int>> M,N;
vector<pair<int,pair<int,int>>> A;
int par[100005],rnk[100005];

int find(int v){
    if(par[v]==v)
        return v;
    return par[v]=find(par[v]);
}

void merge(int i,int j){
    i=find(i);
    j=find(j);

    if(i==j)
        return;
    if(rnk[i]<rnk[j]){ 
        par[i]=j;
    }else{
        par[j]=i;
        if(rnk[i]==rnk[j])
            rnk[i]++;
    }
}


int main(){
    ios_base::sync_with_stdio(false); //Fast I/O
    cin.tie(0);
    cout.tie(0);
	//freopen("input.in","r",stdin);
	//freopen("output.out","w",stdout);

    cin >> n;
    FOR(i,0,n){
        cin >> x[i] >> y[i];
        M.pb(mp(x[i],i));
        N.pb(mp(y[i],i));
    }

    sort(M.begin(),M.end());
    sort(N.begin(),N.end());

    FOR(i,0,n-1){
        int v=M[i].ss;
        int u=M[i+1].ss;
        int d=M[i+1].ff-M[i].ff;
        A.pb(mp(d,mp(v,u)));
    }

    FOR(i,0,n-1){
        int v=N[i].ss;
        int u=N[i+1].ss;
        int d=N[i+1].ff-N[i].ff;
        A.pb(mp(d,mp(v,u)));
    }

    ll res=0;
    int cc=0;
    FOR(i,0,n){
        par[i]=i;
        rnk[i]=0;
    }

    sort(A.begin(),A.end());

    FOR(i,0,(int)A.sz()){
        int c=A[i].ff;
        int v=A[i].ss.ff;
        int u=A[i].ss.ss;

        if(find(v)!=find(u)){
            merge(v,u);
            res+=c;
            cc++;
            if(cc==n-1){
                cout << res << endl;
                return 0;
            }
        }
    }

    return 0;
}


Measured memory_bytes: 7912
//#include <bits/stdc++.h>
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
//#include "boost/multiprecision/cpp_int.hpp"
//typedef boost::multiprecision::cpp_int 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;
typedef pair<dd,dd> d_d;
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;
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define fi first
#define se second
#define endl "\n"
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
//template<class T>void max(T a,T b){if(a<b)return b;else return a;}
//template<class T>void min(T a,T b){if(a>b)return b;else return a;}
//template<class T>bool Max(T&a, T b){if(a < b){a = b;return 1;}return 0;}
//template<class T>bool Min(T&a, T b){if(a > b){a = b;return 1;}return 0;}

//////////////////////////



int main(){fastio
    ll a,b;cin>>a>>b;
    cout<<a*(a-1)/2+b*(b-1)/2<<endl;
    
    return 0;
}


Measured memory_bytes: 256
from itertools import product

n, m, x = map(int, input().split())
C = []
M = []

for _ in range(n):
    c, *mi = map(int, input().split())
    C.append(c)
    M.append(mi)

sta = list(product((0, 1), repeat=n))
res = 10**10

for k in sta:
    tmp = 0
    cnt = [0] * m
    for j in range(n):
        if k[j] == 1:
            tmp += C[j]
            for l in range(m):
                cnt[l] += M[j][l]
    if min(cnt) >= x:
        res = min(res, tmp)

if res == 10**10:
    print(-1)
else:
    print(res)


Measured memory_bytes: 9524
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, n) for(int i = 0; i < n; i++)
#define all(a) a.begin(), a.end()
#define P pair<int, int>
#define F first
#define S second
#define mod 1000000007
#define MOD 998244353
#define INF 40000000000000000
int dx8[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
int dy8[8] = {1, 1, 1, 0, -1, -1, -1, 0};
int dx4[4] = {-1, 0, 1, 0};
int dy4[4] = {0, -1, 0, 1};
signed main(void) {
    int N, Q;
    cin >> N >> Q;
    vector<tuple<int, int, int>> V(N);
    rep(i, N) {
        int f, r, x;
        cin >> f >> r >> x;
        V[i] = make_tuple(x, f - x, r - x);
    }
    sort(all(V));
    map<int, int> M;
    set<int> S;
    rep(i, Q) {
        int d;
        cin >> d;
        S.insert(d);
        M[d] = -1;
    }
    S.insert(INF);
    rep(i, N) {
        int x, s, t;
        tie(x, s, t) = V[i];
        set<int>::iterator now;
        ;
        now = S.lower_bound(s);
        vector<int>w;
        while(*now < t) {
            M[*now] = x;
            w.push_back(*now);
            now++;
        }
        for(auto y:w)S.erase(y);
    }
    map<int, int>::iterator ite;
    ;
    for(ite = M.begin(); ite != M.end(); ite++) {
        P p = *ite;
        cout << p.S << endl;
    }
}


Measured memory_bytes: 28940
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define xx first
#define yy second
#define sci(n) scanf("%d",&n)
#define scii(n,m) scanf("%d%d",&n,&m)
#define sciii(n,m,w) scanf("%d%d%d",&n,&m,&w)
#define scl(n) scanf("%lld",&n)
#define scll(n,m) scanf("%lld%lld",&n,&m)
#define sclll(n,m,w) scanf("%lld%lld%lld",&n,&m,&w)
#define pf(a)   printf("%d\n",a)
#define CASE(a) printf("Case %d:\n",a)
#define dbg(i) printf("yo %lld\n", i)
#define endl '\n'
#define READ  freopen("input.txt","r",stdin)
#define WRITE freopen("output.txt","w",stdout);
#define pi acos(-1)
#define mem(a,b) memset(a,b,sizeof(a))
#define SQR(a) (a)*(a)
#define all(v) v.begin(),v.end()
#define pb push_back
#define pri priority_queue<int>
#define rev_pri priority_queue<int,vector<int>,greater<int> >
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define mod 1000000007
#define inf INT_MAX
#define eps 1e-9

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

using namespace __gnu_pbds;
using namespace std;


#define mxn 100005


//bool vis[1LL << 19];
const ll nax=100005;
ll ar[nax];
ll W[102],C[102];
void solve()
{
    ll a,b,n,w,k=0,c,i,q=0,j,l,m,mx=-1;
    cin>>n>>w;
    FOR(i,1,n+1)scll(W[i],C[i]);
    FOR(i,1,w+2)ar[i]=-1;
    for(i=1;i<=n;i++){
        for(j=w;j-W[i]>=0;j--){
            if(ar[j-W[i]]!=-1){
                ar[j]=max(ar[j],ar[j-W[i]]+C[i]);
                mx=max(mx,ar[j]);
            }
        }
    }cout<<mx<<'\n';
}
int main()
{
    //IOS;
    double start_time = clock();
    ll t=1,mex=1;
   //cin>>t;
    while(t--){
        solve();
    }
    double end_time = clock();
    //fprintf(stderr, "Time = %lf\n", (end_time - start_time) / CLOCKS_PER_SEC);
    return 0;
}


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

int main() {
  int n;
  cin>>n;
  int t[n],v[n];
  rep(i,n) cin>>t[i];
  rep(i,n) cin>>v[i];
  int s[n+1];
  s[0]=0;
  rep(i,n){
    s[i+1]=s[i]+t[i];
  }
  double ans[2*s[n]+1];
  rep(i,2*s[n]+1){
    ans[i]=min(i/2.0,s[n]-i/2.0);
  }
  rep(i,2*s[n]+1){
    rep(j,n){
      if(i/2.0<s[j]){
        ans[i]=min(ans[i],v[j]+s[j]-i/2.0);
      }
      else if(i/2.0>s[j+1]){
        ans[i]=min(ans[i],v[j]-s[j+1]+i/2.0);
      }
      else{
        ans[i]=min(ans[i],v[j]+0.0);
      }
    }
  }
  double res=0;
  rep(i,2*s[n]){
    res+=(ans[i]+ans[i+1])/4.0;
  }
  cout<<fixed<<setprecision(5);
  cout<<res<<endl;
}

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

using namespace std;

#define lli long long int
#define REP(i,s,n) for(int i=s;i<n;i++)
#define MOD 1000000007
#define NUM 2520
#define INF (1LL<<50)
#define DEBUG 0
#define mp(a,b) make_pair(a,b)
#define SORT(V) sort(V.begin(),V.end())
#define PI (3.141592653589794)

signed main(){

    lli x,a,b;
    cin>>x>>a>>b;

    lli over = b - a;

    if(over<=0)cout<<"delicious"<<endl;
    else if(over<=x)cout<<"safe"<<endl;
    else cout<<"dangerous"<<endl;

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int x,y;
  cin>>x>>y;
  for(int i=0;i<=x;i++){
    int j=x-i;
    if(i*4+j*2==y){
      puts("Yes");
      exit(0);
    }
  }
  puts("No");
  return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define reps(i,s,n) for(int i=(s); i<(n); i++)
#define all(v) v.begin(),v.end()
#define res(n) resize(n)
#define rev(v) reverse(v.begin(),v.end())
#define sor(v) sort(v.begin(),v.end())
#define outve(v) for(auto i : v) cout << i << " ";cout << endl
#define in(n,v) for(int i=0; i<(n); i++){cin >> v[i];}
#define out(n) cout << (n) << endl
#define fi first
#define se second
#define ve vector
#define pq priority_queue
#define vi vector<int>
#define vl vector<long long>
#define vii vector<vector<int>>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll mod = 1000000007;



int main()
{

    ll A,B,K;
    cin >> A >> B >> K;
    if(A >= K){
        A -= K;
    }else{
        K -= A;
        A = 0;
        if(B >= K){
            B -= K;
        }else{
            K -= B;
            B = 0;
            
        }
    }

    cout << A << " " << B << endl;

    return 0;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <algorithm>
#include <time.h>
#include <chrono>
#include <random>
//#include <math.h>
#include <cmath>
#include <fstream>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <stdlib.h>
#include <cstring>
#include <iomanip>
#include <cstdio>
#include <cassert>
#include <bitset>

#pragma comment(linker, "/STACK:36777216")
using namespace std;

#define flu fflush(stdout)
#define gg return 0
#define mp make_pair

typedef long double ptype;

long long mod = /*27449*//*998244353*/ /*1e9 + 7*/998244353 /*1e9 + 9*/;
int inf = 1e9;
double eps = 1e-7;
long double pi = acosl(-1);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ifstream in("input.txt");
ofstream out("output.txt");

int tree[2][800000]; //update value;
int a[2][200000]; // real values;
int n;

void build()
{
	for (int i = 1; i <= 4 * n; i++)
	{
		tree[0][i] = tree[1][i] = 1e9;
	}
	for (int i = 0; i < n; i++)
	{
		a[0][i] = a[1][i] = n - 1;
	}
}

void push(int id, int v)
{
	tree[id][v << 1] = min(tree[id][v << 1], tree[id][v]);
	tree[id][v << 1 | 1] = min(tree[id][v << 1 | 1], tree[id][v]);
}

int get(int id, int v, int tl, int tr, int p)
{
	if (tl == p && p == tr)
		return a[id][p] = min(a[id][p], tree[id][v]);
	int tm = (tl + tr) / 2;
	push(id, v);
	if (p <= tm)
		return get(id, v << 1, tl, tm, p);
	else 
		return get(id, v << 1 | 1, tm + 1, tr, p);
}

void setv(int id, int v, int val, int l, int r, int tl, int tr) 
{
	if (r < l) return;
	if (l == tl && tr == r) 
		tree[id][v] = min(tree[id][v], val);
	else
	{
		int tm = (tl + tr) / 2;
		setv(id, v << 1, val, l, min(r, tm), tl, tm);
		setv(id, v << 1 | 1, val, max(l, tm + 1), r, tm + 1, tr);
	}
}

void solve()
{
	cin >> n;
	build();
	int q;
	cin >> q;
	long long ans = (n - 2ll) * (n - 2ll);
	while (q--)
	{
		int type;
		int x;
		cin >> type;
		cin >> x;
		x--;
		type--;
		int pos = get(type, 1, 0, n - 1, x);
		ans -= pos - 1;
		setv(!type, 1, x, 0, pos - 1, 0, n - 1);
	}
	cout << ans;
}

int main()
{
	cout << setprecision(20) << fixed;
	cin.tie();
	cout.tie();
	clock_t t1 = clock();
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int t;
	//cin >> t;
	t = 1;
	while (t--) {
		solve();
		//test();
	}
	//cout << (clock() - t1) * 1.0 / CLOCKS_PER_SEC;
	gg;
}

Measured memory_bytes: 11384
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10 + 5e5;

int n,m,ans[MAXN],t[2*MAXN],ri[MAXN],f[MAXN];
pair < int,int > a[MAXN],c[MAXN];

void Build()
{
	for (int i = n-1; i > 0; --i)
		t[i] = t[i << 1] + t[i << 1 | 1];
}

void Update(int p)
{
	for (t[p += n] = 0; p > 1; p >>= 1)
		t[p >> 1] = t[p] + t[p ^ 1];
}

int Query(int l,int r)
{
	int res = 0;
	for (l += n, r += n; l < r; l >>= 1, r >>= 1)
	{
		if (l&1) res += t[l++];
    	if (r&1) res += t[--r];
	}

	return res;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(NULL); cout.tie(NULL);

	cin >> n >> m;
	memset(f, -1, sizeof f);
	for (int i = 0; i < n; ++i)
	{
		int x;
		cin >> x;
		c[i].first = f[x];
		c[i].second = i;
		f[x] = i;
	}


	sort(c,c+n);

	for (int i = 0; i < m; ++i)
	{
		int x;
		cin >> a[i].first >> x;
		a[i].second = i;
		ri[i] = x;
	}

		for (int i = 0; i < n; ++i) t[n+i] = 1;

		Build();

	sort(a,a+m);

    int k = 0;
	for (int i = 0; i < m; ++i)
	{
		if (k < n) while (c[k].first < a[i].first-1) Update(c[k++].second);

		ans[a[i].second] = ri[a[i].second] - a[i].first - Query(a[i].first-1,ri[a[i].second]) + 1;

	}

	for(int i = 0; i < m; ++i)
		cout << ans[i] << "\n";

	return 0;
}


Measured memory_bytes: 21280
#include "bits/stdc++.h"

using namespace std;
using ll = long long;
using ull = unsigned long long;

typedef pair<ll, ll> P;
typedef pair<ll, P> PP;
typedef pair<P, P> PPP;

const ll MOD = 1e9 + 7;
const ll INF = 9e18;
const double DINF = 5e14;
const double eps = 1e-10;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };

#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
#define pb push_back
#define eb emplace_back
#define fr first
#define sc second

int n, p[5010], dp[5010][5][5], ans = 100000;

int main() {
	cin >> n;
	for (int i = 1;i <= n;i++)cin >> p[i];
	for (int i = 0;i <= n;i++) {
		for (int j = 0;j < 4;j++) {
			for (int k = 0;k < 4;k++) {
				dp[i][j][k] = 1000000;
			}
		}
	}
	dp[0][0][0] = 0;
	for (int i = 1;i <= n;i++) {
		for (int j = 0;j < 4;j++) {//そこだけ裏返す(i==1 or i==n)
			for (int k = 0;k < 4;k++) {//そことその次を裏返す(1<=i<n)
				for (int l = 0;l < 4;l++) {//前の一点だけ裏返していたとき
					for (int m = 0;m < 4;m++) {//前で今を含めて裏返していたとき
						if (i == 1) {
							if (j + k < p[i])continue;
							dp[i][j][k] = min(dp[i][j][k], j + k * 2);
						}
						else if (i != n) {
							if (j != 0)continue;
							if (i != 2 && l != 0)continue;
							if (k + m < p[i])continue;
							dp[i][j][k] = min(dp[i][j][k], dp[i - 1][l][m] + k * 2);
						}
						else {
							if (j + m < p[i])continue;
							if (l != 0)continue;
							ans = min(ans, dp[i - 1][l][m] + j);
						}
					}
				}
			}
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3596
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list
#from itertools import combinations # (string,3) 3回
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    n = int(input())
    A = sorted(readInts())
    dic = {}
    for a in A:
        if a in dic:
            print('NO')
            exit()
        else:
            dic[a] = 1
    print('YES')
if __name__ == '__main__':
  main()


Measured memory_bytes: 32972
#include <bits/stdc++.h>
#define mk make_pair
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;
int a[110];
int main(){
    int x, y;
    bool l=1;
        for(int i=0; i<3; ++i){
            scanf("%d%d",&x,&y);
            ++a[x];
            ++a[y];
            if(a[x]>=3||a[y]>=3){
                l=0;
            }
        }
        if(l)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
  return 0;
}




Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<ll, P> PP;
 
static const double EPS = 1e-8;
static const double PI = 4.0 * atan(1.0);
static const ll INF = 1023456789;
 
#define REP(i,n)	for(int i=0;i<n;++i)
#define REPR(i,n)	for(int i=n-1;i>=0;--i)
#define FOR(i,s,n)	for(int i=s;i<n;++i)
#define FORR(i,s,n)	for(int i=n-1;i>=s;--i)
#define ALL(c)		(c).begin(),(c).end()
#define CLEAR(v)	memset(v,0,sizeof(v))
#define MP(a,b)		make_pair((a),(b))
#define ABS(a)		((a)>0?(a):-(a))
#define F			first
#define S			second

ll n, a[100002];
 
int main(int argc, char **argv) {
	cin >> n;
	REP(i, n) cin >> a[i+1];
	a[0] = a[n+1] = 0;
	ll s = 0;
	REP(i, n+1) s += abs(a[i+1] - a[i]);
	REP(i, n) cout << (s - abs(a[i+1] - a[i]) - abs(a[i+2] - a[i+1]) + abs(a[i+2] - a[i])) << endl;
	return 0;
}
 

Measured memory_bytes: 2048
#include <bits/stdc++.h>
#define rep(i,n) for (int i=0;i<=(n);++i)
using namespace std;
int main(){
	int a,b,c,x;cin>>a>>b>>c>>x;
	int cnt=0;
	rep(i,a){
		rep(j,b){
			rep(k,c){
				if(500*i+100*j+50*k==x){
					cnt++;
				}
			}
		}
	}
	cout<<cnt<<endl;
}

Measured memory_bytes: 256
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<unordered_map>
#include<array>
#include<map>
#include<bitset>
#include<iomanip>
using namespace std;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
//ios::sync_with_stdio(false);
//std::cin.tie(0);
//<< setprecision(20)
//19234567892927;
const int mod=1e9+7;
const llint big=1e15+100;
const long double pai=3.141592653589793238462643383279502884197;
const long double ena=2.71828182845904523536;
const long double eps=1e-7;
template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}}
template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}}
template <class T> void soun(T& ar){sort(ar.begin(),ar.end());ar.erase(unique(ar.begin(),ar.end()),ar.end());}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){return a/gcd(a,b)*b;}

int main(void){
	int H,W,i,j,k;cin>>H>>W;
	int co[10][10];
	for(i=0;i<10;i++){
		for(j=0;j<10;j++){
			cin>>co[i][j];
		}
	}
	co[1][1]=0;
	for(j=0;j<10;j++){
		for(i=0;i<10;i++){
			for(k=0;k<10;k++){
				mineq(co[i][k],co[i][j]+co[j][k]);
			}
		}
	}
	llint ans=0;
	for(i=0;i<H*W;i++){
		int a;cin>>a;if(a==-1){continue;}
		ans+=co[a][1];
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); i++)
#define sz(x) int(x.size());
typedef long long ll;
typedef pair<int,int> P;
const int mod = 1e9+7;
using Graph = vector<vector<P>>;
Graph G;
ll dist[100100];
void dfs(int u, int p, ll d) {
  dist[u] = d;
  for (auto v : G[u]) {
    if (v.first == p) continue;
    dfs(v.first,u,d+v.second);
  }
}

int main() {
  int n;
  cin >> n;
  G.resize(n);

  rep(i,n-1) {
    int a, b, c;
    cin >> a >> b >> c;
    G[--a].push_back({--b,c});
    G[b].push_back({a,c});
  }

  int q,k;
  cin >> q >> k;
  dfs(--k,-1,0);

  rep(i,q) {
    int x, y;
    cin >> x >> y;
    cout << dist[--x] + dist[--y] << endl;
  }
  return 0;
}

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

using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;

#define fi first
#define se second

const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll MOD3 = 1812447359;
const ll INF = 1ll << 62;
const double PI = 2 * asin(1);

void yes() {printf("yes\n");}
void no() {printf("no\n");}
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}

int N, Q;
string S;
int cnt[int(1e5+5)];

int main(){
  cin >> N >> Q;
  cin >> S;
  for (int i = 2; i <= N; i++){
    cnt[i] = cnt[i-1];
    if (S[i-2] == 'A' && S[i-1] == 'C') cnt[i]++;
  }

  for (int i = 0; i < Q; i++){
    int L, R; cin >> L >> R;
    int ans = cnt[R] - cnt[L-1];
    if (L > 1 && S[L-1] == 'C' && S[L-2] == 'A') ans--;
    cout << ans << endl;
  }

  return 0;
}


Measured memory_bytes: 4144
def main():
	x,n=map(int,input().split())
	p=[]
	try:
		p=list(map(int,input().split()))
	except:
		print(str(x))
		return
	p=set(p)
	ans=0
	ansc=x
	for i in range(1,102):
		if not(i in p):
			a=min(abs(x-i),ansc)
			if(a!=ansc):
				ans=i
				ansc=a
	print(ans)
main()

Measured memory_bytes: 9132
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i > 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

int main()
{
  int N, W;
  cin >> N >> W;

  ll dp[N + 1][W + 1];
  REP(i, W + 1)
  dp[0][i] = 0;

  int w, v;
  REP(i, N)
  {
    cin >> w >> v;
    REP(j, W + 1)
    dp[i + 1][j] = (j - w >= 0) ? max(dp[i][j - w] + v, dp[i][j]) : dp[i][j];
  }

  cout << dp[N][W] << endl;
  return 0;
}


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

#define ll long long
#define db double
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);
#define ino freopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);

#define fr(i,n) for(i=0;i<n;i++)
#define frs(i,a,n) for(i=a;i<n;i++)
#define frv(i,n) for(i=n-1;i>=0;i--)

#define ne cout<<"\n";
#define cas(i) cout<<"Case #"<<i<<": "

#define vi vector <int>
#define vpi vector <pair <int,int> >
#define vpin(v,a,b) v.push_back(make_pair(a,b))
#define vsort(v) sort(v.begin(),v.end());
#define all(v) ((v).begin()),((v).end())
#define sz(v) ((int)((v).size()))

#define todegree(rad) rad*(180.0/pi)
#define isnttriangle(a,b,c) (a+b<c||a+c<b||b+c<a)
#define pi acos(-1)
#define siz 1000


int main()
{
    int A,B,num,cn;
    cin>>A>>B;
    cn=0;
    num=1;
    while(num<B)
    {
        num+=A-1;
        cn++;
    }
    cout<<cn<<"\n";

    return 0;
}



Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
void input()
{ 
  #ifndef ONLINE_JUDGE 
  freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
  #endif
}
typedef long long int ll;
#define rep(i,a,b) for( ll i=a;i<b;i++)
#define rrep(i,a,b)for(ll i=a;i>=b;i--)
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define f first
#define s second
#define mod 1000000007
bool compare(pair<int,int>a,pair<int,int>b)
{
  return a.f<b.f;
}
int main()
{
  //input();
  ios_base::sync_with_stdio(0);
    cin.tie(0);
 int n;
 cin>>n;
 int df[n]={},arr[n];
 rep(i,0,n)cin>>arr[i];

 rep(i,1,n)
 {
  int min1=INT_MAX;
    if(i-2>=0)
    {
      //cout<<arr[i];
      min1=min(abs(arr[i]-arr[i-2])+df[i-2],min1);
    }
    min1=min(abs(arr[i]-arr[i-1])+df[i-1],min1);
  df[i]=min1;
 // cout<<min1<<endl;
 }
cout<<df[n-1]<<endl;
}

///shubham gupta/


Measured memory_bytes: 1024
// C++ 14
#include <iostream>
#include <vector>
#include <array>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <math.h>

#define ll long long
#define Int int
#define INTMAX (1 << 21)
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(Int x = start; x > end; x--)

using namespace std;


// 1 (0)
// 1 2 (1)
// 1 2 4 (1)
// 2 4 
// 2 4
// 4
// 4 3
// 3
// 
void bfs(vector<Int> vs[], Int n) {
    Int t = 0;
    bool visited[n];
    Int ds[n];
    
    loop(i,0,n) {
        visited[i] = false;
        ds[i] = -1;
    }
    
    queue<Int> Q;
    Int depth = 0;
    
    Q.push(0);
    visited[0] = true;
    ds[0] = 0;
    
    while (!Q.empty()) {
        Int parent = Q.front(); Q.pop();
        for (auto child: vs[parent]) {
            if (visited[child]) continue;
            Q.push(child);
            visited[child] = true;
            ds[child] = ds[parent] + 1;
        }
    }
    
    loop(i,0,n) cout << i+1 << " " << ds[i] << endl;
}


int main(void){
    Int n, x, cc, c;
    cin >> n;
    vector<Int> vs[n];
    loop(i,0,n) {
        cin >> x >> cc;
        loop(j,0,cc) {
            cin >> c;
            vs[x-1].push_back(c-1);
        }
        
    }
    bfs(vs, n);
}



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

using ll = long long;
using ld = long double;
using vi = vector<int>;
using vll = vector<ll>;
using P = pair<int, int>;

const int INF = 1e9;
const ll INFLL = 1e18;
const int MOD = 1e9 + 7;
const int NIL = -1;
const ld PI = acosl(-1);

#define rep(i,n) for(int i=0; i<(n); ++i)
#define all(n) n.begin(),n.end()

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	//cout << fixed << setprecision(6);
	int n, k;
	cin >> n >> k;

	int ans = 1;
	rep(i, n){
		if(ans + k < ans * 2){
			ans += k;
		} else {
			ans *= 2;
		}
	}

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

Measured memory_bytes: 256
#include<bits/stdc++.h>
typedef long long ll;
typedef double db;
typedef long double ld;
using namespace std;
const int N=1e5;
int h,n,i,j,f[N],a[N],b[N];
int main()
{
	cin>>h>>n;
	for (i=1;i<=n;i++)
		scanf("%d%d",&a[i],&b[i]);
	memset(f,0x3f,sizeof(f));
	f[0]=0;
	 for (j=a[i];j<=h;j++)
	 for (i=1;i<=n;i++)
	 f[j]=min(f[j],f[j-a[i]]+b[i]);
	cout<<f[h]<<endl;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
#define rint register int 
#define ll long long
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
struct node{int to,next,v;} e[1010100];
int N,K,h[1010000],tot,A[1010000];
int Min[1010000],rt,dep[1000100],depp[1010000],vis[1001000];
inline void add(int from,int to) {
	e[++tot].to=to;e[tot].next=h[from];h[from]=tot;
}
inline void Pre(int now,int ffa){
	Min[now]=1e9;dep[now]=dep[ffa]+1;
	Min[rt]=0;
	if((A[now]!=-1)&&now!=rt) {
		int dis=dep[now]-dep[rt];
		int d=A[now]-A[rt];
		int o=dis+d;
		if((o&1)||o<0) {
			cout<<"No\n";exit(0);
		}
		Min[now]=o/2;
		//cout<<now<<" "<<Min[now]<<endl;
	}
	for(rint i=h[now];i;i=e[i].next){
		int to=e[i].to;if(to==ffa) continue;
		Pre(to,now);
		if((A[now]!=-1)&&Min[to]<Min[now]) {
			//debug(now);
			cout<<"No\n";exit(0);
		}
		Min[now]=min(Min[to],Min[now]);
	}
}
inline void Gao(int now,int ffa){
	//debug(now);debug(Min[now]);
	if(vis[now]&&depp[now]!=Min[now]) {
		//debug(now);
		cout<<"No\n";exit(0);
	}
	for(rint i=h[now];i;i=e[i].next){
		int to=e[i].to;if(to==ffa) continue;
		if(Min[to]<1e8&&Min[to]>depp[now]) {
			depp[to]=depp[now]+1;
			A[to]=A[now]+1;
		}
		else A[to]=A[now]-1,depp[to]=depp[now];
		Gao(to,now);
	}
}
int main(){
	cin>>N;
	for(rint i=1;i<N;++i) {
		int u,v;cin>>u>>v;
		add(u,v);add(v,u);
	}
	cin>>K;
	memset(A,-1,sizeof(A));
	for(rint i=1;i<=K;++i) {
		int x;cin>>x;
		cin>>A[x];vis[x]=1;
	}
	rt=1;
	for(rint i=1;i<=N;++i) {
		if(A[i]!=-1) rt=i; 
	}
	//debug(rt);
	if(A[rt]==-1) A[rt]=0;
	Pre(rt,0);
	//debug(1);
	Gao(rt,0);
	cout<<"Yes\n";
	for(rint i=1;i<=N;++i) cout<<A[i]<<"\n";
	return 0;
}

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

int main(){
    int h,w;
    cin >> h >> w;
    vector<vector<char>> c(h,vector<char>(w));

    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            cin >> c.at(i).at(j);
        }
    }
    for(int i=0; i<h; i++){
        for(int k=0; k<2; k++){
            for(int j=0; j<w; j++){
                cout << c.at(i).at(j);
            }
            cout << endl;
        }
    }
}

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

using namespace std;

#define rep(i,n) for(int i=0;i<(n);i++)
#define repa(i,a,n) for(int i=(a);i<(n);i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define rrepa(i,a,n) for(int i=n-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()
#define MOD 1000000007
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
#define vc vector

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;

int main(){

    int n;
    cin>>n;

    vi a(n);
    rep(i,n)cin>>a[i];

    ll tmp=0;

    rep(i,n){
        if(i%2==0)tmp+=a[i];
        else tmp-=a[i];
    }

    rep(i,n){
        cout<<tmp<<"\n";
        tmp=2*a[i]-tmp;
    }

    return 0;

}

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

long long n, a, b, m;

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

	m = (n / (a + b)) * a;

	if (n % (a + b) > a)
		m += a;
	else
		m += n % (a + b);

	cout << m << endl;
}


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

int main() {
    int a, b;

    cin >> a >> b;

    int ans = 0;

    if( (b % a) == 0) {
        ans = a + b;
    } else {
        ans = b - a;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
	int S,h,m,s;
	scanf("%d",&S);
	h = S / 3600;
	m = S % 3600 / 60;
	s = S % 3600 % 60;
	printf("%d:%d:%d\n",h,m,s);
	return 0;
}



Measured memory_bytes: 2068