akhauriyash/Code-Regression huggingface dataset:
H, W = map(int, input().split())
items = []
black = []
for i in range(H):
    tmp = list(input())
    for j in range(W):
        if tmp[j] == "#":
            black.append((i, j))
    items.append(tmp)

que = []
for b in black:
    que.append(b)

ans = 0
d4 = [(1, 0), (0, -1), (-1, 0), (0, 1)]
next_que = que
while len(que) != H * W:
    tmp = next_que
    next_que = []
    for b in list(tmp):
        x, y = b[0], b[1]
        for d in d4:
            dx = d[0]
            dy = d[1]
            if 0 <= x + dx <= H - 1 and 0 <= y + dy <= W - 1:
                tar = items[x + dx][y + dy]
                if tar == ".":
                    next_que.append((x + dx, y + dy))
                    que.append((x + dx, y + dy))
                    items[x + dx][y + dy] = "#"
    ans += 1
print(ans)


Measured memory_bytes: 165236
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const ll INF = 1LL << 60;

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

Measured memory_bytes: 256
# coding=utf-8
from math import floor, ceil, sqrt, factorial, log, gcd
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict
from heapq import heappop, heappush, heappushpop, heapify
import copy
import numpy as np
import sys
INF = float('inf')
mod = 10**9+7
sys.setrecursionlimit(10 ** 6)


def lcm(a, b): return a * b / gcd(a, b)

# 1 2 3
# a, b, c = LI()


def LI(): return list(map(int, sys.stdin.buffer.readline().split()))

# a = I()


def I(): return int(sys.stdin.buffer.readline())

# abc def
# a, b = LS()


def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

# a = S()


def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')

# 2
# 1
# 2
# [1, 2]


def IR(n): return [I() for i in range(n)]

# 2
# 1 2 3
# 4 5 6
# [[1,2,3], [4,5,6]]


def LIR(n): return [LI() for i in range(n)]

# 2
# abc
# def
# [abc, def]


def SR(n): return [S() for i in range(n)]

# 2
# abc def
# ghi jkl
# [[abc,def], [ghi,jkl]]


def LSR(n): return [LS() for i in range(n)]

# 2
# abcd
# efgh
# [[a,b,c,d], [e,f,g,h]]


def SRL(n): return [list(S()) for i in range(n)]


def main():
    n, m = LI()
    a = sorted(list(LI()))
    # 1. c以下をcに毎回置き換え.
    # for i in range(m):
    #     b, c = LI()
    #     for j in range(b):
    #         if a[j] > c:
    #             break
    #         heappushpop(a, c)
    # print(sum(a))

    # 2. 大きいcから入れていってbの累計がlen(a)になったら即終わり.
    # bc = LIR(m)
    # bc.sort(key=lambda x: x[1])
    # cnt = 0
    # for pair in bc:
    #     heappushpop(a, pair[1])
    #     cnt += pair[0]
    #     if cnt > len(a):
    #         break
    # print(sum(a))

    bc = LIR(m)
    bc.sort(key=lambda x: x[1], reverse=True)
    d = []
    i = 0
    while len(d) < n and i < len(bc):
        if bc[i][0] + len(d) < n:
            d.extend([bc[i][1]] * bc[i][0])
        else:
            d.extend([bc[i][1]] * (n - len(d)))
            break
        i += 1
    for i in range(len(d)):
        if d[i] < a[i]:
            break
        a[i] = d[i]
    print(sum(a))


if __name__ == "__main__":
    main()


Measured memory_bytes: 50860
import sys

input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))

cnt = [0] * N

for a in A:
    cnt[a - 1] += 1

combination = [0] * N

for a in A:
    combination[a - 1] = cnt[a - 1] * (cnt[a - 1] - 1) // 2

total = sum(combination)

for a in A:
    c = combination[a - 1]
    b = cnt[a - 1]
    ans = total - c + c * (b - 2) // b
    print(ans)


Measured memory_bytes: 25696
#include <iostream>
#include <algorithm>
#include <vector>
#include <climits>
using namespace std;

static const int MAX = 100;
static const long long INFTY = (1LL<<32);

int n;
long long d[MAX][MAX];

void floyd()
{
    for(int k=0; k<n; k++)
    {
        for(int i=0; i<n; i++)
        {
            if(d[i][k] == INFTY) continue;
            for(int j=0; j<n; j++)
            {
                if(d[k][j] == INFTY) continue;
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
}

int main()
{
    int e, u, v, c;
    cin >> n >> e;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++) d[i][j] = ((i==j)?0:INFTY);
    }
    for(int i=0; i<e; i++)
    {
        cin >> u >> v >> c;
        d[u][v] = c;
    }
    floyd();
    bool negative = false;
    for(int i=0; i<n; i++) if(d[i][i]<0) negative = true;

    if(negative) cout << "NEGATIVE CYCLE" << endl;
    else
    {
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<n; j++)
            {
                if(j) cout << " ";
                if(d[i][j] == INFTY) cout << "INF";
                else cout << d[i][j];
            }
            cout << endl;
        }
    }
    return 0;
}



Measured memory_bytes: 3180
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll INF = 100000000;
#define rep1(i, n) for (ll i=0; i<(n); i++) 
#define rep2(i, k, n) for (ll i=k; i<(n); i++)
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 n, m;
    cin >> n >> m;
    ll ans = 0;
    ans += min(n, m/2);
    n -= ans;
    m -= ans * 2;
    ans += m / 4;
    cout << ans << endl;
    //printf("%.12f", ans);
}

Measured memory_bytes: 3628
a, b = list(map(int, input().split()))

ans = -1 # 答えが見つからなかった場合の-1を初期値にしておく

for price in range(10000):
    tax_a = int(price * 0.08)
    tax_b = int(price * 0.1)
    if tax_a == a and tax_b == b:
        ans = price
        break

print(ans)

Measured memory_bytes: 3064
#!/usr/bin/env python3
import sys

import math


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

def solve(N: int):
    from functools import reduce
    from operator import mul

    a = prime_factorize(N)
    a.sort(reverse=True)
    if(len(a)==1):
        print(len(str(a[0])))
        exit()

    # bit all search
    ans = 100000000
    for i in range(1<<len(a)):
        x = 1
        y = 1
        for j in range(len(a)):
            if((i >> j)&1):
                x *= a[j]
            else:
                y *= a[j]

        ans = min(ans, max(len(str(x)), len(str(y))))


    print(ans)
    


    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()


Measured memory_bytes: 41324
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>
#include <numeric>
#include <iomanip>

