akhauriyash/Code-Regression huggingface dataset:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		String x = "";
		try {
			x = in.readLine();
			char[] word = x.toCharArray();
			int lines = Integer.parseInt(in.readLine());
			
			String str;
			for (int j = 0; j < lines; j++) {
				x = in.readLine();
				String[] ins = x.split(" ");
				int a = Integer.parseInt(ins[1]);
				int b = Integer.parseInt(ins[2]);
				
				if (ins[0].equals("print")) {
					for (int i = a; i < (b + 1); i++) {
						System.out.print(word[i]);
					}
					System.out.println();
				} else if (ins[0].equals("reverse")) {
					str = String.valueOf(word).substring(a, (b + 1));
					for (int i = 0; i < str.length(); i++) {
						word[b - i] = str.charAt(i);
					}
				} else {
					str = ins[3];
					for (int i = 0; i < str.length(); i++) {
						word[a + i] = str.charAt(i);
					}
				}
			}
		} catch (NumberFormatException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
}

Measured memory_bytes: 29804
#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
using namespace std;
#define pb push_back
#define mp make_pair
#define INF 1e9
#define mod 1000000007
#define eps 1e-6
#define abs(x) ((x)>=0?(x):-(x))
#define y1 solai
#define fi first
#define se second
typedef long long ll;
void read(ll &x)
{
	scanf("%lld",&x);
}
void read(ll &x, ll &y)
{
	scanf("%lld%lld",&x,&y);
}
void read(ll &x, ll &y, ll &z)
{
	scanf("%lld%lld%lld",&x,&y,&z);
}
void print(ll x)
{
	printf("%lld ",x);
}
void println(ll x)
{
	printf("%lld\n",x);
}
const ll N=300000;
ll n,a[N+10],b[N+10],xo[N+10],su[N+10],cnt[N+10],sz,ans;
int main()
{
	//freopen("c.cpp","r",stdin);
 
	cin>>n;
	for(ll i=1;i<=n;i++)
	{
		read(a[i]);
		if(a[i]==0)
			cnt[sz]++;
		else
			b[++sz]=a[i];
	}
	for(ll i=0;i<=sz;i++)
		ans+=cnt[i]*(cnt[i]+1)/2;
	for(ll i=1;i<=sz;i++)
	{
		su[i]=su[i-1]+b[i];
		xo[i]=(xo[i-1]^b[i]);
		for(ll j=i;j>=max(1LL,i-25);j--)
			if((xo[i]^xo[j-1])==su[i]-su[j-1])
				ans+=(cnt[j-1]+1)*(cnt[i]+1);
			else
				break;
	}
	cout<<ans;
}

Measured memory_bytes: 10112
#include <bits/stdc++.h>
 
typedef long long ll;

using namespace std;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)

#define INF 1000000000000 //10^12:極めて大きい値,∞

const unsigned int BIT_FLAG_0 = (1 << 0); // 0000 0000 0000 0001
const unsigned int BIT_FLAG_1 = (1 << 1); // 0000 0000 0000 0010
const unsigned int BIT_FLAG_2 = (1 << 2); // 0000 0000 0000 0100
const unsigned int BIT_FLAG_3 = (1 << 3); // 0000 0000 0000 1000
const unsigned int BIT_FLAG_4 = (1 << 4); // 0000 0000 0001 0000
const unsigned int BIT_FLAG_5 = (1 << 5); // 0000 0000 0010 0000
const unsigned int BIT_FLAG_6 = (1 << 6); // 0000 0000 0100 0000
const unsigned int BIT_FLAG_7 = (1 << 7); // 0000 0000 1000 0000
const unsigned int BIT_FLAG_8 = (1 << 8); // 0000 0001 0000 0000
const unsigned int BIT_FLAG_9 = (1 << 9); // 0000 0010 0000 0000
const unsigned int BIT_FLAG_10 = (1 << 10); // 0000 0100 0000 0000
const unsigned int BIT_FLAG_11 = (1 << 11); // 0000 1000 0000 0000

void Main() {

    ll ans=INF;
    int N, M, X;
    int total, value, o;
    cin >> N >> M >> X;

    vector<int> C;
    vector<vector<int>> A(N);
    int p, q;


    REP(i, N) {
        cin >> p;
        C.push_back(p);
        REP(j, M) {
            cin >> q;
            A[i].push_back(q);
        }
    }

    REP(i, (1 << N)) { // 全通り
        REP(j, M) { // 全教科
            total = 0;
            REP(k, N) { // iのパターンにどれが入っているか
                if (i & (1 << k)) { // iのパターンに入っているとき
                    total = total + A[k][j];
                }
            }
            if (total < X) {
                total = -1;
                break;
            }
        }
        if (total != -1) {
            value = 0;
            REP(k, N) { // iのパターンにどれが入っているか
                if (i & (1 << k)) { // iのパターンに入っているとき
                    value = value + C[k];
                }
            }
            if (ans > value) {
                ans = value;
            }
        }
    }

    if (ans == INF) {
        cout << "-1" << endl;
        return;
    }
    cout << ans << endl;
}
 
int main()
{
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
}



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

int main() {
    int a, b;
    char op;

    while(1) {
        cin >> a >> op >> b;

        switch (op) {
        case '+':
            cout << (a + b) << endl;
            break;
        case '-':
            cout << (a - b) << endl;
            break;
        case '*':
            cout << (a * b) << endl;
            break;
        case '/':
            cout << (a / b) << endl;
            break;
        case '?':
            return 0;
            break;
        }
    }
}




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

int main() {
  int N, M, Q;
  cin >> N >> M >> Q;

  vector<vector<int>> S(N+2, vector<int>(M+2));
  auto V = S, H = S;
  for(auto i=1; i<=N; ++i) {
    string s;
    cin >> s;
    for(auto j=1; j<=M; ++j) {
      S[i][j] = s[j-1]=='1';
      V[i-1][j] = S[i-1][j]+S[i][j]==2;
      H[i][j-1] = S[i][j-1]+S[i][j]==2;
    }
  }

  for(auto* p: {&S, &V, &H}) for(auto i=1; i<=N; ++i) for(auto j=1; j<=M; ++j) (*p)[i][j] += (*p)[i][j-1] + (*p)[i-1][j] - (*p)[i-1][j-1];

  auto sum = [](auto& a, auto y1, auto x1, auto y2, auto x2) {return a[y2][x2] - a[y2][x1-1] - a[y1-1][x2] + a[y1-1][x1-1];};

  for(auto i=0; i<Q; ++i) {
    int y1, x1, y2, x2;
    cin >> y1 >> x1 >> y2 >> x2;
    cout << sum(S, y1, x1, y2, x2) - sum(V, y1, x1, y2-1, x2) - sum(H, y1, x1, y2, x2-1) << endl;
  }
}


