akhauriyash/Code-Regression huggingface dataset:
# https://tjkendev.github.io/procon-library/python/string/rolling_hash.html
import sys
def input():
	return sys.stdin.readline()[:-1]

BASE, MOD = 80408696819889532, (1<<61)-1

class RollingHash():
	def __init__(self, s, base, mod):
		self.mod = mod
		self.pw = pw = [1]*(len(s)+1)

		l = len(s)
		self.h = h = [0]*(l+1)

		v = 0
		for i in range(l):
			# case of letters
			h[i+1] = v = (v * base + ord(s[i])) % mod
		v = 1
		for i in range(l):
			pw[i+1] = v = v * base % mod

	# [l. r)
	def get(self, l, r):
		return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod

	def concatenate(self, l1, r1, l2, r2):
		return (self.get(l1, r1) * self.pw[r2-l2] + self.get(l2, r2)) % self.mod

s = input()
s_concat = s
t = input()
ns, nt = len(s), len(t)

if ns == 1:
	if {s} == set(list(t)):
		print(-1)
	else:
		print(0)
	sys.exit()

while len(s_concat) < ns + nt - 1:
	s_concat += s
rh_s, rh_t = RollingHash(s_concat, BASE, MOD), RollingHash(t, BASE, MOD)
t_hash = rh_t.get(0, nt)

adj = [-1 for _ in range(ns)]
for i in range(ns):
	if rh_s.get(i, i+nt) == t_hash:
		if i == (i+nt)%ns:
			print(-1)
			sys.exit()
		adj[i] = (i+nt)%ns

visited = [False for _ in range(ns)]
path_len = [0 for _ in range(ns)]

def dfs(x):
	cur = x
	res = 0
	while adj[cur] >= 0:
		visited[cur] = True
		if adj[cur] == x:
			print(-1)
			sys.exit()
		res += 1
		if path_len[adj[cur]] > 0:
			path_len[x] = path_len[adj[cur]] + res
			return path_len[adj[cur]] + res
		cur = adj[cur]
	path_len[x] = res
	return res

ans = 0
for i in range(ns):
	if not visited[i]:
		d = dfs(i)
		ans = max(ans, d)

if ans == ns:
	print(-1)
else:
	print(ans)

Measured memory_bytes: 426088
#include <iostream>
#include <algorithm>
#include <string>

using namespace std;
int N;
string ar;
int check[990],check2[990],Cnt,Max;

int main()
{
	cin>>N>>ar;
	for(int x=1; x<N; x++)
	{
		Cnt=0;
		for(int y=0; y<900; y++)
		{
			check[y]=0;
			check2[y]=0;
		}

		for(int z=0; z<x; z++)
		{
			check[ar[z]-97]=1;
		}

		for(int w=x; w<N; w++)
		{
			if(check[ar[w]-97]==1&&check2[ar[w]-97]!=1)
			{
				Cnt++;
				check2[ar[w]-97]=1;
			}
		}
		if(Cnt>Max) Max=Cnt;
		
	}
	cout<<Max;
}

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    LL n;
    cin>>n;
    
    char arr[n+1];
    
    LL west_left[n+2];
    LL east_left[n+2];
    LL west_right[n+2];
    LL east_right[n+2];
    
    LL i;
    
    
    for(i=0;i<=n+1;i++)
    {
        west_left[i]=0;
        east_left[i]=0;
        west_right[i]=0;
        east_right[i]=0;
    }
    
    for(i=1;i<=n;i++)
    cin>>arr[i];
    
    for(i=1;i<=n;i++)
    {
        if(arr[i]=='W')
            west_left[i]=west_left[i-1]+1;
        
        else
            west_left[i]=west_left[i-1];
            
        if(arr[i]=='E')
            east_left[i]=east_left[i-1]+1;
        
        else
            east_left[i]=east_left[i-1];    
    }
    
    for(i=n;i>=1;i--)
    {
        if(arr[i]=='W')
            west_right[i]=west_right[i+1]+1;
        
        else
            west_right[i]=west_right[i+1];
            
        if(arr[i]=='E')
            east_right[i]=east_right[i+1]+1;
        
        else
            east_right[i]=east_right[i+1];    
    }
    
    LL ans=1000000000000;
    
    for(i=1;i<=n;i++)
    ans=min(ans,west_left[i-1]+east_right[i+1]);
    
    cout<<ans<<"\n";
}
    

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

bool even(int a) {
    return (a % 2) == 0;
}

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

    int pt = 0;
    int px = 0, py = 0;

    for (int i = 0; i < N; i++) {
        int t, x, y;
        cin >> t >> x >> y;
        t -= pt;
        x -= px;
        y -= py;

        int m = abs(x) + abs(y);

        if (even(t) != even(m) || m > t) {
            cout << "No" << endl;
            return 0;
        }

        pt += t;
        px += x;
        py += y;
    }

    cout << "Yes" << endl;

    return 0;
}

Measured memory_bytes: 256
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r=l+1
 if r<H:
  if A[i]<A[l]:
   if A[l]<A[r]:A[i],A[r]=A[r],A[i];h(r)
   else:A[i],A[l]=A[l],A[i];h(l)
  elif A[i]<A[r]:A[i],A[r]=A[r],A[i];h(r)
 elif l<H and A[i]<A[l]:A[i],A[l]=A[l],A[i];h(l)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))


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

#define int long long

using namespace std;

#ifdef LOCAL 
#include "/media/brayand/7801-B00D/debugger.h"
#else
template<typename... Args>
void db(Args... args){}
#endif

vector<int> arr[100];

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

    int N, M;
    cin >> N >> M;

    int mcm2 = 1;

    bool flai = true;

    for(int i = 0 ; i < N ; i++)
    {
    	int n;
    	cin >> n;
    	mcm2 = mcm2*n/__gcd(mcm2,n);
    	if(mcm2 > M)flai = false;
    	n /= 2;

    	int cont = 0;

    	while(n%2 == 0)
    	{
    		cont++;
    		n/=2;
    	}
    	arr[cont].push_back(n);
    }


    bool flag = false;

    int mcm = 1;

    int res = 1;

    for(int i = 0 ; i < 100 ; i++)
    {
    	if(arr[i].size() == N)
    	{
    		flag = true;
    		for(auto x : arr[i])
    		{
    			mcm = mcm*x/__gcd(mcm,x);
    			if(mcm > M)
    			{
    				flag = false;
    				break;
    			}
    		}
    		mcm *= (1ll<<i);
    		if(mcm > M)flag = false;

    		if(flai)
    		{
    			res += (M-mcm)/mcm2;
    		}
    	}
    }

    if(flag)cout << res << '\n';
    else cout << 0 << '\n';

    return 0;
}

