akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

const double eps = 1e-9;
bool same(double a, double b) { return abs(a - b) < eps; }

struct P {
    double x, y;
    P() : x(0), y(0) {}
    P(double x, double y) : x(x), y(y) {}
    P operator + (P b) { return P(x + b.x, y + b.y); }
    P operator - (P b) { return P(x - b.x, y - b.y); }
    P operator * (double b) { return P(x * b, y * b); }
    P operator / (double b) { return P(x / b, y / b); }
    double operator * (P b) { return x * b.x + y * b.y; }
    double operator ^ (P b) { return x * b.y - y * b.x; }
    double abs() { return hypot(x, y); }
    P unit() { return *this / abs(); }
    P spin(double o) {
        double c = cos(o), s = sin(o);
        return P(c * x - s * y, s * x + c * y);
    }
};

struct L {
    // ax + by + c = 0
    double a, b, c, o;
    P pa, pb;
    L() : a(0), b(0), c(0), o(0), pa(), pb() {}
    L(P pa, P pb) : a(pa.y - pb.y), b(pb.x - pa.x), c(pa ^ pb), o(atan2(-a, b)), pa(pa), pb(pb) {}
    P project(P p) { return pa + (pb - pa).unit() * ((pb - pa) * (p - pa) / (pb - pa).abs()); }
    P reflect(P p) { return p + (project(p) - p) * 2; }
    double get_ratio(P p) { return (p - pa) * (pb - pa) / ((pb - pa).abs() * (pb - pa).abs()); }
};

struct C {
    P c;
    double r;
    C() : r(0) {}
    C(P c, double r) : c(c), r(r) {}
};

bool parallel(L x, L y) { return same(x.a * y.b, x.b * y.a); }

P intersect(L x, L y) { return P(-x.b * y.c + x.c * y.b, x.a * y.c - x.c * y.a) / (-x.a * y.b + x.b * y.a); }

vector<L> tangent(C c1, C c2) {
#define Pij \
    P i = (c2.c - c1.c).unit() * c1.r, j = P(i.y, -i.x);\
    res.emplace_back(c1.c + i, c1.c + i + j);
#define deo(I,J) \
    double d = (c1.c - c2.c).abs(), e = c1.r I c2.r, o = acos(e / d);\
    P i = (c2.c - c1.c).unit(), j = i.spin(o), k = i.spin(-o);\
    res.emplace_back(c1.c + j * c1.r, c2.c J j * c2.r);\
    res.emplace_back(c1.c + k * c1.r, c2.c J k * c2.r);
    if (c1.r < c2.r) swap(c1, c2);
    vector<L> res;
    if ((c1.c - c2.c).abs() + c2.r < c1.r) return res;
    else if (same((c1.c - c2.c).abs() + c2.r, c1.r)) { Pij; } 
    else {
        deo(-,+);
        if (same(d, c1.r + c2.r)) { Pij; } 
        else if (d > c1.r + c2.r) { deo(+,-); }
    }
    return res;
}

int main() {
    C c[2];
    for (int i = 0; i < 2; ++i) cin >> c[i].c.x >> c[i].c.y >> c[i].r;
    vector<L> ls = tangent(c[0], c[1]);
    vector<P> ps;
    for (L &l : ls) ps.push_back(l.project(c[0].c));
    sort(ps.begin(), ps.end(), [&] (const P &a, const P &b) { return same(a.x, b.x) ? a.y < b.y : a.x < b.x; });
    for (P &p : ps) {
        cout << fixed << setprecision(10) << p.x << " " << p.y << endl;
    }
}



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

int main()
{
    ll k,x,y,z,n,w;
	ll sum=0,i,j;
	cin>>n;
	cin>>w;
	vector<pair<ll,ll> > h(n+1);
	
	for (i = 1; i <= n; ++i)
	{
		cin>>h[i].first>>h[i].second;
		sum+=h[i].second;
	}
	std::vector<ll> dp(sum+1,pow(10,17));
	dp[0]=0;
	for (i = 1; i <= n; ++i)
	{
		for (j = sum; j >= h[i].second; --j)
		{
			
				dp[j]=min(dp[j],h[i].first+dp[j-h[i].second]);
		}
	}
	for (i = 1; i <= sum; ++i)
	{
		if(dp[i]<=w)
			z=i;
	}
	cout<<z<<"\n";
}

Measured memory_bytes: 1024
let split_on_char sep s =
  let open String in
  let r = ref [] in
  let j = ref (length s) in
  for i = length s - 1 downto 0 do
    if get s i = sep then begin
      r := sub s (i + 1) (!j - i - 1) :: !r;
      j := i
    end
  done;
  sub s 0 !j :: !r

let () =
  let open Stack in
  let s = create () in
  List.iter (fun n ->
    if n <> "+" && n <> "-" && n <> "*" then push (int_of_string n) s
    else
      let x = pop s in
      let y = pop s in
      if n = "+" then push (y + x) s
      else if n = "-" then push (y - x) s
      else push (y * x) s)
    (read_line () |> split_on_char ' ');
  pop s |> Printf.printf "%d\n"

Measured memory_bytes: 2344
#include <bits/stdc++.h>
using namespace std;
const int MAX = 2*1000*100+10;
int n, m, a, b, fau[MAX], ile[MAX];
int Find(int x)
{
    if(fau[x] == x)
        return x;
    return fau[x] = Find(fau[x]);
}
void Union(int x, int y)
{
    fau[Find(x)] = fau[Find(y)];
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        fau[i] = i;
    for(int i = 1; i <= m; i++)
    {
        cin >> a >> b;
        Union(a, b);
    }
    int maxi = 0;
    for(int i = 1; i <= n; i++)
    {
        ile[Find(i)]++;
        maxi = max(maxi, ile[Find(i)]);
    }
    cout << maxi << "\n";
}


Measured memory_bytes: 10556
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const ll INF=1LL<<60;
 
