akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>

using namespace std;

int main()
{
	int n;
	long ans = 1;

	string s[] = {
"0", 
"1", 
"2", 
"6", 
"24", 
"120", 
"720", 
"5040", 
"40320", 
"362880", 
"3628800", 
"39916800", 
"479001600", 
"6227020800", 
"87178291200", 
"1307674368000", 
"20922789888000", 
"355687428096000", 
"6402373705728000", 
"121645100408832000", 
"2432902008176640000", 
};

	while (cin >> n) {
		cout << s[n] << endl;
	}
	return 0;
}



Measured memory_bytes: 3100
#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long int
 
#define REP(i, n) for(int i = 0; i < (n); i++)
#define SREP(i, s) for(int i = 0; i < (s.size()); i++)
#define SORT(v, n) sort(v, v+n);
#define GSORT(v, n) sort(v, v+n, greater<int>());
#define VSORT(v) sort(v.begin(),v.end());
#define VGSORT(v) sort(v.begin(),v.end(),greater<int>());
#define REV(a) reverse(begin(a),end(a));
 
ll gcd(ll x, ll y){
	if(x<y) swap(x,y);
	if(y==0) return x;
	return gcd(y,x%y);
}
 
ll lcm(ll x, ll y){
	return (x*y/gcd(x,y));
}

int main(){
	ios::sync_with_stdio(false);cin.tie(0);
////////////////////////////////////////////
	ll l,r;
	cin >> l >> r;
	ll mint=2*1e9+1;
	bool a=0;
	bool b=0;
	ll ans=2*1e9+1;
	if(r-l>2019) r=l+2019;
	for(ll i=l;i<=r;i++){
		for(ll j=i;j<=r;j++){
			if(i!=j) mint=min(mint,(i*j)%2019);
		}
	}
	cout << mint << endl;
	
/////////////////////////////////////////////
}


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

using ll = long long;

constexpr ll MOD = 1e9+7;
constexpr ll INF = 1ll<<60;

#define FOR(i,a,b) for (ll i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()

constexpr  ll COMB_MAX = 1e6+10;
vector<ll> fac(COMB_MAX); 
vector<ll> ifac(COMB_MAX); 

ll mpow(ll x, ll n){ 
    ll ans = 1;
    while(n != 0){
        if(n&1) ans = ans*x % MOD;
        x = x*x % MOD;
        n = n >> 1;
    }
    return ans;
}

ll comb(ll a, ll b){ 
    if(a == 0 && b == 0)return 1;
    if(a < b || a < 0)return 0;
    ll tmp = ifac[a-b]* ifac[b] % MOD;
    return tmp * fac[a] % MOD;
}

void init()
{
	fac[0] = 1;
    ifac[0] = 1;
    for(ll i = 0; i<COMB_MAX; i++)
	{
        fac[i+1] = fac[i]*(i+1) % MOD; 
        ifac[i+1] = ifac[i]*mpow(i+1, MOD-2) % MOD; 
    }
}


int main(int argc, char **argv)
{
	ll H, W; cin >> H >> W;
	init();
	ll res;
	if ((H + W) % 3 != 0)
		res = 0;
	else if (H > W*2 || W > H*2)
		res = 0;
	else
		res = comb((W+H)/3, H-(W+H)/3);
	std::cout << res << std::endl;
}


Measured memory_bytes: 16000
// clang-format off
#include <bits/stdc++.h>

#define mp make_pair
#define fst first
#define snd second
#define forn(i,n) for (int i = 0; i < int(n); i++)
#define forn1(i,n) for (int i = 1; i <= int(n); i++)
#define popcnt __builtin_popcount
#define ffs __builtin_ffs
#define ctz __builtin_ctz
#define clz __builtin_clz
#define all(a) (a).begin(), (a).end()
 
using namespace std;

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
using pil = pair<int,ll>;
using pll = pair<ll,ll>;
template <typename T> using vec = vector<T>;
using vi = vec<int>;
using vl = vec<ll>;
template <typename T> using que = queue<T>;
template <typename T> using deq = deque<T>;

template <typename T> T id(T b) {return b;};
template <typename T> void chmax(T &x, T y) {if (x < y) x = y;}
template <typename T> void chmin(T &x, T y) {if (x > y) x = y;}
template <typename S, typename K> bool contains(S &s, K k) { return s.find(k) != s.end(); }
void fastio() { ios_base::sync_with_stdio(false); cin.tie(nullptr); }
constexpr ll TEN(int n) { if (n == 0) return 1LL; else return 10LL*TEN(n-1); }
// clang-format on

int main() {
    fastio();

    string s;
    cin >> s;

    if (s[2] == s[3] && s[4] == s[5]) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }

    return 0;
}

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

typedef long long LL;
typedef long double LD;
const int mod = 1000000007;

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int s, w;
    cin >> s >> w;
    if(s <= w) cout << "unsafe" << endl;
    else cout << "safe" << endl;
}

Measured memory_bytes: 3560
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

int main() {
  int n, q;
  cin >> n >> q;
  vector<vi> tree(n);
  rep(i, n - 1) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    tree[a].push_back(b);
    tree[b].push_back(a);
  }
  vi cnt(n, 0);
  rep(i, q) {
    int p, x;
    cin >> p >> x;
    p--;
    cnt[p] += x;
  }
  vb seen(n, false);
  stack<int> st;
  st.push(0);
  while(!st.empty()) {
    int i = st.top();
    st.pop();
    seen[i] = true;
    for(int v : tree[i]) {
      if(seen[v]) continue;
      cnt[v] += cnt[i];
      st.push(v);
    }
  }
  rep(i, n) cout << cnt[i] << (i == n - 1 ? "\n" : " ");
}


