akhauriyash/Code-Regression huggingface dataset:
fn read_stdin() -> String {
    use std::io::Read;
    let mut input = String::new();
    std::io::stdin().read_to_string(&mut input).unwrap();
    input
}

fn scan<'a, I: Iterator<Item = &'a str>, T: std::str::FromStr>(tokens: &mut I) -> T {
    tokens.next().unwrap().parse().ok().unwrap()
}

fn main() {
    let input = read_stdin();
    let tokens = &mut input.split_whitespace();
    let n: usize = scan(tokens);
    let s: String = scan(tokens);
    if n % 2 == 1 {
        println!("No");
        return;
    }
    let s = s.into_bytes();
    let h = n / 2;
    for i in 0..h {
        if s[i] != s[h + i] {
            println!("No");
            return;
        }
    }
    println!("Yes");
}


Measured memory_bytes: 4352
A,B,C,K = list(map(int,input().split()))
"""
for n in range(1):
    n = list(map(int,input().split()))
    L.append(n)
"""

if K <= A:
    print(K)
elif A < K <= A + B:
    print(A)
elif A + B < K <= A + B + C:
    print(A - (K - A - B))

Measured memory_bytes: 9104
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
//#include<cstdio>
//#include<cmath>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
//int MOD=1000000007;

signed main(){
    int h,w;cin>>h>>w;
    vector<string> c(h);
    rep(i,h)cin>>c[i];
    //vector<string> res(2*h);
    rep(i,2*h){
        int buf=i/2;
        cout<<c[buf]<<endl;;
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

int main ()
{
	int n, x;
	while (true) {
		std::cin >> n >> x;
		if (n==0 && x==0) break;
		
		int count = 0;
		for (int a=1; a<=n; a++) {
			for (int b=a+1; b<=n; b++) {
				int c = x-a-b;
				if (b < c && c <= n) count++;
				
			}
		}
		
		std::cout << count << std::endl;
	}
	
	return 0;
}




Measured memory_bytes: 3084
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
int main(void){
    // Your code here!
    string A;
    cin >> A;
    if(A[3-1] == A[4-1] && A[5-1] == A[6-1]){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}


Measured memory_bytes: 256
#pragma GCC optimize ("O2")
#pragma GCC target ("avx2")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

const ll mod = 998244353;

ll dp[301][310][310];

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


	string S;
	int K;

	int kosuu = 0;
	int k = 0;
	int A[301] = {};

	cin >> S >> K;
	rep(i, S.size()) {
		if (S[i] == '0') k++;
		else {
			A[k]++;
			kosuu++;
		}
	}

	dp[k + 1][0][0] = 1;
	for (int i = k; i >= 0; i--) {
		auto ne = dp[i];;
		auto ma = dp[i + 1];

		rep(j, kosuu + 1) {
			ll tmp = 0;
			for (int k = kosuu; k >= 0; k--) {
				ma[j][k] %= mod;
				ne[j][k] += tmp;
				tmp += ma[j][k];
				rep(p, A[i] + 1) ne[j + p][k + p] += ma[j][k];
			}
		}
	}

	ll kotae = 0;
	rep(i, min(K, kosuu) + 1) {
		kotae += dp[0][i][0] % mod;
	}
	co(kotae % mod);



	Would you please return 0;
}


Measured memory_bytes: 59924
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <queue>
#include <stack>
#include <list>
#include <functional>
#include <numeric>
#include <iostream>

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

int N, a[123];

int main() {

	scanf("%d", &N);
	rep(i, N) scanf("%d", &a[i]);

	int C = 101;
	rep(i, N - 1) {
		if (a[i] == a[i + 1]) {
			a[i + 1] = C;
			C++;
		}
	}


	printf("%d\n", C - 101);

	return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;

namespace CSharpSample01
{
    
    

    class Program
    {

        static void Set_Case(HashSet<string> set, string s1, string s2)
        {
            string s1_re = string.Join("", s1.Reverse());
            string s2_re = string.Join("", s2.Reverse());

            set.Add(s1 + s2);
            set.Add(s1_re + s2);
            set.Add(s1 + s2_re);
            set.Add(s1_re + s2_re);

            set.Add(s2 + s1);
            set.Add(s2_re + s1);
            set.Add(s2 + s1_re);
            set.Add(s2_re + s1_re);
           
        }

        static int All_Case(string arrival)
        {
            int all_caes = 0;
            int lenght = arrival.Length;
            HashSet<string> set = new HashSet<string>();

            for(int i = 1; i < lenght; i++)
            {
                string s1 = arrival.Substring(0, i);
                string s2 = arrival.Substring(i, lenght - i);
                Set_Case(set, s1, s2);
            }

            all_caes = set.Count();

            return all_caes;
        }
        
        static void Main(string[] args)
        {
            int m = int.Parse(Console.ReadLine());
            
            for(int i = 0; i < m; i++)
            {
                string arrival = Console.ReadLine();

                Console.WriteLine(All_Case(arrival));
            }

        }
    }
}


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

int main(){
  int n,a[101],tmp,cnt=0;
  cin>>n;
  for(int i=0;i<n;i++) cin>>a[i];
  for(int i=0;i<n-1;i++)
    for(int j=n-1;j>i;j--){
      if(a[j]<a[j-1]){
	tmp=a[j];
	a[j]=a[j-1];
	a[j-1]=tmp;
	cnt++;
      }
    }

  for(int i=0;i<n-1;i++)cout<<a[i]<<" ";
  cout<<a[n-1]<<endl<<cnt<<endl;
  
  return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repI(i, d, n) for (int i = (d); i < (n); ++i)
#define reps1(i, n) for (int i = 1; i < (n); ++i)
using namespace std;
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; }

using ll = long long;
using P = pair<int, int>;
using Pl = pair<ll, ll>;
using M = map<int, int>;
ll const INF = 1ll<<61;
double pi = 3.141592653589793238;

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

  ll max_l = *max_element(l.begin(), l.end());
  ll sum_l = accumulate(l.begin(), l.end(), 0);
  if (max_l < sum_l - max_l) cout << "Yes" << endl;
  else cout << "No" << endl;

  return 0;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define whole(x) (x).begin(),(x).end()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
using P = pair<int, int>;
#define debug(var) cerr << "[" << #var << "] " << var << endl
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
const ll mod = 1000000007;
const int dx[] = {-1,0,1,0};
const int dy[] = {0,-1,0,1};


int main(){
    int q;
    cin >> q;
    rep(qi, q) {
        ll a, b;
        cin >> a >> b;
        if (a>b) swap(a, b);
        ll ans = a-1;
        ll l = 0;
        ll r = mod;
        if (a==b) {
            ans *= 2LL;
            cout << ans << endl;
            continue;
        }
        while (r-l>1) {
            ll x = (l+r)/2;
            if (x*x<a*b) l = x;
            else r = x;
        }
        ans += (l*2-a-1);
        if (l*(l+1)<a*b) ans++; 
        cout << ans << endl;
    }
    
    return 0;
}


Measured memory_bytes: 256
N, X=map(int, input().split())
W=[0]*51
W[0]=1
for i in range(1,51):
  W[i]=W[i-1]*2 + 3
  
P=[0]*51
P[0]=1
for i in range(1,51):
  P[i]=P[i-1]*2+1
#nバーガーのX番目までのP  
def burger(n,x):
  if n==0:
    return 1
  #n-1バーガーの長さ
  l=W[n-1]
  if x==1:
    return 0
  if x==W[n]:
    return P[n]
  if x==1+l+1:
    return P[n-1]+1
  if 1<x<=l+1:
    return burger(n-1,x-1)
  if 1+l+1<x<=1+l+1+l:
    return P[n-1]+1+burger(n-1,x-(l+2))
  
print(burger(N, X))



Measured memory_bytes: 3064
export class Main {
  static main(input): string {
    const tmp: string[] = input.split("\n");
    const n: number = Number(tmp[0].split(" "));
    let bList: number[] = tmp[1].split(" ").slice(0, n).map(Number);
    if (bList.some((v, i) => v > i + 1)) {
      return "-1";
    }
    return `${Main.make(bList).join("\n")}`;
  }

  static make(bList: number[]): number[] {
    if (bList.length == 1) {
      return bList;
    }
    const last: number = bList[bList.length - 1];
    const acc: number[] = Main.make(bList.slice(0, bList.length - 1));
    if (last == bList.length) {
      return acc.concat([last]);
    }
    return acc.slice(0, last - 1).concat([last], acc.slice(last - 1));
  }
}
console.log(Main.main(require("fs").readFileSync("/dev/stdin", "utf8")));

Measured memory_bytes: 7500
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for (int i = (n)-1; i >= 0; i--)
#define rep2(i,s,n) for (int i = (s); i < (n); ++i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vs vector<string>
#define vc vector<char>
#define vb vector<bool>
#define vp vector<P>
using namespace std;
using ll = long long;
using P = pair<int,int>;
using LP = pair<ll,ll>;
template<class T> istream& operator>>(istream& is,vector<T>& v) { for(T& t:v){is>>t;} return is; }
template<class T> ostream& operator<<(ostream& os,const vector<T>& v) { for(T t:v){os<<t<<" ";} os<<"\n"; return os; }
void Yes(bool b) { cout << (b ? "Yes" : "No") << endl; }
void YES(bool b) { cout << (b ? "YES" : "NO") << endl; }
template<class T> inline bool chmin(T& a,T b) {if(a > b){a = b; return true;} return false;}
template<class T> inline bool chmax(T& a,T b) {if(a < b){a = b; return true;} return false;}
const int inf = 1001001001;
const ll linf = 1001001001001001001;

class flow {
    struct edge {
        int to,cap,rev;
        edge(int to,int cap,int rev):to(to),cap(cap),rev(rev) {}
    };
    int n;
    vector<vector<edge>> G;
    vi level,iter;

    void bfs(int s) {
        level.assign(n,-1);
        queue<int> q;
        level[s] = 0;
        q.push(s);
        while(!q.empty()) {
            int v = q.front();
            q.pop();
            for(auto& e : G[v]) {
                if(e.cap > 0 && level[e.to] < 0) {
                    level[e.to] = level[v]+1;
                    q.push(e.to);
                }
            }
        }
    }
    int dfs(int v,int t,int f) {
        if(v == t) return f;
        rep2(i,iter[v],G[v].size()) {
            auto &e = G[v][i];
            if(e.cap > 0 && level[v] < level[e.to]) {
                int d = dfs(e.to,t,min(f,e.cap));
                if(d > 0) {
                    e.cap -= d;
                    G[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }

public:
    explicit flow(int n):n(n),G(n),level(n),iter(n) {}
    void add_edge(int from,int to,int cap) {
        G[from].eb(to,cap,G[to].size());
        G[to].eb(from,0,G[from].size()-1);
    }
    // O(|E||V|^2) dinic-algorithm
    int max_flow(int s,int t) {
        int fl = 0;
        while(true) {
            bfs(s);
            if(level[t] < 0) return fl;
            iter.assign(n,0);
            int f;
            while((f = dfs(s,t,inf)) > 0) fl += f;
        }
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int v,e;
    cin >> v >> e;
    flow f(v);
    rep(_,e) {
        int a,b,c;
        cin >> a >> b >> c;
        f.add_edge(a,b,c);
    }
    cout << f.max_flow(0,v-1) << endl;
}



Measured memory_bytes: 3204
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 1e6+7;
string s;
int n;
int S[2][N];
void nhap()
{
    cin >> n;
    cin >> s;
    for (int i = 1; i <= n; i++) {
        int x = 0;
        if (s[i - 1] == 'W') {
            x = 1;
        }
        S[0][i] = S[0][i - 1];
        S[1][i] = S[1][i - 1];
        S[x][i]++;
    }
    S[0][n + 1] = S[0][n];
    S[1][n + 1] = S[1][n];
}
void solve()
{
    int Res = n;
    for (int i = 1; i <= n; i++) {
        int X1 = S[1][i - 1];
        int X2 = S[0][n] - S[0][i];
        Res = min(Res,X1 + X2);
    }
    cout << Res;
}
int main()
{
    nhap();
    solve();
}


Measured memory_bytes: 5892
def base_10_to_n(X, n):
    if (int(X/n)):
        return base_10_to_n(int(X/n), n)+str(X%n)
    return str(X%n)

number_list = [int(i) for i in input().split()]
n_val = base_10_to_n(number_list[0], number_list[1])
len_val = len(n_val)
print(len_val)

Measured memory_bytes: 3060
#include <stdio.h>
#define INF 1 << 29

int min(int a,int b){
  if(a < b){
    return a;
  }
  return b;
}

int main(void){
  int N,M;
  scanf("%d%d",&N,&M);

  int a[M],b[M],c[M],dist[N][N];

  for(int i = 0;i < N;i++){
    for(int j = 0;j < N;j++){
      if(i == j)
        dist[i][j] = 0;
      else
        dist[i][j] = INF;
    }
  }

  for(int i = 0;i < M;i++){
    scanf("%d%d%d",&a[i],&b[i],&c[i]);
    a[i]--; b[i]--;
    dist[a[i]][b[i]] = dist[b[i]][a[i]] = c[i];
  }

  for(int k = 0;k < N;k++){
    for(int i = 0;i < N;i++){
      for(int j = 0;j < N;j++){
        dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);
      }
    }
  }

  int ans = 0;
  for(int i = 0;i < M;i++){
    if(dist[a[i]][b[i]] < c[i]) ans++;
  }

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

  return 0;
}

Measured memory_bytes: 256
/// 3 min...
///A: When AtCoder CrackersN is a multiple of K, the answer is 0 because it can be
///distributed evenly. Otherwise, the answer cannot be 0, and the quotient obtained
///by dividing N by K and so much A; B, A + 1 for B, K.

#include <iostream>
using namespace std;
using ll = long long;
int main()
{
    ll n, k;

    cin >> n >> k;
    if(n%k == 0)
        cout << "0" << endl;
    else
        cout << "1" << endl;

    return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace exawizards2019B
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.ReadLine();

            var input = Console.ReadLine();
            var red = input.Count(x => x == 'R');
            var blue = input.Count(x => x == 'B');

            if (red > blue) Console.WriteLine("Yes");
            else Console.WriteLine("No");
        }
    }
}


Measured memory_bytes: 11220
#include <bits/stdc++.h>
using namespace std;
const int MAX_LIM = 1e3;
const long long MOD = 1e9 + 7;
typedef long long ll;

int fact[MAX_LIM];

void factoring(int num){
	int x = 2;
	while(num >= x*x){
		if(num%x == 0) {
			fact[x]++;
			num /= x;
		}
		else x++;
	}
	fact[num]++;
}

int main(){
	ll n;
	cin >> n;
	ll ans = 1;
	
	if(n == 1) {
		cout << 1 << endl;
		return 0;
	}
	
	for(int i=2; i<=n; i++) factoring(i);
	
	for(int i=2; i<=n; i++){
		if(fact[i] == 0) continue;
		else ans = ans * (fact[i] + 1) % MOD;
	}
	cout << ans << endl;
  
  return 0;
}

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

#define REP(i, n) for(int i = 0;i < n;i++)
using namespace std;

int main(){
    int N;
    cin >> N;
    set<string> se;
    char tail = 'A';
    bool ans = true;

    string s;
    cin >> s;
    tail = s[s.size()-1];
    se.insert(s);
    REP(i,N-1){
        cin >> s;
        //if(tail == s[i].back())
        if(tail != s[0])
            ans = false;
        tail = s[s.size()-1];
        if(se.find(s) != se.end())
            ans = false;
        se.insert(s);
    }

    if(ans)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}


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

#define dforsn(i,s,n) for(int i=int(n-1);i>=int(s);i--)
#define forsn(i,s,n) for(int i=int(s);i<int(n);i++)
#define forn(i,n) for(int i=0;i<int(n);i++)
#define D(a) cerr << #a << " = " << a << endl
#define all(a) a.begin(),a.end()
#define si(a) int((a).size())
typedef pair<int,int> pii;
typedef long long int ll;
typedef vector<int> vi;
#define pb emplace_back
#define mp make_pair
#define snd second
#define fst first

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    
    int n; cin >> n;
    int a[n], res = 0;
    forn(i,n) cin >> a[i];
    forn(i,n) forsn(j,i+1,n) res += a[i]*a[j];
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#define N_MAX 100000  // 荷物の最大個数
#define K_MAX 100000  // トラックの最大数
#define W_MAX 10000   // 荷物の重さの最大値

// 最大積載量が P のトラック k 台で何個の荷物を載せれるかを返す
int check(long int P, int n, int k, int *T)
{
  int i, j;
  long int s;
  
  i = 0;
  for (j = 0; j < k; j++) {
    s = 0;
    while (s + T[i] <= P) {
      s += T[i];
      i++;
      if (i == n)
        return n;
    }
  }
  return i;
}

// n 個の荷物を載せられる最小の積載量 P を求める
long int solve(int n, int k, int *T)
{

  long int left, right, mid;
  left = 0;
  right = W_MAX* N_MAX;

  while (right - left > 1) {  // 解に収束するまで繰り返す(解は right に入る)
    mid = (left + right)/2;
    //printf("%ld %ld %ld ", left, mid, right);
    int v = check(mid, n, k, T);  // 積載量を mid とした時に載せられる荷物の数を求める
    if (v == n)  // n 個の荷物を載せられる間は，探索範囲の最大値を小さくする
      right = mid;  
    else
      left = mid;
    //printf(": %d\n", v);
  }
  return right;
}

int main(void)
{
  int n;   // 荷物の個数
  int k;   // トラックの台数
  int T[N_MAX]; // 各荷物の重さ
  long int ans;

  // 入力
  scanf("%d %d", &n, &k);
  for (int i = 0; i < n; i++)
    scanf("%d", &T[i]);
  
  ans = solve(n, k, T);

  printf("%ld\n", ans);  // 答えを出力

  return 0;
}


Measured memory_bytes: 2128
import sys,collections,random,math;sys.setrecursionlimit(10**7)
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def Ss(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

n = I()
d = collections.defaultdict(int)
for i in range(n):
    d[I()] = i
d[0] = n
t,maxinc = 0,0
for i in range(1,n+1):
    if d[i-1] < d[i]:
        t += 1
        maxinc = max(maxinc,t)
    else:
        t = 0
print(n-1-maxinc)

Measured memory_bytes: 35132
def resolve():
    A,B,C,D = map(int,input().split())

    while A > 0 and C > 0:
        C-=B
        if C <= 0:
            break
        A-=D
    

    if A <= 0 :
        print("No")
    else:
        print("Yes")





if __name__ == "__main__":
    resolve()

Measured memory_bytes: 9176
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define s(x, n) memset(x, n, sizeof(x));
#define pb(x) push_back(x)

int main()
{
#ifdef WIN32
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

#ifndef WIN32
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#endif
    ll d, t, s;
    cin >> d >> t >> s;
    if (s * t >= d)
        cout << "Yes" << '\n';
    else
    {
        cout << "No\n";
    }

    return 0;
}

Measured memory_bytes: 3648
import java.util.*;
public class Main {
    static long INF = 100000000000000L;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        List<Edge> edges = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            int from = sc.nextInt();
            int to = sc.nextInt();
            long cost = -sc.nextLong();
            edges.add(new Edge(from, to, cost));
        }
        long[] d = new long[100000];
        d = bellmanFord(d, edges, 1, n, m);
        if (negativeLoop(d, edges, 1, n, m)) {
            System.out.println("inf");
            return;
        }
        // System.out.println(Arrays.toString(d));
        System.out.println(-d[n]);
    }

    public static long[] bellmanFord(long[] d, List<Edge> es, int s, int vl, int el) {
        for (int i = 0; i <= vl; i++) {
            d[i] = INF;
        }
        d[s] = 0;
        for (int j = 0; j < vl; j++) {
            for (int i = 0; i < el; i++) {
                Edge e = es.get(i);
                // System.out.println(e);
                // System.out.printf("d[%d] = %d d[%d] = %d e.cost = %d%n", e.to, d[e.to], e.from,
                //     d[e.from], e.cost);
                if (d[e.from] != INF && d[e.to] > d[e.from] + e.cost) {
                    d[e.to] = d[e.from] + e.cost;
                    //   System.out.printf("d[%d] = %d %n", e.to, d[e.to]);
                }
            }
        }
        return d;
    }

    public static boolean negativeLoop(long[] d, List<Edge> es, int s, int vl, int el) {
        boolean[] negative = new boolean[vl + 1];
        for (int i = 0; i < vl; i++) {
            for (int j = 0; j < el; j++) {
                Edge e = es.get(j);
                // System.out.println(e);
                // System.out.printf("d[%d] = %d d[%d] = %d e.cost = %d%n", e.to, d[e.to], e.from,
                //    d[e.from], e.cost);
                if (d[e.from] == INF) {
                    continue;
                }
                if (d[e.to] > d[e.from] + e.cost) {
                    d[e.to] = d[e.from] + e.cost;
                    // if (i == vl - 1) {
                    //    return true;
                    //}
                    negative[e.to] = true;
                }
                // System.out.printf("negative[%d] = %s %n", e.to, negative[e.to]);
                if (negative[e.from]) {
                    negative[e.to] = true;
                }
            }
        }
        // for (int i = 0; i <= vl; i++) {
        //    System.out.println(d[i]);
        //}
        return negative[vl];
    }
}
class Edge {
    int from;
    int to;
    long cost;
    public Edge(int from, int to, long cost) {
        this.from = from;
        this.to = to;
        this.cost = cost;
    }
    public String toString() {
        return String.format("from = %d to = %d cost = %d", this.from, this.to, this.cost);
    }
}


Measured memory_bytes: 30748
#include<iostream>

using namespace std;

int main() {

	int W, H, x, y, r, xr, yr;

	cin >> W >> H >> x >> y >> r;

	xr = x + r;
	yr = y + r;

	if (xr > W || yr > H)
		cout << "No" << endl;

	else if (xr < 0 || yr < 0)
		cout << "No" << endl;

	else if (x < 0 || r < 0)
		cout << "No" << endl;

	else if (xr <= W&&yr <= H)
		cout << "Yes" << endl;

	else
		cout << "No" << endl;


}

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

using namespace std;

int main() {
    cout << fixed << setprecision(0);
    string S, T;
    cin >> S >> T;

    int ans = T.size();

    for(int i = 0; i < S.size() - T.size() + 1; i++) {
        int cnt = 0;
        for(int j = 0; j < T.size(); j++) {
            if(S[i + j] != T[j])
                cnt++;
        }
        ans = min(ans, cnt);
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3588
MOD = 1000000007
MAX = 100005
P = [0 for i in range(MAX)]
P[0] = 1
for i in range(MAX-1):
    P[i+1] = P[i] * (i + 1)
    P[i+1] %= MOD

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

if N == M:
    res = 2 * P[N] * P[N]
elif abs(N - M) == 1:
    res = P[N] * P[M]
else:
    res = 0
print(res % MOD)


Measured memory_bytes: 7064
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define rep(i,n) for(int i=0, i##_len=(int)(n); i<i##_len; i++)
#define reps(i,n) for(int i=1 , i##_len=(int)(n);i<=i##_len;i++)
#define rrep(i,n) for(int i=((int)(n)-1);i>=0;i--)
#define rreps(i,n) for(int i=((int)(n));i>0;i--)
#define repi(i,x) for(auto i=(x).begin(),i##_fin=(x).end();i!=i##_fin;i++)
#define all(x) (x).begin(), (x).end()
#define input(array) repi(array##_itr, array) { cin >> *(array##_itr); }
#define F first
#define S second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
string solve(bool a) { return ((a) ? "YES" : "NO"); }
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef pair<int , int> Pi;
typedef vector<Pi> VPi;
typedef vector<long long> V;
typedef vector<V> VV;
typedef pair<long long , long long> P;
typedef vector<P> VP;
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;}
const long long INFLL = 1LL<<60;
const int INF = 1<<30;
const double PI=acos(-1);
int main(){
	string s;
	bool ans=true;
	cin >>s;
	map<char, int> dis;
	rep(i, s.size()) { dis[s[i]]++; }
	repi(itr, dis) { clog << itr->S << endl; }
	if (dis.size() != 3) {
		repi(itr, dis) { ans &= (itr->S == 1); }
	} else {
		repi(itr1, dis) {
			repi(itr2, dis) {
				if (itr1->F == itr2->F) {
					continue;
				}
				ans &= (abs(itr1->S - itr2->S) <= 1);
			}
		}
	}

	cout<<solve(ans)<<endl;
}
/*
1 2 3
1 3 3
bcabcbc

11
ab

1
*/

Measured memory_bytes: 3744
#include <functional>
#include <unordered_map>
#include <queue>
#include <iostream>
using namespace std;

int main() {
    int t; cin >> t;
    while (t--) {
        long long N, A, B, C, D; cin >> N >> A >> B >> C >> D;
        priority_queue<pair<long long, long long> > pq;
        pq.push({0LL, N});
        unordered_map<long long, long long> dist;
        dist[N] = 0;
        function<void(long long, long long)> add = [&](long long x, long long c) {
            if (dist.find(x) == dist.end() || dist[x] > c) {
                dist[x] = c;
                pq.push({-c, x});
            }
        };
        int count = 0;
        while (!pq.empty()) {
            count++;
            long long c = -pq.top().first, n = pq.top().second;
            pq.pop();
            if (dist.find(n) != dist.end() && dist[n] < c) continue;
            if (n == 1) {
                cerr << count << endl;
                cout << c + D << endl;
                break;
            }
            for (int d : {2, 3, 5}) {
                long long cost = d == 2 ? A : d == 3 ? B : C;
                long long r = n / d;
                if (n - r > 1e9) {
                    add(r, c + D * (n % d) + cost);
                    add(r+1, c + D * (d - n % d) + cost);
                } else {
                    add(r, c + min(D * (n - r), D * (n % d) + cost));
                    add(r+1, c + min(D * (n - r - 1), D * (d - n % d) + cost));
                }
            }
        }
    }
}


Measured memory_bytes: 4252
using System;
using System.Collections.Generic;
using System.Linq;
using System.Collections;

public class Coder
{

    public static int[] ReadArray()
    {
        return Array.ConvertAll(Console.ReadLine().Split(' '), m => Convert.ToInt32(m));
    }

    public static int ReadInt()
    {
        return Convert.ToInt32(Console.ReadLine());
    }

    public static string ReadStr()
    {
        return Console.ReadLine();
    }

    public static long ReadLong()
    {
        return Convert.ToInt64(Console.ReadLine());
    }

    public static long[] ReadLongArray()
    {
        return Array.ConvertAll(Console.ReadLine().Split(' '), m => Convert.ToInt64(m));

    }

    public static void Main()
    {

        long n = ReadLong();

        var ans = new HashSet<long>() { n, n- 1 > 1 ? n - 1 : n };

        for (long i = 2; i * i <= n; i++)
        {
            if ((n - 1) % i == 0)
            {
                ans.Add(i);
                ans.Add((n - 1) / i);
            }
        }


        for (long i = 2; i * i <= n; i++)
        {
            var a = n;

            while (a % i == 0)
            {
                a /= i;
            }

            if (a % i == 1)
                ans.Add(i);

        }

        Console.WriteLine(ans.Count);

    }
}

Measured memory_bytes: 13396
#include<iostream>
#include<vector>
#include<cmath>
#include<string>
#include<algorithm>
#include<map>
#include<utility>
#include<cstdio>
#include<bits/stdc++.h>

using namespace std;
using ll = long long;
const long long INF = 1LL<<60;

typedef pair<ll,ll> Pair;
int main(){

ll N;

cin >> N;

vector<Pair> fs;

for(ll i = 2;i*i <= N;++i ){

    ll cnt = 0;

    while(N%i==0){
        N/=i;
        ++cnt;
    }
        fs.emplace_back(i,cnt);
}

if(N!=1) fs.emplace_back(N,1);

ll ans = 0;

for(Pair p : fs){

    ll cnt = p.second;
    ll x = 1;
    while(x <= cnt){
        cnt -= x;
        ++ans;
        ++x;
    }
}

cout << ans << endl;

return 0;

}


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

int main(){
    int N, X;
    cin >> N >> X;
    vector<int> m(N);
    int sum = 0;
    rep(i,N){
        cin >> m.at(i);
        sum += m.at(i);
    }
    int flag = 1001;
    int count = 0;
    bool judge = false;
    while(true){
        rep(i,N){
            if(flag > m.at(i)){
                flag = m.at(i);
            }
        }
        if(X - sum - flag < 0){
            judge = true;
            break;
        }else{
            X = X - flag;
            count++;
        }
        if(judge) break;
    }
    cout << N + count << endl;
    
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef pair<ll,ll> pll;
const ll mod=1e9+7;
//const ll mod=998244353;
const ll inf=1LL<<61;

typedef pair<ll,pll> ppll;

vec idx={1,0,-1,0};
vec idy={0,1,0,-1};

int main() {
  ll h,w,k;
  cin >> h >> w >> k;
  vector<string> maze(h);
  for(ll i=0;i<h;i++) cin >> maze[i];
  mat d(h,vec(w,-1));
  ll sy,sx;
  for(ll i=0;i<h;i++) {
    for(ll j=0;j<w;j++) {
      if(maze[i][j]=='S') {
        sx=j;
        sy=i;
      }
    }
  }
  queue<ppll> q;
  d[sy][sx]=0;
  q.push({k,{sy,sx}});
  while(q.size()) {
    ll cnt=q.front().first;
    ll y=q.front().second.first;
    ll x=q.front().second.second;
    q.pop();
    for(ll i=0;i<4;i++) {
      ll nx=x+idx[i];
      ll ny=y+idy[i];
      if(nx<0||ny<0||nx>=w||ny>=h) continue;
      if(d[ny][nx]>-1) continue;
      if(maze[ny][nx]!='.') continue;
      d[ny][nx]=0;
      if(cnt==1) continue;
      q.push({cnt-1,{ny,nx}});
    }
  }
  for(ll i=0;i<h;i++) {
    for(ll j=0;j<w;j++) {
      if(d[i][j]==0) {
        q.push({0,{i,j}});
      }
    }
  }
  while(q.size()) {
    ll y=q.front().second.first;
    ll x=q.front().second.second;
    ll td=d[y][x];
    q.pop();
    for(ll i=0;i<4;i++) {
      ll nx=x+idx[i];
      ll ny=y+idy[i];
      if(nx<0||ny<0||nx>=w||ny>=h) continue;
      if(d[ny][nx]>-1) continue;
      d[ny][nx]=td+1;
      q.push({0,{ny,nx}});
    }
  }
  ll ans=inf;
  for(ll i=0;i<h;i++) {
    ans=min({ans,d[i][0],d[i][w-1]});
  }
  for(ll i=0;i<w;i++) {
    ans=min({ans,d[0][i],d[h-1][i]});
  }
  ans=(ans+k-1)/k;
  cout << ans+1 << endl;
}

Measured memory_bytes: 24332
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
int main(){
  int x;
  cin>>x;
  int temp=1;
  int cnt=0;
  int ans=1;
  for(int i=2;i<=40;i++){
    while(1){
      temp *=i;
      cnt++;
      if(temp>x){
        break;
      }
    }
    temp /=i;
    cnt--;
    
    if(cnt<2){
      continue;
    }
    
    ans = max(ans,temp);
    temp=1;
    cnt=0;
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <numeric>

using namespace std;
using ll = long long;
using ull = unsigned long long;

#define REP(i,n) for(long long i = 0; i < (n); i++)
#define FOR(i, m, n) for(long long i = (m);i < (n); ++i)
#define ALL(obj) (obj).begin(),(obj).end()
#define SPEED cin.tie(0);ios::sync_with_stdio(false);

template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;

const ll MOD = (ll)1e9 + 7;
const ll MOD2 = 998244353;
const ll HIGHINF = (ll)1e18;
const ll LOWINF = (ll)1e15;
const long double PI = 3.1415926535897932384626433;

template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; exit(0);}}
template <class T, class U>ostream &operator<<(ostream &o, const map<T, U>&obj) {o << "{"; for (auto &x : obj) o << " {" << x.first << " : " << x.second << "}" << ","; o << " }"; return o;}
template <class T>ostream &operator<<(ostream &o, const set<T>&obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}
template <class T>ostream &operator<<(ostream &o, const multiset<T>&obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}
template <class T>ostream &operator<<(ostream &o, const vector<T>&obj) {o << "{"; for (int i = 0; i < (int)obj.size(); ++i)o << (i > 0 ? ", " : "") << obj[i]; o << "}"; return o;}
template <class T, class U>ostream &operator<<(ostream &o, const pair<T, U>&obj) {o << "{" << obj.first << ", " << obj.second << "}"; return o;}
template <template <class tmp>  class T, class U> ostream &operator<<(ostream &o, const T<U> &obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr)o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}
void print(void) {cout << endl;}
template <class Head> void print(Head&& head) {cout << head;print();}
template <class Head, class... Tail> void print(Head&& head, Tail&&... tail) {cout << head << " ";print(forward<Tail>(tail)...);}
template <class T> void chmax(T& a, const T b){a=max<T>(a,b);}
template <class T> void chmin(T& a, const T b){a=min<T>(a,b);}
void YN(bool flg) {cout << ((flg) ? "YES" : "NO") << endl;}
void Yn(bool flg) {cout << ((flg) ? "Yes" : "No") << endl;}
void yn(bool flg) {cout << ((flg) ? "yes" : "no") << endl;}

int main() {
    int P,Q,R; cin >> P >> Q >> R;
    cout << min({P+Q,Q+R,R+P}) << endl;

    return 0;
}


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

using namespace std;
using ll = long long;
using VI = vector<int>;
using VL = vector<ll>;
#define FOR(i, a, n) for(int (i)=(a);(i)<(n);(i)++)
#define eFOR(i, a, n) for(int (i)=(a);(i)<=(n);(i)++)
#define rFOR(i, a, n) for(int (i)=(n)-1;(i)>=(a);(i)--)
#define erFOR(i, a, n) for(int (i)=(n);(i)>=(a);(i)--)
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i, a) sort((i).begin(),(i).end(),(a))
#define all(i) (i).begin(),(i).end()
constexpr ll INF = 1000000000;
//constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;

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

inline void init() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
}

template<class T>
inline istream &operator>>(istream &input, vector<T> &v) {
    for (auto &elemnt : v)input >> elemnt;
    return input;
}

int main() {
    init();
    int x;
    string day_list[7] = {"fri", "sat", "sun", "mon", "tue", "wed", "thu"};
    cin >> x;
    if(x%7==0) {
        cout << day_list[6] << endl;
        return 0;
    }else{
        cout << day_list[x % 7 - 1] << endl;
    }
    return 0;
}



Measured memory_bytes: 3164
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

using namespace std;

// repetition
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

// container util
#define all(x) (x).begin(), (x).end()

// debug
#define dump(x) cerr << #x << " = " << (x) << endl;
#define debug(x)                                         \
  cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" \
       << " " << __FILE__ << endl;

// typedef
typedef long long lint;
typedef unsigned long long ull;
typedef complex<long double> Complex;
typedef pair<int, int> P;
typedef tuple<int, int, int> TP;
typedef vector<int> vec;
typedef vector<vec> mat;

// constant
const int MOD = (int)1e9 + 7;
const int INF = (int)1e18;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1};

// 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();
}

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

double a, b, x;
const double pi = 3.141592653589793;

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

  cin >> a >> b >> x;
  double S = x / a;
  double ans;
  if (S < a * b / 2) {
    ans = b * b / (2 * S);
    printf("%.12f\n", atan(ans) * 180 / pi);
  } else {
    ans = 2 * (a * b - S) / (a * a);
    printf("%.12f\n", atan(ans) * 180 / pi);
  }

  return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long ll;
int main() {
    int n;
    cin >> n;
    vector<int> h(n);
    for (int i = 0; i < n; ++i) {
        cin >> h[i];
    }
    for (int i = n-1; i > 0; --i) {
        if(h[i-1] == h[i]+1){
            h[i-1] -= 1;
        }else if(h[i-1] > h[i]){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 768
#include <iostream>
#include <vector>
#include <string>
#include <iterator>
#include <algorithm>

using namespace std;

int main(){
    int N, Q;
    string S;
    string tmp;
    string ac = "AC";
    

    cin >> N; cin >> Q;
    cin >> S;
    
    vector<int> ans(N+1, 0);

    for(int i = 1; i < N; i++){
        if(S[i - 1] == 'A' && S[i] == 'C'){
            ans.at(i+1) = ans.at(i) + 1;
        }
        else{
            ans.at(i+1) = ans.at(i);
        }
    }

    int l;
    int r;

    for(int i = 0; i < Q; i++){
        cin >> l;
        cin >> r;
        cout << (ans.at(r) - ans.at(l)) << endl;
    }
}

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

using ll = long long;
using ld = long double;
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define FORR(i, m, n) for (int i = (m); i >= (n); i--)
#define REP(i, n) FOR(i, 0, (n))
#define REPR(i, n) FORR(i, (n) - 1, 0)
#define REP1(i, n) FOR(i, 1, (n) + 1)
#define REPS(c, s) for (char c : s)
#define ALL(c) (c).begin(), (c).end()
#define sz(v) (int)v.size()
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
const int MOD = 1000000007;
const int INF = 1000000001;
const ll LINF = 1000000001000000001LL;
const char EOL = '\n';

void solve();

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(numeric_limits<double>::max_digits10);
    solve();
    return 0;
}

void solve() {
    string s;
    cin >> s;
    string t = s;
    reverse(ALL(t));
    replace(ALL(t), 'b', 'B');
    replace(ALL(t), 'd', 'b');
    replace(ALL(t), 'B', 'd');
    replace(ALL(t), 'p', 'P');
    replace(ALL(t), 'q', 'p');
    replace(ALL(t), 'P', 'q');
    cout << (s == t ? "Yes" : "No") << EOL;
}


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

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

    vector<bool> era(100000, true);
    era[0] = era[1] = false;

    for (int i = 2; i < 100000; ++i)
        if (era[i])
            for (int j = i + i; j < 100000; j += i)
                era[j] = false;

    for (int i = x; i < 100000; ++i)
        if (era[i])
        {
            cout << i << endl;
            return 0;
        }
    cout << 100003 << endl;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=200005,INF=1<<30;
vector<int> prime;//i番目の素数
bool is_prime[MAX+1];

void sieve(int n){
    int p=0;
    for(int i=0;i<=n;i++){
        is_prime[i]=true;
    }
    
    is_prime[0]=is_prime[1]=false;
    
    for(int i=2;i<=n;i++){
        if(is_prime[i]){
            prime.push_back(i);
            for(int j=2*i;j<=n;j+=i){
                is_prime[j] = false;
            }
        }
    }
}

vector<pair<int,int>> G[MAX];
int dis[MAX][2];

void dijkstra(int u){
    dis[u][0]=0;
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> PQ;
    
    PQ.push(make_pair(0,u));
    while(!PQ.empty()){
        int a=PQ.top().first;
        int b=PQ.top().second;
        PQ.pop();
        if(dis[b][a%2]<a) continue;
        for(int i=0;i<G[b].size();i++){
            int c=G[b][i].first;
            int d=G[b][i].second;
            if(dis[c][(dis[b][a%2]+d)%2]>dis[b][a%2]+d){
                dis[c][(dis[b][a%2]+d)%2]=dis[b][a%2]+d;
                PQ.push(make_pair(dis[c][(dis[b][a%2]+d)%2],c));
            }
        }
    }
    return;
}//a,dが長さ

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    sieve(MAX-2);
    
    int N,M;cin>>N>>M;
    int s,t;cin>>s>>t;s--;t--;
    
    for(int i=0;i<M;i++){
        int a,b;cin>>a>>b;
        a--;b--;
        G[a].push_back({b,1});
        G[b].push_back({a,1});
    }
    
    for(int i=0;i<N;i++){
        dis[i][0]=dis[i][1]=INF;
    }
    
    dijkstra(s);
    
    if(dis[t][0]==2) cout<<2<<endl;
    else if(dis[t][1]!=INF){
        for(int a=dis[t][1];;a+=2){
            if(is_prime[a]){
                cout<<a<<endl;
                return 0;
            }
        }
    }else cout<<-1<<endl;
    
}




Measured memory_bytes: 12540
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <list>
#include <set>
#include <stack>
#include <deque>
#include <queue>
#include <cmath>
#include <algorithm>
#include <utility>
#include <functional>
#include <fstream>
#define debug(x) cout << #x << " = " << x << endl
#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,n) for(int i = 0; i < (n); i++)
#define repr(i,n) for(int i = (n); i > -1; i--)
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const int MOD = 1000000007;
const ll LINF = 1e18;
const double EPS = 1e-9;


int n,m;
map<int, set<int>> from,to;
int result[100100];
int next[2] = {-1,-1};

void solve(int k) {
  set<int> s = from[k];
  if(s.size() == 0) return;
  for(set<int>::iterator it = s.begin(), end = s.end(); it != end; ++it) {
    to[*it].erase(k);
  }
  for(set<int>::iterator it = s.begin(), end = s.end(); it != end; ++it) {
    if(result[*it] == -1 && to[*it].size() == 0) {
      result[*it] = k;
      solve(*it);
    }
  }
}


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

  cin>>n>>m;
  rep(i, n-1+m) {
    int x,y;
    cin>>x>>y;
    from[x].insert(y);
    to[y].insert(x);
  }
  int root = 0;
  rep(i, 100100) {
    result[i] = -1;
  }
  FOR(i,1,n+1) {
    if(to[i].size() == 0) {
      root = i;
      result[i] = 0;
      break;
    }
  }
  solve(root);
  // while(next[0] != -1 || next[1] != -1) {
  //   int nnext[2] = {-1,-1}, p = 0;
  //   rep(i,2) {
  //     debug(next[i]);
  //     if(next[i] == -1) continue;
  //     set<int> s = from[next[i]];
  //     for(set<int>::iterator it = s.begin(), end = s.end(); it != end; ++it) {
  //       debug(*it);
  //       to[*it].erase(next[i]);
  //       if(to[*it].size() == 0) {
  //         result[*it] = next[i];
  //         debug(next[i]);
  //         nnext[p++] = *it;
  //       }
  //     }
  //   }
  //   next[0] = nnext[0]; next[1] = nnext[1];
  //   debug(next[0]);debug(next[1]);
  // }
  FOR(i,1, n + 1) {
    cout << result[i] << endl;
  }

  return 0;
}


Measured memory_bytes: 48128
#include<cstdio>
#include<algorithm>
#include<vector>
#include<map>

using namespace std;

int main() {
    int n, ans = 1e9, i;
    vector <pair<int, int> > v, w;
    map <int, int> mp1, mp2;
    map <int, int>::iterator it;

    scanf("%d", &n);

    for (i = 0; i < n; i++) {
        int x;

        scanf("%d", &x);

        if (i % 2 == 0) {
            mp1[x]++;
        } else {
            mp2[x]++;
        }
    }

    mp1[1e9] = 0;
    mp2[1e9] = 0;

    for (it = mp1.begin(); it != mp1.end(); it++) v.push_back(make_pair(it->second, it->first));
    sort(v.begin(), v.end());
    reverse(v.begin(), v.end());

    for (it = mp2.begin(); it != mp2.end(); it++) w.push_back(make_pair(it->second, it->first));
    sort(w.begin(), w.end());
    reverse(w.begin(), w.end());

    for (i = 0; i < v.size(); i++) {
        int p = 0;

        if (v[i].second == w[0].second) p = 1;

        ans = min(ans, n - (v[i].first + w[p].first));
    }

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

    return 0;
}

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

int main(){
  int N;
  cin >> N;
  vector<int> a(N);
  vector<int> b(N);
  vector<int> c(N);
  vector<int> d(N);
  vector<pair<int,int>> red(N);
  vector<pair<int,int>> blue(N);
  for(int i = 0; i < N; i++){
    cin >> a[i] >> b[i];
    red[i] = make_pair(a[i],b[i]);
  }

  for(int i = 0; i < N; i++){
    cin >> c[i] >> d[i];
    blue[i] = make_pair(c[i],d[i]);
  }

  int num = 0;
  int ans = 0;
  sort(red.begin(),red.end());
  sort(blue.begin(),blue.end());
  int aka[N],ao[N];

  for(int i = 0; i < N; i++){
    aka[i] = 0;
    ao[i] = 0;
  }
  int flag = 0;
  for(int i = 0; i < N; i++){
    flag = 0;
    int max = -1;
    int mita = 0;
    for(int j = 0; j < N; j++){
      if(red[j].first < blue[i].first && red[j].second < blue[i].second && aka[j] == 0 && ao[i] == 0 ){

      if(red[j].second > max){ max = red[j].second; flag = j; mita = 1; }
    }
    }
    if(mita == 1){
    aka[flag] = 1;
    ao[i] = 1;
    ans++;
    }
    }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define pi M_PI
#define EPS 1e-6
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

double dot(double ax, double ay, double az, double bx, double by, double bz){
    return ax * bx + ay * by + az * bz;
}

double norm(double x, double y, double z){
    return sqrt(x*x + y*y + z*z);
}

int main() {
    int n, q;
    cin >> n >> q;
    vector<double> x(n), y(n), z(n), r(n);
    VL l(n);
    REP(i,n) cin >> x[i] >> y[i] >> z[i] >> r[i] >> l[i];
    while (q--){
        double sx, sy, sz, dx, dy, dz;
        cin >> sx >> sy >> sz >> dx >> dy >> dz;
        ll ans = 0;
        REP(i,n) {
            if (dot(dx-sx,dy-sy,dz-sz,x[i]-sx,y[i]-sy,z[i]-sz) < 0) continue;
            if (dot(dx-sx,dy-sy,dz-sz,x[i]-dx,y[i]-dy,z[i]-dz) > 0) continue;
            double cx, cy, cz;
            cx = (y[i]-sy)*(dz-sz) - (z[i]-sz)*(dy-sy);
            cy = (z[i]-sz)*(dx-sx) - (x[i]-sx)*(dz-sz);
            cz = (x[i]-sx)*(dy-sy) - (y[i]-sy)*(dx-sx);
            double d = norm(cx,cy,cz) / norm(dx-sx,dy-sy,dz-sz);
            if (d < r[i] + EPS) ans += l[i];
        }
        cout << ans << endl;
    }

    return 0;
}

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

int main(){
	int n;
	cin >> n;
	rep(i,n){
		char s;
		cin >> s;
		if(s == 'Y'){
			cout << "Four" << endl;
			return 0;
		}
	}
	cout << "Three" << endl;
}

Measured memory_bytes: 256