Measured memory_bytes: 1400
#include <bits/stdc++.h>
#include <boost/range/irange.hpp>

using namespace std;
using namespace boost;

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

    vector<int64_t> a(n);
    for (auto&& aa : a) {
        cin >> aa;
    }

    sort(a.begin(), a.end());

    vector<pair<int64_t, int64_t>> p(m);
    for (auto&& pp : p) {
        cin >> pp.second >> pp.first;
    }

    sort(p.begin(), p.end());

    int64_t s = 0;
    for (auto aa : a) {
        if (!p.empty() && aa < p.back().first) {
            s += p.back().first;
            --p.back().second;
            if (p.back().second == 0) {
                p.pop_back();
            }
        } else {
            s += aa;
        }
    }

    cout << s << endl;
}

Measured memory_bytes: 2560
import math
from collections import deque

# 2つの入力を空白で分割し、数値化
N, D = map(int, input().split())

points = []

for i in range(0, N):
    points.append(list(map(int, input().split())))


def distance(x, y):
    dd = 0
    for xy in zip(x,y):
        dd += (xy[0] - xy[1])**2
    return math.sqrt(dd)

q = deque(points)

result = 0
while len(q) != 0:
    left = q.popleft()
    for right in q:
        d = distance(left, right)
        if d.is_integer():
            result += 1
        else:
            pass

print(result)

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

#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define show(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define show(x)
#endif

typedef long long int ll;
typedef pair<int,int> pii;
template<typename T> using vec=std::vector<T>;

const int inf=1<<30;
const long long int infll=1LL<<62;
const double eps=1e-9;
const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
    	os << v << ",";
    }
    os << "]";
    return os;
}

void solve(){
    string s;
    cin >> s;
    ll ans=stol(s);
    const int len=s.size();
    rep(i,1,1<<(len-1)){
        vector<int> v;
        bitset<9> bs(i);
        rep(j,0,len-1){
            if(!bs[j]) continue;
            v.push_back(j);
        }
        ll tmp=0,k=0;
        rep(j,0,v.size()){
            tmp+=stol(s.substr(k,v[j]+1-k));
            k=v[j]+1;
        }
        tmp+=stol(s.substr(k,s.size()-k));
        ans+=tmp;
    }
    cout << ans << endl;
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(10);
    solve();
    return 0;
}


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

int main(){
  int n, res = 0, min = 110;
  cin >> n;
  int h[n];
  rep(i, n) {
    cin >> h[i];
  }
  rep(i, n-1) {
    if (h[i] > h[i+1]) {
      res += h[i] - h[i+1];
    }
    if (min >= h[i]) {
      min = h[i];
    }
  }

  if (min >= h[n-1]) {
    min = h[n-1];
  }
  res += h[n-1] - min;
  cout << res + min << endl;
}


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

using namespace std;
int32_t main()
{
 long long n;cin>>n;;
 long long a[n];
 for(long long i=0;i<n;i++){
  cin>>a[i];
 }
 long long dp[n];
 dp[n-1]=0;
 dp[n-2]=abs(a[n-1]-a[n-2]);
 for(long long i=(n-3);i>=0;i--){
  long long pos1=abs(a[i]-a[i+1])+dp[i+1];
  long long pos2=abs(a[i]-a[i+2])+dp[i+2];
  dp[i]=min(pos1,pos2);
 }
 cout<<dp[0]<<endl;
 return 0;
}


Measured memory_bytes: 5176
#include<bits/stdc++.h>
#define lowbit(a) ((a)&(-(a)))
using namespace std;

void file(bool opt)
{
	if (opt&&fopen("in.txt", "r"))
	{
		freopen("in.txt", "r", stdin);
		//freopen("out.txt", "w", stdout);
	}
}

