akhauriyash/Code-Regression huggingface dataset:
N = gets.to_i

points = []
N.times do
  x, y, h = gets.split.map(&:to_i)
  points << [x, y, h]
end

0.upto(101) do |x|
  0.upto(101) do |y|
    sum = []
    points.select {|p| p[2] > 0}.each do |p|
      sum << p[2] + (p[0] - x).abs + (p[1] - y).abs
    end

    # puts "#{points} x: #{x} y: #{y} => #{sum}"

    if sum.uniq.size == 1
      satisfied = true
      points.select {|p| p[2] == 0}.each do |p|
        if sum.first > (p[0] - x).abs + (p[1] - y).abs
          satisfied = false
          break
        end
      end
      if satisfied
        puts "#{x} #{y} #{sum.first}"
        exit 0
      end
    end
  end
end


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

#define sci(a) scanf("%d", &a)
#define fto(i, a, b) for (int i = a; i <= b; ++i)
#define fdto(i, a, b) for (int i = a; i >= b; --i)
#define scii(a, b) scanf("%d %d", &a, &b)
#define ll long long
#define ff first
#define ss second
#define vi vector<int>
#define ii pair<int, int>
#define vii vector<ii>
#define pii pair<int, ii>
#define maxN 105
#define oo 1000000007
#define mp make_pair
#define pb push_back
#define bug(a) cout << #a << "= " << a << endl;
#define bug2(a, b) cout << #a << "= " << a << "; " << #b << "= " << b << endl
#define pri(a) printf("%d", a)
#define pril(a) printf("%d\n", a)

using namespace std;

int n, A;
int a[maxN];
ll f[maxN][maxN*maxN];

int main() {
//    #ifndef ONLINE_JUDGE
//    freopen("cf.inp", "r", stdin);
//    freopen("cf.out", "w", stdout);
//    #endif

    scii(n, A);
    fto(i, 1, n) sci(a[i]), a[i] -= A;
//    f[0][0] = 1;
//    fto(i, 1, n) {
//        fto(j, 0, A-1) {
//            fto(k, 0, i-1) {
//                bug2(k, (j-a[i]%A+A)%A);
//                bug(f[k][(j-a[i]%A+A)%A]);
//                f[i][j] += f[k][(j-a[i]%A+A)%A];
//            }
//            bug2(i, j);
//            bug(f[i][j]);
//        }
//    }
    int M = 2500;
    f[0][M] = 1;
    fto(i, 1, n) {
        fto(j, -M, M) {
            int k = j-a[i]+M;
            if(k < 0 || k>2*M) continue;
//            bug2(i, j+M);
            f[i][j+M] = f[i-1][j+M]+f[i-1][k];
        }
    }
    cout << f[n][M]-1 << '\n';
    return 0;
}


Measured memory_bytes: 5376
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> p;

int main(){


    int n;
    cin >> n;
    string s;
    s = to_string(n);
    char c;
    c = s.at(s.size()-1);
    
    if (c == '3'){
        cout << "bon" << endl;
    }
    else if ((c == '0') || (c == '1') || (c == '6') || (c == '8')){
        cout << "pon" << endl;
    }
    else{
        cout << "hon" << endl;
    }
    return 0;
}

Measured memory_bytes: 3696
N,M = map(int, input().split())

isAC = [0] * (N+1)
isWA = [0] * (N+1)

ACnum = 0
WAnum = 0

for _ in range(M):
    p, s = input().split()
    p = int(p)
    
    if isAC[p] == 1: continue
    if s == 'AC':
        isAC[p] += 1
        ACnum += 1
        WAnum += isWA[p]
    elif s == 'WA':
        isWA[p] += 1

print("%d %d"%(ACnum, WAnum))

Measured memory_bytes: 4596
import sys

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inl = lambda: [int(x) for x in sys.stdin.readline().split()]
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))


def solve():
    n = ini()
    return n * (n - 1) // 2


print(solve())


Measured memory_bytes: 9188
#include<iostream>
#include<utility>
#include<queue>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;

using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;

bool can(ll t,ll a, ll b, const vl &A) {
	ll anum = 0;
	for (auto x : A) {
		if (x <= t*b) {
			continue;
		}
		else {
			ll num = (x - t*b - 1) / (a - b) + 1;
			if (num > t)return false;
			anum += num;
			//cout << "x ="<<x<<" num" <<num << endl;
		}
	}
	//cout << "anum = " << anum << " " << t << endl;
	if (anum <= t) {
		return true;
	}
	return false;
}

int main() {
	int n;
	ll a, b;
	cin >> n >> a >> b;
	vl A(n);
	ll m = 0;;
	for (int i = 0; i < n; i++) {
		cin >> A[i];
		m = max(m, A[i]);
	}
	ll low = 0;
	ll up = m / b + 1;//low ->not able  up ->able
	while (up - low > 1) {
		int mean = (up + low) / 2;
		if (can(mean,a,b,A)) {
			up = mean;
		}
		else {
			low = mean;
		}
	}
	cout << up <<endl;
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define REP(i,n) for(ll i=0;i<n;i++)
#define FOR(i,n1,n2) for(ll i=n1;i<n2;i++)
#define bFOR(i,n1,n2) for(ll i=n1;i>=n2;i--)
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
typedef long long int ll;
typedef pair<ll,ll> Pi;
typedef tuple<ll,ll,ll> Tu;
const int INF=(ll)(1LL<<30)-1;
const double INFd=100000000000.0;
const double PI=3.14151926535;
const ll INFl=(ll)9223372036854775807;
const int MAX=10000;
const ll MOD=(ll)1e9+7;
const ll tMOD=(ll)998244353;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a, b)*b;}
int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};
int mdx[8]={0,1,0,-1,1,1,-1,-1},mdy[8]={-1,0,1,0,1,-1,1,-1};


template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