Measured memory_bytes: 49024
import java.util.Scanner;

public class Main {
    public static void main(final String[] args) {
        final Scanner scanner = new Scanner(System.in);
        final int n = scanner.nextInt();
        final int m = scanner.nextInt();

        final long[] array = new long[n];
        for (int i = 0; i < n; i++) {
            array[i] = scanner.nextLong() / 2;
        }

        long base = array[0];
        for (int i = 1; i < n; i++) {
            final long gcd = computeGCD(base, array[i]);
            if (base / gcd % 2 == 0 || array[i] / gcd % 2 == 0) {
                System.out.println(0);
                return;
            }
            base = base * array[i] / gcd;

            if (base > m) {
                System.out.println(0);
                return;
            }
        }

        System.out.println((m / base + 1) / 2);
    }

    private static long computeGCD(final long a, final long b) {
        if (b > a) {
            return computeGCD(b, a);
        }

        if (b == 0) {
            return a;
        }

        return computeGCD(b, a % b);
    }
}


Measured memory_bytes: 64288
const MAX: usize = 4001;
fn main() {
    let (n, k): (usize, usize) = readln();
    let mut b = vec![vec![0i32; MAX]; MAX];
    let mut w = vec![vec![0i32; MAX]; MAX];
    for _ in 0..n {
        let (x, y, c): (usize, usize, String) = readln();
        let (bx, by) = (x % (2 * k), y % (2 * k));
        let (ex, ey) = (bx + k, by + k);
        if &c == "B" {
            b[by][bx] += 1;
            b[by][ex] -= 1;
            b[ey][bx] -= 1;
            b[ey][ex] += 1;
        } else {
            w[by][bx] += 1;
            w[by][ex] -= 1;
            w[ey][bx] -= 1;
            w[ey][ex] += 1;
        }
    }
    for y in 0..MAX {
        for x in 1..MAX {
            b[y][x] += b[y][x - 1];
            w[y][x] += w[y][x - 1];
        }
    }
    for y in 1..MAX {
        for x in 0..MAX {
            b[y][x] += b[y - 1][x];
            w[y][x] += w[y - 1][x];
        }
    }
    let mut ans = 0;
    for y in 0..2 * k {
        for x in 0..2 * k {
            let (bx, by) = (x, y);
            let (cx, cy) = ((x + k) % (2 * k), (y + k) % (2 * k));
            let mut s = 0;
            for b1 in &[0, 2 * k] {
                for b2 in &[0, 2 * k] {
                    s += w[by + b1][bx + b2];
                    s += w[cy + b1][cx + b2];
                    s += b[by + b1][cx + b2];
                    s += b[cy + b1][bx + b2];
                }
            }
            ans = max(ans, s);
        }
    }
    println!("{}", ans);
}

// --- template ---
#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused_imports)]
use std::collections::HashSet;

pub trait FromLn {
    fn fromln(s: &str) -> Self;
}
pub fn readln<T: FromLn>() -> T {
    let mut buf = String::new();
    let _ = ::std::io::stdin().read_line(&mut buf).unwrap();
    T::fromln(buf.trim())
}
pub fn readlns<T: FromLn>(n: usize) -> Vec<T> {
    let mut vs = vec![];
    for _ in 0..n {
        vs.push(readln());
    }
    vs
}
macro_rules! fromln_primitives {
    ($($t:ty),*) => { $(
        impl FromLn for $t {
            fn fromln(s: &str) -> $t {
                s.parse().unwrap()
            }
        }
    )* }
}
fromln_primitives!(
    String,
    bool,
    f32,
    f64,
    isize,
    i8,
    i16,
    i32,
    i64,
    usize,
    u8,
    u16,
    u32,
    u64
);
impl<T> FromLn for Vec<T>
where
    T: FromLn,
{
    fn fromln(s: &str) -> Vec<T> {
        s.split_whitespace().map(T::fromln).collect()
    }
}
impl FromLn for Vec<char> {
    fn fromln(s: &str) -> Vec<char> {
        s.chars().collect()
    }
}
macro_rules! fromln_tuple {
    ($($t:ident),*) => {
        impl<$($t),*> FromLn for ($($t),*) where $($t: FromLn),* {
            fn fromln(s: &str) -> ($($t),*) {
                let mut it = s.split_whitespace();
                let t = ($($t::fromln(it.next().unwrap())),*);
                assert_eq!(it.next(), None);
                t
            }
        }
    }
}
fromln_tuple!(A, B);
fromln_tuple!(A, B, C);
fromln_tuple!(A, B, C, D);
fromln_tuple!(A, B, C, D, E);
fromln_tuple!(A, B, C, D, E, F);


Measured memory_bytes: 168188
#include "bits/stdc++.h"
 
using namespace std;
 

 
int main(){
   
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
 
    int n;
    // while(cin>>n){
    cin>>n;
        map<string,int>mp;
        int res(0);
        string s;
        for(int i=0; i<n; ++i)
            cin>>s,mp[s]++,res=max(res,mp[s]);

        for(auto x: mp)
            if(x.second==res)
                cout<<x.first<<endl;

    // }
    
    return 0;
}

Measured memory_bytes: 23808
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int X, rest;
    cin >> X;
    int num500 = 0, num5 = 0;
    int sum;

    num500 = X/500;
    rest = X%500;
    num5 = rest/5;
    sum = num500 * 1000 + num5 * 5;

    cout << sum << endl;
} 

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <string> 
using namespace std;
#include <string> 
#define fast ios_base::sync_with_stdio(false);	cin.tie(NULL);
typedef long long ll;
#define inrage(x,y,n,m) (x <= m && y <= n && x >= 1 && y >= 1)
const ll MOD=1e9+7;
const int maxk=1e5+1;
const int maxn=101;
int k,n,arr[maxn];
bool dp[maxk];
int main()
{
    cin>>n>>k;
    for(int i=0;i<n;i++)cin>>arr[i];
    dp[0]=0;
    for(int i=1;i<=k;i++)
    {
        bool f=0;
        for(int j=0;j<n;j++)
        {
            if(arr[j]>i)continue;
            if(!dp[i-arr[j]])
            {
                f=1;
                break;
            }
        }
        dp[i]=f?1:0;
    }
    cout<<(dp[k]?"First":"Second")<<endl;
    return 0;
}