int main()
{
	int a, b, c;
	cin >> a >> b >> c;
	int ans = a + b;
	ans = min(ans, a + c);
	ans = min(ans, b + c);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <map>
using namespace std;
using ll = long long;
int main() {
  int N;
  cin >> N;
  ll a;
  map<ll, ll> ms;
  for(int i = 0; i < N; ++i) {
    cin >> a;
    ms[a]++;
  }
  if(ms.size() == N) {
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }
  return 0;
}

Measured memory_bytes: 12800
#include <stdio.h>
int button(int*,int*);
int process(int*,int*,int*);

int main(){
    int A,B,coin=0;
    scanf("%d",&A);
    scanf("%d",&B);

    process(&coin,&A,&B);
    process(&coin,&A,&B);
    
    printf("%d",coin);
    return 0;
}

int button(int *C,int *X){
    *C = *C + *X;
    *X = *X - 1;
    return 0;
}

int process(int *c,int *a,int *b){
    if(*a>*b){
        button(c,a);
    }else{
        button(c,b);
        }
    return 0;
}


Measured memory_bytes: 128
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstdint>
#include <string>
#include <unordered_map>
#include <vector>

int main() {
  int n, k;
  while (std::cin >> n >> k) {
    int res = 0;
    if (k > 1) res = n - k;
    std::cout << res << std::endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n, k, t, p;
int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> k;
	for (int i = 0; i < n; i++)
	{
		cin >> t;
		if (t >= k)
		{
			p++;
		}
	}
	cout << p << endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(int argc, char *argv[])
{
	int n;
	char s[100001];
	int count[26];
	int i;
	long long ans;
	
	scanf("%d", &n);
	scanf("%s", s);

	for (i = 0; i < 26; i++) {
		count[i] = 1;
	}
	
	for (i = 0; i < n; i++) {
		count[s[i] - 'a']++;
	}
	
	ans = 1;
	for (i = 0; i < 26; i++) {
		ans *= count[i];
		ans %= 1000000007;
	}
	ans--;
	
	printf("%lld\n", ans);
	
	return 0;
}

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

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

typedef long long ll;
using namespace std;
int mod = 1000000007;

int main(void){
    vector<pair<int, int>> ans;
    while(true){
        int val = mod;
        pair<int, int> ans;
        int N, M; cin >> N >> M;
        if(N == 0 && M == 0) break;
        vector<int> A(N), B(M);
        int sum_taro = 0, sum_hanako = 0;
        rep(i, N) {cin >> A[i]; sum_taro += A[i];}
        rep(i, M) {cin >> B[i]; sum_hanako += B[i];}
        rep(i, N){
            rep(j, M){
                if(sum_taro - A[i] + B[j] == sum_hanako - B[j] + A[i]){
                    val = min(val, A[i] + B[j]);
                    if(val == A[i] + B[j]){
                        ans.first = A[i];
                        ans.second = B[j];
                    }
                }
            }
        }
        if(val == mod) cout << -1 << endl;
        else cout << ans.first << " " << ans.second << endl;
    }
    return 0;
}


Measured memory_bytes: 3116
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file  
#include <ext/pb_ds/tree_policy.hpp>  
#include <functional> // for less  
using namespace         std;
#define                 int long long
#define                 double long double
#define                 pb push_back
#define                 mp make_pair
#define st(arr,a)       memset(arr,a,sizeof arr)
#define                 nl cout<<'\n'
#define bitcount(x)     __builtin_popcountll(x)
const int MOD = 1000000007ll;
#define forn(i,a,b)     for(int i=a;i<=b;i++)
#define rfor(i,a,b)     for(int i=a;i>=b;i--)
#define all(x)          x.begin() , x.end()
#define pi pair<int,int>
#define X first
#define Y second
#define N 1014159
#define  vi vector<int>
#define  v  vector
#define die exit(0)
#define alln(arr) arr+1 , arr+1+n
using namespace __gnu_pbds;  
typedef tree<int, null_type, less<int>, rb_tree_tag,  
            tree_order_statistics_node_update> oset; 

int n,m,k,arr[N];
int A[N],B[N];
int dp[1003][10003];

int get(int idx,int rem)
{
	if(rem<=0)return 0;

	if(idx == n+1)
	{
		if(rem>0)return MOD;
		return 0;
	}
	int&ans = dp[idx][rem];
	if(ans!=-1)return ans;
	ans = min(A[idx]+get(idx,rem-B[idx]),get(idx+1,rem));
	return ans;
}


void solve()
{
	cin>>m>>n;
	forn(i,1,n)
	{
		cin>>B[i]>>A[i];
	}
	st(dp,-1);
	cout<<get(1,m);

    
}


signed main() 
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
    int t = 1;
    //cin>>t;
    forn(i,1,t)
    {
        solve();
        nl;
    }



    return 0;

}

//       clang++ c.cpp ; ./a.out < a.txt ;  

Measured memory_bytes: 82688
n = int(input())
a = list(map(int, input().split()))
rain = [0]*n
rain[0] += sum([a[i] for i in range(n) if i%2 == 0]) - sum([a[i] for i in range(n) if i%2 == 1])
for i in range(n-1):
    rain[i+1] = 2 * (a[i] - rain[i]//2)
print(*rain)


Measured memory_bytes: 14092
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cassert>
#include <iostream>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <sstream>
#include <bitset>
#define repr(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define invrepr(i,a,b) for(int i=b-1;i>=a;i--)
#define invrep(i,n) invrepr(i,0,n)
 
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;
 
int main() {
    std::ios::sync_with_stdio(0); cin.tie(0);
 
    int i,j,h;
    int Q,K,P,C,N,X;
 
    long double kh,km,A,B;
 
    string S;
    map<long double, ll> m;
 
    cin >> A>>B;
    
 
    cout<<setprecision(17)<< floor(A*B)<<endl;
    
    return 0;
}

Measured memory_bytes: 3848
ri = lambda: int(input())
rl = lambda: list(map(int,input().split()))
rr = lambda N: [ri() for _ in range(N)]
YN = lambda b: print('YES') if b else print('NO')
INF = 10**18

N,K=rl()

W = [[0 for _ in range(2*K+3)] for _ in range(2*K+3)]
for i in range(N):
    x,y,c=input().split()
    x = int(x)%(2*K)
    y = (int(y) if c=='W' else int(y)+K)%(2*K)
    if (x<K)^(y<K):
        x %= K
        y %= K
        W[0][y+1] += 1
        W[0][y+K+1] -= 1
        W[x+1][0] += 1
        W[x+1][y+1] -= 2
        W[x+1][y+K+1] += 2
        W[x+1][2*K] -= 1
        W[x+K+1][0] -= 1
        W[x+K+1][y+1] += 2
        W[x+K+1][y+K+1] -= 2
        W[x+K+1][2*K] += 1
        W[2*K][y+1] -= 1
        W[2*K][y+K+1] += 1
    else:
        x %= K
        y %= K
        W[0][0] += 1
        W[x+1][0] -= 1
        W[0][y+1] -= 1
        W[x+1][y+1] += 2
        W[x+K+1][y+1] -= 2
        W[x+1][y+K+1] -= 2
        W[x+K+1][y+K+1] += 1
        W[x+K+1][0] += 1
        W[2*K][0] -= 1
        W[2*K][y+1] += 1
        W[0][y+K+1] += 1
        W[0][2*K] -= 1
        W[x+1][2*K] += 1

ans = 0
for x in range(0,2*K+1):
    for y in range(0,2*K+1):
        W[x][y] += W[x][y-1]
for y in range(0,2*K+1):
    for x in range(0,2*K+1):
        W[x][y] += W[x-1][y]
        ans = max(ans,W[x][y])

print(ans)

Measured memory_bytes: 91868
#include <stdio.h>
#include <string.h>
#include <math.h>
 int main(void){
    
    int N,i,s=0;
   scanf("%d",&N);
    int a[N],b[N],c[N-1];
   for(i=0;i<N;i++)
     scanf("%d",&a[i]);
   for(i=0;i<N;i++)
     scanf("%d",&b[i]);
   for(i=0;i<N-1;i++)
     scanf("%d",&c[i]);
    /* if(i<N-1){
     scanf("%d %d %d",&a[i],&b[i],&c[i]); //N-1までのabcを求めた
     }
     else
       scanf("%d%d",&a[i],&b[i]);*/
   for(i=0;i<N;i++){
     s+=b[a[i]-1];
     if(i>0){
       if(a[i]-a[i-1]==1){
         s+=c[a[i-1]-1];
       }
     }
   }
   printf("%d",s);     
     
}

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

using namespace std;

typedef long long int ll;
typedef pair<ll, ll> pll;

#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))
#define REP(i, n) FOR(i,n,0)
#define OF64 std::setprecision(10)

const ll MOD = 998244353;
const ll INF = (ll) 1e15;

template<typename T>
struct SegmentTree {
    using F = function<T(T, T)>;

    SegmentTree(F func, T id)
            : merge(func), identity(id) {}

    void init(ll n) {
        offset = 1;
        while (offset < n)
            offset <<= 1;
        node.assign(offset << 1, identity);
    }

    void build(const vector<T> &v) {
        int n = static_cast<int>(v.size());
        init(n);
        for (int i = 0; i < n; ++i) {
            node[offset + i] = v[i];
        }
        for (int i = offset - 1; i >= 0; --i) {
            node[i] = merge(node[(i << 1) | 0], node[(i << 1) | 1]);
        }
    }

    void set(int index, T value) {
        index += offset;
        node[index] = value;
        while (index >>= 1) {
            node[index] = merge(node[(index << 1) | 0], node[(index << 1) | 1]);
        }
    }

    //! [left, right]
    T get(int left, int right) {
        left += offset;
        right += offset + 1;

        T val = identity;
        while (left < right) {
            if (left & 1)
                val = merge(val, node[left++]);
            if (right & 1)
                val = merge(val, node[--right]);

            left >>= 1;
            right >>= 1;
        }
        return val;
    }

    T identity;
    F merge;
    vector<T> node;
    int offset;
};

pll X[15];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N, K;
    cin >> N >> K;
    REP(i, K) {
        cin >> X[i].first >> X[i].second;
    }

    SegmentTree<ll> seg([](ll a, ll b) { return (a + b) % MOD; }, 0);
    seg.init(N + 5);
    seg.set(1, 1);
    FOR(i, N, 1) {
        ll sum = 0;
        REP(j, K) {
            ll b = std::max(0LL, i + 1 - X[j].second);
            ll a = i + 1 - X[j].first;
            if (a < b)
                continue;
            sum += seg.get(b, a);
            sum %= MOD;
        }

        seg.set(i + 1, sum);
    }

    cout << seg.get(N, N) % MOD << endl;
    return 0;
}

Measured memory_bytes: 7420
import java.io.*;
import java.util.*;

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = Integer.parseInt(sc.next());
    int A[] = new int[N];
    int B[] = new int[N];
    int C[] = new int[N-1];
    
    for (int i = 0; i < N; i++) {
      A[i] = Integer.parseInt(sc.next());
    }
    for (int i = 0; i < N; i++) {
      B[i] = Integer.parseInt(sc.next());
    }
    for (int i = 0; i < N-1; i++) {
      C[i] = Integer.parseInt(sc.next());
    }
    
    int sum = B[A[0]-1];
    for (int i = 1; i < N; i++) {
      sum += B[A[i]-1];
      if (A[i] == A[i-1] + 1) {
        sum += C[A[i-1]-1];
      }
    }
    
    System.out.println(sum);
  }
}