#define SPBR(w, n) std::cout<<(w + 1 == n ? '\n' : ' ');
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define ALL(i) (i).begin(), (i).end()
#define FOR(i, a, n) for(int i=(a);i<(n);++i)
#define RFOR(i, a, n) for(int i=(n)-1;i>=(a);--i)
#define REP(i, n) for(int i=0;i<int(n);++i)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define IN(a, x, b) (a<=x && x<b)
#define OUT(a, x, b) (x<a || b<=x)
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; }

#define int ll
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int MOD = 1000000007;
/* const int MOD = 998244353; */
const int INF = 1e18;
const double PI = acos(-1);

using namespace std;
struct INIT { INIT(){
  cin.tie(0); ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
}}INIT;


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

  int a = 1000;
  for(int i = 1; ; i++){
    if(N <= a*i){
      cout << a*i-N << "\n";
      return 0;
    }
  }

  return 0;
}


Measured memory_bytes: 3636
import java.util.*;

public class Main {
    public static void main(String[] arg) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int Z = scanner.nextInt();
        int W = scanner.nextInt();
        int[] a = new int[N + 2];
        a[0] = Z;
        a[1] = W;
        for (int i = 0; i < N; i++) {
            a[2 + i] = scanner.nextInt();
        }
        System.out.println(solve(a, 0, 1));
    }

    final static int MAX_N = 2048;

    static Integer[][] memo = new Integer[MAX_N][MAX_N];

    /**
     * それぞれ z 枚目, w 枚目を持っている局面での最適解。
     */
    static int solve(int[] a, int z, int w) {
        int n = Math.max(z, w) + 1;  // 取り終わっている枚数
        if (n == a.length) return Math.abs(a[z] - a[w]);

        // memoization
        if (memo[z][w] != null) return memo[z][w];

        // 差が何枚でも1枚差と結果は同じ
        if (Math.abs(z - w) > 1) {
            return z < w ? solve(a, w - 1, w) : solve(a, z, z - 1);
        }

        int m = z < w ? 0 : Integer.MAX_VALUE;
        int zz = z;
        int ww = w;
        for (int i = n; i < a.length; i++) {
            if (z < w) { zz = i; }
            else       { ww = i; }
            int mx = solve(a, zz, ww);
            m = z < w ? Math.max(m, mx) : Math.min(m, mx);
        }
        memo[z][w] = m;
        return m;
    }
}


Measured memory_bytes: 57492
#include<bits/stdc++.h>
using namespace std;
void sati(char t[12][12],int p,int q){
	t[p][q]='0';
	//for(int p=0;p<12;p++){
	//	for(int q=0;q<12;q++){
	//		cout<<t[p][q];
	//	}
	//	cout<<""<<endl;
	//}
	//cout<<""<<endl;
	if(p>0&&t[p-1][q]=='1'){//上
		sati(t,p-1,q);
	}
	if(p<11&&t[p+1][q]=='1'){//下
		sati(t,p+1,q);
	}
	if(q>0&&t[p][q-1]=='1'){//左
		sati(t,p,q-1);
	}
	if(q<11&&t[p][q+1]=='1'){//右
		sati(t,p,q+1);
	}
	return;
}

int ans(char t[12][12]){
	int a=0;
	for(int p=0;p<12;p++){
		for(int q=0;q<12;q++){
			if(t[p][q]=='1'){
				a++;
				//cout<<a<<endl;
				sati(t,p,q);
			}
		}
	}
	return a;
}
				
int main(){
	while(true){
		int n=12;
		char t[12][12]={};
		for(int p=0;p<n;p++){
			for(int q=0;q<n;q++){
				//cout<<p<<" "<<q<<endl;
				if(!(cin>>t[p][q])){
					return 0;
				}
			}
		}
		cout<<ans(t)<<endl;
		//for(int p=0;p<n;p++){
		//	for(int q=0;q<n;q++){
		//		cout<<t[p][q];
		//	}
		//	cout<<""<<endl;
		//}
	}
}
			


Measured memory_bytes: 3100
#include <bits/stdc++.h>
#include <math.h>
#define ALL(a)    a.begin(), a.end() 
#define rep(i, K, N)  for(long long int i = K; i < N; i++)
#define ll long long int
using namespace std;

int main(){
ll A, B, C, K;cin >> A >> B >> C >> K;
ll Ans = 0, i = 1, j = 1;
  
while(A >= B*pow(2, i - 1)){Ans++;i++;}
B*=pow(2, i - 1);
  
while(B >= C*pow(2, j - 1)){Ans++;j++;}
  
if(Ans <= K)cout <<"Yes";

else cout << "No";
  
 



}

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

const int N_max = 2e5;
vector<int> sub(N_max);
int N;


int main(){
    cin >> N;
    sub.resize(N);
    int s;
    for(int i=1; i!=N; i++){
        cin >> s;
        sub.at(s-1)++;
    }
    for(const auto s: sub) cout << s << endl;

    return 0;
}

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

int main(){
  int X;
  cin >> X;
  
  if(X < 100){
    cout << "0" << endl;
    return 0;
  }
  //した3桁だけ見ればあとは100で調整できる。
  int a = X % 1000; //3けただけ抽出
  int N = X /100;//100の位以上の数が選べる数
  int b = a % 100; //しも2桁
  int count = 0;
  while(b){ //ｂがゼロになるまで
    if(b-5 >= 0)b-=5;
    else if(b-4 == 0)b-=4;
    else if(b-3 == 0)b-=3;
    else if(b-2 == 0)b-=2;
    else if(b-1 == 0)b-=1;
    count++;
  }
  if(count <= N)cout << 1 << endl;
  else cout << 0 << endl;
}

Measured memory_bytes: 256
package main

import "os"
import "fmt"
import "bufio"

func main() {
    var sc = bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    sc.Scan()
    s := sc.Text()
    n := 0
    for i := 0; i < len(s); i++ {
        if s[i:i + 1] == "+" {
            n++
        } else {
            n--
        }
    }
    fmt.Printf("%d\n", n)
}


Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#include <unordered_map>
#include <iomanip>
#include <functional>
#include <bitset>
#include <complex>
#include <stack>
#include <cstdint>



#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define rrep(i, n) for(ll i = (ll)(n-1); i >= 0; i--)
#define repi(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rrepi(i,a,b) for(ll i=(ll)(b);i>=(ll)(a);i--)

#define all(x) (x).begin(),(x).end()

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

typedef long long ll;

using namespace std;


int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n;cin>>n;
  struct ab{ll a,b;};
  vector<ab>dish(n);
  rep(i,n)cin>>dish[i].a>>dish[i].b;
  sort(all(dish),[](ab x,ab y){return x.a+x.b>y.a+y.b;});
  ll res=0;
  rep(i,n){
    if(i%2==0)res+=dish[i].a;
    else res-=dish[i].b;
  }
  cout<<res<<endl;

  return 0;

}


Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <stack>
#include <queue>
#include <math.h>
#include <string>
#include <numeric>
#include <algorithm>
#include <utility>

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


