akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

int fri[100010];

int find(int x){
  if( fri[x] == x ) return x;
  else return fri[x] = find(fri[x]);
}

bool same(int x, int y){
  return find(x) == find(y);
}

void uf_union(int x, int y){
  x = find(x);
  y = find(y);
  fri[x] = y;
}

int main(){

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

  // init
  for(int i=0; i<n; i++) fri[i] = i;

  //
  for(int i=0; i<m; i++){
    int u,v; scanf("%d %d",&u,&v);
    uf_union(u,v);
  }

  cin >> q;
  for(int i=0; i<q; i++){
    int u,v; scanf("%d %d",&u,&v);
    if( find(u) == find(v) ) printf("yes\n");
    else printf("no\n");
  }


}

Measured memory_bytes: 2200
N,K = map(int,input().split())
A = list(map(int,input().split()))
from collections import defaultdict as ddict
A_dict = ddict(int)
for a in A:
    A_dict[a] += 1
A_tupple = sorted(A_dict.items(), key=lambda x:x[1],reverse=True)
ans = 0
for a in A_tupple[K:]:
    ans += a[1]
print(ans)

Measured memory_bytes: 40060
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, n) for(int i = 0; i < (n); i++)
#define MEM(a, x) memset(a, x, sizeof(a))
#define ALL(a) a.begin(), a.end()
#define UNIQUE(a) a.erase(unique(ALL(a)), a.end())
typedef long long ll;

int h, w, n;
int a[10005], b[105][105];

int main(int argc, char const *argv[]) {
	ios_base::sync_with_stdio(false);
	cin >> h >> w >> n;
	int x = 1, y = 1;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		while (a[i]) {
			b[x][y] = i;
			if (x & 1) {
				if (y < w) y++;
				else x++;
			}
			else {
				if (y > 1) y--;
				else x++;
			}
			a[i]--;
		}
	}
	for (int i = 1; i <= h; i++) {
		for (int j = 1; j <= w; j++) {
			cout << b[i][j];
			if (j == w) cout << endl;
			else cout << " ";
		}
	}
	return 0;
}

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

using namespace std;

vector<int> init_cand (int n) {
    vector<int> cand;

    int i = 6;
    while ( i <= n ) {
        cand.push_back(i);
        i *= 6;
    }

    i = 9;
    while ( i <= n ) {
        cand.push_back(i);
        i *= 9;
    }

    return cand;
}

int main (void) {
    int N;
    cin >> N;

    vector<int> cand = init_cand(N);

    vector<int> ans(N+1);
    /* 1円ずつ引き出したときの回数で初期化 */
    for ( int i = 0; i <= N; i++ ) ans.at(i) = i;

    for ( auto itr : cand ) {
        for ( int i = 1; i <= N; i++ ) {
            if ( i - itr < 0 ) continue;
            ans.at(i) = min(ans.at(i), ans.at(i-itr) + 1);
        }
    }

    cout << ans.at(N) << endl;
    return 0;
}


Measured memory_bytes: 3724
r, c = map(int, input().split())
cells = [list(map(int, input().split())) for _ in range(r)]

cells.append([0 for i in range(c+1)])
for i in range(r):
    cells[i].append(sum(cells[i]))
    for j in range(c+1):
        cells[r][j] += cells[i][j]

for c in cells:
    print(' '.join(map(str, c)))


Measured memory_bytes: 5700
# coding: utf-8
n = int(input())
dic = {}
for i in range(n):
    s = "".join(sorted(input()))
    dic.setdefault(s, 0)
    dic[s] += 1
ans = 0
for x in dic.values():
    ans += int(x * (x - 1) / 2)
print(ans)

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

namespace test
{
    class MainClass
    {
        public static void Main(string[] args)
        {

            //問題162

            int k = int.Parse(Console.ReadLine());

            int ans = 0;

            for (int a = 1; a < k + 1; a++)
            {
                for (int b = 1; b < k + 1; b++)
                {
                    for (int c = 1; c < k + 1; c++)
                    {
                        //最大公約数
                        int d = Saidaikoyaku(a, b);

                        ans += Saidaikoyaku(c, d);
                    }
                }
            }


            Console.WriteLine(ans);
        }

        //a < b < cに並べ替えてから使用
        private static int Saidaikoyaku(int a, int b)
        {

            if (a < b)
            {
                if (b % a == 0)
                {
                    return a;
                }

                return Saidaikoyaku(b % a, a);

            }
            else
            {
                if (a % b == 0)
                {
                    return b;
                }

                return Saidaikoyaku(a % b, b);

            }



        }

    }





    
}


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

const int N = 200009, Mod = 1000000007;
int n, a[N], sum[N], ans;

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++ i) scanf("%d", &a[i]), sum[i] = (a[i] + sum[i - 1]) % Mod;
	for (int i = 1; i <= n; ++ i) 
		ans = (ans + 1LL * a[i] * (sum[n] - sum[i] + Mod) % Mod) % Mod;
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 5356
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a,b,c;
  //入力 
  cin >> a >> b;
  //処理
	if ((a * b) % 2) {
      cout << "Odd" << endl;
    }else{
     cout << "Even" << endl; 
    }
  
  //出力
}

Measured memory_bytes: 3568
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
    public static void main(String [] args) {
        final Scanner scanner = new Scanner(System.in);
        int L = scanner.nextInt();
        final int [][] edges = new int[20][20];
        final Set<Double>[][] lengths = new HashSet[20][20];
        final int [] pow = new int[20];
        int i = 0;
        int largest = 0;
        while (L > 0) {
            pow[i] = L % 2;
            if (pow[i] == 1) {
                largest = i;
            }
            L /= 2;
            ++i;
        }
        for (i = 0; i <= largest; ++i) {
            for (int j = 0; j <= largest; ++j) {
                lengths[i][j] = new HashSet<>();
            }
        }
//        for (i = 0; i < 20; ++i) {
//            System.out.println("pow[" + i + "]: " + pow[i]);
//        }
//        System.out.println("largest: " + largest);
        int edgeNum = 0;
        for (i = 0; i < largest; ++i) {
            edges[i][i + 1] = 2;
            edgeNum += 2;
            lengths[i][i + 1].add((double)0);
            lengths[i][i + 1].add(Math.pow(2, i));
        }
        double maxLength = Math.pow(2, largest) - 1;

        for (i = largest - 1; i >= 0; --i) {
            if (pow[i] == 1) {
                edges[i][largest]++;
                lengths[i][largest].add(maxLength + 1);
                maxLength = Math.max(maxLength, maxLength + Math.pow(2, i));
                ++edgeNum;
            }
        }
        System.out.println(largest + 1 + " " + edgeNum);
        for (i = 0; i <= largest; ++i) {
            for (int j = i; j <= largest; ++j) {
                for (final double length : lengths[i][j]) {
                    System.out.println((i + 1) + " " + (j + 1) + " " + (int)length);
                }
            }
        }
    }
}


