akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
int H,W,h,w;
long long ans[600][600];

int main()
{
	scanf("%d%d%d%d",&H,&W,&h,&w);
	if(h==1&&w==1)
	{
		printf("No");
		return 0;
	}
	if(H%h==0&&W%w==0)
	{
		printf("No");
		return 0;
	}
	long long k=(long long)H*W/(h*w)+100;
	long long cnt=0;
	for(int i=1;i<=H;++i)
	{
		for(int j=1;j<=W;++j)
		{
			if(i%h==0&&j%w==0)
			{
				ans[i][j]=-k*(h*w-1)-1;
			}
			else
			{
				ans[i][j]=k;
			}
			cnt+=ans[i][j];
		}
	}
	if(cnt==0)
	{
		printf("No\n");
	}
	else
	{
		printf("Yes\n");
		for(int i=1;i<=H;++i)
		{
			for(int j=1;j<=W;++j)
			{
				printf("%lld ",ans[i][j]);
			}
			printf("\n");
		}
	}
	return 0;
}

Measured memory_bytes: 4480
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;

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

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

// Self settings
// clang-format off
#define MAX_N 100000
#define REP(i, N) for (int i = 0; i < (int)(N); ++i)
#define SLN(i,N) (i == N-1 ? "\n" : " ")
ll fact(ll n) { ll res = 1; for(ll i=2;i<=n;++i) res = res * i; return res;}
ll nCr(ll n, ll r) {return (fact(n)/fact(n-r)*fact(r)) ;}
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
const ll MOD = 1e9+7;
const ll INF = 1LL << 60;
const int inf = 1000100011;
// clang-format on

int main(void) {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int K, S;
  cin >> K >> S;

  int ans = 0;
  for (int i = 0; i <= K; i++) {
    for (int j = 0; j <= K; j++) {
      if (S - (i + j) <= K && (S - (i + j) >= 0)) {
        ans++;
      }
    }
  }
  cout << ans << endl;

  return 0;
}


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

using i64=int64_t;

#define rep(i,x,y) for(i64 i=i64(x),i##_max_for_repmacro=i64(y); i<i##_max_for_repmacro; ++i)
#define debug(x) #x << "=" << (x)
 
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif
 
const int inf=1.01e9;
const i64 inf64=4.01e18;
const double eps=1e-9;
 
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
        os << v << ",";
    }
    os << "]";
    return os;
}

void solve(){
    i64 N,P;
    cin >> N >> P;

    map<i64,i64> cnt;
    rep(i,2,P+1){
        if(i*i>P) break;
        while(P%i==0){
            ++cnt[i];
            P/=i;
        }
    }

    if(P!=1) ++cnt[P];

    i64 ans=1;
    for(auto p:cnt){
        i64 tmp=1;
        rep(i,0,p.second/N) tmp*=p.first;
        ans*=tmp;
    }

    cout << ans << endl;
}

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


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

using namespace std;
using ll = long long;
#define int ll
using PII = pair<int, int>;
template <typename T> using V = vector<T>;
template <typename T> using VV = vector<V<T>>;
template <typename T> using VVV = vector<VV<T>>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll INF = (1LL<<60);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

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

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

  int n, m;
  cin >> n >> m;

  int ans = INF;

  int ret = 0;
  int n2 = n, n1 = 0, m2 = m, m1 = 0;
  while(1) {
    // uku
    int tmp = 0;
    // m1を減らす
    if(m1 > (n2+n1)) m1 -= n2+n1, tmp = n1+n2;
    else tmp = m1, m1 = 0;
    // m2を減らす (n2+n1) - tmp
    m2 -= (n2+n1-tmp)/2;
    // 余ってたらm1
    if(m2 <= 0 && m1 <= 0) break;
    if((n2+n1-tmp)%2 == 1) m2--, m1++; 
    ret++;
    // usi
    // n2->n1
    tmp = 0;
    if(n2 < m1+m2) tmp = n2, n1 += n2, n2 = 0;
    else n2 -= m1+m2, n1 += m1+m2, tmp = m1+m2;
    // n1を減らす (m1+m2) - tmp
    n1 -= m1+m2-tmp;
    if(n2 <= 0 && n1 <= 0) break;
    ret++;
  }
  chmin(ans, ret);

  swap(n, m);
  ret = 0;
  n2 = n, n1 = 0, m2 = m, m1 = 0;
  while(1) {
    // uku
    // n2->n1
    int tmp = 0;
    if(n2 < m1+m2) tmp = n2, n1 += n2, n2 = 0;
    else n2 -= m1+m2, n1 += m1+m2, tmp = m1+m2;
    // n1を減らす (m1+m2) - tmp
    n1 -= m1+m2-tmp;
    if(n2 <= 0 && n1 <= 0) break;
    ret++;
    // usi
    tmp = 0;
    // m1を減らす
    if(m1 > (n2+n1)) m1 -= n2+n1, tmp = n1+n2;
    else tmp = m1, m1 = 0;
    // m2を減らす (n2+n1) - tmp
    m2 -= (n2+n1-tmp)/2;
    // 余ってたらm1
    if(m2 <= 0 && m1 <= 0) break;
    if((n2+n1-tmp)%2 == 1) m2--, m1++; 
    ret++;
  }
  chmin(ans, ret);

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



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

int main() {
  int N, A, B, C;
  cin >> N;
  A = N / 100;
  B = (N % 100) / 10;
  C = N % 10;
  if (A == 7 || B == 7 || C == 7) cout << "Yes" << endl;
  else cout << "No" << endl;
}

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

int main(){
    int A, B;
    cin >> A >> B;

    int C = max(A, B);
    if(max(A, B) == A){
        A--;
        C += max(A, B);
    } 
    else if(max(A, B) == B){
        B--;
        C += max(A, B);
    }
    cout << C << endl;
}

Measured memory_bytes: 256
n = int(input())

while True:
  flag = False
  for i in range(len(str(n))-1):
    if str(n)[i] == str(n)[i+1]:
      flag = True
      
    elif str(n)[i] != str(n)[i+1]:
      flag = False
      break
  
 
  if flag:
    print(n)
    break
  n +=1

Measured memory_bytes: 3060
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys  # {{{
import os
import time
import re
from pydoc import help
import string
import math
from operator import itemgetter
from collections import Counter
from collections import deque
from collections import defaultdict as dd
import fractions
from heapq import heappop, heappush, heapify
import array
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy as dcopy
import itertools
# }}}

