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

#define dump(...) do{print_vars(cout<<"# "<<#__VA_ARGS__<<'=',__VA_ARGS__);cout<<endl;}while(0)
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define peri(i,a,b) for(int i=int(b);i-->int(a);)
#define rep(i,n) repi(i,0,n)
#define per(i,n) peri(i,0,n)
#define all(c) begin(c),end(c)
#define mp make_pair
#define mt make_tuple

using uint=unsigned;
using ll=long long;
using ull=unsigned long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using vd=vector<double>;
using vvd=vector<vd>;
using vs=vector<string>;

template<typename T,typename U>bool chmin(T& a,const U& b){return a>b?(a=b,1):0;}
template<typename T,typename U>bool chmax(T& a,const U& b){return a<b?(a=b,1):0;}

void print_vars(ostream&){}
template<typename Car,typename... Cdr>
void print_vars(ostream& os,const Car& car,const Cdr&... cdr){
	print_vars(os<<car<<(sizeof...(cdr)?",":""),cdr...);
}

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

template<int I,typename Tuple>
void print_tuple(ostream&,const Tuple&){}
template<int I,typename Car,typename... Cdr,typename Tuple>
void print_tuple(ostream& os,const Tuple& t){
	os<<get<I>(t)<<(sizeof...(Cdr)?",":"");
	print_tuple<I+1,Cdr...>(os,t);
}
template<typename... Args>
ostream& operator<<(ostream& os,const tuple<Args...>& t){
	print_tuple<0,Args...>(os<<'(',t);
	return os<<')';
}

template<typename Ch,typename Tr,typename C>
basic_ostream<Ch,Tr>& operator<<(basic_ostream<Ch,Tr>& os,const C& c){
	os<<'[';
	for(auto i=begin(c);i!=end(c);++i)
		os<<(i==begin(c)?"":" ")<<*i;
	return os<<']';
}

constexpr int INF=1e9;
constexpr int MOD=1e9+7;
constexpr double EPS=1e-9;

int main()
{
	#ifndef _GLIBCXX_DEBUG
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	constexpr char endl='\n';
	#endif

	for(int n,m;cin>>n>>m&&n|m;){
		vvi d(m,vi(m));
		vvi c(n,vi(n));
		rep(i,m) rep(j,m) cin>>d[i][j];
		rep(i,n) rep(j,n) cin>>c[i][j],c[i][j]--;

		vector<map<int,int>> fs(3);
		rep(i,n) rep(j,n) fs[(i+j)%3][c[i][j]]++;

		int res=INF;
		rep(i,m) rep(j,m) rep(k,m) if(i!=j&&j!=k&&k!=i){
			int sum=0;
			for(auto p:fs[0]) sum+=d[p.first][i]*p.second;
			for(auto p:fs[1]) sum+=d[p.first][j]*p.second;
			for(auto p:fs[2]) sum+=d[p.first][k]*p.second;
			chmin(res,sum);
		}
		cout<<res<<endl;
	}
}


Measured memory_bytes: 1280
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
	int max, min, s = 0, N;
	cin >> N;
	int a[N];
	cin >> s;
	max = s;
	min = s;
	for (int i = 1; i < N; i++) {
		cin >> s;
		if (s > max)
			max = s;
		else if (s < min)
			min = s;
	}
	cout << max - min;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define rep(i,b) for(ll i=0;i<b;i++)
#define ll long long
using namespace std;
/*--Input//////////////////////////////////////////////////*/
inline void IN(void){return;}
template <typename First, typename... Rest>
void IN(First& first, Rest&... rest){cin >> first;IN(rest...);return;}
#define SS(T, ...)      T __VA_ARGS__; IN(__VA_ARGS__);
#define SV(type,c,n) vector<type> c(n);for(auto& i:c)cin >> i;
/*--Output/////////////////////////////////////////////////*/
inline int p(void){cout << endl; return 0;}
template<class Head> int p(Head&& head){cout << head;p();return 0;} template<class Head,class... Tail> int p(Head&& head,Tail&&... tail){cout<<head<<" ";p(forward<Tail>(tail)...);return 0;}
struct ProconInit {
    static constexpr bool AUTOFLUSH = false;
    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(20);
        if(AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;

#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl10
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define vl vector<ll>
#define debug(x) cerr<<#x<<" "<<x<<'\n';
#define all(x) (x).begin(),(x).end()
#define bit(n) (1LL<<(n))
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; }
bool cmp(pair<ll,ll> a, pair<ll,ll> b) { return a.first+a.second > b.first+b.second; }

signed main() {
  SS(long double,a,b);
  ll ans=floor(a*b);
  p(ans);
  
}


Measured memory_bytes: 3748
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define mp make_pair
#define pb push_back
#define ip pair<ll,ll>
#define ff first
#define ss second
#define MAX 100005
const ll MOD = 1000000007;

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

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

	int x;
	cin>>x;
	cout<< 360/gcd(360,x) <<endl;
}

Measured memory_bytes: 3548
#include <stdio.h>

int main() {
	int a,b,c;
	scanf ("%d %d %d",&a,&b,&c);
	if (a==b&&b==c&&a==c) {
	printf("%d\n",1);
	} else if (a!=b&&b!=c&&a!=c) { 
	printf("%d\n",3) ;
} else { printf("%d\n",2);
}	return 0; 
    
}
	

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

int main() {
    int n;
    cin >> n;
    vector<int> h(n);
    for(int i=0; i<n; i++){
        cin >> h[i]; 
    }
    vector<ll> ans(n);
    ans[n-1] = 0;
    for(int i=n-2; i>=0; i--){
        if(h[i] >= h[i+1]){
            ans[i] = ans[i+1] + 1;
        }else{
            ans[i] = 0;
        }
    }
    cout << *max_element(ans.begin(), ans.end()) << endl;
    return 0;
}

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

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 main() {
  int n;
  cin >> n;
  vector<string> s(n);
  rep(i, n) cin >> s[i];

  int last_a = 0;
  int first_b = 0;
  int both_ba = 0;
  int ab = 0;
  rep(i, n){
    int siz = s[i].size();
    if(s[i][0] == 'B' && s[i][siz-1] == 'A') both_ba++;
    else if (s[i][0] == 'B') first_b++;
    else if (s[i][siz-1] == 'A') last_a++;
    rep(j, siz-1){
      if(s[i][j] == 'A' && s[i][j+1] == 'B'){
        ab++;
      }
    }
  }

  if(both_ba == 0){
    ab += min(last_a, first_b);
  }
  else{
    if(last_a + first_b > 0){
      ab += both_ba + min(last_a, first_b);
    }
    else{
      ab += both_ba - 1;
    }
  }
  cout << ab << endl;
  return 0;
}