Measured memory_bytes: 15604
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static long solve[] = new long[100001];
    public static int a[] = new int[100001];
    public static long n,k;
    public static void main(String args[])throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String nk[]=br.readLine().split(" ");
        n=Long.parseLong(nk[0]);
        k=Long.parseLong(nk[1]);
        for(int i=0;i<n-1;i++)
            solve[i]=-1;
        solve[(int)n-1]=0;
        String S[]=br.readLine().split(" ");
        for(int i=0;i<n;i++)
            a[i]=Integer.parseInt(S[i]);
        System.out.println(DP(0));
    }
    public static long DP(int x)
    {
        if(solve[x]==-1)
        {
            long minVal= Long.MAX_VALUE;
            long tempVal;
            for(int i=x+1;i<=x+k&&i<n;i++)
            {
                tempVal=DP(i)+(Math.abs(a[x]-a[i]));
                if(tempVal<minVal)
                    minVal=tempVal;
            }
            solve[x]=minVal;
        }
        return solve[x];
    }
}

Measured memory_bytes: 48288
#include <iostream>
#include <vector>
#include <algorithm> // sort
using namespace std;

int diff_S(int a, int b, int c) {
	vector<int> vec(3);
	vec[0] = a * c;
	vec[1] = (a/2) * (b-c);
	vec[2] = (a-a/2) * (b-c);
	sort(vec.begin(), vec.end());
	return vec[2] - vec[0];
}

