akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include <algorithm>
#include<string>
#include <bitset>
#include <vector>
#include <functional>
#include <climits>
#include <iomanip>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <iomanip>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <numeric>
using namespace std;
using ll = long long;

typedef pair <int, int> pii;

int main()
{

	ll a = 0, b = 0, c = 0, d = 0, e = 0, f = 0, g = 0, h = 0, ans = 0;
	string s, t;
	ll x, y;
	cin >> a;
	cin >> b;
	cin >> c;
	cin >> x;
	cin >> y;
	while (x > 0 || y > 0)
	{
		if (x > 0 && y > 0 && a + b < 2 * c)
		{
			x--;
			y--;
			ans += a + b;
		}
		else if (x > 0 && y > 0 && a + b >= 2 * c)
		{
			x--;
			y--;
			ans += 2 * c;
		}
		else if (x > 0 && a < 2 * c)
		{
			x--;
			ans += a;
		}
		else if (x > 0 && a > 2 * c)
		{
			x--;
			ans += 2 * c;
		}
		else if (y > 0 && b < 2 * c)
		{
			y--;
			ans += b;
		}
		else if (y > 0 && b > 2 * c)
		{
			y--;
			ans += 2 * c;
		}

	}

	cout << ans << endl;
	//cout <<  << endl;

	////std::cout << std::fixed;
	//cout << std::setprecision(20) << << endl;
	//cout << d+1 << endl;
	//cout << "" << endl;

	return 0;
}
//char型の文字数字は、-'0'で数値に変換できる
//accumulate(x, x + a, 0);//int型までの配列の合計
//memcpy(x, visited, sizeof(ll)*n);
//void kansuu(ll num, ll visited[10]) {}
//kansuu(1, zz);
//cout << setprecision(15) << v << endl;
//cout << char(z - 'a');
//log10(i) + 1 //10進数の桁数を取得

//int temp;
//for (int i = 0; i < n - 1; i++) {
//	for (int j = n - 1; j > i; j--) {
//		if (w[j - 1] < w[j]) {  /* 前の要素の方が大きかったら */
//			temp = w[j];        /* 交換する */
//			w[j] = w[j - 1];
//			w[j - 1] = temp;
//		}
//	}
//}

//最小公倍数
//ll x = a * b;
//ll tmp;
///* 自然数 a > b を確認・入替 */
//if (a<b) {
//	tmp = a;
//	a = b;
//	b = tmp;
//}
///* ユークリッドの互除法 */
//ll r = a % b;
//while (r != 0) {
//	a = b;
//	b = r;
//	r = a % b;
//}
//a = x / b;//答え

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

int main()
{
	int K,S;
	cin >> K >> S;
	int X = 0;int Y = 0;int Z = 0;
	int res=0;
	for (int i = 0;i <= K;i++) {
		X = i;
		for (int j = 0;j <= K;j++) {
			Y = j;
			Z = S - X - Y;
			if (0 <= Z && Z <= K) {
				res++;
			}
		}
	}

	cout << res << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
constexpr int64_t mod=1e9+7;

int main()
{
  int n;
  cin>>n;
  string s;
  cin>>s;
  int ans=0;
  for (int i = 0; i < n-1; ++i)
  {
    if(s[i]!=s[i+1]) ans++;
  }
  cout<<ans+1;
}

Measured memory_bytes: 512
#include <iostream>
#include <cstdio>
using namespace std;
int a[100][100];
int main()
{
    int h,w,flag = 0;
    scanf("%d%d",&h,&w);

    for(int i = 1; i <= h; i++ )
    {
        getchar();
        for(int j = 1; j <= w; j++)
        {
            char tem;
            scanf("%c",&tem);
            a[i][j] = tem =='#'?1:0;
        }
    }
    for(int i = 1; i <= h; i++ )
    {
        for(int j = 1; j <= w; j++)
        {
            if(a[i][j] == 1)
            {
                if(a[i-1][j] == 1 || a[i+1][j] == 1 ||a[i][j-1] == 1 ||a[i][j+1] == 1)
                    continue;
                else
                {
                    flag = 1;
                    break;
                }
            }
        }
        if(flag)
            break;
    }
    printf("%s\n",flag?"No":"Yes");
    return 0;
}


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

char m[3][3];
int main()
{
	for (int i = 0; i < 3; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			cin >> m[i][j];
		}
	}
	cout << m[0][0] << m[1][1] << m[2][2];
	return 0;
}

Measured memory_bytes: 256
while True:
    a, b= (int(i) for i in input().split())
    if a == 0 and b ==0:
        break
    print('#' * b)
    for i in range(1,a-1):
        print('#'+ '.'*(b -2)+'#')
            
    print('#' * b)
    print()
    
   


Measured memory_bytes: 5616
m1 = []
m2 = []
n, m = [int(s) for s in input().split()]
for i in range(n):
    m1.append([int(s) for s in input().split()])

for i in range(m):
    m2.append(int(input()))

for ma in m1:
    print(sum(map(lambda m, n: m * n, ma, m2)))

Measured memory_bytes: 8096
from heapq import heappush, heappop, heapify

n, m = [int(v) for v in input().split()]
values = [-int(v) for v in input().split()]
heapify(values)

for _ in range(m):
    v = -((-heappop(values)) >> 1)
    heappush(values, v)

print(-sum(values))

Measured memory_bytes: 72088
def ints():
  return [int(x) for x in input().split()]
def ii():
  return int(input())

import math

N, K = ints()
A = list(sorted(ints()))
F = list(reversed(sorted(ints())))
AF = [A[i]*F[i] for i in range(N)]

afmax = max(AF)

def can(max_af):
  k = K
  for i in range(N):
    af = AF[i]
    if af>max_af:
      max_ai = max_af // F[i]
      k -= A[i]-max_ai
      if k<0:
        return False
  return k>=0

l = -1
r = afmax
while r-l>1:
  m = (l+r)//2
  if can(m):
    r = m
  else:
    l = m
print(r)



Measured memory_bytes: 122544
using System;
using System.Text;

namespace D
{
    class Program
    {
        static void Main(string[] args)
        {
            long K = Convert.ToInt64(Console.ReadLine());
            var sb = new StringBuilder();
            long snuke = 0;
            for (var i = 0; i < K; i++)
            {
                snuke = f(snuke + 1);
                sb.AppendFormat($"{snuke}\n");
            }
            Console.Write(sb);
        }