int main(){
    while(1){
        int h,w;
        cin>>h>>w;
        if(h+w==0)break;
        Pi c[1000];
        REP(i,h){
            REP(j,w){
                char t;
                cin>>t;
                if(t=='_')continue;
                c[t]=Pi{i,j};
            }
        }
        int ans=0;
        string s;
        cin>>s;
        int t1=0,t2=0;
        REP(i,s.size()){
            ans+=(abs(c[s[i]].first-t1)+abs(c[s[i]].second-t2));
            t1=c[s[i]].first;
            t2=c[s[i]].second;
        }
        cout<<ans+s.size()<<endl;
    }
    return 0;
}


Measured memory_bytes: 3224
#!python3.4
# -*- coding: utf-8 -*-
# abc155/abc155_b
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N = i2n()
    A = i2nn()
    for a in A:
        if a % 2 == 0 and (a % 3 and a % 5):
            print('DENIED')
            return
    else:
        print('APPROVED')
    return

main()


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define REP(i, n) for(ll i = 0; i < (ll)n; i++)
#define FOR(i, a, b) for(ll i = (a); i < (ll)b; i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define INF (1ll << 60)
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;
typedef pair<ll, ll> p;
constexpr int MOD = 1000000007;
using ll = long long;
template <class T> inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

void print(const std::vector<int> &v) {
    std::for_each(v.begin(), v.end(), [](int x) { std::cout << x << " "; });
    std::cout << std::endl;
}
vector<bool> reached;
vector<vector<ll>> edge;
vector<ll> ans;
vector<ll> cost;
int dfs(int parent) {
    // parentは確定してるとして
    for(int i = 0; i < edge[parent].size(); i++) {
        int child = edge[parent][i];
        if(reached[child] == false) {
            ans[child] = ans[parent] + cost[child];
            reached[child] = true;
            dfs(child);
        }
    }
}
int main() {
    ll N, Q;
    cin >> N >> Q;
    reached.resize(N);
    REP(i, N) { reached[i] == false; }
    ans.resize(N);
    REP(i, N) { ans[i] = 0; }
    edge.resize(N);
    vector<ll> a(N - 1), b(N - 1);
    vector<ll> p(Q), x(Q);
    REP(i, N - 1) {
        cin >> a[i] >> b[i];
        a[i]--;
        b[i]--;
        edge[a[i]].push_back(b[i]);
    }
    cost.resize(N);
    REP(i, N) { cost[i] = 0; }
    REP(i, Q) {
        cin >> p[i] >> x[i];
        p[i]--;
        cost[p[i]] += x[i];
    }
    ans[0] = cost[0];
    reached[0] = true;
    // cout << "hoge" << endl;
    dfs(0);
    REP(i, N) { cout << ans[i] << " "; }
    cout << endl;
    return 0;
}

Measured memory_bytes: 32128
#include <bits/stdc++.h>
using namespace std;
 
/* REPmacro */
#define REP(i,n) for(int i=0,i##_len=(n);i<i##_len;++i)
#define REPR(i,n) for(int i=((int)(n)-1);i>=0;--i)
#define FOR(i,m,n) for(int i=(int)(m);i<(int)(n);++i)
 
/*alias*/
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define F first
#define S second
#define PB push_back
#define EB emplace_back
#define MP make_pair 
 
#define y0 y3487465
#define y1 y8687969
#define j0 j1347829
#define j1 j234892
#define next asdnext
#define prev asdprev
#define itn int
 
/*using*/
using ll = long long;
using ull = unsigned long long;
using unsi = unsigned;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using pii = pair<int, int>;
using db = double;
using plex = complex<double>;
using vs = vector<string>;
 
/*template*/
template<class T>inline bool amax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>inline bool amin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
 
/* func */
 
/*struct*/
struct aaa {
	aaa() {
		cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(20);
	};
}aaaaaaa;
 
/* const */
const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
const int MOD = 1e9 + 7; //10^9
const db EPS = 1e-9;
const int dx[] = { 1, 1, 0, -1, -1, -1, 0, 1 }, dy[] = { 0, 1, 1, 1, 0, -1, -1, -1 };
//Counterclockwise from the 9o'clock direction
//Take the x-axis downward and the y-axis right
 
//#define int ll
#define int long long
 
 array<int,200010> a;
signed main()
{
  int n, k;
  cin>>n>>k;
  for(int i = 0; i < n; ++i){
    int t;
    cin>>t;
    ++a[t];
  }
  
//  REP(i,n)cout<<a[i];

  sort(&a[0],&a[n+1]); //0~nとその次を対象にsort
/*
  int* itr2 = &a[0]+n+1;
  cout << *itr2 <<endl;
  auto itr=a.end();
  cout << *itr<<endl;
  */
  int ans = 0;
  for(int i = 0; i <= n-k; ++i)
    ans += a[i];
    cout<<ans;
 
  return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define ll long long
using namespace std;
long long arr[1000007];
long long cs[1000007];
long long ps[1000007];

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

    int z = s.size();

    if(s[z-1]=='s')
        s+="es";

    else
        s+="s";

    cout<<s<<endl;


    return 0;

}















Measured memory_bytes: 3628
#include <stdio.h>
#include <math.h>

int main() {
    int a,b,sum;
    char op;
    while(1){
    scanf("%d %c %d",&a,&op,&b);
    
        switch(op){
            case '+':
                sum=a+b;
                break;
            case '-':
                sum=a-b;
                break;
            case '*':
                sum=a*b;
                break;
            case '/':
                sum=a/b;
                break;
            default:
                break;
        }
        if(op=='?')
            break;
        printf("%d\n",sum);
        
    }
    return 0;
}


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

const int N = 107, M = 1e5 + 7, INF = 0x3f3f3f3f;

int dp[N][M], w[N], v[N];

int32_t main() {
        int n, k; cin >> n >> k;
        for(int i = 1; i <= n; i++) {
                cin >> w[i] >> v[i];
        }

        for(int i = 1; i <= n; i++) {
                for(int j = 1; j <= k; j++) {
                    dp[i][j] = dp[i - 1][j];
                    if(j - w[i] >= 0) dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i]);
                }
        }

        cout << dp[n][k] << endl;

}


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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF = (1<<30) - 1;
const ll LINF = (1LL<<60) - 1;

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

    int res = 0;
    for (int i = 0; i < n; ++i) {
        int len = 0;
        for (int j = 0; j < n-i; ++j) {
            if (s[j] == s[j+i] && len < i) {
                len++;
            } else {
                len = 0;
            }
            chmax(res, len);
        }
    }
    cout << res <<endl;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define MOD 1000000007