int main() {
	int H, W;
	cin >> H >> W;
	
	if (H%3==0 || W%3==0) {
		cout << 0 << endl;
		return 0;
	}

	int ans = min(H, W);
	ans = min(ans, diff_S(H, W, W/3));
	ans = min(ans, diff_S(H, W, W/3+1));
	ans = min(ans, diff_S(W, H, H/3));
	ans = min(ans, diff_S(W, H, H/3+1));
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

void YesNo (int x, int y, int z) {
  if (x * x + y * y == z * z) {
    printf ("YES\n");
  } else if (x * x == y * y + z * z) {
    printf ("YES\n");
  } else if (y * y == z * z + x * x) {
    printf ("YES\n");
  } else {
    printf ("NO\n");
  }
}

int main (void) {
  int x = 0, y = 0, z = 0;
  int i = 0, N = 0;
  scanf ("%d", &N);
  for (i = 0;i < N;i++) {
    scanf ("%d %d %d", &x, &y, &z);
    YesNo(x, y, z);
  }

  return 0;
}

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

template <typename InputIterator>
typename InputIterator::value_type summation(InputIterator first,
                                             InputIterator last) {
  return std::accumulate(first, last, typename InputIterator::value_type());
}
template <typename T>
std::istream &operator>>(std::istream &stream, std::vector<T> &v);
template <typename T1, typename T2>
std::istream &operator>>(std::istream &stream, std::pair<T1, T2> &p);
template <typename T>
std::istream &operator>>(std::istream &stream, std::vector<T> &v) {
  for (auto &i : v) {
    stream >> i;
  }
  return stream;
}
template <typename T1, typename T2>
std::istream &operator>>(std::istream &stream, std::pair<T1, T2> &p) {
  stream >> p.first >> p.second;
  return stream;
}

int main() {
  int64_t n;
  std::cin >> n;
  std::vector<int64_t> a(n);
  std::cin >> a;

  std::map<int64_t, int64_t> vals;

  for (int64_t i = 0; i < n; i++) {
    const auto v = a[i] - i;
    if (vals.count(v) != 0) {
      vals[v]++;
    } else {
      vals[v] = 1;
    }
  }

  int64_t ans = 0;
  for (int64_t i = 0; i < n; i++) {
    // j - i  == a[i] + a[j]
    // j - a[j] = a[i] + i
    const auto v = -(a[i] + i);
    if (vals.count(v) != 0) {
      ans += vals[v];
    }
  }

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


Measured memory_bytes: 16344
N, Q = map(int,input().split())
S = input()

ac_count = [0]*N
temp = 0
for i in range(1,N):
    if S[i] == 'C' and S[i-1] == 'A':
        temp += 1
        ac_count[i] = temp
    else:
        ac_count[i] = temp
#print(ac_count)
for _ in range(Q):
    l,r = map(int,input().split())
    if S[l-1] != 'C':
        print(ac_count[r-1]-ac_count[l-1])
    else:
        print(ac_count[r-1]-ac_count[l-1])

Measured memory_bytes: 6084
n,m = map(int,input().split())
a = list(map(int,input().split()))
lis = []
for i in range(m):
    wa = list(map(int,input().split()))
    lis.append(wa)
a.sort()
lis = sorted(lis, key=lambda x:x[1], reverse=True)
cnt = 0
for i in range(m):
    b,c = lis[i]
    for j in range(b):
        if c > a[cnt]:
            a[cnt] = c
        else:
            print(sum(a))
            exit()
        cnt += 1
        if cnt == n:
            print(sum(a))
            exit()
print(sum(a))

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

int main(){
  int N;
  cin >> N;
  vector<int> d(N);
  int i;
  for( i = 0 ; i < N ; i++ )	cin >> d.at(i);
  sort( d.begin(), d.end() );
  
  vector<int> mochi(0);

  for( i = 0 ; i < N ; i++ ){
    mochi.push_back( d.at( N - i - 1 ) );
    if( mochi.size() > 1 && mochi.at( mochi.size() - 1 )  == mochi.at( mochi.size() - 2 ) )mochi.pop_back();
    d.pop_back();
  }
  
  cout << mochi.size() << endl;
  
}

Measured memory_bytes: 256
import sys
from collections import Counter
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

input = sys.stdin.buffer.readline
int1 = lambda x: int(x) - 1

N, M = map(int, input().split())

frm, to = [0] * M, [0] * M
for i in range(M):
    a, b = map(int1, input().split())
    frm[i] = a
    to[i] = b

matr = csr_matrix(([1] * M, (frm, to)), shape=(N, N))
_, labels = connected_components(matr, directed=False)
print(max(Counter(labels).values()))


Measured memory_bytes: 64456
#include<iostream>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<utility>
#include<algorithm>
#include<cmath>
#include<climits>
using namespace std;

int main(){
	int a, b, c, x, y;
	cin >> a >> b >> c >> x >> y;
	int anum = x, bnum = y, cnum = 0;
	if(2*c < a+b){
		cnum += min(anum, bnum)*2;
		anum -= cnum/2;
		bnum -= cnum/2;
	}
	if(2*c < a){
		cnum += anum*2;
		anum = 0;
	}
	if(2*c < b){
		cnum += bnum*2;
		bnum = 0;
	}
	cout << a*anum+b*bnum+c*cnum << '\n';
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	int A, B;
	int max;
	
	scanf("%d %d", &A, &B);
	
	max = A + B;
	max < A - B ? max = A - B : max;
	max < A * B ? max = A * B : max;
	
	printf("%d\n", max);
	
	return (0);
}

Measured memory_bytes: 128
#include <iostream>
#include<string>

using namespace std;

int main()
{
    string s;
    cin >> s;
    int co1=0;
    int co2=0;
    int a=s[0];
    co1++;
    int b=0;
    if(s[1]!=a){
         b=(int)s[1];
         co2++;
    }
    else{
        co1++;
    }
    for(int i=2;i<4;i++){
        if((int)s[i]==a)co1++;
        else if(b==0)b=(int)s[i];
        if((int)s[i]==b)co2++;
    }
    if(co1==2&&co2==2){
        puts("Yes");
    }
    else{
        puts("No");
    }

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,e) for(int i= 0; i< (int)(e); i++)
#define reps(i,s,e) for(int i = s; i < (int)(e); i++)
#define repr(i,s,e) for(int i = s; i > (int)(e); i--)
typedef long long ll;
long bigp = 1000000007;
using wGraph = vector<vector<tuple<int, int>>>;

int main(){
    int n;
    cin >> n;
    wGraph g(n);
    reps(i,1,n){
        int u,v,w;
        cin >> u >> v >> w;
        g[u-1].push_back(make_tuple(v-1,w));
        g[v-1].push_back(make_tuple(u-1,w));        
    }
    queue<int> q;
    q.push(0);
    vector<int> ans(n), seen(n);
    rep(i,n){
        ans[i] = -1;
    }
    ans[0]=0;
    while(!q.empty()){
        int v = q.front();
        q.pop();
        seen[v] = 1;
        for( auto nv : g[v]){
            int nvv = get<0>(nv);
            int nvw = get<1>(nv);
            if(seen[nvv]==1){
                continue;
            }
            else{
                q.push(nvv);
                if(nvw%2==0){
                    ans[nvv] = ans[v];
                }
                if(nvw%2==1){
                    ans[nvv] = 1-ans[v];
                }
            }
        }
    }
    for(auto elem:ans){
        cout << elem << endl;
    }
}


Measured memory_bytes: 7168
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
int main(){
    long long h,w,ans=0LL;
    cin >> h >> w;
  	if(h==1LL||w==1LL)ans=1LL;
    else if(!(h%2)){
        ans=(h/2)*w;
    }
    else{
        ans=(h/2)*(w/2)+(h/2+1)*(w-w/2);
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define itn int
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define FORL(i,x) for(int i=head[x];i;i=nxt[i])
#define ALL(a)  (a).begin(),(a).end()
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define PB push_back
#define MP make_pair
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


ll mod = pow(10,9) + 7;

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

  map<char,ll> m;
  FOR(i,0,n-1) ++m[s[i]];
  
  ll ans = 1;
  FOR(i,0,25){
    ans *= m[char('a'+i)]+1;
    ans %= mod;
  }

  cout << ans%mod-1 << endl;

}

Measured memory_bytes: 512
#pragma GCC optimize("Ofast",3,"inline")
#include<bits/stdc++.h>
using namespace std;
typedef priority_queue<int> p_queue;
typedef long long ll;
ll n;
int a[500010];
ll minn=0x7f7f7f7f;
ll cnt=1;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	cin>>n>>a[0];
	minn=a[0];
	for(int i=1;i<n;i++){
		cin>>a[i];
		if(minn>=a[i])minn=a[i],cnt++;	
	}
	cout<<cnt;
	return 0;
}


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

ll choose2(ll n) {
    return n * (n - 1) / 2;
}
int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n) {
        cin >> a[i];
        a[i]--;
    }
    vector<int> d(n);
    rep(i, n) {
        d[a[i]]++;
    }
    ll tot = 0;
    rep(i, n) {
        tot += choose2(d[i]);
    }
    rep(i, n) {
        ll ans = tot;
        ans -= choose2(d[a[i]]);
        ans += choose2(d[a[i]] - 1);
        cout << ans << endl;
    }
}

Measured memory_bytes: 4224
import java.util.Scanner;
import java.util.HashMap;
import java.util.regex.Pattern;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        Pattern p = Pattern.compile("^.+$");
        StringBuilder sb;
        while(true) {
            int n = sc.nextInt();
            if (n == 0) {
                break;
            }
            sb = new StringBuilder();
            HashMap<String, String> map = new HashMap<>();
            for (int i = 0; i < n; i++) {
                map.put(sc.next(), sc.next());
            }
            int m = sc.nextInt();
            for (int i = 0; i < m; i++) {
                String s = sc.next();
                if (map.containsKey(s)) {
                    sb.append(map.get(s));
                } else {
                    sb.append(s);
                }
            }
            System.out.println(sb.toString());
        }
    }
}