# pre-defined{{{
sys.setrecursionlimit(10**7)
INF = 10**20
GOSA = 1.0 / 10**10
MOD = 10**9+7
ALPHABETS = [chr(i) for i in range(ord('a'), ord('z')+1)]  # can also use string module
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def DP(N, M, first): return [[first] * M for n in range(N)]
def DP3(N, M, L, first): return [[[first] * L for n in range(M)] for _ in range(N)]
from inspect import currentframe
def dump(*args):
    names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' => '+repr(arg) for arg in args), file=sys.stderr)
# }}}

def local_input():# {{{
    from pcm.utils import set_stdin
    import sys
    from pathlib import Path
    parentdir = Path(os.path.dirname(__file__)).parent
    inputfile = parentdir.joinpath('test/sample-1.in')
    if len(sys.argv) == 1:
        set_stdin(inputfile)
# }}}

m = 10**9 + 7


def solve():
    global n,s;
    n  = int(input())
    s = input()

    res = 1
    for k, v in Counter(s).items():
        res *= (v+1)
        res %= m

    print(res-1)

    return 0

if __name__ == "__main__":# {{{
    try:
        local_input()
    except:
        pass
    solve()
# vim: set foldmethod=marker:}}}


Measured memory_bytes: 104172
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <climits>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <string>

using namespace std;
using pii=pair<int,int>;
using ll=long long;

struct EDGE{
    int dst;
    bool check;
};

int n,m,s,t;
vector<vector<int>> adj;

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

    cin>>n>>m;
    adj.resize(3*n);
    for(int i=0; i<m; i++){
        int u,v;
        cin>>u>>v;
        u-=1;
        v-=1;
        adj[u].push_back(v+n);
        adj[u+n].push_back(v+2*n);
        adj[u+2*n].push_back(v);
    }
    cin>>s>>t;
    s-=1;
    t-=1;

    queue<pii> q;
    vector<int> visited(3*n);
    visited[s]=true;
    q.push({s,0});
    while(!q.empty()){
        auto now=q.front();
        q.pop();
        if(now.first==t){
            cout<<now.second/3;
            return 0;
        }
        for(int nxt : adj[now.first]){
            if(!visited[nxt]){
                visited[nxt]=true;
                q.push({nxt,now.second+1});
            }
        }
    }
    cout<<-1;

    return 0;
}


Measured memory_bytes: 17792
#include<stdio.h>

int main(){
	int S,h,m,s;
	scanf("%d",&S);
	h=S/3600;
	m=S/60-h*60;
	s=S-h*3600-m*60;
	printf("%d:%d:%d\n",h,m,s);
	return 0;
}

Measured memory_bytes: 592
import static java.lang.System.*;
import java.util.*;

public class Main {
	static Scanner sc = new Scanner(System.in);
	static List<Integer> list = new ArrayList<>();
	static int num = 0;

	
	public static void main(String[] args) {
		int n = sc.nextInt();
		for (int i=0; i<n; i++) list.add(sc.nextInt());

		mergeSort(list);
		
		StringBuilder sb = new StringBuilder();
		for (int i=0; i<list.size(); i++) sb.append((i==0?"":" ")+list.get(i));
		out.println(sb);
		out.println(num);
	}

	
	static void mergeSort(List<Integer> list) {
		int size = list.size();

		//listの大きさが1なら再帰終了
		if (size == 1) return;

		//1でないなら分割
		ArrayList<Integer> L = new ArrayList<>(), R = new ArrayList<>();
		int M = size/2;

			//分割処理、左側を作成
			for (int i=0; i<M; i++) L.add(list.get(i));
			//分割処理、右側を作成
			for (int i=M; i<size; i++) R.add(list.get(i));

			
		//再帰
		mergeSort(L); mergeSort(R);

		//マージ処理
		list.clear();
		int indexL = 0, indexR = 0;
		while (indexL<L.size() || indexR<R.size()) {
			if (indexL == L.size()) {
				list.add(R.get(indexR)); indexR++; num++;
			}
			else if (indexR == R.size()) {
				list.add(L.get(indexL)); indexL++; num++;
			}
			else {
				int tempL = L.get(indexL);
				int tempR = R.get(indexR);
				if (tempL <= tempR) {
					list.add(tempL); indexL++;
				}
				else {
					list.add(tempR); indexR++;
				}
				num++;
			}
		}
	}
}


Measured memory_bytes: 332068
using System;

namespace ITP_5_C{
    public class Program{
        public static void Main(string[] args){
            bool loopFlag = true;

            while(loopFlag){
                string[] temp = Console.ReadLine().Split(' ');
                int y = int.Parse(temp[0]);
                int x = int.Parse(temp[1]);

                if(x==0 && y==0){
                    loopFlag = false;
                }else{
                    //???????????????????????????
                    for(int h=0;h<y; h++){
                        for(int w=0;w<x; w++){
                            if((h+w)%2 == 0){
                                Console.Write("#");
                            }else{
                                Console.Write(".");
                            }
                        }
                        Console.WriteLine();
                    }
                    Console.WriteLine();
                }
            }
        }
    }
}

Measured memory_bytes: 8792
#include<bits/stdc++.h>
#define  ll  long long int
#define  sz   200010

using namespace std;