#define PI 3.141592653589793238
#define pb push_back
#define ALL(V) (V).begin(), (V).end()
#define rep(i, a, b) for(int i = (a); i < (b); ++i)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long long int lint;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
inline ll gcd(ll a, ll b) { return (a % b == 0 ? b : gcd(b, a % b)); }
inline ll lcm(ll a, ll b) { return a * b / gcd(a, b); }
inline ll char_to_ll(char c) { return (int)(c - '0'); }
inline ll string_to_ll(string s) { return atoi(s.c_str()); }
inline bool is_prime(ll x){ if(x <= 1) return false; for(ll i = 2; sqrt(i) <= x; i++) if(x % i == 0) return false; return true; }

// 動作環境 : C++14 AOJ
int main(){
    double r;
    cin >> r;
    printf("%.8f %.8f", pow(r, 2) *  acos(-1), r * 2 * acos(-1));

    return 0;
}



Measured memory_bytes: 3208
n = int(input())
a = list(map(int,input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
ans = sum(b)
count = 100
for i in a:
  if i - 1 == count:
    ans += c[i - 2]
  count = i
print(ans)


Measured memory_bytes: 3316
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <complex>
using namespace std;

using ll = long long;
using ull = uint64_t;
using P = pair<int, int>;
constexpr double EPS = 1e-9;
constexpr int INF = 1501001001;
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;

template<class T>
inline bool chmax(T& x, T y){
    if(x < y){
        x = y;
        return true;
    }
    return false;
}
template<class T>
inline bool chmin(T& x, T y){
    if(x > y){
        x = y;
        return true;
    }
    return false;
}

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

    for(;;){
        int N, M;
        cin >> N >> M;
        if(N == 0 && M == 0)    return 0;
        vector<int> C(M);
        for(int i = 0; i < M; ++i)  cin >> C[i];
        vector<vector<int>> dp(N + 1, vector<int>(256, INF));
        dp[0][128] = 0;
        for(int i = 0; i < N; ++i){
            int x;
            cin >> x;
            for(int j = 0; j <= 255; ++j){
                if(dp[i][j] == INF) continue;
                for(int k = 0; k < M; ++k){
                    int nj = j + C[k];
                    if(nj > 255)    nj = 255;
                    if(nj < 0)  nj = 0;
                    int cost = abs(x - nj) * abs(x - nj);
                    chmin(dp[i + 1][nj], dp[i][j] + cost);
                }
            }
        }
        cout << *min_element(dp[N].begin(), dp[N].end()) << '\n';
    }
}


Measured memory_bytes: 23668
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#include <numeric>
typedef long long Int;
#define rep(i,a,b) for(Int i=a;i<b;++i)
#define rrep(i,a,b) for(Int i=a;i>=b;--i)
using namespace std;

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

    Int N; cin >> N;
    vector<Int> A(N);
    unordered_map<Int, Int> mp;
    rep(i, 0, N) { cin >> A[i]; mp[A[i]]++; }

    if (N%2 == 0) {
        for(Int i = 1; i < N; i += 2) {
            if (mp[i] != 2) { cout << 0 << endl; return 0; }
        }
    }
    else {
        if (mp[0] != 1) { cout << 0 << endl; return 0; }
        for(Int i = 2; i < N; i += 2) {
            if (mp[i] != 2) { cout << 0 << endl; return 0; }
        }
    }

    Int res = 1;
    rep(i, 0, N/2) {
        res *= 2;
        res %= 1000000007;
    }

    cout << res << endl;
}


Measured memory_bytes: 4492
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <functional>
#include <climits>
#include <cstring>
#include <unordered_map>

using namespace std;

#define int long long
#define rep(i, n) for (int i=0;i<(int)(n);++i)
#define rep1(i, n) for (int i=1;i<=(int)(n);++i)
#define range(i, l, r) for (int i=l;i<(int)(r);++i)
#define rrange(i, l, r) for (int i=r-1;i>=(int)(l);--i)
#define unless(a) if(!(a))
#define all(a) begin(a),end(a)
#define fst first
#define scd second
#define PB emplace_back
#define PPB pop_back

using vi=vector<int>;
using pii=pair<int, int>;
using ll=long long;

bool chmin(int&a,int b){return a>b?(a=b,true):false;}
bool chmax(int&a,int b){return a<b?(a=b,true):false;}
//int read(){int a;scanf("%lld",&a);return a;}

constexpr int TEN(int n){return n==0?1:10*TEN(n-1);}

const int inf = TEN(18)*3 + 10;
const int mod = TEN(9) + 7;

map<pii, bool> exists;
map<pii, bool> used;

int ans;

void dfs(pii point, int p, int q, int depth = 0)
{
	if (used.count(point) > 0) {
		return;
	}
	if (exists.count(point) == 0) {
		return;
	}
	if (depth == 0) ans++;
	used[point] = true;
	
	dfs(pii(point.fst + p, point.scd + q), p, q, depth + 1);
	dfs(pii(point.fst - p, point.scd - q), p, q, depth + 1);
}

signed main()
{
	int N; cin >> N;
	vector<pii> points;
	rep(i, N) {
		int x, y; cin >> x >> y;
		points.PB(x, y);
		exists[pii(x,y)] = true;
	}

	if (N == 1)
	{
		puts("1");
		return 0;
	}

	int mn = inf;
	rep(i, N) {
		rep(j, i) {
			int p = points[i].fst - points[j].fst;
			int q = points[i].scd - points[j].scd;

			used.clear();
			ans = 0;
			rep(k, N) {
				dfs(points[k], p, q);
			}
			chmin(mn, ans);
		}
	}

	cout << mn << endl;
}


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

using i64 = long long;
using P = pair<i64, i64>;

