akhauriyash/Code-Regression huggingface dataset:
/*
AuThOr Gwj
*/
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define KEEP while(1)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define debug_pair(A) cerr<<A.FIR<<" "<<A.SEC<<endl;
using namespace std;
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
typedef pair<mp,mp> superpair;
int main(){
	fastio;
	int dis;
	int a,b,v,w;
	int t;
	cin>>a>>v>>b>>w>>t;
	dis=abs(a-b);
	if(w>=v){
		cout<<"NO"<<endl;
	}
	else{
		v-=w;
		if((LL)(v)*(LL)(t)>=(LL)dis){
			cout<<"YES"<<endl;
		}
		else{
			cout<<"NO"<<endl;
		}
	}
	return 0;
}


Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
int main(void){
    // Your code here!
    int N,K,count,ans;
    cin>>N>>K;
    int d[K];
    ans=0;
    int A[K][N];
    for(int i=0;i<K;i++){
        cin>>d[i];
        for(int j=0;j<d[i];j++){
            cin>>A[i][j];
        }
    }
    for(int h=1;h<=N;h++){
        count=0;
        for(int i=0;i<K;i++){
            for(int j=0;j<d[i];j++){
                if(h==A[i][j]){
                    count++;
                }
            }
        }
        if(count==0){
            ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 3672
// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<unordered_map>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define FOR(i,a) for(auto i:a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define show1d(v) rep(_,v.size())cout<<" "<<v[_];cout<<endl;
#define show2d(v) rep(_,v.size()){rep(__,v[_].size())cout<<" "<<v[_][__];cout<<endl;}cout<<endl;
using namespace std;
//kaewasuretyuui
typedef long long ll;
//#define int ll
typedef ll Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
// #define mt make_tuple
// typedef tuple<int,int,int> tp;
// typedef vector<tp> vt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
//template<class C>constexpr int size(const C &c){return (int)c.size();}
//template<class T,size_t N> constexpr int size(const T (&xs)[N])noexcept{return (int)N;}
const double PI=acos(-1);
const double EPS=1e-9;
Def inf = sizeof(Def) == sizeof(long long) ? 1e18+10 : 1e9+10;
// int dx[]={0,1,0,-1,1,1,-1,-1};
// int dy[]={1,0,-1,0,1,-1,1,-1};//RDLU
int dx[]={-1,-1,0,0,1,1};
int dy[]={-1,0,-1,1,0,1};//RDLU
int main(){
	int n,m;
	cin>>n>>m;
	if(n+m==15)cout<<"+"<<endl;
	else if(n*m==15)cout<<"*"<<endl;
	else cout<<"x"<<endl;
}
	








Measured memory_bytes: 256
/***************************************** START OF TEMPLATE *********************************************/
#pragma optimization_level 3
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#include<bits/stdc++.h>

using namespace std;

#define  SPEED          ios:: sync_with_stdio(0);cin.tie(0);cout.tie(0);cout<<fixed;cout<<setprecision(10);
#define  randomINIT     mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define  foo(i,a,n)     for(ll i = (a); i <= n; i++)
#define  frr(i,a,n)     for(ll i = (a); i >= n; i--)
#define  fo(i,n)        for(ll i = 0; i < n; i++)
#define  newl           cout<<"\n";
#define  f              first
#define  s              second
#define  pb             push_back
#define  mp             make_pair
#define  sym(s)         s="#"+s+"#";   
#define  all(x)         (x).begin(),(x).end()
#define  alll(x, n)     x+1, x+n+1
#define  mset(x,val)    memset(x,val,sizeof(x))
#define  mset1d(a,n,v)  foo(i,0,n+5)a[i]=v;
#define  mset2d(a,n,m,v)foo(i,0,n+5)foo(j,0,m+5)a[i][j]=v;
#define  INP(a,n)       foo(i,1,n) cin>>a[i];
#define  deb1d(a,n)     foo(i,1,n)cout<<a[i]<<" ";newl;
#define  deb2d(a,n,m)   foo(i,1,n){foo(j,1,m){cout<<a[i][j]<<" ";}newl;}    
#define  debm(a)        for(auto it: a)cout<<"{"<<it.f<<","<<it.s<<"}, ";newl;
#define  debp(a,n)      foo(i,1,n)cout<<"{"<<a[i].f<<","<<a[i].s<<"}, ";newl;
#define  debv(a)        for(auto it: a)cout<<it<<" ";newl;
#define  deb1(a)        cout<<a<<" ";newl;
#define  deb2(a,b)      cout<<a<<" "<<b<<" ";newl;
#define  deb3(a,b,c)    cout<<a<<" "<<b<<" "<<c<<" ";newl;
#define  deb4(a,b,c,d)  cout<<a<<" "<<b<<" "<<c<<" "<<d;newl;
#define  ll             long long
#define  ld             long double
#define  pll            pair<ll,ll>
#define  vll            vector<ll>
#define  vpll           vector<pll>

const ld   PI    =  3.14159265358979323846; 
const ll   MOD   =  1e+9+7;
const ll   INF   =  LLONG_MAX;
const int  INFi  =  INT_MAX;
const ll   N     =  2e+5+8;

vll adj[N]; ll vis[N];
ll dx4[]={0,1,0,-1}, dy4[]={1,0,-1,0};

ll test_cases = 1; randomINIT;

/*********************************************************************************************************/
/***************************************** VARIABLE DECLARATIONS *****************************************/
ll n, q, a[N], f[N],b,c;


/***************************************** FUNCTION IMPLEMENTATIONS **************************************/



/***************************************** START OF MAIN FUNCTION ****************************************/
void MAIN(ll tc){
    ll sum =0;
    cin>>n;
    foo(i,1,n){
        cin>>a[i];
        f[a[i]]++;
        sum+=a[i];
    }
    cin>>q;
    foo(i,1,q){
        cin>>b>>c;
        sum-=f[b]*b;
        sum+=f[b]*c;
        f[c]+=f[b];
        f[b]=0;
        cout<<sum;newl;
    }
}

int main(){
    SPEED;

    //cin>>test_cases;
    foo(i,1,test_cases){
    MAIN(i);
    }
}

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

using namespace std;

string UOP(string str){
  string ans;
  if('a' <= str[0] && str[0] <= 'z') str[0] = toupper(str[0]);
  for(int i = 0 ; i < str.size() ; i++){
    if(str[i] == '_'){
      if('a' <= str[i+1] && str[i+1] <= 'z') str[i+1] = toupper(str[i+1]);
    }
    else ans += str[i];
  }
  return ans;
}

string LOP(string str){
  string ans;
  if('A' <= str[0] && str[0] <= 'Z') str[0] = tolower(str[0]);
  for(int i = 0 ; i < str.size() ; i++){
    if(str[i] == '_'){
      if('a' <= str[i+1] && str[i+1] <= 'z') str[i+1] = toupper(str[i+1]);
    }
    else ans += str[i];
  }
  return ans;
}

string DOP(string str){
  string ans;
  for(int i = 0 ; i < str.size() ; i++){
    if('A' <= str[i] && str[i] <= 'Z') str[i] = tolower(str[i]);
    ans += str[i];
    if('A' <= str[i+1] && str[i+1] <= 'Z') ans += '_';
  }
  return ans;
}

int main(){
  string str;
  char op;
  while(cin >> str >> op, op != 'X'){
    if(op == 'U'){
      cout << UOP(str) << endl;
    }
    else if(op == 'L'){
      cout << LOP(str) << endl;
    }
    else if(op == 'D'){
      cout << DOP(str) << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 0
class Graph(): #non-directed
    def __init__(self,n,edge):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.deg = [0 for _ in range(n)]
        for e in edge:
            self.graph[e[0]].append(e[1])
            self.graph[e[1]].append(e[0])
            self.deg[e[0]] += 1
            self.deg[e[1]] += 1

    def lowlink(self): #DFS木, ord, lowを計算
        self.ord = [None for _ in range(self.n)]
        self.low = [None for _ in range(self.n)]
        self.group = [None for _ in range(self.n)]
        self.prev = [None for _ in range(self.n)]
        self.tree = [[] for _ in range(self.n)]
        self.sorted = []
        order = 0
        count = 0
        low = [None for _ in range(self.n)]
        for s in range(self.n):
            if self.group[s] is None:
                stack = [(s, None)]
                while stack:
                    node, par = stack.pop()
                    if self.group[node] is None:
                        self.group[node] = count
                        self.ord[node] = order
                        self.sorted.append(node)
                        order += 1
                        if par is not None:
                            self.prev[node] = par
                            self.tree[par].append(node)
                        for adj in self.graph[node]:
                            if self.group[adj] is None:
                                stack.append((adj, node))
                count += 1
        for node in self.sorted[::-1]:
            self.low[node] = self.ord[node]
            for adj in self.graph[node]:
                if self.prev[adj]  == node:
                    self.low[node] = min(self.low[node], self.low[adj])
                elif self.prev[node] == adj:
                    continue
                else:
                    self.low[node] = min(self.low[node], self.ord[adj])

    def articulation(self):
        res = []
        for node in range(self.n):
            if self.prev[node] is None and len(self.tree[node]) > 1:
                res.append(node)
            if self.prev[node] is not None:
                for adj in self.tree[node]:
                    if self.ord[node] <= self.low[adj]:
                        res.append(node)
                        break
        return res

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
E = [tuple(map(int, input().split())) for _ in range(M)]

g = Graph(N, E)
g.lowlink()
res = g.articulation()
if res:
    print('\n'.join(map(str, res)))


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

typedef unsigned long long ull;

#define loop(i,a,b) for(int i=(a);i<ull(b);++i)
#define rep(i,n) loop(i,0,n)

map<string, int> m;


string IntToString(int number) {
    stringstream ss;
    ss << number;
    return ss.str();
}

int sti(string input){
    int num = 0;
    for(int i=0; i < input.size(); i++){
        const char *c = input.substr(i, 1).c_str();
        if(isalpha(*c)){
            num += m[input.substr(i,1)];
        }
        else {
            int a = atoi(input.substr(i, 1).c_str());
            num += a*m[input.substr(i+1,1)];
            i++;
        }
    }
    return num;
}

string its(int num){
    string r;
    if(num / 1000){
        if(num / 1000 == 1) r += "m";
        else r += IntToString(num/1000) + "m";
        num = num % 1000;
    }
    if(num / 100){
        if(num / 100 == 1) r += "c";
        else r += IntToString(num/100) + "c";
        num = num % 100;
    }
    if(num / 10){
        if(num / 10 == 1) r += "x";
        else r += IntToString(num/10) + "x";
        num = num % 10;
    }
    if(num / 1){
        if(num / 1 == 1) r += "i";
        else r += IntToString(num) + "i";
    }
    return r;
}

int main(){
    int n;
    cin >> n;
    m["m"] = 1000; m["c"] = 100; m["x"] = 10; m["i"] = 1;
    rep(p, n){
        string s1, s2;
        cin >> s1 >> s2;
        cout << its(sti(s1)+sti(s2)) << endl;
    }
}

Measured memory_bytes: 1244
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
int n;
set<int>S;
main()
{
  cin>>n;
  for(int i=0;i<n;i++)
  {
    int c,x;cin>>c>>x;
    if(c)cout<<(S.find(x)!=S.end())<<endl;
    else S.insert(x),cout<<S.size()<<endl;
  }
}



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


int main() {
  int x,y,a,b,c;
  cin >> x >> y >> a >> b >> c;
  vector<ll> p(a);
  vector<ll> q(b);
  vector<ll> r(c);
  rep(i,a) cin >> p[i];
  rep(i,b) cin >> q[i];
  rep(i,c) cin >> r[i];
  sort(p.begin(),p.end());
  sort(q.begin(),q.end());
  sort(r.begin(),r.end());
  reverse(p.begin(),p.end());
  reverse(q.begin(),q.end());
  reverse(r.begin(),r.end());
  ll ans=0;
  rep(i,x) ans+=p[i];
  rep(i,y) ans+=q[i];
  int ri=0;
  int pi=x-1;
  int qi=y-1;
  while(1) {
    if(ri>c-1) break;
    if(pi<0 && qi <0) break;
    if(pi>=0 && qi>=0) {
      int d=min(p[pi],q[qi]);
      if(r[ri]>d) {
        ans+=r[ri]-d;
       
        ri++;
        if(p[pi]>q[qi]) qi--;
        else pi--;
      }
      else break;
    }
    else if(pi<0) {
      if(r[ri]>q[qi]) {
        ans+=r[ri]-q[qi];
        ri++;
        qi--;
      }
      else break;
    }
    else if(qi<0) {
      if(r[ri]>p[pi]) {
        ans+=r[ri]-p[pi];
        ri++;
        pi--;
      }
      else break;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 2560
import java.util.*;
import java.io.PrintWriter;
public class Main{
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		TreeMap<Integer,Boolean> map=new TreeMap<>();
		for(int i=0; i<n; i++){
			int a=sc.nextInt();
			if(map.containsKey(a)){
				map.put(a,true);
			}else{
				map.put(a,false);
			}
		}
		boolean[] fur=new boolean[1000001];
		int ans=0;
		for(int i:map.keySet()){
			if(!fur[i]){
				int mul=1;
				while(1000000>=i*mul){
					fur[i*mul]=true;
					mul++;
				}
				if(!map.get(i)){
					ans++;
				}
			}
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 70976
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int N;
const int MAX_N = 1.0e5 + 100;
pair<int, int> ab[MAX_N];
vector<int> G[MAX_N];
map<pair<int,int>,int> mp;

void dfs(int u, int pre, int col, int k) {
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (v == pre) continue;
        col++;
        col %= k;
        if (u < v) mp[{u, v}] = col;
        else mp[{v, u}] = col; 
        dfs(v, u, col, k);
    }
}

int main() {
    cin >> N;
    for (int i = 0; i < N-1; i++) {
        int a, b;
        cin >> a >> b;
        ab[i] = {a, b};
        G[a].push_back(b);
        G[b].push_back(a);
    }

    int root;
    int K = 0;
    for (int i = 1; i <= N; i++) {
        if (K < G[i].size()) {
            K = G[i].size();
            root = i;
        }
    }

    dfs(root, -1, 0, K);

    cout << K << endl;
    for (int i = 0; i < N-1; i++) {
        cout << mp[ab[i]] + 1 << endl;
    }

    return 0;
}

Measured memory_bytes: 15872
#include <bits/stdc++.h>
using namespace std;
#define SZ(v) int((v).size())
#define fi first
#define se second
#define em emplace_back
#define ALL(a) a.begin(), a.end()
#define pb push_back
#define mk make_pair
typedef long long ll;
using pii = pair<int,int>;

template<typename T> inline bool uax(T &x, T y) {return (y > x) ? x = y, true : false;}
template<typename T> inline bool uin(T &x, T y) {return (y < x) ? x = y, true : false;}
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); \
  stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
string to_string(char c) { return "'" + string(1, c) + "'";}
string to_string(string s) { return '"' + s + '"';}
string to_string(const char* s) { return to_string((string) s);}
template<typename A> string to_string(A);
template<typename A, typename B> string to_string(pair<A, B> p){
  return "(" + to_string(p.first) + ": " + to_string(p.second) + ")";}
template<typename A> string to_string(A v) {bool f = false; string r = "{"; 
  for (auto x: v) {if (f) r += ", "; r += to_string(x); f = true;} return r += "}";}
template<typename A> string to_string(vector<vector<A>> v) {string r; 
  for (auto x: v) r += "\n" + to_string(x); return r;}
void err(istream_iterator<string>) { cerr << endl; }
template<typename T,typename... Args> void err(istream_iterator<string> it, T a, Args... args) {
  cerr << *it << " =: " << to_string(a) << "; "; err(++it, args...); }
template<typename T> void kek(T ans) {cout << ans << endl; exit(0);}
/*----------------------------------------------------------------------------------*/
int  mod = 1e9 + 7;
int const N = 200100;
typedef long long i64;
i64 INF = 1e18, NIN = -1 * INF;

/******************************/

int add(int a, int b){
  if(a + b >= mod)return a+ b - mod;
  return a + b;
}
int mul(int a, int b){
  return 1LL * a * b  % mod;
}
int power(int a, int b){
  int re = 1;
  while(b){
    if(b&1)re= mul(re, a);
    a = mul(a, a);
    b>>=1;
  }
  return re;
}

int fact[N], inv[N];

int ncr(int a, int b){
  if(a < 0 || b < 0 || a < b)return 0;
  return mul(fact[a], mul(inv[a-b], inv[b]));
}
int ncr(pii a){
  return ncr(a.fi, a.se);
}
void fac(){
  fact[1] = fact[0] = 1;
  for(int x =2; x<N; x++){
    fact[x] = mul(x, fact[x-1]);
  }
  inv[N-1] = power(fact[N-1], mod - 2);
  for(int x = N-2; x>= 0; x--){
    inv[x] = mul(x+1, inv[x+1]);
  }
}

void solve(){
  int k, n;
  cin >> k >> n;
  int ans = 0;
  vector<int> v(n);for(auto &y : v)cin >> y;
  for(int x = 0; x<n-1; x++){
    ans = max(ans, v[x+1] - v[x]);
  }
  ans = max(ans, k - v[n-1] + v[0]);
  cout << k - ans;
}

int32_t main() {
 
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);  int test = 1;
  // cin >> test;
  while(test--)solve();
}

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

vector<int> a;

int calc(int len,int x){
	return (((len+x-1)/x) - 1);
}

int solve(int x) {
	int ans = 0;
  	for(int i=0;i<a.size();i++){
    	ans += calc(a[i],x);
    }
  	return ans;
}

int main() {
	int n,k;
  
  	cin >> n >> k;
  
  	a.resize(n);
  	
  	for(int i=0;i<n;i++) {
    	cin >> a[i];
    }
  
  	int l = 1;
  	int r = *max_element(a.begin(),a.end());
  
  	while(l<r) {
    	int mid = (l+r)/2;
      	if(solve(mid) <= k){
        	r = mid;
        } else{
        	l = mid + 1;
        }
    }
  	
  	cout << l << endl;
  
  	return 0;
}

Measured memory_bytes: 3940
a=[int('0') for i in range(10)]
w=["#" for i in range(20)]
z=[]
for i in range(15):
    z+=[a]
    if i == 3 or i== 7 or i== 11:
        z+=[w]
x=[[[0 for i in range(10)] for k in range(3)] for j in range(4)]
n=int(input())
for i in range(n):
    b,f,r,v=map(int,input().split())
    x[b-1][f-1][r-1]+=v

for i in range(4):
    for k in range(3):
        print(" "+" ".join(str(x[i][k][o]) for o in range(10)))
    if i ==0 or i ==1 or i==2:
        print("#"*20)
    
    
        
    

    

Measured memory_bytes: 7768
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <iostream>
using namespace std;

int N, M;
const int MAX_N = 20;

struct Lab {
	double L;
	double a;
	double b;
};

Lab colors[MAX_N];

int main() {
	cin >> N >> M;
	for(int i=0; i<N; i++) {
		cin >> colors[i].L;
		cin >> colors[i].a;
		cin >> colors[i].b;
	}

	int limit = 1 << N;
	double ans = 0.0;
	for(int i=0; i<limit; i++) { // all select pattern
		vector<Lab> v;
		for(int j=0; j<N; j++) {
			if(i & (1<<j)) { // select i-th color
				v.push_back(colors[j]);
			}
		}

		if(v.size() != M) continue;

		double x = 0.0;
		for(vector<Lab>::const_iterator it = v.begin(); it != v.end(); ++ it) {
			for(vector<Lab>::const_iterator jt = it+1; jt != v.end(); ++jt) {
				double dL = (*it).L - (*jt).L;
				double da = (*it).a - (*jt).a;
				double db = (*it).b - (*jt).b;
				x += dL*dL + da*da + db*db;
			}
		}
		ans = max(ans, x);
	}
	printf("%.6f\n", ans);
	return 0;
}

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

int n;
long long a[100];
long long cnt = 1000;

int main()
{
	ios::sync_with_stdio(0);
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 1; i < n; i++)
		if(a[i] < a[i + 1]) cnt += (a[i + 1] - a[i]) * (cnt / a[i]);
	cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define REP(i,n) for(ll i=0;i<n;i++)
#define FOR(i,n1,n2) for(ll i=n1;i<n2;i++)
#define bFOR(i,n1,n2) for(ll i=n1;i>=n2;i--)
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
typedef long long int ll;
typedef pair<ll,ll> Pi;
typedef tuple<ll,ll,ll> Tu;
const int INF=(ll)(1LL<<30)-1;
const double INFd=100000000000.0;
const double PI=3.14151926535;
const ll INFl=(ll)9223372036854775807;
const int MAX=10000;
const ll MOD=(ll)1e9+7;
const ll tMOD=(ll)998244353;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a, b)*b;}
int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};
int mdx[8]={0,1,0,-1,1,1,-1,-1},mdy[8]={-1,0,1,0,1,-1,1,-1};


template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

int pri[1300000]={};
int pril[1300000];
int prih[1300000];
vector<ll> prime;
int main(){
    prime.push_back(2);
    pri[2]=1;
    for(int i=3;i<1300000;i++){
        int flag=1;
        for(int j=0;j<prime.size()&&prime[j]*prime[j]<=i;j++){
            if(i%prime[j]==0){
                flag=0;break;
            }
        }
        if(flag){
            prime.push_back(i);pri[i]=1;
        }
    }
    int t=2;
    for(int i=2;i<1300000;i++){
        if(pri[i])t=i;
        pril[i]=t;
    }
    for(int i=1299999;i>=2;i--){
        if(pri[i])t=i;
        prih[i]=t;
    }
    while(true){
        int n;
        cin>>n;
        if(n==0)break;
        cout<<prih[n]-pril[n]<<endl;
    }
    return 0;
}


Measured memory_bytes: 18684
def f(i, j)
    return nil if S[i] =~ /[(),]/

    if S[i] == ?0
        if i == j
            return 0
        else
            return nil
        end
    end

    if S[i] =~ /\d/
        if S[i..j] =~ /[LR,()]/
            return nil
        else
            return S[i..j].tr(??, ?9).to_i
        end
    end

    if S[i] == ?L
        return nil if j - i < 5
        return nil if S[i+1] !~ /[(?]/
        return nil if S[j] !~ /[)?]/
        return l(i+2, j-1)
    end

    if S[i] == ?R
        return nil if j - i < 5
        return nil if S[i+1] !~ /[(?]/
        return nil if S[j] !~ /[)?]/
        return r(i+2, j-1)
    end

    if S[i..j] !~ /[LR,()]/
        return S[i..j].tr(??, ?9).to_i
    end

    return nil if j - i < 5
    return nil if S[i+1] !~ /[(?]/
    return nil if S[j] !~ /[)?]/

    x(i+2, j-1)
end

def l(i, j)
    return nil if j - i <= 1
    max = - Float::INFINITY
    (j-1).downto(i+1) do |k|
        break if 10 ** (k - i) <= max
        next if S[k] !~ /[?,]/
        next if ! f(k+1, j)
        if t = f(i, k-1)
            max = t if t > max
        end
    end
    max >= 0 ? max : nil
end

def r(i, j)
    return nil if j - i <= 1
    max = - Float::INFINITY
    (i+1..j-1).each do |k|
        break if 10 ** (j - k) <= max
        next if S[k] !~ /[?,]/
        next if ! f(i, k-1)
        if t = f(k+1, j)
            max = t if t > max
        end
    end
    max >= 0 ? max : nil
end

def x(i, j)
    return nil if j - i <= 1
    max = - Float::INFINITY
    (i+1..j-1).each do |k|
        next if S[k] !~ /[?,]/
        if (a = f(i, k-1)) && (b = f(k+1, j))
            max = [max, a, b].max
        end
    end
    max >= 0 ? max : nil
end

module Memoizable
	def memoize(name)
		original = "__original_#{name}__"
		([Class, Module].include?(self.class) ? self : self.class).class_eval {
			alias_method(original, name)
			private(original)
			cache = {}
			define_method(name){|*args|
				cache[args] ||= send(original, *args)
			}
		}
	end
end
include Memoizable

memoize :f
memoize :l
memoize :r
memoize :x

S = gets.chomp
puts f(0, S.size-1) || 'invalid'

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

int main(void){
    long long int n, k;
    std::cin >> n >> k;
    long long int tmp;
    long long int ans;

        tmp = n / k;
        n = n - tmp * k;
        //std::cout << n << std::endl;
        double border = (double) k / 2;
        if(n > border){
            ans = -n + k;
        }else{
            ans = n;
        }

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i, a, b) for (int i = (a); i < int(b); ++i)
#define RFOR(i, a, b) for (int i = (b)-1; i >= int(a); --i)
#define rep(i, n) FOR(i, 0, n)
#define rep1(i, n) FOR(i, 1, int(n) + 1)
#define rrep(i, n) RFOR(i, 0, n)
#define rrep1(i, n) RFOR(i, 1, int(n) + 1)
#define all(c) begin(c), end(c)
const int MOD = 1000000007;

template <typename T>
void __dump__(std::ostream &os, const T &first) {
    os << first;
}
template <typename First, typename... Rest>
void __dump__(std::ostream &os, const First &first, const Rest &... rest) {
    os << first << ", ";
    __dump__(os, rest...);
}
#define dump(...)                                         \
    do {                                                  \
        std::ostringstream os;                            \
        os << __LINE__ << ":\t" << #__VA_ARGS__ << " = "; \
        __dump__(os, __VA_ARGS__);                        \
        std::cerr << os.str() << std::endl;               \
    } while (0)

int main() {
    int n;
    while (cin >> n) {
        vector<int> a(n);
        rep(i, n) cin >> a[i];
        a.erase(unique(all(a)), a.end());
        n = a.size();
        if (n < 3) cout << 1 << endl;
        else {
            int ans = 0;
            int i = 1;
            while (i + 1 < n) {
                bool f = a[i-1] < a[i];
                bool g = a[i] < a[i+1];
                if (f ^ g) {
                    ++ans;
                    i += 2;
                } else {
                    i += 1;
                }
            }
            cout << ans + 1 << endl;
        }
    }
}


Measured memory_bytes: 640
#include<stdio.h>
#define MAX 500000
#define SENTINEL 2000000000

int L[MAX/2+2];
int R[MAX/2+2];
int count;

void merge(int A[],int n,int left,int mid,int right){
  int n1=0,n2=0,i,j,k;
  n1=mid-left;
  n2=right-mid;
  for(i=0;i<n1;i++){
    L[i]=A[left+i];
  }
  for(i=0;i<n2;i++){
    R[i]=A[mid+i];
  }
  L[n1]=SENTINEL;
  R[n2]=SENTINEL;
  i=0;
  j=0;
  for(k=left;k<right;k++){
    count++;
    if(L[i]<+R[j]){
      A[k]=L[i++];
    }
    else{
      A[k]=R[j++];
    }
  }
}

void mergeSort(int A[],int n,int left,int right){
  int mid;
  if(left+1<right){
    mid=(left+right)/2;
    mergeSort(A,n,left,mid);
    mergeSort(A,n,mid,right);
    merge(A,n,left,mid,right);
  }
}

int main(){
  int n,i,A[MAX];
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&A[i]);
  }
  mergeSort(A,n,0,n);
  for(i=0;i<n;i++){
    if(i>0)printf(" ");
    printf("%d",A[i]);
  }
  printf("\n");
  printf("%d\n",count);
  return 0;
}



Measured memory_bytes: 5604
n,m=map(int,input().split())
a=[int(x) for x in input().split()]
b=[0 for x in range(n+1)]
l=list([0])

for i in range(1,n+1):
  b[i]=b[i-1]+a[i-1]

for i in range(1,n+1):
  l.append(b[i]%m)

d=list()
l.sort()
t,c=0,1
for i in range(1,n+1):
  if l[i]==l[i-1]:
    c+=1
  else:
    if c!=1:
      t += c*(c-1)//2
      c=1

if c!=1:
  t += c*(c-1)//2  

print(t)


Measured memory_bytes: 16072
import math
A, B, H, M = map(int, input().split())

minutes = H * 60 + M

choshin = (minutes * 6) % 360
tanshin = (minutes * 0.5) % 360

if choshin == tanshin:
    print(abs(B - A))
else:
    C = abs(choshin - tanshin)
    tmp = (A ** 2) + (B ** 2) - (2 * A * B * math.cos(math.radians(C)))
    print(math.sqrt(tmp))


Measured memory_bytes: 9564
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <utility>
#include <cmath>
#include <tuple>
#include <queue>
#include <bitset>
#include <set>
#include <map>
#include <list>

using namespace std;


void solve(long long N, long long K){
  N %= K;

  if (abs(N-K) < N) {
    N = abs(N-K);
  }

  cout << N << endl;
}

int main(){
  long long N;
  scanf("%lld",&N);
  long long K;
  scanf("%lld",&K);
  solve(N, K);
  return 0;
}


Measured memory_bytes: 256
#include<cstdio>
int d[100000],dp[100000];
int dist(int x,int y){return (x>y)?(x-y):(y-x);}
int min(int x,int y){return (x>y)?y:x;}
int max(int x,int y){return (x>y)?x:y;}
int main(){
  int n,k;
  scanf("%d%d",&n,&k);
  for(int i=0;i<n;i++)scanf("%d",&d[i]);
  for(int i=0;i<n;i++)dp[i]=1e9+7;
  dp[0]=0;
  for(int i=1;i<n;i++){
    for(int j=max(0,i-k);j<i;j++){
      dp[i]=min(dp[i],dp[j]+dist(d[i],d[j]));
    }
  }
  printf("%d",dp[n-1]);
  return 0;
}


Measured memory_bytes: 896
#include<stdio.h>

int main(void){

int  k,a,b;

scanf("%d",&k);scanf("%d",&a);scanf("%d",&b);

if(k==1){
  printf("OK");
}else if(a%k==0||b%k==0){
  printf("OK");
}else if(a/k==b/k){
printf("NG");
}else{
printf("OK");
}

return 0;
}

Measured memory_bytes: 2152
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>

#define REP(i, a, b) for (int i = int(a); i < int(b); i++)
using namespace std;
typedef long long int ll;

// clang-format off
#ifdef _DEBUG_
#define dump(...) do{ cerr << __LINE__ << ":\t" << #__VA_ARGS__ << " = "; PPPPP(__VA_ARGS__); cerr << endl; } while(false)
template<typename T> void PPPPP(T t) { cerr << t; }
template<typename T, typename... S> void PPPPP(T t, S... s) { cerr << t << ", "; PPPPP(s...); }
#else
#define dump(...)
#endif
template<typename T> vector<T> make_v(size_t a, T b) { return vector<T>(a, b); }
template<typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v(ts...))>(a, make_v(ts...)); }
template<typename T>
bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false;}
template<typename T>
bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false;}
// clang-format on