Measured memory_bytes: 23764
match = ['eraser', 'erase', 'dreamer', 'dream']
len_m = [len(m) for m in match]
S = input()
n = len(S)
dp = [False] * (n + 1)
dp[0] = True
for i in range(1, n + 1):
    for lm, m in zip(len_m, match):
        if S[:i].endswith(m):
            dp[i] |= dp[i - lm]
print('YES' if dp[n] else 'NO')

Measured memory_bytes: 3956
H, W = map(int, input().split())
N = H * W

chart = [input() for _ in range(H)]

def node(h, w):
    return h * W + w

minDist = [[10**10] * N for _ in range(N)]

for i in range(N):
    minDist[i][i] = 0

for h in range(H):
    for w in range(W):
        if chart[h][w] == '#':
            continue

        if h > 0 and chart[h - 1][w] == '.':
            minDist[node(h, w)][node(h - 1, w)] = 1
            minDist[node(h - 1, w)][node(h, w)] = 1
        if h < H - 1 and chart[h + 1][w] == '.':
            minDist[node(h, w)][node(h + 1, w)] = 1
            minDist[node(h + 1, w)][node(h, w)] = 1
        if w > 0 and chart[h][w - 1] == '.':
            minDist[node(h, w)][node(h, w - 1)] = 1
            minDist[node(h, w - 1)][node(h, w)] = 1
        if w < W - 1 and chart[h][w + 1] == '.':
            minDist[node(h, w)][node(h, w + 1)] = 1
            minDist[node(h, w + 1)][node(h, w)] = 1

for k in range(N):
    for i in range(N):
        for j in range(N):
            d = minDist[i][k] + minDist[k][j]
            if minDist[i][j] > d:
                minDist[i][j] = d

ans = 0
for dists in minDist:
    for d in dists:
        if d < 10**10:
            ans = max(ans, d)

print(ans)

Measured memory_bytes: 44636
#include <bits/stdc++.h>
using namespace std;       //     ____   _   _  __   __
#define ll long long       //    / ___| | |_| |   / /
const ll INF = 0x3f3f3f3f; //   | |     |  _  |   V /
const ll N   = 1e5 + 5;    //   | |___  | | | |   | |
const ll MOD = 1e9 + 7;    //    ____| |_| |_|   |_|
ll read() {
  ll   x = 0, f = 1;
  char ch = getchar();

  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1; ch = getchar();
  }

  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0'; ch = getchar();
  }
  return x * f;
}

ll n, m, dp[N];
struct node {
  ll x, y;
}  a[N];
ll ans;
ll cmp(node a, node b) {
  return a.y < b.y;
}

int main() {
  n = read(), m = read();

  for (int i = 1; i <= n; i++) {
    a[i].x = read(), a[i].y = read();
  }
  sort(a + 1, a + 1 + n, cmp);

  for (int i = 1; i <= n; i++) {
    for (int j = m; j >= a[i].x; j--) {
      dp[j] = max(dp[j], dp[j - a[i].x] + a[i].y);
    }
  }
  ans = dp[m];

  for (int k = max(1LL, n - 100); k <= n; k++) {
    for (int i = 0; i <= m; i++) dp[i] = 0;

    for (int i = 1; i <= n; i++) {
      if (i == k) continue;

      for (int j = m; j >= a[i].x; j--) {
        dp[j] = max(dp[j], dp[j - a[i].x] + a[i].y);
      }
    }

    for (int i = 0; i < m; i++) {
      ans = max(ans, dp[i] + a[k].y);
    }
  }


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


Measured memory_bytes: 384
#include "bits/stdc++.h"

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

typedef pair<int,int>Pi;
typedef pair<long long,long long>P;
typedef pair<long long,P>PP;
typedef pair<P,P>PPP;

const long long MOD=1e9+7;
const long long INF=5e18;
const int di[4]={1,0,-1,0};
const int dj[4]={0,1,0,-1};

#define fr first
#define sc second
#define pb push_back
#define eb emplace_back
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()

ll n,a[100010],b[100010],sum,ans;
priority_queue<ll>pq;
bool fl;

void input(){
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i]>>b[i];
		pq.push(a[i]+b[i]);
		sum+=b[i];
	}
	return;
}

void solve(){
	for(int i=0;i<n;i++){
		if(!fl)ans+=pq.top(),fl=true;
		else fl=false;
		pq.pop();
	}
	cout<<ans-sum<<endl;
	return;
}

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