Measured memory_bytes: 23764
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 200005

int a[maxn];
int n, i;

int main(void){
	cin >> n;
	for(i = 0; i < n; i++)	cin >> a[i];
	int maxv = a[1] - a[0];
	int minv = a[0];
	for(i = 1; i < n; i++){
		maxv = max(maxv, a[i] - minv);
		minv = min(minv, a[i]);
	}
	cout << maxv << endl;
	return 0;
} 


Measured memory_bytes: 3852
def s():
 def b(M,x,y,n=1):
  M[x][y]=0;a=n
  if M[x-1][y]:a=max(a,b(M,x-1,y,n+1))
  if M[x][y-1]:a=max(a,b(M,x,y-1,n+1))
  if M[x+1][y]:a=max(a,b(M,x+1,y,n+1))
  if M[x][y+1]:a=max(a,b(M,x,y+1,n+1))
  M[x][y]=1
  return a
 for e in iter(input,'0'):
  n,m=int(e),int(input())
  P=[[0]*(n+2)for _ in[0]*(m+2)]
  for i in range(m):P[i+1][1:-1]=map(int,input().split())
  print(max([b(P,i,j)for i in range(1,m+1)for j in range(1,n+1)if P[i][j]]))
if'__main__'==__name__:s()


Measured memory_bytes: 5744
// --https://kenkoooo.com/atcoder/#/table/soma62jp
#include <iostream>
#include <string>
#include <cmath>
#include <sstream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cstring>

using namespace std;

int main(int argc, char* argv[]) {

	int x1,y1,x2,y2;

	cin >> x1 >> y1 >> x2 >> y2;

	cout << (x2-x1)+(((y2-y1)*-1+x1)-x1)+x1 << " " << (y2-y1)+(((x2-x1)+y1)-y1)+y1 << " " << (y2-y1)*-1+x1 << " " << (x2-x1)+y1 << endl;

	return 0;

}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int k = sc.nextInt();
		int num = 0;
		if(k%2 == 0) {
			num = k/2;
			System.out.println(num * num);
		}else {
			num = k/2;
			System.out.println(num * ((k/2)+1));
		}
	}
}

Measured memory_bytes: 22996
get = lambda: map(int, raw_input().split())

while True:
        (n, m) = get()

        if n + m == 0:
                break

        res = [0 for i in range(m)]
        for i in range(n):
                a = get()
                for j in range(m):
                        res[j] -= a[j]

        res = zip(res, range(1, m + 1))
        res.sort()

        for i in range(m):
                print res[i][1],

        print

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

typedef long double ld;									// XD
#define int long long
#define PB push_back
#define all(x) (x).begin(),(x).end()
#define ii pair <int,int>
#define mii map <int,int>
#define vi vector<int>
#define vii vector< ii >
#define F first
#define S second
#define rep(i,a,b)  for(int i=a;i<b;i++)
#define rep1(i,a,b) for(int i=a;i<=b;i++)
#define repd(i,a,b) for(int i=a; i>=b; --i)
#define sz(x) (int)((x).size())
#define mem(a,x) memset(a,x,sizeof(a))
const long double PI=3.141592653589793238462643383279502884197169399375105820974944;
inline void io(){
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}

const int mod = 1e9+7;
const int INF = 1e18;
const int maxn = 2e5+5;


void solve(){
	int n; cin>>n;
	int a[n];
	rep(i, 0, n) cin>>a[i];
	sort(a, a+n);
	int ans = 0;
	rep(i, 0, n){
		rep(j, 0, i){
			rep(k, 0, j){
				if(a[i] == a[j] || a[j] == a[k] || a[i] == a[k]) continue;
				if(a[j]+a[k] > a[i]) ++ans;
			}
		}
	}
	cout<<ans;
}
signed main() 
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); //io();
    cout<<setprecision(16);
    
    int tc=1;// cin>>tc; 
    while(tc--){
        solve();cout<<'\n';
    }
    return 0;
}



Measured memory_bytes: 3656
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
    sizeは(int)とキャストしよう
    ごちゃごちゃ場合分けを考える前に全探索は考えましたか？
*/

const ll mod = 1e9+7;

void chmod(ll &M){
    if(M >= mod) M %= mod;
    else if(M < 0){
        M += (abs(M)/mod + 1)*mod;
        M %= mod;
    }
}

ll modpow(ll x, ll n){
    if(n == 0) return 1;

    ll res = modpow(x, n/2);
    if(n%2 == 0) return res*res%mod;
    else return res*res%mod*x%mod;
}

ll power(ll x, ll n){
    if(n == 0) return 1;

    ll res = power(x, n/2);
    if(n%2 == 0) return res*res;
    else return res*res*x;
}

int getl(int i, int N) { return i==0? N-1:i-1; };
int getr(int i, int N) { return i==N-1? 0:i+1; };

/* <--------------------------------------------> */


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

    ll n, k; cin >> n >> k;
    ll ans = 0;
    for(ll b=k+1; b<=n; ++b){
        ans += (b-k)*(n/b);
        if(k==0) --ans;
        ans += max(0LL, n+1-b*(n/b)-k);
    }
    cout << ans << '\n';

	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
int main() {
    int w, h, x, y, r;
    scanf("%d %d %d %d %d", &w, &h, &x, &y, &r);
    if (r <= x && r <= y && x <= (w - r) && y <= (h - r)) printf("Yes\n");
    else printf("No\n");
    return 0;
}


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