#include <utility>
using P = pair<int, int>;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll n, k;
    cin >> n >> k;
    vector<int> a(n);
    REP(i, 0, n) {
        cin >> a[i];
    }
    vector<int> next(n);

    {
        vector<int> combine(2 * n);
        REP(i, 0, n) {
            combine[i] = combine[i + n] = a[i];
        }
        vector<int> lst(200010, -1);
        for (int i = 2 * n - 1; i >= 0; i--) {
            if (i < n) {
                next[i] = lst[combine[i]];
            }
            lst[combine[i]] = i;
        }
    }

    int cnt = 0;
    int pos = 0;
    REP(i, 0, 2 * n) {
        int nxt = next[pos] + 1;
        dump(cnt, pos, nxt);
        if (nxt >= n) {
            cnt += nxt / n;
        }
        nxt %= n;
        if (nxt == 0) break;
        pos = nxt;
    }
    dump(cnt);
    k %= cnt;

    cnt = 0;
    pos = 0;
    vector<int> ans;
    REP(i, 0, 5 * n) {
        int nxt = next[pos] + 1;
        dump(cnt, pos, nxt);
        if (cnt + 1 == k) {
            if (nxt > n) {
                ans.push_back(a[pos]);
                pos = (pos + 1) % n;
            } else {
                pos = (nxt % n);
            }
            if (pos == 0) break;
        } else {
            if (nxt >= n) {
                cnt++;
            }
            pos = (nxt % n);
        }
    }
    REP(i, 0, ans.size()) {
        cout << ans[i] << " \n"[i + 1 == ans.size()];
    }

    return 0;
}