Measured memory_bytes: 2676
#include <bits/stdc++.h>
using namespace std;
long long GCD(long long a, long long b) {
    if (a > b) swap(a, b);
    if (a == 0) return b;
    return GCD(b % a, a);
}
long long LCM(long long a, long long b) {
    return a/GCD(a, b)*b;
}
int main () {
    int N;
    cin >> N;
    long long ans;
    cin >> ans;
    for (int i = 0; i < N-1; i++) {
        long long T;
        cin >> T;
        ans = LCM(ans, T);
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef double db; //
typedef string str; //
//
typedef pair<int,int> pi;
typedef pair<ll,ll> pl; //
typedef pair<db,db> pd; //
//
typedef vector<int> vi; 
typedef vector<ll> vl; //
typedef vector<db> vd; //
typedef vector<str> vs; //
typedef vector<pi> vpi;
typedef vector<pl> vpl; //
typedef vector<pd> vpd; //
 
typedef tree<pi, null_type, less<pi>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
 
#define mp make_pair
#define f first
#define s second
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend() //
#define rsz resize
#define ins insert //
#define ft front() //
#define bk back()
#define pf push_front //
#define pb push_back
#define eb emplace_back //
#define lb lower_bound //
#define ub upper_bound //
 
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
 
const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5; //
const ll INF = 1e18; //
const ld PI = acos((ld)-1);
const int xd[4] = {1,0,-1,0}, yd[4] = {0,1,0,-1}; //
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); //
//
template<class T> bool ckmin(T& a, const T& b) { 
	return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { //
	return a < b ? a = b, 1 : 0; } //
constexpr int pct(int x) { return __builtin_popcount(x); } //
constexpr int bits(int x) { return 31-__builtin_clz(x); } // floor(log2(x)) //
constexpr int cdiv(int a, int b) { return a/b+!(a<0||a%b == 0); } // division of a by b rounded up, assumes b > 0 //
// IGNORE
int fstTrue(function<bool(int)> f, int lo, int hi) {
	hi ++; assert(lo <= hi); // assuming f is increasing
	while (lo < hi) { // find first index such that f is true 
		int mid = (lo+hi)/2; 
		f(mid) ? hi = mid : lo = mid+1; 
	} 
	return lo;
}
template<class T> void remDup(vector<T>& v) { 
	sort(all(v)); v.erase(unique(all(v)),end(v)); }
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
 
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
// IGNORE
//
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int A, B, C;
	cin >> A >> B >> C;
	int K;
	cin >> K;
	int cnt = 0;
	while(B <= A){
		cnt++;
		B *= 2;
	}
	while(C <= B){
		cnt++;
		C *= 2;
	}
	cout << (cnt <= K ? "Yes" : "No") << endl;
}


Measured memory_bytes: 3608
package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)

	divs := make([]int, n+1)
	for i := 1; i < n+1; i++ {
		for j := i; j < len(divs); j += i {
			divs[j] += j
		}
	}

	cnt := 0
	for i := 1; i < n+1; i++ {
		cnt += divs[i]
	}

	fmt.Println(cnt)
}

Measured memory_bytes: 82556
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.io.PrintWriter;
import java.util.*;

// import 
class Main {


    static int min(int a,int b)
    {
        return Math.min(a, b);
    }

    static int abs(int a)
    {
        return Math.abs(a);
    }

    public static void main(String[] args) throws Exception {
        PrintWriter p = new PrintWriter(System.out);
        // Scanner sc = new Scanner(System.in);
        // int n = sc.nextInt();
        // sc.nextLine();
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        
        Object[] nk =Arrays.stream(bf.readLine().split(" ")).map(Integer::parseInt).toArray();

        int n = (int)nk[0];
        int k = (int)nk[1];


        Integer arr[] = Arrays.stream(bf.readLine().split(" ")).map(Integer::parseInt).toArray(Integer[]::new);
        
        int dp[] = new int[n+1];
        // int mod = 100000000+7;
        Arrays.fill(dp, Integer.MAX_VALUE); //fill large values in dp 
        dp[0] = 0;
        for (int i = 0; i < n; i++) 
        {
            for (int j = 1; j <= k; j++)
            {
                if(i+j< n) dp[i+j] = min(dp[i+j],dp[i]+abs(arr[i]-arr[i+j]));    
            }
        }
        // System.out.println(Arrays.toString(dp));
        // System.out.println(dp[n-1]);
        p.println(dp[n-1]);
        p.flush();
    }
}

Measured memory_bytes: 49012
#include<bits/stdc++.h>
using namespace std;
int main(){
  char a[100],b[100];
  cin >> a >> b;
  for(int i=0;i<strlen(a);i++){
    cout << a[i];
    if(b[i]!='\0'&& b[i]!='@'){
      cout << b[i];
    }
  }
}


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

int main() {
  int a, b, c;
  cin >> a >> b >> c;
  int temp = a;
  for(int i=0; i<b; i++) {
    if(temp % b == c) {
      cout << "YES" << endl;
      return 0;
    }
    temp += a;
  }
  cout << "NO" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define se second
#define fi first
#define pb push_back
const int N=1e5 + 5;
int a[N], b[N];

int main(){

//	freopen("in.txt","r",stdin);

	int n;
	scanf("%d", &n);
	for (int i=0; i<n; i++)scanf("%d", a +i);
	for (int i=0; i<n; i++)scanf("%d", b +i);
	ll sum1=0, sum2 =0;
	for (int i =0; i<n; i++){
		if ((b[i]&1) != (a[i]&1))sum2++, b[i]++;
		sum1 += max (0, (b[i] - a[i])/2);
		sum2 += max (0, a[i] - b[i]);
	}
	if (sum1>=sum2)puts("Yes");
	else puts("No");


	return 0;

}


Measured memory_bytes: 384
#define DEBUG(...)
/*                        Strip me down and go to town                        */
/*                          Lick me over upside down                          */
/*                     Pound and pound and pound and pound                    */
/*                        Baby make me make that sound                        */
/*                Aaah, aaah, aaah, aaah, aaaaaaaaaaaaaaaaaah!                */
#include<stdio.h>

int ar[20];

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &ar[i]);
  }
  int ans = 0;
  for (int i = 1; i < n-1; i++) {
    if (ar[i-1] > ar[i] && ar[i] > ar[i+1]) ans++;
    if (ar[i-1] < ar[i] && ar[i] < ar[i+1]) ans++;
  }
  printf("%d\n", ans);
  return 0;
}

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

using namespace std;

typedef long long           ll;
typedef vector<int>         vi;
typedef pair<int,int>       ii;