        static long f(long n)
        {
            long ans = n;
            double min = ((double)n / S(n));
            long div = 1;
            for (int i = 0; i < 16; i++)
            {
                // x,xxx,xxx,xxx,xxx,xxx (div == 2のとき)
                long upper = (n / (div * 10)) * (div * 10); // x,xxx,xxx,xxx,xxx,x00
                long num = (n / div) % 10;                  // x,xxx,xxx,xxx,xxx,N00
                for (long j = num + 1; j <= 9; j++)
                {
                    long y = upper + (j * div) + div - 1;
                    double tmp = ((double)y / S(y));
                    if (tmp < min)
                    {
                        min = tmp;
                        ans = y;
                    }
                }
                div *= 10;
            }
            return ans;
        }

        static long S(long x)
        {
            long ans = 0;
            while (x > 0)
            {
                ans += x % 10;
                x /= 10;
            }
            return ans;
        }
    }
}


Measured memory_bytes: 11420
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <map>
#include <set>
#define ull unsigned long long
#define ll long long
using namespace std;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    if(abs(a-c)<=d){cout << "Yes" << endl;}
    else if(abs(a-b)<=d && abs(b-c)<=d){
        cout << "Yes" << endl;
    }

    else cout << "No" << endl;

    return 0;
}

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

int main(){
  int n,i,j;
  scanf("%d",&n);
  int a[n],tmp,count;
  for(i=0; i<n; i++){
    scanf("%d",&a[i]);
  }

  count=0;

  for(i=0; i<n-1; i++){
    for(j=n-1; j>i; j--){
      if(a[j-1] > a[j]){
        tmp = a[j];
        a[j] = a[j-1];
        a[j-1] = tmp;
        count += 1;
      }
    }
  }
  for(i=0; i<n; i++){
    printf("%d",a[i]);
    if(i!=n-1){
      printf(" ");
    }else if(i==n-1){
      printf("\n");
    }
  }
  printf("%d\n",count);
}

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

const int MAX_N = 10000;
const int MAX_Q = 500;

int main() {
	int n, q, s[MAX_N], t, ans = 0;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> s[i];
	}
	cin >> q;
	for (int i = 0; i < q; i++) {
		cin >> t;
		for (int i = 0; i < n; i++) {
			if (t == s[i]) {
				ans++;
				break;
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3092
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10**9)
mod = 10**9+7

N = i()
print(lcm(2,N))

Measured memory_bytes: 77216
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|i| i.parse().ok().unwrap())
        .collect()
}

fn main() {
    let input = read_vec::<i64>();
    let a = input[0];
    let b = input[1];
    let c = input[2];

    if 4 * a * b < (c - a - b) * (c - a - b) && a + b < c{
        println!("Yes");
    } else {
        println!("No");
    }
}

Measured memory_bytes: 4352
#include<iostream>

using namespace std;

#define MAX 16

int main(){

	int a,b,n;
	int na,nb;
	bool road[MAX+2][MAX+2];
	int dp[MAX+2][MAX+2];
	int dx[]={0,1};
	int dy[]={1,0};
	int m;

	while(1){

		cin>>a>>b;
		if(a==0&&b==0) break;

		for(int i=0;i<MAX+2;i++){
			for(int j=0;j<MAX+2;j++){
				road[i][j]=false;
				dp[i][j]=0;
			}
		}

		for(int i=1;i<=b;i++){
			for(int j=1;j<=a;j++){
				road[i][j]=true;
			}
		}

		cin>>n;

		for(int i=0;i<n;i++){
			cin>>na>>nb;
			road[nb][na]=false;
		}

		dp[1][1]=1;

		for(int i=1;i<=b;i++){
			for(int j=1;j<=a;j++){
				if(dp[i][j]>=1){
					for(int k=0;k<2;k++){
						if(road[i+dy[k]][j+dx[k]]==true){
							dp[i+dy[k]][j+dx[k]]+=dp[i][j];
						}
					}
				}
			}
		}

		cout<<dp[b][a]<<endl;

	}
	
	return 0;
}

Measured memory_bytes: 1160
q=int(input())

for i in range(q):
    xp0,yp0,xp1,yp1,xp2,yp2,xp3,yp3=map(int,input().split())
    if xp0==xp1:
        if xp2==xp3:
            print(2)
        elif yp2==yp3:
            print(1)
        else:
            print(0)
    elif xp2==xp3:
        if xp1==xp0:
            print(2)
        elif yp0==yp1:
            print(1)
        else:
            print(0)
    else:
        a1=(yp1-yp0)/(xp1-xp0)
        a2=(yp3-yp2)/(xp3-xp2)
        
        #print(a1,a2)
        if a2>=a1-0.0000001 and a2<=a1+0.0000001:
            print(2)
        elif a2*a1>=-1-0.0000001 and a2*a1<=-1+0.0000001:
            print(1)
        else:
            print(0)



Measured memory_bytes: 5632
a, b, c = map(int, input().split())

if a<b and a<c:
    if b<c :
        print(a, b, c)
    else :
        print(a, c, b)
elif b<a and b<c :
    if a<c :
        print(b, a, c)
    else :
        print(b, c, a)
else :
    if a<b :
        print(c, a, b)
    else :
        print(c, b, a)
  



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

#define rep(i,n) for(long long int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(long long int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(long long int i=(a);i>(b);i--)
#define all(v) (v).begin(), (v).end()
#define pb(q) push_back(q)
#define P pair<int,int>
#define Abs(a,b) max(a,b)-min(a,b)
#define YES(condition) if(condition){cout << "YES" << endl;}else{cout << "NO" << endl;}
#define Yes(condition) if(condition){cout << "Yes" << endl;}else{cout << "No" << endl;}
#define Cout(x) cout<<(x)<<endl

typedef long long ll;

using namespace std;

const int INF = 1e9,MOD = 1e9 + 7;
const ll LINF = 1e18;

//while(x!=0){
            //sum+=x%10;
           // x/=10;
        //}
        //各桁の和

//pair<int,int> p[100000];
//P r[100000];
//cin >> tmp;
//p[i]=make_pair(tmp,i);
//cout << p[i].second+1 << endl;//ペアの右側つまりiを出力

//s.find(w[i])==string::npos
//findの使い方

//for(int i=0;i<n;i++){
   // b[i]=x%2;
    //x/=2;
  //}二進数

long long int n=1,cnt=0,ans=0,a[100000],b,c,cmp=0,data,m,h,x,y,xcmp=0,ycmp=0,sum=0,cmpp;

string s,w;