int main() {
  string s;
  cin >> s;
  int n = s.length();
  string t = "";
  for (int i = 0; i < n; i++) {
    if (i < n - 1 && s[i] == 'B' && s[i + 1] == 'C') {
      t += 'X';
      i++;
    } else {
      t += s[i];
    }
  }
  n = t.length();
  int c = 0;
  ll ans = 0;
  for (int i = 0; i < n; i++) {
    if (t[i] == 'X') {
      ans += c;
    } else {
      c = (t[i] == 'A') ? c + 1 : 0;
    }
  }
  cout << ans << endl;
}



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

int main() {
	int n;
	cin >> n;
	vector<int> h(n);
	for (int i = 0; i < n; i++) {
		cin >> h[i];
	}
	vector<int> c(n);
	c[0] = 0;
	c[1] += abs(h[1] - h[0]);
	for (int i = 2; i < n; i++) {
		c[i] = min(c[i-1] + abs(h[i] - h[i-1]), c[i-2] + abs(h[i] - h[i-2]));
	}
	cout << c[n-1] << endl;
}


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

int main()
{
    int n,m;cin >> n;
    vector<int> LIS(n+2,INF);
    for (int i=0;i<n;i++)
    {
        cin >> m;
        *lower_bound(LIS.begin(),LIS.end(),m)=m;
    }
    for (int i=0;i<n+1;i++)
    {
        if (LIS[i]==INF)
        {
            cout << i << endl;
            break;
        }
    }
    return 0;
}


Measured memory_bytes: 3132
s = gets.chomp
t = gets.chomp

s_origin = s.dup
loop do
  if s == t
    puts 'Yes'
    break
  end

  ss = s.chars
  c = ss.shift
  ss << c
  s = ss.join

  if s == s_origin
    puts 'No'
    break
  end
end


Measured memory_bytes: 3964
#include <stdio.h>
#include <stdlib.h>

int main(){
    int n, total = 0, pos_inicial, pos_final;
    scanf("%d", &n);
    for (int i = 0; i < n; i++){
        scanf("%d %d", &pos_inicial, &pos_final);
        if (pos_inicial == pos_final)
            total += 1;
        else
            total += abs(pos_final - pos_inicial) + 1;
    }
    printf("%d\n", total);
    return 0;
}

Measured memory_bytes: 128
import Control.Applicative
import Control.Monad
import Data.List
import Data.Maybe (isJust)

parse :: String -> Maybe String
parse [] = Just ""
parse xs
    | Just ys <- stripPrefix "eraser" xs = Just ys
    | Just ys <- stripPrefix "erase" xs = Just ys
    | Just _ <- stripPrefix "dreamer" xs
        = let Just as = stripPrefix "dream" xs
              Just bs = stripPrefix "dreamer" xs
           in parse as <|> parse bs
    | Just ys <- stripPrefix "dream" xs = Just ys
    | otherwise = Nothing

loop xs = case parse xs of
    Nothing -> Nothing
    Just "" -> Just ""
    Just ys -> loop ys

main :: IO ()
main = do
    ss <- getLine
    if isJust $ loop ss
        then putStrLn "YES"
        else putStrLn "NO"

Measured memory_bytes: 4988
#include <bits/stdc++.h>
#define int long long
#define double long double
#define mod (int)(1e9+7)
#define inf (int)(3e18+7)
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define all(x) x.begin(),x.end()
using namespace std;

signed main() {
  int n, ans = 0;
  cin >> n;
  vector<int> p(n);
  rep(i, n) cin >> p.at(i);
  for(int i = 1; i < n-1; i++) {
    if(p.at(i) < p.at(i+1) && p.at(i) > p.at(i-1)) ans++;
    else if(p.at(i) > p.at(i+1) && p.at(i) < p.at(i-1)) ans++;
  }
  cout << ans;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void) {
    int H, W, i, j;
    while(1) {
        scanf("%d%d", &H, &W);
        if(H == 0 && W == 0) break;
        for(i = 0; i < H; i++) {
            putchar('#');
            for(j = 1; j < W-1; j++) {
                if(i == 0 || i == H-1) putchar('#');
                else putchar('.');
            }
            puts("#");
        }
        putchar('\n');
    }
    return 0;
}


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

int main()
{
	int a, b, c;
	cin >> a >> b >> c;
	if(a > b) swap(a, b);
	if(a > c) swap(a, c);
	if(b > c) swap(b, c);
	int ans = 0;
	ans += (c - a) / 2;
	a += ((c - a) / 2 * 2);
	ans += (c - b) / 2;
	a += ((c - b) / 2 * 2);
	int t = (c - b) + (c - a);
	cout << ans + (t == 0 ? 0 : 3 - t) << endl;
	return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
int main()
{
    int n;
    char j;
    scanf("%d\n", &n);
    set<char> s;
    for (int i = 0; i < n; ++i)
    {
        scanf("%c ", &j);
        s.insert(j);
    }
    printf(s.size() == 3 ? "Three\n" : "Four\n");
}



Measured memory_bytes: 256
/*
int arr[N+1];
  
  for(i=0;i<N;i++){
    scanf("%d",&in);
    arr[in] = i+1;
  }
 
  for(i=0;i<N;i++){
    printf("%d ",arr[i+1]);
  }

*/







#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main(){
    ll n, x, i;
    cin >> n;
   
   
  
  
    vector < pair < ll, ll > > v;
    for(i = 0; i < n; i++){
        cin >> x;
        v.push_back(make_pair(x, i+1));
// or   v.emplace_back(x, i+1);
    }
   
    
  
  
     sort(v.begin(), v.end());//wrt first element
   
   
  
  
  
     for(auto it : v){
        cout << it.second << " ";
    }
   
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  return 0;
}


Measured memory_bytes: 2544
package main

import (
	"bufio"
	"fmt"
	"io"
	"math"
	"os"
	"strconv"
)

func main() {
	n := readInt()

	ans := math.MaxInt64
	sq := int(math.Sqrt(float64(n)))
	for i := 1; i <= sq; i++ {
		if n%i == 0 {
			ans = min(ans, i+n/i)
		}
	}

	fmt.Println(ans - 2)
}

// sort ------------------------------------------------------------

type xxx struct {
	x int
}

type sortArray []xxx

func (s sortArray) Len() int           { return len(s) }
func (s sortArray) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
func (s sortArray) Less(i, j int) bool { return s[i].x < s[j].x }

// -----------------------------------------------------------------

var (
	readString func() string
	readBytes  func() []byte
)

func init() {
	readString, readBytes = newReadString(os.Stdin)
}