Measured memory_bytes: 67296
#include<iostream>

using namespace std;

int main() {
	long long a,b,c,d;
	cin >> a >> b >> c >> d;
//	cout << a*c << endl;
	cout << (long long)max(max(a*c,a*d),max(b*c,b*d)) << endl;
	return 0;
}

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

// template {{{
#define  range(i, l, r) for (int i = (int)(l); i < (int)(r); (i) += 1)
#define rrange(i, l, r) for (int i = (int)(r) - 1; i >= (int)(l); (i) -= 1)

#define  whole(f, x, ...) ([&](decltype((x)) container) { return (f)(  begin(container),  end(container), ## __VA_ARGS__); })(x)
#define rwhole(f, x, ...) ([&](decltype((x)) container) { return (f)( rbegin(container), rend(container), ## __VA_ARGS__); })(x)

#define debug(x) cerr << "(" << __LINE__ << ")" << #x << ": " << (x) << endl

using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;

// constexpr i32 mod   = 998244353;
constexpr i32 mod   = 1e9 + 7;
constexpr i32 inf   = 1001001001;
constexpr i64 infll = 1001001001001001001ll;

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

struct IoSetup { IoSetup(int x = 15){ cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(x); cerr << fixed << setprecision(x); } } iosetup;

template <typename T = i64> T input() { T x; cin >> x; return x; }

template <typename T> ostream &operator<<(ostream &os, vector<T> &v) { range(i, 0, v.size()) { os << v[i] << (i + 1 != v.size() ? " " : ""); } return os; }
template <typename T> istream &operator>>(istream &is, vector<T> &v) { for (T &in : v) is >> in; return is; }

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

template <typename T> vector<T> make_vector(size_t a, T b) { return vector<T>(a, b); }
template <typename... Ts> auto make_vector(size_t a, Ts... ts) { return vector<decltype(make_vector(ts...))>(a, make_vector(ts...)); }

template <typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template <typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
// }}}

void solver() {
    string n;
    cin >> n;

    for (auto &c: n) {
        if (c == '1') c = '9';
        else if (c == '9') c = '1';
    }

    cout << n << endl;
}