int main() {
  ll n,m,k,t,b[2];
  scanf("%lld%lld%lld%lld%lld%lld",&n,&m,&k,&t,&b[0],&b[1]);
  int c[n];ll d[n];
  for(int i=0; i<n; i++) c[i]=1<<29,d[i]=INF;
  queue<int> que2;
  for(int i=0; i<k; i++) {
    int x;
    scanf("%d",&x);
    x--;
    c[x]=0;
    que2.push(x);
  }
  vector<int> v[n];
  for(int i=0; i<m; i++) {
    int x,y;
    scanf("%d%d",&x,&y);
    x--,y--;
    v[x].push_back(y);
    v[y].push_back(x);
  }
  while(!que2.empty()) {
    int x=que2.front();que2.pop();
    for(int i=0; i<v[x].size(); i++) {
      int y=v[x][i];
      if(c[y]<=c[x]+1) continue;
      c[y]=c[x]+1;
      que2.push(y);
    }
  }
  priority_queue<P,vector<P>,greater<P> > que;
  que.push(P(0,0));
  d[0]=0;
  while(!que.empty()) {
    P p=que.top();que.pop();
    ll x=p.second,cost=p.second;
    if(x==n-1) break;
    if(d[x]<cost) continue;
    for(int i=0; i<v[x].size(); i++) {
      int y=v[x][i];
      ll cc=d[x]+(c[y]>t?b[0]:b[1]);
      if(!c[y]) continue;
      if(d[y]>cc) {
        d[y]=cc;
        que.push(P(cc,y));
      }
    }
  }
  printf("%lld\n",d[n-1]-(c[n-1]>t?b[0]:b[1]));
  return 0;
}


Measured memory_bytes: 8764
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using P = pair<int,int>;
template <class T> void chmin(T &a, const T &b) noexcept { if (b < a) a = b; }
template <class T> void chmax(T &a, const T &b) noexcept { if (a < b) a = b; }
void debug_out() { cout << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cout << H << " "; debug_out(T...); }
#ifdef _DEBUG
  #define debug(...) debug_out(__VA_ARGS__)
#else
  #define debug(...) 
#endif

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(15);
  int n, p;
  cin >> n >> p;
  vector<int> a(n);
  int cnt0 = 0;
  rep(i,n) {
    cin >> a[i];
    a[i] %= 2;
    if (a[i] == 0) cnt0++;
  }
  int cnt1 = n - cnt0;
  debug(cnt0, cnt1);
  ll numzero = pow(2,cnt0), numone = 0;
  if (p == 1) {
    ll res = 1;
    for (int i = 1; i <= cnt1; ++i) { //奇数個
      res *= (cnt1 - i + 1);
      res /= i;
      if (i % 2 == 1) numone += res;
    }
  }
  else {
    ll res = 1;
    numone = 1; // {cnt1}C_0 の1通り
    for (int i = 1; i <= cnt1; ++i) { //偶数個
      res *= (cnt1 - i + 1);
      res /= i;
      if (i % 2 == 0) numone += res;
    }
  }
  debug(numzero, numone);
  ll ans = numone * numzero;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#define mod 1000000007
using namespace std;
int main(){
    long long n,x[26]={},ans=1;
    char s[100000];
    scanf("%lld",&n);
    scanf("%s",s);
    for(int i=0;i<n;i++){
        x[s[i]-'a']++;
    }
    for(int i=0;i<26;i++){
        ans*=x[i]+1;
        ans%=mod;
    }
    printf("%lld\n",ans-1);
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define FOR(i,n,j) for(int i=(j);i<(n);++i)
#define rrep(i,n) for(int i=(n);i>=0;--i)
#define ssort(n) sort((n).begin(),(n).end())
using ll=long long;
using ld=long double;
typedef pair<int,int> P;
#define Yes cout << "Yes" << endl
#define No cout << "No" << endl
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define INF 10101010

int main()
{
    int n;
    int k;
    cin >> n >> k;
    vector<ll> a(n);
    rep(i,n)cin >> a[i];

    rep(i,n-k){
        if(a[i]<a[k+i]){
            Yes;
        }else{
            No;
        }
    }
}

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

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

template<typename T> void chmin(T& a, T b) { a = (a > b) ? b : a; }
template<typename T> void chmax(T& a, T b) { a = (a < b) ? b : a; }
int in() { int x; scanf("%d", &x); return x; }

using namespace std;

typedef long long Int;
typedef unsigned uint;

string S;
int res;

int toInt(string s) {
	int ans = 0;
	
	for (int i = 0; i < (int) s.size(); i++) {
		ans = ans * 10 + (s[i] - '0');
	}

	return ans;
}

string toString(int s) {
	string ans = "";

	while (s > 0) {
		ans = char('0' + s % 10) + ans;
		s /= 10;
	}

	return ans;
}

bool evalR(string s) {
	vector<string> vs;

	for (int i = 0; i < s.size(); i++) {
		vs.push_back(string(1, s[i]));
	}

	for (int i = 0; i < vs.size(); i++) {
		if (vs[i] == "*") {
			int l = 0, r = 0;

			for (int j = 0; j < vs[i - 1].size(); j++) {
				l = l * 10 + (vs[i - 1][j] - '0');
			}

			for (int j = 0; j < vs[i + 1].size(); j++) {
				r = r * 10 + (vs[i + 1][j] - '0');
			}


			int ins = l * r;

			vs.erase(vs.begin() + i - 1, vs.begin() + i + 2);
			vs.insert(vs.begin() + i - 1, toString(ins));
			i--;
		}
	}
	
	for (int i = 0; i < vs.size(); i++) {
		if (vs[i] == "+") {
			int l = 0, r = 0;

			for (int j = 0; j < vs[i - 1].size(); j++) {
				l = l * 10 + (vs[i - 1][j] - '0');
			}

			for (int j = 0; j < vs[i + 1].size(); j++) {
				r = r * 10 + (vs[i + 1][j] - '0');
			}

			int ins = l + r;

			vs.erase(vs.begin() + i - 1, vs.begin() + i + 2);
			vs.insert(vs.begin() + i - 1, toString(ins));
			i--;
		}
	}	
	
	return toInt(vs[0]) == res;
}

bool evalF(string s) {
	vector<string> vs;

	for (int i = 0; i < s.size(); i++) {
		vs.push_back(string(1, s[i]));
	}
	
	for (int i = 0; i < vs.size(); i++) {
		if (vs[i] == "*" || vs[i] == "+") {
			int l = 0, r = 0;

			for (int j = 0; j < vs[i - 1].size(); j++) {
				l = l * 10 + (vs[i - 1][j] - '0');
			}

			for (int j = 0; j < vs[i + 1].size(); j++) {
				r = r * 10 + (vs[i + 1][j] - '0');
			}


			int ins = -1;

			if (vs[i] == "+") {
				ins = l + r;
			} else {
				ins = l * r;
			}

			vs.erase(vs.begin() + i - 1, vs.begin() + i + 2);
			vs.insert(vs.begin() + i - 1, toString(ins));
			i--;
		}
	}

	return toInt(vs[0]) == res;
}

int main(void) {
	cin >> S >> res;

	bool R = evalR(S);
	bool F = evalF(S);

	if (R && F) {
		cout << "U\n";
	} else if (R) {
		cout << "M\n";
	} else if (F) {
		cout << "L\n";
	} else {
		cout << "I\n";
	}

    return 0;
}

Measured memory_bytes: 1208
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;
using static System.Console;
using static System.Math;

namespace CP
{
    class Atria
    {
        static void Main(string[] args)
        {
            int n = int.Parse(ReadLine());
            var dic = new Dictionary<string, int>();
            for (int i = 0; i < n; i++)
            {
                string s = ReadLine();

                try
                {
                    dic.Add(s,1);
                }
                catch (Exception)
                {
                    dic[s]++;
                }
            }
            var d = dic.OrderByDescending(x => x.Value);
            int cnt = -1;
            var ans = new List<string>();
            foreach (var item in d)
            {
                if(cnt == -1)
                {
                    cnt = item.Value;
                }
                if (item.Value != cnt) break;
                ans.Add(item.Key);
            }
            var a = ans.ToArray();
            Array.Sort(a,StringComparer.OrdinalIgnoreCase);
            foreach (var item in a)
            {
                WriteLine(item);
            }
        }
    }
}


Measured memory_bytes: 47216
N,K = map(int,input().split())
pl = list(map(int,input().split()))

maxsum = sum(pl[:K])
maxindex = K-1

tmpsum = maxsum
for i in range(K,N):
    tmpsum = tmpsum - pl[i-K] + pl[i]
    if(tmpsum>maxsum):
        maxindex = i
        maxsum = tmpsum

anspl = pl[maxindex-K+1:maxindex+1]
print(sum(map(lambda x:x/2+0.5,anspl)))


Measured memory_bytes: 71792
#include<bits/stdc++.h>
using namespace std;
int ch(int a)
{
	int j=0;
	while(a>0)
	{
		a/=10;
		j++;
	}
	return j;
}
int main()
{
	int cnt=0;
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		if(ch(i)%2==1)
		{
			cnt++;
		}
	}
	printf("%d",cnt);
}