// 68 11 55 - rank 3
// 69 12 19 - rank 3
// 70 12 34 - rank 100
// 71 12 58 - rank 4
// 72 13 24

ull gcd(ull a, ull b) {
    while (b != 0) {
        auto na = a % b;
        a = b;
        b = na;
    }
    return a;
}


void oneCase() {
    int n;
    cin >> n;
    vector<int> p(n);
    for (auto& el : p) {
        cin >> el;
        --el;
    }
    int cnt = 0;
    int i = 0;
    while (i < n) {
        int cur = 0;
        while (i < n && p[i] == i) {
            ++i;
            ++cur;
        }
        cnt += cur / 2 + cur % 2;

        ++i;
    }

    cout << cnt << '\n';
}


int main() {
    int t = 1;
//    cin >> t;
    while (t--) {
       oneCase();
    }

    return 0;
}

ll fact(ll n, ll mod) {
    ll res = 1;
    while (n > 0) {
        res = (res * n) % mod;
        --n;
    }
    return res;
}


Measured memory_bytes: 640
in_data=input()

in_list=[]

in_list=in_data.split(" ")

in_list[0]=int(in_list[0])
in_list[1]=int(in_list[1])
in_list[2]=int(in_list[2])


if in_list[0]<=in_list[1] and in_list[1]<=in_list[2] :

    print(str(in_list[0])+" "+str(in_list[1])+" "+str(in_list[2]))

elif in_list[0]<=in_list[1] and in_list[2]<=in_list[1]:
    
    print(str(in_list[0])+" "+str(in_list[2])+" "+str(in_list[1]))
    
elif in_list[1]<=in_list[0] and in_list[0]<=in_list[2]:
    print(str(in_list[1])+" "+str(in_list[0])+" "+str(in_list[2]))

elif in_list[1]<=in_list[2] and in_list[2]<=in_list[0]:
    print(str(in_list[1])+" "+str(in_list[2])+" "+str(in_list[0]))

elif in_list[2]<=in_list[0] and in_list[0]<=in_list[1]:
    
    print(str(in_list[2])+" "+str(in_list[0])+" "+str(in_list[1]))

elif in_list[2]<=in_list[1] and in_list[1]<=in_list[0]:
    
    print(str(in_list[2])+" "+str(in_list[1])+" "+str(in_list[0]))


Measured memory_bytes: 5608
# coding: utf-8


def solve(*args: str) -> str:
    n = int(args[0])
    k = int(args[1])

    N = list(map(int, '0' + str(n)))
    d = len(str(n))
    F = [[0]*(k+1) for _ in range(d+1)]
    U = [[0]*(k+1) for _ in range(d+1)]

    U[0][0] = 1
    for i in range(1, d+1):
        for j in range(1, k+1):
            if 0 < N[i]:
                F[i][j-1] += F[i-1][j-1] + U[i-1][j-1]
                U[i][j] += U[i-1][j-1]
            else:
                F[i][j-1] += F[i-1][j-1]
                U[i][j-1] += U[i-1][j-1]
            F[i][j] += max(0, N[i]-1)*U[i-1][j-1] + 9*F[i-1][j-1]
    return str(sum([x[k] for x in F])+sum([x[k] for x in U]))


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


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

int main(void)
{
	int n,h,m,s;
	scanf("%d", &n);
	h = n/3600;
	m = n%3600/60;
	s = n%60;
	printf("%d:%d:%d\n", h, m, s);
	
	return 0;
}


Measured memory_bytes: 2752
#include<bits/stdc++.h>
#define ll long long int

using namespace std;

const ll mod=1000000007;
const ll inf=1e18;

ll sousa(ll p){
  if(p==0)return p;

  ll c=0;
  while(p!=0){
    ll q=__builtin_popcountll(p);
    p=p%q;
    c++;
  }
  return c;
}


int main(){

  ll n;
  string x;
  cin >> n >> x;



  ll a=0;//popcount(x)
  for(int i=0;i<n;i++)if(x[i]=='1')a++;

  if(a==0){
    for(int j=0;j<n;j++)cout << 1 << endl;
    return 0;
  }
  if(a==1){
    if(x[n-1]=='1'){
      for(int j=0;j<n-1;j++)cout << 2 << endl;
      cout << 0 << endl;
    }
    else{
      for(int j=0;j<n;j++){
        if(x[j]=='1')cout << 0 << endl;
        else if(j==n-1)cout << 2 << endl;
        else cout << 1 << endl;
      }
    }
    return 0;
  }


  ll v1[n],v2[n],v3[n];//popcount=a-1,a,a+1についての2^iをpopcountで割ったあまり
  v1[n-1]=1%(a-1);
  v2[n-1]=1%(a);
  v3[n-1]=1%(a+1);
  
  for(int i=n-2;i>=0;i--){
    v1[i]=(v1[i+1]*2)%(a-1);
    v2[i]=(v2[i+1]*2)%(a);
    v3[i]=(v3[i+1]*2)%(a+1);    
  }
  ll b=0,c=0,d=0;//popcount=a-1,a,a+1についてのxをpopcountで割ったあまり
  for(int i=0;i<n;i++){
    if(x[i]=='1'){
      b=(b+v1[i])%(a-1);
      c=(c+v2[i])%(a);
      d=(d+v3[i])%(a+1);
    }
  }


  for(int i=0;i<n;i++){
    if(x[i]=='1'){
      ll e=b;
      e-=v1[i];
      e%=(a-1);
      e+=(a-1);
      e%=(a-1);
      ll r=sousa(e)+1;
      cout << r << endl;
    }
    else{
      ll e=d;
      e+=v3[i];
      e%=(a+1);
      ll r=sousa(e)+1;
      cout << r << endl;
    }
  }


}

Measured memory_bytes: 8384
s = input()
is_yy = lambda x: 0 <= int(x) <= 99
is_mm = lambda x: 1 <= int(x) <= 12

yymm = False
mmyy = False

a = is_yy(s[:2])
b = is_mm(s[2:])

if a and b:
    yymm = True

a = is_mm(s[:2])
b = is_yy(s[2:])

if a and b:
    mmyy = True

if yymm and mmyy:
    print('AMBIGUOUS')
elif yymm:
    print('YYMM')
elif mmyy:
    print('MMYY')
else:
    print('NA')


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

using namespace std;
typedef long long ll;

