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

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define int long long
#define all(v) v.begin() , v.end()
#define pb push_back
#define pii pair<int,int>
#define F first
#define S second
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
int mod = 998244353;
vector<int>v;
int minCoins(int V)
{
    // table[i] will be storing the minimum number of coins
    // required for i value.  So table[V] will have result
    int table[V+1];

    int  m = v.size();
    // Base case (If given value V is 0)
    table[0] = 0;

    // Initialize all table values as Infinite
    for (int i=1; i<=V; i++)
        table[i] = INT_MAX;

    // Compute minimum coins required for all
    // values from 1 to V
    for (int i=1; i<=V; i++)
    {
        // Go through all coins smaller than i
        for (int j=0; j<m; j++)
            if (v[j] <= i)
            {
                int sub_res = table[i-v[j]];
                if (sub_res != INT_MAX && sub_res + 1 < table[i])
                    table[i] = sub_res + 1;
            }
    }
    return table[V];
}

int dp[200000][20];
int solve(int n , int i)
{
    if(n<0) return 1e13;
    if(n == 0) return 0;
    if(i == v.size()) {
        if(n == 0) return 0;
        return 1e13;
    }

    if(dp[n][i] != -1) return dp[n][i];

    int ans=1e13;
    if(n >= v[i]) {
        ans=min(ans , 1+solve(n-v[i] , i+1));
        ans=min(ans , 1+solve(n-v[i] , i));
    }
    ans=min(ans , solve(n , i+1));

    return dp[n][i] = ans;
}


int32_t main()
{   fastio;

    int n;
    cin>>n;
    memset(dp , -1 , sizeof(dp));

    v.pb(1);
    int p=6;
    while(p<=100000)
    {
        v.pb(p);
        p *= 6;
    }
    int z=9;
    while(z<=100000)
    {
        v.pb(z);
        z *= 9;
    }

    cout<<minCoins(n)<<"\n";

}


Measured memory_bytes: 35604
#include<cstdio>
const static int MAX_N = 1e5;

int par[MAX_N], rank[MAX_N], group_size[MAX_N];

void init_union_find(int n){
	for (int i = 0; i < n; ++i){
		par[i] = i;
		rank[i] = 0;
		group_size[i] = 1;
	}
}

int find(int x){
	if(par[x] == x) return x;
	else return par[x] = find(par[x]);
}

void unite(int x, int y){
	x = find(x);
	y = find(y);
	if(x == y) return;
	if(rank[x] < rank[y]){
		par[x] = y;
		group_size[y] += group_size[x];
	}else{
		par[y] = x;
		group_size[x] += group_size[y];
		if(rank[x] == rank[y]) rank[x]++;
	}
}

bool same(int x, int y){
	return find(x) == find(y);
}

int main(){
	int N, M, K;
	scanf("%d %d %d", &N, &M, &K);
	int friend_c[N];
	for (int i = 0; i < N; ++i) friend_c[i] = 0;
	init_union_find(N);
	for (int i = 0; i < M; ++i){
		int tmp1, tmp2;
		scanf("%d %d", &tmp1, &tmp2);
		tmp1--;tmp2--;
		friend_c[tmp1]--;friend_c[tmp2]--;
		unite(tmp1, tmp2);
	}
	for (int i = 0; i < K; ++i){
		int tmp1, tmp2;
		scanf("%d %d", &tmp1, &tmp2);
		tmp1--;tmp2--;
		if(same(tmp1, tmp2)){
			friend_c[tmp1]--;friend_c[tmp2]--;
		}
	}
	for (int i = 0; i < N; ++i){
		if(i) printf(" ");
		printf("%d", friend_c[i] + group_size[find(i)] - 1);
	}
	printf("\n");
	return 0;
}

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

typedef long long ll;

ll t1,t2;
ll a1,a2;
ll b1,b2;