Measured memory_bytes: 256
def hasParent(id, n, h):
    pk = (id+1)//2
    if pk >= 1 and pk <= n:
        return "parent key = {}, ".format(h[pk-1])
    else:
        return ""


def hasChildren(id, n, h):
    lk = (id+1)*2
    rk = (id+1)*2+1
    ret = ""
    if lk >= 1 and lk <= n:
        ret = "left key = {}, ".format(h[lk-1])

    if rk >= 1 and rk <= n:
        ret += "right key = {}, ".format(h[rk-1])

    return ret


def main():
    N = int(input())
    H = list(map(int, input().split()))

    for node, key in enumerate(H):
        addtext = hasParent(node, N, H)
        addtext += hasChildren(node, N, H)

        print("node {}: key = {}, {}".format(node+1, key, addtext))


if __name__ == '__main__':
    main()


Measured memory_bytes: 5620
from math import sqrt
P = [map(int, raw_input().split()) for i in [0,1,2]]
def dist(p, q):
    return sqrt((p[0]-q[0])**2 + (p[1]-q[1])**2)
D = [dist(P[i-1], P[i]) for i in xrange(3)]
D = D*2

def rtanhalf(a, b, c):
    p = 2*a*b
    q = a**2 + b**2 - c**2
    return sqrt(float(q + p) / float(p - q))
def solve(a, b, c):
    s = rtanhalf(a, b, c)
    t = rtanhalf(c, b, a)
    r = b / (2. + s + t)
    return r
print max(solve(*D[i:i+3]) for i in xrange(3))


Measured memory_bytes: 2692
#include <bits/stdc++.h>
#define rep(i, n, m) for (int i = (int)(n); i < (int)(m); i++)
#define repr(i, n, m) for (int i = (int)(n) - 1; i >= (int)(m); i--)
using namespace std;
using ll = int64_t;
const int MOD = 1000000007; // 10^9+7

int main() {
    // https://atcoder.jp/contests/abc157/tasks/abc157_c

    int N, M;
    cin >> N >> M;
    vector<int> num(N, -1);

    rep(i, 0, M)
    {
        int s, c;
        cin >> s >> c;

        if (
            num[s - 1] != -1 && num[s - 1] != c
            || s == 1 && c == 0 && N != 1
        )
        {
            cout << -1 << endl;
            return 0;
        }

        num[s - 1] = c;
    }

    int ans = 0;
    rep(i, 0, N)
    {
        if(num[i] == -1)
        {
            if (N == 1) num[i] = 0;
            else if (i == 0) num[i] = 1;
            else num[i] = 0;
        }

        ans += num[i] * pow(10, N - i - 1); 
    }

    cout << ans << endl;
}


Measured memory_bytes: 384
#include<iostream>
#include<vector>
int main() {
	std::vector<int> a;
	while (true) {
		int i;
		std::cin >> i;
		if (i == 0) {
			break;
		}
		a.push_back(i);
	}
	for (int x = 0; x < a.size(); ++x) {
		std::cout << "Case " << x + 1 << ": " << a[x] << std::endl;
	}
}

Measured memory_bytes: 1320
N = int(input())
input_list = [int(i) for i in input().split()]

ans = 10 ** 20

for i in range(min(input_list), max(input_list)+1):
    ans1 = 0
    for input in input_list:
        ans1 += (i - input) ** 2
    ans = min(ans, ans1)

print(ans)

Measured memory_bytes: 3060
using System;

class Program
{
    static void Main()
    {
            int a, b, c, smp = 0;
            string inp = Console.ReadLine();
            string[] data = inp.Split(' ');
            a = int.Parse(data[0]);
            b = int.Parse(data[1]);
            c = int.Parse(data[2]);
            if (a >= 1 && a <= 10000 && b >= 1 && b <= 10000 && c >= 1 && c <= 10000)
            {
                if (b < a)
                {
                    smp = a;
                    a = b;
                    b = smp;
                }
                if (c < b)
                {
                    smp = b;
                    b = c;
                    c = smp;
                }
                if (b < a)
                {
                    smp = a;
                    a = b;
                    b = smp;
                }
                if (c < b)
                {
                    smp = b;
                    b = c;
                    c = smp;
                }
                Console.WriteLine("{0} {1} {2}", a, b, c);
            }
}
}