Measured memory_bytes: 384
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define Sort(Array) sort(Array.begin(), Array.end())
#define Reverse(a) reverse(a.begin(), a.end())
#define out(ans) cout << ans << endl;
const int MOD = 1000000007;
const int INF = 2147483647;
const ld PI = 3.14159265358979323846;

//------------↓------------- M -------------- E ---------------- M --------------- O ---------------↓--------------//
// コンパイル 
// g++ -std=c++1z
//
// -------型変換--------
// int を string に変換
// string s = to_string(n);
// string を int に変換
// int n = stoi(s);
//
// -------二分探索---------
// k以上の値が最初に現れる時のイテレータ
// lower_bound(data.begin(), data.end(), k)
// kより大きい値が最初の現れる時のイテレータ O(logN)
// upper_bound(data.begin(), data.end(), k)
// kがdataに存在するかをtrue or falseで返す O(logN)
// binary_search(data.begin(), data.end(), k)
// 
//
//
//
//
//
// 
//------------↑------------- M -------------- E ---------------- M --------------- O ---------------↑--------------//







int main(void) {

    int n; cin >> n;
    vector <string> S(n);
    rep(i,n) cin >> S[i];
    int cnt[n]['z' - 'a' + 1];
    rep(i,n){
        rep(j, 'z' - 'a' + 1) {
            cnt[i][j] = 0;
        }
    }
    rep(i,n) {
        rep(j,S[i].size()) {
            int c = S[i][j] - 'a';
            ++cnt[i][c];
        }
    }
    int mn['z' - 'a' + 1];
    rep(i, 'z' - 'a' + 1) mn[i] = 0;
    rep(j, 'z' - 'a' + 1) {
        int c_min = INF;
        rep(i,n) {
            c_min = min(c_min, cnt[i][j]);
        }
        mn[j] = c_min;
    }
    rep(i,'z' - 'a' + 1) {
        char c = 'a' + i;
        rep(j,mn[i]) {
            cout << c;
        }
    }
    cout << endl;
    

    return 0;
}











Measured memory_bytes: 256
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<map>
#include<cmath>
#include<queue>
#include<string>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
const int N=100010;
const ll mod=1e9+7;
ll qmi(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
int main()
{
    IO;
    int T=1;
    //cin>>T;
    while(T--)
    {
        ll n;
        cin>>n;
        if(n==1) cout<<0<<'\n';
        else if(n==2) cout<<2<<'\n';
        else cout<<((qmi(10ll,n)-2*qmi(9ll,n)+qmi(8ll,n))%mod+mod)%mod<<'\n';
    }
    return 0;
}

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



int main(){
  int A,B;
  int t[100][100];
  for(int i=0;i<100;i++){
    for(int j=0;j<100;j++){
      if(j>=50)t[i][j]=0;
      else t[i][j]=1;
    }
  }
  cin>>A>>B;

  for(int i=0;i<100;i+=2){
    for(int j=0;j<49;j+=2){
      if(A>1){
        t[i][j]=0;
        A--;
      }
    }
  }
  
  for(int i=0;i<100;i+=2){
    for(int j=51;j<100;j+=2){
      if(B>1){
        t[i][j]=1;
        B--;
      }
    }
  }

  cout<<100<<' '<<100<<endl;
  for(int i=0;i<100;i++){
    for(int j=0;j<100;j++){
      if(t[i][j]==0)cout<<'.';
      else cout<<'#';
    }
    cout<<endl;
  }

  return 0;
}


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

using namespace std;
#define ll long long
#define ld long double
#define  P pair<ll,ll>
#define FOR(i,n,m) for(ll i=n; i<(ll)m;i++)
#define FORr(i,n,m) for(ll i=n; i>=(ll)m; i--)
#define FORm(i,m) for(auto i=m.begin();i!=m.end();i++)
#define VEC2(x,a,b) vector<vector<ll>> x = vector<vector<ll>>(a,vector<ll>(b,0))
#define sortAl(v) sort(v.begin(),v.end())
#define sortAlr(v) sort(v.begin(),v.end()); reverse(v.begin(),v.end())
#define cinv(v,n,m) FOR(i,n,m) cin>>v.at(i)
#define coutv(v,n,m) FOR(i,n,m) cout<<v.at(i) <<" "; cout<<endl
#define cout(n) cout<<fixed<<setprecision(n)

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;
    cin>>n;
    vector<ll> v(n);
    cinv(v,0,n);
    sortAlr(v);
    ll sum=v[0]/2;
    FOR(i,1,n){
      sum+=v[i];
    }
    cout<<sum<<endl;
}


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

using ll = long long;
using pii = pair<int, int>;
template <class T>
using V = vector<T>;
template <class T>
using VV = V<V<T>>;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i, n) rep2(i, 0, n)
#define rep2(i, m, n) for (int i = m; i < (n); i++)
#define ALL(c) (c).begin(), (c).end()

constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }

template <class T, class U>
void chmin(T& t, const U& u) {
    if (t > u) t = u;
}
template <class T, class U>
void chmax(T& t, const U& u) {
    if (t < u) t = u;
}

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

template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "{";
    rep(i, v.size()) {
        if (i) os << ",";
        os << v[i];
    }
    os << "}";
    return os;
}

#ifdef LOCAL
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << H;
    debug_out(T...);
}
#define debug(...) \
    cerr << __LINE__ << " [" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define dump(x) cerr << __LINE__ << " " << #x << " = " << (x) << endl
#else
#define debug(...) (void(0))
#define dump(x) (void(0))
#endif