int main() {
    cin >> t1 >> t2;
    cin >> a1 >> a2;
    cin >> b1 >> b2;
    if (a1 * t1 + a2 * t2 == b1 * t1 + b2 * t2) {
        cout << "infinity" << endl;
        return 0;
    }
    if (b1 * t1 + b2 * t2 > a1 * t1 + a2 * t2) {
        swap(a1,b1);
        swap(a2,b2);
    }
    if (b1 < a1) {
        cout << 0 << endl;
        return 0;
    }
    ll m = (a1 * t1 - b1 * t1) / (b1 * t1 + b2 * t2 - a1 * t1 - a2 * t2);
    m = max(m, 0LL);
    ll ans = (m + 1) * 2;
    ans--;
    if (m * (a1 * t1 + a2 * t2) + a1 * t1 == m * (b1 * t1 + b2 * t2) + b1 * t1) {
        ans--;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
sys.setrecursionlimit(10**6)

# n = int(input())
# G = [[] for i in range(n)]
# for i in range(n-1):
#   a,b = map(int,input().split())
#   # a-=1;b-=1
#   G[a].append(b)
#   G[b].append(a)

n=int(input())
G = [[] for i in range(n)]
for i in range(n):
  data = list(map(int,input().split()))
  for j in range(1,len(data)):
    G[i].append(data[j])

depth = [0] * n
parent = [[0] * n for i in range(20)]
def setdepth(node,pre,d):
  depth[node] = d
  parent[0][node] = pre
  for vi in G[node]:
    if vi == pre: continue
    setdepth(vi,node,d + 1)

setdepth(0,-1,0)

for k in range(19):
  for v in range(n):
    if parent[k][v] < 0: parent[k+1][v] = -1
    else: parent[k+1][v] = parent[k][parent[k][v]]

def lca(u,v):
  # 高度調整
  if depth[u] > depth[v]: u,v = v,u
  for k in range(20):
    if (depth[v] - depth[u]) >> k & 1:
      v = parent[k][v]
  # 2部探索
  if u == v:
    return u
  for k in range(19,-1,-1):
    if parent[k][u] != parent[k][v]:
      u = parent[k][u]
      v = parent[k][v]
  return parent[0][u]

Q = int(input())
for _ in range(Q):
  x,y = map(int,input().split())
  # x-=1;y-=1
  print(lca(x,y))
  # print(depth[x] + depth[y] - 2 * depth[lca(x,y)] + 1)



Measured memory_bytes: 143284
#include<cmath>
#include<queue>
#include<stack>
#include<deque>
#include<vector>
#include<cstdio>
#include<set>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#define per(i,a,b) for(long long int i=a;i<=b;++i)
#define rep(i,a,b) for(long long int i=a;i>=b;--i)
#define inf 0xf3f3f3f
#define ll long long 
using namespace std;
int main(){
	ll a,sum=0,x=1;
	scanf("%lld",&a);
	while(a){
		sum+=x;
		x*=2;
		a/=2;
	}
	printf("%lld",sum);
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	string s,s2="";
	cin>>s;
	for(int t=0;t<s.size();t++)
	{
		s2+=s[t];
		if(s[t]=='?')
		{
			s2.erase(t,1);
			s2+='D';
		}
	}
	cout<<s2;
	return 0;
} 

Measured memory_bytes: 3924
import java.util.*;

class Main {
	public static void main (String[] args) {
		Scanner scan = new Scanner(System.in);
		int uhouho = scan.nextInt();
		int h = uhouho / 3600;
		int m = (uhouho - h * 3600) / 60;
		int s = uhouho - 3600 * h - 60 * m;
		System.out.println(h + ":" + m + ":" + s );
	}
}

Measured memory_bytes: 17324
program main
  implicit none
  integer :: n, prev, i
  integer, allocatable :: a(:)
  read (*, *) n
  allocate (a(n))
  read (*, *) a(:)
  prev = 0
  do i = 1, n
    if (a(i) == prev + 1) prev = prev + 1
  end do
  if (prev == 0) then
    write (*, "(i0)") -1
  else
    write (*, "(i0)") n - prev
  end if
end program main


Measured memory_bytes: 1536
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <sstream>
#include <iomanip>

using namespace std;
 
typedef long long ll;
 
#define pb push_back
#define ppb pop_back
#define F first
#define S second
#define left(x) x * 2
#define right(x) x * 2 + 1

#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

#define ml " "
#define nl endl

#define lb lower_bound
#define ub upper_bound

#define fo(i, a, b) for (int i = a; i <= b; ++ i)
#define foo(i, a, b) for (int i = a; i >= b; -- i)

#define srt(a, n) sort(a, a + n)

const int N = 4e6 + 10;
const int sz = 1 << 17;
const int MOD = 1e9 - 7;
const int INF = 4e5 + 7;

main (){
	clog << "Ready\n";
	
	int a, b, c;
	cin >> a >> b >> c;
	cout << min(a + b + 1, c) + b;
	
	cerr << '\n';
}

Measured memory_bytes: 256
#include<stdio.h>
int main(){
  int a,b;
   scanf("%d %d",&a,&b);
   if(a<b){
    printf("a < b\n");
   }
   else if(a>b){
    printf("a > b\n");
   }
   else{
    printf("a == b\n");
   }
   return 0;
}




Measured memory_bytes: 2100
# スペース区切りの整数の入力
n,l=gets.chomp.split(" ").map(&:to_i);

taste = 0
#本来できるはずだった味の計算
for i in 0..n-1
    taste += l + i
end


min_diff = 99999
min_diff_taste= 0

for i in 0..n-1
    taste2 = 0
    for j in 0..n-1
        if i!=j
            taste2 += l + j
        end
    end
    if (taste - taste2).abs < min_diff
        min_diff_taste = taste2
        min_diff = (taste - taste2).abs
    end
end

# 出力
print("#{min_diff_taste}\n")


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

typedef long long int ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<ll, ll> Pair;
typedef vector<Pair> VP;

#define MOD 1000000007
#define times(n) rep(_idx, n)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define REP(i, s, n) for(int i = (int)(s); i < (int)(n); i++)
#define all(a) (a).begin(),(a).end()
#define pb push_back
#define mk make_pair
#define out(x) cout << (x) << endl;
#define DU(x) cerr << #x << " = " << (x) << endl;

template<typename _Ty>ostream& operator << (ostream& ostr, const vector<_Ty>& v) {if (v.empty()) {ostr << "[]";return ostr;}ostr << "[" << v.front();for (auto itr = ++v.begin(); itr != v.end(); itr++) {ostr << ", " << *itr;}ostr << "]";return ostr;}

int main() {
    int N; cin >> N;
    VI A(N + 1), B(N), C(N - 1);
    rep(i, N) cin >> A[i];
    rep(i, N) cin >> B[i];
    rep(i, N - 1) cin >> C[i];
    A[N] = -1;

    int ans = 0;
    rep(i, N) {
        ans += B[A[i] - 1];
        if(A[i] + 1 == A[i + 1]) ans += C[A[i] - 1];
        DU(ans)
    }
    out(ans);
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  char s[110];
  char t[5]="Yes";
  bool b=true;
  cin >>s;
  for(int i=0;i<sizeof(s);++i){
    if(i%2==0 && (s[i]=='L'))b=false;
    if(i%2==1 && (s[i]=='R'))b=false;
  }
  if(b)cout << "Yes";
  else cout << "No";
}

Measured memory_bytes: 256
/*
 * AOJ 0033: Ball
 * 题意：序号为1-10的10个球，按一定排列顺序进入2个队列之一，最终每队入队球的序号都为增序的方案是否存在。
 * 类型：贪心
 * 算法：对于每个球，若大于队列顶端元素，则可以记录该情况并继续递归。每次优先加入左边，可保证左边的顶端元素大于右边。
 */

#include <iostream>

using namespace std;

int balls[10];

int main() {
  //每次就先看左边能不能放，能放就放入，否则再看右边，右边也不能放，则不存在方案
  int n;
  cin >> n;
  while (n--) {
    for (int i = 0; i < 10; i++) cin >> balls[i];
    int l = 0, r = 0;
    bool flag = true;
    for (int i = 0; i < 10; i++) {
      if (balls[i] > l) {
        l = balls[i];
      } else if (balls[i] > r) {
        r = balls[i];
      } else {
        flag = false;
        break;
      }
    }
    if (flag) cout << "YES" << endl;
    else cout << "NO" << endl;
  }
}



// int a[10];


// int main() {
//   int T;
//   scanf("%d", &T);
//   while (T--) {
//     bool ans = true;
//     for (int i = 0; i < 10; ++i) {
//       scanf("%d", &a[i]);
//     }
//     int l, r;
//     l = r = 0;
//     for (int i = 0; i < 10; ++i) {
//       if (a[i] > l) {
//         l = a[i];
//       } else if (a[i] > r) {
//         r = a[i];
//       } else {
//         ans = false;
//         break;
//       }
//     }
//     printf("%s\n", ans ? "YES" : "NO");
//   }
//   return 0;
// }



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

int main()
{
    ios::sync_with_stdio(false);
    int a, b, x;
    cin >> a >> b >> x;

    if (x < a + b && x >= a && x - a <= b)
    {
        cout << "YES" << endl;
    }
    else
    {
        cout << "NO" << endl;
    }

    return 0;
}


Measured memory_bytes: 256
use std::cmp::{max, min};
use std::collections::{HashMap, HashSet, VecDeque};
use std::io::{stdin, Read};
use std::str::FromStr;

// https://qiita.com/tubo28/items/e6076e9040da57368845
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

#[allow(dead_code)]
fn main() {
    let n = read::<usize>();
    let mut s = (0..n)
        .map(|_| {
            let mut a = read::<String>().chars().collect::<Vec<_>>();
            a.sort();
            a
        })
        .collect::<Vec<_>>();
    s.sort();

    let mut prev = vec![];
    let mut ans = 0 as u64;
    let mut tmp = 0 as u64;
    for x in s {
        if x == prev {
            tmp += 1;
            ans += tmp;
        } else {
            tmp = 0;
        }
        prev = x;
    }
    println!("{}", ans)
}


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

using namespace std;

#define rep(i,n) for(int i=0;i<(n);i++)
#define repa(i,a,n) for(int i=(a);i<(n);i++)
#define rrep(i,n) for(int i=n;i>=0;i--)
#define rrepa(i,a,n) for(int i=n;i>=(a);i--)
#define all(a) (a).begin(),(a).end()
#define MOD 1000000007
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
#define vc vector

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<int,int> pi;

int main(){

    int n;
    cin>>n;
    vi a(n);
    rep(i,n)cin>>a[i];

    unordered_map<int,int> l;

    ll ans=0;

    rep(i,n){
        l[i+a[i]]++;
        ans+=l[i-a[i]];
    }

    cout<<ans<<"\n";
    
    return 0;
}

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

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

    if(a==b && b==c){
        cout << "1" << endl;
    }else if(a==b || b==c || a==c){
        cout << "2" << endl;
    }else{
        cout << "3" << endl;
    }
    return 0;
}

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

typedef vector<int> vi;

#define REPI(_i,len) for(int _i=0;_i<len;++_i)
#define REPI2(_i,_l,len) for(int _i=0,_l=len;_i<_l;++_i)
#define VREP(v,_itr,_end) for(auto _itr=v.begin(),_end=v.end();_itr!=_end;++_itr)
#define VCREP(v,_itr,_end) for(auto _itr=v.cbegin(),_end=v.cend();_itr!=_end;++_itr)
#define TST(st) typedef struct st st;

int abs(int x, int y) {
	return x >= 0 ? x : -x;
}

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

	vi a(N),b(N),c(N);
	REPI(i,N)
		cin >> a[i] >> b[i] >> c[i];

	vi aMax(N),bMax(N),cMax(N);

	REPI(i,N){
		if(i==0){
			aMax[0]=a[0];
			bMax[0]=b[0];
			cMax[0]=c[0];
			continue;
		}
		aMax[i]=a[i]+max(bMax[i-1],cMax[i-1]);
		bMax[i]=b[i]+max(cMax[i-1],aMax[i-1]);
		cMax[i]=c[i]+max(aMax[i-1],bMax[i-1]);
	}
	int max=aMax[N-1];
	if(max<bMax[N-1]){
		max=bMax[N-1];
	}
	if(max<cMax[N-1]){
		max=cMax[N-1];
	}
	cout<<max<<endl;

	return 0;
}