#define overload3(_1, _2, _3, name, ...) name
#define rep1(i, n) for(i64 i = 0LL; i < (n); ++i)
#define rep2(i, a, b) for(i64 i = (a); i < (b); ++i)
#define rep(...) overload3(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)
#define all(v) v.begin(), v.end()


void solve(long long N){
    vector<vector<string>> s(2);
    s[0].push_back("a");
    rep(i, 1, N){
        rep(j, s[(i - 1) % 2].size()){
            i64 r = 0;
            rep(k, i) r = max(r, (i64)s[(i - 1) % 2][j][k]);
            rep(k, r - 'a' + 2){
                s[i % 2].push_back(s[(i - 1) % 2][j] + char('a' + k));
            }
        }
        s[(i - 1) % 2].clear();
    }
    //cout << s[(N - 1) % 2].size() << endl;
    //auto t = s;
    sort(s[(N - 1) % 2].begin(), s[(N - 1) % 2].end());
    //if(s == t) cout << "hoge" << endl;
    rep(i, s[(N - 1) % 2].size()) cout << s[(N - 1) % 2][i] << endl;
}

struct IoSetup {
    IoSetup() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(10);
        cerr << fixed << setprecision(10);
    }
} iosetup;

int main(){
    long long N;
    scanf("%lld",&N);
    solve(N);
    return 0;
}


Measured memory_bytes: 11124
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

class Main{

	public static void main(String[] args) throws IOException{

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input = br.readLine();
		StringTokenizer st = new StringTokenizer(input, " ");
		int a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());
		int dig = Integer.parseInt(st.nextToken());
		double rad = Math.toRadians(dig);
		double pow_a = Math.pow(a, 2);
		double pow_b = Math.pow(b, 2);
		double pow_c = pow_a + pow_b - 2 * a * b * Math.cos(rad);
		double h = b * Math.sin(rad);
		double s = a * h / 2;
		double l = a + b + Math.sqrt(pow_c);

		System.out.printf("%.8f\n%.8f\n%.8f\n", s, l, h);

	}
}

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

int main() {

  int N,M;
  cin >> N >> M;
  int K[N];
  int A[N][M];
  for (int i=0; i<N ; i++){
    for (int j=0; j<M ; j++){
      A[i][j]=-1;
    }
  }
  for (int i=0; i<N ; i++){
    cin >> K[i];
    for (int j=0; j<K[i] ; j++){
      cin >> A[i][j];
    }
  }
  int total[M];
  for (int j=0; j<M ; j++){
    total[j]=0;
  }
  for (int i=0; i<N ; i++){
    for (int j=0; j<M ; j++){
      for (int k=0; k<M ; k++){
	if(A[i][j]==k+1) total[k] +=1;	
      }
    }
  }
  int hito=0;
  for (int j=0; j<M ; j++){
    if( total[j]==N) hito++;
  }
  cout << hito << endl;

}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<sstream>
#include<iterator>
#include<list>

using namespace std;

typedef  long long int lint;

#define rep(i, n) for (lint i = 0; i < n; i++)
#define sort(v) sort((v).begin(), (v).end())
#define reverse(v) reverse((v).begin(), (v).end())
#define upper(v,hoge) upper_bound(v.begin(),v.end(),hoge)
#define lower(v,hoge) lower_bound(v.begin(),v.end(),hoge)
#define mp make_pair
#define enld endl
#define P pair<lint,lint>

int main() {
	lint A, B, C, D;
	cin >> A >> B >> C >> D;
	cout << max(A * B, C * D) << endl;
}

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

int main(void){
    int a = 0, b = 0; 
    int num_b = 0;
    int sum_b = 0;

    scanf("%d%d", &a, &b);

    num_b = b - a;

    for(int i = 1; i <= num_b; i++){
        sum_b += i;
    }

    printf("%d\n", sum_b - b);

    return 0;

}


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

string::size_type find(char ch) {
  string sch; sch.push_back(ch);
  string tgt = "()[]";
  return tgt.find(sch);
}

int main() {
  string str;
  
  while(getline(cin, str)) {
    if(str == ".") break;

    string s;

    for(unsigned i=0; i<str.size(); i++) {
      if(find(str[i]) != string::npos) {
	s.push_back(str[i]);
      }
    }
    
    int len = s.size();
    char ch;
    stack<char> st;
    
    bool ok = 1;
    for(int i=0; i<len; i++) {
      if(s[i] == '(') st.push(s[i]);
      if(s[i] == '[') st.push(s[i]);
      
      if(s[i] == ')') {
	if(st.empty()) {
	  ok = 0;
	  break;
	}

	ch = st.top();
	if(ch != '(') {
	  ok = 0;
	  break;
	}
	st.pop();
      }
      
      if(s[i] == ']') {
	if(st.empty()) {
	  ok = 0;
	  break;
	}

	ch = st.top();
	if(ch != '[') {
	  ok = 0;
	  break;
	}
	st.pop();
      }

    }
    cout << ( ok && st.empty() ? "yes" : "no" ) << endl;
  }
  
  return 0;
}

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

const int MAX_N=1e5; // 1e8=x, 1e7=? 1e6=o
int n[MAX_N+1]={};
vector <int> prime;

void eratos_sieve(){
  for(int i=2;i<=MAX_N;i++){
    if(!n[i]){
      prime.push_back(i);
      for(int j=i;j<=MAX_N;j+=i) n[j]=1;
    }
  }
}

int main(){

  eratos_sieve();

  int p,q,r=1;
  cin>>p>>q;

  p=q/__gcd(p,q);

  for(int i=0;i<(int)prime.size();i++){
    if(!(p%prime[i])){
      r*=prime[i];
      for(;!(p%prime[i]);) p/=prime[i];
    }
  }

  cout<<r*p<<endl;

  return 0;

}



Measured memory_bytes: 3624
// C.

#include <iostream>
#include <sstream>
#include <algorithm>
#include <set>
#include <vector>

using namespace std;

typedef long long LL;