func newReadString(ior io.Reader) (func() string, func() []byte) {
	r := bufio.NewScanner(ior)
	r.Buffer(make([]byte, 1024), int(1e+11))
	r.Split(bufio.ScanWords)

	f1 := func() string {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Text()
	}
	f2 := func() []byte {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Bytes()
	}
	return f1, f2
}

func readInt() int {
	return int(readInt64())
}

func readInt64() int64 {
	i, err := strconv.ParseInt(readString(), 10, 64)
	if err != nil {
		panic(err.Error())
	}
	return i
}

func readFloat64() float64 {
	f, err := strconv.ParseFloat(readString(), 64)
	if err != nil {
		panic(err.Error())
	}
	return f
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

func sum(a []int) int {
	var ret int
	for i := range a {
		ret += a[i]
	}
	return ret
}

func sumFloat64(a []float64) float64 {
	var ret float64
	for i := range a {
		ret += a[i]
	}
	return ret
}

func gcd(m, n int) int {
	for m%n != 0 {
		m, n = n, m%n
	}
	return n
}

func lcm(m, n int) int {
	return m / gcd(m, n) * n
}


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

int readint() {
    return readln.chomp.to!int;
}

int[] readints() {
    return readln.split.map!(to!int).array;
}

int calc(int[] xs) {

    int rec(int p, int[] buf) {
        if (p == buf.length) {
            bool ok = false;
            for (int i = 0; i < buf.length; i++) {
                if (buf[i] % 2 == 0) {
                    ok = true;
                    break;
                }
            }
            return ok ? 1 : 0;

        }

        int ans = 0;
        for (int i = -1; i <= 1; i++) {
            buf[p] = xs[p] + i;
            ans += rec(p + 1, buf);
        }
        return ans;
    }

    auto buf = new int[xs.length];
    return rec(0, buf);
}

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


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include<math.h>
#include<list>
#include <algorithm>
#include<set>
#include<vector>
#include<math.h>
#include<map>
#include<string>
#include <numeric>
#include <queue>
#include <sstream>
#include <bitset>
#include<stack>

using namespace std;
using ll = long long;
using vll = vector<long long>;
using sll = set<long long>;


template<typename T>
T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<typename T>
T lcm(T a, T b) { return a / gcd(a, b) * b; }

template<typename T>
map<T, T> getPrimeFactor(T n) {
	map<T, T> res;
	for (T i = 2; i * i <= n; ++i) {
		while (n % i == 0) {
			res[i] ++;
			n /= i;
		}
	}
	if (n != 1) res[n] = 1;
	return res;
}

template<typename T>
bool IsPrimeNumber(T num)
{
	if (num <= 2) return true;
	else if (num % 2 == 0) return false;

	double sqrtNum = sqrt(num);
	for (int i = 3; i <= sqrtNum; i += 2)
	{
		if (num % i == 0)
		{
			return false;
		}
	}

	return true;
}

long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}

// 繰り返し二乗法
ll pow2(ll n, ll p, ll mod) {
	if (p == 0 || n == 1) {
		return 1;
	}
	else {
		ll ret = pow2(n * n % mod, p / 2, mod);
		if (p % 2 == 1) {
			ret *= n;
		}
		return ret % mod;
	}
}


#define rep(i,s,e) for(ll i=s;i<e;i++)
#define repeq(i,s,e) for(ll i=s;i<=e;i++)

int main() {
	string S;
	cin >> S;

	vector<set<char>> vs(S.size()+1);
	rep(i, 0, S.size()) {
		vs[i + 1] = vs[i];
		vs[i+1].insert(S[i]);
	}

	char next = 'a'-1;
	for (ll i = S.size(); i >=0; i--) {
		for (char c = next+1; c <= 'z'; c++) {
			if (vs[i].find(c) == vs[i].end()) {
				cout << S.substr(0,i) << c << endl;
				return 0;
			}
		}
		next = S[i - 1];
	}

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

}


Measured memory_bytes: 3640
#ifdef LOCAL
  #define debug_echo(expr) cout << expr;
#else
  #define debug_echo(expr)
#endif

#define rep(i, n) for (int i = 0; i < n; i++)

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
using namespace std;

template<class T>
ostream& operator <<(ostream& out, const vector<T>& v) {
    out << "[";
    bool isfirst = false;
    for (const T& e : v) {
        out << (isfirst ? ", " : "") << e;
        isfirst = true;
    }
    out << "]";
    return out;
}
template<class T>
ostream& operator <<(ostream& out, const set<T>& s) {
    out << "{";
    bool isfirst = false;
    for (const T& e : s) {
        out << (isfirst ? ", " : "") << e;
        isfirst = true;
    }
    out << "}";
    return out;
}
template<class A, class B>
ostream& operator <<(ostream& out, const pair<A, B>& p) {
    out << "(" << p.first << ", " << p.second << ")";
    return out;
}
template<class K, class V>
ostream& operator <<(ostream& out, const map<K, V>& s) {
    out << "{";
    bool isfirst = false;
    for (const auto& e : s) {
        out << (isfirst ? ", " : "") << e;
        isfirst = true;
    }
    out << "}";
    return out;
}

//
// Implementation
//

int N;
int M;
char squares[50][50];

int get_repaintnum(int borderA, int borderB) {
    int repaintnum = 0;
    for (int i = 0; i < borderA; i++) {
        rep(j, M) {
            if (squares[i][j] != 'W') repaintnum++;
        }
    }
    for (int i = borderA; i < borderB; i++) {
        rep(j, M) {
            if (squares[i][j] != 'B') repaintnum++;
        }
    }
    for (int i = borderB; i < N; i++) {
        rep(j, M) {
            if (squares[i][j] != 'R') repaintnum++;
        }
    }
    return repaintnum;
}

int main() {
    cin >> N >> M;
    rep(i, N) {
        rep(j, M) {
            cin >> squares[i][j];
        }
    }

    int min_repaintnum = N*M;
    for (int borderA = 1; borderA < N-1; borderA++) {
        for (int borderB = borderA; borderB < N; borderB++) {
            min_repaintnum = min(min_repaintnum, get_repaintnum(borderA, borderB));
        }
    }
    cout << min_repaintnum << endl;
}