Measured memory_bytes: 5212
#include <stdio.h>

int main() {
    int n, m;
    int t[101] = { 0 };
    int p[101] = { 0 };
    int x[101] = { 0 };
    int sum = 0;
    int w = 0;

    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &t[i]);
    }

    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &p[i], &x[i]);
    }

    for (int i = 0; i < n; i++) {
        sum += t[i];
    }

    for (int i = 0; i < m; i++) {
        w = t[p[i] - 1];
        w -= x[i];
        printf("%d\n", sum - w); 
    }
    return 0;
}


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

int sg(int x, int k) {
	if (x%k==0) return x/k;
	int t = x/k+1;
	return sg(x-(x%k+t-1)/t*t,k);
}

int main() {
	int n;
	scanf("%d", &n);
	int ans = 0;
	while (n--) {
		int a, k;
		scanf("%d%d", &a, &k);
		ans ^= sg(a,k);
	}
	puts(ans?"Takahashi":"Aoki");
}









Measured memory_bytes: 384
#pragma region template
#include "bits/stdc++.h"
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const long long MOD = 1e9+7, MAX = 1e18, larg = 1e5, INF = -1e9;
long long A,B,C,D,E,F,G,H,I,J,K,L,N,M,O,P,Q,R,S,T,U,V,W,x,y,z;
long long max_value = INF, max_index = -1;
long long min_value = MAX, min_index = -1;
typedef long long ll;
typedef pair<ll, ll> Pa;

template <std::int_fast64_t Modulus> class modint {
  using u64 = std::int_fast64_t;
public:
  u64 a;
  constexpr modint(const u64 x = 0) noexcept : a(x % Modulus) {}
  constexpr u64 &value() noexcept { return a; }
  constexpr const u64 &value() const noexcept { return a; }
  constexpr modint operator+(const modint rhs) const noexcept {
    return modint(*this) += rhs;
  }
  constexpr modint operator-(const modint rhs) const noexcept {
    return modint(*this) -= rhs;
  }
  constexpr modint operator*(const modint rhs) const noexcept {
    return modint(*this) *= rhs;
  }
  constexpr modint operator/(const modint rhs) const noexcept {
    return modint(*this) /= rhs;
  }
  constexpr modint &operator+=(const modint rhs) noexcept {
    a += rhs.a;
    if (a >= Modulus) {
      a -= Modulus;
    }
    return *this;
  }
  constexpr modint &operator-=(const modint rhs) noexcept {
    if (a < rhs.a) {
      a += Modulus;
    }
    a -= rhs.a;
    return *this;
  }
  constexpr modint &operator*=(const modint rhs) noexcept {
    a = a * rhs.a % Modulus;
    return *this;
  }
  constexpr modint &operator/=(modint rhs) noexcept {
    u64 exp = Modulus - 2;
    while (exp) {
      if (exp % 2) {
        *this *= rhs;
      }
      rhs *= rhs;
      exp /= 2;
    }
    return *this;
  }
};
typedef modint<MOD> m;
#pragma endregion

int main() {
  cin >> N >> K >> S;
  rep(i, K){
    cout << S << " ";
  }
  rep(i, N-K){
    if(S == pow(10, 9)){
      cout << (int)(pow(10, 9)-1) << " ";
    }else{
      cout << (int)pow(10, 9) << " ";
    }
  }
}


Measured memory_bytes: 1408
// practice with Dukkha
#include <algorithm>
#include <iostream>

using namespace std;

const int N = 200000, MD = 1000000007;

struct V {
	long long a, b;
} uu[N], vv[N];

long long gcd(long long a, long long b) {
	return b == 0 ? a : gcd(b, a % b);
}