inline int at(ll x, int k){ return (x >> k) & 1; }
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define rrep(i,a,b) for(ll i=a;i>=b;i--)


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

	ll bb;
	if(n>=b){
		bb=b-1;
	}else{
		bb = n;
	}
	ll ans;
	ans = floor(a*bb/b);

	cout << ans << endl;

}


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

using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using vvl = vector<vector<ll>>;

double eps = 0.00001;
using p2 = complex<double>;

double det(p2 v1, p2 v2) {
  return v1.real() * v2.imag() - v1.imag() * v2.real();
}

double dot(p2 v1, p2 v2) {
  return v1.real() * v2.real() + v1.imag() * v2.imag();
}

bool same(double x, double y) { return fabs(x - y) < eps; }

double dist2(p2 l1, p2 l2) { return dot(l1 - l2, l1 - l2); }

struct Line {
  p2 st, ed;
  Line(p2 st, p2 ed) : st(st), ed(ed) {}
  double dist() { return sqrt(dist2(st, ed)); }
  double isPalla(Line l) { return fabs(det(ed - st, l.ed - l.st)) < eps; }
  double x() { return ed.real() - st.real(); }
  double y() { return ed.imag() - st.imag(); }
};

struct Circle {
  p2 p;
  double r;
  int col;
  Circle(p2 p, double r, int col) : p(p), r(r), col(col) {}
  bool include(p2 l) { return dist2(p, l) < r * r + eps; }
  bool include(Circle c) { return sqrt(dist2(p, c.p)) < r + c.r - eps; }
};

vector<Circle> cs;
int ans = 0;
int n;
bool vis[1LL << 24] = {0};

void dfs(ll bit) {
  if (vis[bit])
    return;
  vis[bit] = true;
  int c = 0;
  vector<bool> used(n), ok(n);
  for (int i = 0; i < n; i++) {
    used[i] = (bit & (1LL << i)) > 0;
    ok[i] = !used[i];
    if (used[i])
      c++;
  }
  ans = max(ans, c);
  for (int i = 0; i < n; i++) {
    if (used[i])
      continue;
    for (int j = 0; j < i; j++) {
      if (!used[j] && cs[i].include(cs[j])) {
        ok[i] = false;
      }
    }
  }
  for (int i = 0; i < n; i++) {
    if (!ok[i])
      continue;
    for (int j = i + 1; j < n; j++) {
      if (!ok[j] || cs[i].col != cs[j].col)
        continue;
      dfs(bit ^ (1LL << i) ^ (1LL << j));
    }
  }
}

int main() {
  while (true) {
    cin >> n;
    if (n == 0)
      break;
    cs.clear();
    ans = 0;
    for (int i = 0; i < (1LL << n); i++)
      vis[i] = false;
    for (int i = 0; i < n; i++) {
      double x, y, r;
      int c;
      cin >> x >> y >> r >> c;
      cs.emplace_back(p2(x, y), r, c);
    }
    dfs(0LL);
    cout << ans << endl;
  }
  return 0;
}


Measured memory_bytes: 19580
#include <stdio.h>

int main(void){
    double EPS = 0.0000000001;
    double xa, ya, xb, yb, xc, yc, xd, yd;
    while( scanf("%lf %lf %lf %lf %lf %lf %lf %lf",
                  &xa, &ya, &xb, &yb, &xc, &yc, &xd, &yd) != EOF ){
        double prod = (xb-xa)*(xd-xc)+(yb-ya)*(yd-yc);
        if( prod < EPS && prod > -EPS ){
            puts("YES");
        }else{
            puts("NO");
        }
    }
    return 0;
}

Measured memory_bytes: 612
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		Map<String, Long> map = new HashMap<>();
		long cnt = 0;
		for ( int i = 0; i < n; i++ ) {
			char[] s = in.next().toCharArray();
			Arrays.sort(s);
			String key = new String(s);
			Long value = (map.containsKey(key) ? map.get(key) + 1 : 1);
			map.put(key, value);
			//			if ( map.containsKey(key) ) {
			//				// cnt += map.get(key);
			//				map.put(key, map.get(key) + 1);
			//			} else {
			//				map.put(key, (long) 1);
			//			}
		}

		for ( Entry<String, Long> en : map.entrySet() ) {
			Long v = en.getValue();
			cnt += v * (v - 1) / 2;
		}

		System.out.println(cnt);
		in.close();
	}
}

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

using namespace std;


typedef pair <long long ,long long>	PII;
typedef vector <int>	VI;
typedef vector <PII>    VII;
typedef priority_queue<PII,vector<PII>,greater<PII>> pairMinHeap;
typedef priority_queue<PII> pairMaxHeap;
typedef priority_queue<long long ,vector<long long>,greater<long long>> minHeap;
typedef priority_queue<long long> maxHeap;

#define what_is(x) cerr <<#x<<" is "<<x<<endl;
#define wis(x,y) cerr <<#x<<" is "<<x<<" and "<<#y<<" is "<<y<<endl;
#define getarr(n,d) for(int i=0;i<n;i++)cin>>d[i];
#define getgraph(n,g) for(int i=1;i<n;i++){int a,b;cin>>a>>b;a--;b--;g[a].push_back(b);g[b].push_back(a);}
#define getpartree(n,tree) for(int i=1;i<n;i++){int a;cin>>a;tree[a-1].push_back(i);}

struct POS{
    int x=0,y=0;
    POS():x(0),y(0){}
    POS(int _x,int _y):x(_x),y(_y){}
};

struct triple{
    int f,s,t;
    triple():f(0),s(0),t(0){}
    triple(int _f,int _s,int _t):f(_f),s(_s),t(_t){}
};

const int INF = 1e9+9;
const long long LINF = 1e17+9;
const long long MD=998244353 ;

inline long long po(long long a,long long b){
    long long ans=1;
    while(b>0){
        if(b&1)ans = (ans*a)%MD;
        a = (a*a)%MD;
        b/=2;
    }
    return ans;
}


const int N=2e5+33;

long long n,m,k,t;
long long arr[N];
string s;


int main() {
	ios_base::sync_with_stdio(false);cout.tie(nullptr);cin.tie(nullptr);cout << fixed;cout << setprecision(10);
    cin>>n;
    cin>>m>>k;
    getarr(n,arr)
    sort(arr,arr+n);
    int f=0,s=0,tr=0;
    for(int i=0;i<n;i++){
        if(arr[i]<=m)f++;
        else if(arr[i]<=k)s++;
        else tr++;
    }

    int ans=min(min(f,s),tr);
    //wis(f,s)
    cout<<ans;
    return 0;
}