int main() {
    string S, T;
    cin >> S >> T;
    V<int> pfs(S.size() + 1), pft(T.size() + 1);
    rep(i, S.size()) pfs[i + 1] = pfs[i] + (S[i] == 'A' ? 1 : 2);
    rep(i, T.size()) pft[i + 1] = pft[i] + (T[i] == 'A' ? 1 : 2);
    int q;
    cin >> q;

    while (q--) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        --a, --c;
        if ((pft[d] - pft[c]) % 3 == (pfs[b] - pfs[a]) % 3) {
            puts("YES");
        } else {
            puts("NO");
        }
    }
    return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <utility>
#include <tuple>
#include <algorithm>
#include <numeric>
#include <cstdio>
#include <cmath>
#define rep(i, n) for(int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

int main(){
  int N;
  string S;
  cin >> N >> S;
  int start = 0, fin = 0;
  rep(i, N) {
    if(S[i] == '(')
      start++;
    else if(start)
      start--;
  }
  for(int i=N-1; i>=0; i--) {
    if(S[i] == ')')
      fin++;
    else if(fin)
      fin--;
  }
  rep(i, fin)
    S = '('+S;
  rep(i, start)
    S += ')';
  cout << S << endl;
  return 0;
}

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

int main(){
	int h,w,k;
	cin >> h >> w >> k;
	
	vector<string> s(h);
	rep(i,h) cin >> s[i];
	
	
	
	vector<vector<int>> checked(h,vector<int>(w,-1));
	
	queue<pair<int,int>> que;
	int color = 0;
	rep(i,h){
		rep(j,w){
			if(s[i][j] == '#'){
				que.push(make_pair(i,j));
				color++;
			}
			
			while(!que.empty()){
				auto q = que.front();
				que.pop();
				checked[q.first][q.second] = color;
				//if(q.first+1 < h && checked[q.first+1][q.second] == -1 && s[q.first+1][q.second] == '.') que.push(make_pair(q.first+1,q.second));
				if(q.second+1 < w && checked[q.first][q.second+1] == -1 && s[q.first][q.second+1] == '.') que.push(make_pair(q.first,q.second+1));
				//if(q.first-1 >= 0 && checked[q.first-1][q.second] == -1 && s[q.first-1][q.second] == '.') que.push(make_pair(q.first-1,q.second));
				if(q.second-1 >= 0 && checked[q.first][q.second-1] == -1 && s[q.first][q.second-1] == '.') que.push(make_pair(q.first,q.second-1));
			}
		}
	}

	rep(k,h){
rep(i,h){
    if(checked[i][0] == -1){
    	if(i>0 && checked[i-1][0] != -1) checked[i] = checked[i-1];
    	else if(checked[i+1][0] != -1) checked[i] = checked[i+1];
    }
}	
}
	rep(i,h){
		rep(j,w){
			cout << checked[i][j] << " ";
		}
		cout << endl;
	}
	

	return 0;
}


Measured memory_bytes: 1280
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<utility>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_set>
#include<bitset>
using namespace std;
//#define MODE 1
#ifdef MODE
#define DEB(X) cout<< #X <<": "<<X<<" ";
#define ARDEB(i,X) cout<< #X <<"["<<i<<"]: "<<X[i]<<" ";
#define END cout<<endl;
#else
#define DEB(X) {}
#define ARDEB(i,X) {}
#define END {}
#endif
typedef long long int ll;
typedef pair<int,int> P;
struct edge{int to,cost;};
#define REP(i,n) for(int i=0;i<(n);i++)
const int INF=100000000;