int main(int argc, char *argv[]) {
	LL n;
	cin >> n;
	vector<LL> a, b;
	for (int i = 0; i < (1 << 16); ++i) {
		LL x = 0;
		for (int b = 0; b < 16; ++b) {
			if (i & (1 << b)) {
				x += 1LL << (b * 2);
			}
		}
		a.push_back(x);
		b.push_back(x * -2);
	}
	string ans;
	set<LL> s(b.begin(), b.end());
	for (LL x : a) {
		set<LL>::const_iterator it = s.find(n - x);
		if (it != s.end()) {
			LL y = x | (*it * -1);
			while (y) {
				ans = (y & 1 ? '1' : '0') + ans;
				y >>= 1;
			}
			break;
		}
	}
	cout << (ans.empty() ? "0" : ans) << endl;
	return 0;
}


Measured memory_bytes: 4340
#include<iostream>
#include<vector>
using ll = long long;
using namespace std;

int main(){
    int n;
    cin>>n;
    vector<ll> v(n);
    for(int i=0;i<n;i++){
        int a;
        cin>>a;
        if(i) v[i]=v[i-1]+a;
        else v[i]=a;
    }

    ll ans=1e10;
    for(int i=0;i<n-1;i++){
        ll x=v[i];
        ll y=v[n-1]-v[i];
        ans=min(ans,abs(x-y));
    }
    cout<<ans<<endl;
}

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

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

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}
fn main() {
    input!{
        a: u8,
        b: u8,
    }
    println!("{}", 6 - a - b);
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; i++)
#define RFOR(i, a, n) for (ll i = (ll)n - 1; i >= (ll)a; i--)
#define rep(i, n) FOR(i, 0, n)
#define rrep(i, n) RFOR(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define bra(first, second) '(' << first << ',' << second << ')'
constexpr ll MOD = 1000000007;
//constexpr ll MOD = 998244353;
ll INF = 1001001001001001001;
long double EPS = 1e-9;
long double PI = 3.141592653589793238;
template <typename T>
void remove(std::vector<T> &vector, unsigned int index)
{
   vector.erase(vector.begin() + index);
}

using Graph = vector<vector<pair<ll,ll>>>;

// MOD確認

ll N;
ll B[1000010];

int main(){
   cin >> N;
   vector<ll> A(N);
   rep(i,N) cin >> A[i];
   rep(i,N){
      ll n = A[i];
      for(ll j = 2;j * j <= n;j++){
         if(n % j == 0) B[j]++;
         while(n % j == 0){
            n /= j;
         }
      }
      if(n != 1) B[n]++;
   }
   bool flag = 1;
   rep(i,1000010) if(B[i] > 1) flag = 0;
   if(flag) cout << "pairwise coprime" << endl;
   else{
      ll G = __gcd(A[0],A[1]);
      rep(i,N-1){
         G = __gcd(G,A[i+1]);
      }
      if(G == 1) cout << "setwise coprime" << endl;
      else cout << "not coprime" << endl;
   }
}

Measured memory_bytes: 18748
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n) ;i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
using ll=long long;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define MOD  1000000007
const ll INF=1e18;
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(int argc, char const *argv[]) {
  ll n,k,ans=0;
  cin >> n >> k;
  while(n>0){
    n/=k;
    ans++;
  }
  cout << ans << endl;
  return 0;
}


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

namespace AtCorder
{
	public class Program
	{
		// sbsss sbsss sbsss
		// sbshs sbshs sbshs
		// 
		// sbssss sbssss sbssss
		// sbshsh sbshsh sbshsh
		static void Main(string[] args)
		{
			Scanner cin = new Scanner();
			string s = cin.Next();
			long k = cin.Long();
			char prev = s[0];
			int n = s.Length;
			bool changed = false;
			long ans = 0;

			if (n == 1) {
				ans = k / 2;
				Console.WriteLine(ans);
				return;
			} else if(n == 2) {
				if (s[0] != s[1]) {
					ans = 0;
				} else {
					ans = k;
				}

				Console.WriteLine(ans);
				return;
			}

			bool isAllSame = true;
			char first = s[0];
			for (int i = 1; i < n; i++) {
				if (s[i] != first) {
					isAllSame = false;
					break;
				}
			}

			if (isAllSame) {
				ans = (n * k) / 2;
				Console.WriteLine(ans);
				return;
			}

			for (int i = 1; i < n; i++) {
				if (s[i] == s[i - 1]) {
					if (changed) {
						changed = false;
					} else {
						++ans;
						changed = true;
					}
				} else {
					changed = false;
				}
			}

			ans *= k;

			if (s[0] == s[n - 1]) {
				int fCount = 1;
				int fIndex = 1;
				while (fIndex < n) {
					if (s[fIndex] == s[0]) {
						++fCount;
					} else {
						break;
					}

					++fIndex;
				}

				int bCount = 1;
				int index = n - 2;
				while (index >= 0) {
					if (s[index] == s[n - 1]) {
						++bCount;
					} else {
						break;
					}

					--index;
				}

				if (bCount % 2 == 1 && fCount % 2 == 1) {
					ans += k - 1;
				}
			} 

			Console.WriteLine(ans);
		}
	}

	public class Scanner
	{
		private readonly char[] delimiter_ = new char[] { ' ' };
		private string[] buf_;
		private int index_;

		public Scanner()
		{
			buf_ = new string[0];
			index_ = 0;
		}

		public string Next()
		{
			if (index_ < buf_.Length) {
				return buf_[index_++];
			}

			string st = Console.ReadLine();
			while (st == "") {
				st = Console.ReadLine();
			}

			buf_ = st.Split(delimiter_, StringSplitOptions.RemoveEmptyEntries);
			if (buf_.Length == 0) {
				return Next();
			}

			index_ = 0;
			return buf_[index_++];
		}

		public int Int() => int.Parse(Next());
		public long Long() => long.Parse(Next());
		public double Double() => double.Parse(Next());

		public int[] ArrayInt(int N, int add = 0)
		{
			int[] Array = new int[N];
			for (int i = 0; i < N; i++) {
				Array[i] = Int() + add;
			}
			return Array;
		}