#define endl                '\n'
#define ln                  puts("")
#define fi                  first
#define pf                  printf
#define se                  second
#define MX                  109
#define pb                  push_back
#define DB                  pf("Hi\n")
#define pf1(a)              pf("%d\n",a)
#define sc1(a)              scanf("%d",&a)
#define sz(a)               int((a).size())
#define all(c)              (c).begin(),(c).end()
#define mem(a,b)            memset(a, b, sizeof(a))
#define TC                  int _T;sc1(_T);while(_T--)
#define RD                  freopen("0iuput.txt","r",stdin)
#define WR                  freopen("0uput.txt","w",stdout)
#define rep(i,a,b)          for(int i=int(a)-(a>b);i!=(b)-(a>b);i+=1-2*(a>b))

int main()
{
   string s1,s2,s3;

   cin>>s1>>s2>>s3;

   if(s1[s1.size()-1]==s2[0] and s2[s2.size()-1]==s3[0])
        pf("YES");
   else
    pf("NO");
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define RFOR(i, a, b) for (int i = (a); i >= (b); i--)
#define LFOR(i, a, b) for (long long int i = (a); i <= (b); i++)
#define LRFOR(i, a, b) for (long long int i = (a); i >= (b); i--)
#define MOD 1000000007
#define INF 1000000000           // 2000000000
#define LINF 1000000000000000000 // 9000000000000000000
#define DINF 1000000000000000.0
#define PI 3.14159265358979

//.size()はunsigned int　0-1をするとオーバーフローする

using namespace std;
typedef long long int ll;
typedef pair<long long int, long long int> P;

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

int main(void) {
    int a,b;

    cin>>a>>b;

    if(a<=9&&b<=9){
        cout<<a*b<<endl;
    }else{
        cout<<-1<<endl;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define all(a) (a).begin(),(a).end()

using namespace std;

int main(int argc, char const *argv[]) {
  string N;
  string turnN;
  std::cin >> N;
  int leng=N.size();
  for (size_t i = leng-1,j=0; j<leng ; --i,++j) {
    turnN.push_back(N[i]);
  }
  if(turnN==N){
    printf("Yes\n");
  }else{
    printf("No\n");
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  vector<long long> a(N);
  for (int i=0;i<N;i++){
    cin >> a[i];
  }
  vector<long long> b(N),c(N);
  long long count1=0,count2=0;
  if (a[0]<=0){
    b[0]=1;
    count1+=1-a[0];
    if (a[0]==0){
      c[0]=-1;
      count2++;
    }
    else {
      c[0]=a[0];
    }
  }
  if (a[0]>0){
    c[0]=-1;
    count2+=a[0]+1;
    b[0]=a[0];
  }
  for (int i=1;i<N;i++){
    if (b[i-1]<0&&b[i-1]+a[i]<=0){
      count1+=1-(b[i-1]+a[i]);
      b[i]=1;
    }
    else if (b[i-1]>0&&b[i-1]+a[i]>=0){
      count1+=(b[i-1]+a[i])+1;
      b[i]=-1;
    }
    else {
      b[i]=b[i-1]+a[i];
    }
    if (c[i-1]<0&&c[i-1]+a[i]<=0){
      count2+=1-(c[i-1]+a[i]);
      c[i]=1;
    }
    else if (c[i-1]>0&&c[i-1]+a[i]>=0){
      count2+=(c[i-1]+a[i])+1;
      c[i]=-1;
    }
    else {
      c[i]=c[i-1]+a[i];
    }
  }
  long long ans=min(count1,count2);
  cout << ans << endl;
}

Measured memory_bytes: 2560
from bisect import bisect_left,bisect_right,insort_left

dict = {}
keytbl =[]
q = int(input())
for i in range(q):
    a = list(input().split())
    ki = a[1]
    if a[0] == "0":
        if ki not in dict:
            insort_left(keytbl,ki)
        dict[ki] = int(a[2])
    elif a[0] == "1":
        print(dict[ki] if ki in dict else 0)
    elif a[0] == "2":
        if ki in dict: dict[ki] = 0
    else:
        L =bisect_left(keytbl,a[1])
        R = bisect_right(keytbl,a[2],L)
        for j in range(L,R):
            if dict[keytbl[j]] > 0:
                print(keytbl[j],dict[keytbl[j]])



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

int main(){
	int N;
	cin >> N;
	int a[N+1];
	rep(i,N) cin >> a[i+1];

	int ans = 0;
	for (int i = 1; i <= N; i++) {
		if (a[a[i]] == i) ans++;	
	}
	ans /= 2;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3984
import java.util.*;

public class Main {
    public static void main(String[] args){
    
    Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
  
        int all = 0;
        for(int i=0; i<M; i++){
            all += sc.nextInt();
        } 
        if(all>N){
            System.out.println("-1");
        }else{
            System.out.println(N-all);
        }
    }
}

Measured memory_bytes: 46004
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
  int N; cin >> N;
  string str = "";
  while (N != 0) {
	/* N を 2 で割ったあまりを求める */
	int r = N % 2;
	if (r < 0) r += 2; // N がマイナスだと r がマイナスになったりするので 2 を足す

	/* N から余りを取り除いて -2 で割る */
	N = (N - r) / (-2);

	/* 答えに追加 */
	str += (char)('0' + r);
  }
  /* 向きが逆なので反転 */
  reverse(str.begin(), str.end());
  if (str == "") str = "0"; // N = 0 のときは空文字列になってしまうので例外処理
  cout << str << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long long a[100005];
long long b[100005];
int main()
{
	int n;
	long long cnt=0;
	scanf("%d",&n); 
	for(int i=0;i<n+1;i++){
		scanf("%lld",&a[i]);
	}
	for(int i=0;i<n;i++){
		scanf("%lld",&b[i]);
	}
	for(int i=0;i<n;i++){
		if(b[i]>a[i]){
			if(a[i+1]-(b[i]-a[i])>0){
				cnt+=b[i];
				a[i+1]-=(b[i]-a[i]);
			}
			else {
				cnt+=a[i+1]+a[i];
				a[i+1]=0;
			}
		}
		else{
			cnt+=b[i];
		}
	}
	printf("%lld\n",cnt);
	return 0;
}

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

long long n,L,a[100005],last=0,ansl,ansr,l=0,r,sum[100005];

int main(){
	cin>>n>>L;sum[0]=0;ansl=0,ansr=n;
	for(int i=1;i<=n;i++)cin>>a[i],sum[i]=sum[i-1]+a[i];
	//找到一段最小的区间,使得l---R>=L 
	for(r=1;r<=n;r++){
		while(sum[r]-sum[l+1]>=L)l++;
		if(r-l<ansr-ansl&&sum[r]-sum[l]>=L){
			ansr=r;
			ansl=l;
		}
	}
	//r----l+2内大于L
	if((sum[ansr]-sum[ansl]<L)||(sum[n]<L)){
		cout<<"Impossible"<<endl;
		exit(0);
	} 
	ansl++;//
	l=ansl,r=ansr;
	if(r-l+1<=2){
		cout<<"Possible"<<endl;
		for(int i=1;i<l;i++)cout<<i<<endl;
		for(int i=n-1;i>=r;i--)cout<<i<<endl;
		if(r-l+1==2)cout<<l<<endl;
	}
	else cout<<"Impossible"<<endl;
}

Measured memory_bytes: 2432
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int count = 0;
  int A,B,C;
  cin >> A >> B >> C;
  
  while (A <= B) {
   
    if (C <= count) {
      break;
    }
    
    B -= A;
    count++;
  }
  
  cout << count << endl;
}

Measured memory_bytes: 256
fun main(args: Array<String>) {
    val (n, k) = readLine()!!.split(" ").map(String::toLong)
    val ab = mutableListOf<Pair<Long, Long>>()
    for (i in 0 until n.toInt()) {
        val (a, b) = readLine()!!.split(" ").map(String::toLong)
        ab.add(Pair(a, b))
    }
    ab.sortBy { it.first }

    var bSum = 0L
    for (i in 0 until n.toInt()) {
        bSum += ab[i].second
        if (bSum >= k) {
            println(ab[i].first)
            return
        }
    }
}


Measured memory_bytes: 85204
#include <bits/stdc++.h>
using namespace std;
#define rep0(i,n) for(ll (i) = 0; (i) < (n); ++(i))
#define rrep0(i,n) for(ll (i) = (n) - 1; (i) >= 0; --(i))
#define rep1(i,n) for(ll (i) = 1; (i) <= (n); ++(i))
#define rrep1(i,n) for(ll (i) = (n); (i) >= 1; --(i))
#define nfor(i,a,b) for(ll (i) = (a); (i) < (b); ++(i))
#define rfor(i,a,b) for(ll (i) = (a); (i) > (b); --(i))
#define ll long long
#define mod (1000000007)
#define YES cout << "YES" << endl;
#define Yes cout << "Yes" << endl;
#define yes cout << "yes" << endl;
#define NO cout << "NO" << endl;
#define No cout << "No" << endl;
#define no cout << "no" << endl;
#define all(x) (x).begin(),(x).end()

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

ll lcm(ll a,ll b){
    ll g = gcd(a,b);
    return a / g * b;
}

ll fac(ll n){
    ll t = 1;
    rep1(i, n + 1)t *= i;
    return t;
}

int main()
{
    double n;
    cin >> n;
    vector<double> v(n);
    rep0(i, n)cin >> v[i];
    sort(all(v));
    rep0(i, n - 1){
        v[i + 1] = (v[i] + v[i + 1]) / 2;
    }
    cout << v[n - 1] << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define X first
#define Y second
#define pb emplace_back
#define FOR(i,a,b) for(int (i)=(a);i<(b);++(i))
#define EFOR(i,a,b) for(int (i)=(a);i<=(b);++(i))
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define rreps(X,S,Y) for (int (X) = (Y)-1;(X) >= (S);--(X))
#define all(X) (X).begin(),(X).end()
#define rall(X) (X).rbegin(),(X).rend()
#define eb emplace_back
#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef ll LL;
typedef pii PII;
typedef pll PLL;
template<class T> using vv=vector<vector<T>>;
template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;}
template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;}
const ll MOD=1e9+7;

int N;
int M;
int Q;
int C[114514];
int U[114514];
int V[114514];
int argm[114514][11][11];

int main() {
  scanf("%d%d", &N, &M);
  rep(i, M) {
    scanf("%d%d", &U[i], &V[i]);
    --U[i];
    --V[i];
  }

  fill(argm[0][0], argm[N][0], -1);

  scanf("%d", &Q);
  rep(i, Q) {
    int v, d;
    scanf("%d%d%d", &v, &d, &C[i]);
    --v;
    argm[v][d][0] = i;
  }

  rep(_, 11) {
    rep(i, M) {
      int u = U[i];
      int v = V[i];

      rep(j, 11) {
        rep(k, j) {
          MX(argm[v][j][k+1], argm[u][j][k]);
          MX(argm[u][j][k+1], argm[v][j][k]);
        }
      }
    }
  }

  rep(v, N) {
    int ci = -1;
    rep(j, 11) {
      rep(k, j+1) {
        MX(ci, argm[v][j][k]);
      }
    }
    
    if (ci == -1) {
      puts("0");
    } else {
      printf("%d\n", C[ci]);
    }
  }
}


Measured memory_bytes: 51968
#pragma gcc optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(V) (V).begin(),(V).end()
#define SORT(V) sort(ALL(V)) //小さい方からソート
#define REV(V) reverse(ALL(V)) //リバース
#define RSORT(V) SORT(V);REV(V) //大きい方からソート
#define NPN(V) next_permutation(ALL(V)) //順列
#define pb(n) push_back(n)
#define endl '\n'
#define Endl '\n'
#define DUMP(x)  cout << #x << " = " << (x) << endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define yes(n) cout << ((n) ? "yes" : "no"  ) << endl
#define Yay(n) cout << ((n) ? "Yay!": ":(") << endl
#define RAPID cin.tie(0);ios::sync_with_stdio(false)
#define VSUM(V) accumulate(ALL(V), 0)
#define MID(a,b,c) (a) < (b) && (b) < (c)
#define MIDe(a,b,c) (a) <= (b) && (b) <= (c)
#define IN(n) cin >> n
#define IN2(a,b) cin >> a >> b
#define IN3(a,b,c) cin >> a >> b >> c 
#define IN4(a,b,c,d) cin >> a >> b >> c >> d
#define VIN(V) for(int i = 0; i < (V).size(); i++) {cin >> (V).at(i);}
#define OUT(n) cout << n << endl
#define VOUT(V) REP(i, (V).size()) {cout << (V)[i] << endl;}
#define VOUT2(V) REP(i, (V).size()) {cout << (V)[i] << " ";} cout<<endl;
#define FIX cout << fixed << setprecision(15)

// 型マクロ定義
#define int long long
#define P pair<ll,ll>
#define Vi vector<ll>
#define VVi vector<vector<ll>>
#define Vd vector<double>
#define Vb vector<bool>
#define Vs vector<string>
#define Vc vector<char>
#define M map<ll,ll>
#define S set<ll>
#define PQ priority_queue<ll>
#define PQG priority_queue<ll,V,greater<ll>
//

template<class T> inline bool chmin(T& a, T b) {if(a>b){a=b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if(a<b){a=b;return true;}return false;}

using ll = long long;
using Graph = vector<vector<int>>;

const int MOD = 1000000007;
const int INF = 1061109567;
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int gcd(int a,int b){return b != 0 ? gcd(b, a % b) : a;} //最大公約数
int lcm(int a, int b){return a * b / gcd(a, b);}
string toStrUp(string str){char diff = 'A'-'a';REP(i,str.size()) str[i] += diff;return str;}
string gCh(string str, int key){return str.substr(key,1);}

int modfactNM(int n, int m){
  int ans = 1;
  FOR(i,1,n+1){
    ans *= i;
    ans %= MOD;
  }
  FOR(i,1,m+1){
    ans *= i;
    ans %= MOD;
  }
  return ans;
}

signed main() {
  RAPID;
  // デフォルト変数定義
  int n=0,m=0,a=0,b=0,c=0,d=0,x=0,y=0,z=0;
  string s="",t="";
  //

  // ここから
  IN2(n,m);
  if(abs(n-m) > 1) {
    OUT(0);
    return 0;
  }
  if(n == m) {
    OUT((modfactNM(n,m)*2)%MOD);
  } else {
    OUT(modfactNM(n,m)%MOD);
  }
}

Measured memory_bytes: 256
let () = Scanf.scanf "%d\n" @@ fun n ->
  let as_ = Array.init n @@ fun _ -> Scanf.scanf "%d " @@ fun a -> a - 1 in
  Printf.printf "%d\n" @@ (fun n -> n / 2) @@
    Array.fold_left ( + ) 0 @@
    Array.init n @@ fun i -> if as_.(as_.(i)) = i then 1 else 0


Measured memory_bytes: 6144
#include<iostream>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>

using namespace std;

//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2340

#define int long long
#define rep(i,n) for(int i = 0; i < (n); i++)
#define INF ((long long)1e18)
#define MOD ((int)1e9+7)
#define endl "\n"

#define yn(f) ((f)?"Yes":"No")
#define YN(f) ((f)?"YES":"NO")

#define MAX

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);
	
	int q;
	int p, n;
	char c;
	int con1 = 0, con2 = 0;
	
	cin>>q;
	
	for(int i = 0; i < q; i++){
		cin>>p>>c>>n;
		if(c == '(') con1 += n;
		else con2 += n;
		
		cout<<yn(con1 == con2)<<endl;
	}
	
	
	return 0;
}


Measured memory_bytes: 3232
#![allow(unused_imports)]
use std::collections::HashMap;
use std::collections::HashSet;
use std::collections::VecDeque;
use std::collections::BinaryHeap;

#[allow(unused_macros)]
macro_rules! read {
    ([$t:ty] ; $n:expr) =>
        ((0..$n).map(|_| read!([$t])).collect::<Vec<_>>());
    ($($t:ty),+ ; $n:expr) =>
        ((0..$n).map(|_| read!($($t),+)).collect::<Vec<_>>());
    ([$t:ty]) =>
        (rl().split_whitespace().map(|w| w.parse().unwrap()).collect::<Vec<$t>>());
    ($t:ty) =>
        (rl().parse::<$t>().unwrap());
    ($($t:ty),*) => {{
        let buf = rl();
        let mut w = buf.split_whitespace();
        ($(w.next().unwrap().parse::<$t>().unwrap()),*)
    }};
}

#[allow(dead_code)]
fn rl() -> String {
    let mut buf = String::new();
    std::io::stdin().read_line(&mut buf).unwrap();
    buf.trim_end().to_owned()
}

trait IteratorExt: Iterator + Sized {
    fn vec(self) -> Vec<Self::Item> {
        self.collect()
    }
}
impl<T: Iterator> IteratorExt for T {}

fn main() {
    let _n = read!(usize);
    let a = read!([usize]);

    let mut dp = vec![0; *a.iter().max().unwrap()+1];

    for e in &a {
        for i in 1..=(dp.len()-1)/e {
            dp[i*e] += 1;
        }
    }

    let mut ans = 0;
    for &e in &a {
        if dp[e] == 1 {
            ans += 1;
        }
    }
    println!("{}", ans);
}



Measured memory_bytes: 8284
import java.util.Scanner;

public class Main {

	private static final long x = (long) Math.pow(10, 18);

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();

		System.out.println(s.lastIndexOf('Z') - s.indexOf('A') + 1);

		sc.close();
	}

}


Measured memory_bytes: 40128
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int x,a,b;
    cin >> x >> a >> b;
  	string ans;
  	if(b-a<=0) cout << "delicious" << endl;
  	else if(x>=b-a) cout << "safe" << endl;
  	else cout << "dangerous" << endl;
    return 0;
}

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