Measured memory_bytes: 256
n,k=map(int,input().split())
a=list(map(int,input().split()))
d={}
ans=0
for i in range(n):
  if a[i] in d: d[a[i]]+=1
  else: d[a[i]]=1
dd = sorted(d.values(), reverse = True)
if len(dd)<=k:
  print(0)
else:
  ans=n
  for i in range(k):
    ans -= dd[i]
  print(ans)

Measured memory_bytes: 120180
#include <iostream>
#include <vector>
using namespace std;
typedef vector<string> vs;

int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};

vs dfs(vs map, int nx, int ny) {
	map[nx][ny] = '0';
	for (int i=0; i<4; i++) {
		if (nx+dx[i]>=0&&nx+dx[i]<12&&
				ny+dy[i]>=0&&ny+dy[i]<12&&map[nx+dx[i]][ny+dy[i]]=='1') {
			map = dfs(map, nx+dx[i], ny+dy[i]);
		}
	}
	return map;
}

int main() {
	vs map;
	string buff;
	while (cin >> buff) {
		map.push_back(buff);
		for (int i=0; i<11; i++) {
			cin >> buff;
			map.push_back(buff);
		}
		int res = 0;
		for (int i=0; i<12; i++) {
			for (int j=0; j<12; j++) {
				if (map[i][j] == '1') {
					res++;
					map = dfs(map, i, j);
				}
			}
		}
		cout << res << endl;
		map.clear();
	}
}

Measured memory_bytes: 0
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,k,a,s[100002],t[100002],r,l,m,tot,cnt,L,CNT,TOT;
vector<ll> v;
int main(void){
    ll n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>a;
        s[a]++;
        t[a]++;
        v.push_back(a);
    }
    sort(v.begin(),v.end());
    for(ll i=100000;i>=1;i--){
        t[i]*=i;
    }
    for(int i=100001;i>=1;i--){
        s[i-1]+=s[i];
        t[i-1]+=t[i];
    }
    l=-1;
    r=200001;
    while(r-l>1){
        m=(r+l)/2;
        tot=0;
        cnt=0;
        for(int i=0;i<v.size();i++){
            L=m-v[i];
            L=max(0LL,L);
            if(L<=100000&&s[L]>0){
                cnt+=t[L]+v[i]*s[L];
                tot+=s[L];
            }
        }
        if(tot>=k){l=m;CNT=cnt;TOT=tot;}
        else r=m;
    }
    cout<<CNT-l*(TOT-k)<<endl;
}


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

using namespace std;

int main(){
	int n, m, l;
	cin >> n;
	cin >> m;
	cin >> l;

	vector<vector<int>> A(n, vector<int>(m));
	vector<vector<int>> B(m, vector<int>(l));
	vector<vector<long long>> C(n, vector<long long>(l, 0));

	for(auto&& i : A){
		for(auto&& j : i){
			cin >> j;
		}
	}
	for(auto&& i : B) {
		for(auto&& j : i) {
			cin >> j;
		}
	}

	for(int i = 0; i < n; ++i){
		for(int j = 0; j < l; ++j){
			for(int k = 0; k < m; ++k){
				C[i][j] += A[i][k] * B[k][j];
			}
		}
	}

	for(auto&& e : C){
		for(int i = 0; i < l; ++i){
			cout << e[i];
			if(i < l - 1) { cout << " "; }
		}
		cout << endl;
	}
	
	return 0;
}


Measured memory_bytes: 3180
import java.util.Scanner;

public class Main{
    public static int[][] land;
    public static int W,H; 
    public static void main(String arg[]){
        Scanner sc=new Scanner(System.in);
        while(true){
            W=sc.nextInt();
            H=sc.nextInt();
            if(W==0 && H==0)break;
            land=new int[H][W];
            for(int i=0;i<H;i++){
                for(int j=0;j<W;j++)land[i][j]=sc.nextInt();
            }   
            int count=0;
            for(int i=0;i<H;i++){
                for(int j=0;j<W;j++){
                    if(land[i][j]==0)continue;
                    dfs(i,j);
                    count++;
                }
            }   
            System.out.println(count);
        }
        sc.close();
    }
    public static void dfs(int h,int w){
        int dh,dw,nh,nw;
        //数え済み
        land[h][w]=0;
        // 八方向を探索
        for(dh=-1;dh<=1;dh++){
            for(dw=-1;dw<=1;dw++){
                nh=h+dh;
                nw=w+dw;
                // 場外
                if( nh<0 || nh >= H || nw < 0 || nw >= W )continue;
                // 海
                if(land[nh][nw]==0)continue;
                // 再帰的に探索
                dfs(nh, nw);
            }
        }
    }
}


Measured memory_bytes: 45212
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i,a,b) for(int i=(a); i<=(b); i++) 
#define rep(i,n) for(int i = 0; i < (n); i++)
#define chmin(a,b) if((a)>(b)) (a)=(b); 
#define chmax(a,b) if((a)<(b)) (a)=(b);
#define vi vector<int>
#define pi pair<int,int>
#define all(v) (v).begin(),(v).end()
#define allr(v) (v).rbegin(),(v).rend()
#define pb push_back
#define pf push_front
int gcd(int a,int b){/*a>=0,b>=0,￢(a=b=0)*/
  while(min(a,b)>0){if(a<b)swap(a,b);a%=b;}return max(a,b);
}
int dx[]={0,1,0,-1,1,-1,-1,1};
int dy[]={1,0,-1,0,1,1,-1,-1};
const int MOD = 2019;
const int INF = 1e18+10;

/*----------------------------------------------*/
int modpow(int x,int n){
  int res=1;
  while(n>0){
    if(n&1) res=(res*x)%MOD;
    x=(x*x)%MOD;
    n>>=1;
  }
  return res;
}


signed main(){
  string s;
  cin>>s;
  int n=s.size();
  vi t(n+3,0);
  rep(i,n){
    t[n-1-i]=(t[n-i]+(s[n-1-i]-'0')*modpow(10,i))%2019;
  }
  vi cnt(2019,0);
  rep(i,n+1){
    cnt[t[i]]++;
    // if(cnt[t[i]]>1) cout<<i<<endl;
  }
  int ans=0;
  rep(i,2019){
    ans+=cnt[i]*(cnt[i]-1)/2;
    // if(cnt[i])cout<<cnt[i]<<endl;
  }
  // cout<<endl;
  cout<<ans<<endl;
  // rep(i,n) cout<<t[i]<<endl;

  return 0;
}


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