Measured memory_bytes: 3056
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define v(t) vector<t>
#define vv(t) vector<vector<t>>
#define p(t1,t2) pair<t1,t2>
using namespace std ;
int main(){
    ll N , K , i;
    cin >> N >> K ;
    v(int) P(N+1) , C(N+1) ;
    for(i=1;i<=N;++i) cin >> P[i] ;
    for(i=1;i<=N;++i) cin >> C[i] ;
    ll ans = INT64_MIN ;
    for(i=1;i<=N;++i){
        v(int) path ;
        int j = P[i] ;
        ll sum = 0 , cyclesum = 0 ;
        while(j!=i){
            sum += C[j] ;
            path.push_back(C[j]) ;
            j = P[j] ;
        }
        sum += C[i] ;
        path.push_back(C[i]) ;
        int m = path.size() ;
        for(j=0;j<m;++j){
            if(j<K){
                int lcnt = (K-1-j)/m ;
                cyclesum += path[j] ;
                ans=max(ans,cyclesum + max(sum*lcnt,sum*0)) ;
            }
        }
    }
    cout << ans << "\n" ;
    return 0 ;
}

Measured memory_bytes: 3708
#include <iostream>
#include <vector>
#include <map>
#include <cctype>
#include <algorithm>
#include <set>
#include <cmath>
using namespace std;

bool reach_above(int v, int t, const vector<int> &above) {
  if(v == t) return true;
  if(v == -1) return false;
  return reach_above(above[v], t, above);
}

void put_on_floor(int current, vector<int> &above, vector<int> &bellow) {
  if(current == -1) return;
  if(bellow[current] != -1) {
	above[bellow[current]] = -1;
	bellow[current] = -1;
  }
  put_on_floor(above[current], above, bellow);
}

int main(){
  for(int m; cin >> m && m;) {
	vector<int> bellow(m, -1), above(m, -1);

	for(int former, latter; cin >> former >> latter && former;) {
	  if(latter == 0) {
		--former;
		if(bellow[former] != -1) put_on_floor(former, above, bellow);
	  }
	  else if(latter != former) {
		--former, --latter;
		if(reach_above(former, latter, above)) {
		  put_on_floor(above[former], above, bellow);
		  if(bellow[former] != -1) above[bellow[former]] = -1;
		  above[latter] = former;
		  bellow[former] = latter;
		}
		else if(reach_above(latter, former, above)) {
		  // ignore
		}
		else {
		  while(above[latter] != -1) latter = above[latter];
		  put_on_floor(former, above, bellow);
		  above[latter] = former;
		  bellow[former] = latter;
		}
	  }
	  else { // latter == former
		// ignore
	  }
	}
	
	vector<int> piles;
	for(int i = 0; i < m; ++i) {
	  if(above[i] == -1) {
		int current = i;
		int height = 0;

		while(current != -1) {
		  current = bellow[current];
		  ++height;
		}
		piles.emplace_back(height);
	  }
	}

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

	for(const auto &e : piles) {
	  cout << e << endl;
	}
	cout << "end" << endl;
  }

  return 0;
}

Measured memory_bytes: 1212
import java.util.*;

class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] edges = new int[N];
        int sum = 0;
        int max = 0;
        for (int i = 0; i < N; i++) {
            edges[i] = sc.nextInt();
            sum += edges[i];
            max = Math.max(max, edges[i]);
        }
        System.out.println(max < (sum - max) ? "Yes" : "No");
    }
}

Measured memory_bytes: 23252
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
from collections import defaultdict

n = getN()
dc = defaultdict(int)
for i in range(n):
    s = input().strip()
    dc["".join(sorted(list(s)))] += 1

ans = 0
for v in list(dc.values()):
    ans += (v * (v - 1)) // 2

print(ans)

Measured memory_bytes: 59612
s = input()
ans = 0
tmp = ''
atgc = ['A', 'T', 'G', 'C']
kosu = 0

for mae in range(len(s)):
    for ato in range(len(s)):
        tmp = s[mae:ato+1]
        kosu = 0
        for cnt in range(len(tmp)):
            if tmp[cnt] in atgc:
                kosu += 1
            if kosu == len(tmp) and len(tmp) > ans:
                ans = len(tmp)

print(ans)

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

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

using namespace std;

bool is_57577(const vector<int> &l, int i) {
  deque<int> phrases = {5, 7, 5, 7, 7};
  for (int j = i; j < l.size(); ++j) {
    phrases[0] -= l[j];
    if (phrases[0] < 0) return false;
    if (phrases[0] == 0) {
      phrases.pop_front();
      if (phrases.empty()) return true;
    }
  }
  return false;
}

int main() {
  while(1){
    int n;
    cin>>n;
    if(!n)break;
    vector<int> l(n);
    REP(i,n){
      string s;
      cin>>s;
      l[i] = s.size();
    }
    REP(i,n) {
      if(is_57577(l, i)) {
        cout << (i+1) << endl;
        break;
      }
    }
  }
  return 0;
}

Measured memory_bytes: 3172
#include <iostream>
#include <vector>
#include <numeric>


using ll = long long int;
using namespace std;

using vll = std::vector<ll>;

vll values;