Measured memory_bytes: 9224
N=int(input())
A=list(map(int,input().split()))
A.sort()
flag=[0]*N
ans=[]
for i in range(1,N-1):
    if A[i]<0:
        ans.append([A[-1],A[i]])
        A[-1]-=A[i]
    else:
        ans.append([A[0],A[i]])
        A[0]-=A[i]
ans.append([A[-1],A[0]])
M=A[-1]-A[0]
print(M)
for u in ans:
    print(*u)

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

#define rep2(x,fr,to) for(int x=(fr);x<(to);x++)
#define rep(x,to) for(int x=0;x<(to);x++)
#define repr(x,fr,to) for(int x=(fr);x>=(to);x--)
#define all(c) c.begin(),c.end()
#define sz(v) (int)v.size()

using namespace std;
typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii;
typedef vector<ll> VL; const int MD = 1e9 + 7;
void dbg(){ cerr << "\n"; } template <typename T,typename ...T2> void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }

const double PI = acos(-1);
int main()
{
	cin.tie(0); ios_base::sync_with_stdio(false);
	int a, b, h, m;
	cin >>a >>b >>h >>m;
	
	double fn=m*6.0;
	double jk=30.0*h + 0.5*m;
	//dbg(fn, jk);
	
	double kd = abs(jk - fn);
	//if(kd > 180) kd = 360-kd;
	double z = a*a + b*b - 2*a*b*cos(kd*PI/180.0);
	//dbg(kd);
	printf("%.14f\n", sqrt(z));
	return 0;
	
}


Measured memory_bytes: 4212
import java.util.*;

class Main{
public static void main(String[] args){
	Scanner sc = new Scanner(System.in);
	int a = sc.nextInt();
	int b = sc.nextInt();
	int c = 0;
	int lB = 0;
	boolean flag = false;
	if(b / 100 > 0) {
		lB = 3;
	} else if(b / 10 > 0) {
		lB = 2;
	} else {
		lB = 1;
	}
	c = a * (int)Math.pow(10, lB) + b;
	for(int i = 1; i <  500; i++) {
		if(c == (int)Math.pow(i, 2)) {
			System.out.println("Yes");
			flag = true;
			break;
		}
	}
	if(flag == false) {
		System.out.println("No");	
	}
}
}


Measured memory_bytes: 23764
from collections import deque
N, X, Y = map(int, input().split())

pairs = [set() for _ in range(N)]

graph = [[] for _ in range(N)]
for i in range(N-1):
    graph[i].append(i+1)
    graph[i+1].append(i)

graph[X-1].append(Y-1)
graph[Y-1].append(X-1)

distCount = [0 for _ in range(N)]

for i in range(N):

    dist = [0 for _ in range(N)]
    visited = [False for _ in range(N)]
    queue = deque()
    queue.append(i)
    visited[i] = True

    #bfs
    while len(queue) > 0:
        now = queue.popleft()
        for adj in graph[now]:
            if visited[adj]:
                continue
            queue.append(adj)
            dist[adj] = dist[now] + 1
            visited[adj] = True


    for i in range(N):
        distCount[dist[i]] += 1