int main()
{


    string s;
    ll i,j,k,p;

    cin>>s>>k;

    p=s.size();

   ll x=min(p,k);

    for(i=0;i<x;i++)
    {
        if(s[i]!='1')
        {
            cout<<s[i]<<endl;
            return 0;
        }
    }

    cout<<1<<endl;

    return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize(3 , "Ofast" , "inline")

#include <bits/stdc++.h>

#define rep(i , a , b) for(register int i=(a);i<=(b);i++)
#define per(i , a , b) for(register int i=(a);i>=(b);i--)


using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int , int> pi;

template<class T>
inline void read (T &x) {
    x = 0;
    int sign = 1;
    char c = getchar ();
    while (c < '0' || c > '9') {
        if ( c == '-' ) sign = - 1;
        c = getchar ();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar ();
    }
    x = x * sign;
}

const int maxn = 1e6 + 10;
const int inf = int (1e9);
const ll INF = ll (1e18);
const double PI = acos (- 1);
const int mod = 1e9+7;
const double eps = 1e-8;


string s;
ll dp[maxn][2];
int main () {
    cin>>s;
    reverse (s.begin (),s.end ());
    string t = "0"+s;
    dp[1][0]=t[1]-'0';
    dp[1][1]=10-(t[1]-'0');
    int l = s.size ();
    rep (i,2,l) {
        int x = t[i]-'0';
        dp[i][0]=min (dp[i-1][0]+x,dp[i-1][1]+x+1);
        dp[i][1]=min (dp[i-1][0]+10-x,dp[i-1][1]+9-x);
    }
    printf ("%lld\n",min (dp[l][0],dp[l][1]+1));
    return 0;
}


Measured memory_bytes: 17924
#include <iostream>
#include<iomanip>
#include<cmath>
using namespace std;
#define pi 3.14159265358979323846264338327950L

int main() {
     int a,b;
     cin>>a>>b;
    int m,h;
    cin>>h>>m;
    long double x=(m*pi)/30-(pi*h)/6-(pi*m)/360;
    long double k=cos(x);
    long double ans;
  ans=sqrt(a*a+b*b-2*a*b*k);
  cout<<fixed<<setprecision(20)<<ans<<endl;
    return 0;

}

Measured memory_bytes: 4168
#include <cstdio>
#include <iostream>
#include <string>
#include <cstdlib>
#include <algorithm>
#include <cctype>
using namespace std;

typedef long long LL;

#define MOD 1000000007LL

LL expr();
LL term();

const char *P;

LL expr(){
	LL x = term();
	while(*P == '>' && P[1] == '>' && (P[2] == 'S' || isdigit(P[2]))){
		P += 2;
		LL y = term();
		x >>= min(y, 63LL);
	}
	return x;
}

LL term(){
	LL x = 0;
	if(*P == 'S'){
		P += 2;
		x = expr();
		x = x * x % MOD;
		++P;
	}
	else{
		char *endp;
		x = strtoll(P, &endp, 10);
		P = endp;
	}
	return x;
}

int main(){
	string s;
	while(getline(cin, s), s[0] != '#'){
		s.erase(remove(s.begin(), s.end(), ' '), s.end());
		P = s.c_str();
		cout << expr() << endl;
	}
}

Measured memory_bytes: 3400
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

N, M, A, B = map(int, input().split())
X = list(map(int, input().split()))
Y = list(map(int, input().split()))

min_z = max(X) + 1
max_z = min(Y)
ok = False
for z in range(min_z, max_z + 1):
    if A < z <= B:
        ok = True
if ok:
    print("No War")
else:
    print("War")


Measured memory_bytes: 9492
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
using ld = long double;
template<typename T> using V = vector<T>;
template<typename T> using VV = vector<vector<T>>;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(),(v).end()
#define siz(v) (ll)(v).size()
#define rep(i,a,n) for(ll i=a;i<(ll)(n);++i)
#define repr(i,a,n) for(ll i=n-1;(ll)a<=i;--i)
#define ENDL '\n'
typedef pair<int,int> Pi;
typedef pair<ll,ll> PL;
constexpr ll mod = 1000000007;
constexpr ll INF = 1000000099;
constexpr ll LINF = (ll)(1e18 +99);
const vector<ll> dx={-1,1,0,0},dy={0,0,-1,1};
template<typename T,typename U> inline bool chmin(T& t, const U& u){if(t>u){t=u;return 1;}return 0;}
template<typename T,typename U> inline bool chmax(T& t, const U& u){if(t<u){t=u;return 1;}return 0;}
template<typename T> inline T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T,typename Y> inline T mpow(T a, Y n) {
  T res = 1;
  for(;n;n>>=1) {
    if (n & 1) res = res * a;
    a = a * a;
  }
  return res;
}

const int MAX = 1000010;//設定して

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

void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % mod;
        inv[i] = mod - inv[mod%i] * (mod / i) % mod;//＊１
        finv[i] = finv[i - 1] * inv[i] % mod;
    }
}

long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}


signed main(){
  cin.tie(0);ios::sync_with_stdio(false);
  cout<<fixed<<setprecision(20);
  ll n;cin>>n;
  COMinit();
  V<ll> undk(n,0);

  ll ans=0;
  rep(i,1,n){
    if(i-1<n-1-i)continue;

    ll tmp=COM(i-1,n-1-i);
    tmp%=mod;
    tmp*=fac[i];
    tmp%=mod;
    tmp*=fac[n-1-i];
    tmp%=mod;
    undk[i]=tmp;
  }

  rep(i,1,n){
    ans+=i*(undk[i]-undk[i-1]+mod)%mod;
    ans%=mod;
  }

  cout<<ans<<ENDL;
}
//! ( . _ . ) ! 
//CHECK overflow,vector_size,what to output?

Measured memory_bytes: 31488
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
int n,p;
int main()
{
	cin>>n>>p;
	bool ok=false;
	for(int i=1;i<=n;i++)
	{
		int a;
		cin>>a;
		if(a%2) ok=true;
	}
	if(ok)
	printf("%lld\n",(1LL<<(n-1)));
	else if(p) printf("0\n");
	else printf("%lld\n",1LL<<n);
	return 0;
	
}

Measured memory_bytes: 256
n = int(input())
H = list(map(int, input().split()))

H.insert(0, 0)
H.append(0)

a = 0
while sum(H) != 0:
    
    S, E = [], []
    for i in range(n + 1):
        if H[i] == 0 and H[i + 1] != 0:
            S.append(i + 1)
        elif H[i] != 0 and H[i + 1] == 0:
            E.append(i + 1)
    
    for i in range(len(S)):
        s, e = S[i], E[i]
        m = min(H[s:e])
        H[s:e] = [h - m for h in H[s:e]]
        a += m

print(a)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define ALL(x) (x).begin(),(x).end()
#define COUT(x) cout<<(x)<<"\n"
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define REP(i, n) for(int i=0;i<n;i++)
#define YES(x) cout<<(x?"YES":"NO")<<"\n"
#define Yes(x) cout<<(x?"Yes":"No")<<"\n"
#define dump(x) cout<<#x<<" = "<<(x)<<"\n"
#define endl "\n"
using G = vector<vector<int>>;
using M = map<int,int>;
using P = pair<int,int>;
using PQ = priority_queue<int>;
using PQG = priority_queue<int,vector<int>,greater<int>>;
using V = vector<int>;
using ll = long long;
using edge = struct { int to; int cost; };
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

int main() {
  IOS;
  string s; cin >> s;
  int n = s.size();
  vector<int> ans(n);

  int cnt = 0;
  REP(i,n) {
    if (s[i] == 'L') {
      if (cnt > 0) {
        ans[i] += cnt / 2;
        ans[i-1] += cnt - cnt/2;
      }
      cnt = 0;
      continue;
    }
    cnt++;
  }

  cnt = 0;
  for (int i = n-1; i >= 0; i--) {
    if (s[i] == 'R') {
      if (cnt > 0) {
        ans[i] += cnt / 2;
        ans[i+1] += cnt - cnt/2;
      }
      cnt = 0;
      continue;
    }
    cnt++;
  }

  REP(i,n) {
    if (i > 0) cout << " ";
    cout << ans[i];
  }
  cout << endl;
  return 0;
}

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