Measured memory_bytes: 4948
def minDistPoint(Student,List):
    ans_dist = 500000000
    res = 0
    for k,pos in List.items():
        dist = abs(Student[0]-pos[0])+abs(Student[1]-pos[1])
        if dist<ans_dist:
            ans_dist = dist
            res=k
    return res+1

N,M=map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]
CD = {i:list(map(int,input().split())) for i in range(M)}

cp = [0]*N

for i in range(len(AB)):
    cp[i] = minDistPoint(AB[i],CD)
    
for i in cp:
    print(i)

Measured memory_bytes: 9180
import math

n = int(input())

dp = [float('inf') for _ in range(n+1)]
dp[0] = 0
dp[1] = 1

for i in range(1,n+1):
    tmp = float('inf')
    tmp6, tmp9 = 1,1
    while tmp6 <= i:
        if dp[i-tmp6]+1 < tmp:
            tmp = dp[i-tmp6] + 1
        tmp6 *= 6
    while tmp9 <= i:
        if dp[i-tmp9] + 1 < tmp:
            tmp = dp[i-tmp9] + 1
        tmp9 *= 9
    dp[i] = tmp

'''
    for j in range(int(math.log(i,6))+1):
        if dp[i-6**j]+1 < tmp:
            tmp = dp[i-6**j] + 1
    for j in range(int(math.log(i,9))+1):
        if dp[i-9**j]+1 < tmp:
            tmp = dp[i-9**j]+1
'''
    #dp[i] = tmp