int main(){
  long long int n,a,b;
  cin >> n >> a >> b;
  if((b-a)%2==0){
    cout << (b-a)/2 << endl;
  }else if((n-a)>=(b-1)){
    cout << (a+b-1)/2 << endl;
  }else{
    cout << (2*n-a-b+1)/2 << endl;
  }
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		 Scanner scan = new Scanner(System.in);
		 
		 int n = scan.nextInt();
		 int a = scan.nextInt();
		 int b = scan.nextInt();
		 
		 int fee = n*a;
		 
		 if(fee > b) {
			 fee = b;
		 }
		 
		 System.out.print(fee);

	}

}

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

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> ii;
typedef tuple<ll, ll, ll> iii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define REP(i,n) for (ll i = 0; i < n; ++i)
#define REPR(i,n) for (ll i = n-1; i >= 0; --i)
#define FOR(i,m,n) for (int i = m; i < n; ++i)
#define FORR(i,m,n) for (ll i = n-1; i >= m; --i)
#define FORE(x,xs) for (const auto& x : xs)
#define PB push_back
#define MP make_pair
#define MT make_tuple
#define ALL(v) v.begin(), v.end()
#define rALL(v) v.rbegin(), v.rend()

const int MAX = 111;

int N;
vector<pair<double, double>> vec;

ld solve() {
    vector<tuple<ld, ll, ll>> order;
    REP (i, N) order.PB(MT(atan2(vec[i].first, vec[i].second), vec[i].first, vec[i].second));
    sort(ALL(order));
    ll res = 0;
    REP (left, N) {
        ll x = 0, y = 0;
        FOR (right, left, left+N) {
            x += get<1>(order[right%N]);
            y += get<2>(order[right%N]);
            res = max(res, x*x + y*y);
        }
    }
    return sqrt(res);
}