Measured memory_bytes: 768
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;

int main(){

	int N;
	while(1){
		cin>>N;if(N==0)break;
	int s[15]={};
	for(int i=0;i<N;i++)
		cin>>s[i];

	int a[15]={};
	
	for(int i=0;i<N;i++){int p=0;
	for(int j=0;j<N;j++)
	{if(s[i]==s[j])p++;}
	a[i]=p;
	}

	int X=0;
	while(1){bool F=true;
		for(int i=0;i<N;i++)
			if(a[i]!=s[i])F=false;

		if(F==true)break;
		for(int i=0;i<N;i++)
			s[i]=a[i];
		for(int i=0;i<N;i++){int p=0;
	for(int j=0;j<N;j++)
	{if(s[i]==s[j])p++;}
	a[i]=p;
	}
		X++;
	}

	cout<<X<<endl;
	for(int i=0;i<N;i++)
	{	if(i>0)cout<<" ";cout<<a[i];

	
	}
	cout<<endl;
	}
	return 0;
}

Measured memory_bytes: 1160
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stdio.h>
using namespace std;
#define int long long
int MOD = 1000000007;
vector<vector<int> > g;
vector<int> C;
vector<int> res;
int dfs(int a, int p = -1, int sum = 0) {
	sum += C[a];
	res[a] = sum;
	for (int i : g[a]) {
		if (i != p) {
			dfs(i, a, sum);
		}
	}
}
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N, Q;;
	cin >> N >> Q;
	g.resize(N);
	C.resize(N, 0);
	res.resize(N);
	int a, b;
	for (int i = 0; i < N - 1; i++) {
		cin >> a >> b; a--; b--;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	for (int i = 0; i < Q; i++) {
		cin >> a >> b; a--;
		C[a] += b;
	}
	dfs(0);
	for (int i = 0; i < N; i++) {
		if (i > 0)cout << " ";
		cout << res[i];
	}
	cout << endl;
}

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

int main() {
  int A, B, C, D;
  cin >> A >> B >> C >> D;

  if (A + B > C + D ) {
    cout << "Left" << endl;
  }
  
  else if (A + B == C + D ) {
    cout << "Balanced" << endl;
  }
  
  else if (A + B < C + D ) {
    cout << "Right" << endl;
  }
}