int main(){
	int n,m;
	char s[110][110];
	string t[110];
	vector<string> v;
	vector<string> v2;
	cin>>n>>m;
	REP(i,n){
		cin>>s[i];
	}
	REP(i,n){
		int count=0;
		for(int j=0;j<m;j++){
			if(s[i][j]=='.'){
				count++;
			}
		}
		if(count!=m){
			string tmp;
			REP(j,m)tmp.push_back(s[i][j]);
			v.push_back(tmp);
		}
	}
	n=v.size();
	DEB(v.size())END
	for(int i=0;i<m;i++){
		int count=0;
		for(int j=0;j<n;j++){
			if(v[j][i]=='.'){
				count++;
			}
		}
		if(count!=n){
			string tmp;
			REP(j,n)tmp.push_back(v[j][i]);
			v2.push_back(tmp);
		}
	}
	REP(i,v.size()){
		REP(j,v2.size()){
			cout<<v2[j][i];
		}
		cout<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;

int main(){
    ll n, c;
    cin >> n >> c;
    vector<pair<ll, ll>> s(n);
    for(int i = 0; i < n; ++i){
        cin >> s.at(i).first >> s.at(i).second;
    }

    ll ans = 0;

    // clockwise
    vector<ll> cs1(n + 1, 0);
    ll cv = 0;
    for(int i = n - 1; i > 0; --i){
        cv += s.at(i).second;
        cs1.at(i) = max(
            cs1.at(i + 1),
            cv - 2 * (c - s.at(i).first)
        );
    }
    
    cv = 0;
    for(int i = 0; i < n; ++i){
        cv += s.at(i).second;
        ans = max(
            ans,
            cv - s.at(i).first + cs1.at(i + 1)
        );
    }

    // anticlockwise
    vector<ll> cs2(n + 1, 0);
    cv = 0;
    for(int i = 1; i <= n; ++i){
        cv += s.at(i - 1).second;
        cs2.at(i) = max(
            cs2.at(i - 1),
            cv - 2 * s.at(i - 1).first
        );
    }
    
    cv = 0;
    for(int i = n - 1; i >= 0; --i){
        cv += s.at(i).second;
        ans = max(
            ans,
            cv - (c - s.at(i).first) + cs2.at(i)
        );
    }

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


Measured memory_bytes: 3456
#include <stdio.h>
#include <iostream>

#define MAX 200000

int sum_time = 0;

typedef struct process{
    char name[20];
    int time;
}process;

process q[MAX];
int head = 0;
int tail = 0;
bool is_full = false;
bool is_empty = false;

void enqueue(process p){
    is_empty = false;
    q[tail] = p;
    if(tail == MAX - 1){
        tail = 0;
    }else{
        tail += 1;
    }
    if(tail == head){
        is_full = true;
    }
}


process dequeue(){
    process p;
    if(head == MAX - 1){
        p = q[head];
        head = 0;
    }else{
        p = q[head];
        head += 1;
    }
    if(head == tail){
        is_empty = true;
    }
    return p;
}

int main(void){
    int n, quantum;
    scanf("%d %d", &n, &quantum);
    
    for(int i = 0; i < n; i++){
        process p;
        scanf("%s %d", p.name, &p.time);
        enqueue(p);
    }

    while(!is_empty){
        process p = dequeue();
        if(p.time > quantum){
            sum_time += quantum;
            p.time -= quantum;
            enqueue(p);
        }else{
            sum_time += p.time;
            printf("%s %d\n", p.name, sum_time);
        }
    }
}




Measured memory_bytes: 7572
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {

    /**
     * @param args
     */
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int N =sc.nextInt();
        
        Map<String,Boolean>map=new HashMap<String,Boolean>();
        for (int i = 0; i < N; i++) {
            map.put(sc.next(), false);
        }
        int M =sc.nextInt();
        boolean f = true;
        for (int i = 0; i < M; i++) {
            String s = sc.next();
            if(map.containsKey(s)==false){
                System.out.println("Unknown "+s);
                continue;
            }
            if(f){
                System.out.println("Opened by "+s);
            } else {
                System.out.println("Closed by "+s);
            }
            f=!f;
        }
        
        
        

    }

}

Measured memory_bytes: 20496
/*
  Motto - try hard to become an expert
*/
#include <bits/stdc++.h>
#include <map>
#include <algorithm>
#include <vector>
#include <string.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <chrono>
#include <thread>
#include <iomanip>
 
//define
#define rep(i,n)    for(int i=0;i<n;i++)
#define repu(i,k,n) for(int i=k;i<=n;i++)
#define repd(i,k,n) for(int i=k;i>=n;i--)
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define INF (int)INT_MAX
#define all(v)  v.begin(), v.end()
#define endl "\n"
 
//typedef
typedef long long int ll;
typedef long double ld;
typedef std::pair<int, int> pii;
typedef std::vector<int> vi;
typedef std::vector< pii > vii;
typedef std::vector< ll > vll;
typedef std::vector< std::pair < pii, int > > vpp;
 
const int N = 3*1e5 +5 ;
const long long MOD = 998244353;
const long long inf = 1e18;
 
using namespace std;
 
ll MAXN=100001;
ll spf[100001]; 
 
ll modpow(ll x,ll n){
    ll res=1;
    while(n>0){
        if(n&1) res=res*x%MOD;
        x=x*x%MOD;
        n>>=1;
    }
    return res;
}
 
ll modFact(ll n, ll p) 
{ 
    if (n >= p) 
        return 0; 
  
    ll result = 1; 
    for (ll i = 1; i <= n; i++) 
        result = (result * i) % p; 
  
    return result;  
} 
 
bool isPrime(int x)
{
    if(x%2==0)
        return 0;
    for(int i=3;i<=sqrt(x);i+=2)
    {
        if(x%i==0)
            return 0;
    }
    return 1;
}
 

 ll check  = 1e18;
 ll a[100001] ;
void solve()
{
	ll  n  ;
	cin>>n ; 
	vector<ll>fac ; 
	map<ll , ll>facc;
	if(n%2==0){
		fac.pb(2) ; 
		ll c = 0 ;
		while(n%2==0){
			n/=2  ;
			c++;
		}
		facc[2] = c;
	}
	ll tn = n ; 
	for(ll i = 3 ; i*i<=tn;i+=2){
		if(n%i==0){
			fac.pb(i);
			ll c = 0 ;
			while(n%i==0){
				n /= i ;
				c++;
			}
			facc[i] = c;
		}
	}
	if(n>1){
		fac.pb(n);
		facc[n] = 1 ;
		n /= n;
	}
	ll ans = 0 ;
	rep(i , fac.size()){
		ll tc = 0 ;
		ll st = 1 ;
		ll en = facc[fac[i]]; 
		while(st<=en){
			en -= st;
			st++;
			tc++;
		}
		// tc;
		ans += tc;
	}
	cout<<ans;
}
 
int main() {
    #ifndef ONLINE_JUDGE
        // for getting input from input.txt
        freopen("input.txt", "r", stdin);
        // for writing output to output.txt
        freopen("output.txt", "w", stdout);
    #endif
    
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    int t = 1;
    //cin>>t;
    while(t--)
    {
        solve();
    } 
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}

Measured memory_bytes: 3860
#include <bits/stdc++.h>
using namespace std;
#define int long long 
using ldb = long double;
using pa = pair < int, int >;
#define pb push_back
#define F  first
#define S  second
#define f(i,x,n) for(int i=x;i<n;i++) 
#define all(c) c.begin(),c.end()
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)

const int MOD = 1e9 + 7, N = 5e5 + 10;
const int LINF = LLONG_MAX;

int32_t main() {
    fast();
    int n;
    cin >> n;
    map<string,int> maps;
    string s;
    f(i,0,n){
    	cin >> s;
    	maps[s]++;
    }
    vector<pair<int,string>>q;
    for(auto s:maps){
    	q.pb({s.S,s.F});
    }
    sort(all(q));
    reverse(all(q));
    int c=1;
   	int ma=q[0].F;
   	map<string,int>mas;
   	mas[q[0].S]=1;
   	f(i,1,n){
   		if(ma==q[i].F){
   			c++;
   			mas[q[i].S]=1;
   		}
   		else{
   			break;
   		}
   	}
   	for(auto s:mas){
   		cout<<s.F<<endl;
   	}
    
}
 

Measured memory_bytes: 39916
using System;
using System.Collections.Generic;
class Program
    {
        static void Main(string[] args)
    	{
            string s = Console.ReadLine();
            string t = Console.ReadLine();
            int[,] letter_pos = new int[s.Length, 26];

            int s_size = s.Length;
            for (int i=0; i<s_size; i++)
            {
                int letter = s[i] - 'a';
                for (int j=i; j>=0; j--)
                {
                    if (letter_pos[j, letter] > 0) break;
                    letter_pos[j, letter] = i + 1;
                }
            }
            for (int i=0; i<26; i++)
            {
                if (letter_pos[0, i] == 0) continue;
                for (int j=s_size-1; letter_pos[j, i]==0; j--)
                {
                    letter_pos[j, i] = letter_pos[0, i];
                }
            }

            int pos = 0;
            long ans = 0;
            int t_size = t.Length;
            for (int i=0; i<t_size; i++)
            {
                int letter = t[i] - 'a';
                int buf = letter_pos[pos, letter];
                
                if (pos < buf)
                {
                    ans += buf - pos;
                    pos = buf;
                }
                else{
                    ans += s_size + buf - pos;
                    pos = buf;
                }
                //Console.Error.WriteLine(buf + " " + ans);
                if (pos == 0)
                {
                    Console.WriteLine(-1);
                    return;
                }
                else if(pos == s_size) pos = 0;
            }
            Console.WriteLine(ans);
        }
    }

Measured memory_bytes: 21856
x1, x2, x3, x4, x5 = map(int, input().split())

if x1 ==0:
  print(1)
  
if x2 ==0:
  print(2)
  
if x3 ==0:
  print(3)
  
if x4 ==0:
  print(4)

if x5 ==0:
  print(5)

Measured memory_bytes: 9136
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i < (n); ++i)
using namespace std;
typedef long long ll;
 