print(dp[n])

Measured memory_bytes: 6296
#include <bits/stdc++.h>
using namespace std;
main(){
  // ここにプログラムを追記
  int A,B,C;
  cin>> A >>B>>C;
  int X=100*A+10*B+C;
  if (X %4 ==0) cout <<"YES"<<endl;
               

else  cout<<"NO"<<endl;

}


Measured memory_bytes: 256
from collections import deque
n,q = map(int,input().split())
l = [[] for i in range(n+1)]
pts = [0]*(n+1)
for _ in range(n-1):
  a,b = map(int,input().split())
  l[a].append(b)
  l[b].append(a)
for _ in range(q):
  p,x = map(int,input().split())
  pts[p] += x
Q = deque()
Q.append(1)
ans = [0]*(n+1)
vst = [0]*(n+1)
while Q:
  temp = Q.popleft()
  for n in l[temp]:
    if vst[n]:
      continue
    ans[n] = ans[temp] + pts[temp]
    Q.append(n)
  ans[temp] += pts[temp]
  vst[temp] = 1
print(*ans[1:])

Measured memory_bytes: 64376
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
//#define rep(i,n) for(int i=0;i<(n);i++)
#define rep(i,n) for(int i=0;i<(n);i++)

typedef long long int lli;
typedef pair<lli,int> mp;