int main() {
    cin >> N;
    REP (i, N) {
        int x, y; cin >> x >> y;
        vec.PB(MP(x, y));
    }
    cout << setprecision(15) << solve() << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <algorithm>
#include <vector>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;

int asc(const void* a, const void* b) {
	return *(int*)b - *(int*)a;
}

int main()
{
	int n;
	cin >> n;
	int ans = 0;
	int nud = 0;
	for (int i = 1; i <= n; i += 2) {
		for (int j = 1; j <= i; j++) {
			if (i % j == 0) {
				nud++;
			}
		}
		if (nud == 8) {
			ans++;
		}
		nud = 0;
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define CYES cout<<"Yes"<<"\n";
#define CNO cout<<"No"<<"\n";
#define CFS cin.tie(nullptr);ios::sync_with_stdio(false);
#define CST(x) cout<<fixed<<setprecision(x);
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <class T>
using MaxHeap = priority_queue<T>;
template <class T>
using MinHeap = priority_queue<T, vector<T>, greater<T>>;
const int IINF = 1 << 30;
const ll LINF = 1LL << 60;
const int MOD = (int) 1e9 + 7;
const string MM = " ";

int main(){
    int a, b, c;
    cin >> a >> b >> c;
    if (a == b && b != c) {
        cout << "Yes" << "\n";
        return 0;
    } else if (b == c && c != a) {
        cout << "Yes" << "\n";
        return 0;
    } else if (c == a && a != b) {
        cout << "Yes" << "\n";
        return 0;
    } else {
        cout << "No" << "\n";
        return 0;
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <functional>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <queue>
#include <map>
#include <iomanip>
#include <complex>
#include <random>
#include <bitset>
#include <list>
// #include <prettyprint.hpp>
using namespace std;
#define repi(i,n) for(int i=0;i<n;++i)
#define rep(i,n) for(ll i=0;i<n;++i)
#define repinvi(i,n) for(int i=n-1;i>=0;--i)
#define sll(n) scanf("%lld", &n);
#define sii(n) scanf("%d", &n);
#define slf(n) scanf("%lf", &n);
#define pll pair<ll,ll>
#define pii pair<int,int>
#define psi pair<si,si>
typedef long long ll;
typedef double lf;
typedef short int si;

vector<vector<ll>> field(3, vector<ll>(3, 0));
vector<ll> coord1 = {0, 4, 8};
vector<ll> coord2 = {2, 4, 6};
void Main(){
    ll N;
    sll(N);
    string s;
    map<string, ll> as;
    rep(i, N){
        cin >> s;
        as[s] ++;
    }

    cout << "AC x " << as["AC"] <<endl;
    cout << "WA x " << as["WA"] <<endl;
    cout << "TLE x " << as["TLE"] <<endl;
    cout << "RE x " << as["RE"] <<endl;

}

int main(){
    Main();
}

Measured memory_bytes: 3292
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for(int i=0;i<n;i++)
typedef long long ll;
#define MOD 1000000007

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

const ll INF = 1LL << 60;


int main(){
  ll n;
  cin >> n;
  string s;
  cin >> s;
  ll d[1000000];
  d[0]=0;
  ll w=0,e=0;
  for(int i=1;i<n+1;i++){
    if(s[i-1]=='W'){
      d[i]=d[i-1]+1;
      w++;
    }else{
      d[i]=d[i-1];
      e++;
    }
  }
  ll ans=INF;
  FOR(i,n){
    chmin(ans,d[i]+(n-i-1-(w-d[i+1])));
  }

  cout << ans << endl;
}


Measured memory_bytes: 4996
import sys
l= input()
a=len(l)
b=(-1,-1)
for i in range(a-1):
  if l[i]==l[i+1]:
    print(i+1,i+2)
    sys.exit()
for i in range(a-2):
  if l[i]==l[i+2]:
    print(i+1,i+3)
    sys.exit()
print(-1,-1)
sys.exit()

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

typedef long long ll;

const int INF = 1e9;

const int MAXN = 100010;
int N, K;
int X[MAXN];

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> N >> K;
	for (int i = 0; i < N; i++) cin >> X[i];
	int ans = INF;
	for (int i = 0; i + K - 1 < N; i++) {
		int l = X[i];
		int r = X[i+K-1];
		if (ll(l) * r >= 0) {
			ans = min(ans, max(abs(l), abs(r)));
		} else {
			ans = min(ans, min(2 * r - l, r - 2 * l));
		}
	}
	cout << ans << endl;

	return 0;
}


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

typedef long long ll;

int main()
{
    int i,j;
    string s;
    s = "1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51";
    vector<int> a;
    vector<char> t;
    for(i = 0;i < s.size();++i){
        if(s.at(i) == ',' || s.at(i) == ' '){
            if(t.size() == 0){
                continue;
            }else{
                if(t.size() == 1){
                    a.push_back((int)t.at(0) - 48);
                    t.clear();
                }else{
                    int b = (int)t.at(0) - 48;
                    int c = (int)t.at(1) - 48;
                    a.push_back(b*10 + c);
                    t.clear();
                }
            }
        }else{
            t.push_back(s.at(i));
        }
    }
    int k;
    cin >> k;
    if(k == 32){
        cout << 51 << endl;
    }else{
        cout << a.at(k-1) << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; ++i)
#define ALL(v) v.begin(), v.end()
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1000000007;

int main()
{
   ll n;
   cin >> n;
   ll ans = 1;
   for(ll i=2;i*i<=n;++i)
   {
      if(n%i==0)ans = i;
   }
   cout<<n/ans+ans-2<<endl;
   return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define INF 1000000000
int main(){
cin.tie(0);
ios::sync_with_stdio(false);

	char s[3];
	int a=0,b=0,c=0;
	REP(i,3){
		cin>>s[i];
		if(s[i]=='a')a=1;
		else if(s[i]=='b')b=1;
		else if(s[i]=='c')c=1;
	}
	if(a==1 && b==1 && c==1)
	cout<<"Yes"<<endl;
	else
		cout<<"No"<<endl;
	
	return 0;
}

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

int main(){
  int h,w; cin>>h>>w;
  vector<string>S(h);
  rep(i,h) cin>>S[i];
  vector<bool> R(h,false), C(w,false);
  rep(i,h) rep(j,w){
    if (S[i][j]=='#') R[i]=true, C[j]=true;
  }
  rep(i,h){
    if (R[i]){
      rep(j,w){
        if (C[j]) cout << S[i][j];
      }
      cout << endl;
    }
  }
}

Measured memory_bytes: 3640
mod=10**9+7
N,M=map(int,input().split())
from collections import defaultdict
yaku=defaultdict(int)
now=M
for i in range(2,1+M):
    if now**0.5<i:
        yaku[now]+=1
        break
    while now%i==0:
        yaku[i]+=1
        now//=i
    if now==1:
        break
kaijo=[0]*(1+N)
kaijo[0]=1
for i in range(1,1+N):
    kaijo[i]=kaijo[i-1]*i%mod
gyaku=[0]*(1+N)
gyaku[N]=pow(kaijo[N],mod-2,mod)
for i in range(N,0,-1):
    gyaku[i-1]=gyaku[i]*i%mod
def calc(N,x):
    dp=defaultdict(list)
    dp[1].append([1])
    for i in range(1,x):
        for L in dp[i]:
            if L[-1]+i<=x:
                dp[i+L[-1]].append(L+[L[-1]])
            M=L.copy()
            M[-1]+=1
            dp[i+1].append(M)
    res=0
    for L in dp[x]:
        if len(L)>N:
            continue
        now=kaijo[N]*gyaku[N-len(L)]%mod
        cnt=defaultdict(int)
        for l in L:
            cnt[l]+=1
        for k,v in cnt.items():
            now=now*gyaku[v]%mod
        res=(res+now)%mod
    return res
ans=1
for k,v in yaku.items():
    ans=ans*calc(N,v)%mod
print(ans)

Measured memory_bytes: 14700
L,R=map(int,input().split())

if L%2019==0 or R%2019==0 or L//2019!=R//2019:
    print(0)
else:
    mn=L*R % 2019
    for i in range(L,R):
        for j in range(i+1,R+1):
            mn=min(mn,i*j % 2019)
    print(mn)

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

using namespace std;

using P = pair<int, int>;

vector<vector<int>> g(200010);

// distance, vertex
P dfs(int cur, int pre)
{
    int p = -1, ma = -1;
    for (auto v : g[cur])
    {
        if (v == pre)
            continue;
        auto ret = dfs(v, cur);
        if (ret.first > ma)
        {
            ma = ret.first;
            p = ret.second;
        }
    }
    if (ma == -1)
    {
        return P(0, cur);
    }
    return P(ma + 1, p);
}

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

    int n;
    cin >> n;
    for (int i = 0; i < n - 1; i++)
    {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    P p = dfs(0, -1);
    P p2 = dfs(p.second, -1);
    cout << (p2.first % 3 == 1 ? "Second" : "First") << endl;
}


Measured memory_bytes: 23680
const MOD: u64 = 1_000_000_007;

fn mod_pow(r: u64, mut n: usize) -> u64 {
    let mut t = 1;
    let mut s = r;
    while n > 0 {
        if n & 1 == 1 {
            t = t * s % MOD;
        }
        s = s * s % MOD;
        n >>= 1;
    }
    t
}

fn run() {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    let mut it = s.trim().split_whitespace();
    let a: usize = it.next().unwrap().parse().unwrap();
    let b: usize = it.next().unwrap().parse().unwrap();
    let mut comb = vec![vec![]; b + 1];
    comb[0] = vec![1, 0];
    for i in 1..(b + 1) {
        comb[i] = vec![1; i + 1];
        for j in 1..i {
            comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]) % MOD;
        }
    }
    let mut g1 = vec![vec![1; b + 1]; a + 1];
    for i in 1..(a + 1) {
        for j in 1..(b + 1) {
            if i >= j {
                g1[i][j] = mod_pow(2, j);
            } else {
                g1[i][j] = (g1[i - 1][j] + comb[j][i]) % MOD;
            }
        }
    }
    let mut f1 = vec![vec![1; b + 1]; a + 1];
    for i in 1..(a + 1) {
        for j in 1..(b + 1) {
            f1[i][j] = (f1[i - 1][j] + g1[i][j - 1]) % MOD;
        }
    }
    let mut ans = 0;
    for i in 0..(a + 1) {
        let a = a - i;
        let b = b - 1;
        if a >= b {
            for j in 0..(b + 1) {
                ans += comb[b][j] * f1[a - (b - j)][b - j] % MOD;
            }
        } else {
            for j in 0..(a + 1) {
                ans += comb[b][j] * f1[a - j][j] % MOD;
            }
        }
    }
    ans %= MOD;
    println!("{}", ans);
}

fn main() {
    run();
}


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

int main() {
  int n;
  cin>>n;
  vector<int>a(n),b(n);
  for(int i=0;i<n;i++){
    cin>>a[i];
    b[i]=a[i];
  }
  int chuo=n/2;
  sort(b.begin(),b.end());
  for(int i=0;i<n;i++){
    if(a[i] <b[chuo])cout<<b[chuo]<<endl;
    else cout<<b[chuo-1]<<endl;
  }
  return 0;
}


Measured memory_bytes: 4820
import java.util.ArrayList;
import java.util.Scanner;

class Digit{

	private static final int [] sizeTable = { 9, 99, 999, 9999, 99999, 999999, 9999999,99999999, 999999999, Integer.MAX_VALUE };
	public int digit;

	public Digit(int a,int b){digit = calc_digit(a+b);}

	private int calc_digit(int x){
        for (int i=0;;i++){if (x <= sizeTable[i]){return i+1;}}
 	}
}

public class Main {

    public static void main(String[] args) {

    	ArrayList<Digit> Ar = new ArrayList<Digit>();

        //input
        Scanner sc = new Scanner(System.in);

        while(sc.hasNext()){
        	Ar.add(new Digit(sc.nextInt(),sc.nextInt()));
        }

        //output
        for(Digit d:Ar){System.out.println(d.digit);}
    }
}

Measured memory_bytes: 20424
///****In the name of Allah, most Gracious, most Compassionate****//

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

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

#define ALL(a) a.begin(), a.end()
#define FastIO ios::sync_with_stdio(false); cin.tie(nullptr);cout.tie(nullptr)
#define IN freopen("input.txt","r+",stdin)
#define OUT freopen("output.txt","w+",stdout)


#define TEST

#ifdef TEST
    #define DBG(a) cout<< #a <<" --> "<<(a)<<endl;
    #define NL cout<<"\n";
#else
    #define DBG(a) ;
    #define NL cout<<"\n";
#endif // TEST

template < class T1,class T2>
ostream &operator <<(ostream &os,const pair < T1,T2 > &p)
{
    os<<"{"<<p.first<<","<<p.second<<"}";
    return os;
}

const ll N=1e6+6;
const ll oo=998244353;

ll T[N];
ll T2[N];
ll a[N];
ll w[N];
ll inv[N];
void for_all_mod_inverse(ll m)
{
    inv[1] = 1;
    for(ll i = 2; i < N; ++i)
        inv[i] = (m - (m/i) * inv[m%i] % m) % m;
}

int32_t main()
{
    FastIO;
    for_all_mod_inverse(oo);
    ll n;
    cin>>n;
    for(ll i=0;i<n;i++)
    {
        cin>>a[i];
    }

//    for(ll i=1;i<N;i++)
//    {
//        a[i] = i;
//    }
//    ll n= N;
    for(ll i=0;i<n;i++)
    {
        T[a[i]] =( T[a[i]] + a[i] ) % oo;
        T2[a[i]] =( T2[a[i]] + a[i]*a[i] % oo  ) % oo;
    }
    for(ll i=1;i<N;i++)
    {
        for(ll j=i+i;j<N;j+=i)
            T[i]= (T[i] + T[j])%oo ,
            T2[i]= (T2[i] + T2[j])%oo ;
    }
//    for(ll i=1;i<N;i++) cout<<T2[i]<<" "; NL;
    for(int i=1;i<N;i++)
    {
        T[i] = (T[i]* T[i] % oo- T2[i] + oo)%oo;
        T[i]  = ( T[i] * inv[2]) % oo;
        //T[i] = (T[i] + T2[i])%oo;
    }
//    DBG(T);
//    for(int i=1;i<N;i++)
//        cout<<T[i]<<" "; NL;
    for(int i=1;i<N;i++)
    {
        w[i]=inv[i];
    }
    for(int i=1;i<N;i++)
    {
        for(int j=i+i;j<N;j+=i)
            w[j] = (w[j] - w[i])%oo;
    }
    ll ans = 0;
    for(int i=1;i<N;i++)
    {
        ans = (ans + w[i] * T[i] % oo) % oo;
    }
    while(ans<0) ans+=oo;
    cout<<ans<<"\n";
}


Measured memory_bytes: 35200
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

#define iFOR(idx, from, upto) for (int  idx = from; idx < upto; ++idx)
#define lFOR(idx, from, upto) for (long idx = from; idx < upto; ++idx)

using namespace std;

int main() {
    string s;
    cin >> s;
    if (s == "AAA" || s == "BBB") {
        cout << "No" << endl;
    } else {
        cout << "Yes" << endl;
    }
    return 0;
}


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

using namespace std;

typedef pair<int, int> P_ii;
typedef pair<string, int> P_si;
typedef long long int ll;

const int MOD = 1000000007;

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

    ll ansh = 0, ansn = 0, answ = 0;
    for (ll h = 1; h <= 3500; ++h) {
        for (ll n = 1; n <= 3500; ++n) {
            ll x = N*h*n;
            ll y = 4*h*n - N*n - N*h;
            if (y <= 0) continue;
            if (x % y != 0) continue;
            ll w = x / y;
            if (w <= 0 || w > 3500) continue;
            cerr << h << n << w << endl;
            ansh = h;
            ansn = n;
            answ = w;
            break;
        }
    }
    printf("%lld %lld %lld", ansh, ansn, answ);
    return 0;
}



Measured memory_bytes: 256
//header{{{
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
//#include<boost/multiprecision/cpp_int.hpp>
//#include<boost/math/common_factor_rt.hpp>
//#include<boost/multiprecision/cpp_dec_float.hpp>
  
using namespace std;
//using namespace boost;
//using namespace multiprecision;  

#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define Fixed fixed << setprecision(12)
#define int int64_t
using pii = pair<int,int>;
constexpr int INF  = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int mod1 = 1e9+7; 
constexpr int mod2 = 998244353;

template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }

template <class T> using min_heap = priority_queue<T,vector<T>,greater<T> >;
template <class T> using max_heap = priority_queue<T>;
template <class A, class B> using umap = unordered_map<A,B>;
  
inline int square(int a){ return a * a;}
inline int updiv(int a,int b){ return (a + b - 1) / b; }

template <class A, class B> inline int Max(const A &a, const B &b){ return (a < b ? b : a); }
template <class A, class B> inline int Min(const A &a, const B &b){ return (a > b ? b : a); }

constexpr int dx[] = {1,0,-1,0,1,1,-1,-1};
constexpr int dy[] = {0,-1,0,1,1,-1,-1,1};
//}}}


signed main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int n;
    cin >> n;

    vector<int> a, x(n), cnt(1e6+1);
    vector<bool> num(1e6+1);

    rep(i,n){
        cin >> x[i];
        ++cnt[x[i]];
    }

    rep(i,n){
        if(cnt[x[i]] == 1){
            a.emplace_back(x[i]);
        }else{
            num[x[i]] = true;
        }
    }

    sort(all(a));

    int res = 0;
    n = a.size();

    for(int i = 0; i < n; ++i){
        bool isok = true;
        for(int j = 1; j * j <= a[i]; ++j){
            if(a[i] % j == 0){
                if(num[j]){
                    isok = false;
                    break;
                }
                if(num[a[i] / j]){
                    isok = false;
                    break;
                }
            }
        }
        if(isok){
            ++res;
        }
        num[a[i]] = true;
    }

    cout << res << '\n';

    return (0);
}


Measured memory_bytes: 14796