int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
 
    int h, w;
    cin >> h >> w;
 
    vector<vector<int>> c(10, vector<int>(10));
    rep(i, 10) rep(j, 10) cin >> c[i][j];
    
    vector<vector<int>> a(h, vector<int>(w));
    rep(i, h) rep(j, w) cin >> a[i][j];

    rep(k, 10) rep(i, 10) rep(j, 10){
        c[i][j] = min(c[i][j], c[i][k] + c[k][j]);
    }
 
    int res = 0;
    rep(i, h) rep(j, w){
        if(a[i][j] == -1) continue;
        res += c[a[i][j]][1];
    }
 
    cout << res << endl;
 
    return 0;
}

Measured memory_bytes: 384
#include <stdio.h>

int main(void)
{
	int m, f, r;
	int s;

	while (1) {
		scanf("%d%d%d", &m, &f, &r);
		if (m == -1 && f == -1 && r == -1) break;

		if (m < 0 || f < 0) puts("F");
		else {
			s = m + f;
			if (s >= 80) puts("A");
			else if (s >= 65) puts("B");
			else if (s >= 50) puts("C");
			else if (s < 30) puts("F");
			else puts(r >= 50 ? "C" : "D");
		}
	}
	return 0;
}



Measured memory_bytes: 2104
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <functional>
#include <limits.h>
#include <set>
#include <map>
#include <tuple>
using namespace std;



#define ll long long
#define ull unsigned long long
#define rep(i,N) for (ll i=0;i<N;i++)
#define loop(i,N,M) for(ll i=N;i<M;i++)
#define MAX(v) *max_element(v.begin(),v.end())
#define MIN(v) *min_element(v.begin(),v.end())
#define SORTL2S(type,v) sort(v.begin(),v.end(),greater<type>())
#define SORTS2L(type,v) sort(v.begin(),v.end())
#define SORTMF(v,func) sort(v.begin(),v.end(),func)
#define MP(a,b) make_pair(a,b)

ll debugFlag = false;
template<typename T> void debug(T&);
template<typename T> void debug(T&, bool);
template<typename T> void debug(vector<T>&);
template<typename T> void debug(vector<T>&, bool);
template<typename T, typename U> void debug(pair<T, U>&);
template<typename T, typename U> void debug(pair<T, U>&, bool);

template<typename T>
void debug(T& obj) {
	debug(obj, true);
}

template<typename T>
void debug(T& obj, bool lnFlag) {
	if (!debugFlag) return;
	cout << obj;
	if (lnFlag) cout << endl;
}

template<typename T>
void debug(vector<T>& obj) {
	debug(obj, true);
}

template<typename T>
void debug(vector<T>& obj, bool lnFlag) {
	if (!debugFlag) return;
	cout << "[";
	rep(i, obj.size()) {
		if (i != 0) cout << ",";
		debug(obj[i], false);
	}
	cout << "]";
	if (lnFlag) cout << endl;
}

template<typename T, typename U>
void debug(pair<T, U>& obj) {
	debug(obj, true);
}

template<typename T, typename U>
void debug(pair<T, U>& obj, bool lnFlag) {
	if (!debugFlag) return;
	cout << "(";
	debug(obj.first, false);
	cout << ",";
	debug(obj.second, false);
	cout << ")";
	if (lnFlag) cout << endl;
}

void solve() {

	int N;
	string str;
	cin >> N >> str;

	rep(i, str.size()) {
		str[i] = (str[i] + N <= 'Z' ? str[i]+N : str[i]+N-'Z'+'A'-1);
	}
	
	cout << str;
}


int main(int argc, char* argv[]) {
	if (argc == 2 && string(argv[1]) == "debug") debugFlag = true;
	solve();
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
#include<utility>
#include<queue>
#include<deque>
#include<stack>
#include<set>
#include<map>
#include<bitset>
#include<string>
#define mod 1000000007
typedef long long ll;
using namespace std;

ll N=0,K;
ll dp[51][11];
string S="0";

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	dp[0][0]=dp[0][10]=1;
	for(i=0;i<10;i++) dp[1][i]=1;
	dp[1][10]=10;
	for(i=2;i<=38;i++) {
		for(x=0;x<10;x++) {
			dp[i][x]+=dp[i-1][x];
			if(x) dp[i][x]+=dp[i-1][x-1];
			if(x<9) dp[i][x]+=dp[i-1][x+1];
		}
		dp[i][10]=dp[i-1][10];
		for(x=1;x<=9;x++) dp[i][10]+=dp[i][x];
	}
	
	
	cin>>K;
	
	if(S.size()==1) {
		K+=S[0]-'0'+1;
	}
	else {
		K += dp[S.size()-1][10];
		for(i=1;i<S[0]-'0';i++) {
			K += dp[S.size()][i];
		}
		for(i=1;i<S.size();i++) {
			if(S[i]>S[i-1]+1) {
				if(S[i-1]<'9') K += dp[S.size()-i][S[i-1]-'0'+1];
				K += dp[S.size()-i][S[i-1]-'0'];
				if(S[i-1]>='1') K += dp[S.size()-i][S[i-1]-'0'-1];
				break;
			}
			else if(S[i]<S[i-1]-1) {
				break;
			}
			
			if(S[i]==S[i-1]+1) {
				K += dp[S.size()-i][S[i-1]-'0'];
				if(S[i-1]>='1') K += dp[S.size()-i][S[i-1]-'0'-1];
			}
			if(S[i]==S[i-1]) {
				if(S[i-1]>='1') K += dp[S.size()-i][S[i-1]-'0'-1];
			}
		}
		if(i==S.size()) K++;
	}
	
	
	for(i=37;i>=0;i--) {
		if(K>dp[i][10]&&K<=dp[i+1][10]) {
			// i+1 digit
			int d=i+1;
			K -= dp[i][10];
			int S=1,E=9;
			for(x=0;x<d;x++) {
				for(i=S;i<=E;i++) {
					ll sum=0;
					for(y=S;y<=i;y++) {
						sum+=dp[d-x][y];
					}
					if(sum>=K) {
						K-=sum-dp[d-x][i];
						cout<<i;
						S=max(i-1,0);
						E=min(i+1,9);
						break;
					}
				}
				
			}
			cout<<endl;
			return;
			
			
		}
	}
}