int n,m,st;
vector<mp> vs[100005];//グラフの情報を持つ
lli dist[100005];//距離を持つ

int main(void){
	scanf("%d%d%d",&n,&m,&st);
	rep(i,m){
		int a,b;
		lli c;
		scanf("%d%d%lld",&a,&b,&c);
		vs[a].push_back( mp(c,b) );
	}
	
	memset(dist,-1,sizeof(dist));//最初は、無限大で初期化
	
	priority_queue<mp,vector<mp>,greater<mp> > que;
	
	que.push(mp(0,st));//stには0で行ける
	
	while(!que.empty()){//queが空になるまでやる
		
		mp pa = que.top();
		que.pop();
		//queの先頭要素(一番軽いの)を取り出す。
		
		int no = pa.second;//今の頂点
		lli co = pa.first;//今の距離
		
		if(dist[no]!=-1)continue; //もし、すでに確定していたら、飛ばす
		
		dist[no] = co;//確定させる
		
		rep(i,vs[no].size()){//今の地点から出ているすべての辺の先について、キューに突っ込んでいく
			int to = vs[no][i].second;//次の頂点
			lli tc = co + vs[no][i].first;//次の距離
			
			if(dist[to]!=-1)continue; //もし、すでに確定していたら、飛ばす
			que.push( mp(tc,to) ); //queに追加
		}
	}
	//これで、全ての頂点について、stからの距離が求まった
	
	rep(i,n){
		if(dist[i]==-1)printf("INF\n");//もし-1なら、その頂点には到達不可のう
		else printf("%lld\n",dist[i]);//そうでなければ、距離を出力
	}
	
	return 0;
}