int main() {
	int n; cin >> n;
	int z = 0, pa = 1, pb = 1;
	int nu = 0, nv = 0;
	for (int i = 0; i < n; i++) {
		long long a, b; cin >> a >> b;
		if (a == 0 && b == 0) {
			z++;
			continue;
		}
		if (a == 0) {
			pa = pa * 2 % MD;
			continue;
		}
		if (b == 0) {
			pb = pb * 2 % MD;
			continue;
		}
		if (b < 0) {
			a = -a;
			b = -b;
		}
		long long d = gcd(abs(a), b); a /= d, b /= d;
		if (a > 0) {
			auto &u = uu[nu++];
			u.a = a, u.b = b;
		} else {
			auto &v = vv[nv++];
			v.a = b, v.b = -a;
		}
	}
	long long ans = (pa + pb - 1) % MD;
	sort(uu, uu + nu, [] (auto &u, auto &v) { return u.a < v.a || u.a == v.a && u.b < v.b; });
	sort(vv, vv + nv, [] (auto &u, auto &v) { return u.a < v.a || u.a == v.a && u.b < v.b; });
	for (int i = 0, j = 0; i < nu || j < nv; ) {
		int mode;
		if (j == nv)
			mode = 1;
		else if (i == nu)
			mode = 2;
		else if (uu[i].a < vv[j].a)
			mode = 1;
		else if (uu[i].a > vv[j].a)
			mode = 2;
		else if (uu[i].b < vv[j].b)
			mode = 1;
		else if (uu[i].b > vv[j].b)
			mode = 2;
		else
			mode = 0;
		int pu = 1, pv = 1;
		if (mode != 2) {
			int i_ = i;
			while (i_ < nu && uu[i_].a == uu[i].a && uu[i_].b == uu[i].b) {
				pu = pu * 2 % MD;
				i_++;
			}
			i = i_;
		}
		if (mode != 1) {
			int j_ = j;
			while (j_ < nv && vv[j_].a == vv[j].a && vv[j_].b == vv[j].b) {
				pv = pv * 2 % MD;
				j_++;
			}
			j = j_;
		}
		if (mode == 1)
			ans = ans * pu % MD;
		else if (mode == 2)
			ans = ans * pv % MD;
		else
			ans = ans * (pu + pv - 1) % MD;
	}
	ans = (ans + z - 1) % MD;
	if (ans < 0)
		ans += MD;
	cout << ans << '\n';
	return 0;
}


Measured memory_bytes: 6484
#include<bits/stdc++.h>
using namespace std;
const int maxn=4e5,mod=1e9+7;
int n,iv2,a[maxn],cnt[maxn],zero[maxn],t[maxn];
long long Ans,S,inv[maxn],D[maxn],invD[maxn];
long long tr[2][maxn];
long long qpow(long long x,int i){
	long long res=1;
	while(i){
		if(i&1){res=res*x%mod;}
		x=x*x%mod;i/=2;
	}
	return res;
}
int lowbit(int x){return x&(-x);}
void update(int x,int val){
    while(x<=n){
	    tr[1][x]=(tr[1][x]+val)%mod;
		tr[0][x]++;
		x+=lowbit(x);
	}
}
long long sum(int x,int opt){
	long long res=0;
	while(x){
		res=(res+tr[opt][x])%mod;
		x-=lowbit(x);
	}
	return res;
}
int main(){
	scanf("%d",&n);
	Ans=0;S=1;iv2=qpow(2,mod-2);
	inv[1]=1;for(int i=2;i<=n;i++){inv[i]=(inv[mod%i]*(mod-mod/i))%mod;}
	for(int i=1;i<=n;i++){scanf("%d",&a[i]);cnt[a[i]]++;}
	for(int i=n;i>=1;i--){cnt[i]=cnt[i]+cnt[i+1];}
	for(int i=n;i>=1;i--){S=S*(cnt[i]+i-n)%mod;}
	D[0]=t[0]=1;
	for(int i=1;i<=n;i++){
		long long tmp=(cnt[i]-n-1+i)*qpow(cnt[i]-n+i,mod-2)%mod;
		if(tmp==0){zero[i]=zero[i-1]+1;t[zero[i]]=i;D[i]=D[i-1];}
		else{zero[i]=zero[i-1];D[i]=D[i-1]*tmp%mod;}
		invD[i]=qpow(D[i],mod-2);
	}
	memset(tr,0,sizeof(tr));
	for(int i=1;i<=n;i++){
		Ans=(Ans+S*(sum(a[i],1)-sum(t[zero[a[i]]]-1,1)+mod)%mod*D[a[i]]%mod*iv2%mod)%mod;
		update(a[i],invD[a[i]]);
	}
	memset(tr,0,sizeof(tr));
	for(int i=n;i>=1;i--){
		Ans=(Ans+mod-S*(sum(a[i]-1,1)-sum(t[zero[a[i]]]-1,1)+mod)%mod*D[a[i]]%mod*iv2%mod)%mod;
		Ans=(Ans+S*sum(a[i]-1,0)%mod)%mod;
		update(a[i],invD[a[i]]);
	}
	printf("%lld\n",Ans);
	return 0;
}

Measured memory_bytes: 21376
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <fstream>
#include <cstdlib>
#include <ctime>
#include <string>
#include <cstring>
#include <fstream>
#include <random>
#include <tuple>
using namespace std;

bool cmp(const pair<long long, long long> &p1, pair<long long,long long> &p2) {
    return p1.second * p2.first < p1.first * p2.second;
}
int main() {
    vector<pair<long long,long long>> v;
    long long q, h, s, d, n;
    cin>>q>>h>>s>>d>>n;
    v.emplace_back(25, q);
    v.emplace_back(50, h);
    v.emplace_back(100, s);
    v.emplace_back(200, d);
    sort(v.begin(), v.end(), cmp);
    long long ans = n * 100 / v[0].first * v[0].second;
    if (v[0].first == 200 && n % 2 != 0) {
        ans += v[1].second * 100 / v[1].first;
    }
    cout<<ans<<endl;
}

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

int main(){
    string s;
    cin >> s;
    int t = 0;
    for( char cc : s ) t += cc - '0';
    if( t % 9 == 0 ) cout << "Yes";
    else cout << "No";
    return 0;
}

Measured memory_bytes: 3696
#include <stdio.h>

int main(void)
{
    char S[5];
    int i,yen=700;

    scanf("%s",S);

    for(i=0;i<3;i++){
        if(S[i]=='o'){
            yen+=100;
        }
    }

    printf("%d\n",yen);

    return 0;
}

Measured memory_bytes: 128
using System;