int main() {
  ll n, k;
  cin >> n >> k;
  for (int i = 0; i < n; i++) {
    ll v;
    cin >> v;
    values.push_back(v);
  }

  ll max_value = 0;
  for (ll l = 0; l <= n && l <= k; l++) {
    for (ll r = 0; r <= n && l + r <= n && l + r <= k; r++) {
      ll rest = k - l - r;
      vll positives, negatives;

      for (ll i = 0; i < l; i++) {
        ll v = values[i];
        if (v > 0) {
          positives.push_back(v);
        } else {
          negatives.push_back(-v);
        }
      }

      for (ll i = 0; i < r; i++) {
        ll v = values[n - 1 - i];
        if (v > 0) {
          positives.push_back(v);
        } else {
          negatives.push_back(-v);
        }
      }

      sort(negatives.begin(), negatives.end());
      ll returns = max(0LL, static_cast<ll>(negatives.size()) - rest);

      ll positive_sum = accumulate(positives.begin(), positives.end(), 0LL);
      ll negative_sum = accumulate(negatives.begin(), negatives.begin() + returns, 0LL);

//      cout << l << "," << r << "," << returns << "," << positive_sum << "," << negative_sum << endl;

      max_value = max(max_value, positive_sum - negative_sum);
    }
  }

  cout << max_value << endl;
  return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
using ll=long long;
#define print(n) cout<<n<<endl
#define rep(i,a,n) for(int i=a;i<n;i++)
#define ALL(s) s.begin(),s.end()
#define P pair<ll,ll>
#define vl vector<ll>
#define vi vector<int>
#define vvl vector<vector<ll>>
#define vvi vector<vector<int>>
const int M=100111;
const int inf=1000000007;
const long long INF=1e18;
int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
int ddx[8]={1,-1,0,0,1,-1,-1,1},ddy[8]={0,0,1,-1,1,-1,1,-1};

int main(){
	while(1){
		double dp[101][105]={};//dp[now][turn]: nowマス目に行く時にかかったターン数turn.
		dp[0][0]=1;
		int n,t,a,b,stop[101],back[101];
		cin>>n>>t>>a>>b;
		if(n==0)break;
		rep(i,0,a)cin>>stop[i];
		rep(i,0,b)cin>>back[i];
		double ans=0;
		double prob=0.16666666666666666;
		rep(turn,0,t)rep(now,0,n){
			if(dp[now][turn]){
				rep(k,1,7){
					//nowマスからnextマスへ進む.
					int next=now+k;
					if(next>n)next=n-(next-n);
					//nextがstopの座標だった時,continue
					bool ok=false;
					rep(l,0,a)if(stop[l]==next)ok=true;
					if(ok){
						dp[next][turn+2]+=dp[now][turn]*prob;
						continue;
					}
					//nextがbackの座標だった時,continue.
					ok=false;
					rep(l,0,b)if(back[l]==next)ok=true;
					if(ok){
						dp[0][turn+1]+=dp[now][turn]*prob;
						continue;
					}
					//nowからnextに進む.
					dp[next][turn+1]+=dp[now][turn]*prob;
				}
			}
		}
		rep(i,1,t+1)ans+=dp[n][i];
		print(fixed<<round(ans*1000000)/1000000);
	}
}






Measured memory_bytes: 3440
N,M = map(int,input().split())
drinkList = []
for _ in range(N):
    a,b = map(int,input().split())
    drinkList.append((a,b))
drinkList.sort()
neededMoney = 0
for price,num in drinkList:
    buy = min(M,num)
    neededMoney += buy*price
    M -= buy
    if M==0: break
print(neededMoney)

Measured memory_bytes: 16896
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		char[] s = sc.next().toCharArray();
		sc.close();

		int n = s.length;
		int[] a = new int[n];
		int now = 0;
		for (int i = 0; i < n; i++) {
			int k = s[i] - 'a';
			now ^= 1 << k;
			a[i] = now;
		}
		if (a[n - 1] == 0) {
			System.out.println(1);
			return;
		}

		int[] dp = new int[1 << 26];
		Arrays.fill(dp, 100000000);
		dp[0] = 0;
		for (int i = 0; i < n; i++) {
			for (int k = 0; k < 26; k++) {
				int pre = a[i] ^ (1 << k);
				dp[a[i]] = Math.min(dp[a[i]], dp[pre] + 1);
			}
		}
		System.out.println(dp[a[n - 1]]);
	}
}


Measured memory_bytes: 293124
#pragma GCC opointimize("Ofset_asc")
#pragma GCC opointimize("unroll-loops")
#pragma GCC target("avx2")
#pragma GCC opointimize("Os")
#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);
#define FO cout.tie(NULL);
#define FI cin.tie(NULL);
#define IN cin>>
#define OUT cout<<
#define loop(i,a,n) for(int i=a; i<n; i++)
#define rloop(i,a,n) for(int i=a; i>=n; i--)
#define endl "\n";
#define pb push_back
#define mp make_pair
#define set_bits(a) __builtin_popcountll(a)
#define ll long long int
#define ld long double
#define vll vector<long long int>
#define pll pair<long long int, long long int>
#define mod 1000000007
#define M 998244353
using namespace std;
ll gcd(ll a, ll b)
{
    return (b?gcd(b,a%b):a);
}
ll P(ll B, ll power, ll modulo)
{
    ll ans=1LL;
    while(power>0LL)
    {
        if(power%2LL==1LL)
        {
            ans=(ans*B)%modulo;
        }
        B=(B*B)%modulo;
        power/=2LL;
    }
    return ans;
}
bool isPrime(ll n)
{
    if(n<=1LL)
    {
        return false;
    }
    if(n<=3LL)
    {
        return true;
    }
    if(n%2==0LL || n%3==0LL)
    {
        return false;
    }
    for(ll i=5LL; (i*i)<=n; i+=6LL)
    {
        if(n%i==0LL || n%(i+2LL)==0LL)
        {
            return false;
        }
    }
    return true;
}
void vok()
{
    FAST
    FO
    FI
    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
        // freopen("error.txt","w",stderr);
    #endif
}
int main()
{
    vok();
    ll n;
    IN n;
    string s="";
    ll curr=26, countt=0, last=0;
    ll len=1;
    while(1)
    {
        countt+=curr;
        if(countt>=n)
        {
            break;
        }
        len++;
        curr*=26LL;
        last=countt;
    }
    n-=last;
    n--;
    loop(i,0,len)
    {
        int curr=n%26;
        char ch=curr+'a';
        s+=ch;
        n/=26;
    }
    reverse(s.begin(),s.end());
    OUT s<<endl
    return 0;
}

Measured memory_bytes: 3620
#include<bits/stdc++.h>
using namespace std;
#define itn int
#define rep(i,x,y) for(int i=x;i<y;i++)
#define range(a) a.begin(),a.end()
#define print(A,n) rep(i,0,n){cout<<(i ? " ":"")<<A[i];}cout<<endl;
#define pprint(A,m,n) rep(j,0,m){print(A[j],n);}
const long mod=1e9+7;
const int size=1e5;
const long INF=1e18;
int N;
long dp[400][400]={};long sum[401];
long recursive(int i,int j){
	if(dp[i][j]) return dp[i][j];
    if(i==j) return 0;
    long res=INF;
	rep(k,i,j){
		res=min(res,recursive(i,k)+recursive(k+1,j));
	}dp[i][j]=res+sum[j+1]-sum[i];
	return dp[i][j];
}
int main(){
	cin>>N;
    long A[N]={};long pro=0;sum[0]=0;
	rep(i,0,N){
        cin>>A[i];
        pro+=A[i];
        sum[i+1]=pro;
    }
	cout<<recursive(0,N-1)<<endl;
    //pprint(dp,N,N);
}