int main() {
    int N;
    cin >> N;
    vector<int>a(N);
    for (int i = 0; i < N; ++i) {
        cin >> a[i];
    }

    bitset<2000001> flag;
    flag[0] = 1;
    int sum = 0;
    for (int i = 0; i < N; ++i) {
        sum += a[i];
        flag |= (flag << a[i]);
    }
    for (int i = sum / 2; i >= 0; --i) {
        if (flag[i]) {
            cout << sum - i << "\n";
            break;
        }
    }
    return 0;
}

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

int main() {
	int N, p[10], ans;
	cin >> N;
	for (int i = 0; i < N; ++i) cin >> p[i];
	sort(p, p + N);
	reverse(p, p + N);
	ans = p[0] / 2;
	for (int i = 1; i < N; ++i) ans += p[i];
	cout << ans;
}

Measured memory_bytes: 256
// C++ 14
#include <iostream>
#include <vector>
using namespace std;
#define ll long long
#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)
//  cout.precision(15); cout << fixed;

typedef pair<int, int> P;

int main() {
  ll n, m; cin >> n >> m;
  vector<P> S(n), C(m);
  loop(i,0,n) cin >> S[i].first >> S[i].second;
  loop(i,0,m) cin >> C[i].first >> C[i].second;
  
  const int INF = 1400000000;
  vector<int> I(n);
  loop(i,0,n) {
    int min_ = INF;
    loop(j,0,m) {
      int d = abs(S[i].first - C[j].first) + abs(S[i].second - C[j].second);
      if (min_ > d) {
        I[i] = j + 1;
        min_ = d;
      }
    }
  }
  loop(i,0,n) cout << I[i] << endl;
  return 0;
}


Measured memory_bytes: 3608
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mp make_pair
#define pb push_back
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)

const ll mod=1e9+7;
ll mu(ll a,ll b){
  return (ll)a*b%mod;
}
ll ad(ll a,ll b){
  if((a+=b)>=mod)a-=mod;
  return a;
}
ll pw(ll a,ll b,ll c=1LL){
  for(;b;b>>=1,a=mu(a,a))if(b&1)c=mu(c,a);
  return c;
}
ll dv(ll a,ll b){
  return mu(a,pw(b,mod-2));
}

int main(){
  int h,w,k;
  cin >> h >>w >>k;
  
  ll dp[w];
  ll ndp[w];
  rep(i,w){
    dp[i]=0;ndp[i]=0;
  }
  dp[0]=1;

  rep(i,h){
    rep(j,1<<(w-1)){
      bool ok=true;
      rep(l,w-2){
	if((j & (3<<l))==(3<<l)) ok=false;
      }
      if(ok){
	rep(l,w-1){
	  if(j&(1<<l)){
	    ndp[l] = ad(ndp[l],dp[l+1]);
	    ndp[l+1] = ad(ndp[l+1],dp[l]);
	    l++;
	    if(l==w-2){
	      ndp[l+1]=ad(ndp[l+1],dp[l+1]);
	    }
	  }
	  else{
	    if(l==w-2) ndp[l+1]=ad(ndp[l+1],dp[l+1]);
	    ndp[l] = ad(dp[l],ndp[l]);
	  }
	}
      }
      //      cout << bitset<3>(j) << " " << ok << " "  << ndp[2] <<endl;
    }
    rep(i,w) swap(ndp[i],dp[i]);
    rep(i,w) ndp[i]=0;
  }
  if(w!=1) cout << dp[k-1] << endl;
  else cout << 1 << endl;
  return 0;

}


Measured memory_bytes: 256
S = sorted(list(set(list(input()))))
alfabet = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
count = 0
for char in alfabet:
    if not(char in S):
        print(char)
        break
    count+=1
if count == 26:
    print("None")

Measured memory_bytes: 9744
c=input()
n=0
alphabet=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
for i in alphabet:
    if c==i:
        print(alphabet[n+1])
    n+=1

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

ll N;
ll F[110][10];
ll P[110][11];