using namespace std;

int main(void){
    int n, k;
    cin >> n >> k;
    vector<int> h(n);
    vector<long long int> cost(n, -1);

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

    cost[0] = 0;
    cost[1] = abs(h[1] - h[0]);
    for(int i = 2;i < n;i++){
        for(int j = 1;j < k+1 && i-j > -1;j++){
            if(cost[i] == -1){
                cost[i] = abs(h[i] - h[i-j]) + cost[i-j];
            }else{
                cost[i] = min(cost[i], abs(h[i] - h[i-j]) + cost[i-j]);
            }
        }
    }

    cout << cost[n-1] << endl;

    return 0;
}

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

int main() {
  int H, W;
  cin >> H >> W;
  
  vector<string> A(H);
  for (int i = 0; i < H; i++) {
    cin >> A.at(i);
  }
  
  string sharp = "";
  for (int i = 0; i < W + 2; i++) {
    sharp += '#';
  }
  
  cout << sharp << endl;
  
  for (int i = 0; i < H; i++) {
    cout << '#' << A.at(i) << '#' << endl;
  }
  
  cout << sharp << endl;
  
}


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

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

#define boost ios::sync_with_stdio(0); cin.tie(0);
#define int long long

const int N = 100 + 10;
const int MOD = 1e9 + 7;


int a[N][N];
int h , w , n;
int32_t main(){
    boost;
    //code
    
    string s;

    cin >> s;

    int i = 0 , b = 0 , w = 0;
    int n = s.length();

    while(i < n){
    	int j = i+1;
    	if(s[i] == 'B'){
    		b++;
    	}
    	else{
    		w++;
    	}
    	while(j < n and s[j] == s[i]){
    		j++;
    	}

    	i = j;
    }

    if(b == 0 or w == 0){
    	cout << 0;
    }
    else{
    	cout << b+w-1;
    }
    return 0;
}

Measured memory_bytes: 512