Measured memory_bytes: 1536
#include <bits/stdc++.h>
using namespace std;
int main()
{
  vector<int> v(5);
  for(int i=0;i<5;i++) cin >> v[i];
  int k;
  cin >> k;
  sort(v.begin(),v.end());
  if(v[4]-v[0] > k) cout << ":(" << endl;
  else cout << "Yay!" << endl;
}


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

template <class S>
void subset_zeta_transform(std::vector<typename S::value_type> &a) {
  using size_t = std::size_t;

  const size_t n = a.size();
  for (size_t i = 1; i < n; i *= 2) {
    for (size_t j = 0; j != n; j += 1) {
      if ((j & i) != 0)
        a[j] = S::operation(a[j & ~i], a[j]);
    }
  }
}

template <class S>
void superset_zeta_transform(std::vector<typename S::value_type> &a) {
  using size_t = std::size_t;

  const size_t n = a.size();
  for (size_t i = 1; i < n; i *= 2) {
    for (size_t j = 0; j != n; j += 1) {
      if ((j & i) != 0)
        a[j & ~i] = S::operation(a[j & ~i], a[j]);
    }
  }
}

template <class G>
void subset_mobius_transform(std::vector<typename G::value_type> &a) {
  using size_t = std::size_t;

  const size_t n = a.size();
  size_t i = 1;
  while (i < n)
    i *= 2;
  while (i != 1) {
    i /= 2;
    for (size_t j = 0; j != n; j += 1) {
      if ((j & i) != 0)
        a[j] = G::operation(G::inverse(a[j & ~i]), a[j]);
    }
  }
}

template <class G>
void superset_mobius_transform(std::vector<typename G::value_type> &a) {
  using size_t = std::size_t;

  const size_t n = a.size();
  size_t i = 1;
  while (i < n)
    i *= 2;
  while (i != 1) {
    i /= 2;
    for (size_t j = 0; j != n; j += 1) {
      if ((j & i) != 0)
        a[j & ~i] = G::operation(a[j & ~i], G::inverse(a[j]));
    }
  }
}

#include <algorithm>
#include <array>
#include <cstdio>
#include <functional>

int scan() {
  int r = 0, c;
  while ((c = getchar_unlocked() - '0') >= 0)
    r = r * 10 + c;
  return r;
}

struct top2 {
  using value_type = std::array<int, 2>;

  static value_type operation(const value_type &l, const value_type &r) {
    if (l[0] > r[0])
      return {l[0], std::max(l[1], r[0])};
    else
      return {r[0], std::max(l[0], r[1])};
  }
  static constexpr value_type identity = {0, 0};
};
constexpr typename top2::value_type top2::identity;

int main() {
  const int n = scan();
  std::vector<top2::value_type> a(1 << n);

  for (auto &e : a) {
    e[0] = scan();
  }

  subset_zeta_transform<top2>(a);
  int cur = 0;
  const int s = 1 << n;
  for (int i = 1; i != s; i += 1) {
    cur = std::max(cur, a[i][0] + a[i][1]);
    printf("%d\n", cur);
  }
  return 0;
}

Measured memory_bytes: 5120
#include <iostream>
#include <vector>
using namespace std;
int main()
{
    int n, d, d_sum = 0, d_sqs = 0;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> d;
        d_sum += d;
        d_sqs += d*d;
    }
    cout << (d_sum*d_sum - d_sqs) / 2 << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