namespace tes
{
    class Program
    {
        static void Main(string[] args)
        {
            var line1 = Console.ReadLine().Split();
            Array.Sort(line1);
            Console.Write(int.Parse(line1[0]) + " " + int.Parse(line1[1]) + " " + int.Parse(line1[2]));
            Console.WriteLine();
        }
    }
}

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

#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))

typedef long long LL;

int main(){
  int n;
  cin >> n;
  string s;
  cin >> s;
  string aka,ao;
  LL ans=0;
  vector<vector<LL>> dp(n+1,vector<LL>(n+1,0));
  for(int i=0;i<(1<<n);i++){
    aka=ao="";
    for(int j=0;j<n;j++){
      if(i&(1<<j)){
        aka=s[j]+aka;
      }else{
        ao=s[j]+ao;
      }
    }
      for(int k=0;k<=n;k++){
        for(int j=0;j<=n;j++){
          dp[k][j]=0;
        }
      }
    if(s[n]==aka[0]) dp[1][1]=1;
    if(s[n]==ao[0]) dp[1][0]=1;
    for(int k=2;k<=n;k++){
      if(k<=ao.length()){
        if(s[k+n-1]==ao[k-1]){
          dp[k][0]=dp[k-1][0];
        }
      }
      for(int l=1;l<=k&&l<=aka.length();l++){
        if(s[k+n-1]==ao[k-l-1]){
          dp[k][l]+=dp[k-1][l];
        }
        if(s[k+n-1]==aka[l-1]){
          dp[k][l]+=dp[k-1][l-1];
        }
      }
    }
    ans+=dp[n][aka.length()];
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pi acos(-1)
#define IOS ios_base::sync_with_stdio(0); cin.tie(); cout.tie();
#define fi first
#define se second
#define pf push_front
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define debug(val) cerr << "Value of " << #val << " : " << val << '\n';
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1e9 + 7;
const ll inf = 0x3f3f3f3f;
const ll nax = 0;

int main(){
	IOS	
	int n, arr[105], ans=0;
	cin >> n;
	for(int i=1;i<=n;++i){
		cin >> arr[i];
		if(i&1 && arr[i]&1) ans++;
	}
	cout << ans << '\n';
}


Measured memory_bytes: 3600
#include<stdio.h>
int main(void)
{
	int a, b, k,yaku[1000],su;
	scanf("%d", &a);
	scanf("%d", &b);
	scanf("%d", &k);
	int i,co=0;
	for (i = 1; i <= 100; i++) {
		if (a%i == 0) {
			if (b%i == 0) {
				yaku[co]=i;
				co++;
			}
		}
	}
	su = yaku[co - k];
	printf("%d\n", su);
	return 0;
}

Measured memory_bytes: 128
S=input()
T=input()
ans='UNRESTORABLE'
for j in range(len(S)-len(T)+1):
    flag=1
    for i in range(len(T)):
        if S[j+i]==T[i] or S[j+i]=='?':
            continue
        else:
            flag=0
    if flag:
        ans =S[0:j]+T+S[j+len(T):]
        ans =ans.replace('?','a')

print(ans)



Measured memory_bytes: 2940
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <cstring>
#include <utility>
#include <numeric>

using namespace std;

int main(){

    long long A, B, C;
    cin >> A >> B >> C;

    if(A % 2 == 0 || B % 2 == 0 || C % 2 == 0){
        cout << 0 << endl;
    }
    else{
        vector<long long> a = {A, B, C};
        sort(a.begin(), a.end());
        cout << a[0] * a[1] << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<math.h>
#include<vector>
#include<array>
#include<algorithm>
#include<numeric>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
using ll = long long;
using P = pair<int, int>;
const ll INF=1e18;
#define PI 3.14159265358979323846
const int MAX = 510000;
const int MOD = 1000000007;

ll fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
ll COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

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

    int N;
    cin >> N;
    map<string, int> prisesDic;
    for (int i=0; i<N; i++) {
        string str;
        cin >> str;

        if (prisesDic.count(str) == 0){
            prisesDic[str] = 1;
        }
    }

    cout << prisesDic.size() << '\n';

    return 0;
}

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << setprecision(20) << fixed;
  string A, B, C;
  cin >> A >> B >> C;
  cout << A[0] << B[1] << C[2] <<endl;
} 


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

typedef int i32;
typedef long long i64;
typedef unsigned int u32;
typedef unsigned long long u64;


template<typename First, typename Second, typename Third>
struct triple {
   First first;
   Second second;
   Third third;
};


#define debug(x)  cerr<<x<<"\n";
#define loop(i,n) for(i32 i = 0; i < n; ++i)
#define pi  pair<i32,i32>
#define ti  triple<i32,i32,i32>
#define mk  make_pair
#define vi  vector<i32>
#define vll vector<i64>
#define fastInOut ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pr(a) for(auto x:a) cout<<x<<" ";
#define prmap(m) for(auto x:m) cout<<x.first<<" "<<x.second<<"\n";
using namespace std;

bool isPrime(i64 x){
	
	for(i64 i=2;i*i<=x;i++)
		if(x%i==0)
			return false;
	return true;
}

vi V;
const i32 N=1e4+9;
bool prime[N]; 
void SieveOfEratosthenes() 
{
    for (int  p=2; p*p<=N; p++){ 
        if (prime[p] == false){ 
            for (int  i=p*p; i<=N; i += p) 
                prime[i] = true; 
        } 
    } 
    int u=0,mx=0;
    for (int p=2; p<=N; p++) 
      if (!prime[p]) {
         V.push_back(p);
    }
   
}
i64 x;
void solve(){
     cin>>x;
     i32 count=0;
     for(int i=11;count<x;i+=10){
          if(isPrime(i)){
             cout<<i<<" ";count++;
          }
     }
}
int main(){
    fastInOut
    solve();
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <map>

using namespace std;

int main(void) {
    map<string, int> mp;
    int N;
    cin >> N;
    for(int i=0; i<N; i++) {
        string s;
        cin >> s;
        mp[s]++;
    }
    int M;
    cin >> M;
    for(int i=0; i<M; i++) {
        string t;
        cin >> t;
        mp[t]--;
    }

    int ans = 0;
    for(auto itr=mp.begin(); itr!=mp.end(); itr++) {
        ans = max(ans, itr->second);
    }

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


Measured memory_bytes: 384
import sys
input = sys.stdin.readline

from bisect import bisect_left
from math import pi

sx,sy,gx,gy = map(int,input().split())
N = int(input())
XY = [tuple(int(x) for x in input().split()) for _ in range(N)]

if sx > gx:
    sx,gx = gx,sx
    sy,gy = gy,sy
gx -= sx
gy -= sy

XY = [(x-sx,y-sy) for x,y in XY if 0<=x-sx<=gx]

if gy >= 0:
    XY = [(x,y) for x,y in XY if 0<=y<=gy]
else:
    gy = -gy
    XY = [(x,-y) for x,y in XY if 0<=-y<=gy]

# xは相異なるので...
XY.sort()
Y = [y for x,y in XY]

# longest increasing subseq
INF = 10**18
dp = [INF] * (len(Y)+1)
for y in Y:
    idx = bisect_left(dp,y)
    dp[idx] = y
L = bisect_left(dp,INF)

if L <= min(gx,gy):
    answer = 100*(gx+gy) + (10*pi/2-20) * L
else:
    answer = 100*(gx+gy) + (10*pi/2-20) * (L-1) + (10*pi-20)

print(answer)

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

using namespace std;

int main (){
    ios_base::sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    int a[n];
    for (int i = 0; i < n; i++)
        cin >> a[i];
    int tot = 0;
    for (int i = 0; i < n; i++){
        int b = min(a[i] - 0, k - a[i]);
        tot += 2 * b;
    }
    cout << tot;
    return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;

public class Main {

	static BufferedReader reader;
	final static boolean MODE_DEBUG = false;
	//static field here
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		reader = new BufferedReader(new InputStreamReader(System.in));
		//code here
		int[] NM = readLineInt();
		int N = NM[0];
		int[] a = readLineInt();
		int M = a[0];
		int K = a[1];
		
		print((M%N==0||K%N==0)||(M/N!=K/N)?"OK":"NG");
		//String[] s = readLine();
		//print(num);
	}
	
	//functions here
	//note that all methods should be STATIC


	private static <T> int arraySearch(T needle, T[] heystack) {
		for(int i=0;i<heystack.length;i++) {
			if(needle.equals(heystack[i])) {
				return i;
			}
		}
		return -1;
	}
	private static int[] sort(int[] base) {
		int[] copy = array_copy(base);
		Arrays.sort(copy);
		return copy;
	}
	private static int[] array_copy(int[] base) {
		int[] copy = new int[base.length];
		for(int i=0;i<base.length;i++) {
			copy[i] = base[i];
		}
		return copy;
	}
	private static int[] asArray(ArrayList<Integer> ints) {
		int[] intlist = new int[ints.size()];
		for(int i=0;i<intlist.length;i++) {
			intlist[i] = ints.get(i);
		}
		return intlist;
	}
	private static String[] readLine(){
		try{
			return reader.readLine().split(" ");
		}catch(Exception e){
			e.printStackTrace();
			return new String[]{e.getMessage()};
		}
	}
	private static int[] readLineInt(){
		try{
			String[] s = readLine();
			int[] ints = new int[s.length];
			for(int i=0;i<ints.length;i++) {
				ints[i] = Integer.parseInt(s[i]);
			}
			return ints;
		}catch(Exception e){
			e.printStackTrace();
			return null;
		}
	}
	private static byte[] readLineByte(){
		try{
			String[] s = readLine();
			byte[] bytes = new byte[s.length];
			for(int i=0;i<bytes.length;i++) {
				bytes[i] = Byte.parseByte(s[i]);
			}
			return bytes;
		}catch(Exception e){
			e.printStackTrace();
			return null;
		}
	}
	private static char[] readLineChar(){
		try{
			String[] s = readLine();
			char[] chars = new char[s.length];
			for(int i=0;i<chars.length;i++) {
				chars[i] = (char)Integer.parseInt(s[i]);
			}
			return chars;
		}catch(Exception e){
			e.printStackTrace();
			return null;
		}
	}
	private static void print(Object o){
		System.out.println(o);
	}
	private static void print(){
		System.out.println();
	}
	private static void printd(Object o){
		if(MODE_DEBUG)System.err.println(o);
	}
	private static void printd(){
		if(MODE_DEBUG)System.err.println();
	}
}


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

a = list(map(int,input().split()))
edge = [0]*N
for _ in range(M):
    b,c = map(int,input().split())
    b -= 1;c -= 1
    if a[b] > a[c]:
        edge[c] += 1
    elif a[b] < a[c]:
        edge[b] += 1
    else:
        edge[b] += 1
        edge[c] += 1

print(edge.count(0))


Measured memory_bytes: 84888
#ifdef __cplusplus
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
#else
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#endif

#define rep(i,n) for(int i = 0; i < (n); ++i)
 
#define BIG_PRIME 1000000007
#define BP_remainder(x) ((x) % BIG_PRIME)

#define INF (1 << 30)
#define INF_NEG (INF * -1)
#define INF_LONG (1LL << 62)
#define INF_LONG_NEG (INF_LONG * -1L)

typedef long long ll;
typedef char str255[256];
int StrLen(char *s) { for(int ptr = 0;; ++ptr) if(!s[ptr]) return ptr; } 
// char * の後ろから n 文字削除, 削除後の文字数を返す
int StrDel(char *s, int n) { int l = StrLen(s); s[l - n + 1] = '\0'; return l - n; }

int NumDigits(int i){ char s[20]; return sprintf(s, "%d", i); }
int NumDigitsLL(long long l){ char s[30]; sprintf(s, "%lld", l); return strlen(s); }

int is1stAns = 1;
#ifdef __cplusplus
template <class T> 
void print(T t) { if (is1stAns) cout << t, is1stAns = 0; else cout << " " << t; }
#else
void printI(int    i) { if (is1stAns) printf(  "%d", i), is1stAns = 0; else printf(  " %d", i); }
void printL(ll     l) { if (is1stAns) printf("%lld", l), is1stAns = 0; else printf(" %lld", l); }
void printD(double d) { if (is1stAns) printf("%.9f", d), is1stAns = 0; else printf(" %.9f", d); }
void printC(char   c) { if (is1stAns) printf(  "%c", c), is1stAns = 0; else printf(  " %c", c); }
void printS(char  *s) { if (is1stAns) printf(  "%s", s), is1stAns = 0; else printf(  " %s", s); }
#endif

signed main()
{
#ifdef __cplusplus
    cout << fixed << setprecision(9);
#endif

    int A, B;
    scanf("%d %d", &A, &B);
    int sum = A + B;
    if (sum % 2){
        puts("IMPOSSIBLE");
    } else {
        printf("%d\n", sum / 2);
    }

    return 0;
}


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

#define int long long

signed main(){
	int x,y,a,b,c;
	cin>>x>>y>>a>>b>>c;

	priority_queue<pair<int,int> > h;

	while(a--){
		int w;
		cin>>w;
		h.push(make_pair(w,1));
	}
	
	while(b--){
		int w;
		cin>>w;
		h.push(make_pair(w,2));
	}
	
	while(c--){
		int w;
		cin>>w;
		h.push(make_pair(w,3));
	}
	
	int z=x+y;
	int ans=0;
	
	while(z){
		pair<int,int> f=h.top();
		h.pop();
		if(f.second==3){
			ans+=f.first;
			--z;
		}
		else if(f.second==1 && x){
			ans+=f.first;
			--x;
			--z;
		}
		else if(f.second==2 && y){
			ans+=f.first;
			--y;
			--z;
		}
	}
	
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 10476
N = int(input())
x = tuple(map(int, input().split()))
mid = (max(x) + min(x)) // 2
curr_sum = 0
dp = [10**9] * 101
for i in range(1, 101):
  dp[i] = 0
  for num in x:
    dp[i] += (num - i) ** 2
print(min(dp))

Measured memory_bytes: 38512
#include <stdio.h>

int main(){
	int a,b,c,x;
	int ans = 0;
	scanf("%d",&a);
	scanf("%d",&b);
	scanf("%d",&c);
	scanf("%d",&x);

	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++;
				}
			}
		}
	}
	printf("%d",ans);
	return 0;

}

Measured memory_bytes: 128
n, m = map(int, input().split())


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors


divisors = sorted(make_divisors(m), reverse=True)
ans = []
for div in divisors:
    if div <= m//n:
        print(div)
        exit()


Measured memory_bytes: 3060
using System;
using System.Linq;

namespace abc129
{
    class B
    {
        static void Main(string[] args)
        {
            var N = Input.Int();
            var W = Input.IntArray();

            var l = 0;
            var r = W.Sum();
            int min = r;

            for (int i = 0; i < N; i++)
            {
                l += W[i];
                r -= W[i];
                min = Math.Min(min, Math.Abs(l - r));
            }

            Console.WriteLine(min);
        }

        /** Input Class */
        internal static class Input
        {
            /** input int */
            public static int Int() => int.Parse(Console.ReadLine());

            /** input str */
            public static string Str() => Console.ReadLine();

            /** input array of int */
            public static int[] IntArray() => Console.ReadLine().Split(' ').Select(int.Parse).ToArray();

            /** input array of string */
            public static string[] StrArray() => Input.Str().Split(' ');

            /** input array of char */
            public static char[] charArray() => Input.Str().ToCharArray();
        }

    }
}

Measured memory_bytes: 13396
x, y = map(int, input().split())
z = [0, 300000, 200000, 100000]

if(x == 1 and y == 1):
    print(1000000)
elif(1 <= x <= 3 and 1 <= y <= 3):
    print(z[x]+z[y])
elif(1 <= x <= 3):
    print(z[x])
elif(1 <= y <= 3):
    print(z[y])
else:
    print(0)

Measured memory_bytes: 3064
# https://atcoder.jp/contests/abc138/tasks/abc138_d

import sys
input = sys.stdin.readline
import marshal


class Graph:
    def __init__(self, n, dictated=False, decrement=True, destroy=False, edges=[]):
        self.n = n
        self.dictated = dictated
        self.decrement = decrement
        self.destroy = destroy
        self.edges = [[] for _ in range(self.n)]
        self.parent = [-1]*self.n
        self.info = [-1]*self.n
        for x, y in edges:
            self.add_edge(x,y)

    def add_edge(self, x, y):
        if self.decrement:
            x -= 1
            y -= 1
        self.edges[x].append(y)
        if self.dictated == False:
            self.edges[y].append(x)

    def add_adjacent_list(self, i, adjacent_list):
        if self.decrement:
            self.edges[i] = list(map(lambda x: x - 1, adjacent_list))
        else:
            self.edges[i] = list(adjacent_list)

    def dfs2(self, info, start, goal=-1, time=0, save=False):
        """
        :param info: 各頂点の付加情報
        :param start: スタート地点
        :param goal: ゴール地点
        :param save: True = 前回の探索結果を保持する
        :return: ゴール地点までの距離。存在しなければ -1
        """

        if self.decrement:
            start -= 1
            goal -= 1
        if not save:
            self.parent = [-1] * self.n
        if self.destroy:
            edge2 = self.edges
        else:
            edge2 = marshal.loads(marshal.dumps(self.edges))

        p, t = start, time
        self.parent[p] = -2
        while True:
            if edge2[p]:
                q = edge2[p].pop()
                if q == self.parent[p] and not self.dictated:
                    """ 逆流した時の処理 """
                    """"""""""""""""""""
                    continue
                if self.parent[q] != -1:
                    """ サイクルで同一点を訪れた時の処理 """
                    """"""""""""""""""""
                    continue
                if q == goal:
                    """ ゴール時の処理"""
                    # return t + 1
                    """"""""""""""""""""
                    continue
                """ p から q への引継ぎ"""
                info[q] += info[p]
                """"""""""""""""""""
                self.parent[q] = p
                p, t = q, t + 1
            else:
                """ 探索完了時の処理 """
                """"""""""""""""""""
                if p == start and t == time:
                    break
                p, t = self.parent[p], t-1
                """ 二度目に訪問時の処理 """

                """"""""""""""""""""
        return info


######################################################################################################

N, Q = map(int, input().split())  # N:頂点数, Q: クエリの数
M = N-1

graph = Graph(N, dictated=False, destroy=True)

for _ in range(M):
    x, y = map(int, input().split())
    graph.add_edge(x,y)

info = [0] * N
for _ in range(Q):
    p, x = map(int, input().split())
    info[p - 1] += x

print(*graph.dfs2(info, start=1))



Measured memory_bytes: 116128
#include<iostream>
#include<iomanip>
using namespace std;
char db[16]={'C','O','D','E','F','E','S','T','I','V','A','L','2','0','1','6'};
int main()
{
	char sr[16];
	int s=0;
	cin>>sr;
	for(int i=0;i<16;i++)
	{
		if(sr[i]!=db[i])
			s++;
	}
	cout<<s<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
// define
#define int long long
#define UNIQUE(v) v.erase(unique(all(v)), v.end());
#define ZIP(v) sort(all(v)),UNIQUE(v)
#define ADD(a, b) a = (a + b) % mod
#define SUB(a, b) a = (a+mod-b)%mod
#define MUL(a, b) a = (a * b) % mod
#define rollcall cout << "I'm Sucu." << endl;
#define repi(i,m,n) for(int i = m;i < n;i++)
#define drep(i,n,m) for(int i = n;i >= m;i--)
#define rep(i,n) repi(i,0,n)
#define rrep(i,n) repi(i,1,n+1)
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(), v.rend()
#define dmp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define fi first
#define se second
// debug
template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p){
  os << "(" << p.first << "," << p.second << ")";return os;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v){
  for (auto it = v.begin();it != v.end();++it){
    if(it != v.begin())os << " ";os << *it;
      }return os;
}
template <typename T, typename U>
ostream &operator<<(ostream &os, const map<T, U> &mp){
  for(auto x: mp)os << "(" << x.first << "," << x.second << ")" << endl;
  return os;
}
template<typename T, int SIZE>
int array_length(const T (&)[SIZE]){return SIZE;}
template<typename T, int N>
void PRINTF(const T (&a)[N], int s = N, int t = -1, bool f = true){
	if(t == -1){rep(i,s){if(i)cout << " ";cout << a[i];}}
	else repi(i,s,t){if(i!=s)cout << " ";cout << a[i];}
	if(f)cout << "\n";
}
template<typename T, int N1, int N2>
void PRINTF(const T (&a)[N1][N2], int h = N1, int w = N2){
	rep(i,h){rep(j,w){cout << a[i][j] << " \n"[j==w-1];}}
}
// typedef
typedef complex<double> Point;
typedef pair<int, int> P;
typedef pair<int, P> PP;
typedef pair<P, int> Pi;
typedef vector<int> vi;
typedef deque<int> dq;
const int inf = 1e9+7;
const int INF = 1e18+7;
const int MAX = 5e5;


int x[MAX], y[MAX], h[MAX];
signed main(){
   int n;
   scanf("%lld", &n);
   rep(i,n)scanf("%lld%lld%lld", &x[i], &y[i], &h[i]);
   rep(Y,101)rep(X,101){
     int H = 0, f = 1;
     rep(i,n)if(h[i])H = h[i]+llabs(Y-y[i])+llabs(X-x[i]);
     rep(i,n){
       int hh = max(H-llabs(Y-y[i])-llabs(X-x[i]), 0LL);
       if(h[i] != hh)f = 0;
     }
     if(f and H){
       printf("%lld %lld %lld\n", X, Y, H);
       return 0;
     }
   }
  return 0;
}










Measured memory_bytes: 4352
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <functional>
#include <map>
#include <queue>
#define REP(i,n) for(int (i)=0; (i)<(n); (i)++)
using namespace std;
using ll = long long;
ll MOD = 1e9+7;


int main(int argc, const char * argv[]) {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    string s;
    cin >> s;
    int ans = 0;
    for(int i = 0; i < s.size(); i++){
        if(s[i] == '2'){
            ans++;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include<math.h>
#include<map>
#include<iostream>
#include <algorithm>
#include <string>
#include<vector>
#include<array>
#include<tuple>
#include<queue>
#include<stack>
#include<iomanip>
#include<bitset>
#include <list>
#include<numeric>
#include <fstream>
#include<set>
//AtCoderC++.cpp

using namespace std;

template<typename T>
inline T ceiling(T n, T d) {
	return n % d == 0 ? n / d : n / d + 1;
}


int main() {
int a;string s;cin>>a>>s;
cout<<(a<3200?"red":s)<<endl;
}

Measured memory_bytes: 256
def calc_intersection():
    n = int(input())
    s = input()
    list_intersection = []

    for i in range(1, n):
        a = set(s[:i])
        b = set(s[i:])
        intersection_a_b = a.intersection(b)
        list_intersection.append(len(intersection_a_b))
    return max(list_intersection)


if __name__ == '__main__':
    print(calc_intersection())

Measured memory_bytes: 9200
#include<iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int Max = 1000000;
int main(){
  	int N;
  	cin >> N;
  	int X[N];
  	for(int i=0;i<N;i++) cin >> X[i];

  	int M = 10000000;

  	for(int k=1;k<=100;k++){
  		int sum = 0;
  		for(int i=0;i<N;i++){
  			sum += (X[i]-k)*(X[i]-k);
  		}
  		M = min(sum, M);
  	}
  	cout << M <<endl;

  	return 0;
}


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

haba = list()
max_L = 0
min_R = 10 ** 5 + 1
for i in range(M):
    L, R = map(int, input().split())
    haba.append([L, R])
    max_L = max(max_L, L)
    min_R = min(min_R, R)

print(max(min_R + 1 - max_L, 0))

Measured memory_bytes: 19600
n = gets.to_i
nums = gets.to_s.split.map(&:to_i)

cnt = 0
prev_cnt = 0
prev = nums.first
nums.each_with_index do |num, idx|
  next if idx == 0
  if prev >= num
    cnt += 1
  else
    prev_cnt = [cnt, prev_cnt].max
    cnt = 0
  end
  prev = num
end

puts [cnt, prev_cnt].max


Measured memory_bytes: 11012
#include<bits/stdc++.h>
using namespace std ;
#define int long long
#define ld long double
#define fast ios_base::sync_with_stdio(false) ;cin.tie(NULL);cout.tie(NULL)
#define F(i,a,b) for(int i= (int)(a); i<(int)(b);i++)
#define FI(i,a,b) for(int i=(int)(a);i<=(int)(b);i++)
#define RF(i,a,b) for(int i = (int)(a); i >= (int)(b); i--)
#define what_is(x) cerr << #x << " is " << x << endl;
#define ms(x,a) memset(x,(int)(a),sizeof(x))
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define pii pair<int,int>
#define vi vector<int >
#define pb push_back
#define endl '\n'
#define mp make_pair
#define ff first
#define ss second
#define MOD 1000000007
const int N = 1e5+7 ;
vector<pii> ans ;
vector<pair<int,int> >g[N] ;
bool vis[N] ;
void dfs(int x, int sm){
	vis[x] = true ;
	if(sm % 2 == 0){
		ans.pb({x,0}) ;
	}
	else{
		ans.pb({x,1}) ;
	}
	for(auto i : g[x]){
		if(vis[i.ff] != true){
			int v = i.ff ;
			int cost = i.ss ;
			dfs(v,sm+cost) ; 
		}
	}
}

int32_t main(){fast ;
	int n,k,x,y,w ;
	cin >> n ;
	for(int i = 0 ; i < n-1 ; i++){
		cin >> x >> y >> w ;
		--x , --y ;
		g[x].pb({y,w}) ;
		g[y].pb({x,w}) ;
	}
	dfs(0,0) ;
	sort(all(ans)) ;
	for(auto i : ans)
		cout << i.ss << ' ' ;
	cout << endl ;
}







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

int main(){
  vector<char> vec(4);
  for(int i=0; i<4; i++){
    cin >> vec.at(i);
  }
  int ans = 0;
  for(int i=0; i<4; i++){
    if(vec.at(i) == '+'){
      ans++;
    }
    else{
      ans--;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256