		public long[] ArrayLong(int N, long add = 0)
		{
			long[] Array = new long[N];
			for (int i = 0; i < N; i++) {
				Array[i] = Long() + add;
			}
			return Array;
		}

		public double[] ArrayDouble(int N, double add = 0)
		{
			double[] Array = new double[N];
			for (int i = 0; i < N; i++) {
				Array[i] = Double() + add;
			}
			return Array;
		}
	}
}

Measured memory_bytes: 13140
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <set>
#include <sstream>
#include <bitset>
#include <stack>
#include <cstdlib>

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

typedef long long ll;

using namespace std;

int main() {
    
    ll a,b,c,x,y;
    
    cin >> a >> b >> c >> x >> y;
    
    ll ans=0;
    
    if(a+b >= 2*c){
        if(x>=y){
            if(a>2*c){
                ans = 2*c*x;
            }else{
                 ans = 2*y*c + (x-y)*a;
            }
        }else{
            if(b>2*c){
                ans = 2*c*y;
            }else{
                ans = 2*x*c + (y-x)*b;
            }
        }
    }else{
        ans = a*x+b*y;
    }
    
    cout << ans << endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <numeric>
    
using namespace std;    
typedef long long ll;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
const bool DEBAG = true;

int main(){

    int a, b , c;
    cin >> a >> b >> c;
    cout << a + b + c - max( max(a,b),c) << endl;    

}

Measured memory_bytes: 764
#include <stdio.h>
#define M 500000

int unit[M],cnt;
int L[M/2+2],R[M/2+2];

void merge(int left,int mid, int right){
    int n1,n2,i;
    n1=mid -left;
    n2=right - mid;
    for(i=0;i<n1;i++){
        L[i]=unit[left+i];
    }
    for(i=0;i<n2;i++){
        R[i]=unit[mid+i];
    }
    L[n1]=R[n2]=2000000000;
    i=0;
    int j=0;
    for(int k=left;k<right;k++){
        cnt++;
        if(L[i]<=R[j]){
            unit[k]=L[i++];
        }
        else {
            unit[k]=R[j++];
        }
    }
}

void mergesort(int left,int right){
    if(left+1<right){
        int mid = (left + right)/2;
        mergesort(left,mid);
        mergesort(mid,right);
        merge(left,mid,right);
    }
}

int main(void){
    cnt=0;
    int kari;
    int i=0,limit,right,left;
    scanf("%d",&limit);
    for(i=0;i<limit;i++){
        scanf("%d",&kari);
        unit[i]=kari;
    }
    mergesort(0,limit);
    for(i=0;i<limit;i++){
        printf("%d",unit[i]);
        if(i!=limit-1)printf(" ");
    }
    printf("\n%d\n",cnt);
    return 0;
}




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

signed main(){

  int n,m;
  cin>>n>>m;
  vector<int> a(m);
  for(auto& ai:a)cin>>ai;

  vector<int> need = {0,2,5,5,4,5,6,3,7,6};

  auto add = [](string s,int a){
    s += to_string(a);
    int n = s.size();
    for(int i=n-1;i-1>=0;--i){
      if(s[i-1]>s[i])break;
      swap(s[i-1],s[i]);
    }
    return s;
  };
  auto cmp = [](string& s,string& t){
    // operator <
    int n = s.size();
    int m = t.size();
    if(n<m)return true;
    if(n>m)return false;
    assert(n==m);
    for(int i=0;i<n;++i){
      if(s[i]<t[i]){
        return true;
      }
      if(s[i]>t[i]){
        return false;
      }
    }
    return false;
  };
  auto chmax = [&cmp](string& s,string t){
    if(cmp(s,t))s=t;
  };

  vector<string> dp(n+1);
  for(int i=0;i<=n;++i){
    for(auto const& ai:a){
      if(i-need[ai]<0)continue;
      if(dp[i-need[ai]]==""&&i-need[ai]!=0)continue;
      chmax(dp[i],add(dp[i-need[ai]],ai));
    }
  }
  cout<<(dp[n])<<endl;


}

Measured memory_bytes: 29824
#pragma GCC optimize ("O3")

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for (long long i = 0; i < (long long) (n); ++i)
#define pb emplace_back
#define endl '\n'

template<typename T> void _dbg(const char*_s,T _h) { cerr<<_s<<" = "<<_h<<"\n"; }

template<typename T, typename... Ts> void _dbg(const char*_s,T _h,Ts... _t) {
    for(int _b=0;((_b+=*_s=='(')-=*_s==')')!=0||*_s!=',';)cerr<<*_s++;
    cerr<<" = "<<_h<<",";_dbg(_s+1,_t...);
}

#define int long long

#ifdef LOCAL
    #define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
    #define dbg(...)
#endif

const int N = 500 * 1000 + 17;
const int MOD = 1000 * 1000 * 1000 + 7;

int n;
set<int> ans;

bool read() {
    if (!(cin >> n))
        return false;

    return true;
}

void check(int k) {
    if (k == 1) {
        return ;
    }

    int nn = n;

    while (nn % k == 0)
        nn /= k;

    if (nn % k == 1)
        ans.insert(k);
}

void solve(int id = 0) {
    for (int d = 1; d * d <= n; ++d)
        if (n % d == 0) {
            check(d);
            check(n / d);
        }

    for (int d = 1; d * d <= n - 1; ++d)
        if ((n - 1) % d == 0) {
            ans.insert(d);
            ans.insert((n - 1) / d);
        }

    ans.erase(1);
    cout << ans.size() << endl;
}

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

    int T;
    T = 1;

    while (read())
        solve(T++);

    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)n; ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cout<<*i<<" "; cout<<endl; }

typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const int MOD = 1000000007;