int main(void){
   int N,K;
   cin>>N>>K;
   int A[N]; int count[N];
   for(int i=0;i<N;i++){
       cin>>A[i];
       count[i]=0;
   }
   for(int i=0;i<N;i++){
       count[A[i]-1]++;
   }
   sort(count,count+N);
   int sum=0;
   int diver=0;
   for(int i=N-1;i>=0;i--){
       sum+=count[i];
       diver++;
       if(diver>=K){break;}
   }
   cout<<N-sum;
   return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
#include <functional>
#include <ctime>
#include <cmath>
#include <limits>
#include <numeric>
#include <type_traits>
#include <iomanip>
using namespace std;
using ll = long long;

unsigned euclidean_gcd(unsigned a, unsigned b) {
    if (a < b) return euclidean_gcd(b, a);
    unsigned r;
    while ((r = a % b)) {
        a = b;
        b = r;
    }
    return b;
}

class UnionFind {
public:
    vector <ll> par;
    vector <ll> siz;
    UnionFind(ll sz_) : par(sz_), siz(sz_, 1LL) {
        for (ll i = 0; i < sz_; ++i) par[i] = i;
    }
    void init(ll sz_) {
        par.resize(sz_);
        siz.assign(sz_, 1LL);
        for (ll i = 0; i < sz_; ++i) par[i] = i;
    }
    ll root(ll x) {
        while (par[x] != x) {
            x = par[x] = par[par[x]];
        }
        return x;
    }
    bool merge(ll x, ll y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }

    bool issame(ll x, ll y) {
        return root(x) == root(y);
    }

    ll size(ll x) {
        return siz[root(x)];
    }
};

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

long long modinv(long long a, long long mod) {
    return modpow(a, mod - 2, mod);
}


int main() {
    ll m,k;
    cin >> m >> k;
    ll c = 1;
    for (int i = 0; i < m; i++) {
        c *= 2;
    }
    if (m == 1 && k == 0) {
        cout << "0 0 1 1" << endl;
    }
    else if (m == 1) {
        cout << -1 << endl;
    }
    else if (k >= c) {
        cout << -1 << endl;
    }
    else{
        cout << k;
        for (int i = 0; i < c; i++) {
            if (i != k)cout << " "<< i;
        }
        cout << " " << k;
        for (int i = c-1; i > -1; i--) {
            if (i != k)cout << " " << i;
        }
        cout << endl;
    }
}

Measured memory_bytes: 1792
<?php
  $input = explode(" ", fgets(STDIN));
$cont = $input[0];
$blk = $input[1];

for($i = $blk - ($cont -1); $i <= $blk + ($cont -1); $i++){
  if($i < $blk + ($cont -1)){
     echo $i." "; 
  }else{
      echo $i; 
  }
  
}

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

int main(){
  int N;
  cin >> N;
  vector<long long> A(N),B(N);
  for(int i=0; i<N; i++){
    cin >> A[i] >> B[i];
  }
  sort(A.begin(),A.end());
  sort(B.begin(),B.end());
  long long ans;
  if(N%2 == 1){
    ans = B[(N-1)/2] - A[(N-1)/2] + 1;
  }
  else{
    long long Bt = B[N/2 -1] + B[N/2];
    long long At = A[N/2 -1] + A[N/2];
    ans = Bt - At +1;
  }
  cout << ans;
  return 0;
}

Measured memory_bytes: 6428
N, K, Q = map(int, input().split())
A = list(map(int, input().split()))
D = set()
for i in range(N):
    D.add(A[i])

D = list(D)
ans = float('inf')
for Y in D:
    T = []
    tmp = []
    for j in range(N):
        if A[j] >= Y:
            tmp.append(A[j])
        else:
            if len(tmp) >= K:
                tmp = sorted(tmp)
                T += tmp[:len(tmp) - K + 1]
            tmp = []

    if len(tmp) >= K:
        tmp = sorted(tmp)
        T += tmp[:len(tmp) - K + 1]

    if len(T) >= Q:
        T = sorted(T)
        T = T[:Q]
        ans = min(ans, T[-1] - T[0])

print(ans)


Measured memory_bytes: 3316
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int a,b,c;
int main(void) 
{
	scanf("%d%d%d",&a,&b,&c);
	if(a==b&&a!=c)
	{
		printf("Yes\n");
		return 0;
	}
	if(a==c&&b!=c)
	{
		printf("Yes\n");
		return 0;
	}
	if(b==c&&a!=c)
	{
		printf("Yes\n");
		return 0;
	}
	printf("No\n");
    return 0;
}

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

const int MAXN = 1e5 + 7;
set<int> G[MAXN]; 
set<int> T[MAXN];

int main() {
    //ifstream cin("E.in");

    int n; cin >> n;

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

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

    queue<pair<int, int>> Q;
    set<pair<int, int>> seen;

    for(int i = 0; i < n; ++i)
        for(auto node : G[i])
            if(T[i].find(node) != T[i].end()) {
                auto edge = make_pair(min(node, i), max(node, i));
                if(seen.find(edge) == seen.end()) {
                    Q.push(edge);
                    seen.insert(edge);
                }
            }
    
    int many = 0;

    while(not Q.empty()) {
        auto edge = Q.front();
        Q.pop();

        int a = edge.first, b = edge.second;
            
        if(T[a].empty() or T[b].empty())
            continue;

        many++;
        vector<pair<int, int>> check;

        for(auto node : T[a]) {
            if(node != b) {
                T[b].insert(node);
                T[node].insert(b);
                T[node].erase(a);
                check.push_back(make_pair(min(b, node), max(b, node)));
            }
        }

        for(auto node : G[a]) {
            if(node != b) {
                G[b].insert(node);
                G[node].insert(b);
                G[node].erase(a);
                check.push_back(make_pair(min(b, node), max(b, node)));
            }
        }
        
        T[b].erase(a);
        G[b].erase(a);

        T[a].clear();
        G[a].clear();
        
        for(auto temp : check) {
            int x = temp.first;
            int y = temp.second;
            if(G[x].find(y) != G[x].end() and T[x].find(y) != T[x].end()) {
                if(seen.find(temp) == seen.end()) {
                    Q.push(temp);
                    seen.insert(temp);
                }
            }
        }
    }
        
    if(many == n - 1) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }    
}

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

int main(){
  ll a, b;
  cin >> a >> b;
  print(a * b / 2);
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<vector>
#include<string> 
#include<queue>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define ll long long
ll f(ll x){if(x==0) return 0;else return x%10+f(x/10);}
int main(){
    std::ios::sync_with_stdio(false);
    int k;cin>>k;
    int num=0;ll ans=1;ll p=1;
    while(num<k){
        cout<<ans<<endl;
        ll ans1=ans+p;
        ll ans2=ans+p*10;
        if(ans1*f(ans2)<=ans2*f(ans1)){ans=ans1;}
        else{ans=ans2;p*=10;}
        num++;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define pii pair<int,int>
const long long MOD=1000000007;

int main(){
    int n,m;
    cin>>n>>m;
    vector<string> A(n),B(m);
    rep(i,n) cin>>A[i];
    rep(i,m) cin>>B[i];
    
    rep(i,n-m+1) rep(j,n-m+1){
        bool temp=true;
        rep(k,m){
            string sub_ak=A[k+j].substr(i,m);
            //cout<<i<<" "<<j<<" "<<k<<":"<<sub_ak<<" "<<B[k]<<endl;
            if(sub_ak!=B[k]) temp=false;
        }
        if(temp){
            cout<<"Yes"<<endl;
            return 0;
        }
    }
    cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <iomanip>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <algorithm>
#include <climits>
using namespace std;

void solve(vector<int> a, vector<int> b)
{
	int difference = 0;
	for(unsigned i=0; i<a.size(); ++i)
		difference += a[i];
	for(unsigned i=0; i<b.size(); ++i)
		difference -= b[i];
	if(difference % 2 != 0){
		cout << -1 << endl;
		return;
	}

	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	for(unsigned i=0; i<a.size(); ++i){
		if(find(b.begin(), b.end(), a[i]-difference/2) != b.end()){
			cout << a[i] << ' ' << (a[i]-difference/2) << endl;
			return;
		}
	}
	cout << -1 << endl;
}

int main()
{
	for(;;){
		int n, m;
		cin >> n >> m;
		if(n == 0 && m == 0)
			break;

		vector<int> a(n);
		vector<int> b(m);
		for(int i=0; i<n; ++i)
			cin >> a[i];
		for(int i=0; i<m; ++i)
			cin >> b[i];

		solve(a, b);
	}
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
    #define int long long
    using namespace std;
     
    signed main() {
      int n;
      cin>>n;
      int k=1;
      for(int i=0;i<n;i++){
        k*=i+1;
        k%=1000000007;
      }
      cout<<k<<endl;
    }

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
      	String s=sc.next();
        if(s.equals("ABC")){
            System.out.println("ARC");
        }
        else{
            System.out.println("ABC");
        }

    }
}


Measured memory_bytes: 35676