signed main(int argc, char *argv[]) {
    solver();
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
ll a, b;
//ld ;
//string s;

int main() {
    cin >> a >> b;
    vector<ll> prices;
    ll ans=-1;
    for(ll i=0;i<10000;i++){
        if((i/10)==b){
            prices.push_back(i);
        }else if((i/10)>b){
            break;
        }
    }
    for(ll j=0; j<prices.size(); j++){
        if((prices[j]*8)/100==a){
            ans = prices[j];
            break;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define GET_MACRO(_1, _2, _3, NAME, ...) NAME
#define _repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define _rep(i,n) _repl(i,0,n)
#define rep(...) GET_MACRO(__VA_ARGS__, _repl, _rep)(__VA_ARGS__)
#define mp(a,b) make_pair((a),(b))
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#define fi first
#define se second
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
void _dbg(string){cout<<endl;}
template<class H,class... T> void _dbg(string s,H h,T... t){int l=s.find(',');cout<<s.substr(0,l)<<" = "<<h<<", ";_dbg(s.substr(l+1),t...);}
template<class T,class U> ostream& operator<<(ostream &o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream &o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

#define INF 1120000000
#define MOD 1000000007

long mod_pow(long x, long n, long p=MOD){
  if(x==0) return 0;
  long res=1;
  x %= p;
  while(n>0){
    if(n&1) res=res*x%p;
    x=x*x%p;
    n>>=1;
  }
  return res;
}
inline long mod_inv(long x, long p=MOD){ return mod_pow(x%p, p-2, p); }

vector<int> tree[200005];
int dep_nodes[200005];

int dd(int v, int dep){
  dep_nodes[dep]++;
  int ret = dep;
  for(auto to : tree[v]) ret = max(ret, dd(to, dep+1));
  return ret;
}

deque<vector<long>> memo[200005];

int calc(int v){
  vector<int> idxs;
  for(auto to : tree[v]){
    int r = calc(to);
    idxs.pb(r);
  }

  int m = idxs.size();

  if(m==0){
    memo[v] = {{1,1,0}};
    return v;
  }

  sort(all(idxs), [](const int &l, const int &r){
    return memo[l].size() < memo[r].size();
  });

  int p = idxs.back();
  if(m>=2){
    rep(j, memo[idxs[m-2]].size()){
      memo[p][j][0] += memo[p][j][2];
      memo[p][j][2] = 0;
    }
  }

  rep(i,m-1){
    int q = idxs[i];
    rep(j,memo[q].size()){
      memo[q][j][0] += memo[q][j][2];

      vector<long> nxt = {0,0,0};
      rep(ii,2) rep(jj,3){
        nxt[min(ii+jj,2)] += memo[q][j][ii] * memo[p][j][jj] %MOD;
      }
      rep(k,3) nxt[k] %= MOD;
      memo[p][j] = nxt;
    }
  }

  memo[p].push_front({1,1,0});
  return p;
}

int main(){
  int n;
  cin>>n;
  rep(i,n){
    int d;
    cin>>d;
    tree[d].pb(i+1);
  }

  fill(dep_nodes, dep_nodes+n, 0);
  int dep_max = dd(0, 0);

  int r = calc(0);

  long ans = 0;
  rep(i,dep_max+1){
    ans += memo[r][i][1] * mod_pow(2, n+1 - dep_nodes[i]);
    ans %= MOD;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 244724
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
using namespace std;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;

int main()
{
    string s;
    cin >> s;
    string ans = "";
    if (s == "Sunny")
    {
        ans = "Cloudy";
    }
    else if (s == "Cloudy")
    {
        ans = "Rainy";
    }
    else
    {
        ans = "Sunny";
    }
    cout << ans << endl;
    return 0;
}

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

using namespace std;

#define ll long long
#define fix cout << fixed; cout << setprecision(0)





void solve() {

	int n;
	cin >> n;
	ll total = 0;
	total += n / 500 * 1000;
	n %= 500;
	total += n / 5 * 5;
	cout << total << "\n";




	
}

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	fix;
	solve();

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iterator>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <numeric>
#include <iomanip>
#include <limits>

using namespace std;

int main(){

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

    for(long long int i=0;i<2*k-1;i++){
        if(x-(k-1)+i>-1000000 && 1000000>x-(k-1)+i){
            cout<<x-(k-1)+i<<endl;
        }
    }
    
    return 0;
}


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

int main(){
    string s;
    cin >> s;
    if(s == "SAT") cout << 1 << endl;
    else if(s == "FRI") cout << 2 << endl;
    else if(s == "THU") cout << 3 << endl;
    else if(s == "WED") cout << 4 << endl;
    else if(s == "TUE") cout << 5 << endl;
    else if(s == "MON") cout << 6 << endl;
    else if(s == "SUN") cout << 7 << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int sz = 2e5+5;
ll int arr[sz]={0},arr1[sz]={0};
//ll int arr[100][100]= {0};
int prime[10005]= {0};
vector <ll int> vec,vec1,vec2;
//vector <pair <int,int>> vec;
set<ll int>st;

int main()
{
    int n;
    cin>>n;
    map <string, int>mp;

    while(n--)
    {
        string s;
        cin>>s;

        mp[s]++;
    }
    string s = "AC";
    cout<<"AC x "<<mp[s]<<endl;
    s = "WA";
    cout<<"WA x "<<mp[s]<<endl;
    s= "TLE";
    cout<<"TLE x "<<mp[s]<<endl;
    s= "RE";
    cout<<"RE x "<<mp[s]<<endl;
}


Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace  std;
int main()
{
	int arr[3];
	cin>>arr[0]>>arr[1]>>arr[2];
	sort(arr,arr+3);
	if(arr[0]==5 && arr[1]==5 && arr[2]==7)
	{
		cout<<"YES"<<endl;
	}
	else
	{
		cout<<"NO"<<endl;
	}
	return 0;
}

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

#define ll long long
#define fw(p) for(int w=0;w<(p);w++)
#define fx(p) for(int x=0;x<(p);x++)
#define fy(p) for(int y=0;y<(p);y++)
#define fz(p) for(int z=0;z<(p);z++)
#define fyg(p,g) for(int y=(g);y<(p);y++)
#define fzg(p,g) for(int z=(g);z<(p);z++)
#define ce(d) cout<<d<<endl;
#define vecp(p) int aa;cin>>aa;(p).push_back(aa);
#define vecpl(p) long long aa;cin>>aa;(p).push_back(aa);
#define vecps(p) string aa;cin>>aa;(p).push_back(aa);
#define vecp2(p) cin>>aa;(p).push_back(aa);
#define vecpl2(p) long long a	b;cin>>ab;(p).push_back(ab);
#define vecps2(p) string ab;cin>>ab;(p).push_back(ab);
#define sorts(c) sort((c).begin(),(c).end());
#define reverses(c) reverse((c).begin(),(c).end());
#define vec(b) vector<int> (b);
#define vecl(b) vector<long long> (b);
#define vecs(b) vector<string> (b);
#define pb(b,a) (b).push_back((a));
#define doublece(a,b) cout<<(a)<<' '<<(b)<<endl;
#define pairs(s) vector<pair<int,int>> (s);
#define pairsp(s) int aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define MOD 1000000007
#define cey ce("Yes")
#define cen ce("No")
#define ceY ce("YES")
#define ceN ce("NO")
bool blue[5000];
int main()
{
	int N;
	string S;
	cin >> N >> S;
	vector<vector<int>> K(3);
	
	fx(N) {
		if (S[x]=='R') {
			K[0].push_back(x);
		}
		else if (S[x]=='G') {
			K[1].push_back(x);
		}
		else {
			K[2].push_back(x);
			blue[x] = true;
		}
	}
	ll ans = 0;
	ll b = K[2].size();
	fx(K[0].size()) {
		fy(K[1].size()) {
			int a = max(K[1][y], K[0][x]);
			int c = min(K[1][y], K[0][x]);
			int j = a-c;
			ans += b;
			if (c>=j&&blue[c-j]) {
				ans--;
			}
			if (a+j < N && blue[a + j]) {
				ans--; 
			}
			if (j%2==0 && blue[(a+c)/2]) {
				ans--;
			}
		}
	}
	ce(ans)
    return 0;
}



Measured memory_bytes: 3676
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <bits/stdc++.h>
#include<queue>
#include <numeric>
using namespace std;
 
//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
 
//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}
 template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
 
//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
 
//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define fore(i,a) for(auto &i:a)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
 
//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))
 
//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
 



int main(){
    string S;
    cin >> S;
    int L=S.length();
    bool exist=false;
    int res=0;
    string T;
    if(L%2==0){
        for(int i=0;i<L/2;++i){
            T+='h';
            T+='i';
        }
        if(T==S){
            exist=true;
        }
    }
    if(exist){
            cout << "Yes";
        }
    else{
        cout << "No";
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
const ll LINF=0x1fffffffffffffff;
const int INF=0x3fffffff;
const int MOD=1000000007;
#define VAR(type,...) type __VA_ARGS__;in(__VA_ARGS__)
#define VEC(type,name,size) vector<type> name(size);each(x, name)in(x)
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define rrep(i,a,b) for(int i=(a-1);i>=(b);--i)
#define each(x,v) for(auto &x:(v))
#define all(x) (x).begin(),(x).end()
#define print(x) cout<<(x)<<endl
void in(){} template<class T,class... U> void in(T &t,U &...u){cin>>t;in(u...);}
void solve();
int main(){cin.tie(0);ios::sync_with_stdio(0);solve();}

void solve() {
  VAR(int, N, L);
  VEC(string, S, N);
  sort(all(S));
  each(x, S) {
    cout << x;
  }
  cout << endl;
}


Measured memory_bytes: 256
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    if n == 1:
        print(0)
        exit()

    res = pow(10, n, mod) - (pow(9, n, mod) + pow(9, n, mod) - pow(8, n, mod))
    print(res % mod)


if __name__ == '__main__':
    resolve()


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

public class Main {

    public static void main(String[] args) {
        FastReader fs = new FastReader();
        final int inf = Integer.MAX_VALUE;
        String s = fs.nextLine();
        int n = s.length();
        if (s.charAt(n - 1) == 's') {
            s += "es";
        }
        else s += "s";
        System.out.println(s);





    }


    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}


Measured memory_bytes: 36340
#include<bits/stdc++.h>
#define lln long long int
#define llu unsigned lln
#define sc(n) scanf("%d",&n);
#define scl(n) scanf("%lld",&n);
#define scd(n) scanf("%lf",&n);
#define pf(res) printf("%d\n",res);
#define pfl(res) printf("%lld\n",res);
#define pfd(res) printf("%lf\n",res);
#define maxii 200005
using namespace std;
typedef pair<int,int> pii;
typedef pair<lln,lln> pll;
 vector<int> vi[maxii];
 vector<int>::iterator child;
typedef vector<lln> vl;
typedef vector<pii> vii;
typedef vector<pll> vll;


int arr[maxii];
int arr2[maxii];


int main()
{
    lln a,b,x;
    cin>>a>>b>>x;
    lln res1=a/x;
    lln res2=b/x;
    lln res=res2-res1;
    if(a%x==0)res++;
    cout<<res;

}






Measured memory_bytes: 8248
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>

// output
#define SPBR(w, n) std::cout<<(w + 1 == n ? '\n' : ' ');
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
// utility
#define ALL(i) (i).begin(), (i).end()
#define FOR(i, a, n) for(int i=(a);i<(n);++i)
#define RFOR(i, a, n) for(int i=(n)-1;i>=(a);--i)
#define REP(i, n) for(int i=0;i<int(n);++i)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define IN(a, x, b) (a<=x && x<b)
#define OUT(a, x, b) (x<a || b<=x)
template<class T> inline T chmax(T & a, const T b) { return a = (a < b) ? b : a; }
template<class T> inline T chmin(T& a, const T b) { return a = (a > b) ? b : a; }

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

using namespace std;


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

  vector<vector<int>> graph(N);
  REP(i, N-1){
    int u, v;
    cin >> u >> v;
    u--; v--;
    graph[u].emplace_back(v);
    graph[v].emplace_back(u);
  }

  vector<int> A(N);
  REP(i, N) cin >> A[i];
  sort(ALL(A), greater<>());

  queue<int> q;
  q.push(0);
  vector<int> ans(N);
  vector<bool> visited(N, false);
  int cnt = 0;
  while(!q.empty()){
    int p = q.front(); q.pop();
    visited[p] = true;
    ans[p] = A[cnt++];

    for(auto v : graph[p]){
      if(visited[v]) continue;
      q.push(v);
    }
  }

  int sum = 0;
  FOR(i, 1, N) sum += A[i];
  cout << sum << endl;
  REP(i, N){
    cout << ans[i]; SPBR(i, N);
  }

  return 0;
}

Measured memory_bytes: 1152
// Problem : E - Dist Max
// Contest : AtCoder - AtCoder Beginner Contest 178
// URL : https://atcoder.jp/contests/abc178/tasks/abc178_e
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

//#pragma GCC optimize "trapv"//  WA to RE int!!
#include <bits/stdc++.h>
#define FOR(i,n) for(int i=0;i<n;i++)
#define FORR(i,n) for(int i=n;i>=0;i--)
#define pb push_back
#define vint vector<int>
#define sint set<int>
#define mint map<int,int>
#define pint pair< int,int >
#define int long long int 
#define test int tt1234; cin>>tt1234;while(tt1234--)
#define endl "\n"
#define SI(a,n) int a[n];FOR(i,n) cin>>a[i];
#define input(a,n) int n;cin>>n; SI(a,n)
#define all(zz) zz.begin(),zz.end()
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define error(x) cerr << #x <<" is " << x << endl;
#define Error(a,b) cerr<<"( "<<#a<<" , "<<#b<<" ) = ( "<<(a)<<" , "<<(b)<<" )\n";
#define precision(x) cout<<fixed<<setprecision(x);
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define present(container, element) (container.find(element)!=container.end())
#define fint fast;test
#define set(a,x) memset(a,x,sizeof(a))
#define L(x)	((x)<<1)
#define R(x)	(((x)<<1)+1)
#define ft first
#define se second
#define MOD 1000000007
using namespace std;
template<typename... T> void rd(T&... args) { ((cin >> args), ...); }
template<typename... T> void pp(T... args) { ((cout << args << " "), ...); cout<<"\n"; }

void solve(){
	map<pair<int,int>,bool>vis;
	int n;
	rd(n);
	vector<pint>a;
	FOR(i,n)
	{
		int x,y;
		rd(x,y);
		if(vis[{x,y}])continue;
		a.pb({x,y});
		vis[{x,y}]=true;
	}
	if(a.size()==1)
	{
		pp(0);
		return ;
	}
	sort(all(a),[](pint A,pint B)
	{
		int aA=A.ft+A.se;
		int bB=B.ft+B.se;
		return aA<bB;
	});
	int ans=abs(a[0].ft-a[a.size()-1].ft)+abs(a[0].se-a[a.size()-1].se);
	sort(all(a),[](pint A,pint B)
	{
		int aA=A.ft-A.se;
		int bB=B.ft-B.se;
		return aA<bB;
	});
	ans=max(ans,abs(a[0].ft-a[a.size()-1].ft)+abs(a[0].se-a[a.size()-1].se));
	pp(ans);
	return;	
}


int32_t main() {
    // fint{
    	fast;
    	solve();
    // }
    return 0;
}


Measured memory_bytes: 18892
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a) for(int i = 0; i < (a); i++)
#define ALL(a) (a).begin(),(a).end()
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9;
const int MOD = 1e9 + 7;

signed main(){
    int n,c,k;
    cin >> n >> c >> k;
    int t[n];
    REP(i,n){
        cin >> t[i];
    }
    sort(t, t + n);
    int ans = 0;
	int right = 1;
	for(int left = 0; left < n; left++){
        right = left + 1;
        while(t[right] - t[left] <= k && right - left < c){
            right++;
        }
        ans++;
        left = right - 1;
    }
    cout << ans << endl;
}

Measured memory_bytes: 640
#include <iostream>
#include <stdio.h>
#include <string>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <math.h>
#include <vector>
#include <algorithm>

using namespace std;

bool exp(int n){
	if(n==1) return true;
	for(int i=2; i*i<=n; i++){
		int n_tmp=n;
		int cnt=0;
		while(n_tmp%i==0){
			n_tmp/=i;
			cnt++;
		}
		if(n_tmp==1 && cnt>=2){
			return true;
		}
	}
	return false;
}

int main(){
	int x;
	cin >> x;
	for(int i=x; i>0; i--){
		if(exp(i)){
			cout << i << endl;
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
using namespace std;
int N,ans=0,zj;
char S[105];
bool v1[26],v2[26];
int main()
{
	scanf("%d %s",&N,S);
	for(int i=0;i<N-1;i++)
	{
		zj=0;
		for(int j=0;j<26;j++)
		v1[j]=v2[j]=false;
		for(int j=i,a;j>=0;j--)
		{
			a=S[j];
			v1[a-'a']=true;
		}
		for(int j=i+1,a;j<N;j++)
		{
			a=S[j];
			v2[a-'a']=true;
		}
		for(int j=0;j<26;j++)
		{
			if(v1[j]==true&&v2[j]==true)
			zj++;
		}
		if(zj>ans)
		ans=zj;
	}
	printf("%d",ans);
	return 0;
}

Measured memory_bytes: 128
#define lp(i,n) for(int i=0;i<n;i++)
#define pau system("pause")
#include<bits/stdc++.h>

using namespace std;
int main() {
    int a,b;
    cin>>a>>b;
    if(abs(a-b)%2!=0)
        cout<<"IMPOSSIBLE"<<endl;
    else
        cout<<max(a,b)-abs(a-b)/2<<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<functional>
#include<queue>
#include<map>
#include<limits>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<utility>
#include<complex>
#include<cstdlib>
#include<set>
#include<cctype>

#define DBG cerr << '!' << endl;
#define REP(i,n) for(int (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(int (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(int (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int i = 0;i < (n);i++)cerr << v[i] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()

using namespace std;

typedef long long ll;
typedef vector<int> iv;
typedef vector<iv> iiv;
typedef vector<string> sv;

ll dist[100010];

int main()
{
	int n;
	cin >> n;
	
	vector<vector<pair<int,int> > > v(n);
	
	REP(i,n-1)
	{
		int a,b,c;
		cin >> a >> b >> c;
		
		a--;b--;
		v[a].PB(MP(b,c));
		v[b].PB(MP(a,c));
	}
	
	int Q,k;
	cin >> Q >> k;
	
	k--;
	
	queue<pair<int,int> > q;
	q.push(MP(k,-1));
	
	while(!q.empty())
	{
		pair<int,int> tmp = q.front();q.pop();
		
		REP(i,v[tmp.FI].size())
		{
			pair<int,int> tmptmp = v[tmp.FI][i];
			if(tmp.SE == tmptmp.FI)continue;
			
			dist[tmptmp.FI] = dist[tmp.FI] + tmptmp.SE;
			
			q.push(MP(tmptmp.FI,tmp.FI));
		}
	}
	
	//SHOW1d(dist,n);
	
	REP(i,Q)
	{
		int x,y;
		cin >> x >> y;
		
		cout << dist[x-1] + dist[y-1] << endl;
	}
	
		
	return 0;
}

Measured memory_bytes: 9204
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <vector>
using namespace std;
int main(){
  cin.tie(NULL);
  ios::sync_with_stdio(false);
  int a,b;
  cin>>a>>b;
  if(a<9 && b<9){
    cout<<"Yay!"<<"\n";
  }
  else{
    cout<<":("<<"\n";
  }
  return 0;
}

Measured memory_bytes: 3580
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using ld = long double;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
template<class T> using PQ = priority_queue<T>;
template<class T> using PQG = priority_queue<T, vector<T>, greater<T> >;
const int INF = 0xccccccc;
const ll LINF = 922337203685477580LL;
template<typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) {return a < b && (a = b, true);}
template<typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) {return a > b && (a = b, true);}
template<typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) { return is >> p.first >> p.second;}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) { return os << p.first << ' ' << p.second;}

const int mod = 1000000007;
//const int mod = 998244353;

struct mint {
  int64_t x;
  mint(int64_t x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(int64_t t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  //for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) {return mint(*this) /= a;}
};

istream& operator>>(istream& is, mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}
const int N = 3010;

//head

int n;
string s;
mint dp[N];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> s;
  rep(i, n) dp[i] = 1;

  rep(i, n-1) {
    mint now;
    if(s[i] == '<') {
      rep(j, n-i-1) {
        now += dp[j];
        dp[j] = now;
      }
    }
    else {
      rep(j, n-1-i) {
        now += dp[j+1];
      }
      rep(j, n-i-1) {
        dp[j] = now;
        now -= dp[j+1];
      }
    }
  }
  cout << dp[0] << endl;
}

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

#define ll long long
#define fr(i,a,b) for (int i=a ; i<b ; i++)
#define fre(i,a,b) for (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 a[100005];
long dp[100000005];


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int n;
    int k;
    cin>>n; cin>>k;
    fre(i,1,n)
    	cin>>a[i];
    mem(dp,0);
    dp[1] = 0;
    dp[2] = abs(a[2] - a[1]);
    for(int i=3;i<=n;i++){
    	dp[i] = inf;
    	if(k<i){
    		for(int j=i-1; j>=i-k;j--){
    			dp[i] = min(dp[i],(abs(a[i] - a[j]) + dp[j]));
    		}
    	}
    	else{
    		for(int j= i-1; j>=1;j--){
    			dp[i] = min(dp[i],(abs(a[i] - a[j]) + dp[j]));
    		}
    	}
    }
    cout<<dp[n]<<endl;
}

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

int main()
{
    char s[200005];
    cin >> s;
    int length = strlen(s);
    int begin, end;
    for(int i=0; i<length; i++){
        if(s[i]=='A'){
            begin=i+1;
            break;
        }
    }
    for(int i=length-1; i>=0; i--){
        if(s[i]=='Z'){
            end=i+1;
            break;
        }
    }
    cout << end-begin+1 << endl;
    return 0;
}

Measured memory_bytes: 384
#include "stdio.h"

int main(void)
{
    int N;
    scanf("%d", &N);
    int H[N-1];
    int max = 0;
    int count = 0;
    
    for( int i = 0; i < N; ++i){
        scanf("%d", &H[i]);
    }     

    max = H[0];
    count = 1;    
    for( int i = 1; i < N; ++i){
        if(H[i] >= max){
            max = H[i];
            count = count + 1;
        }        
    }
    printf("%d", count);    
    return 0;
}


Measured memory_bytes: 128
# python3
# -*- coding: utf-8 -*-
import sys
import math
import bisect
from fractions import gcd
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint

INF = float('inf')

ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
lmtx = lambda h: [list(map(int, lmis())) for _ in range(h)]
sys.setrecursionlimit(1000000000)


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


# main
a, b, c, d = mis()

while(True):
    c -= b
    if c <= 0:
        print('Yes')
        exit(0)
    a -= d
    if a <= 0:
        print('No')
        exit(0)



Measured memory_bytes: 10508
N,A = map(int,input().split())
X = list(map(int,input().split()))
X = [A-x for x in X]
dp = [[0]*(5001) for _ in range(N+1)]
dp[0][2500] = 1
for i in range(1,N+1):
    x = X[i-1]
    for j in range(5001):
        if 0<=j-x<5001:
            dp[i][j] = dp[i-1][j-x]+dp[i-1][j]
        else:
            dp[i][j] = dp[i-1][j]

print(dp[-1][2500]-1)

Measured memory_bytes: 41712
function Main(input) {
    const H = parseInt(input.shift());
    const W = parseInt(input.shift());
    const N = parseInt(input.shift());
    const sr = parseInt(input.shift());
    const sc = parseInt(input.shift());
    const S = input.shift();
    const T = input.shift();

    var left = sc, right = sc, top = sr, bottom = sr;

    for (var i = 0; i < N; i++) {
        var s = S.charAt(i);
        var t = T.charAt(i);
        if (s == "L") {
            left--;
        } else if (s == "R") {
            right++;
        } else if (s == "U") {
            top--;
        } else {
            bottom++;
        }
        if(left <= 0 || right > W || top <= 0 || bottom > H) {
            console.log("NO");
            return;
        } 

        if (t == "L") {
            right = Math.max(1, right-1);
        } else if (t == "R") {
            left = Math.min(W, left+1);
        } else if (t == "U") {
            bottom = Math.max(1, bottom-1);
        } else {
            top = Math.min(H, top+1);
        }
    }
    console.log("YES");
}

// 改行・空白で分割
Main(require("fs").readFileSync("/dev/stdin", "utf8").trim().split(/\n|\s/));


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

const int dk = 1000000007;

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

    if(n-m < -1 || n-m > 1){
        cout << 0 << endl;
        return 0;
    }

    long long int ans = 1;

    for(int i=1;i<=n;i++){
        ans = ans*i%dk;
    }
    for(int i=1;i<=m;i++){
        ans = ans*i%dk;
    }

    if(n==m){
        ans = ans*2%dk;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256