akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
#include<complex>
using namespace std;

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 998244353;
const ll INF = mod * mod;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef pair<ll, ll> LP;
typedef vector<ll> vec;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-5;
const ld pi = acos(-1.0);

struct graph {
private:
	int n;
	vector<vector<int>> G, rG;
	vector<bool> used;
	vector<int> vs;

	int mk;
	vector<vector<int>> fG;
	vector<vector<int>> ori;
	vector<int> trans;
public:
	graph(int sz) {
		n = sz;
		G.resize(n);
		rG.resize(n);
		used.resize(n);

		fG.resize(n);
		trans.resize(n, -1);
		ori.resize(n);
	}
	void add_edge(int a, int b) {
		G[a].push_back(b);
		rG[b].push_back(a);
	}
	void dfs(int v) {
		used[v] = true;
		rep(i, G[v].size()) {
			if (!used[G[v][i]])dfs(G[v][i]);
		}
		vs.push_back(v);
	}
	void rdfs(int v, int k) {
		used[v] = true;
		queue<int> q; q.push(v);
		vector<int> c;
		while (!q.empty()) {
			int id = q.front(); q.pop();
			ori[k].push_back(id);
			rep(j, rG[id].size()) {
				int to = rG[id][j];
				if (used[to]) {
					if (trans[to] >= 0)c.push_back(trans[to]);
					continue;
				}
				used[to] = true; q.push(to);
			}
		}
		sort(c.begin(), c.end());
		int len = unique(c.begin(), c.end()) - c.begin();
		rep(i, len) {
			fG[c[i]].push_back(k);
		}
		rep(i, ori[k].size()) {
			trans[ori[k][i]] = k;
		}
	}
	void scc() {
		fill(used.begin(), used.end(), false);
		rep(i, n) {
			if (!used[i])dfs(i);
		}
		fill(used.begin(), used.end(), false);
		int k = 0;
		per(i, (int)vs.size()) {
			if (!used[vs[i]]) {
				rdfs(vs[i], k); k++;
			}
		}
		mk = k;
	}
	void query() {
		rep(i, mk)sort(ori[i].begin(), ori[i].end());
		rep(i, n) {
			int id = trans[i];
			rep(j, ori[id].size()) {
				if (j > 0)cout << " ";
				cout << ori[id][j]+1;
			}
			cout << endl;
		}
	}
};

void solve() {
	int n, m; cin >> n >> m;
	graph g(n);
	rep(i, m) {
		int a, b; cin >> a >> b; a--; b--;
		g.add_edge(a, b);
	}
	g.scc();
	g.query();
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	solve();
	//stop
	return 0;
}



Measured memory_bytes: 4284
#include "bits/stdc++.h"
using namespace std;
int main() {
	long long N;
	cin >> N;
	vector<long long>A(N);
	for (long long i = 0; i < N; i++) {
		cin >> A.at(i);
	}
	if (N <= 2) {
		cout << 1 << endl;
		return 0;
	}
	int ans = 0;
	int comparison = 0;
	//comparison == -1 : A[i] < A[i + 1]
	//comparison == 1 : A[i] > A[i + 1]
	for (int i = 0; i < N - 1; i++) {
		if (A.at(i) > A.at(i + 1)) {
			if (comparison == -1) {
				ans++;
				comparison = 0;
			}
			else comparison = 1;
		}
		if (A.at(i) < A.at(i + 1)) {
			if (comparison == 1) {
				ans++;
				comparison = 0;
			}
			else comparison = -1;
		}
	}
	cout << ans + 1 << endl;
}


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

int main() {
  string s;
  cin>>s;
  if (s[0]==s[1]&&s[2]==s[3]&&s[0]!=s[2]
      ||s[0]==s[2]&&s[1]==s[3]&&s[0]!=s[1]
      ||s[0]==s[3]&&s[1]==s[2]&&s[0]!=s[1]) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
      
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
#define all(x) (x).begin(), (x).end()
ll inf = LLONG_MAX;
long double pi = M_PI;
void Yes() {cout << "Yes" << endl;}
void No() {cout << "No" << endl;}
void YES() {cout << "YES" << endl;}
void NO() {cout << "NO" << endl;}

ll root(ll x, vll &parent) {
  if (parent[x] == x) return x;
  else return parent[x] = root(parent[x], parent);
}

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

  vll p(n);
  for (ll i = 0; i < n; i++) cin >> p[i];

  vector<vll> xy(m, vll(2));
  for (ll i = 0; i < m; i++) {
    cin >> xy[i][0] >> xy[i][1];
    if (xy[i][0] > xy[i][1]) swap(xy[i][0], xy[i][1]);
  }

  vll parent(n);
  for (ll i = 0; i < n; i++) parent[i] = i;
  for (ll i = 0; i < m; i++) {
    parent[root(xy[i][1] - 1, parent)] = root(xy[i][0] - 1, parent);
  }

  ll cnt = 0;
  for (ll i = 0; i < n; i++) {
    if (root(i, parent) == root(p[i] - 1, parent)) cnt++;
  }
  cout << cnt << endl;
}

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

vector<ll> s(100005, 1e16);
vector<ll> t(100005, 1e16);