int main(){
  char sensha[] = {'^', '>', 'v', '<'};
  map<char, int> toi;
  toi['U'] = 0;
  toi['R'] = 1;
  toi['D'] = 2;
  toi['L'] = 3;
  toi['S'] = 4;
  int dx[] = {0, 1, 0, -1};
  int dy[] = {-1, 0, 1, 0};
  int T;
  cin>>T;
  bool f = false;
  while(T--){
    if(f)cout<<endl;
    else f = true;
    int H, W;
    cin>>H>>W;
    vector<string> grid(H);
    REP(i,H)cin>>grid[i];
    int N; cin>>N;
    string ope; cin>>ope;
    int nx, ny, nr;
    REP(y,H)REP(x,W)REP(r,4)if(sensha[r] == grid[y][x]){
      nx = x;
      ny = y;
      nr = r;
      grid[y][x] = '.';
    }
    REP(time, N){
      char o = ope[time];
      int t = toi[o];
      if(t < 4){
        nr = t;
        int gx = nx+dx[nr];
        int gy = ny+dy[nr];
        if(0<=gx && gx < W && 0<=gy && gy < H && grid[gy][gx] == '.'){
          nx = gx;
          ny = gy;
        }
      }else{
        int bx = nx;
        int by = ny;
        while(0<=bx && bx < W && 0<=by && by < H){
          if(grid[by][bx] == '*'){
            grid[by][bx] = '.';
            break;
          }else if(grid[by][bx] == '#'){
            break;
          }
          bx += dx[nr];
          by += dy[nr];
        }
      }
    }
    grid[ny][nx] = sensha[nr];
    REP(y,H)cout<<grid[y]<<endl;
  }
  return 0;
}

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

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

int main() {
  int n, m, a, b;
  cin >> n >> m;
  vector<int> counts(n, 0);
  rep(i, m) {
    cin >> a >> b;
    a--, b--;
    counts[a]++;
    counts[b]++;
  }
  rep(i, n) cout << counts[i] << endl;
  return 0;
}


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

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

int n, m;
map<int, vector<pair<int, int>>> edgelist;
int dsu[505];

int find(int n) {
	return n == dsu[n] ? n : dsu[n] = find(dsu[n]);
}

void merge(int u, int v) {
	u = find(u), v = find(v);
	if (u == v) return;
	dsu[v] = u;
}

vi num, st;
vector<vector<pii>> ed;
int Time;

template<class F>
int dfs(int at, int par, F& f) {
	int me = num[at] = ++Time, e, y, top = me;
	trav(pa, ed[at]) if (pa.second != par) {
		tie(y, e) = pa;
		if (num[y]) {
			top = min(top, num[y]);
			if (num[y] < me)
				st.push_back(e);
		} else {
			int si = sz(st);
			int up = dfs(y, e, f);
			top = min(top, up);
			if (up == me) {
				st.push_back(e);
				st.resize(si);
			}
			else if (up < me) st.push_back(e);
			else {
				//cout << "!!!!" << endl;
				f(e);
			}
		}
	}
	return top;
}

template<class F>
void bicomp(F f) {
	num.assign(sz(ed), 0);
	rep(i, 0, sz(ed)) if (!num[i]) dfs(i, -1, f);
}

int main() {
	/*
	cin.sync_with_stdio(false); cin.tie(0);
	cin.exceptions(cin.failbit);
	*/

	rep(i, 0, 505) dsu[i] = i;
	
	cin >> n >> m;
	rep(i, 0, m) {
		int s, d, c; cin >> s >> d >> c;
		//cout << s << " " << d << " " << c << endl;
		edgelist[c].push_back({s, d});
	}

	int nab = 0, sumnab = 0;

	for (auto p : edgelist) {
		//cout << "!!" << endl;
		//cout << p.first << " / " << p.second.size() << endl;
		vector<pair<int, int>> edges = p.second;
		int eid = 0;
		
		vector<int> dirty;
		vector<pair<int, int>> chosen;

		ed.clear(); ed.resize(505);

		//cout << edges.size() << endl;
		for (auto edge : edges) {
			///cout << "!!!" << edge.first << " " << edge.second << endl;
			int u, v; tie(u, v) = edge;
			//printf("%d <-> %d\n", u, v);
			u = find(u), v = find(v);
			//printf("Equiv %d <-> %d\n", u, v);
			if (u != v) {
				dirty.push_back(u), dirty.push_back(v);
				ed[u].emplace_back(v, eid);
				ed[v].emplace_back(u, eid++);
				chosen.emplace_back(u, v);
				//printf("Edge: (%d, %d)\n", u, v);
			}
			//printf("Edge %d is %d, %d\n", eid-1, chosen[eid-1].first, chosen[eid-1].second);
		}
		
		bicomp([&] (const int edge_id) {
			nab++, sumnab += p.first;
				});

		for (auto edge : edges) merge(edge.first, edge.second);

		for (int h : dirty) ed[h].clear();
	}
	cout << nab << " " << sumnab << endl;
}



Measured memory_bytes: 6468
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
#include<deque>
#include<cmath>
#include<map>
#include<unordered_map>
#include<set>
#include<cstring>
#include<iomanip> //cout << fixed << setprecision(15) << x << endl;

using namespace std;
typedef long long ll;
const ll INF = 1e9 + 6;
const ll MOD = 1e9 + 7;
const ll LLINF = 1e18;
#define Pint pair<int, int>
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rnr(i,a,b) for(int i=int(a);i>=int(b);i--)
#define rep(i,b) rng(i,0,b)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
/* -- template -- */

Pint dir[4] = {mp(0, 1), mp(1, 0), mp(-1, 0), mp(0, -1)};