/*
ちなみに、上の
「もし-1なら、その頂点には到達不可のう」
のコメントの、
「のう」の字を「能」にしたところ、
手元ではまともに動かなくなったことを、ここに付記しておきます。
*/

Measured memory_bytes: 20668
n, k, s = map(int, input().split())
a = [s] * n
if s == 1:
    s = 2
else:
    s -=1
for i in range(k, n):
    a[i] = s
print(a[0], end = "")
for i in a[1:]:
    print("", i, end = "")
print()


Measured memory_bytes: 6128
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        if (str.charAt(0) == '9' || str.charAt(1) == '9') {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll A, B;
    cin >> A >> B;
    if (B % A)
    {
        cout << B - A << endl;
    }
    else
    {
        cout << B + A << endl;
    }
    return 0;
}

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

const ll p = 1e9+7;
const int MAXN = 2e5+5;

ll h, w, a, b;

ll fact[MAXN], invfact[MAXN], inv[MAXN], n;
ll comb(int x, int y) {
	if (x < 0 || y < 0 || x < y)
		return 0;
	return fact[x]*invfact[y]%p*invfact[x-y]%p;
}

ll exp(ll x, ll k) {
	if (k == 0)
		return 1;
	ll y = exp(x, k/2);
	return (k%2 == 0) ? y*y%p : y*y%p*x%p;
}