for i in range(1, N):
    print(distCount[i]//2)


Measured memory_bytes: 78044
import java.awt.Point;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.StringJoiner;

public class Main {

    static class UnionFind {
        private int[] parent;

        public UnionFind(int n) {
            parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        private int root(int x) {
            if (parent[x] == x) {
                return x;
            }
            return parent[x] = root(parent[x]);
        }

        private void unite(int x, int y) {
            int rx = root(x);
            int ry = root(y);
            if (rx == ry) {
                return;
            }
            parent[rx] = ry;
        }

        private boolean same(int x, int y) {
            int rx = root(x);
            int ry = root(y);
            return rx == ry;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int l = sc.nextInt();
        int[] p = new int[k];
        int[] q = new int[k];
        int[] r = new int[l];
        int[] s = new int[l];
        UnionFind uf1 = new UnionFind(n + 1);
        UnionFind uf2 = new UnionFind(n + 1);
        for (int i = 0; i < k; i++) {
            p[i] = sc.nextInt() - 1;
            q[i] = sc.nextInt() - 1;
            uf1.unite(p[i], q[i]);
        }
        for (int i = 0; i < l; i++) {
            r[i] = sc.nextInt() - 1;
            s[i] = sc.nextInt() - 1;
            uf2.unite(r[i], s[i]);
        }
        Map<Point, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            Point point = new Point(uf1.root(i), uf2.root(i));
            map.put(point, map.getOrDefault(point, 0) + 1);
        }
        StringJoiner sj = new StringJoiner(" ");
        for (int i = 0; i < n; i++) {
            sj.add(String.valueOf(map.get(new Point(uf1.root(i), uf2.root(i)))));
        }
        System.out.println(sj);
    }

}


Measured memory_bytes: 81584
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fr(i,a,b) for (ll i = (a), _b = (b); i <= _b; i++)
#define frr(i,a,b) for (ll i = (b), _a = (a); i >= _a; i--)
#define rep(i,n) for (ll i = 0, _n = (n); i < _n; i++)
#define repr(i,n) for (ll i = (n) - 1; i >= 0; i--)
#define debug(x) cout<<#x<<": "<<x<<endl
#define all(ar) ar.begin(), ar.end()
#define sz(x) ((long long)x.size())
#define pb push_back
#define pob pop_back()
#define pf push_front
#define pof pop_front()
#define mp make_pair
#define ff first
#define ss second
#define endl "\n"
#define trace2(x, y)            cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl;
#define trace3(x, y, z)         cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl;
#define trace4(a, b, c, d)      cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl;
#define trace5(a, b, c, d, e)   cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<<": "<<e<<endl;
 
typedef pair<ll, ll> ii;
typedef pair<ll, ii> iii;
typedef vector<ii> vii;
typedef vector<ll> vi;
typedef vector<string> vs;
typedef vector<vi> vvi;

ll const INF=1LL<<60LL;
double const pi=3.14159265358979323846264338327950; 

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

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

ll modpower(ll base,ll power,ll mod){
	ll res=1;
	while(power){
		if(power%2){
			res=(res*base)%mod;
			power--;
		}
		base=(base*base)%mod;
		power/=2;
	}
	return res;
}
ll const MAX=1000001;

void solve(){
	ll n;
	cin>>n;	
	n=n%10;
	if(n==2||n==4||n==5||n==7||n==9)cout<<"hon"<<endl;
	else if(n==3)cout<<"bon"<<endl;
	else cout<<"pon"<<endl;
}
    
int main () 
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout<<setprecision(11);
    #ifndef ONLINE_JUDGE
    freopen("inputf.in", "r", stdin);
    freopen("outputf.in", "w", stdout);
    #endif
 
    ll t=1;
    //cin>>t;
    while(t--){
        solve();
 
    }
 
    return 0;   
}

Measured memory_bytes: 3652
#include<stdio.h>
int main(){
  int n,d[110],c=1,s=0,i;
  scanf("%d",&n);
  for(i=0;i<n;i++)scanf("%d",&d[i]);
  d[n]=-1;
  for(i=0;i<n;i++){
    if(d[i]==d[i+1])c++;
    else{
      s+=c/2;
      c=1;
    }
  }
  printf("%d\n",s);
  return 0;
}
    


Measured memory_bytes: 128
//0019 Factorial

//nツつェツ禿シツ療債つウツづェツづゥ(ツつスツつセツつオ0<=n<=20)nツづ個階ツ湘ヲツづーツ出ツ療債つケツづヲ

//20!ツづ絞ntツづ可つィツつウツづ慊づィツづ慊つケツづア

#include<iostream>
using namespace std;
int main(void)
{
	long long n;
	cin >> n;
	long long x = 1;
	while(n)
	{
		x *= n;
		n--;
	}
	cout << x << 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++)
#define For(i,n1,n2) for(int i=n1;i<n2;i++)
#define REP(i,n) for(ll i=0;i<n;i++)
#define RREP(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,n1,n2) for(ll i=n1;i<n2;i++)
#define put(a) cout<<a<<"\n"
#define all(a)  (a).begin(),(a).end()
#define SORT(a) sort((a).begin(),(a).end())
#define oorret 0
#define oor(x) [&](){try{x;} catch(const out_of_range& oor){return oorret;} return x;}()
typedef long long ll;
typedef pair<int, int> P;
template<typename T1,typename T2> inline bool chmin(T1 &a,T2 b){if(a>b){a=b;return 1;}return 0;}
template<typename T1,typename T2> inline bool chmax(T1 &a,T2 b){if(a<b){a=b;return 1;}return 0;}

int main(){
    vector<int> a(5);
    vector<int> b(5);
    REP(i,5){
        cin >> a[i];
        b[i] = a[i]%10;
        if(b[i]==0)b[i]=10;
    }
    int res = 0;
    REP(i,5){
        res += (a[i]+9)/10*10;
    }
    res -= 10 - *min_element(all(b));
    put(res);
    return 0;
}


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

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

fn warshall_floyd(mut edges: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    for k in 0..edges.len() {
        for i in 0..edges.len() {
            for j in 0..edges.len() {
                edges[i][j] = std::cmp::min(edges[i][j], edges[i][k] + edges[k][j]);
            }
        }
    }
    edges
}

fn main() {
    let v = read_vec::<usize>();
    let (h, w) = (v[0], v[1]);
    let mut edges: Vec<Vec<i32>> = vec![vec![0; 10]; 10];

    for i in 0..10 {
        let v = read_vec::<i32>();
        for (j, &elem) in v.iter().enumerate() {
            // Change from i to j is elem.
            edges[i][j] = elem;
        }
    }
    let edges = warshall_floyd(edges);

    let mut ans = 0;
    for i in 0..h {
        let v = read_vec::<i32>();
        for elem in v {
            if elem != -1 {
                ans += edges[elem as usize][1];
            }
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define F first
#define S second
#define ll long long
#define ull  unsigned long long
#define pb push_back

using namespace std;
using namespace __gnu_pbds;
typedef  tree< int , null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int N = 3000000;
int mod = 1e9 + 7;
int a[N];
bitset < 4000000 > bs;
main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt","w", stdout);
    int n;
    cin >> n;
    bs[0] = 1;
    int s = 0;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        s += a[i];
        bs |= (bs << a[i]);
    }
    s = (s + 1) / 2;
    while(bs[s] == 0) s++;
    cout << s;
}


Measured memory_bytes: 1792
from collections import Counter
 
h, w = map(int, input().split())
a = Counter(''.join(input() for _ in range(h)))
 
center = h * w % 2 
side = (h//2) * (w%2) + (w//2) * (h%2)
corner = (h//2) * (w//2)

for _ in range(center):
    for i in a:
        if a[i] % 2 == 1:
            a[i] -= 1
            break
for _ in range(side):
    for j in a:
        if a[j] % 4 == 2:
            a[j] -= 2
            break

print('Yes' if sum(a[i]%4 for i in a) == 0 else 'No')


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef complex<double> Point;

#define PI acos(-1.0)
#define EPS 1e-10
const ll INF = 1e16;
const ll MOD = 1e9 + 7;

#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define rep(i,N) for(ll i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define EQ(a,b) (abs((a)-(b))<EPS)
#define EQV(a,b) ( EQ((a).real(), (b).real()) && EQ((a).imag(), (b).imag()) )
#define fi first
#define se second
#define N_SIZE (1LL << 20)
#define NIL -1

ll mod_add(ll a, ll b) { return (a + b) % MOD; }
ll mod_sub(ll a, ll b) { return (a - b + MOD) % MOD; }
ll mod_mul(ll a, ll b) { return a*b % MOD; }

int n;

int main(){
    cin >> n;
    ll ans = 0;
    int A = 0,B = 0,BA = 0;
    rep(i,n){
        string s;
        cin >> s;
        rep(j,s.size()-1){
            if(s[j] == 'A' && s[j+1] == 'B')ans++;
        }
        if(s[0] == 'B' && s.back() == 'A')BA++;
        else if(s[0] == 'B')B++;
        else if(s.back() == 'A')A++;
    }
    if(BA != 0){
        ans += BA - 1;
        if(A > 0){
            ans++;
            A--;
        }
        if(B > 0){
            ans++;
            B--;
        }
    }
    ans += min(A,B);
    cout << ans << endl;        
}

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

#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_CAT_I(x,y) x ## y
//#define CPP_STR(x) CPP_STR_I(x)
//#define CPP_STR_I(args...) #args
//#define ASSERT(expr...) assert((expr))

using i8 = int8_t;
using u8 = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
using f32 = float;
using f64 = double;
//using f80 = __float80;
#pragma endregion

#pragma region const
constexpr i64 INF = 1'010'000'000'000'000'017LL;
constexpr i64 MOD = 1'000'000'007LL;
constexpr f64 EPS = 1e-12;
constexpr f64 PI = 3.14159265358979323846;
#pragma endregion

#pragma region util
#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))

template<typename C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }
template<typename T, size_t N>
i64 SIZE(const T(&)[N]) { return static_cast<i64>(N); }

template<typename T, typename U, typename Comp = less<>>
bool chmax(T& xmax, const U& x, Comp comp = {}) {
	if (comp(xmax, x)) {
		xmax = x;
		return true;
	}
	return false;
}
template<typename T, typename U, typename Comp = less<>>
bool chmin(T& xmin, const U& x, Comp comp = {}) {
	if (comp(x, xmin)) {
		xmin = x;
		return true;
	}
	return false;
}
#pragma endregion

#pragma region init
struct ProconInit {
	static constexpr int IOS_PREC = 15;
	static constexpr bool AUTOFLUSH = false;

	ProconInit() {
		cin.tie(nullptr);
		ios::sync_with_stdio(false);
		cout << fixed << setprecision(IOS_PREC);
		if (AUTOFLUSH)
			cout << unitbuf;
	}
} PROCON_INIT;
#pragma endregion

int main()
{
	i64 D, N;
	cin >> D >> N;
	i64 ans = N * (i64)pow(100, D);
	if ((ans / (i64)pow(100, D)) % 100 == 0)
		ans += (i64)pow(100, D);
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef long double D;
//typedef complex<D> P;
#define F first
#define S second
const ll MOD=1000000007;
//const ll MOD=998244353;

template<typename T,typename U>istream & operator >> (istream &i,pair<T,U> &A){i>>A.F>>A.S; return i;}
template<typename T>istream & operator >> (istream &i,vector<T> &A){for(auto &I:A){i>>I;} return i;}
template<typename T,typename U>ostream & operator << (ostream &o,const pair<T,U> &A){o<<A.F<<" "<<A.S; return o;}
template<typename T>ostream & operator << (ostream &o,const vector<T> &A){int i=A.size(); for(auto &I:A){o<<I<<(--i?" ":"");} return o;}



int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll N,M,Q;
  cin>>N>>M;
  vector<vector<ll>> edge(N);
  for(int i=0;i<N;i++){edge[i].push_back(i);}
  for(int i=0;i<M;i++){
    int u,v;
    cin>>u>>v;
    u--; v--;
    edge[u].push_back(v);
    edge[v].push_back(u);
  }
  cin>>Q;
  vector<vector<int>> dp(N,vector<int>(11,-1));
  vector<int> col(Q);
  for(int i=0;i<Q;i++){
    int v,d,c;
    cin>>v>>d>>c;
    v--;
    col[i]=c;
    dp[v][d]=i;
  }
  for(int i=10;i>0;i--){
    for(int u=0;u<N;u++){
      for(auto &v:edge[u]){
        dp[v][i-1]=max(dp[v][i-1],dp[u][i]);
      }
    }
  }
  for(int i=0;i<N;i++){
    int mx=-1;
    for(int j=0;j<=10;j++){mx=max(mx,dp[i][j]);}
    cout<<(mx==-1?0:col[mx])<<endl;
  }


  return 0;
}


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

typedef long long ll;

int N;
char S[40], curr[20];
ll dp[20][20], tot;

int main() {
	scanf("%d", &N);
	scanf("%s", S);

	for (int msk = 0; msk < (1<<N); ++msk) {
		int cnt = 0, bcnt = 0;
		for (int i = 0; i < N; ++i) if ((msk>>i)&1) curr[cnt++] = S[i], bcnt++;
		for (int i = N; i--; ) if (!((msk>>i)&1)) curr[cnt++] = S[i];

		for (int i = 0; i < 20; ++i) for (int j = 0; j < 20; ++j) dp[i][j] = 0;

		dp[bcnt][N-bcnt] = 1;
		for (int i = 0; i <= N; ++i) for (int j = 0; j <= N; ++j) {
			if (i < N && S[i+j] == curr[i]) dp[i+1][j] += dp[i][j];
			if (j < N && S[i+j] == curr[N-j-1]) dp[i][j+1] += dp[i][j];
		}

		tot += dp[N][N];
	}

	printf("%lld\n", tot);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> Pi;
typedef unsigned long long ULL;
int gcd(int a,int b){if (b == 0) return a; return gcd(b , a%b);}
int lcm(int a, int b){ return a/gcd(a,b)*b;}
inline int read(){
    int f = 1, x = 0;char ch = getchar();
    while (ch > '9' || ch < '0'){if (ch == '-')f = -f;ch = getchar();}
    while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
    return x * f;
}
int main(){
    //freopen("/Users/chutong/data.txt", "r", stdin);
    string s;
    cin >> s;
    int len = (int)s.length();
    int mth = (s[len-5]-'0')*10 + s[len-4]-'0';
    int day = (s[len-2]-'0')*10 + s[len-1]-'0';
    if (mth > 4) cout << "TBD" << endl;
    else if (mth < 4) cout << "Heisei" << endl;
    else{
        if (day > 30) cout << "TBD" << endl;
        else cout << "Heisei" << endl;
    }
    return 0;
}



Measured memory_bytes: 256
#pragma GCC optimize("O3")
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;

using ll = long long;
using P = pair<int, int>;
using T = tuple<int, int, int>;

template <class T> inline T chmax(T &a, const T b) {return a = (a < b) ? b : a;}
template <class T> inline T chmin(T &a, const T b) {return a = (a > b) ? b : a;}

constexpr int MOD = 1e9 + 7;
constexpr int inf = 1e9;
constexpr long long INF = 1e18;

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

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

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

    string s; cin>>s;

    cout << (s.find('7') != string::npos ? "Yes" : "No") << endl;

    return 0;
}


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

typedef long long int ll;
#define loop(i,s,e) for(ll i=s;i<e;i++)
#define test ll x;cin>>x;while(x--)
#define pb push_back
#define vec vector<ll>
#define sortvec(x) sort(x.begin(),x.end())
#define sz(x) x.size()

int main () {
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	char a;
	cin>>a;
	if (a-97>=0)
		cout<<"a\n";
	else
		cout<<"A\n";
}


Measured memory_bytes: 3636
#include<iostream>
#include<algorithm>
#include<math.h>
#include<set>
#include<vector>
#include<string>
using namespace std;
int main() {
int x,a,b;
cin>>x>>a>>b;
if(abs(x-a)>abs(x-b))
cout<<'B'<<endl;
else
cout<<'A'<<endl;
}

Measured memory_bytes: 256
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#include <iostream>
#include <fstream>

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
using ll = long long;
constexpr ll INF = 1010000000000000017LL;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()

class CFlipFlipAndFlip {
public:
	void solve(std::istream& in, std::ostream& out) {
        ll n,m;
        in>>n>>m;
        if(n==2 || m==2){
            out<<0<<endl;
            return;
        } else if(n==1 && m==1){
            out<<1<<endl;
            return;
        } else if (n==1 || m==1){
            out<<max(n,m)-2<<endl;
            return;
        } else {
            out<<(m-2)*(n-2)<<endl;
            return;
        }
	}
};


int main() {
	CFlipFlipAndFlip solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


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

int main(){
	string S, T;
	cin >> S >> T;
	int p = 0;
	for(int i = 0; i < S.size(); i++){
		if(S[i] != T[i]){
			p = p + 1;
		}
	}
	
	if(p > 0){
		cout << "No" << endl;
	}else{
		cout << "Yes" << endl;
	}
	return 0;

}

Measured memory_bytes: 3132
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int mxn= 5e5+5;
// check for forloop
// intialize variable
// overflow
// go for easy solution
#define mod 1000000007
ll INF = 1000000000000000005LL;
#define endl '\n'
void rishabh(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}
int main(){
    rishabh();
    int n;
    cin>>n;
    int arr[n];
    for(int i=0;i<n;i++)cin>>arr[i];
    int mx=arr[0];
    int ans=1;
    for(int i=1;i<n;i++){
        mx=min(arr[i],mx);
        if(arr[i]>mx){
            continue;
        }
        else ans++;
    }
    cout<<ans;
}



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

int main() {
	int A, B, C, D, E, ans = 0;
	cin >> A >> B >> C >> D >> E;
	for (int i = A; i < B; ++i) {
		if (0 < i) ans += E;
		else if (0 == i) ans += D + E;
		else ans += C;
	}
	cout << ans << endl;
}


Measured memory_bytes: 3084
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define f first
#define s second
#define fastio ios_base::sync_with_stdio(false); cin.tie(0)
#define loop(i, a, b) for(lli i=a; i<b; i++)
#define loopb(i, a, b) for(lli i=a; i>=b; i--)
#define pb push_back
typedef long long int lli;
typedef pair<lli, lli> pii;
typedef vector<lli> vll;
// use to avoid collision
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
// for pair in unordered_map
struct hash_pair {
    template <class T1, class T2>
    size_t operator()(const pair<T1, T2>& p) const
    {
        auto hash1 = hash<T1>{}(p.first);
        auto hash2 = hash<T2>{}(p.second);
        return hash1 ^ hash2;
    }
};
lli power(lli x, lli y, lli p){
    lli res = 1;
    x = x % p;
    while (y > 0) {
        if (y & 1)
            res = (res*x) % p;
        y = y>>1;
        x = (x*x) % p;
    }
    return res;
}
vector<vll> S;
vll dp;
lli M = 1e9 + 7;
lli bitmask(lli mask){
	if(mask == 0)
		return 0;
	if(dp[mask] != -1)
		return dp[mask];
	lli p = 0;
	vll pos;
	lli n = S.size();
	lli res = 0;
	loop(j, 0, n){
		if(1<<j & mask){
			p++;
			pos.pb(j);
		}
	}
	if(p == 1){
		if(S[0][pos[0]] == 1)
			res = 1;
		else
			res = 0;
	}
	else{
		loop(j, 0, p){
			lli temp = bitmask(mask - (1<<pos[j]));
			res = (res + (S[p-1][pos[j]] == 1 ? temp : 0))%M;
		}
	}
	dp[mask] = res;
	return dp[mask];
}
lli solve(){
	lli n;
	cin>>n;
	S.clear();
	S.resize(n, vll(n));
	loop(i, 0, n)	
		loop(j, 0, n)	cin>>S[i][j];
	dp.clear();
	lli N = pow(2, n);
	dp.resize(N, -1);
	dp[0] = 1;
	// iterative method
	
/*	loop(i, 1, N){
		lli p = 0;
		vll pos;
		loop(j, 0, n){
			if(1<<j & i){
				p++;
				pos.pb(j);
			}
		}
		if(p == 1){
			if(S[0][pos[0]] == 1)
				dp[i] = 1;
			else
				dp[i] = 0;
		}
		else{
			loop(j, 0, p){
				dp[i] = (dp[i] + (S[p-1][pos[j]] == 1 ? dp[i - (1<<pos[j])] : 0))%M;
			}
		}
//		cout<<i<<" "<<p<<" "<<dp[i]<<"\n";
	}
*/
	// recursive method
	bitmask(N-1);
	cout<<dp[N-1]<<"\n";
	return 0;
}
int main(){
	fastio;
	lli t;
//	cin>>t;
	t = 1;
	while(t>0){
		t--;
		solve();
	}
}


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

int main()
{
    int n;
    cin >> n;
    vector<int> A(n);
    int mod = 1000000007;
    long long sum = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> A[i];
        sum += A[i];
        sum %= mod;
    }

    long ans = 0;
    rep(i, n)
    {
        sum -= A[i];
        if (sum < 0)
            sum += mod;

        ans += A[i] * sum;
        ans %= mod;
    }

    cout << ans << endl;
}

Measured memory_bytes: 3972
#include <bits/stdc++.h>
#define ll long long
#define sz(x) (int)(x).size()
using namespace std;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//uniform_int_distribution<int>(1000,10000)(rng)

ll binpow(ll a, ll b)
{
    if (b == 0)
        return 1;
    ll res = binpow(a, b / 2);
    res*=res;
    if (b % 2)
        return res * a;
    return res;
}

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

string to_upper(string a)
{
    for (int i=0;i<(int)a.size();++i) if (a[i]>='a' && a[i]<='z') a[i]-='a'-'A';
    return a;
}
 
string to_lower(string a)
{
    for (int i=0;i<(int)a.size();++i) if (a[i]>='A' && a[i]<='Z') a[i]+='a'-'A';
    return a;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    string s,t;
    cin>>s>>t;
    int n=sz(s),m=sz(t),ans=sz(t),cur;
    for (int i=0;i+m-1<n;++i)
    {
        cur=0;
        for (int j=0;j<m;++j)
            if (s[i+j]!=t[j])
                ++cur;
        ans=min(ans,cur);
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 3656
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <iostream>
#include <sstream>
#include <climits>
#include <cfloat>
#include <complex>

using namespace std;

int main()
{
	int x, y;
	while (scanf("%d %d", &x, &y), x | y)
	{
		int topo[15 + 1][15 + 2];
		memset(topo, 0, sizeof(topo));
		for (int i = 0; i < y; ++i)
			for (int j = 1; j <= x; ++j)
				scanf("%d", &topo[i][j]);

		int dp[15 + 1][15 + 2];
		memset(dp, 0, sizeof(dp));
		for (int i = 1; i <= x; ++i)
			if (topo[0][i] != 1)
				dp[0][i] = 1;

		for (int i = 0; i < y-1; ++i)
		{
			for (int j = 1; j <= x; ++j)
			{
				if (topo[i][j] == 0)
				{
					for (int k = -1; k <= 1; ++k)
						if (topo[i+1][j+k] != 1 && (topo[i+1][j+k] == 0 || k == 0))
							dp[i+1][j+k] += dp[i][j];
				}
				else if (topo[i][j] == 2 && topo[i+2][j] != 1)
					dp[i+2][j] += dp[i][j];
			}
		}
		int ans = 0;
		for (int i = 1; i <= x; ++i)
			ans += dp[y-1][i] + dp[y][i];
		printf("%d\n", ans);
	}

	return 0;
}

Measured memory_bytes: 0
#include<stdio.h>
#define MAX 30
#define NIL -1
struct Node_struct{int p, l, r, s;}; 
typedef struct Node_struct Node;
Node T[MAX];
int D[MAX];
int Deg[MAX];
int H[MAX];

void print(int u){
 int i, c;
 printf("node %d: parent = %d, sibling = %d, degree = %d, depth = %d, height = %d", u, T[u].p, T[u].s, Deg[u], D[u], H[u]);

 if(D[u] == 0) printf(", root");
 else if(H[u] == 0) printf(", leaf");
 else printf(", internal node");

 printf("\n");

}

void printPre(int u){
  if(u == NIL)
    return;
  printf(" %d",u);
  printPre(T[u].l);
  printPre(T[u].r);
}

void printIn(int u){
  if(u == NIL)
    return;
  printIn(T[u].l);
  printf(" %d",u);
  printIn(T[u].r);
}

void printPost(int u){
  if(u == NIL)
    return;
  printPost(T[u].l);
  printPost(T[u].r);
  printf(" %d",u);
}

void calcDegree(int u){
  if(T[u].r != NIL){
    Deg[u]++;
    calcDegree(T[u].r);
  }
  if(T[u].l != NIL){
    Deg[u]++;
    calcDegree(T[u].l);
  }
}

void calcDepth(int u, int p){
 D[u] = p;
 if(T[u].r != NIL) calcDepth(T[u].r,p+1);
 if(T[u].l != NIL) calcDepth(T[u].l,p+1);
}

int calcHeight(int u){
  int l=0,r=0;
  if(T[u].r == NIL && T[u].l == NIL){
    H[u] = 0;
    return 0;
  }
  if(T[u].r != NIL)r = calcHeight(T[u].r)+1;
  if(T[u].l != NIL)l = calcHeight(T[u].l)+1;
  if(l>r)H[u] = l;
  else H[u] = r;
  return H[u];
}

int main(){
 int i, j, k;
 int n;
 int id, child;
 int root = NIL;
 scanf("%d", &n);
 for(i=0; i<n; i++) T[i].p = T[i].l = T[i].r = T[i].s = NIL;

 for(i=0; i<n; i++){
   scanf("%d", &id);
   for(j = 0; j<2; j++){ //子を入力する (input children)
     scanf("%d", &child);
     T[child].p = id;
     if(j == 0) T[id].l = child; //idの一番左の子 (the most left child of id)
     else{
       T[id].r = child;
       T[T[id].r].s = T[id].l;
       T[T[id].l].s = T[id].r;
     } //左の兄弟に繋げる (connect to left sibling)
     //次の子供の左の兄弟 (the left sibling of the next child)
   }
 }

 //根を求める (find the root)
 for(i=0; i<n; i++){
   if(T[i].p == -1) root = i;
 }

 printf("Preorder\n");
 printPre(root);
 printf("\nInorder\n");
 printIn(root);
 printf("\nPostorder\n");
 printPost(root);
 printf("\n");

 //calcDegree(root);

 //それぞれのノードの深さを求める (find depth of each node)
 //calcDepth(root, 0);

 //calcHeight(root);

 //出力 (output)
 //for(i=0; i<n; i++) print(i);

 return 0;
}



Measured memory_bytes: 2048
import Data.List
import Data.Maybe

main = print . solve . map read . drop 1 . words =<< getContents

solve :: [Int] -> Int
solve ss
    | t `rem` 10 /= 0 = t
    | otherwise = (maybe 0 (t -) $ find ((/=0) . (`rem` 10)) ss')
    where
        ss' = sort ss
        t = sum ss


Measured memory_bytes: 892
import std.stdio, std.string, std.conv;
import std.range, std.algorithm, std.array, std.typecons, std.container;
import std.math, std.numeric, core.bitop;


void main() {
    int a, b, c;
    long k;
    scan(a, b, c, k);

    writeln(k & 1 ? b - a : a - b);
}













































void scan(T...)(ref T args) {
    import std.stdio : readln;
    import std.algorithm : splitter;
    import std.conv : to;
    import std.range.primitives;

    auto line = readln().splitter();
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}



void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}


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

using namespace std;

const long long mod = 1e9 + 7;

long long fpow(long long a, long long b) { long long ret = 1; while (b) { if (b & 1) ret = ret * a %mod; a = a * a % mod; b >>= 1; } return ret; }

int main() {
    long long n, k; cin >> n >> k;
    long long gcd[k+1] = {};
    for (int i = 1; i <= k; i++)
        gcd[i] = fpow(k / i, n);
    for (int i = k / 2; i >= 1; i--)
        for (int j = i + i; j <= k; j += i)
            gcd[i] -= gcd[j];
    for (int i = 1; i <= k; i++)
        gcd[i] = i * gcd[i] % mod;
    cout << accumulate(gcd + 1, gcd + 1 + k, 0LL) % mod;
}

Measured memory_bytes: 4376