vector<int> z;

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

        cin >> b >> c;
        x=b;
        y=c;
        if(b<=0 && c>=0){
            Cout("Zero");
            return 0;
        }
      if(b>0){
          Cout("Positive");
      }
      else{
          x*=-1;
          y*=-1;
         if((x-y)%2==0){
             Cout("Negative");
         }
         else{
             Cout("Positive");
         }
      }
return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#define int long long
#define range(i, a, b) for(auto i = a; i < b; i++)
#define rep(i, a) range(i, 0, a)
#define all(a) (a).begin(),(a).end()
using namespace std;
const int INF = sizeof(int) == sizeof(long long) ? 1000000000000000000LL : 1000000000;
const int MOD = 1000000007;
const long double EPS = 1e-8;
using vi = vector <int>;
using vvi = vector <vi>;

signed main() {
	int n, a, b;
	cin >> n >> a >> b;
	bool alice = true;
	map <pair <int, int>, int> mp;
	while(1) {
		if( alice ) {
			if ( a + 1 != b ) {
				a++;
			} else if ( a - 1 != 0 ) {
				a--;
			} else {
				cout << "Borys" << endl;
				break;
			}
			alice = false;
		} else {
			if ( b - 1 != a ) {
				b--;
			} else if ( b + 1 != n + 1 ) {
				b++;
			} else {
				cout << "Alice" << endl;
				break;
			}
			alice = true;
		}
		if( mp[make_pair( a, b )] == 1 ) {
			cout << "Draw" << endl;
			break;
		}
		mp[make_pair( a, b )] = 1;
	}
}

Measured memory_bytes: 256
s = input()
l = len(s)
flag = True

for i in range(l):
    if s[i] != s[l-i-1]:
        flag = False