ll inve(ll x) { return exp(x, p-2); }

void init() {
	inv[1] = fact[0] = fact[1] = invfact[0] = invfact[1] = 1;
	for (int i = 2; i < MAXN; ++i) {
		inv[i] = (p - (p/i) * inv[p%i] % p) % p;
		fact[i] = i*fact[i-1]%p;
		invfact[i] = inv[i]*invfact[i-1]%p;
	}
}

int main() {
	cin >> h >> w >> a >> b;
	ll tot = 0;
	init();
	tot += comb(w+h-2, w-1);
	for (int i = 0; i < b; ++i)
		tot = (tot + p - comb(h-1-a+i, i)*comb(a-1+w-1-i, a-1)%p);
	cout << tot%p << endl;
}

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

#ifndef __TOPCYBERFLOWER
#define debug(...) 0
#else
#define debug(...) cout << " [-] ", _dbg(#__VA_ARGS__, __VA_ARGS__)
template<class TH> void _dbg(const char *sdbg, TH h){ cout << sdbg << '=' << h << endl; }
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
    while(*sdbg != ',') cout << *sdbg++;
    cout << '=' << (h) << ','; 
    _dbg(sdbg+1, a...);
}
#endif

#define TYPEMAX(type)   numeric_limits<type>::max()
#define TYPEMIN(type)   numeric_limits<type>::min()
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;

int main(void){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n,m; cin>>n>>m;
    vector<int> arr(n);
    int tot=0;
    for(int i=0;i<n;i++){
        int x; cin>>x;
        arr[i]=x;
        tot+=x;
    }
    sort(arr.begin(),arr.end(),[&](int x, int y){
        return x>y;
    });
    if(arr[m-1]*4*m>=tot) cout<<"Yes";
    else cout<<"No";
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i < (n); ++i)
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 namespace std;
using ll = long long;
using P = pair<int,int>;
using Pl = pair<long long,long long>;
using veci = vector<int>;
using vecl = vector<long long>;
using vecveci = vector<vector<int>>;
using vecvecl = vector<vector<long long>>;

int main() {
    string S; cin >> S;
    int N = S.size();
    deque<char> deq;
    REP(i,N) {
        if(S[i] == 'T') {
            if(deq.empty()) deq.push_front('T');
            else if(deq.front() == 'S') deq.pop_front();
            else deq.push_front('T');
        } else deq.push_front('S');
    }
    cout << deq.size() << endl;
}

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

using namespace std;
using sz = size_t;

vector<int> stdinput() {
  sz N;
  cin >> N;

  vector<int> A;
  A.reserve(N - 1);

  for (sz i = 1; i < N; ++i) {
    int tmp;
    cin >> tmp;
    A.push_back(tmp);
  }

  return A;
}

vector<int> count(sz N, vector<int>& A) {
  vector<int> result(N, 0);

  for (sz i = 0; i < N - 1; ++i) {
    result[A[i] - 1]++;
  }

  return result;
}

int main() {
  auto A = stdinput();

  auto result = count(A.size() + 1, A);

  for (auto e : result) {
    cout << e << endl;
  }

  return 0;
}


Measured memory_bytes: 4844
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

using namespace std;
using namespace __gnu_pbds;
#define  st first
#define  nd second



void debug_out() { cerr << endl; }
template<class T> ostream& prnt(ostream& out, T v) { out << v.size() << '\n'; for(auto e : v) out << e << ' '; return out;}
template<class T> ostream& operator<<(ostream& out, vector <T> v) { return prnt(out, v); }
template<class T> ostream& operator<<(ostream& out, set <T> v) { return prnt(out, v); }
template<class T1, class T2> ostream& operator<<(ostream& out, map <T1, T2> v) { return prnt(out, v); }
template<class T1, class T2> ostream& operator<<(ostream& out, pair<T1, T2> p) { return out << '(' << p.st << ' ' << p.nd << ')'; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << H; debug_out(T...);}

#define dbg(...) cerr << #__VA_ARGS__ << " ->", debug_out(__VA_ARGS__)
#define dbg_v(x, n) do{cerr<<#x"[]: ";for(int _=0;_<n;++_)cerr<<x[_]<<" ";cerr<<'\n';}while(0)
#define dbg_ok cerr<<"OK!\n"

#define maxn  1000001
#define M   1000000007
#define int long long
template <typename T> using ordered_set =  tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef cc_hash_table<int, int, hash<int > > ht;

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n;
    cin>>n;
    cout<<3*n*n;

}


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

#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for (int i = x; i < n; i++)
#define OP(m) cout << m << endl;
typedef long long ll;
typedef unsigned long long ull;

int main()
{
    string text;
    while (getline(cin, text))
    {
        while (text.find("the") == string::npos && text.find("this") == string::npos && text.find("that") == string::npos)
        {
            rep(i, text.size())
            {
                if (text[i] != ' ' && text[i] != '.')
                {
                    if (text[i] != 'z')
                        text[i]++;
                    else
                    {
                        text[i] = 'a';
                    }
                }
            }
        }
        OP(text)
    }
    return 0;
}


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

using namespace std;

using ll = long long;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, x, t;
  cin >> n >> x >> t;
  cout << t * ((n + x - 1) / x) << '\n';
  return 0;
}