int main(){
    int a, b, q;
    cin >> a >> b >> q;
    for(int i = 0; i < a; i++) cin >> s[i];
    for(int i = 0; i < b; i++) cin >> t[i];
    for(int i = 0; i < q; i++){
        ll x;
        cin >> x;
        if(x == 0){
            cout << max(s[0], t[0]) << endl;
        }else if(x >= max(s[a-1], t[b-1])){
            cout << abs(x - max(s[a-1], t[b-1])) + abs(s[a-1] - t[b-1]) << endl;
        }else{
            int l = 0, r = a - 1;
            ll t1, t2, x1, x2;
            while(r - l > 1){
                int mid = (l + r) / 2;
                if(s[mid] < x) l = mid;
                else r = mid;
            }
            t1 = t2 = 0, x1 = x2 = x;
            t1 += abs(x - s[l]), x1 = s[l];
            t2 += abs(x - s[r]), x2 = s[r];
            l = 0, r = b - 1;
            while(r - l > 1){
                int mid = (l + r) / 2;
                if(t[mid] < x1) l = mid;
                else r = mid;
            }
            t1 += min(abs(x1 - t[l]), abs(x1 - t[r]));
            l = 0, r = b - 1;
            while(r - l > 1){
                int mid = (l + r) / 2;
                if(t[mid] < x2) l = mid;
                else r = mid;
            }
            t2 += min(abs(x2 - t[l]), abs(x2 - t[r]));
            ll tmp = min(t1, t2);

            l = 0, r = b - 1;
            while(r - l > 1){
                int mid = (l + r) / 2;
                if(t[mid] < x) l = mid;
                else r = mid;
            }
            t1 = t2 = 0, x1 = x2 = x;
            t1 += abs(x - t[l]), x1 = t[l];
            t2 += abs(x - t[r]), x2 = t[r];
            l = 0, r = a - 1;
            while(r - l > 1){
                int mid = (l + r) / 2;
                if(s[mid] < x1) l = mid;
                else r = mid;
            }
            t1 += min(abs(x1 - s[l]), abs(x1 - s[r]));
            l = 0, r = a - 1;
            while(r - l > 1){
                int mid = (l + r) / 2;
                if(s[mid] < x2) l = mid;
                else r = mid;
            }
            t2 += min(abs(x2 - s[l]), abs(x2 - s[r]));
            cout << min(tmp, min(t1, t2)) << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 2944
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stdio.h>
#include<cstring>
#include<math.h>
#include<map>
#include<bitset>
#include<iomanip>
#include<queue>
#include<functional>
#include<stack>
#include<tuple>
#include<cassert>
using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
using P = pair<int, int>;

int main() {
  int N;
  map<string, int> mp;
  cin >> N;
  rep(i, N) {
    string temp;
    cin >> temp;
    if(mp[temp] == 0) {
      mp[temp]++;
    } else {
      cout << "NO" << endl;
      return 0;
    }
  }
  cout << "YES" << endl;
  return 0;
}

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

void print_vec(vector<int> vec) {
  cout << "[";
  for (int i = 0; i < vec.size(); i++) {
    if (i) {
      cout << ", ";
    }
    cout << vec.at(i);
  }
  cout << "]...size: " << vec.size() << endl;
}

void bubble_sort(vector<pair<char, int>> &c, int n) {
  rep(i, n) {
    for (int j = n - 1; j > i; j--) {
      if (c[j].second < c[j - 1].second) {
        swap(c[j], c[j - 1]);
      }
    }
  }
}

void selection_sort(vector<pair<char, int>> &c, int n) {
  rep(i, n) {
    int minj = i;
    for (int j = i; j < n; j++) {
      if (c[j].second < c[minj].second) {
        minj = j;
      }
    }
    swap(c[i], c[minj]);
  }
}

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

  vector<pair<char, int>> v1(n);

  rep(i, n) {
    char ch;
    int num;
    cin >> ch >> num;
    v1[i] = make_pair(ch, num);
  }

  vector<pair<char, int>> v2 = v1;

  bubble_sort(v1, n);
  selection_sort(v2, n);

  rep(i, n) {
    if (i) {
      printf(" ");
    }
    printf("%c%d", v1[i].first, v1[i].second);
  }

  printf("\nStable\n");

  rep(i, n) {
    if (i) {
      printf(" ");
    }
    printf("%c%d", v2[i].first, v2[i].second);
  }

  if (v1 == v2) {
    printf("\nStable\n");
  } else {
    printf("\nNot stable\n");
  }
}



Measured memory_bytes: 3224
n = int(input())
p = list(map(int, input().split()))

count = 0
for i in range(1,len(p)-1,1):
    if p[i+1] > p[i] > p[i-1]:
        count = count +1
    elif p[i+1] < p[i] < p[i-1]:
        count = count +1
    else:
        pass

print(count)

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

#define REP(i, n) for(int (i) = 0; (i) < (n); ++(i))
#define REPR(i, n) for(int (i) = (n); (i) >= 0; --(i))
#define FOR(i, n, m) for(int (i) = (n); (i) <= (m); ++(i))

int N, ans = 0;
void solve(ll n, bool seven, bool five, bool three){
  if(n > N){
    return;
  }
  if(seven && five && three){
    ans++;
  }
  solve(10*n+3, seven, five, true);
  solve(10*n+5, seven, true, three);
  solve(10*n+7, true, five, three);
}
int main(){
  cin >> N;
  solve(0, false, false, false);
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
const ll mod = 1e9+7;
const ll INF = 2e9;
const double PI = 3.1415926535;

ll a[100000];
ll b[100000];

int main(void){
    ll n; cin >> n; for(int i = 0;i < n;i++)cin >> a[i] >> b[i];
    ll ans = 0;
    for(int i = n-1;i >= 0;i--){
        ll na = a[i] + ans;
        if(na%b[i] != 0)ans += b[i] - na%b[i];
    }
    cout << ans << endl;
	return 0;
}

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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()

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

    // start
    int x;
    cin >> x;
    if(x<1200)
        cout << "ABC" << endl;
    else
        cout << "ARC" << endl;
    // end

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main(int argc, char const *argv[]) {
  int N;
  cin >> N;
 
  bool failed = false;
  int t, x, y, t_prev, x_prev, y_prev;
  t_prev = x_prev = y_prev = 0;
  for (int i = 1; i <= N; i++) {
    cin >> t >> x >> y;
    t -= t_prev;
    x -= x_prev;
    y -= y_prev;
 
    if (failed) continue;
    // cout << t << ", " << x << ", " << y << endl;
 
    int norm = abs(x) + abs(y);
    if (norm > t) {
      failed = true;
    }
    if ((t % 2 == 0 && norm % 2 == 1) || (t % 2 == 1 && norm % 2 == 0)) {
      failed = true;
    }
 
    t_prev = t;
    x_prev = x;
    y_prev = y;
  }
 
  if (failed) {
    cout << "No" << endl;
  } else {
    cout << "Yes" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main()
{
    int a, b, c, x;
    cin >> a >> b >> c >> x;
    int ans = 0;
    for(int i = 0; i <= a; i++)
    {
        for(int j = 0; j <= b; j++)
            {
                for(int k = 0; k <= c; k++)
                {
                    if((i * 500 + j * 100 + k * 50) == x)
                        ans++;
                }
            }
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;
int main()
{
    int n;
    cin >> n;
    if (n <= 1000)
        cout << 1000 - n;
    else
    {
        int k = 1000;
        while (n > k)
            k += 1000;
        cout << k - n;
    }
}


Measured memory_bytes: 3640
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read(){
	ll a=0,b=getchar(),c=1;
	while(!isdigit(b))c=b=='-'?-1:1,b=getchar();
	while(isdigit(b))a=a*10+b-'0',b=getchar();
	return a*c;
}
ll n,ans,mod=1e9+7,a[105];
int main(){
	n=read();
	for(int i=0;i<n;i++){
		ll x=read();
		for(int j=0;j<60;j++)
			a[j]+=x>>j&1;
	}
	for(int i=0;i<60;i++)
		(ans+=(a[i]*(n-a[i]))%mod*((1ll<<i)%mod))%=mod;
	printf("%lld",ans);
	return 0;
}

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

long Factorial(int k);

int main()
{
	long n,m,ans=0;	
	cin >> n >> m;
	if(abs(n-m)>=2){
		ans=0;
	}
	else if(abs(n-m)==1){
		ans=(Factorial(n)%1000000007)*Factorial(m)%1000000007;
	}
	else if(n==m){
		ans=2*(Factorial(n)%1000000007)*Factorial(m)%1000000007;
	}

	cout << ans << endl;
	return 0;
}

long Factorial(int k){
    long sum=1;
    for (int i=1;i<=k;i++)
    {
        sum *= i;
        sum %= 1000000007;
    }
    return sum;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
using namespace std;

int main() {
  int n;
  cin >> n;
  string s;
  cin >> s;
  int left = 0, right = 0, e = 0;
  for(c : s) {
    if(c == '(') {
      right++;
      // if(left > 0) left--;
    } else if(c == ')') {
      if(right > 0) {
        right--;
      } else {
        left++;
      }
    }
  }
  while(left--)
    s.insert(s.begin(), '(');
  while(right--)
    s.insert(s.end(), ')');
  cout << s << endl;
}


Measured memory_bytes: 256
from bisect import bisect_left
N,Q,*L = map(int, open(0).read().split())
A = L[:N]
S = []
M = []
x = 0
y = 0
m = sum(A)
for i in range(N):
  if i%2==0:
    x += A[i]
    S.append(x)
  else:
    y += A[i]
    S.append(y)
for i in range(N):
  M.append(m)
  m -= A[i]

for q in L[N:]:
  i = bisect_left(A,q)
  if 0<i<N and q-A[i-1]<=A[i]-q:
    i = i-1
  if i>=N-1:
    print(S[N-1])
    continue
  l = -1
  r = N
  while l+1<r:
    s = (l+r)//2
    k = N-1-s
    if s<=i:
      l = s
      continue
    x = s-i+1
    if x>k:
      r = s
      continue
    y = k-x
    m = i-y-1
    if m<0:
      l = s
      continue
    if q-A[m]<=A[s]-q:
      r = s
    else:
      l = s
  a = M[r]
  cnt = N-r
  cnt -= r-i-1
  b = i-cnt
  if b>=0:
    a += S[b]
  print(a)

Measured memory_bytes: 98768
#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define ll long long
#define fr(i,a,b) for (long long int i=a ; i<b ; i++)
#define fre(i,a,b) for (long long int i=a ; i<=b ; i++)
#define mem(a, b) memset(a, (b), sizeof(a))
#define mp make_pair
#define pb push_back
#define inf (int)1e9
#define pii 3.1415926535897932384626433832795
#define mod 1000000007
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<pi> vii;
typedef map<int,int> mi;
typedef set<int> si;






int main() {
    FAST_IO;
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    ll n;
    cin>>n;
    ll w;
    cin>>w;
    ll val[n+1];
    ll wt[n+1];
    int totalvalue =0;
    fr(i,0,n){
    	cin>>wt[i];
    	cin>>val[i];
    	totalvalue = totalvalue + val[i];
    }
    ll dp[n+1][totalvalue+1];
    //instead  of finding maximum value for given weight , find minimum weight for gieven value.
    // so iterate overe values not weight weights are huge
    for(int i=0;i<=totalvalue;i++)
    	dp[0][i] = 1e18;
    dp[0][0] = 0;
    int ans = -1;
    for(int i=1;i<=n;i++){
    	for(int j=0;j<=totalvalue;j++){
    		if(val[i-1] <= j)
    			dp[i][j] = min(dp[i-1][j-val[i-1]] + wt[i-1] , dp[i-1][j]);
    		else
    			dp[i][j] = dp[i-1][j];
    		if(dp[i][j]<=w)
    			ans = max(ans,j);
    	}
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 82404
N = int(input())
ARR = []

for i in range(N):
    ARR.append([int(s) for s in input().split(" ")])


import math

def calculate(n,arr):

    arr.insert(0,[0,0,0])

    result = True

    for i in range(1,n+1):

        diff = arr[i][0] - arr[i-1][0]

        distance = int(math.fabs(arr[i][1] - arr[i-1][1]) + math.fabs(arr[i][2] - arr[i-1][2]))

        if diff < distance:
            result = False
            break

        if (diff + distance) % 2 == 1:
            result = False
            break

    if result:
        print("Yes")
    else:
        print("No")


calculate(N,ARR)



Measured memory_bytes: 21108
#include<stdio.h>
int main()
{
  int n,h1=0,h2=0,h3=0;
  char S[4];
  
  scanf("%s",S);
  
  for(n=0; n<3; n++){
    if(S[n]=='a'){
      h1++;
    }else if(S[n]=='b'){
      h2++;
    }else if(S[n]=='c'){
      h3++;
    }
  }
  
  if(h1==1 && h2==1){
    if(h3==1){
      printf("Yes");
    }else{
      printf("No");
    }
  }else{
    printf("No");
  }
  
  return 0;
}

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

#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

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

  vector<int> d(n);
  for (int &x : d) {
    cin >> x;
  }
  vector<int> count(100, 0);

  for (int x : d) {
    count.at(x - 1)++;
  }
  int ret = 0;
  for (int x : count) {
    if (x > 0) {
      ret++;
    }
  }
  cout << ret << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define d(i) cout << #i << " = " << i << endl
#define int long long
using namespace std;

const int maxn = 2e3+10, maxl = 1e3+10;;

int n, l[maxn], cnt[maxl<<1], sum[maxl<<1], ans;

signed main() {
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> l[i];
		cnt[l[i]]++;
	}
	for (int i = 1; i < maxl<<1; ++i)
		sum[i] = sum[i-1]+cnt[i];
	for (int i = 0; i < maxl; ++i) if (cnt[i]) {
		for (int j = 0; j <= i; ++j) if (cnt[j] > (i==j)) {
			if (i == j) {
				ans += (sum[i+j-1]-sum[i])*cnt[i]*(cnt[i]-1)/2;
				ans += cnt[i]*(cnt[i]-1)*(cnt[i]-2)/6;
			} else {
				ans += (sum[i+j-1]-sum[i])*cnt[i]*cnt[j];
				ans += cnt[i]*(cnt[i]-1)/2*cnt[j];
			}
//			d(i), d(j), d(ans);
		}
	}
/*
	int check = 0;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < i; ++j)
			for (int k = 0; k < j; ++k)
				check += (l[i]+l[j]>l[k])&&(l[i]+l[k]>l[j])&&(l[j]+l[k]>l[i]);
	assert(check == ans);
*/
	cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int a,b;
    cin>>a>>b;
    if(1<=a&&a<=9&&1<=b&&b<=9){cout<<a*b;}
    else{cout<<-1;}
}



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


char s[1000];

int main() {
    int n, k;
    cin >> n >> k;
    scanf("%s", s + 1);
    s[k] = s[k]  + 'a' - 'A';
    printf("%s\n", s + 1);
    return 0;
}


Measured memory_bytes: 256
while True:
    H, W = map(int, input().split())
    if H == 0 and W == 0:
        break
    for i in range(H):
        for j in range(W):
            if (i + j) % 2 == 0:
                print('#', end='')
            else:
                print('.', end='')
        print()
    print()




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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------


int N;
vector<int> E[202020];
ll dp[202020];
int C[202020];
ll pdp[202020];
const ll mo=1000000007;

ll comb(ll N_, ll C_) {
	const int NUM_=400001;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	if (fact[0]==0) {
		inv[1]=fact[0]=factr[0]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}

ll modpow(ll a, ll n=mo-2) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

void dfs(int cur,int pre) {
	C[cur]=0;
	dp[cur]=1;
	FORR(e,E[cur]) if(e!=pre) {
		dfs(e,cur);
		
		dp[cur]=dp[cur]*dp[e]%mo*comb(C[cur]+C[e],C[e])%mo;
		C[cur]+=C[e];
	}
	C[cur]++;
}

void dfs2(int cur,int pre,ll pv) {
	dp[cur]=dp[cur]*pv%mo*comb(N-1,N-C[cur])%mo;
	FORR(e,E[cur]) if(e!=pre) {
		
		pv=dp[cur]*modpow(dp[e]*comb(N-1,C[e])%mo)%mo;
		dfs2(e,cur,pv);
		
		
		
	}
	
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	
	dfs(0,0);
	dfs2(0,0,1);
	
	FOR(i,N) cout<<dp[i]<<endl;
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


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

#define VARNAME(x) #x
#define show(x) cerr << #x << " = " << x << endl

using namespace std;
using ll = long long;

template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v)
{
    os << "sz:" << v.size() << "\n[";
    for (const auto& p : v) {
        os << p << ",";
    }
    os << "]\n";
    return os;
}

template <typename T>
istream& operator>>(istream& is, vector<T>& v)
{
    for (auto& e : v) {
        is >> e;
    }
    return is;
}

template <typename S, typename T>
ostream& operator<<(ostream& os, const pair<S, T>& p)
{
    os << "(" << p.first << "," << p.second
       << ")";
    return os;
}


constexpr ll MOD = (ll)1e9 + 7LL;

template <typename T>
constexpr T INF = numeric_limits<T>::max() / 10;


int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll L;
    cin >> L;
    vector<string> S(2);
    cin >> S[0] >> S[1];
    auto comp = [](const string& s1, const string& s2) {
        return s1 + s2 < s2 + s1;
    };
    sort(S.begin(), S.end(), comp);
    const ll s = S[0].size();
    const ll t = S[1].size();
    for (ll l = L; l >= 0; l--) {
        const ll len = s * l;
        if (len <= L and (L - len) % t == 0) {
            const ll snum = l;
            const ll tnum = (L - len) / t;
            for (int i = 0; i < snum; i++) {
                cout << S[0];
            }
            for (int i = 0; i < tnum; i++) {
                cout << S[1];
            }
            cout << endl;
            return 0;
        }
    }


    return 0;
}


Measured memory_bytes: 1684
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <queue>
#include <sstream>
#include <stack>
#include <time.h>
#include <vector>
#include <complex>
#include <map>
#include <set>
#include <iomanip>
#include <math.h>
#include <stdlib.h>
#include <list>
#include <utility>
#include <memory>
#include <cstring>
#include <fstream>
#include <numeric>
#include <assert.h>
#include <bits/stdc++.h>
using namespace std;
int n,m;
int a[100004];
int main(){
	cin>>n>>m;
	for (int i=0;i<m;i++) cin>>a[i];
	sort (a,a+m);
	int ans=a[m-1]-a[0]+1-n; 
	if (n>=m) return !puts("0");
	vector <int> tt;
	for (int i=0;i<m-1;i++){
		tt.push_back(a[i+1]-a[i]-1);
	}
	sort (tt.begin(),tt.end());
	for (int i=int(tt.size()-1),j=1;j<=n-1;j++,i--)
		ans-=tt[i];
	cout<<ans;
}

Measured memory_bytes: 1276
import java.util.*;
import java.io.PrintWriter;

public class Main{
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int d=sc.nextInt();
		int ans=0;
		for(int i=0; i<n; i++){
			double x=sc.nextDouble();
			double y=sc.nextDouble();
			if(Math.sqrt(x*x+y*y)<=d){
				ans++;
			}
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 63500
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define FOR(i, a, b) for(int i=(a);i<(b);i++)
#define RFOR(i, a, b) for(int i=(b-1);i>=(a);i--)
#define REP(i, n) for(int i=0; i<(n); i++)
#define RREP(i, n) for(int i=(n-1); i>=0; i--)
#define REP1(i, n) for(int i=1; i<=(n); i++)
#define RREP1(i, n) for(int i=(n); i>=1; i--)
#define ALL(a) (a).begin(),(a).end()
#define UNIQUE_SORT(l) sort(ALL(l)); l.erase(unique(ALL(l)), l.end());
#define CONTAIN(a, b) find(ALL(a), (b)) != (a).end()
#define out(...) printf(__VA_ARGS__)
#if DEBUG
#define debug(...) printf(__VA_ARGS__)
#else
#define debug(...) /* ... */
#endif
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}

void solve();
signed main()
{
#if DEBUG
    std::ifstream in("input.txt");
    std::cin.rdbuf(in.rdbuf());
#endif
    cin.tie(0);
    ios::sync_with_stdio(false);
    solve();
    return 0;
}

/*================================*/
#if DEBUG
#define SIZE 100
#else
#define SIZE 223450
#endif

int L,R,d;
int A[SIZE];

void solve() {
    cin>>L>>R>>d;
    int ans = 0;
    FOR(n,L,R+1) if(n%d==0) ans++;
    
    cout << ans << endl;
}


Measured memory_bytes: 3636
fun main(args: Array<String>) {
    val sub = mutableListOf(0)
    val list = mutableListOf<Int>()
    repeat(9) {
        val l = sub.toList()
        sub.clear()
        for (ln in l) {
            for (n in ln * 10 + 3..ln * 10 + 7 step 2) {
                sub.add(n)
                if ("357".all { n.toString().contains(it) }) list.add(n)
            }
        }
    }
    print(readLine()!!.toLong().let { n -> list.count { it <= n } })
}

Measured memory_bytes: 40760
n = gets.to_i
g = Array.new(n){ Array.new }
(1..n-1).each do |i|
  a,b,c = gets.split.map(&:to_i)
  a -= 1
  b -= 1
  g[a] << [b,c]
  g[b] << [a,c]
end

q,k = gets.split.map(&:to_i)
k -= 1

dist = Array.new(n,0)
st = [[k,-1]]
while not st.empty? do
  v,p = st.pop
  for to,c in g[v] do
    if to != p
      dist[to] = dist[v] + c
      st.push [to, v]
    end
  end
end

(1..q).each do |i|
  x,y = gets.split.map(&:to_i)
  x -= 1
  y -= 1
  puts dist[x] + dist[y]
end


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

using namespace std;

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

int main(){

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

  ll m=0;
  for(int i=0;i<n;i++){
    if(h[i]<h[i+1])continue;
    ll k=0;
    while(i+k+1<=n-1 && h[i+k]>=h[i+k+1]){
      k++;
    }
    i+=k;
    m=max(m,k);
  }
  cout << m << endl;

}

Measured memory_bytes: 4316
package main

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

var sc = bufio.NewScanner(os.Stdin)
var out = bufio.NewWriter(os.Stdout)

func main() {
	buf := make([]byte, 1024*1024)
	sc.Buffer(buf, bufio.MaxScanTokenSize)
	sc.Split(bufio.ScanWords)
	defer out.Flush()

	a, b, c := nextInt(), nextInt(), nextInt()

	var values = []int{a, b, c}
	returns := sort(values)

	fmt.Fprintf(out, "%d %d %d\n", returns[0], returns[1], returns[2])
}

func sort(val []int) (ret []int) {
	if len(val) < 2 {
		return val
	}

	pivot := val[0]

	left := []int{}
	right := []int{}

	for _, v := range val[1:] {
		if v > pivot {
			right = append(right, v)
		} else {
			left = append(left, v)
		}
	}

	left = sort(left)
	right = sort(right)

	ret = append(left, pivot)
	ret = append(ret, right...)

	return
}

func temp(a int, b int) (int, int) {
	return b, a
}

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	a, _ := strconv.Atoi(next())
	return a
}



Measured memory_bytes: 1156
import std.functional,
       std.algorithm,
       std.container,
       std.typetuple,
       std.typecons,
       std.bigint,
       std.string,
       std.traits,
       std.array,
       std.range,
       std.stdio,
       std.conv;

void main() {
  long[] NY = readln.chomp.split.to!(long[]);
  long N = NY[0],
       Y = NY[1] / 1000;

  foreach (long i; 0..N+1) {
    foreach (long j; 0..N+1) {
      long k = N - i - j;
      if (k < 0) { continue; }
      long y = i + j * 5 + k * 10;
      if (y == Y) {
        writefln("%d %d %d", k, j, i);
        return;
      }
    }
  }

  writeln("-1 -1 -1");
}

Measured memory_bytes: 256
#include<iostream>
//#define int long long

using namespace std;

long long dp[100001];

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

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

    if (n <= 25)
    {
        long long ans = 0, p[25], l[25];
        for (int i = 0; i < 25; i++)
            cin >> p[i] >> l[i];
        for (int i = 0; i < (1 << 25); i++)
        {
            bool use[25];
            int t = i;
            for (int j = 0; j < n; j++)
                use[j] = t % 2, t /= 2;

            long long tp = 0, tl = 0;
            for (int j = 0; j < n; j++)
                tp += use[j] * p[j], tl += use[j] * l[j];

            if (tp <= m)
                ans = max(ans, tl);
        }
        cout << ans << '\n';
    }
    /*else if (m <= 1000000)
    {
        long long p, l;
        for (int i = 0; i < n; i++)
        {
            cin >> p >> l;
            for (int j = m; j >= p; j--)
                dp[j] = max(dp[j], dp[j - p] + l);
        }

        long long ans = 0;
        for (int i = 0; i <= m; i++)
            ans = max(ans, dp[i]);
        cout << ans << '\n';
    }*/
    else
    {
        for (int i = 1; i <= 100000; i++)
            dp[i] = 1e18;

        long long p, l, sum = 0;
        for (int i = 0; i < n; i++)
        {
            cin >> p >> l;

            if (l < 0)
                continue;
            sum += l;
            for (int j = sum; j >= l; j--)
                dp[j] = min(dp[j], dp[j - l] + p);
        }
        while (dp[sum--] > m);
        cout << sum + 1 << '\n';
    }

    return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <cstdio>
#include <map>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
#include <list>
#include <stack>
#include <queue>
#define INF 1000000
using namespace std;

typedef list<int> L;
typedef pair <int,int> P;
typedef vector<int> V;
typedef queue<int> Q;
typedef stack<int> S;
typedef map<string,int> M;

int N;
int dp[1000001];
int dp2[1000001];
int tetra[1000];

int main()
{
    for (int i = 0; i <= INF; i++) {dp[i] = INF;dp2[i] = INF;}
    int n = 1;
    int tmp;
    while ((tmp = (n * (n + 1) * (n + 2) / 6)) <= 1000000) {
        tetra[n++] = tmp;
        dp[tmp] = 1;
        if (tmp % 2) dp2[tmp] = 1;
    }
    int max = 1;
    while (cin >> N, N) {
        if (max > N) {
            cout <<  dp[N] << " ";
        } else {
            for (int i = max; i <= N; i++) {
                for (int j = 1; tetra[j] <= i; j++) {
                    dp[i] = min(dp[i], dp[i - tetra[j]] + 1);
                }
            }
            cout << dp[N] << " ";
        }

        if (max > N) {
            cout << dp2[N] << endl;
        } else {
            for (int i = max; i <= N; i++) {
                for (int j = 1; tetra[j] <= i; j++) {
                    if (tetra[j] % 2)
                        dp2[i] = min(dp2[i], dp2[i - tetra[j]] + 1);
                }
            }
            cout << dp2[N] << endl;
            max = N;
        }
    }

    return 0;
}

Measured memory_bytes: 8980
#include<bits/stdc++.h>
#define pll              pair<long,long>
#define pii              pair<int,int>
#define scn(a)           scanf("%d", &a)
#define scn2(a, b)       scanf("%d%d", &a, &b)
#define scn3(a, b, c)    scanf("%d%d%d", &a, &b, &c)
#define pairl            pair<ll , ll >
#define scnl(a)          scanf("%lld", &a)
#define scnl2(a, b)      scanf("%lld%lld", &a, &b)
#define scnl3(a, b, c)   scanf("%lld%lld%lld", &a, &b, &c)
#define scns(s)          scanf("%s",s)
#define prts(s)          printf("%s\n",s)
#define prt(a)           printf("%d\n", a)
#define prtl(a)          printf("%lld\n", a)
#define prs(a)           printf("%d ", a)
#define prt2(a, b)       printf("%d %d\n", a, b)
#define prt3(a, b, c)    printf("%d %d %d\n", a, b, c)
#define prsl(a)          printf("%lld ", a)
#define prtl2(a, b)      printf("%lld %lld\n", a, b)
#define prtl3(a, b, c)   printf("%lld %lld %lld\n", a, b, c)
#define ptcs(a)          printf("Case %d: ", a)
#define pf               printf
#define sc               scanf
#define vi               vector<int >
#define vil              vector<ll >
#define pb               push_back
#define mem(a, b)        memset((a), (b), sizeof(a))
#define lg2(n)           (31-__builtin_clz(n))
#define N                300005
#define inf              999999999
#define ll               long long
#define ull              unsigned long long
#define MIN              INT_MIN
#define MAX              INT_MAX
#define fast             ios_base::sync_with_stdio(false),cin.tie(NULL)
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
typedef tree<int , null_type, less<int >, rb_tree_tag, tree_order_statistics_node_update> odrst;
ll gcd(ll a, ll b){if(b==0) {return a;}return gcd(b, a % b);}
ll BigMod(ll B,ll P,ll M){     ll R=1; while(P>0)      {if(P%2==1){R=(R*B)%M;}P/=2;B=(B*B)%M;} return R;}
//________________________________________________________________________________________________________________
bool cmp(pair<ll,ll> a, pair<ll,ll> b)
{
    if(a.first>b.first) return true;
    if(a.first<b.first) return false;
    if(a.second<b.second) return true;
    else return false;

}
bool ok=false;
ll cnt[N],a[N];
ll t,n,m,x,p,r,y,z,mod=998244353,ans=0;
vector<ll>v[N];
string s,s1;
int main()
{
    cin>>n;
    if(n&1)
    {
        cout<<0<<endl;
        return 0;
    }
    n/=2;
    x=5;
    while(x<=n)
    {
        ans+=n/x;
        x*=5LL;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 8448
#include<bits/stdc++.h>
using namespace std;
int main(){
	string str,str2;
	cin>>str>>str2;
	int a,b;
	cin>>a>>b;
	string s;
	cin>>s;
	(str==s)?cout<<a-1<<" "<<b:cout<<a<<" "<<b-1;
	return 0;
}


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

#include <math.h>
#include <stdlib.h>


#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;

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; }

//INT_MAX	2,147,483,647 = 2*1.0e9

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

    vector<vector<int>> A(2, vector<int>(N));
    for(int i = 0; i < 2; i++){
        for(int j = 0; j < N; j++){
            cin >> A[i][j];
        }
    }

    vector<int> sum1(N,0);
    sum1[0] = A[0][0];
    for(int i = 1; i < N; i++){
        sum1[i] = sum1[i-1] + A[0][i];
    }

    vector<int> sum2(N,0);
    sum2[0] = A[1][0];
    for(int i = 1; i < N; i++){
        sum2[i] = sum2[i-1] + A[1][i];
    }

    int ans = A[0][0]+sum2[N-1];

    for(int i = 1; i < N; i++){
        int sum = sum1[i] + sum2[N-1]-sum2[i-1];
        ans = max(ans, sum);
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int f(int x)
{
	return x<0?-x:x;
}

int a[500001], sum[500001];

int main()
{
	int n, i;
	scanf("%d", &n);
	for(i=1; i<=n; i++)
	{
		scanf("%d", &a[i]);
		sum[i]=sum[i-1]+f(a[i]-a[i-1]);
	}
	for(i=1; i<n; i++)
		printf("%d\n", f(a[n])+sum[n]+f(a[i+1]-a[i-1])-sum[i+1]+sum[i-1]);
	printf("%d\n", sum[n-1]+f(a[n-1]));
}

Measured memory_bytes: 1920
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	ll h,w;
	cin>>h>>w;
	if(h==1||w==1)
	{
		cout<<1<<endl;
	}
	else
	{
		ll pro=h*w;
	if(pro%2==0)
	{
		cout<<pro/2<<endl;
	}
	else
	cout<<(pro+1)/2<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
# include <stdio.h>
# include <string.h>

int main(){
    char str[111];
    scanf("%s", str);
    
    int tam = strlen(str);
    
    char ini[3];
    char fim[3];
    ini[0] = str[0];
    fim[0] = str[tam-1];
    
    printf("%c%d%c\n", ini[0], tam-2, fim[0]);
    
    
    
    return 0;
}

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

int q,h,s,d,n;
signed main()
{
	scanf("%lld%lld%lld%lld%lld",&q,&h,&s,&d,&n);
	int mi=min(q*4,min(h*2,s));
	if(d<s*2&&d<h*4&&d<q*8)
	{
		if(n&1) cout << (n/2)*d+mi << endl;
		else cout << (n/2)*d << endl;
	}
	else cout << mi*n << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define eps 1e-9
#define oo 1e7+5

using namespace std;

typedef unsigned long long ull;
typedef vector<pair<int,pair<int,int>>> dirgraph;
typedef vector<vector<int>> graph;

const int maxN=1e18+5;

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

	int n,w;
	cin>>n>>w;
	vector<int>values(n),weights(n);
	int sum=0;
	for (int i = 0; i < n; i++)
	{
		cin>>weights[i]>>values[i];
		sum+=values[i];
	}
	
	//minimun weight to have total value i
	vector<int> dp(sum+1,maxN);
	dp[0]=0;
	
	for (int obj = 0; obj < n; obj++)
	{
		for(int old_value=sum-values[obj];old_value>=0;old_value--)
		{
			dp[old_value+values[obj]]=min(dp[old_value+values[obj]],
								dp[old_value]+weights[obj]);
		}
	}
	
	int ans=0;
	for (int i = sum; i >=0; i--)
	{
		if(dp[i] && dp[i]<w+1)
		{
			ans=i;
			break;
		}
	}
	cout<<ans<<endl;

	return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <string> 
#include <vector> 
#include <algorithm> 
#include <utility> 
#include <tuple> 
#include <cstdint> 
#include <cstdio> 
#include <map> 
#include <queue> 
#include <set> 
#include <stack> 
#include <deque> 
#include <unordered_map> 
#include <unordered_set> 
#include <bitset> 
#include <cctype> 
#include<math.h>
using namespace std;

#define int long long
#define endl "\n"
#define fir first
#define sec second
#define fro front
#define m_p make_pair
#define mod 1000000007
#define rep(i,n)  for(int i=0; i<(int) (n); i++)
#define all(v)  v.begin(),v.end()
#define vecin(v) for(int i=0; i<(int)v.size(); i++)cin>>v[i];
using namespace std;

const int MAX = 510000;
const int MOD = 1000000007;
long long fac[MAX], finv[MAX], inv[MAX];
int jousu(int x00, int y00) {
	int z00 = 1;
	for (int i = 0; i < y00; i++) {
		z00 *= x00;
	}
	return z00;
}
int keta(int x00) {
	int z00 = x00;
	int w00 = 0;
	while (z00 != 0) {
		z00 /= 10;
		w00++;
	}
	return w00;
}

int modinv(int a, int m) {
	int b = m, u = 1, v = 0;
	while (b) {
		int t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
int modpow(int a, int n) {
	int res = 1;
	while (n > 0) {
		if (n & 1) res* a% mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}
int gcd(int xx, int yy) {
	int p = xx;
	int q = yy;
	if (q > p)swap(p, q);
	while (p % q != 0) {
		p %= q;
		swap(p, q);
	}
	return q;
}
int lcm(int xx, int yy) {
	return xx * yy / gcd(xx, yy);
}
bool prime(int xx) {
	int a = xx;
	for (int i = 2; i * i <= xx; i++) {
		if (xx % i == 0) {
			return 0;
		}
	}
	return 1;
}
int com(int xx, int yy) {
	int zz = 1;
	for (int i = xx; i > xx - yy; i--) {
		zz *= i;
		zz %= mod;
	}
	for (int i = 1; i <= yy; i++) {
		zz *= modinv(i, mod);
		zz %= mod;
	}
	return zz;
}


signed main() {
	int a, b;
	cin >> a >> b;
	if (a == b) {
		cout << a * 2 << endl;
	}
	else {
		cout << max(a, b) * 2 - 1 << endl;
	}
}





Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 5e3 + 1;
int a, b;
int min(int x, int y)
{
    return (x < y)? x: y;

}

double calcAngle(double h, double m)
{
    // validate the input
    if (h <0 || m < 0 || h >12 || m > 60)
        printf("Wrong input");

    if (h == 12) h = 0;
    if (m == 60) m = 0;

    // Calculate the angles moved
    // by hour and minute hands
    // with reference to 12:00
    double hour_angle = 0.5 * (h * 60 + m);
    double minute_angle = 6 * m;

    // Find the difference between two angles
    double angle = abs(hour_angle - minute_angle);

    // Return the smaller angle of two possible angles
    angle = min(360 - angle, angle);
    angle *= acos(-1) / 180;
    //cout << angle << "\n";
    double ans = a * a + b * b - 2 * a * b * cos(angle);

    return sqrt(ans);
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int h, m;
    cin >> a >> b >> h >> m;
    double ans = calcAngle(h, m);
    cout << fixed << setprecision(10) << ans;
    return 0;
}

Measured memory_bytes: 4236
import Control.Applicative ((<$>), (<*>))
import Control.Monad
import Data.List

main :: IO ()
main = do
  n <- getl toInt
  m <- getl toInt
  solve n <$> replicateM m (getl toInt) >>= mapM_ print

solve :: Int -> [Int] -> [Int]
solve n = foldl shuffle [1..2*n]
  where
    shuffle ys i
      | i == 0 = concat $ zipWith (\a b -> [a,b]) (take n ys) (drop n ys)
      | otherwise = (drop i ys) ++ (take i ys)
                    
toInt :: String -> Int
toInt = read

getl :: (String -> a) -> IO a
getl f = f <$> getLine

Measured memory_bytes: 5592
def main():
    N, M, Q, *X = map(int, open(0).read().split())
    L = [0]*M
    R = [0]*M
    p = [0]*Q
    q = [0]*Q
    for i in range(M):
        L[i], R[i] = X[2*i], X[2*i + 1]
    for i in range(Q):
        p[i], q[i] = X[2*M + 2*i], X[2*M + 2*i + 1]
    # print(N, M, Q, L, R, p, q)
    S = [[0]*(N+1) for i in range(N+1)]
    for i in range(M):
        S[L[i]][R[i]] += 1
    # for s in S:
    #     print(s)
    S2 = [[0]*(N+1) for i in range(N+1)]
    for i in range(N+1):
        S2[i][0] = S[i][0]
        for j in range(1, N+1):
            S2[i][j] = S2[i][j-1] + S[i][j]
    # for s in S2:
    #     print(s)
    S3 = [[0]*(N+1) for i in range(N+1)]
    for i in range(N+1):
        S3[0][i] = S2[0][i]
        for j in range(1, N+1):
            S3[j][i] = S3[j-1][i] + S2[j][i]
    for i in range(Q):
        pi, qi = p[i], q[i]
        ans = S3[qi][qi] - S3[qi][pi-1]
        ans -= S3[pi-1][qi] - S3[pi-1][pi-1]
        print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 57248
N=str(input())
cc=['+']*3
ans=int(N[0])
for j in range(2**3):
    temp=bin(2**3+j)
    for i in range(3,6):
        if temp[i]=='0':
            ans+=int(N[i-2])
            cc[i-3]='+'
        else:
            ans-=int(N[i-2])
            cc[i-3]='-'
    if ans==7:
        print(N[0]+cc[0]+N[1]+cc[1]+N[2]+cc[2]+N[3]+'=7')
        exit()
    else:
        ans=int(N[0])

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

using namespace std;
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)

typedef long long ll;
typedef pair<ll, ll> P;
const ll INF = 1LL<<60;

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

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; }

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

int n;
double dp[310][310][310];

double solve(int i, int j, int k){

  if(dp[i][j][k] >= 0) return dp[i][j][k];

  if(i == 0 && j == 0 && k == 0) return 0.0;

  double ret = 0.0;

  if(i > 0) ret += solve(i-1, j, k) * i;
  if(j > 0) ret += solve(i+1, j-1, k) * j;
  if(k > 0) ret += solve(i, j+1, k-1) * k;
  ret += n;
  ret *= (1.0 / (i + j + k));

  dp[i][j][k] = ret;

  return ret;

}

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

  cin >> n;

  int one = 0, two = 0, three = 0;

  rep(i, n){
    int tmp; cin >> tmp;
    if(tmp == 1) one++;
    else if(tmp == 2) two++;
    else three++;
  }

  memset(dp, -1, sizeof(dp));

  double ans = solve(one, two, three);

  cout << setprecision(20) << ans << endl;

  return 0;
}


Measured memory_bytes: 233088
# Begin Header {{{
from math import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement
# }}} End Header
# _________コーディングはここから！！___________

n, m, k = map(int, input().split())
a = [0]+list(accumulate(map(int, input().split())))
b = [0]+list(accumulate(map(int, input().split())))
ans = [0]
for i in range(n+1):
    c = bisect_right(b, k-a[i])-1
    if c!=-1: ans.append(c+i)
print(max(ans))

Measured memory_bytes: 48596
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,n) for(int i=1;i<=(n);i++)
#define lol long long
#define SUM(n) ((n)+1)*(n)/2 //1〜nまでの総和を求める式
#define mp make_pair
#define fi first
#define se second
#define pu push_back
#define SYOU(x) fixed<<setprecision(x+1) //小数点桁数を指定する
#define abs(x,y) max(x,y)-min(x,y)
#define all(v) v.begin(),v.end()
#define UPDight(a,b) (a+b-1)/b //小数点切り上げ 
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const int MOD=int(1e9)+7; 
using namespace std;
using pii = pair<int, int>;
typedef vector<int> vit;

//最大公約数
lol gcd(lol x, lol y){
  if(x < y) swap(x, y);
  lol r = x % y;
  while(r != 0){
    x = y;
    y = r;
    r = x % y;
  }
  return y;
}

//最小公倍数
lol lcm(lol x, lol y){
  lol a = x * y;
  return (a / gcd(x, y));
}

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

  lol a, b, c, k;
  cin >> a >> b >> c >> k;
  lol ans = 0, memo = k;
  ans += min(k, a);
  k -= min(k, a);
  k -= min(k, b);
  ans -= min(k, c);
  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 3648
#include<bits/stdc++.h>
using namespace std;
    
#define FAST ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
    
#define int long long
#define double long double
    
#define all(a)      (a).begin(),(a).end()
#define sz(x)       (int)x.size()
    
#define ff first
#define ss second
#define mp make_pair
         
#define pb push_back
#define endl "\n" 
         
#define f(i,l,r) for(int i=l;i<=r;i++)
#define rf(i,r,l) for(int i=r;i>=l;i--)    

#define bp __builtin_popcountll
#define inf 1e18
    
const int N=1e6+5;
const int M=1e9+7;
void solve()
{
	string s;
	cin>>s;
	int n=s.size();
	for(int i=0;i<n;i++)
	{
		if(s[i]=='?') s[i]='D';
	}
	cout<<s;
}
signed main()  
{
	FAST
    int t=1;
    // cin>>t;
    for(int tc=1;tc<=t;tc++)
    {
    	// cout<<"Case #"<<tc<<": ";
    	solve();
    }
}


Measured memory_bytes: 3736
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()

ll n, k;
vector<ll> a(20);

ll solve (vector<ll> &d) {
    ll mx = 0, res = 0, p = 0;
    rep(i, k) {
        while (p < d[i]) {
            mx = max(mx, a[p]);
            p++;
        }
        res += max(mx+1-a[p], 0ll);
        mx = max(mx+1, a[p]);
        p++;
    }
    return res;
}

int main() {
    cin >> n >> k;
    rep(i, n) cin >> a[i];
    ll ans = 1e15;
    rep(i, 1<<n) {
        vector<ll> d;
        rep(j, n) if (i>>j & 1) d.push_back(j);
        sort(all(d));
        if (d.size() != k) continue;
        ans = min(ans, solve(d));
    }
    cout << ans << endl;
    return 0;
}

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

int main(){
    double x1,y1,x2,y2;
    cin >> x1 >> y1 >> x2 >> y2;
    printf("%.5f\n",sqrt(pow(fabs(x1-x2),2)+pow(fabs(y1-y2),2)));
    return 0;
}


Measured memory_bytes: 3276
def Check_Num(n):

    for i in range(1,n + 1):
        x = i
        if (x % 3 == 0):
            print(' {}'.format(i),end = '')
            continue
        elif (x % 10 == 3):
            print(' {}'.format(i),end = '')
            continue
        x //= 10
        while (x > 0):
            if (x % 10 == 3):
                print(' {}'.format(i),end = '')
                break
            x //= 10
    print()
if __name__ == '__main__':
    n = int(input())
    Check_Num(n)


Measured memory_bytes: 5876