int main(){

    // input
    cin >> N;
    rep(i, 0, N){
        rep(j, 0, 10){
            cin >> F[i][j];
        }
    }
    rep(i, 0, N){
        rep(j, 0, 11) cin >> P[i][j];
    }

    // bit
    ll ans = -1e18;
    for(ll i = 1; i < (1LL<<10); i++){
        vector<ll> c(N, 0);
        ll tmp = 0;
        for(ll j = 0; j < 10; j++){
            if(i & (1LL<<j)){
                rep(k, 0, N){
                    if(F[k][j] == 1) c[k]++;
                }
            }
        }
        rep(k, 0, N) tmp += P[k][c[k]];
        ans = max(ans, tmp);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <vector>
#include <iostream>
using namespace std;
constexpr long long mod = 1e9+7;

int main(){
  int N, M;
  cin >> N >> M;
  vector<bool> A(N+2,true);
  for(int i = 0; i < M; ++i){
    int a;
    cin >> a;
    A[a] = false;
  }
  vector<int> dp(N+2,0);
  dp[0] = 1;
  for(int i = 0; i < N; ++i){
    if(A[i+1]) dp[i+1] += dp[i], dp[i+1] %= mod;
    if(A[i+2]) dp[i+2] += dp[i], dp[i+2] %= mod;
  }
  cout << dp[N] << endl;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
struct S{
  int id,a=0,p=0,w[11]={};
  bool operator<(const S&o)const{
    return a==o.a?p==o.p?id<o.id:p<o.p:a>o.a;
  }
};
int t,p,r,i,a,b,c;
string s;
main(){
  while(cin>>t>>p>>r,t){
    S z[t];
    for(i=0;i<t;++i)z[i].id=i+1;
    for(i=0;i<r;++i){
      cin>>a>>b>>c>>s;
      if(s=="CORRECT")z[--a].a++,z[a].p+=z[a].w[b]*1200+c;
      else z[--a].w[b]++;
    }
    sort(z,z+t);
    for(i=0;i<t;++i)cout<<z[i].id<<' '<<z[i].a<<' '<<z[i].p<<endl;
  }
}

Measured memory_bytes: 3060
while "-1 -1 -1
"!=gets
m,f,r=$_.split.map &:to_i
puts (if m<0||f<0
?F
elsif (a=m+f)>79
?A
elsif a>64
?B
elsif a>49
?C
elsif a>29
r>49? ?C:?D
else
?F
end)
end


Measured memory_bytes: 6868
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> P;
typedef pair<LL, LL> PL;
typedef pair<P, LL> PP;
typedef pair<P, LL> PP;
typedef long long LL;

#define xx first
#define yy second

int main()
{
  //freopen("input", "r", stdin);
  // freopen("output", "w", stdout);
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  int n;
  multiset<int> si;
  int fl = 1;
  cin>>n;
  for(int i=0;i<(1<<n);i++){
    int t;cin>>t;
    si.insert(t);
  }
  auto eit = si.end();
  eit--;
  vector<int> vp{*eit};
  si.erase(eit);
  while(vp.size()!=(1<<n)){
    vector<int> tp;
    for(auto i:vp){
      tp.push_back(i);
      auto it = si.lower_bound(i);
      if(it==si.begin()){fl = 0;break;}
      it--;
      tp.push_back(*it);
      si.erase(it);
    }
    vp = move(tp);
    if(fl==0)break;
  }
  if(fl)
    cout<<"Yes"<<endl;
  else
    cout<<"No"<<endl;
}


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

int main(){
  int n;
  cin >> n;
  int a[n];
  for(int i=0; i<n; i++){
    cin >> a[i];
  }
  for(int j=n-1; j>=0; j--){
    cout << a[j];
    if(j>0)
      cout << ' ';
  }
  cout << endl;
}


Measured memory_bytes: 3068
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <stdio.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <tuple>
#include <map>
#include <set>
#include <sstream>
using namespace std;
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define FOR(i,a,b) for(int i=a; i<(int)(b); i++)
#define ALL(x) (x).begin(),(x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SORT(c) sort(ALL(x))
#define CLR(a) memset((a), 0 ,sizeof(a))
#define PB push_back
#define MP make_pair
#define SP << " " <<
#define chmax(a, b) a = (((a)<(b))?(b):(a))
#define chmin(a, b) a = (((a)<(b))?(a):(b))

const int INF = 1001001001;
const ll MOD = 1e9+7;
const ll LINF = 100100100100100100;
const double EPS = 1e-10;
const double PI  = acos(-1.0);
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<double> VD;

__attribute__((constructor))
void initial(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}

ll mpow(ll a, ll b){
  if(b==0) return 1;
  else if(b%2==0){ll memo = mpow(a,b/2); return memo*memo%MOD;}
  else return mpow(a,b-1) * a % MOD;
}

int h,w;
char c[25][25];
const int dx[]={0,0,1,-1};
const int dy[]={1,-1,0,0};
int visited[25][25];
int mx = 0;

void bfs(int x, int y){
  queue<pair<PII, int> > q;
  q.push(MP(MP(x,y),0));
  while(!q.empty()){
    pair<PII, int> p = q.front(); q.pop();
    rep(i,4){
      int ax = p.first.first+dx[i];
      int ay = p.first.second+dy[i];
      if(ax==x&&ay==y) continue;
      if(ax>=0&&ax<h&&ay>=0&&ay<w&&c[ax][ay]=='.'&&!visited[ax][ay]){
        visited[ax][ay] = p.second+1;
        chmax(mx,visited[ax][ay]);
        q.push(MP(MP(ax,ay),visited[ax][ay]));
      }
    }
  }
}


signed main(){
  cin>>h>>w;
  rep(i,h){
    rep(j,w){
      cin>>c[i][j];
    }
  }
  rep(i,h){
    rep(j,w){
      if(c[i][j]=='#') continue;
      bfs(i,j);
      memset(visited,0,sizeof(visited));
    }
  }
  cout << mx << endl;

  return 0;
}


Measured memory_bytes: 256
n = gets.to_i
as = gets.split.map(&:to_i)
q = gets.to_i
bc = q.times.map {gets.split.map(&:to_i)}

table = as.tally
sum = as.sum

bc.each do |b, c|
  tmp = table[b] || 0
  sum += (c - b) * tmp
  puts sum
  if table.has_key?(c)
    table[c] += tmp
  else
    table[c] = tmp
  end
  table.delete(b)
end

Measured memory_bytes: 27608
#include <bits/stdc++.h>
using namespace std;
#define rep(i,j) for(int i=0;i<j;++i)
int N,M,p,d[10010];
int main(){
    cin>>N>>M>>p;
    rep(i,M){
        scanf("%d",d+i);
        d[i]=(d[i]-p+N)%N;
    }
    sort(d,d+M);
    p=N;
    rep(i,M){
        p=min(p,d[i]+min(d[M-1]-d[i],i==M-1?d[i]-d[0]:N+d[i]-d[i+1]));
        p=min(p,N-d[i]+min(d[i]-d[0],i==0?d[M-1]-d[i]:N+d[i-1]-d[i]));
    }
    cout<<p*100<<"\n";
    return 0;
}

Measured memory_bytes: 1304
N = int(input())
a = list(map(int, input().split()))
E = [(v, i + 1) for i, v in enumerate(a)]
E.sort(reverse = True)
L = [0] + [i for i in range(N + 1)]
R = [i + 1 for i in range(N + 1)] + [N + 1]
res = 0
for v, i in E:
  l = L[i]
  r = R[i]
  L[r], R[l] = l, r
  res += v * (i - l) * (r - i)
print(res)

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

using namespace std;

int main() {

  

  int n;

bool b =false;

  

int k;

  cin >> n;

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

    cin >> k;

    if (k %2==0){

      if (!(k%3==0 || k%5==0)){

        cout << "DENIED" << endl;

b =true;

        break;

        

        }

      }

    }

 

if (b ==false){

  cout << "APPROVED" << endl;
  }
  }

Measured memory_bytes: 256
# C
n, m = map(int, input().split())
k =[0]*m
s = [0]*m
for i in range(m):
    lst=input().split()
    k[i] = int(lst[0])
    s[i] = [int(x) - 1 for x in lst[1:]]
p = [int(x) for x in input().split()]
# print(s, p)
ans=0
for i in range(2 ** n):
    all_on = True
    for j in range(m):
        light = 0
        for k in s[j]:
            tmp = i >> k & 1
            #iをkだけ左にシフトし1とのANDをとる
            #>>iのk番目が1の時１を返す
            light = (light + tmp) % 2
            # print(tmp,light)
        if light != p[j]:
            all_on = False
            # print(light,p[j])
            break
    ans += int(all_on)
print(ans)


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

using namespace std;

using ll = long long;
using ull = unsigned long long;
constexpr int mo = 1e9+7;
constexpr int inf = 1<<30;
constexpr ll infl = 1ll<<60;
constexpr ll mo2 = 998244353;
const double PAI = acos(-1);
constexpr long double eps = 1e-9;

ll ret = 0;
void prime(ll n){
    for(ll i=2;i*i<=n;++i)if(n%i==0){
        ll count = 0;
        int c = 0;
        while(n%i == 0){
            c++;
            n /= i;
        }
        int j = 1;
        c--;
        while(c >= 0){
            j++;
            c-=j;
            count++;
        }
        ret += count;
    }
    if(n != 1){
        ret++;
    }
}
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    
    
    ll n;
    cin>>n;
    
    prime(n);
    cout << ret << endl;
    return 0;
}


Measured memory_bytes: 3652
x,y = map(int,input().split())
A = [1,3,5,7,8,10,12]
B = [4,6,9,11]
C = [2]
chk = [0]*13
for a in A:
  chk[a] = 1
for a in B:
  chk[a] = 2
for a in C:
  chk[a] = 3
if chk[x]==chk[y]:
  print("Yes")
else:
  print("No")
  

Measured memory_bytes: 9108
N = int(input())
M = 10**6 + 1

counts = [0 for _ in range(M)]
for a in map(int, input().split()):
  counts[a] += 1

max_count = 0
for i in range(2,M):
  max_count = max(max_count,sum(counts[i::i]))

if max_count == N:
  answer = 'not coprime'
elif max_count >= 2:
  answer = 'setwise coprime'
else:
  answer = 'pairwise coprime'

print(answer)

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

int main() {
  int a, b;
  int d;
  int r;
  double f;

  cin >> a >> b;

  d = a / b;
  r = a % b;
  f = (double)a / (double)b;
  printf("%d %d %f\n", d, r, f);
}

Measured memory_bytes: 1184
"use strict"
 
function Main(input) {
  input = input.trim().split('\n');
  const N = input[0].trim().split(' ').map(Number)[0];
  let X = input[0].trim().split(' ').map(Number)[1];
  const a = input[1].trim().split(' ').map(Number).sort((a,b) => a-b);
 
  let ret = 0;
  for(let i=0; i<N; i++){
    if(i === N-1){
      if(a[i] === X) ret += 1;
    }else if(X >= a[i]){
      X -= a[i];
      ret += 1;
    } else {
      break;
    }
  }
 
  console.log(ret);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 30588
class Abc073c
  def self.count_numbers
    counter = Hash.new(0.freeze)
    $stdin.gets.chomp.to_i.times do
      num = $stdin.gets.chomp
      counter[num] += 1
    end
    counter.values.select(&:odd?).length
  end
end

print Abc073c.count_numbers


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

using namespace std;
typedef long long ll;
#define out(ans) cout << ans << endl;
const long long mod = 1e9 + 7;

int main() {
  ll n, ans=0, march[5] = {0},tmp=1;
  cin >> n;
  string s;
  for (int i = 0; i < n; i++) {
    cin >> s;
    switch (s[0]) {
      case 'M':
        march[0]++;
        break;
      case 'A':
        march[1]++;
        break;
      case 'R':
        march[2]++;
        break;
      case 'C':
        march[3]++;
        break;
      case 'H':
        march[4]++;
        break;
      default:
        break;
    }
  }

  for (int i = 0; i < 4; i++) {
    for (int j = i + 1; j < 5; j++) {
      for (int k = 0; k < 5; k++) {
        if (k != i && k != j) {
          tmp *= march[k];
        }
      }
      ans += tmp;
      tmp = 1;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

n = int(input())
s = input()

def main():
    md=10**9+7
    dp=[[0]*(n+1) for _ in range(n+1)]
    dp[1][0]=1
    dpx=dp[1]
    for x in range(2,n+1):
        dpx1=dpx
        dpx=dp[x]
        if s[n - x] == "<":
            for i in range(x-2,-1,-1):
                dpx[i]=(dpx[i+1]+dpx1[i])%md
        else:
            for i in range(1,x):
                dpx[i]=(dpx[i-1]+dpx1[i-1])%md
    #p2D(dp)
    print(sum(dp[n])%md)

main()


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

using namespace std;

#define ll long long 
#define ld long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define ff first
#define ss second
#define endl "\n"
#define MOD 1000000007
#define MOD1 998244353
#define inf 1e18

ll GCD(ll x,ll y){if(y==0)return x;return GCD(y,x%y);}
ll LCM(ll x,ll y){return (x*y)/(GCD(x,y));}
ll LOGK(ll x,ll k){if(x>=k)return 1+LOGK(x/k,k);return 0;}
ll MPOW( ll a, ll b, ll m) { if(b==0) return 1; ll x=MPOW(a,b/2,m); x=(x*x)%m; if(b%2==1) x=(x*a)%m; return x;}
ll MINV(ll a,ll m) {return MPOW(a,m-2,m);}

class pnc{
  ll FACT_MAX,MODU;
  vector<ll> fact;
public:
  pnc( ll n, ll m) { FACT_MAX = n; fact.resize(FACT_MAX); MODU = m; MFACT_INIT(MODU);}
  void MFACT_INIT( ll m) { fact[0]=1; for(ll i=1;i<FACT_MAX;++i) fact[i]=(i*fact[i-1])%MODU;}
  ll MFACT( ll n) { return fact[n];}
  ll PERM( ll n, ll r) { return (fact[n]*::MINV(fact[n-r],MODU))%MODU;}
  ll COMB( ll n , ll r) { return (PERM(n,r)*::MINV(fact[r],MODU))%MODU;}
};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);    

    ll test=1;
    // cin>>test;
    while(test--)
    {
        string str;
        cin>>str;

        ll ans=0;

        for(ll i=0;i<str.length();i++)
        {
            ans+=str[i]-'0';
            ans%=9;
        }

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

Measured memory_bytes: 3784
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007



n, m = LI()
G = [[] for _ in range(n)]
for a, b, c in LIR(m):
    G[a - 1] += [(b - 1, c)]

# 負の閉路がなかったら高々n-1回で更新は終わるはずn回目に更新が起こったとしたら負の閉路がある。
def bellman_ford(G, s=0):
    n = len(G)
    dist = [-INF] * n
    dist[s] = 0
    v_nows = {s}
    for _ in range(n):
        v_changeds = set()
        for u in v_nows:
            for v, c in G[u]:
                if dist[u] + c > dist[v]:
                    dist[v] = dist[u] + c
                    v_changeds.add(v)
        v_nows = v_changeds
    if not v_changeds:
        return dist[n - 1]
    for i in v_nows:
        dist[i] = INF
    dq = deque(v_nows)
    while dq:
        u = dq.popleft()
        if u == n - 1:
            return "inf"
        for v, c in G[u]:
            if dist[v] != INF:
                dist[v] = INF
                dq += [v]
    return dist[n - 1]



print(bellman_ford(G))



Measured memory_bytes: 83872
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cassert>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <iostream>
#include <numeric>

/* debug macros */
#ifdef WAFDAYO
#define DBG_LINE() {std::cerr<<"\e[2m[L"<<__LINE__<<"]\e[m ";}
#define DBG_PRINT(s,t,u) {std::cerr<<(s)<<" \e[2m=\e[m \e[1m"<<(t)<<"\e[m"<<(u);}
#define SELECT_7TH(x1,x2,x3,x4,x5,x6,x7,...) x7
#define dbg1(x1) DBG_PRINT(#x1,x1,std::endl)
#define dbg2(x1,x2) DBG_PRINT(#x1,x1,", ")dbg1(x2)
#define dbg3(x1,x2,x3) DBG_PRINT(#x1,x1,", ")dbg2(x2,x3)
#define dbg4(x1,x2,x3,x4) DBG_PRINT(#x1,x1,", ")dbg3(x2,x3,x4)
#define dbg5(x1,x2,x3,x4,x5) DBG_PRINT(#x1,x1,", ")dbg4(x2,x3,x4,x5)
#define dbg6(x1,x2,x3,x4,x5,x6) DBG_PRINT(#x1,x1,", ")dbg5(x2,x3,x4,x5,x6)
#define dbg(...) DBG_LINE()\
SELECT_7TH(__VA_ARGS__,dbg6,dbg5,dbg4,dbg3,dbg2,dbg1)(__VA_ARGS__)
#else
#define dbg(...) {}
#endif

/* utility functions */
struct read_item{read_item(){};
template<class T>operator T(){T t;std::cin>>t;return t;}};
char splf(int i,int n){return(i+1<n)?' ':'\n';};
template<bool up>
struct _RI{int i;_RI(int a):i(a){}
int operator*(){return i;}void operator++(){i+=(up?1:-1);}
bool operator!=(const _RI& r){return up?i<r.i:i>=r.i;}};
template<bool up>
struct _RX{_RI<up> x,y;_RI<up> begin(){return x;}_RI<up> end(){return y;}
_RX(int a,int b):x(up?a:(a-1)),y(b){}_RX(int a):_RX(up?0:a,up?a:0){}};
typedef _RX<true> range;
typedef _RX<false> revrange;

/* types and constants */
typedef int64_t i64;
typedef uint64_t u64;
// const i64 inf = (i64)1.05e18;
// const int inf = (int)1.05e9;

using namespace std;

int main() {

	const int N = read_item();
	vector<vector<int>> g(N);
	for(auto i : range(N - 1)) {
		int a = (int)read_item() - 1;
		int b = (int)read_item() - 1;
		g[a].push_back(b);
		g[b].push_back(a);
	}

	vector<int> parity(N, -1);

	int zero = 0, one = 0;
	queue<pair<int,int>> q;
	q.push({0, 0});

	while(!q.empty()) {

		int v = q.front().first;
		int p = q.front().second;
		q.pop();

		if(parity[v] != -1) {
			continue;
		}
		parity[v] = p;
		if(p == 0) {
			zero += 1;
		} else {
			one += 1;
		}

		for(auto& w : g[v]) {
			q.push({w, 1 - p});
		}
	}

	int mini = min(zero, one);
	int mini_p = (zero < one) ? 0 : 1;

	int threes = N / 3;
	deque<int> nums;

	if(mini <= threes) {
		for(int i = 3; i <= N; i += 3) {
			nums.push_back(i);
		}
		for(int i = 1; i <= N; i += 3) {
			nums.push_back(i);
		}
		for(int i = 2; i <= N; i += 3) {
			nums.push_back(i);
		}
	} else {

	for(int i = 1; i <= N; i += 3) {
		nums.push_back(i);
	}
	for(int i = 3; i <= N; i += 3) {
		nums.push_back(i);
	}
	for(int i = 2; i <= N; i += 3) {
		nums.push_back(i);
	}

	}

	vector<int> ans(N);

	for(auto v : range(N)) {
		if(parity[v] == mini_p) {
			ans[v] = nums[0];
			nums.pop_front();
		}
	}
	for(auto v : range(N)) {
		if(parity[v] != mini_p) {
			ans[v] = nums[0];
			nums.pop_front();
		}
	}

	for(auto i : range(N)) {
		printf("%d%c", ans[i], splf(i, N));
	}

	return 0;
}

/* wafdayo~~~ */


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


int main() {
  int N;
  cin >> N;
  
  vector<int> vec(N);
  
  for (int i = 0; i < N; i++) {
    cin >> vec.at(i);
  }
  
  int sum =0;
  
  for (int i = 0; i < N; i+=2) {
    if(vec.at(i)%2==1){
      sum++;
    }
    else{
      sum+=0;
    }
  }
  cout << sum <<endl;

}


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

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  string s;
  cin >> s;
  int digits = 0;
  for (int i = 0; i < (int)s.length(); ++i){
		digits += s[i] - '0';
  }
  cout << ( (digits % 9 == 0) ? "Yes" : "No") << "\n";
 
return 0;
}


Measured memory_bytes: 3744
#include <bits/stdc++.h>
#define MP make_pair
#define F first
#define PB push_back
#define S second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
const int mod = (int)1e9 + 7;
const int maxn = 500 + 4;
const int inf = (int)1e9;

pii p[maxn];
int n, ted[maxn], Ted[maxn], a[maxn * maxn];

bool check() {
	for (int i = 1; i <= n * n; i++) {
		ted[a[i]] ++;
		if (ted[a[i]] == a[i]) {
			if (i != Ted[a[i]]) {
				return 0;
			}
		}
	}
	return 1;
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n;
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		p[i] = {x, i + 1};
		Ted[i + 1] = x;
	}
	sort (p, p + n);
	
	int ptr = 0, cnt = p[0].S;
	for (int i = 1; ptr < n and i <= n * n; i++) {
		if (a[i] != 0)
			continue;
		if (cnt > 1) {
			a[i] = p[ptr].S;
			cnt --;
			continue;
		}
		else {
			if (i > p[ptr].F) {
				return cout << "No" << endl, 0;
			}
			else {
				a[p[ptr].F] = p[ptr].S;
				if (p[ptr].F != i)
					i --;
				ptr ++;
				if (ptr < n)
					cnt = p[ptr].S;
				else
					break;
			}
		}
	}
	ptr = 0, cnt = n - p[0].S;
	for (int i = 1; i <= n * n; i++) {
		if (a[i] != 0)
			continue;
		while (cnt == 0) {
			ptr ++;
			cnt = n - p[ptr].S;
		}
		a[i] = p[ptr].S;
		cnt --;
	}
	if (!check()) {
		return cout << "No" << endl, 0;
	}
	cout << "Yes" << endl;
	for (int i = 1; i <= n * n; i++) {
		cout << a[i] << " ";
	}
}


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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF 1e16
#define mod 1000000007

ll X,n,q;
ll a[100010];
ll mn[100010],mx[100010],sum[100010];
ll hi[100010],lo[100010];

int main(){
  cin>>X>>n;
  rep(i,n)cin>>a[i];
  ll crtsum=0;
  mn[0]=0; mx[0]=X;
  sum[0]=0;
  rep(i,n){
    mx[i+1]=mx[i];
    mn[i+1]=mn[i];
    if(i%2==0){ // min
      ll crtmn=crtsum+a[i];
      if(mn[i]<crtmn){
        mn[i+1]=crtmn;
      }
    }else{ // max
      ll crtmx=X+crtsum-a[i];
      if(mx[i]>crtmx){
        mx[i+1]=crtmx;
      }
    }
    crtsum+=(i%2==0?a[i]:-a[i])*2;
    sum[i+1]=crtsum;
  }
  lo[0]=0; hi[0]=X;
  rep(i,n){
    hi[i+1]=hi[i]; lo[i+1]=lo[i];
    if(i%2==0){
      if(i>0){
        hi[i+1]-=a[i]-a[i-1]; lo[i+1]-=a[i]-a[i-1];
        maxch(hi[i+1],0LL); maxch(lo[i+1],0LL);
      }else{
        hi[i+1]-=a[i]; lo[i+1]-=a[i];
        maxch(hi[i+1],0LL); maxch(lo[i+1],0LL);
      }
    }else{
      hi[i+1]+=a[i]-a[i-1]; lo[i+1]+=a[i]-a[i-1];
      minch(hi[i+1],X); minch(lo[i+1],X);
    }
  }

  cin>>q;
  rep(i,q){
    ll T,A;
    cin>>T>>A;
    ll idx=lower_bound(a,a+n,T)-a;
    if(idx>0)T-=a[idx-1];
    if(A<=mn[idx]){
      if(idx%2==0) cout<<max(lo[idx]-T,0LL)<<endl;
      else cout<<min(lo[idx]+T,X)<<endl;
    }else if(A>=mx[idx]){
      if(idx%2==0) cout<<max(hi[idx]-T,0LL)<<endl;
      else cout<<min(hi[idx]+T,X)<<endl;
    }else{
      if(idx%2==0){
        cout<<max(0LL,A-sum[idx]-(idx>0?a[idx-1]:0)-T)<<endl;
      }else{
        cout<<min(X,A-sum[idx]+(idx>0?a[idx-1]:0)+T)<<endl;
      }
    }
  }
  return 0;
}


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

using namespace std;
int main()
{
	string s;
	cin >> s;

	if (s[0] == '9')
		cout << "Yes" << endl;
	
	else if (s[1] == '9')
		cout << "Yes" << endl;

	else 
		cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 384
/*
memo for solution
*/
#include <cstdlib> 
#include <numeric>
#include <cstring>
#include <cstdio> 
#include <cfloat> 
#include <map> 
#include <cassert>
#include <cmath> 
#include <climits> 
#include <utility> 
#include <set> 
#include <iostream> 
#include <memory> 
#include <string> 
#include <vector> 
#include <algorithm> 
#include <functional> 
#include <sstream> 
#include <complex> 
#include <stack> 
#include <queue> 
#include <iomanip>
#include<sys/time.h>
using namespace std; 
double e_time(void){static struct timeval now;gettimeofday(&now, NULL);return (double)(now.tv_sec  + now.tv_usec/1000000.0);}
#define REP(i,b,n) for(int i=b;i<n;i++) 
#define rep(i,n)      REP(i,0,n) 
#define pb push_back  
#define mp make_pair 
#define ALL(C)   (C).begin(),(C).end() 
#define fe(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr != (c).end();itr++)
#define BITSHIFT(X)     ( (1<<(X)) )
#define CONTAIN(S,X) ( ((S)&BITSHIFT(X)) != 0)
typedef complex<double>P; 
typedef long long ll; 
typedef unsigned long long ull; 
typedef pair<int,int> pii; 
typedef vector<int> vint;
template<class T> void vp(T &a,int p){rep(i,p)cout << a[i]<<" ";cout << endl;}  
template<class T> T ceilUp(const T& a,const T& b){return (a+b-1)/b;}
const ll mod =   1000000009;
inline ll modadd(ll a,ll b){a %= mod;b %= mod;return (a+b)%mod;}
inline ll modsub(ll a,ll b){a %= mod;b %= mod;a-=b;a%=mod;if (a<0)a+=mod;return a;}
inline ll modmul(ll a,ll b){a %= mod;b %= mod;return (a*b)%mod;}
inline ll modeq(ll a,ll b,ll m){a = (a%m+m)%m; b = (b%m+m)%m;return a == b;}
//ll modpow(ll n,ll p){if (p == 0)return 1;if (p == 1)return n;ll ret=mypow(n,p/2);ret=ret*ret%mod;if (p&1)ret=ret*n%mod;return ret;}
//ll getinv(ll a){return mypow(a,mod-2);}

int getAnswer(int n, int k){
  int ret = 1;
  if (n == 1)return 0;
  if (n <= k)return 1;
  n -= k;
  return 1 + ceilUp(n, k-1);
}

int solve(int n, int k, int pos1){
  int ret = n;
  for(int i = 1;i+k-1 <= n;i++){
    if (i <= pos1 && pos1 <= i+k-1){
      int left = getAnswer(i, k);
      int right = getAnswer(n - (i+k-1) + 1, k);

      ret = min(ret, 1 + left+  right);
    }
  }
  return ret;
}

int main(){
  int n, k;
  cin >> n >> k;
  int pos1 = 0;
  for(int i = 0;i < n;i++){
    int tmp;
    cin >> tmp;
    if (tmp == 1){
      pos1 = i+1;
    }
  }
  cout << solve(n, k, pos1) << endl;
  return 0;
}
 
 


Measured memory_bytes: 256