Measured memory_bytes: 3648
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <utility>
#include <iomanip>
#include <map>
using namespace std;
typedef long long ll;
const ll MOD = 1e9+7;
ll dp[100001][3];
map<char,int> m;
int main()
{
	int n,k;int pts[3];
	string t;
	ll ans=0;
	cin>>n>>k;
	for(int i=0;i<3;i++)
		cin>>pts[i];
	cin>>t;
	m['r']=0;
	m['s']=1;
	m['p']=2;
	fill(dp[0],dp[100001],0LL);
	//初期値の設定
	for(int i=0;i<k;i++)
	{
		for(int j=0;j<3;j++)
		{
			if(j==(m[t[i]]+2)%3)
				dp[i][j]=pts[j];
		}
	}
	for(int i=0;i<k;i++)
	{
		int ind=i;
		for(int j=i+k;j<n;j+=k)
		{
			for(int l=0;l<3;l++)
			{
				ll pt=0;
				for(int s=0;s<3;s++)
				{
					if(l==s)
						continue;
					pt=max(pt,dp[j-k][s]);
				}
				if(l==(m[t[j]]+2)%3)
					dp[j][l]=max(dp[j][l],pt+pts[l]);
				else
					dp[j][l]=max(dp[j][l],pt);
			}
			ind+=k;
		}
		ll pt=0;
		for(int j=0;j<3;j++)
			pt=max(pt,dp[ind][j]);
		ans+=pt;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 2816
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<fstream>
#include<cstdlib>
#include<iomanip>
#include<string>
#include<cstring>
#include<cmath>
#include<cfloat>
using namespace std;

int main()
{
    string s;
    cin>>s;
    cout<<s[0]<<s.size()-2<<s[s.size()-1];
	exit(0);
}

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

inline bool check(ll a, ll b, ll c){ return a<b+c; }

int main(){
  ll n, a[100100];
  cin >> n;
  for(int i=0;i<n;i++)cin >> a[i];
  sort(a,a+n,greater<ll>());

  ll ans = 0;
  for(int i=0;i<n-2;i++){
    if(check(a[i],a[i+1],a[i+2])){
      for(int j=i+3;j<n-2;j++){
	if(check(a[j],a[j+1],a[j+2])){
	  ll sum = 0;
	  for(int k=0;k<3;k++)sum += a[i+k] + a[j+k];
	  ans = max(ans,sum);
	  goto END1;
	}
      }
    }
  }
 END1:;

  for(int i=0;i<n-5;i++){
    int comb = (1<<3)-1;
    while(comb < (1<<5)){
      vector<ll> A,B;
      for(int j=0;j<6;j++){
	if( (comb>>j)&1 )A.push_back(a[i+j]);
	else B.push_back(a[i+j]);
      }

      if(check(A[0],A[1],A[2]) && check(B[0],B[1],B[2])){
	ll sum = 0;
	for(int k=0;k<6;k++)sum += a[i+k];
	ans = max(ans,sum);
	goto END2;
      }

      int x = comb & -comb, y = comb + x;
      comb = ( ( (comb & ~y) /x ) >> 1) | y;
    }
  }

 END2: cout << ans << endl;
}

Measured memory_bytes: 1996
// +build ignore
package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"strconv"
)

// I/O
type Scanner struct {
	sc *bufio.Scanner
}

func NewScanner() *Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024), int(1e+9))
	return &Scanner{sc}
}

func (s *Scanner) nextStr() string {
	s.sc.Scan()
	return s.sc.Text()
}

func (s *Scanner) nextInt() int {
	i, e := strconv.Atoi(s.nextStr())
	if e != nil {
		panic(e)
	}
	return i
}

func (s *Scanner) nextFloat() float64 {
	f, e := strconv.ParseFloat(s.nextStr(), 64)
	if e != nil {
		panic(e)
	}
	return f
}

func (s *Scanner) nextRuneSlice() []byte {
	return []byte(s.nextStr())
}

func (s *Scanner) nextIntSlice(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextInt()
	}
	return res
}

func (s *Scanner) nextFloatSlice(n int) []float64 {
	res := make([]float64, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextFloat()
	}
	return res
}

func gcd(x, y int) int {
	if x%y != 0 {
		return gcd(y, x%y)
	}
	return y
}

func run(input io.Reader, output io.Writer) int {
	sc := NewScanner()
	N := sc.nextInt()
	M := sc.nextInt()

	e := 0
	for i := 0; i < M; i++ {
		e += sc.nextInt()
	}

	if N-e >= 0 {
		fmt.Println(N - e)
	} else {
		fmt.Println(-1)
	}

	return 0
}

func main() {
	os.Exit(run(os.Stdin, os.Stdout))
}


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

int main() {

    int H, A;
    cin >> H >> A;

    if (H % A == 0)
        cout << H / A;
    else
        cout << H / A + 1;

    cout << endl;

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#define MAX 500000
#define N 1000000000

int L[MAX/2+2],R[MAX/2+2];
int c;

void merge(int A[],int n,int l,int m,int r);
void mergeSort(int A[],int n,int l,int r);

int main()
{
	int A[MAX],n,i;
	c=0;
	
	scanf("%d",&n);
	
	for(i=0;i<n;i++)
	{
		scanf("%d",&A[i]);
	}
	
	mergeSort(A,n,0,n);
	
	for(i=0;i<n;i++)
	{
	if(i)
		{
			printf(" ");
		}
		printf("%d",A[i]);
	}
	
	printf("\n");
	printf("%d\n",c);

}

void merge(int A[],int n,int l,int m,int r)
{
	int i,j,k;
	int n1=m-l;
	int n2=r-m;
	
	for(i=0;i<n1;i++)
	{
		L[i] = A[l+i];
	}
	
	for(i=0;i<n2;i++)
	{
		R[i] = A[m+i];
	}
	
	L[n1]=R[n2]=N;
	
	for(i=0,j=0,k=l;k<r;k++)
	{
		c++;
		if(L[i]<=R[j])
		{
			A[k]=L[i++];
		}
		else
		{
			A[k]=R[j++];
		}
	}

}

void mergeSort(int A[],int n,int l,int r)
{
	int m;
	
	if(l+1<r)
	{
		m=(l+r)/2;
		mergeSort(A,n,l,m);
		mergeSort(A,n,m,r);
		merge(A,n,l,m,r);
	}
}



Measured memory_bytes: 6500
import sys
sys.setrecursionlimit(10000000)
input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
import functools
import itertools
import math
INF = float('inf')
MOD = 10**9+7

def dijkstra_path(s, edges):
    dist = [INF for i in range(len(edges))]
    dist[s], h, p = 0, [], [-1]*len(edges)
    heappush(h, (0, s))
    while (len(h)):
        dv, v = heappop(h)
        if dv > dist[v]:
            continue
        for u, cost in edges[v]:
            tmp = dv+cost
            if tmp < dist[u]:
                dist[u] = tmp
                p[u] = v
                heappush(h, (tmp, u))
    return dist, p

N, M = map(int, input().split())
S = input()
ids = []
for i, x in enumerate(S):
    if x == '0':
        ids.append(-i)
ids = ids[::-1]
l = len(ids)
es = [[] for i in range(N+1)]
for i in range(N, 0, -1):
    es[i].append((-ids[min(l-1, bisect_right(ids, -i+M)-1)], 1))
d, p = dijkstra_path(N, es)
if d[0] == INF:
    print(-1)
    exit()
vs = []
v = 0
while v != -1:
    vs.append(v)
    v = p[v]
ans = [vs[i+1]-vs[i] for i in range(len(vs)-1)]
print(*ans, sep = ' ')


Measured memory_bytes: 75452