int main() {
    int h, w; cin >> h >> w;
    int cH, cW, dH, dW;
    cin >> cH >> cW;
    cin >> dH >> dW;
    string s[h];
    rep(i, h) cin >> s[i];
    int dist[h][w];
    rep(i, h) {
        rep(j, w) {
            dist[i][j] = INF;
        }
    }
    vector<vector<Pint>> values(h * w);
    int value = 0;
    queue<Pint> que;
    dist[cH - 1][cW - 1] = 0;
    values[0].pb(mp(cH - 1, cW - 1));
    que.push(mp(cH - 1, cW - 1));
    while(!que.empty()) {
        Pint f = que.front(); que.pop();
        rep(i, 4) {
            int hi = dir[i].first + f.first, wi = dir[i].second + f.second;
            if(hi >= 0 && hi < h && wi >= 0 && wi < w) {
                if(s[hi][wi] == '.') {
                    if(dist[hi][wi] == INF) que.push(mp(hi, wi));
                    if(dist[hi][wi] > dist[f.first][f.second] && dist[f.first][f.second] == value) {
                        values[value].pb(mp(hi, wi));
                    }
                    dist[hi][wi] = min(dist[hi][wi], dist[f.first][f.second]);
                }
            }
        }

        if(que.empty()) {
            for(Pint v: values[value]) {
                rng(i, -2, 3) {
                    rng(j, -2, 3) {
                        int hi = v.first + i, wi = v.second + j;
                        if(hi >= 0 && hi < h && wi >= 0 && wi < w) {
                            if(s[hi][wi] == '.') {
                                if(dist[hi][wi] == INF) que.push(mp(hi, wi)), values[value + 1].pb(mp(hi, wi));
                                dist[hi][wi] = min(dist[hi][wi], 1 + dist[v.first][v.second]);
                            }
                        }
                    }
                }
            }
            ++value;
        }
    }
    cout << ((dist[dH - 1][dW - 1] == INF) ? -1 : dist[dH - 1][dW - 1]) << endl;
}


Measured memory_bytes: 37676
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repo(i,n) for(int i = 1; i < (int)(n); i++)
#define pb push_back
#define mp make_pair
#define np next_permutation
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define mod 1000000007
#define pi acos(-1.0)
const ll INF = 1LL<<61;
template<class T>bool chmax(T &a, const T &b) { 
  if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) {
  if (b<a) { a=b; return 1; } return 0; }
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }
ll jou(ll N, ll P){if(P==0) return 1;
  if(P%2==0){ll t = jou(N, P/2);return t*t % mod;
  }return (N * jou(N, P-1)) % mod;}  //jou(n,mod-2)で逆元
//intの最大値2147483647 ≒ 2×10^9
//long longの最大値9223372036854775807 ≒ 9×10^18
//'大文字'+=32;    で小文字に
//  cout << fixed << setprecision (20);   小数点以下2０桁まで
//実行時間制約2秒では２×10^8回くらいまで計算できる





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

  cout << (a%500<=b?"Yes":"No") << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PP;
//#define MOD 1000000007
//#define MOD 998244353
#define INF 1145141919810893364
//#define INF 810114514
#define PI 3.141592653589
#define setdouble setprecision
#define REP(i,n) for(ll i=0;i<(n);++i)
#define OREP(i,n) for(ll i=1;i<=(n);++i)
#define RREP(i,n) for(ll i=(n)-1;i>=0;--i)
#define all1(i) begin(i),end(i)
#define GOODBYE do { cout << "0" << endl; return 0; } while (false)
#define MM <<" "<<
#define Endl endl
#define debug false
#define debug2 false

int main(void){
    
    string S;
    cin >> S;
    if(S=="SSS"){
        cout << 0 << endl;
    }else if(S=="RRS" || S=="SRR"){
        cout << 2 << endl;
    }else if(S=="RRR"){
        cout << 3 << endl;
    }else{
        cout << 1 << endl;
    }
    
    return 0;
}



Measured memory_bytes: 3584
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <iomanip>
#include <fstream>
#include <map>
#include <cassert>
#include <sstream>
#include <numeric>
#include <regex>
#include <cctype>
#include <utility>
#include <stdio.h>
#include <set>
#include <queue>
#include <deque>

typedef long long ll;

#define vi vector<int>
#define vs vector<string>
#define vc vector<char>
#define MOD 1000000007
#define pb push_back
#define llnums vector<ll>
#define FOR(i,n) for(int i{0}; i < n; ++i)

using namespace std;

int main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ll t,a=0;
  cin >> t;
  FOR(i, t+1) {a +=i;}
  cout << a << '\n';
  return 0;
}









Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N,K;
  cin >>N >>K;
  long long ans=0, temp=1;
  if(K%2!=0){
    for(int i=0; i<3; i++){
      temp*=N/K;
    }
    ans=temp;
  }
  else{
    for(int i=0; i<3; i++){
      temp*=N/K;
    }
    ans+=temp,temp=1;
    for(int i=0; i<3; i++){
      temp*=(N/(K/2)-N/K);
    }
    ans+=temp;
  }
  cout <<ans <<endl;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
#define ll long long 
using namespace std;
int main(){
    ll a,b,x;
    cin>>a>>b>>x;;
    ll v = a/x;
    ll u = b/x;
    ll ans = u-v;
    if(a%x==0){
        ++ans;
    }
    cout<<ans<<'\n';
}

Measured memory_bytes: 256
n, w = [int(i) for i in input().split()]
a = [0] * (w + 1)
for _ in range(n):
    b, c = [int(i) for i in input().split()]
    for i in reversed(range(w + 1)):
        if i + b >= w + 1:
            continue
        d = i + b
        a[d] = max(a[d], a[i] + c)
print(a[-1])


Measured memory_bytes: 42348
#include <stdio.h>
typedef long long ll;

ll mabs(ll a) {
  return a > 0 ? a : -a;
}

int main(void) {
  ll i, n, max = 0, mn, a, m;
  scanf("%lld", &n);
  for(i = 0; i < n; ++i) {
    scanf("%lld", &a);
    if(mabs(a) > max) max = mabs(a), mn = i, m = a;
  }
  printf("%lld\n", 2 * n - 2);
  for(i = 0; i < n; ++i) if(i != mn) printf("%lld %lld\n", mn + 1, i + 1);
  if(m > 0) for(i = 1; i < n; ++i) printf("%lld %lld\n", i, i + 1);
  else for(i = 1; i < n; ++i) printf("%lld %lld\n", n - i + 1, n - i);
  return 0;
}

Measured memory_bytes: 128
#include "bits/stdc++.h"
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
int n;
cin >> n;
long long a[2*n+1];
for(int i = 0; i < 2*n; i++)cin >> a[i];
sort(a,a+2*n);
long long sum = 0;
for(int i = 0; i < 2*n; i+=2)
{
sum+=a[i];
}
cout << sum;
return 0;
}

Measured memory_bytes: 256