int main(){
    solve();
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)
 
#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=(int)(a)-1;i>=(int)(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)
 
#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define bit(n) (1LL<<(n))
 
// #define DEBUG
 
#ifdef DEBUG
    #define dump(...) fprintf(stderr, __VA_ARGS__)
#else
    #define dump(...)
#endif
 
template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}
 
using namespace std;
using ll=long long;
using vi=vector<int>;
using vll=vector<ll>;
 
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int inf = INT_MAX;
const ll INF = LLONG_MAX;
const ll MOD = 1000000007LL;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
 
ll extgcd(ll a,ll b,ll& x,ll& y){x=1,y=0;ll g=a;if(b!=0) g=extgcd(b,a%b,y,x),y-=a/b*x;return g;}
ll ADD(const ll &a, const ll &b, const ll mod=MOD) { return (a+b)%mod;}
ll SUB(const ll &a, const ll &b, const ll mod=MOD) { return (a-b+mod)%mod;}
ll MUL(const ll &a, const ll &b, const ll mod=MOD) { return (1LL*a*b)%mod;}
ll DIV(const ll &a, const ll &b, const ll mod=MOD) {ll x,y; extgcd(b,mod,x,y);return MUL(a,(x+mod)%mod,mod);}
 
int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n; cin >> n;
    int Y; cin >> Y;
    Y /= 1000;

    int cnt1 = Y;
    int cnt5 = 0;
    while(cnt1 - 5 >= 0 and cnt1 + cnt5 - 4 >= n){
        cnt1 -= 5;
        cnt5 += 1;
    }
    int cnt10 = 0;
    while(cnt5 - 2 >= 0 and cnt1 + cnt5 + cnt10 - 1 >= n){
        cnt5 -= 2;
        cnt10 += 1;
    }

    bool ok = (cnt1 + cnt5 + cnt10 == n);
    if(not ok){
        cnt1 = cnt5 = cnt10 = -1;
    }

    cout << cnt10 << " " << cnt5 << " " << cnt1 << endl;
    

    return 0;
}


Measured memory_bytes: 256
//#include"bits/stdc++.h"
#include<iostream>
#include<ostream>
#include<vector>
#include<string>
#include<algorithm>

#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)



using namespace std;
using ll = long long;



void solve();

int main() {

   solve();
   return 0;

}

void solve() {

	ll w, h, l;

	while (1) {
		cin >> h >> w;
		if (h == 0) { exit(0); }
		l = h*h + w*w;
		ll mw = 1e9, mh = 1e9, ml = 1e9;

		FOR(h_, 1, 200) {
			FOR(w_, h_ + 1, 200) {
				if ((l == h_*h_ + w_*w_ && h<h_ && h_<mh) || (l == h_*h_ + w_*w_ && h<h_ && l<ml) || (l < h_*h_ + w_*w_ && h_*h_ + w_*w_ < ml )) {
					mw = w_;
					mh = h_;
					ml =( h_*h_ + w_*w_);
				}
			}
		}
		cout << mh << ' ' << mw << endl;
	}
}

Measured memory_bytes: 3068
N = int(input())
s_list = []
t_list = []
for i in range(N):
    s,t=input().split()
    s_list.append(s)
    t_list.append(int(t))
    
X = input()

flag = 0
time = 0

for i, x in enumerate(s_list):
  if x == X:
    flag = 1
  
  elif flag == 1:
    time += t_list[i]
print(time)

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

// derangement.cpp
// author: Seong Yong-ju ( @sei40kr )
// Copyright (c) 2017 Seong Yong-ju

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

using namespace std;

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

  int n;
  cin >> n;
  int ps[n];
  bool dp[n];
  REP(i, n) {
    int p;
    cin >> p;
    ps[i] = p;
    dp[i] = p != i + 1;
  }

  int ans = 0;
  REP(i, n) {
    if (dp[i]) {
      continue;
    }

    if (i != n - 1 && !dp[i + 1]) {
      dp[i + 1] = true;
    }

    ++ans;
  }

  cout << ans << endl;
}


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

int main() {
  int n;
  cin >> n;
  vector<int> p(n), sorted(n);
  REP(i, n) cin >> p[i];
  sorted = p;
  sort(sorted.begin(), sorted.end());
  int count = 0;
  REP(i, n) {
    if (p[i] != sorted[i]) count++;
    if (count > 2) {
      cout << "NO" << endl;
      return 0;
    }
  }
  cout << "YES" << endl;
}

Measured memory_bytes: 256
use std::cmp;
use std::collections::VecDeque;

fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());

    let n: usize = sc.read();
    let x = sc.read::<usize>() - 1;
    let y = sc.read::<usize>() - 1;

    let mut graph = vec![vec![]; n];
    for i in 1..n {
        graph[i].push(i - 1);
        graph[i - 1].push(i);
    }

    graph[x].push(y);
    graph[y].push(x);

    let mut count = vec![0; n];
    for start in 0..n {
        let mut dist = vec![1 << 50; n];
        dist[start] = 0;
        let mut q = VecDeque::new();
        q.push_back(start);
        while let Some(v) = q.pop_front() {
            for &next in graph[v].iter() {
                if dist[next] > dist[v] + 1 {
                    dist[next] = dist[v] + 1;
                    q.push_back(next);
                }
            }
        }

        for d in dist.into_iter() {
            count[d] += 1;
        }
    }

    for i in 1..n {
        sc.write(count[i] / 2);
        sc.write("\n");
    }
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> IO<R, W> {
        IO(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: ToString>(&mut self, s: S) {
        use std::io::Write;
        self.1.write(s.to_string().as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


Measured memory_bytes: 4352
# https://atcoder.jp/contests/m-solutions2019/submissions/5738704


from collections import deque, _heapq

n = int(input())

g = [{"num":0,"neighber":[]} for _ in range(n+1) ]

for _ in range(n-1):

    a, b = map(int, input().split())

    g[a]["neighber"].append(b)
    g[b]["neighber"].append(a)


c = sorted( map(int, input().split()) )

# sum(c[:-1]) 
print( sum(c) - c[-1] )


i = 0
s = [(0,1)]

while i < len(s):
    
    pre, cur = s[i]
    i += 1

    g[cur]["num"] = c.pop()

    for e in g[cur]["neighber"]:
        if e == pre:
            continue

        s.append( (cur,e) )

ans = ''
for i in range(1,n+1):
    ans += str( g[i]["num"] ) + " "



print( ans[:-1] )




Measured memory_bytes: 9460
#include<iostream>
#include<vector>
#include<set>
#include<unordered_set>
#include<list>
#include<stack>
#include<queue>
#include<map>
#include<unordered_map>
#include<algorithm>
#include<cmath>
#include<tuple>
#include<iomanip>
#include<climits>
#define ll long long int
#define mod 1000000007
#define pi acos(-1)
using namespace std;

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int h ,a;
  cin>>h>>a;
  int sum=0;
  for(int i=0;i<a;i++)
  {
     int tmp;
     cin>>tmp;
     sum+= tmp;
  }
  if(h<=sum)
    cout<<"Yes";
  else
  {
    cout<<"No";
  }
  
  return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
n = int(input())
ab = []
for _ in range(n):
    a,b = map(int, input().split())
    ab.append((a,b))

res = 0
for i in range(n-1,-1,-1):
    a,b = ab[i]
    a += res
    if b>=a>0:
        res += b-a
    elif a%b==0:
        pass
    else:
        res += b-a%b
print(res)


Measured memory_bytes: 16592
N=int(input())
S=input()

r=S.count('R')
g=S.count('G')
b=S.count('B')

count=r*g*b

for i in range(N):
  for d in range(N):
    j=i+d
    k=j+d
    if k>=N:
      break
    if S[i] != S[j] and S[j] !=S[k] and S[k] != S[i]:
      count -=1

print(count)
      


Measured memory_bytes: 73516
uses
  SysUtils,
  Classes;
  
function CheckFunc(strS : String; const strT : String) : Boolean;
	var
		count : Integer;
		str : String;
	begin
	Result := False;
	count := 0;
	if (Length(strS) <> Length(strT)) then
		exit;
	if (Length(strS) = 1) then
		exit;
	while (Length(strS) <> count) do
		begin
		if (strS = strT)then
			begin
			Result := True;
			exit;
			end;
		str := strS[Length(strS)];
		str := str + Copy(strS, 1, Length(strS) - 1);
		strS := str;
		count := count + 1;
		end;
	end;

var
	strS, strT : String;
begin	
	readln(strS);
	readln(strT);
	
	if CheckFunc(strS, strT) then
		writeln('Yes')
	else
		writeln('No');
end.

Measured memory_bytes: 256
#include<vector>
#include<iostream>
#include<algorithm>

using namespace std;
int main()
{
    int n, k;
    cin >> n >> k;
    vector<int> a;
    for(int i = 0; i < 200001; i++){;
        a.push_back(0);
    }
    for(int i = 0; i < n; i++){
        int in;
        cin >> in;
        a[in]++;
    }
    sort(a.begin(), a.end(), greater<int>());
    int ans = n;
    for(int i = 0; i < k; i++){
        ans -= a[i];
    }
    cout << ans << endl;
    return 0;
}

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

int main(){
    int64_t N,K; cin >> N >> K;
    vector<int64_t> H(N);
    for(int64_t i=0;i<N;i++){
        cin >> H[i];
    }
    sort(H.begin(),H.end());
    int64_t sum=0;
    for(int64_t i=0;i<N-K;i++){
        sum += H[i];
    }
    cout << sum << endl;


}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define RI(X) scanf("%d", &(X))
#define RII(X, Y) scanf("%d%d", &(X), &(Y))
#define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define RS(X) scanf("%s", (X))
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define F first
#define S second
#define RF(x) freopen(x,"r",stdin)
#define WF(x) freopen(x,"w",stdout)
typedef long long LL;
using namespace std;
typedef pair<LL,LL> PLL;
typedef pair<int,int> PII;
const LL MOD = (LL)1e9+7;
const int SIZE = 2e5+5;
const LL INF = 1LL<<29;
const double eps = 1e-4;
const double PI=3.1415926535897932;

vector<int> adj[100009];
int c[100009];
int isbt;

void dfs(int x){
	for(int i:adj[x]){
		if(c[i]==-1){
			c[i]=c[x]^1;
			dfs(i);
		}
		else{
			if((c[i]^c[x])!=1)isbt=0;
		}
	}
}

int main(){
	DRII(n,m);
	REP(i,m){
		DRII(a,b);a--;b--;
		adj[a].PB(b);
		adj[b].PB(a);
	}
	MS1(c);
	LL v1=0,v2=0,v3=0;
	REP(i,n){
		if(c[i]!=-1)continue;
		if(SZ(adj[i])==0){c[i]=0,v1++;}
		else{
			isbt=1;c[i]=0;
			dfs(i);
			if(isbt)v2++;
			else v3++;
		}
	}
	//printf("%lld %lld %lld\n",v1,v2,v3);
	printf("%lld",2LL*v2*v2+v1*v1+v3*v3+2LL*v2*v3+2LL*v1*(n-v1));
}


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

int main(void)
{
    int a, v, b, w, t;
    cin >> a >> v;
    cin >> b >> w;
    cin >> t;

    int l = abs(b-a);

    if(w >= v)
    {
        cout << "NO" << endl;
        return 0;
    }

    if((l+(v-w)-1)/(v-w) <= t)
    {
        cout << "YES" << endl;
    }
    else
    {
        cout << "NO" << endl;
    }
    
    

    return 0;
}



Measured memory_bytes: 3632