Measured memory_bytes: 3592
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 202020;
const int P = 998244353;
char s[MAXN], t[MAXN];
bool vis[MAXN];
int n, ans, val[MAXN];
void update(int &x, int y)
{
	x += y;
	if (x >= P)
		x -= P;
}
int cnt(int x)
{
	int ans = 0;
	for (int i = 1; i <= x; i++)
		ans = ((ans * 2) + (s[i] - '0')) % P;
	int tmp = 1;
	for (int i = 1; i <= n; i++)
	{
		if(tmp <= x)
			t[i] = s[tmp];
		else
			t[i] = s[tmp - x] ^ 1;
		tmp = (tmp == 2 * x) ? 1 : (tmp + 1);
	}	
	for (int i = 1; i <= n; i++)
	{
		if (s[i] > t[i])
			return ans + 1;
		if (t[i] > s[i])
			return ans;
	}
	return ans + 1;
}
int main()
{
	scanf("%d", &n);
	scanf("%s", s + 1);
	for (int i = 1; i <= n; i++)
		if (n % i == 0 && (n / i) % 2 == 1)
			vis[i] = true;
	int ans = 1ll * cnt(n) * (2 * n) % P;
	for(int i = n - 1; i >= 1; i--)
	{
		if(!vis[i])
			continue;
		int tmp = 2 * n;
		for(int j = i; j <= n; j += i)
			if(vis[j])
				update(tmp, val[j]);
		val[i] = 2 * i;
		update(val[i], P - tmp);
		update(ans, 1ll * cnt(i) * val[i] % P);
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 4320
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <math.h>
#include <vector>
#include <ctype.h>
#include <assert.h>

using namespace std;
typedef long long ll;
static const long long BASE = 1000000;
static const int  BW = 6;
static const int MAXDIGIT = 20;

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define DEC(i, s) for (int i = (s); i >= 0; i--)

#define SIZE(v) (int)((v).size())
#define MEMSET(v, h) memset((v), h, sizeof(v))
#define FIND(m, w) ((m).find(w) != (m).end())

struct Node {
  ll length;
  ll size;
  ll loop;
  char c;
  vector<Node> child;
  Node() : length(0), size(0), loop(1), c(0) {;}
};

char str[1000];

Node parse(ll &index) {
  ll loop = 1;
  Node ret;
  if (isalpha(str[index])) {
    ret.length = 1;
    ret.c = str[index];
    index++;
  } else if (isdigit(str[index])) {
    loop = atoi(str + index);
    while (isdigit(str[index])) { index++; }
    if (isalpha(str[index])) {
      ret.child.push_back(parse(index));
      ret.length += ret.child[ret.child.size() - 1].size;
    } else {
      assert(str[index] == '(');
      index++;
      while (str[index] != ')') {
        ret.child.push_back(parse(index));
        ret.length += ret.child[ret.child.size() - 1].size;
      }
      assert(str[index] == ')');
      index++;
    }
  }
  ret.size = ret.length * loop;
  ret.size = min(ret.size, 1000000000LL);
  ret.length = min(ret.length, 1000000000LL);
  ret.loop = loop;
  return ret;
}

char nodechar(const Node &node, ll &n) {
  if (node.size <= n) { return '0'; }
  n %= node.length;
  if (n == 0 && node.c != 0) { return node.c; }
  REP(i, node.child.size()) {
    const Node &target = node.child[i];
    if (target.size > n) {
      return nodechar(target, n);
    }
    n -= target.size;
  }
  assert(false);
  return 0;
}

int main() {
  ll n;
  while (scanf("%s %lld", str, &n), str[0] != '0' || n) {
    ll index = 0;
    Node root;
    while (str[index] != '\0') {
      root.child.push_back(parse(index));
      root.size += root.child[root.child.size() - 1].size;
      root.length += root.size;
    }
    printf("%c\n", nodechar(root, n));
  }
}

Measured memory_bytes: 0
open System
open System.Collections.Generic

let ReadOne T = stdin.ReadLine()|> T
let ReadSplit T = stdin.ReadLine().Split()|>Array.map T
[<EntryPoint>]
let main argv =
    let a,b,c=stdin.ReadLine().Split()|>fun p -> int p.[0],int p.[1],int p.[2]
    let K=ReadOne int
    let rec fn x num = if num=K then x else fn (x*2) (num+1)
    let m =max (max a b) c
    (a+b+c)-m+(fn m 0)
    |>stdout.WriteLine
    0


Measured memory_bytes: 11220
import java.util.*;
import java.io.*;

class Main {

	void solve() {

		out.println(Math.min(inint(), inint()) + Math.min(inint(), inint()));

	}

	public static Scanner in = new Scanner(System.in);
	public static PrintWriter out = new PrintWriter(System.out);

	public static void main(String[] args) {
		new Main().solve();
		out.flush();
	}

	public int inint() {
		return in.nextInt();
	}

	public long inlong() {
		return in.nextLong();
	}
	
	public String instr() {
		return in.next();
	}

	public int[] inintar(int num) {
		int[] a = new int[num];
		for (int i=0; i<num; i++) {
			a[i] = in.nextInt();
		}
		return a;
	}

	public char[] incharar() {
		return in.next().toCharArray();
	}

}

Measured memory_bytes: 21716
/// kazuki08
/*
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int long long
typedef long long ll;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<pi> vpi;
#define ar array
//#define inf 1000000000
#define mod 1000000007
#define dmp(x) cerr<<"line "<<__LINE__<<" "<<#x<<":"<<x<<endl
#define fs first
#define sc second
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define mt make_tuple
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
    return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
    o<<"{";
    for(const T& v:vc) o<<v<<",";
    o<<"}";
    return o;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAXN = 202000;
int valc[MAXN],valr[MAXN],donec[MAXN],doner[MAXN];
int n,q;

signed main(){
IOS;
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
  
  cin >> n >> q;
  priority_queue<int> qc,qr;
  int ans = (n-2)*(n-2);
  for(int i=2;i<n;i++){
    valc[i]=n-1;
    valr[i]=n-1;
    qc.push(i);
    qr.push(i);
  }
  int minr = n-1, minc = n-1;
  for(int i=1;i<=q;i++){
    int x,type;
    cin >> type >> x;
    if(type==1){
      if(donec[x]){
        ans-=(valc[x]-1);
      }
      else {
        while(qc.size() && qc.top()>=x){
          int cur = qc.top();qc.pop();
          valc[cur] = minr;
          donec[cur]=1;
          // cerr << type << " " << cur << " " << minr << endl;
        }
        ans-=(valc[x]-1);
      }
      minc = min(minc,x-1);
    }
    else {
      if(doner[x]){
        ans-=(valr[x]-1);
      }
      else {
        while( qr.size() && qr.top()>=x){
          int cur = qr.top();qr.pop();
          valr[cur] = minc;
          doner[cur]=1;
        }
        ans-=(valr[x]-1);
      }
      minr = min(minr,x-1);
    }
  }
  cout << ans << endl;

return 0;
}
///....


Measured memory_bytes: 12972
#include <bits/stdc++.h>
using LL = long long;
const LL MOD = 1e9+9;
using namespace std;



int main(){
    int h,w;cin >> h >> w;
    int a,b;cin >> a >> b;
    cout<<h*w-((h/a)*a*(w/b)*b)<<endl;;
}



Measured memory_bytes: 3072
import java.util.Scanner;
public class Main{
	public static void main(String[] args){
		Scanner scanner = new Scanner(System.in);
		String a = scanner.next();
		String b = scanner.next();
		String c = scanner.next();
		String A = a.toUpperCase();
		String B = b.toUpperCase();
		String C = c.toUpperCase();
		System.out.printf("%c%c%c",A.charAt(0),B.charAt(0),C.charAt(0));
	}
}

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

int main() {
  int N, K;
  cin >> N >> K;
  vector<int> h(N), dp(N, 0);
  for (int i=0;i<N;i++){
    cin >> h[i];
  }
  for (int i=1;i<N;i++){
    if (i==1){
      dp[1] = abs(h[1] - h[0]);
      continue;
    }
    
    int MIN = 1000000000;
    int k = min(i, K);
    for (int j=1;j<k+1;j++){
        MIN = min(MIN, dp[i-j] + abs(h[i] - h[i-j]));
      }
      dp[i] = MIN;
  }
  cout << dp[N-1] << endl;
}


Measured memory_bytes: 3960
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(x) (x).begin(),(x).end()
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;}

vector<int> a;

int f(int k){
    int ret = 0;
    for(auto t : a){
        ret += (t-k)*(t-k);
    }
    return ret;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;cin>>n;
    a.resize(n);
    rep(i,n) cin>>a[i];
    int ans = 1e9;
    for(int i=-100; i<=100;i++){
        chmin(ans, f(i));
    }
    cout<<ans<<endl;
    return 0;


}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(void)
{
	int H, W;
	cin >> H >> W;

	char mat[102][102];
	for (int i = 0; i < 102; i++) {
		for (int j = 0; j < 102; j++) {
			mat[i][j] = '#';
		}
	}

	for (int i = 1; i < H + 1; i++) {
		for (int j = 1; j < W + 1; j++) {
			cin >> mat[i][j];
		}
	}

	for (int i = 0; i < H + 2; i++) {
		for (int j = 0; j < W + 2; j++) {
			cout << mat[i][j];
		}
		cout << endl;
	}

	return 0;
}

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

int main()
{
  string S;
  cin >> S;
  int year = stoi(S.substr(0, 4));
  int month = stoi(S.substr(5,2));
  if(year >= 2019 && month >= 5)
    cout << "TBD" << endl;
  else
    cout << "Heisei" << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <vector>

using namespace std;

/////////////         qsortのラッピング

int qsort_int_compare_ascend(const void *a, const void *b) {
	return *(int*)a - *(int*)b;
}
int qsort_int_compare_descend(const void *a, const void *b) {
	return *(int*)b - *(int*)a;
}
void ascendOrder(int size, int *array) {//昇順
	qsort(array, size, sizeof(int), qsort_int_compare_ascend);
}
void descendOrder(int size, int *array) {//降順
	qsort(array, size, sizeof(int), qsort_int_compare_descend);
}
int qsort_long_compare_ascend(const void *a, const void *b) {//long型
	long c = *(long*)a - *(long*)b;
	if (c > 0) { return 1; }
	else if (c < 0) { return -1; }
	return 0;
}
int qsort_long_compare_descend(const void *a, const void *b) {//long型
	long c = *(long*)b - *(long*)a;
	if (c > 0) { return 1; }
	else if (c < 0) { return -1; }
	return 0;
}
void ascendOrder(int size, long *array) {//昇順
	qsort(array, size, sizeof(long), qsort_long_compare_ascend);
}
void descendOrder(int size, long *array) {//降順
	qsort(array, size, sizeof(long), qsort_long_compare_descend);
}

int main() {
	int N;
	long *A;
	cin >> N;
	A = new long[N * 3];
	for (int i = 0; i < N * 3; i++) {
		cin >> A[i];
	}

	ascendOrder(N * 3, A);

	long sum = 0;
	for (int i = N; i < N * 3; i+=2) {
		sum += A[i];
	}
	cout << sum << endl;

	return 0;
}

Measured memory_bytes: 4988
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<string>
#include<cstring>
using namespace std;
typedef long long ll;
ll a[200005];
int main()
{  ll i,n,sum=0,t,t1=0,t2;
   cin>>n;
   queue<ll>Q;
   Q.push(1);
   Q.push(2);
   Q.push(3);
   Q.push(4);
   Q.push(5);
   Q.push(6);
   Q.push(7);
   Q.push(8);
   Q.push(9);
   while(Q.size())
   {  t=Q.front();
      a[++t1]=t;
      t2=a[t1]%10;
      if(t2==0)
      { Q.push(a[t1]*10+t2);
        Q.push(a[t1]*10+t2+1);
        
	  }
	  if(t2>0&&t2<9)
	  { 
	    Q.push(a[t1]*10+t2);
        Q.push(a[t1]*10+t2-1);
        Q.push(a[t1]*10+t2+1);
	  }
	  if(t2==9)
      { Q.push(a[t1]*10+t2);
        Q.push(a[t1]*10+t2-1);
        
	  }
	  if(t1>=n+10000)
	   break;
	   Q.pop();
}
   sort(a+1,a+t1+1);
   cout<<a[n]<<endl;
   
}

Measured memory_bytes: 2816
from math import factorial

N, M = map(int, input().split())
mod = 10**9+7

if abs(N-M) > 1:
    print(0)
    quit()

else:
    if N == M:
        #犬猿or猿犬をひとかたまりとして考える。
        NM_half = N
        #犬猿どっちが右かを区別する
        ans = 2
        # ans %= mod 
        #個別の犬、猿がどこに立つかを考慮する
        ans *= factorial(N)
        ans %= mod
        ans *= factorial(M)
        ans %= mod

        print(ans)
    else:
        ans = factorial(N)
        ans %= mod
        ans *= factorial(M)
        ans %= mod

        print(ans)


Measured memory_bytes: 4092
#include <bits/stdc++.h>
using namespace std;
int nextInt() {
  int x;
  cin >> x;
  return x;
}
int main() {
  int n;
  cin >> n;
  set<int> A;
  while (n--) A.insert(nextInt());
  int m;
  cin >> m;
  set<int> B;
  while (m--) B.insert(nextInt());
  set<int> C;
  for (auto a : A)
    if (B.find(a) == B.end()) C.insert(a);
  for (auto c : C) cout << c << endl;

  return 0;
}


Measured memory_bytes: 31144
#include<stdio.h>
int main(void){
long long int A,B, gcd, multi;
scanf("%lld%lld", &A, &B);
multi=A*B;
for(int i=1;i<=A && i<=B;i++){
    if(A%i==0 && B%i==0){
        gcd=i;
    }
}
printf("%lld\n", multi/gcd);
return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>
#include <set>
#include <map>
#include <cassert>
#include <cstdio>
#include <cstdlib>

using namespace std;

set<long long> p;
long long n,a;

int main(int argc,char** argv) {
	cin >> n;
	for(long long i = 0;i < n;i++) {
		cin >> a;
		if(p.find(a) == p.end()) p.insert(a);
		else p.erase(a);
	}
	cout << p.size();
}


Measured memory_bytes: 4864
n=int(input())
A,C,G,T,M,R=0,1,2,3,10**9+7,range(4)
dp=[[[[0]*4for k in R]for j in R]for i in range(n+1)]
dp[0][T][T][T]=1
for i in range(1,n+1):
  for j in R:
    for k in R:
      for l in R:
        for m in R:
          if(G,A,C)!=(k,l,m)!=(A,C,G)!=(k,l,m)!=(A,G,C)!=(j,l,m)!=(A,G,C)!=(j,k,m):dp[i][k][l][m]=(dp[i][k][l][m]+dp[i-1][j][k][l])%M
print(sum(c for a in dp[n]for b in a for c in b)%M)

Measured memory_bytes: 3316
x1,y1,x2,y2=map(int,input().split())
W,H=x2-x1,y2-y1
print(("R"*W)+("U"*H)+("L"*W)+("D"*H)+"D"+("R"*(W+1))+("U"*(H+1))+"LU"+("L"*(W+1))+("D"*(H+1))+"R")

Measured memory_bytes: 3060
#include <stdio.h>
int main(){
	char o[55], e[55];
	int index = 0;
	scanf(" %s %s", o, e);
	while(1){
		if(o[index] != '\0'){
			printf("%c", o[index]);
		}else break;
		if(e[index] != '\0'){
			printf("%c", e[index]);
		}else break;
		index++;
	}
	printf("\n");
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
queue<int> q;
int n,m;
vector<int> v[100010];
int a[100010];
int par[100010];
int main()
{
	cin >>n>>m;
	for (int i=0;i<n+m-1;i++)
	{
		int x,y;
		cin >>x>>y;
		x--,y--;
		v[x].push_back(y);
		a[y]++;
	}
	for (int i=0;i<n;i++)
	{
		if (!a[i])
		{
			q.push(i);
			break;
		}
	}
	while (!q.empty())
	{
		int x=q.front();
		q.pop();
		for (int i=0;i<v[x].size();i++)
		{
			int xi=v[x][i];
			a[xi]--;
			if (!a[xi])
			{
				q.push(xi);
				par[xi]=x+1;
			}
		}
	}
	for (int i=0;i<n;i++) cout <<par[i]<<"\n";
	return 0;
}

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

int N;
int a[200000];

int C[30];
int G[30][200000];

int check(int x,int id){
  int mask=(1<< (id+1) )-1;
  int nx=x&mask;
  /*
  if(x==3 && id==1){
    cout<<mask<<' '<<nx<<endl;

    for(int p:G[id]){
      cout<<p<<endl;
    }
  }
  */
  int left = (1<<id);
  int right = (1<< (id+1) );



  int* itA;
  int* itB;
  int* itC;

  //  int tmp2 = Count( G[id] , left+right - nx, 1e9 )&1;
  itA = lower_bound(G[id],G[id]+N, left+right-nx);
  
  //  int tmp = Count( G[id] , left- nx, right-nx )&1;  
  itB = lower_bound(G[id],G[id]+N, left-nx);
  itC = lower_bound(G[id],G[id]+N, right-nx);
  int res = (itC-itB) + (G[id]+N-itA);
  return res&1;
}

int solve(int x){
  int res=0;
  for(int i=0;i<30;i++){
    if( check(x,i) )
      res|=(1<<i);
  }
  return res;
}

int main(){
  scanf("%d",&N);
  for(int i=0;i<N;i++){
    scanf("%d",&a[i]);
    for(int id=0;id<30;id++){
      int mask = (1<< (id+1) )-1;
      G[id][i]=( a[i] & mask );
    }
  }

  for(int i=0;i<30;i++){
    sort(G[i],G[i]+N);
  }
  
  int ans=0;
  for(int i=0;i<N;i++){
    int x;
    scanf("%d",&x);
    
    //    cout<<x<<"="<<solve(x)<<endl;
    ans^=solve(x);
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 24448
#include<iostream>
#include<string>
#include<vector>
#include<iomanip>
#include<algorithm>
#include<queue>
#include<stack>
#include<list>
#include<map>
#include<deque>
#include<math.h>
using namespace std;
#define ll long long
#define MOD 1000000007
int main(){
    ll N,K;
    cin >> N >> K;
    ll ans=0,i,j;
    for(i=K;i<=N+1;i++){
        ans=(ans+(2*N-i+1)*i/2-i*(i-1)/2+1)%MOD;
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 3164
use std::cmp::Ordering;
use std::collections::BinaryHeap;
const INF:i64 = std::i64::MAX;

#[derive(PartialEq, Debug)]
struct MinInt {
    value:i64,
}

impl Eq for MinInt {}

impl PartialOrd for MinInt {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        other.value.partial_cmp(&self.value)
    }
}

impl Ord for MinInt {
    fn cmp(&self, other: &MinInt) -> Ordering {
        other.value.cmp(&self.value)
    }
}

fn make_pair(x: i64, y:usize) -> (MinInt, usize) {
    (MinInt{value: x}, y)
}

#[derive(Debug, Clone)]
struct Edge {
    to: usize,
    cost: i64
}

fn solve(edges: &Vec<Vec<Edge>>, start_idx: usize, num_apexes: usize) -> Vec<i64> {
    let mut d: Vec<i64> = vec![INF; num_apexes];
    d[start_idx] = 0;
    let mut que = BinaryHeap::new();
    que.push(make_pair(0, start_idx));

    while let Some((u, v)) = que.pop() {
        if d[v] < u.value {
            continue
        }
        for e in &edges[v] {
            if d[e.to] > d[v] + e.cost {
                d[e.to] = d[v] + e.cost;
                que.push(make_pair(d[e.to], e.to));
            }
        }
    }
    d
}


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 main() {
    let v:Vec<i64> = read_vec();
    let (n, m, s, t) = (v[0], v[1], v[2] - 1, v[3] - 1);
    let mut edges:Vec<Vec<Edge>> = vec![Vec::new(); 2 * m as usize];
    let mut sunuke_edges:Vec<Vec<Edge>> = vec![Vec::new(); 2 * m as usize];

    for i in 0..m {
        let vv:Vec<i64> = read_vec();
        let (u1, v1, a1, b1) = (vv[0] - 1, vv[1] - 1, vv[2], vv[3]);
        edges[v1 as usize].push(Edge{to: u1 as usize, cost: a1});
        edges[u1 as usize].push(Edge{to: v1 as usize, cost: a1});

        sunuke_edges[u1 as usize].push(Edge{to: v1 as usize, cost: b1});
        sunuke_edges[v1 as usize].push(Edge{to: u1 as usize, cost: b1});
    }
    let s = s as usize;
    let t = t as usize;
    let n = n as usize;
    let yen_costs = solve(&edges, s, n);
    // println!("{:?}", yen_costs);
    let sunuke_costs = solve(&sunuke_edges, t, n);
    // println!("{:?}", sunuke_costs);
    let mut all_costs:Vec<i64> = vec![0; n];


    for i in 0..n {
        all_costs[i] = yen_costs[i] + sunuke_costs[i];
    }
    // println!("{:?}", all_costs);

    let mut min_cost = INF;
    let mut min_costs:Vec<i64> = vec![0; n];
    for i in 0..n {
        min_cost = std::cmp::min(all_costs[n - 1 - i], min_cost);
        min_costs[n - i - 1] = min_cost;
    }
    // println!("{:?}", min_costs);
    for i in 0..n {
        println!("{:?}", 1000000000000000 - min_costs[i]);
    }
}


Measured memory_bytes: 36604
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
int main()
{
	int a,b;
	cin>>a>>b;
	if(a%3==0||b%3==0||(a+b)%3==0)puts("Possible");
	else puts("Impossible");
	return 0;
}

Measured memory_bytes: 256
// Created by js0805
#include <bits/stdc++.h>
#include<algorithm>
#include<vector>
#include<string>
#define ll long long
#define fr(a,b) for(ll i=a;i<b;i++)
#define prDouble(x) cout << fixed << setprecision(10) <<x
using namespace std;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef set<int> si;
typedef map<string, int> msi;
string solve(int a[], int n, int k) {
    bool dp[k + 1];
    memset(dp, 0, sizeof dp);
    for (int i = 1; i <= k; i++) {
        for (int j = 0; j < n; j++) {
            if (a[j] > i) {
                continue;
            }
            if (dp[i - a[j]] == 0) {
                dp[i] = 1;
            }
        }
    }
    return dp[k] ? "First" : "Second";
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t, k;
    cin >> t >> k;
    int a[t];
    fr(0, t) cin >> a[i];
    cout << solve(a, t, k);
    return 0;
}

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

int main() {
  
 	

    int k,x;
    cin>>k>>x;

    vector<int> v;

    for(int i=((x-k)+1);i<(x+k);i++)
    {
         v.push_back(i);
    }
    int n=v.size();

    for(int i=0;i<n;i++)
    {
    	cout<<v[i]<<" ";
    }

    return 0;
}

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

const int MOD = 1000000007;

const int INF_32 = 1LL << 30;
const int64_t INF_64 = 1LL << 60;

int main()
{
    int N;
    cin >> N;
    vector<int> h(N);
    rep(i, N) cin >> h.at(i);

    vector<int> dp(N);
    dp.at(0) = 0;
    dp.at(1) = abs(h.at(1) - h.at(0));
    for (int i = 2; i < N; i++) {
        dp.at(i) = min(dp.at(i - 1) + abs(h.at(i) - h.at(i - 1)), dp.at(i - 2) + abs(h.at(i) - h.at(i - 2)));
    }

    cout << dp.at(N - 1) << endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using ll= long long;
using vi = vector<int>;
using vl= vector<ll>;
using vs=vector<string>;

ll gcd(ll a, ll b) { if (a == 0) return b; return gcd(b % a, a);}
ll max(ll a, ll b) {if (a > b) return a; else return b;}
ll min(ll a, ll b) {if (a < b) return a; else return b;}
ll power(ll a,ll b) {long long res = 1; while (b > 0) {if (b & 1)res = res * a;a = a * a;b >>= 1;} return res;}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int testcase=1;
    
    for(int p=0;p<testcase;p++){
string s1="AC";
    string s2="WA";
    string s3="TLE";
    string s4="RE";
        ll n=0;
	cin>>n;
        ll hashtable[4]={0};
        for(int i=0;i<n;i++){
            string s;
            cin>>s;
            if(s==s1)
            hashtable[0]++;
            else if(s==s2)
            hashtable[1]++;
            else if(s==s3)
            hashtable[2]++;
            else
            hashtable[3]++;
            
        }
        cout<<"AC x "<<hashtable[0]<<"\n";
        cout<<"WA x "<<hashtable[1]<<"\n";
        cout<<"TLE x "<<hashtable[2]<<"\n";
        cout<<"RE x "<<hashtable[3]<<"\n";
        
        
                }

    return 0;
}


Measured memory_bytes: 3652
from __future__ import print_function

import sys

import re
import array
import copy
import functools
import operator

import math
import string
import fractions
from fractions import Fraction
from fractions import gcd
# fractions.gcd() を用いること
# math.log2()はatcoderでは対応していない．留意せよ．

import collections
import itertools
import bisect

import random
import time

import heapq
from heapq import heappush
from heapq import heappop
from heapq import heappushpop
from heapq import heapify
from heapq import heapreplace
from queue import PriorityQueue as pq
from queue import Queue

from itertools import accumulate

from collections import deque
from collections import Counter

from operator import mul
from functools import reduce

input = sys.stdin.readline


def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return


def lcm(n, m):
    return int(n * m / gcd(n, m))


def coprimize(p, q):
    common = fractions.gcd(p, q)
    return (p // common, q // common)


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


def find_gcd(list_l):
    x = reduce(gcd, list_l)
    return x


def main():
    n,m = map(int,input().strip().split())
    a = list(map(int, input().strip().split()))
    a.sort(reverse=True)
    eprint('a ',end=':\n')
    eprint(a)
    eprint('sum(a)/(4*m) ',end=':\n')
    eprint(sum(a)/(4*m))
    if a[m-1] >= sum(a)/(4*m) :
        print("Yes")
    else:
        print("No")


if __name__ == '__main__':
    main()

Measured memory_bytes: 6596
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define MOD 1000000007
#define rep(i,n) for(i=0;i<n;i++)
#define loop(i,a,n) for(i=a;i<n;i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

typedef vector<int> vi;
typedef pair<int,int> pii;

int main(void) {
  int i,j;
  int n,m;
  cin>>n>>m;
  vector<vi> g(n);
  rep(i,m){
      int a,b;
      cin>>a>>b;
      a--;b--;
      g[a].push_back(b);
      g[b].push_back(a);
  }

  vector<bool> used(n,false);
  vi path;
  int pt=0;
  rep(i,n) if(g[i].size()>0){
    pt=i;
    break;
  }

  while(1){
    bool c=false;
    rep(j,g[pt].size()){
        int next=g[pt][j];
        if(used[next]==false){
            pt=next;
            path.push_back(pt);
            used[next]=true;
            c=true;
            break;
        }
    }
    if(c==false)break;
  }

  pt=path[0];
  reverse(all(path));

  while(1){
    bool c=false;
    rep(j,g[pt].size()){
        int next=g[pt][j];
        if(used[next]==false){
            pt=next;
            path.push_back(pt);
            used[next]=true;
            c=true;
            break;
        }
    }
    if(c==false)break;
  }

  cout<<path.size()<<endl;
  rep(i,path.size()){
     cout<<path[i]+1;
     if(i<path.size()-1)cout<<" ";
     else cout<<endl;
  }                      

}


Measured memory_bytes: 6776
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007

#A
def A():
    x, a, b = LI()
    if abs(x - a) > abs(x - b):
        print("B")
    else:
        print("A")
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    A()


Measured memory_bytes: 4336
#include<vector>
#include<iostream>
#include<string>
#include<algorithm>
#include<math.h>
#include<map>
#include<functional>
#include<queue>
#include<stack>
#include<string.h>
#define ll long long int
#define MOD 1000000007LL
using namespace std;
int main() {
    int n;
    cin>>n;
    string s,t;
    cin>>s>>t;
    for(int i=n;i<=2*n;i++){
        int k=i-n;
        for(int j=0;j<2*n-i;j++){
            if(s[k+j]!=t[j]){
                break;
            }else if(j==2*n-i-1){
                cout<<i<<endl;
                return 0;
            }
        }
    }
    cout<<2*n<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> //gp_hash_table
#include <ext/pb_ds/tree_policy.hpp> // tree<int, null_type, less, rb_tree_tag, tree_order_statistics_node_update>

using namespace std;
using namespace __gnu_pbds;

#define hashmap gp_hash_table

typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; //find_by_order, order_of_key

const int N = (int) 3e3 + 10;
const int MOD = 998244353;

int n, S;
int a[N];
int memo[N][N][4];

int dp(int at, int S, int mask) {
    if(S < 0) return 0;
    if(at == n) return S == 0 && (mask == 0b11 || mask == 0b01);
    int& ans = memo[at][S][mask];
    if(ans != -1) return ans;
    ans = 0;
    if(mask == 0) {
        ans = (ans + dp(at, S, 0b01)) % MOD; //turn it on
        ans = (ans + dp(at + 1, S, mask)) % MOD; //keep it off
    } else if(mask == 0b01) { //can skip, take, or close it
        ans = (ans + dp(at + 1, S, mask)) % MOD; //skip
        ans = (ans + dp(at + 1, S - a[at], mask)) % MOD; //take
        ans = (ans + dp(at + 1, S, 0b11)) % MOD; //close
    } else { //closed, can only continue
        ans = (ans + dp(at + 1, S, mask)) % MOD;
    }
    return ans;
}

void solve() {
    cin >> n >> S;
    for(int i = 0; i < n; ++i) cin >> a[i];
    memset(memo, -1, sizeof(memo));
    cout << dp(0, S, 0) << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.precision(20);
    cout << fixed;
    solve();
    cout.flush();
    return 0;
}

Measured memory_bytes: 142080
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for(int i=0;i<(int)n;i++)
ll mod=1e9+7;
#define PI acos(-1)
struct edge{int from, to;};

int main(){
    int n;
    cin>>n;
    vector<int> a(n),t(n);
    rep(i,n) cin>>a[i];
    t=a;
    sort(a.begin(), a.end(), greater<int>());

    rep(i,n){
        if(t[i]==a[0]) cout<<a[1]<<endl;
        else cout<<a[0]<<endl;
    }
    return 0;
}

Measured memory_bytes: 3200
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long int ll;

#define MAXN 200005

int n,k;
int h[MAXN];

int main(){

	cin >> n >> k;
	for( int i = 0; i < n; i++ )
		cin >> h[i];

	sort( h, h+n );

	ll res = 0;
	for( int i = 0; i < (n-k); i++ ){
		res += h[i];
	}

	cout << res << endl;
	
}


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


int main(void)
{double a,b,c;
	while (scanf("%lf %lf",&a,&b)!= EOF) {
	c = log10((a + b))+1;
		

	printf("%d\n",(int)c);

	}
	return 0;
}
	

Measured memory_bytes: 668
#include<iostream>
#include<map>
using namespace std;
typedef pair<int,int> P;
map< P , bool >t;
int n,m;
P u[200],v[1000];
int ansy,ansx;
int main(){
  while(1){
    cin>>m;
    if(m==0)break;
    t.clear();
    for(int i=0;i<m;i++){
      cin>>u[i].first>>u[i].second;
    }
    cin>>n;
    for(int i=0;i<n;i++){
      cin>>v[i].first>>v[i].second;
      t[v[i]]=true;
    }
    
    for(int i=0;i<n;i++){
      int j;
      int dx=v[i].first-u[0].first;
      int dy=v[i].second-u[0].second;
      for(j=1;j<m;j++){
	P p = P(u[j].first+dx,u[j].second+dy);
	if(!t[p])break;
      }
      if(j==m){
	ansx=dx,ansy=dy;
      }
    }
    cout<<ansx<<' '<<ansy<<endl;
  }
  return 0;
}

Measured memory_bytes: 1324
//tree DP
//ABC036-D
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<stdbool.h>
#include<time.h>
#define inf 1072114514
#define llinf 4154118101919364364
#define mod 1000000007
#define pi 3.1415926535897932384

int max(int a,int b){if(a>b){return a;}return b;}
int min(int a,int b){if(a<b){return a;}return b;}
int zt(int a,int b){return max(a,b)-min(a,b);}

typedef struct{
int val;
int node;
}sd;

int sdsortfnc(const void *a,const void *b){
if(((sd*)a)->val > ((sd*)b)->val){return -1;}
if(((sd*)a)->val < ((sd*)b)->val){return 1;}
return 0;
}

typedef struct{
    long long st;
    long long fi;
    long long kr;
}rs;

typedef struct{
    long long st;
    long long kz;
}mkj;

int sortfnc(const void *a,const void *b){
if(((rs*)a)->st == ((rs*)b)->st){return 0;}
if(((rs*)a)->st < ((rs*)b)->st){return -1;}
return 1;
}

void makemkj(rs g[],mkj x[],long long n){
    long long i,ms=0,nst=g[0].st;
    for(i=1;i<n;i++){
        if(g[i].st!=g[i-1].st){
            x[nst].kz=i-ms;
            x[nst].st=ms;
            nst=g[i].st;ms=i;
        }
    }
    x[nst].kz=n-ms;
    x[nst].st=ms;
}

long long dist[524288],par[524288];
void dfs(long long t,long long l,long long bp,rs g[],mkj x[]){
  long long i;
  if(dist[t]<=l){return;}
  dist[t]=l;
  par[t]=bp;
  for(i=x[t].st;i<x[t].st+x[t].kz;i++){
    dfs(g[i].fi,l+1,t,g,x);
  }
}

long long power(long long a,long long b){
  long long x=1,y=a;
  while(b>0){
    if(b&1ll){
      x=(x*y)%mod;
    }
    y=(y*y)%mod;
    b>>=1;
  }
  return x%mod;
}

long long modular_inverse(long long n){
  return power(n,mod-2);
}


int main(void){
    long long i,j,n,m,k,a,b,c,h,w,r=0,l,t;
    long long res=0;
    long long dp[524288]={0};
    long long arr[524288],ac;
    rs g[524288];
    mkj x[524288];
    sd dat[524288];
    scanf("%lld",&n);
    for(i=0;i<(n-1);i++){
      scanf("%lld%lld",&a,&b);
      g[2*i].st=a;
      g[2*i].fi=b;
      g[2*i].kr=1;
      g[2*i+1].st=b;
      g[2*i+1].fi=a;
      g[2*i+1].kr=1;
    }
    qsort(g,2*(n-1),sizeof(g[0]),sortfnc);
    makemkj(g,x,2*(n-1));
    for(i=0;i<=n;i++){
      dist[i]=inf;
    }
    dfs(1,0,-1,g,x);
    for(i=0;i<n;i++){
      dat[i].node=i+1;
      dat[i].val=dist[i+1];
    }
    qsort(dat,n,sizeof(dat[0]),sdsortfnc);
    b=modular_inverse(power(2,n-1));
    for(i=0;i<n;i++){
      w=dat[i].node;
      ac=0;c=0;
      for(j=x[w].st;j<x[w].st+x[w].kz;j++){
        if(g[j].fi==par[w]){continue;}
        arr[ac]=dp[g[j].fi];
        c+=dp[g[j].fi];
        ac++;
      }
      arr[ac]=(n-1)-c;
      ac++;
      t=(mod+1-b)%mod;
      for(j=0;j<ac;j++){
        t+=(mod-((b*(mod+power(2,arr[j])-1))%mod));
        t%=mod;
      }
      //printf("%lld %lld\n",w,t);
      r+=t;r%=mod;
      dp[w]=c+1;
    }
    printf("%lld\n",(r*modular_inverse(2))%mod);
    return 0;
}


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

int main() {
	int a, b, c;
	cin >> a >> b >> c;
	if (!(a & 1) || !(b & 1) || !(c & 1)) { printf("0"); return 0; }
	int x[3] = { a,b,c };
	sort(x, x + 3);
	printf("%lld", (ll)x[0] * x[1]);
}

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

int main()
{
    long long n,i;
    double x;
    cin>>n;
    long long a[n], ans;
    ans=1;
    for (i = 0; i < n; i++) cin>>a[i];
    for (i = 0; i < n; i++)
    {
        x+=log10(a[i]);
    }
    if (x>18) ans=-1;
    else
    {
        for (i = 0; i < n; i++)
        {
            ans*=a[i];
            if (ans>1000000000000000000)
            {
                ans=-1;
                break;
            }
        }
        for (i = 0; i < n; i++)
        {
            if (a[i]==0)
            {
            ans=0;
            break;
            }
        }
    }
    cout<<ans<<endl;
}

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

const long long MOD = 1000000007;

void solve(long long N) {
	vector<int> morty(N+1,0);
  	for(int i  = 2;i<=N;i++){
      int x = i;
    	for(int i1 = 2;i1<=i;i1++){
        	while(x%i1 == 0){morty[i1]++;x/=i1;}
        }
    }
  	long long  rick = 1;
  	for(int i = 2;i<=N;i++){rick = rick*(morty[i]+1)%MOD;}
                            cout<<rick;
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You
// use the default template now. You can remove this line by using your custom
// template)
int main() {
  long long N;
  scanf("%lld", &N);
  solve(N);
  return 0;
}


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

using ll=long long;
struct RLEchar{
    char x;
    ll len;
};

using RLE=vector<RLEchar>;
istream& operator>>(istream& in,RLE& rle){
    char c;
    while(cin>>c,c!='$'){
        int l; cin>>l;
        rle.push_back(RLEchar{c,l});
    }
    return in;
}
ostream& operator<<(ostream& out,RLE rle){
    for(int i=0;i<rle.size();i++){
        out<<rle[i].x<<" "<<rle[i].len<<" ";
    }
    out<<"$";
    return out;
}

void shrink(RLE &rle){
    RLE res;
    for(int i=0;i<rle.size();i++){
        if(rle[i].len==0) continue;
        else if(res.size()==0 || res.back().x!=rle[i].x) res.push_back(rle[i]);
        else res.back().len+=rle[i].len;
    }
    rle=res;
}

void replace(RLE& a,RLE b,RLE c){
    for(int i=0;i+b.size()<=a.size();i++){
        if(b.size()==1){
            if(a[i].x==b[0].x && a[i].len>=b[0].len){
                RLE tmp;
                for(int j=0;j<i;j++){
                    tmp.push_back(a[j]);
                }
                for(int j=0;j<c.size();j++) tmp.push_back(c[j]);
                tmp.push_back(RLEchar{a[i].x,a[i].len-b[0].len});
                for(int j=i+1;j<a.size();j++){
                    tmp.push_back(a[j]);
                }
                a=tmp;
                break;
            }
        }
        else{
            bool isok=(a[i].x==b[0].x && a[i].len>=b[0].len);
            for(int j=1;j+1<b.size();j++){
                isok&=(a[i+j].x==b[j].x && a[i+j].len==b[j].len);
            }
            isok&=(a[i+b.size()-1].x==b.back().x && a[i+b.size()-1].len>=b.back().len);
            if(isok){
                RLE tmp;
                for(int j=0;j<i;j++){
                    tmp.push_back(a[j]);
                }
                tmp.push_back(RLEchar{a[i].x,a[i].len-b[0].len});
                for(int j=0;j<c.size();j++) tmp.push_back(c[j]);
                tmp.push_back(RLEchar{a[i+b.size()-1].x,a[i+b.size()-1].len-b.back().len});
                for(int j=i+b.size();j<a.size();j++){
                    tmp.push_back(a[j]);
                }
                a=tmp;
                break;
            }
        }
    }
    shrink(a);
}

int main(){
    RLE a,b,c;
    cin>>a>>b>>c;
    replace(a,b,c);
    cout<<a<<endl;
    return 0;
}


Measured memory_bytes: 3272
#include<iostream>
#include<string>
using namespace std;
int main(){
  string str;
  getline(cin,str);
  int i;
  for(i=0;i<str.size();i++){
    if(str[i]>='a'&&str[i]<='z') str[i]+='A'-'a';
    else if(str[i]>='A'&&str[i]<='Z') str[i]+='a'-'A';
  }
    cout << str << endl;
  return 0;
}



Measured memory_bytes: 3160
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define INF 1e9
#define PI 3.14159265359
#define MOD 1000000007
#define ALL(v) v.begin(),v.end()
#define ALLR(v) v.rbegin(),v.rend()
typedef long long ll;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
//isPrime
//modpow modinv
//getDigit
int main() {
  cout << fixed << setprecision(10);
  string s;
  cin >> s;
  int ans = 0;
  rep(i,3){
    if(s.at(i)=='1') ans++;
  }
  cout << ans << endl;
}


Measured memory_bytes: 256