for i in range((l-1)//2):
    if s[i] != s[(l-1)//2-1-i]:
        flag = False

for i in range((l-1)//2):
    if s[l-i-1] != s[(l-1)//2+1+i]:
        flag = False

if flag:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <functional>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#define Inf 1000000000
#define nmax_def 110000
#define mod 1000000007
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;

vl pow_;
void pow_ini(ll n) {
	pow_.push_back(n);
	rep(j, 62) {
		ll nxt = pow_[j] * pow_[j];
		nxt %= mod;
		pow_.push_back(nxt);
	}
	return;
}

ll pow1(ll k) {
	ll ans = 1;
	rep(ntmp, 62) {
		if ((k >> ntmp) % 2 == 1) {
			ans *= pow_[ntmp];
			ans %= mod;
		}
	}
	return ans;
}

vl fact;
vl fact_inv;

void fact_ini(ll n) {
	fact.push_back(1);
	fact.push_back(1);
	for (ll i = 2; i <= n; i++) {
		ll fact_tmp = fact[i - 1] * i;
		fact_tmp %= mod;
		fact.push_back(fact_tmp);
	}
	fact_inv.resize(n + 1);
	pow_ini(fact[n]);
	fact_inv[n] = pow1(mod - 2);
	for (ll i = n - 1; i >= 0; i--) {
		fact_inv[i] = fact_inv[i + 1] * (i + 1);
		fact_inv[i] %= mod;
	}
}

ll nCm(ll n, ll m) {
	ll ans = fact[n] * fact_inv[m];
	ans %= mod;
	ans *= fact_inv[n - m];
	ans %= mod;
	return ans;
}

int main() {
	fact_ini(pow(10, 6));
	ll N, K;
	cin >> N >> K;
	vl A(N);
	rep(i, N) {
		cin >> A[i];
	}
	sort(A.begin(), A.end(), less<ll>());
	ll ans = 0;
	rep(i, N) {
		// max
		if (i + 1 >= K) {
			ll anstmp = A[i];
			anstmp *= nCm(i + 1 - 1, K - 1);
			anstmp %= mod;
			ans += anstmp;
			ans %= mod;
		}
		// min
		if (N - i >= K) {
			ll anstmp = A[i];
			anstmp *= nCm(N - i - 1, K - 1);
			anstmp %= mod;
			ans -= anstmp;
			ans += mod;
			ans %= mod;
		}
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 16872
#include <iostream>
#include <algorithm>
#include<string>
#include<cmath>
#include<stack>
#include <vector>
#include<queue>
#include <random>
using namespace std;



int main() {
	int n, y, five, one,sol;
	bool flg = false;
	cin >> n >> y;
	y = y / 1000;
	for (int i = 0; i <= n; i++) {
		sol = y - i * 10;
		if (((n - i) * 5 - sol) % 4 == 0&& (n - i) * 5>=sol&& (n - i) <=sol) {
			one = ((n - i) * 5 - sol) / 4;
			five = n - one - i;
			cout << i <<' '<< five <<' '<< one << endl;
			flg = true;
			break;
		}
	}
	if (!flg) {
		cout << "-1 -1 -1";
	}
	
	return 0;
}





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

signed main(void)
{
	int n;
	cin >> n;
	if (n <= 999)
		cout << "ABC" << endl;
	else
		cout << "ABD" << endl;
	return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main{

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner s = new Scanner(System.in);
		int N = s.nextInt();
		int K = s.nextInt();
		int ans = 1;
		int twotimes = 0;
		int plus = 0;		
		for (int i = 0; i < N; i++) {
			twotimes = ans * 2;
			plus = ans + K;
			ans = twotimes < plus ? twotimes : plus;
			
		}
		System.out.println(ans);
	}

}

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

template <
    typename TYPE,
    std::size_t SIZE>
std::size_t a_len(const TYPE (&array)[SIZE])
{
    return SIZE;
}

using namespace std;
using ll = long long int;
using vi = vector<ll>;

#define REPS(a, i, n) for (ll(i) = a; (i) < (n); ++(i))
#define REP(i, n) REPS(0, i, n)
#define ALL(x) (x).begin(), (x).end()

const int INF = 100001;

int a;

int main()
{
    cin >> a;
    
    if(a < 1200){
        cout << "ABC" << endl;
    }else if(a < 2800){
        cout << "ARC" << endl;
    }else{
        cout << "AGC" << endl;
    }
}

Measured memory_bytes: 256
fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    val x = readLine()!!.split(" ").map { it.toInt() }
    val sortedX = x.sorted()
    val r = sortedX[n/2]
    val l = sortedX[n/2-1]

    for (n in x)
        if (n <= l) println(r)
        else println(l)
}

Measured memory_bytes: 98272
n=int(input())
line=list(map(int,input().split( )))

count=0
for i in range(0,n-2):
    if line[i]<line[i+1]<=line[i+2]:
        count+=1
    elif line[i+2]<line[i+1]<=line[i]:
        count+=1

print(count)

Measured memory_bytes: 38256
#include<iostream>
#include<string>
#include<algorithm>
#include<unordered_set>
#include<vector>
#include<math.h>
#include<iomanip>

using namespace std;

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

	int a, b;
	cin >> a >> b;

	if (a <= b) {
		for (int i = 0; i < b; i++) {
			cout << a;
		}
	}
	else {
		for (int i = 0; i < a; i++) {
			cout << b;
		}
	}

}

Measured memory_bytes: 256
void main()
{
    string s = rdStr;

    string now;
    string bef;
    long cnt;
    foreach (x; s)
    {
        now ~= x;
        if (now != bef)
        {
            bef = now;
            now = "";
            ++cnt;
        }
    }

    cnt.writeln;
}

T rdElem(T = long)()
{
    //import std.stdio : readln;
    //import std.string : chomp;
    //import std.conv : to;

    return readln.chomp.to!T;
}

alias rdStr = rdElem!string;

dchar[] rdDchar()
{
    //import std.conv : to;

    return rdStr.to!(dchar[]);
}

T[] rdRow(T = long)()
{
    //import std.stdio : readln;
    //import std.array : split;
    //import std.conv : to;

    return readln.split.to!(T[]);
}

T[] rdCol(T = long)(long col)
{
    //import std.range : iota;
    //import std.algorithm : map;
    //import std.array : array;

    return iota(col).map!(x => rdElem!T).array;
}

T[][] rdMat(T = long)(long col)
{
    //import std.range : iota;
    //import std.algorithm : map;
    //import std.array : array;

    return iota(col).map!(x => rdRow!T).array;
}

void wrMat(T = long)(T[][] mat)
{
    //import std.stdio : write, writeln;

    foreach (row; mat)
    {
        foreach (j, compo; row)
        {
            compo.write;
            if (j == row.length - 1) writeln;
            else " ".write;
        }
    }
}

import std.stdio;
import std.string;
import std.array;
import std.conv;
import std.algorithm;
import std.range;
import std.math;
import std.numeric;
import std.container;
import std.typecons;
import std.ascii;
import std.uni;

Measured memory_bytes: 1592
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <stdio.h>
using namespace std;
static inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

int pow(long x, int n, int m){
    long ret = 1;
    while (n > 0) {
        if (n & 1) ret *= x, ret %= m;
        x *= x, x %= m;
        n >>= 1; 
    }
    return ret % m;
}

int euler_phi(int n) {
   int ret = n;
   for(int i = 2; i * i <= n; ++i){
       if(n % i == 0) {
           ret -= ret / i;
           while(n % i == 0) n /= i;
       }
   }
   if(n > 1) ret -= ret / n;
   return ret;
}

int main()
{
    int K = 0, c = getchar();
    while(c > 47 && c < 58){
        K = K * 10 + c - 48;
        c = getchar();
    }

    K /= gcd(K, 7);
    if(K == 1){
        putchar('1');
        return 0;
    }

    K *= 9;

    if(gcd(K, 10) != 1) {
        putchar('-');
        putchar('1');
        return 0;
    }

    int res = euler_phi(K);

    int ans = 1000000;
    int now = 10;
    for(int i = 1; i * i <= res; ++i){
        if(res % i == 0) {
            if(now == 1){
                printf("%d\n", i);
                return 0;
            }
            int tmp = res / i;
            if(pow(10, tmp, K) == 1) if(tmp < ans) ans = tmp;
        }
        now *= 10, now %= K;
    }

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

    return 0;
}


Measured memory_bytes: 1584
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define yesno(flg) if(flg){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define MAX_N 1002
#define i197 1000000007

using namespace std;

typedef long long ll;
typedef pair<ll,ll> P1;
typedef pair<int,int> Pi;
typedef pair<double,Pi> Pdi;
typedef pair<ll,int>Pli;
typedef pair<P1,ll> P2;
const ll INF=1<<29;
struct edge{int to,cost;};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
struct Road{double cost;int a,b;};
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}
int dp[3001][3001]={};
int main() {

	string s,t;
	cin>>s;
	cin>>t;

	for(int i=0; i<s.size(); i++){
		for(int j=0; j<t.size(); j++){
			if(t[j]==s[i])dp[j+1][i+1]=max(dp[j+1][i+1],dp[j][i]+1);
			dp[j+1][i+1]=max(dp[j+1][i+1],dp[j+1][i]);
			dp[j+1][i+1]=max(dp[j+1][i+1],dp[j][i+1]);
		}
	}
	string res="";
	int j=t.size(),i=s.size();
	while(i>0&&j>0){
		if(dp[j][i]==dp[j-1][i])j--;
		else if(dp[j][i]==dp[j][i-1])i--;
		else{
			res=s[i-1]+res;
			i--;
			j--;
		}
	}
	cout<<res<<endl;
	return 0;
}


Measured memory_bytes: 35456
package main

import (
	"fmt"
	"strings"
)

func main() {
	var data string = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
	var N int
	var S string
	var ans string = ""
	fmt.Scan(&N, &S)

	var i = 0
	for i < len(S) {
		var t = S[i : i+1]
		var at = strings.Index(data, t)
		var targetJ int = (at + N) % 26
		var target = data[targetJ : targetJ+1]
		ans = ans + target
		i++
	}
	fmt.Println(ans)
}


Measured memory_bytes: 7680
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

macro_rules! debug {
    ($($a:expr),*) => {
        println!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

fn main() {
    input! {
        ss: [chars; 3],
    }
    println!("{}",
        ss.into_iter().map(|s| s[0].to_uppercase().next().unwrap()).collect::<String>()
    );
}


Measured memory_bytes: 4352
#include <cstdio>
#include <map>
#include <string>
#include <iostream>
#include <vector>
#include <cstdlib>
#include <algorithm>
using namespace std;

typedef struct
{
  string s, t;
  int c;
} Unit;

int main()
{
  const int INF = 1 << 29;

  int N;
  while (~scanf("%d", &N)) {
    if (N == 0)
      break;

    map<string, int> toIndex;
    vector<Unit> unit(N);
    for (int i = 0; i < N; ++i) {
      string s, t, c;
      cin >> t >> t >> c >> c >> s;
      int cc = atoi(c.substr(c.find_first_of("^")+1).c_str());
      unit[i].s = s;
      unit[i].t = t;
      unit[i].c = cc;
      if (toIndex.find(s) == toIndex.end())
	toIndex[s] = toIndex.size()-1;
      if (toIndex.find(t) == toIndex.end())
	toIndex[t] = toIndex.size()-1;
    }

    vector<vector<int> > cost(toIndex.size(), vector<int>(toIndex.size(), INF));
    for (int i = 0; i < cost.size(); ++i)
      cost[i][i] = 0;

    for (int i = 0; i < N; ++i) {
      int s = toIndex.find(unit[i].s)->second;
      int t = toIndex.find(unit[i].t)->second;
      cost[s][t] = unit[i].c;
      cost[t][s] = -unit[i].c;
    }

    for (unsigned int k = 0; k < cost.size(); ++k) {
      for (unsigned int i = 0; i < cost.size(); ++i) {
	for (unsigned int j = 0; j < cost.size(); ++j)
	  cost[i][j] = min(cost[i][j], cost[i][k]+cost[k][j]);
      }
    }

    bool yes = true;
    for (unsigned int i = 0; i < cost.size() && true; ++i) {
      for (unsigned int j = i+1; j < cost.size() && true; ++j) {
	if (cost[i][j] >= 100000000 || cost[j][i] >= 100000000)
	  continue;
	if (cost[i][j] != -cost[j][i])
	  yes = false;
      }
    }

    if (yes)
      cout << "Yes" << endl;
    else
      cout << "No" << endl;
  }
  return 0;
}

Measured memory_bytes: 1124
class Dice
  attr_reader :top, :bottom, :front, :back, :left, :right 
  def initialize(dice_numbers)
    @top = dice_numbers[0]
    @back = dice_numbers[1]
    @right = dice_numbers[2]
    @left = dice_numbers[3]
    @front = dice_numbers[4]
    @bottom = dice_numbers[5]
  end

  def execute_order(orders) 
      orders.each do |order|
        if order == "N"
          move_north
        elsif order == "S" 
          3.times do
            move_north
          end
        elsif order == "W"
          move_west
        elsif order == "E" 
          3.times do
            move_west
          end
        else
          puts "error!" 
        end
      end
  end
  
  private 
  def move_north
    tmp = @top
    @top = @back
    @back = @bottom
    @bottom = @front
    @front = tmp
  end

  def move_west
    tmp = @top
    @top = @right
    @right = @bottom
    @bottom = @left
    @left = tmp
  end
end

dice_numbers = gets.chomp.split.map(&:to_i)
orders = gets.chomp.split("")
dice = Dice.new(dice_numbers)
dice.execute_order(orders)
puts dice.top

Measured memory_bytes: 8612
using System;
using System.Linq;
using System.Collections.Generic;

namespace ABC167
{
    class C
    {
        static void Main(string[] args)
        {
            var NK = Console.ReadLine().Split().Select(long.Parse).ToArray();
            var N = NK[0]; var K = NK[1];
            var A = Console.ReadLine().Split().Select(long.Parse).ToArray();

            var B = new long[N + 1]; // N回目の移動でいるます
            var Visited = new bool[N];
            B[0] = 1;
            Visited[0] = true;
            for (int i = 1; i < N + 1; i++)
            {
                B[i] = A[B[i - 1] - 1];
            }

            if (K <= N) { Console.WriteLine(B[K]); return; }

            long index = 0;
            for (int i = 1; i < N + 1; i++)
            {
                if (!Visited[B[i] - 1]) Visited[B[i] - 1] = true;
                else { index = i; break; }
            }
            var num = B[index];
            //Console.WriteLine(num);
            //Console.WriteLine(index);

            long start = 0;
            for (int i = 0; i < N + 1; i++)
            {
                if (B[i] == num) { start = i; break; }
            }
            //Console.WriteLine(start);

            // start 番目に num がでる
            // idnex 番目に num がまたでる
            K = (K - start) % (index - start);
            var ans = B[start + K];
            Console.WriteLine(ans);
        }
    }
}



Measured memory_bytes: 45552
def main():
    C = [2, 5, 5, 4, 5, 6, 3, 7, 6]
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    dp = [0] + [-1] * N
    K = {a: C[a - 1] for a in A}

    for i in range(min(K.values()), N + 1):
        try:
            dp[i] = max(dp[i - v] * 10 + k for k, v in K.items() if i - v >= 0 and dp[i - v] >= 0)
        except ValueError:
            dp[i] = -1
    print(dp[N])
main()


Measured memory_bytes: 14444
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <map>
#include <unordered_map>

using namespace std;
using ll = long long;

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

ll lcm(ll a, ll b) {
	return a / gcd(a, b) * b;
}

int main() {
	ll A, B, C, D;
	cin >> A >> B >> C >> D;
	ll a = (A - 1) - (((A - 1) / C) + (A - 1) / D - (A - 1) / lcm(C, D));
	ll b = B - (B / C + B / D - B / lcm(C, D));
	ll ans = b - a;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3608
import math
E=0
A,B,C=map(int,input().split())
print((1/2)*A*B*(math.sin(math.radians(C))))
print(((A**2)+(B**2)-2*A*B*(math.cos(math.radians(C))))**(1/2)+A+B)
print(((1/2)*A*B*(math.sin(math.radians(C))))*2/A)



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

bool compare(const vector<int>& left, const vector<int>& right) {
  return left.at(0) + left.at(1) < right.at(0) + right.at(1);
}

int main()
{
  int n, result;
  cin >> n;
  vector<vector<int>> data(n, vector<int>(2));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 2; j++) {
      cin >> data.at(i).at(j);
    }
  }
  sort(data.begin(), data.end(), compare);
  result = n;
  int left_x = 0, left_l = 0, x, l;
  double left, right;
  for (int i = 0; i < n; i++) {
    x = data.at(i).at(0);
    l = data.at(i).at(1);
    if (i == 0) {
      left_x = x;
      left_l = l;
    } else {
      left = left_x + left_l - 0.1;
      right = x - l + 0.1;
      if (left < right) {
        // ok
        left_x = x;
        left_l = l;
      } else {
        // ng
        result--;
      }
    }
  }
  cout << result << endl;
}


Measured memory_bytes: 5760
s = input()

i = 1
ans = 0
while i < (len(s) - 1):
    if (s[i - 1] != s[i + 1]):
        s = s[:i] + s[i + 1:]
        ans = (ans + 1) % 2
        i = 0
    i += 1

if (ans + 1) % 2 == 0:
    print('First')
else:
    print('Second')


Measured memory_bytes: 3316
/*
これを入れて実行
g++ code.cpp
./a.out
 */

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <cmath>
#include <tuple>
#include <iomanip>

using namespace std;
typedef long long ll;
typedef long double ld;

int dy4[4] = {-1, 0, +1, 0};
int dx4[4] = {0, +1, 0, -1};
int dy8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dx8[8] = {0, 1, 1, 1, 0, -1, -1, -1};

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

bool greaterSecond(const pair<int, int>& f, const pair<int, int>& s){
    return f.second > s.second;
}

int gcd(int a, int b){
	if (b == 0)return a;
	return gcd(b, a % b);
}

//-----------------------ここから-----------


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

	vector<int> cw(n);
	vector<int> ce(n);

	for(int i = 0; i < n; i++){
		cw[i] = 0;
		ce[i] = 0;
	}

	if(s[0] == 'W'){
		cw[0]++;
	} 
	for(int i = 1; i < n; i++){
		if(s[i] == 'W'){
			cw[i] += cw[i - 1] + 1;
		} else {
			cw[i] += cw[i - 1];
		}
	}
	
	if(s[n - 1] == 'E'){
		ce[n - 1]++;
	}
	for(int i = n - 2; i >= 0; i--){
		if(s[i] == 'E'){
			ce[i] = ce[i + 1] + 1;
		} else {
			ce[i] = ce[i + 1];
		}
	}

	int ans = 1e9;
	for(int i = 0; i < n; i++){
		int count = 0;
		count += cw[i - 1];
		count += ce[i + 1];

		ans = min(ans, count);
	}

	cout << ans << endl;

}



Measured memory_bytes: 3076
package main

import (
	"fmt"
)

func chocoday(x int, d int)int{
	chocoday := 0
	for a:=0; a*x+1<=d; a++{
		chocoday++
	}
	return chocoday
}

func main() {
	var n, d, x int
	fmt.Scan(&n)
	fmt.Scan(&d, &x)
	chococap := make([]int, n)
	for i:=0; i<n; i++{
		fmt.Scan(&chococap[i])
	}
	choconum := 0
	for l:=0; l<n; l++{
		choconum += chocoday(chococap[l], d)
	}
	fmt.Println(choconum + x)
}

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

using namespace std;


int main(){
    
    int N;
    cin >> N;
    vector<int> A1(N);
    vector<int> A2(N);
    
    for (int i = 0; i < N; i++) {
        cin >> A1[i];
    }
    for (int i = 0; i < N; i++) {
        cin >> A2[i];
    }
    
    for (int i = 1; i <= N-1; i++) {
        A1[i] = A1[i] + A1[i-1];
    }
    for (int i = N-2; i >= 0; i--) {
        A2[i] = A2[i+1] + A2[i];
    }
    int ans = 0;
    for (int i = 0; i < N; i++) {
        ans = max(ans, A1[i]+A2[i]);
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
using namespace std;
int main (){
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    if( a + b > c + d) cout << "Left" << endl;
    else if( a + b == c + d) cout << "Balanced" << endl;
    else if( a + b < c + d) cout << "Right" << endl;
    return 0;
}


Measured memory_bytes: 256
///not today

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

#define SZ(x) (int)(x).size()
#define pb push_back
#define ll long long
#define xmax(x, y) (x) = max((x), (y))
#define xmin(x, y) (x) = min((x), (y))
#define F first
#define S second
#define pii pair<int, int>
#define pll pair<long long, long long>
#define int long long
#define pipii pair<int, pair<int, int> >
#define pf push_front

const int maxn = 2000* 100 + 5;
pll a[maxn];

int32_t main(){
    int n;
    cin >>n;
    for(int i = 0; i < n; i ++){
        cin >>a[i].F;
        a[i].S = i;
    }
    sort(a, a + n);
    int ans = 1, k = 1;
    ll mx=1;
    for(int i = 1; i < n; i ++){
        if(a[i].S > a[i - 1].S)
            k ++;
        else
            k = 1;
        mx=max(mx,k);
    }
    cout <<n - mx <<endl;
}


Measured memory_bytes: 3328
N = int(input())
A = list(map(int, input().split()))
flg = True
cnt = 0
while 1:
    for val in A:
        if val % 2 != 0:
            flg = False
    if flg:
        A = list(map(lambda x: x // 2, A))
        cnt += 1
    else:
        print(cnt)
        exit()



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

int n, score=0;

int main(){
    cin >> n;
    int a[n];
    for(int i=0; i<n; i++){
        cin >> a[i];
    }
    sort(a, a+n);
    for(int i=0; i<n; i++){
        if(i%2){
            score+=a[i];
        }
        else{
            score-=a[i];
        }
    }
    cout << abs(score) << endl;
}


Measured memory_bytes: 384
import java.io.IOException;
import java.io.InputStream;
import java.util.NoSuchElementException;

public class Main {
	private static FastScanner sc = new FastScanner();

	public static void main(String[] args) {
		long N = sc.nextLong();
		long A = sc.nextLong();
		long B = sc.nextLong();
		
		long[] h = new long[(int)N];
		long maxA = 0;
		long maxB = 0;
		for(int i=0; i<N; i++) {
			h[i] = sc.nextLong();

			if((h[i] - 1) / A + 1 > maxA) {
				maxA = (h[i] - 1) / A + 1;
			}
			
			if((h[i] - 1) / B + 1 > maxB) {
				maxB = (h[i] - 1) / B + 1;
			}
		} 
		
		long l = maxA;
		long r = maxB;
		while(l < r) {
			long m = (l + r) / 2; 
//			System.out.println(l + " " + m + " " + r);
			long cnt = 0;
			for(int i=0; i<N; i++) {
				if(h[i] - B * m > 0) {
					cnt += (h[i] - B * m - 1) / (A - B) + 1;
				}
			}
			if(cnt <= m) {
				cnt = 0;
				for(int i=0; i<N; i++) {
					if(h[i] - B * (m - 1) > 0) {
						cnt += (h[i] - B * (m - 1) - 1) / (A - B) + 1;
					}
				}
				if(cnt > (m-1)) {
					l = m;
					break;
				} else {
					r = m - 1;
				}
			} else {
				l = m + 1;
			}
		}
		
		System.out.println(l);
	}

	static class FastScanner {
        private final InputStream in = System.in;
        private final byte[] buffer = new byte[1024];
        private int ptr = 0;
        private int buflen = 0;
        private boolean hasNextByte() {
            if(ptr < buflen) {
                return true;
            } else {
                ptr = 0;
                try {
                    buflen = in.read(buffer);
                } catch(IOException e) {
                    e.printStackTrace();
                }
                if(buflen <= 0) {
                    return false;
                }
            }
            return true;
        }
        private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
        private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
        private void skipUnprintable() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;}
        public boolean hasNext() { skipUnprintable(); return hasNextByte();}
        public String next() {
            if (!hasNext()) throw new NoSuchElementException();
            StringBuilder sb = new StringBuilder();
            int b = readByte();
            while(isPrintableChar(b)) {
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }
        public long nextLong() {
            return Long.parseLong(next());
        }
        public int nextInt(){
            return Integer.parseInt(next());
        }
        public double nextDouble(){
            return Double.parseDouble(next());
        }
    }
}


Measured memory_bytes: 39428
main = do
    line <- getLine
    let [x, y] = map (\n -> read n :: Int) $ words line
    if x == 0 && y == 0 then
        return ()
    else do
        putNums x y
        main

putNums :: Int -> Int -> IO ()
putNums x y
  | x <= y    = putStrLn $ (show x) ++ " " ++ (show y)
  | otherwise = putStrLn $ (show y) ++ " " ++ (show x)


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

   int erato(int a, int b){
    while(a != 0 && b != 0){
      if(a >= b){
          a = a % b;
        }
        else{
          b = b % a;
        }
    }
    return a + b;
  }
     
    int main(){
      int N;
      cin >> N;
      int A[N];
      for(int i=0; i<N; i++)
        cin >> A[i];
      
      int max = 1;

      int L[N], R[N];
      L[0] = 0;
      R[N-1] = 0;
      for(int i=1; i<N; i++){
        L[i] = erato(L[i-1], A[i-1]);
      }
      for(int i=N-1; i>0; i--){
        R[i-1] = erato(R[i], A[i]);
      }

      for(int i=0; i<N; i++){
        if(max < erato(L[i],R[i]))
        max = erato(L[i], R[i]);
      }

      
      cout << max << endl;
    }

Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll mod = 1e9+7;

int main(){
    int n,c,k;
    cin >> n >> c >> k;
    int ans = 0;
    int cnt = 0;
    vector<int> t(n);
    for(int i = 0; i < n; i++) cin >> t[i];
    sort(t.begin(),t.end(),greater<int>());
    int memo = t[0];
    for(int i = 0; i< n; i++){
        cnt++;
        memo = max(t[i],memo);
        if(t[i]+k < memo){
            ans++;
            cnt = 1;
            memo = t[i];
        }
        else if(cnt == c){
            cnt = 0;
            ans++;
            memo = -1;
        }
    }
    ans += (cnt+c-1)/c;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int max_n=5005;
int n,k,a[max_n];
bool pre[max_n][max_n],suf[max_n][max_n];
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)scanf("%d",a+i);
    pre[0][0]=1;
    for(int i=0;i<n;i++){
        for(int j=0;j<=k;j++){
            pre[i+1][j]|=pre[i][j];
            pre[i+1][min(j+a[i+1],k)]|=pre[i][j];
        }
    }
    suf[n+1][0]=1;
    for(int i=n+1;i>=2;i--){
        for(int j=0;j<=k;j++){
            suf[i-1][j]|=suf[i][j];
            suf[i-1][min(j+a[i-1],k)]|=suf[i][j];
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        int now=0;
        for(int j=k;j>=0;j--){
            while(now+j<k-a[i]||now<k&&!suf[i+1][now])++now;
            if(pre[i-1][j]&&now+j<k){
                ans++;
                break;
            }
        }
    }
    printf("%d\n",n-ans);
    return 0;
}

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

int main(){
  int A,B;
  cin>>A>>B;
  if(A>=13){
    cout<<B<<endl;
  }
  else if(A<=12 &&A>=6){
    cout<<B/2<<endl;
  }
  else{
    cout<<0<<endl;
  }
}
    

Measured memory_bytes: 256
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
ab = [LI() for _ in range(n)]

A = [a for a,b in ab]
A.sort()
B = [b for a,b in ab]
B.sort()
ab.sort(key=itemgetter(0))
if n % 2:
    print(B[n//2] - A[n//2] + 1)
else:
    ans = (B[n//2] + B[n//2 - 1]) - (A[n//2] + A[n//2 - 1]) + 1
    print(ans)




Measured memory_bytes: 117124
//g++ -std=c++14 test.cpp -o test.out
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <vector>
#include <queue>
#include <map> 
#include <utility>
#include <limits.h>
#include <bitset>
#include <set>
using namespace std;
 
#define LL long long int
const LL INF = (LL)(1e18)+1;
const int INF_INT = 2147483647-1e6;
const LL mod = 1000000007ll;

string S;
deque<char> S_dequeue;
int Q;
 
LL ans = -1;

bool reverse_flag = false;
 
void solve(){
	for(int i=0;i<S.length();i++){
		S_dequeue.push_back(S[i]);
	}
	for(int i=0;i<Q;i++){
		int T = 1;
		cin >> T;
		if(T==1){
			reverse_flag = !reverse_flag;
		}
		if(T==2){
			int F; char C;
			cin >> F >> C;
			if(F==1){
				if(!reverse_flag){
					S_dequeue.push_front(C);
				}else{
					S_dequeue.push_back(C);
				}
			}
			if(F==2){
				if(!reverse_flag){
					S_dequeue.push_back(C);
				}else{
					S_dequeue.push_front(C);
				}
			}
		}
	}
}
 
int main(){
	cin >> S;
	cin >> Q;
 
	solve();
 
	if(!reverse_flag){
		for(auto i=S_dequeue.begin();i<S_dequeue.end();i++){
			cout << *i;
		}
	}else{
		for(auto i=S_dequeue.end()-1;i>=S_dequeue.begin();i--){
			cout << *i;
		}
	}
	return 0;
}

Measured memory_bytes: 896
def main():
    c1 = list(map(int, input().split()))
    c2 = list(map(int, input().split()))
    c3 = list(map(int, input().split()))
    if abs(c1[0] - c1[1]) == abs(c2[0] - c2[1]) == abs(c3[0] - c3[1]) and \
            abs(c1[0] - c1[2]) == abs(c2[0] - c2[2]) == abs(c3[0] - c3[2]):
        print('Yes')
    else:
        print('No')


main()


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn =1e5+5;
const int inf=1e9;
int n,m,l;
int e[301][301],ans[301][301];

int main(){
    ios::sync_with_stdio(false);
    memset(e,0x3f,sizeof e);
    memset(ans,0x3f,sizeof ans);
    cin>>n>>m>>l;
    for(int i=1;i<=m;i++){
        int a,b,w;
        cin>>a>>b>>w;
        e[a][b]=w;e[b][a]=w;
    }
    for(int i=1;i<=n;i++)e[i][i]=0;

    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            e[i][j]=min(e[i][j],e[i][k]+e[k][j]);
    }

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(e[i][j]<=l)ans[i][j]=1;

     for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                ans[i][j]=min(ans[i][j],ans[i][k]+ans[k][j]);


    int Q;
    cin>>Q;
    while(Q--){
        int s,t;
        cin>>s>>t;
        if(ans[s][t]>2*n)cout<<-1<<endl;
        else cout<<ans[s][t]-1<<endl;
    }
    return 0;
}


Measured memory_bytes: 4304
#include <iostream>
#include <iomanip>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <stack>
#include <queue>

#define FOR(i, b, e) for(ll i = (ll)(b); i < (ll)(e); ++i)
#define RFOR(i, b, e) for(ll i = (ll)(e-1); i >= (ll)(b); --i)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, 0, n)
#define REPC(x,c) for(const auto& x:(c))
#define VS vector<string>
#define VL vector<long long>
#define VI vector<int>
#define VVI vector<vector<int>>
#define ALL(x) (x).begin(),(x).end()
#define SORT(x) sort(ALL(x))
#define RSORT(x) sort((x).rbegin(),(x).rend())
#define PAIR pair<ll,ll>
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

using  ll = long long;
constexpr int MOD = 1000000007;
using namespace std;

ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

VL prime_decomposition(ll n) {
	ll i = 2;
	VL table{};
	while (i * i <= n) {
		while (n % i == 0) {
			n /= i;
			table.emplace_back(i);
		}
		++i;
	}
	if (n > 1) {
		table.emplace_back(n);
		return table;
	}
}

ll compMax(const VL& a, const VL& b, ll tmp) {

	ll size = a.size();
	ll tmpa = 0;
	REP(i, size) {
		tmpa += b[i] - a[i];
		if (i > 0) {
			tmpa += b[i - 1] - a[i];
		}
	}
	if (tmp != 0) {
		tmpa = std::max(tmpa + tmp - a[0], tmpa + b[size - 1] - tmp);
	}
	ll tmpb = 0;
	REP(i, size) {
		tmpb += b[i] - a[i];
		if (i > 0) {
			tmpb += b[i] - a[i - 1];
		}
	}
	if (tmp != 0) {
		tmpb = std::max(tmpb + b[0] - tmp, tmpb + tmp - a[size - 1]);
	}

	return max(tmpa, tmpb);
}

int main() {
	ll n;
	cin >> n;
	VL v(n);
	REP(i, n) { cin >> v[i]; }

	sort(ALL(v));

	VL a, b;
	a.reserve(n / 2);
	b.reserve(n / 2);
	RREP(i, n) {
		if (i < n / 2) {
			a.emplace_back(v[i]);
		} else if (i >= n / 2) {
			b.emplace_back(v[i]);
		}
	}

	ll tmp = 0;
	if (n % 2 == 1) {
		tmp = b[n / 2];
		b.pop_back();
	}

	ll max = 0;
	max = std::max(max, compMax(a, b, tmp));

	VL t = a;
	sort(ALL(a));
	max = std::max(max, compMax(a, b, tmp));

	sort(ALL(b));
	max = std::max(max, compMax(t, b, tmp));

	max = std::max(max, compMax(a, b, tmp));

	cout << max << endl;
}

Measured memory_bytes: 2176
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<iostream>
#include<string.h>
#include<stack>
using namespace std;
int main()
{
    int  n;
    //char aa[40005];
    while(~scanf("%d",&n))
    {
        stack<int>p;
        int a;
        if(n==0)
            printf("0\n");
       else
       {
           while(n!=0)
           {
               a = abs(n%(-2));
               p.push(a);
               n = (n-a)/(-2);
           }
       }
       while(!p.empty())
       {
          cout<<p.top();
           p.pop();
       }
       printf("\n");
    }
    return 0;
}


Measured memory_bytes: 256
/*
このコード、と～おれ!
Be accepted!
  ∧＿∧　
（｡･ω･｡)つ━☆・*。
⊂　　 ノ 　　　・゜+.
　しーＪ　　　°。+ *´¨)
　　　　　　　　　.· ´¸.·*´¨) ¸.·*¨)
　　　　　　　　　　(¸.·´ (¸.·'* ☆
*/

#define rep(i, n) for(int i = 0; i < (n); ++i)
#define repr(i, n) for(int i = n; i >= 0; --i)
#define printynl(a) printf(a ? "yes\n" : "no\n")
#define printyn(a) printf(a ? "Yes\n" : "No\n")
#define printYN(a) printf(a ? "YES\n" : "NO\n")
#define printfin(a) printf(a ? "possible\n" : "inposible\n")
#define all(x) (x).begin(), (x).end()
using ll = long long;

//マクロとかここまで

#include <stdio.h>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <vector>

using namespace std;

int main() {
	
	int n, a, b, ans = 0;
	scanf("%d", &n);
	rep(i, n) {
		scanf("%d%d", &a, &b);
		ans += b - a + 1;
	}
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 128
n = int(input())
if n == 1:
	print (1)
	exit()
def make_divisors(N):
	divisors = []
	for i in range(1, int(N**0.5)+1):
		if N % i == 0:
			divisors.append(i)
			if i != N // i:
				divisors.append(N//i)

	# divisors.sort()
	return divisors
a = make_divisors(n)
a.sort()
c = 100
for i in a:
	if i > n//2:
		break
	j = n//i
	c = min(max(len(str(i)),len(str(j))),c)
print(c)

Measured memory_bytes: 3064
#include<iostream>
#include<string>
using namespace std;
int main()
{
	string s;
	cin>>s;
	int a[11],tot=0;
	for(int i=0;i<s.length();i++)
	{
		if(s[i]=='0') {a[++tot]=0;continue;}
		if(s[i]=='1') {a[++tot]=1;continue;}
		if(tot) tot--;
	}
	for(int i=1;i<=tot;i++) cout<<a[i];
	cout<<endl;
	return 0;
}

Measured memory_bytes: 256