akhauriyash/Code-Regression huggingface dataset:
/* [Template].cpp 
Example code to use when starting new code. This particular problem was problem 
977A_Wrong_Subtraction from CodeForces

Compile: g++  -o E.exe E.cpp 
Execute: ./E
*/ 

#include <cstdio>
#include <iostream>
#include <cmath> 
#include <limits> 
#include <iomanip>
#include <cstring> 
#include <bits/stdc++.h>
#include <string>  
using namespace std;

int main() { 
	long long n, x, m;
	cin >> n >> x >> m;
	
	long long a[100001] = {0}; 
	bool already_visited[100001] = {false};
	a[1] = x;
	already_visited[x] = true;
	long long cycle_starter; 
	long long last_before_cycle_repeats = m; 
	for(int i = 2; 1==1 /*i <= m*/; i++) {
		a[i] = (a[i-1] * a[i-1]) % m; 
		if(already_visited[a[i]]) {
			last_before_cycle_repeats = i-1; 
			cycle_starter = a[i]; 
			break; 
		} else {
			already_visited[a[i]] = true; 
		}
		
		// Checking 
		// cout << a[i] << endl; 
	}
	
	long long s = 0; 
	for(int i = 1; i <= min(n, last_before_cycle_repeats); i++) {
		s += a[i]; 
		
		// Checking 
		// cout << i << "\t" << a[i] << endl; 
	}
	
	
	
	// Figure out the elements and length of cycle
	long long length_cycle = 1; 
	x = (cycle_starter * cycle_starter) % m; 
	long long sum_of_cycle = cycle_starter; 
	vector<long long> cycle_vector; 
	cycle_vector.push_back(cycle_starter); 
	while(x != cycle_starter) {
		length_cycle++; 
		sum_of_cycle += x; 
		cycle_vector.push_back(x); 
		x = (x*x) % m;
		
		// Checking 
		// cout << x << "\t" << cycle_starter << endl; 
	}
	
	long long num_repeats = (n-last_before_cycle_repeats) / length_cycle; 
	long long num_leftover = (n-last_before_cycle_repeats) % length_cycle; 
	
	long long sum_leftover = 0; 
	
	for(int i = 0; i < num_leftover; i++) {
		sum_leftover += cycle_vector[i]; 
	}
	
	long long result = 0; 
	if(n > last_before_cycle_repeats)
		result = s + num_repeats * sum_of_cycle + sum_leftover; 
	else 
		result = s; 
	
	// Checking
	/*
	cout << "Components: " << endl; 
	cout << "s = " << s << endl; 
	cout << "num_repeats = " << num_repeats << endl; 
	cout << "sum_of_cycle = " << sum_of_cycle << endl; 
	*/
	
	cout << result << endl; 
	
	return 0; 
} 


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

int p, q, a;

int FracEx(int num, int den, int pro, int n, int s)
{
	int cnt = 0;
	
	if (n < 0 || p * den < num * q) return 0;
	if (p * den == num * q) return 1;
	
	for (int i = s; i <= a; i++) {
		if (pro * i > a) break;
		cnt += FracEx(num * i + den, den * i, pro * i, n - 1, i);
	}
	
	return cnt;
}

int main()
{
	int n;
	
	while (cin >> p >> q >> a >> n, p | q | a | n) {
		cout << FracEx(0, 1, 1, n, 1) << endl;
	}
	
	return 0;
}

Measured memory_bytes: 1160
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		String line = sc.nextLine();

		if(line.equals("ARC")) {
			System.out.println("ABC");
		}else {
			System.out.println("ARC");
		}
	}

}


Measured memory_bytes: 35716
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fst first
#define snd second
using namespace std;

typedef long long ll;
typedef double db;
typedef long double ldb;

const int inf=1e9+10;
const int maxn=2e5+10;

int p[maxn],n,mn=inf,ans=0;

int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		int x;
		scanf("%d",&x);
		if(x<=mn) ans++,mn=x;
	}
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
//型に気を付けよう
//a=0x61=97 '0'=0x30=48
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long  ll;
typedef long double  ld;
typedef string str;
typedef pair<int,int> pairii;
typedef vector<int> veci;
const double pi=3.1415926535;
const ll  mod=1000000007;
//桁数指定　cout << fixed << setprecision(2)
long long MAX(vector<int> Vec){//配列の最大値
  int n=Vec.size();
  int max= -2147483647;
  for(int i=0;i<n;i++){
    if(max<Vec.at(i))max=Vec.at(i);
  }
  return max;}
long long MAX2(vector<int> v){//配列の最大値
  int n=v.size();int p=MAX(v);
  int max= -2147483647;
  rep(i,n){if(v[i]==p)v[i]=-2147483647;}
  for(int i=0;i<n;i++){
    if(max<v.at(i))max=v.at(i);
  }
  return max;}
int num_cnt(veci v,int a){//ｖの中にint aはいくつ？
  int cnt=0;
  for(unsigned int i=0;i<v.size();i++){
    if(v[i]==a){  
   cnt++;
    }
  }
  return cnt;
}
int main() {
  int n;
  cin>>n;
  veci v(n);
  rep(i,n)cin>>v[i];
  int m=MAX(v);
  int m2=MAX2(v);
  int c=num_cnt(v,m)-1;
  cerr<<MAX2(v);
  rep(j,n){
   if(c){cout<<m<<endl;}
   else if(v[j]==m){cout<<m2<<endl;}
    else cout<<m<<endl;
  }
}

Measured memory_bytes: 5544
#include <iostream>

using namespace std;
int main()
{

    int r,m,d;
    cin>>r>>m>>d;
    if(r==m)
    {
        cout<<d;
    }
    if(r==d)
    {
        cout<<m;
    }
    if(m==d)
    {
        cout<<r;
    }




    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define EPS 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LL long long
const int MOD = 1E9+7;
const int N = 100000+5;
const int dx[] = {-1,1,0,0,-1,-1,1,1};
const int dy[] = {0,0,-1,1,-1,1,-1,1};
using namespace std;

int a[N];
int main() {
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);

    int res=0;
    for(int i=1;i<=n-1;i++){
        if(a[i]==i){
            swap(a[i],a[i+1]);
            res++;
        }
    }
    if(a[n]==n)
        res++;
    printf("%d\n",res);

    return 0;
}

Measured memory_bytes: 640
#include<iostream>
using namespace std;
const int maxn=1e5+10;
int h[maxn];
int main()
{
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>h[i];
	}
	int t=0,ans=0;
	for(int i=1;i<n;i++)
	{
		if(h[i]<=h[i-1])
		{
			t++;
			ans=max(ans,t);
		}
		else t=0;
	}
	if(ans==0) cout<<"0"<<endl;
	else cout<<ans<<endl;
	return 0;
}

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

int main(){ int n, ac = 0, wa = 0, tle = 0, re = 0;
    cin >> n;
    for (int i=0; i<n; i++){ string code;
        cin >> code;
        if(code == "AC")
            ac++;
        else if(code == "WA")
            wa++;
        else if(code == "TLE")
            tle++;
        else if(code == "RE")
            re++;
    }
    cout << "AC x " << ac << endl;
    cout << "WA x " << wa << endl;
    cout << "TLE x " << tle << endl;
    cout << "RE x " << re << endl;
    return 0;
}

Measured memory_bytes: 3608
# define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(){
    int X = 0;
    int b = 0;
    int p = 2;
    int max_b = 0;
    int temp = 0;
    int ans = 0;
    int loop = 0;

    scanf("%d", &X);

    max_b = sqrt(X);

    for (b = 2; b <= max_b; b++){
        while (2 <= p){
            temp = pow(b, p);
            if (X < temp){
                p--;
                break;
            }
            p++;
        }
        if (ans < pow(b, p)){
            ans = pow(b, p);
        }
        p = 2;
    }
    if (1 == X){
        ans = 1;
    }

    printf("%d", ans);
    

    return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<cstdio>
using namespace std;
#define MAX 200200
inline int read()
{
    int x=0;bool t=false;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=true,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return t?-x:x;
}
int n,a[MAX],val[MAX],cnt[MAX];
char s[MAX];
struct SegmentTree
{
#define lson (now<<1)
#define rson (now<<1|1)
    int t[MAX<<2];
    void Build(int now,int l,int r)
    {
        if(l==r){t[now]=1-1e9;return;}
        int mid=(l+r)>>1;
        Build(lson,l,mid);Build(rson,mid+1,r);
        t[now]=max(t[lson],t[rson]);
    }
    void Modify(int now,int l,int r,int p,int w)
    {
        if(l==r){t[now]=w;return;}
        int mid=(l+r)>>1;
        if(p<=mid)Modify(lson,l,mid,p,w);
        else Modify(rson,mid+1,r,p,w);
        t[now]=max(t[lson],t[rson]);
    }
    int Query(int now,int l,int r,int L,int R)
    {
        if(L<=l&&r<=R)return t[now];
        int mid=(l+r)>>1,ret=-1e9;
        if(L<=mid)ret=max(ret,Query(lson,l,mid,L,R));
        if(R>mid)ret=max(ret,Query(rson,mid+1,r,L,R));
        return ret;
    }
}Odd,Even;
bool check(int mx,int Q)
{
    if(Q<0)return false;
    if(Q&1)return Odd.Query(1,1,n,mx,n)>=Q;
    else return Even.Query(1,1,n,mx,n)>=Q;
}
int main()
{
    n=read();
    for(int i=1,mx=0;i<=n;++i)
    {
        a[i]=read();
        if(a[i]>mx)val[i]=2,mx=a[i];
        else val[i]=1;
    }
    Odd.Build(1,1,n);
    for(int i=n;i;--i)
    {
        int mx1=Odd.Query(1,1,n,a[i],n),mx0=Even.Query(1,1,n,a[i],n);
        if(val[i]&1)Odd.Modify(1,1,n,a[i],mx0+val[i]),Even.Modify(1,1,n,a[i],mx1+val[i]);
        else Odd.Modify(1,1,n,a[i],mx1+val[i]),Even.Modify(1,1,n,a[i],mx0+val[i]);
    }
    for(int i=n;i;--i)cnt[i]=cnt[i+1]+val[i]-1;
    int cntX=0,cntY=0,mxX=0,mxY=0;
    for(int i=1;i<=n;++i)
    {
        Odd.Modify(1,1,n,a[i],1-1e9);Even.Modify(1,1,n,a[i],0);
        if(check(mxY,cntX+cnt[i+1]-cntY+(a[i]>mxX)))s[i]='0',cntX+=a[i]>mxX,mxX=max(mxX,a[i]);
        else if(check(max(mxX,a[i]),cntY+cnt[i+1]-cntX-(a[i]>mxX)))s[i]='0',cntX+=a[i]>mxX,mxX=max(mxX,a[i]);
        else s[i]='1',cntY+=a[i]>mxY,mxY=max(mxY,a[i]);
    }
    if(cntX!=cntY){puts("-1");}
    else printf("%s",s+1);
    return 0;
}

Measured memory_bytes: 9216
#include <iostream>

using namespace std;

int main() {
    int N, K;
    cin >> N >> K;
    int idx=0;
    for(int n=0; n<N; n++) {
        int A;
        cin >> A;
        if(A==1) idx=n;
    }
    
    int ans=(N-K)/(K-1);
    if((N-K)%(K-1)) ans++;
    cout << ans+1 << endl;


    return 0;
    
}

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

int main() {
    int d=1;
    string s; cin>>s;
    int n=s.length();
    for(int i=0; i<n; i++){
        if(s[i]!=s[n-1-i]){
            d=0;
            break;
        }
    }
   
    for(int i=0; i<(n-1)/2; i++){
        if(s[i]!=s[ ((n-1)/2) -1-i]){
            d=0;
            break;
        }
    }
  
    for(int i=(n+1)/2; i<n; i++){
        if(s[i]!=s[n-1-(i-(n+1)/2)]){
            d=0;
            break;
        }
    }
    if(d){
        cout<<"Yes";
    }
    else{
        cout<<"No";
    }
    
	return 0;
}

Measured memory_bytes: 256
package main

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

var sc = bufio.NewScanner(os.Stdin)

func init() {
	sc.Split(bufio.ScanWords)
}

func nextInt() int64 {
	sc.Scan()
	i, e := strconv.ParseInt(sc.Text(), 10, 64)
	if e != nil {
		panic(e)
	}
	return i
}

func nextLine() string {
	sc.Scan()
	return sc.Text()
}

func main() {
	a, b, c, d := nextInt(), nextInt(), nextInt(), nextInt()
	// var re int64

	l := Lcm(int(c), int(d))

	fn := func(v int64) int64 {
		return v - (v/c + v/d) + v/int64(l)
	}

	aa := fn(a - 1)

	bb := fn(b)

	fmt.Printf("%#v\n", bb-aa)
}

// greatest common divisor (GCD) via Euclidean algorithm
func Gcd(a, b int) int {
	for b != 0 {
		t := b
		b = a % b
		a = t
	}
	return a
}

// find Least Common Multiple (LCM) via GCD
func Lcm(a, b int, integers ...int) int {
	result := a * b / Gcd(a, b)

	for i := 0; i < len(integers); i++ {
		result = Lcm(result, integers[i])
	}

	return result
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
int main() {
  string s;
  cin >> s;  
  for(int i = s.size()-2; ; i -= 2) {
    if(s.substr(0, i/2) == s.substr(i/2, i/2)) {
      cout << i << "\n";
      return 0;
    }
  }
}

Measured memory_bytes: 256
N, K = map(int, input().split())
p = list(map(int, input().split()))
  
# 「和の期待値」は「期待値の和」なので、期待値を求めておく
for i in range(N):
  p[i] = (1+p[i])/2

# すると結局[(p_1+1)/2,...,(p_N+1)/2]の配列から、隣接するK個の和の最大値を求めればよい
# N=10^5なので、O(N)で解く
# 2重ループは間に合わない・・・累積和！
# 累積和によって、配列上の区間の総和を求める処理を高速化！
S = [0]*(N+1)
for i in range(N):
  S[i+1] = S[i] + p[i]
'''
S[0] = 0
S[1] = p[0]
S[2] = p[0] + p[1]
S[N] = p[0] + ... + p[N-1]

S[K]-S[0] = p[K-1] + ... + p[0]
S[K+1]-S[1] = p[K] + ... + p[1]
S[K+2]-S[2] = p[K+1] + ... + p[2]
S[N]-S[N-K] = p[N-1] + ... + p[N-K]
'''

ans = 0
# max(S[K]-S[0],S[K+1]-S[1],...,S[N]-S[N-K]) を求める
for i in range(N-K+1):
  ans = max(ans, S[i+K] - S[i])
  
print(ans)

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

using namespace std;

using i64 = long;

const i64 MOD = 1e9 + 7;
const i64 INF = 1e18 + 7;


signed main(){
    i64 n;
    cin >> n;
    i64 m = sqrt(n) + 1;
    i64 ans = INF;
    for(i64 i = 1; i <= m; ++i){
        i64 j = n / i;
        if(i * j == n){
            ans = min(ans, i + j - 2);
        }
    }
    cout << ans << endl;
}


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

ll C2(ll x)
{
    if (x < 2) return 0;
    return x * (x-1) / 2;
}
int main()
{
    ll n, k; cin >> n >> k;
    ll count  = C2(n-1);
    if (count < k){
        cout << -1 << endl;
        return 0;
    }
    cout << n - 1 + count - k << endl;
    for (ll i = 2; i <= n; i++)
        cout << 1 << ' ' << i << endl;
    for (ll i = 2; i <= n-1; i++)
    {
        for (ll j = i+1; j <= n; j++)
        {
            if (count == k) break;
            cout << i << ' ' << j << endl;
            count--;
        }
        if(count == k) break;
    }   
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i,n,k) for(int i=(n);i<(k);i++)
#define ALL(a)  (a).begin(),(a).end()
int d=365, n=26, score=0;
int c[27];
int s[366][27];
int sat[366]={};
int last[27]={};
vector<int> a(366,0);
int range = 7;
ofstream fout("out.txt"), flog("log.txt");
uint64_t get_rand_range( uint64_t min_val, uint64_t max_val ) {

    srand((int)time(NULL));
    static mt19937_64 mt64(rand());

    uniform_int_distribution<uint64_t> get_rand_uni_int( min_val, max_val );

    return get_rand_uni_int(mt64);
}

int calcdiff(int t, int q,vector<int> &a){
    int p=a[t];
    int lp=0,rp=d+1,lq=0,rq=d+1;
    For(i,1,d+1){
        if(a[i]==p){
            if(i<t) lp=max(lp,i);
            else if(i>t) rp=min(rp,i);
        }
        if(a[i]==q){
            if(i<t) lq=max(lq,i);
            else if(i>t) rq=min(rq,i);
        }
    }
    int diff=s[t][q]-s[t][p];
    diff -= (t-lp) * (rp-t) * c[p];
    diff += (t-lq) * (rq-t) * c[q];
    return diff;
}

void greedy(){
    For(i,1,d+1){
        int mx = -(1<<30), acc = -1;
        For(con,1,n+1){
            int sati = sat[i-1] + s[i][con];
            For(j,1,n+1){
                if(j != con) sati -= (i-last[j]) * c[j];
            }
            if(mx<sati){
                mx = sati;
                acc = con;
            }
        }
        last[acc] = i;
        sat[i] = mx;
        a[i]=acc;
    }    
    score = sat[d];
}

void Main(){
    clock_t start = clock();
    cin >> d;
    For(i,1,n+1) cin >> c[i];
    For(i,1,d+1) For(j,1,n+1) cin >> s[i][j];
    greedy();
    priority_queue< pair<int,vector<int>>, vector<pair<int,vector<int>>>, greater<pair<int,vector<int>>> > que;
    que.push(make_pair(score,a));
    double time = static_cast<double>(clock() - start) / CLOCKS_PER_SEC * 1000.0;
    while(time < 1950){
        int t = get_rand_range(1,d);
        int q = get_rand_range(1,n);
        priority_queue< pair<int,vector<int>>, vector<pair<int,vector<int>>>, greater<pair<int,vector<int>>> > nque;
        while(!que.empty()){
            auto p = que.top();
            que.pop();
            nque.push(p);
            int diff = calcdiff(t,q,p.second);
            p.second[t]=q;
            p.first+=diff;
            nque.push(p);
        }
        while(nque.size()>range) nque.pop();
        swap(nque,que);
        time = static_cast<double>(clock() - start) / CLOCKS_PER_SEC * 1000.0;
    }
    while(que.size()>1) que.pop();
    auto p = que.top();
    For(i,1,d+1) cout << p.second[i] << endl;

}
int main(){
    Main();
    /*
    東方風神録は神が出てくるので当然神ゲー
    */
    return 0;
}

Measured memory_bytes: 3684
use v5.18;
use warnings;
use utf8;
use Data::Dumper;
use List::Util qw( min max );
use Test::More;

sub line { chomp(my $str = <>); $str; }
sub split_line { (split / /, line) }

main();

sub main {
  my ($s, $c) = split_line;
  say solve($s, $c);
}

sub solve {
  my ($s, $c) = @_;
  if ($s * 2 > $c) {
    int $c / 2;
  }
  elsif ($s * 2 == $c) {
    $s;
  } else {
    my $lack = $c - $s * 2;
    $s + int( $lack / 4 );
  }
}



Measured memory_bytes: 3452
//For higher stack size use g++ -O2 -std=c++11 -Wall -Wl,--stack=268435456 a.cpp -o a.exe in cmd
    #include <bits/stdc++.h>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <cstring>
    #include <chrono>
    #include <complex>
    #define ll long long
    #define ld long double
    #define vi vector<int>
    #define vll vector<ll>
    #define vvi vector < vi >
    #define pii pair<int,int>
    #define pll pair<long long, long long>
    #define mod 1000000007
    #define inf 1000000000000000001;
    #define all(c) c.begin(),c.end()
    #define mp(x,y) make_pair(x,y)
    #define mem(a,val) memset(a,val,sizeof(a))
    #define eb emplace_back
    #define pb push_back
    #define f first
    #define s second
    
    using namespace std;
    int main()
    {
        std::ios::sync_with_stdio(false);
        int T;
        T=1;
        // cin.ignore(); must be there when using getline(cin, s)
        while(T--)
        {
            int n,i,j;
            cin>>n;
            ll ar[n+1],ans=0,pre=0;
            for(i=1;i<=n;++i)
            {
                cin>>ar[i];
                if(ar[i]>=pre)
                {
                    pre=ar[i];
                }
                else
                {
                    ans=ans+pre-ar[i];
                }
            }
            cout<<ans<<endl;
        }
        return 0;
    }


Measured memory_bytes: 5216
class ReRooting(object):
    """ 全方位木DP """
    def merge(self, a, b):
        """ 二項演算 a・b """
        return a * b % M

    def adj_bu(self, a, v:int):
        """
        Bottom-Upの単項演算 g(a)

        v: 頂点
        """
        return a + 1

    def adj_td(self, a, v:int, p:int):
        """
        Top-Downの単項演算 g(a)

        v: 頂点
        p: 親
        """
        return a + 1

    def adj_fin(self, a, v:int):
        """
        最終結果の単項演算 g(a)

        v: 頂点
        """
        return a

    def __init__(self, V:int, e:int):
        """
        V: 頂点数
        e: 単位元
        """
        self.V = V
        self.e = e
        self.edge = [[] for _ in range(V)]
        self.par = [-1] * V
        self.order = []
    
    def add_edge(self, u:int, v:int):
        """ 辺(u,v)をグラフに追加する """
        self.edge[u].append(v)
        self.edge[v].append(u)
    
    def topological_sort(self, root:int = 0):
        """ トポロジカルソート """
        from collections import deque
        que = deque([root])
        while que:
            v = que.popleft()
            self.order.append(v)
            for w in self.edge[v]:
                if w != self.par[v]:
                    self.par[w] = v
                    self.edge[w].remove(v)
                    que.append(w)
    
    def bottom_up(self):
        """ Bottom-Up DP """
        root = self.order[0]
        accBU = [self.e] * self.V
        resBU = [self.e] * self.V

        for v in reversed(self.order):
            resBU[v] = self.adj_bu(accBU[v], v)

            if v == root: break

            p = self.par[v]
            accBU[p] = self.merge(accBU[p], resBU[v])
        return accBU, resBU
    
    def top_down(self, resBU:list):
        """ Top-Down DP """
        accTD = [self.e] * self.V
        resTD = [self.e] * self.V

        for p in self.order:
            # 左からaccTDを更新
            ac = resTD[p]
            for v in self.edge[p]:
                accTD[v] = ac
                ac = self.merge(ac, resBU[v])

            # 右からaccTDを更新
            ac = self.e
            for v in reversed(self.edge[p]):
                accTD[v] = self.merge(accTD[v], ac)
                ac = self.merge(ac, resBU[v])
                resTD[v] = self.adj_td(accTD[v], v, p)
        return resTD
    
    def solve(self):
        self.topological_sort()
        accBU, resBU = self.bottom_up()
        resTD = self.top_down(resBU)

        res = [self.adj_fin(self.merge(a, b), v) for v,(a,b) in enumerate(zip(accBU, resTD))]

        return res

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

RR = ReRooting(N, 1)
for _ in range(N - 1):
    x, y = map(int, input().split())
    RR.add_edge(x - 1, y - 1)

print(*RR.solve(), sep="\n")

Measured memory_bytes: 35824
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <map>



int main() {
	int a, b; std::cin >> a >> b;
	if (a >= 13) {
		std::cout << b << std::endl;
	}
	else if (a >= 6) {
		std::cout << b / 2 << std::endl;
	}
	else {
		std::cout << 0 << std::endl;
	}
}

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


using namespace std;

using ll   = long long;
using ii   = pair   < int , int >;
using i3   = pair   < int , ii  >;
using li   = pair   < ll  , int >;
using lii  = pair   < ll  , ii  >;
using pll  = pair   < ll  , ll  >;
using vi   = vector < int       >;
using vl   = vector < ll        >;
using vii  = vector < ii        >;
using vli  = vector < li        >;
using vpll = vector < pll       >;
using vi3  = vector < i3        >;
using vlii = vector < lii       >;


const int N = 2e5 + 5;
const ll INF = 1e17 + 7;
const double eps = 1e-9 , PI = acos(-1);



int n , m;


void solve(int testCase){

    scanf("%d %d" , &n , &m);

    vi a(m);
    for(int i = 0 ; i < m ; i ++){
            scanf("%d" , &a[i]);
    }
    sort(a.begin() , a.end());

    int mx = 0;
    for(int i = 0 ; i < m-1 ; i ++){
            mx = max(mx , abs(a[i] - a[i+1]));
    }
    mx = max(mx , a[0] + n - a[m-1]);


    printf("%d\n" , n - mx);


}

main(){

    int t = 1;
    // scanf("%d" , &t);

    for(int testCase = 1 ; testCase <= t ; testCase ++){
            solve(testCase);
    }

    return 0;
}


Measured memory_bytes: 1152
n = int(input())
data = [int(x) for x in input().split()]
cnt = [0]*(n+1)

# ボールに書かれた整数を集計する
for x in data:
    cnt[x] += 1

total = int(sum([x*(x-1)/2 for x in cnt]))

for k in range(n):
    answer = total - cnt[data[k]] + 1
    print(answer)

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

int main(){
    char a, b;
    cin >> a >> b;
    if(a == 'H'){
        cout << b << endl;
    }
    else{
        if(b == 'H') puts("D");
        else puts("H");
    }
}

Measured memory_bytes: 3640
#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <cassert>
using namespace std;
typedef long long ll;

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

	ll A, B, N;
	cin >> A >> B >> N;

	ll ans = 1LL << 50;
	for(int i = 1; i <= N; i++) {
		for(int j = 1; j <= N; j++) {
			if(B * i % j != 0) continue;
			ll x = B * i / j - A;
			if(A + x < 0) continue;
			ans = min(ans, abs(x));
		}
	}

	cout << ans << endl;
}

Measured memory_bytes: 3168
#include <bits/stdc++.h>
using namespace std;
 
int n, b=0;
 
int main (){
	cin >>n;
	for(int i=1;i<=9;i++){
		for(int j=1;j<=9;j++){
			if(i*j==n)
			b++;
		}
	}
	if(b>0) cout << "Yes";
	else cout << "No";
}

//semogabisa


Measured memory_bytes: 256
import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {

	public static void solve() {
		int x=s.nextInt();
		boolean[] poss = new boolean[x+1];
		poss[0]=true;
		int[] arr = {100,101,102,103,104,105};
		for(int i=0;i<=x;i++) {
			if(poss[i]) {
				for(int j= 0;j<arr.length;j++) {
					if(i+arr[j]<=x) {
						poss[i+arr[j]]=true;
					}
				}
			}
		}
		if(poss[x]) {
			out.println(1);
		}else {
			out.println(0);
		}
	}

	public static void main(String[] args) {
		out = new PrintWriter(new BufferedOutputStream(System.out));
		s = new FastReader();
		solve();
		out.close();
	}

	public static FastReader s;
	public static PrintWriter out;

	public static class FastReader {
		BufferedReader br;
		StringTokenizer st;

		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (Exception e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (Exception e) {
				e.printStackTrace();
			}
			return str;
		}
	}

	
}


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

#define debug(a) cout << #a << " " << a << endl;
#define _debug(a, i) cout << #a << "[" << i << "]" << " = " << a[i] << endl;
#define fastio ios_base::sync_with_stdio(false); \
		cin.tie(0);							     \
		cout.tie(0);
#define sz(arr) (int)arr.size()

using namespace std;
using ll = long long;
const ll MOD = 998244353;
const ll INF = 1e9 + 9;
const double PI = 4.0 * atan(1.0);

ll powmod(ll a, ll b,const ll MOD) { ll res = 1; a %= MOD; assert(b >= 0); for (; b; b >>= 1) { if (b & 1)res = res * a % MOD; a = a * a % MOD; } return res; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll modInverse(ll n, const ll p) { return powmod(n, p - 2, p);}




int main() {
	//#ifndef ONLINE_JUDGE
	//	(void)freopen("input.txt", "r", stdin);
	//	(void)freopen("output.txt", "w", stdout);
	//#endif // !ONLINE_JUDGE
		//  ======= FAST I/O =========
	fastio;
	//  ==========================
	int a[4][4];
	for (int i = 1; i <= 3; ++i) {
		for (int j = 1; j <= 3; ++j)
			cin >> a[i][j];
	}
	int n;
	cin >> n;
	while (n--) {
		int x;
		cin >> x;
		for (int i = 1; i <= 3; ++i) {
			for (int j = 1; j <= 3; ++j) {
				if (x == a[i][j]) {
					a[i][j] = -1; // marked
					break;
				}
			}
		}
	}
	int r1 = a[1][1] + a[1][2] + a[1][3];
	int r2 = a[2][1] + a[2][2] + a[2][3];
	int r3 = a[3][1] + a[3][2] + a[3][3];
	int c1 = a[1][1] + a[2][1] + a[3][1];
	int c2 = a[1][2] + a[2][2] + a[3][2];
	int c3 = a[1][3] + a[2][3] + a[3][3];
	int d1 = a[1][1] + a[2][2] + a[3][3];
	int d2 = a[1][3] + a[2][2] + a[3][1];
	if (r1 == -3 || r2 == -3 || r3 == -3
		|| c1 == -3 || c2 == -3 || c3 == -3 || d1 == -3 || d2 == -3) {
		cout << "Yes";
		return 0;
	}
	cout << "No";
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long long k, dem;
string s;

int main(){
    cin >> s >> k;
    if (s[0] == '1'){
        dem = 0;
        for (int i = 0; i < s.size(); i++){
            if (s[i] == '1') dem++;
            else break;
        }
        if (k <= dem) cout << 1;
        else cout << s[dem];
    }
    else cout << s[0];
    return 0;
}

Measured memory_bytes: 256
/*#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>

#include <boost/rational.hpp>
*/
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
using ll = long long;
using ld = long double;
#define rep2(i, s, n) for (ll i = (s); i < (ll)(n); i++)
#define rep3(i, n) for (ll i = 1; i < (ll)(n+1); i++)
#define rep4(i, s, n) for (ll i = (s); i < (ll)(n+1); i++)
#define repr(i,n) for (ll i = (n-1); i>=0;i--)
#define repr3(i,n) for(ll i = (n);i>0;i--)
#define repr4(i,s,n) for(ll i = (n);i>=(s);i--)
#define stlen(s) ll s.size()-1
#define all(v) v.begin(), v.end()
#define cout(n) cout<<std::fixed<<std::setprecision(n)
using Graph = vector<vector<int>>;
using Graphw = vector<vector<pair<ll,ll>>>;
#define INF1  INT_MAX;
#define INF2  LLONG_MAX;
#define PI  3.14159265358979323846;
#define MOD 1000000007;
/*
namespace mp = boost::multiprecision;
// 任意長整数型
using Bint = mp::cpp_int;
// 仮数部長が32の浮動小数点数型
using Real32 = mp::number<mp::cpp_dec_float<32>>;
// 仮数部長が1024の浮動小数点数型
using Real1024 = mp::number<mp::cpp_dec_float<1024>>;
// 有理数型
using Rat = boost::rational<Bint>;
*/


int main(){
int X,Y,A,B,C;
cin>>X>>Y>>A>>B>>C;
ll red[A],gre[B],sk[C];
rep(i,A){
    cin>>red[i];

}
rep(i,B){
    cin>>gre[i];
}
rep(i,C){
    cin>>sk[i];
}
int Xcp=X,Ycp=Y;
sort(red,red+A);
reverse(red,red+A);
sort(gre,gre+B);
reverse(gre,gre+B);
sort(sk,sk+C);

while(C>0){
    if((Xcp>0)&&(red[Xcp-1]<=gre[Ycp-1])&&(red[Xcp-1]<sk[C-1])){
        red[Xcp-1]=sk[C-1];
        Xcp--;
        C--;
    }
    else if((Ycp>0)&&(red[Xcp-1]>=gre[Ycp-1])&&(gre[Ycp-1]<sk[C-1])){
        gre[Ycp-1]=sk[C-1];
        Ycp--;
        C--;
    }
    else{
        break;
    }
}
ll ans=0;
rep(i,X){
    ans+=red[i];
}
rep(i,Y){
    ans+=gre[i];
}
cout<<ans<<endl;
return 0;
}

Measured memory_bytes: 5940
#include <stdio.h>
#include <algorithm>
 
using namespace std;
 
int main(){
    int H,W;
    while(true){
        scanf("%d %d",&H,&W);
        if(H == 0 && W == 0) break;
        for(int i = 0; i < H; i++){
            for(int j = 0; j < W; j++){
                printf("#");
            }
            printf("\n");
        }
        printf("\n");
    }
}


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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<long long> vll;
typedef vector<vector<long long>> vvll;
typedef pair<int,int> pii;
typedef pair<long long, int> pli;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

ll mod = 1000000007;

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

ll inv(ll x){
  ll res = 1;
  ll k = mod - 2;
  ll y = x;
  while(k){
    if(k&1)res = (res*y)%mod;
    y = (y*y) % mod;
    k /= 2;
  }
  return res;
}


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

  int k;
  cin >> k;
  string s;
  cin >> s;

  int n = s.length();

  vll pw(n+k+1);
  pw[0] = 1;
  rep(i,n+k) pw[i+1] = pw[i] * 25 % mod;

  vll fact(n+k+1);
  fact[0] = 1;
  rep(i,n+k) fact[i+1] = fact[i] * (i+1) % mod;

  ll rm = 0;
  for(int c = 0;c <= n-1;c++){
    ll cur = pw[n+k-c];
    ll cmb = (fact[n+k] * inv(fact[c]) % mod) * inv(fact[n+k-c]) % mod;
    cur = cur * cmb % mod;
    rm = (rm + cur) % mod;
  }

  ll ret = 1;
  rep(i,n+k)ret = ret * 26 % mod;

  ret -= rm;
  if(ret < 0)ret += mod;
  cout << ret << endl;
}

Measured memory_bytes: 35652
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

int main()
{
    long n, b;
    int a[3][3], res[3][3];

    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            std::cin >> a[i][j];
            res[i][j] = 0;
        }
    }

    std::cin >> n;
    for (int k = 0; k < n; k++)
    {
        std::cin >> b;
        for (int i = 0; i < 3; i++)
        {
            for (int j = 0; j < 3; j++)
            {
                if (a[i][j] == b)
                {
                    res[i][j] = 1;
                    break;
                }
            }
        }
    }

    bool flag = false;
    for (int i = 0; i < 3; i++)
    {
        if (res[i][0] == 1 && res[i][1] == 1 && res[i][2] == 1)
        {
            flag = true;
            break;
        }
        if (res[0][i] == 1 && res[1][i] == 1 && res[2][i] == 1)
        {
            flag = true;
            break;
        }
    }
    if (!flag && res[1][1] == 1)
    {
        if ((res[0][0] == 1 && res[2][2] == 1) || (res[0][2] == 1 && res[2][0] == 1))
        {
            flag = true;
        }
    }

    std::cout << (flag ? "Yes" : "No") << std::endl;
}

Measured memory_bytes: 256
#include <stdio.h>
int main()
{
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	if(a>c&&c>b)
	  printf("Yes");
	else if(a<c&&c<b)
		   printf("Yes");
	else
	  printf("No");
	return 0;
}

Measured memory_bytes: 128
#!/usr/bin/env python3
import math

n = int(input())

mod = 10**9+7

data = {}
zero_zero = 0

for i in range(n):
    a, b = list(map(int, input().split()))
    # # print(a, b)
    if a == 0 and b == 0:
        zero_zero += 1
        continue
    gcd = math.gcd(a, b)
    a, b = a//gcd, b//gcd
    if a < 0:
        a, b = -a, -b

    if a == 0:  # (0, 1)
        a, b = 0, 1

    elif b == 0:  # (1, 0)
        a, b = 1, 0

    # print(a, b)
    # print()

    if b <= 0:  # (+, -) or (1, 0)
        if (-b, a) in data:
            data[(-b, a)][1] += 1
        else:
            data[(-b, a)] = [0, 1]
    elif b > 0:  # (+, +) or (1, 0)
        if (a, b) in data:
            data[(a, b)][0] += 1
        else:
            data[(a, b)] = [1, 0]

# print(data)
# print(zero_zero)

power_2 = [1]
for i in range(1, 2*10**5+100):
    power_2.append(power_2[i-1]*2 % mod)

ans = 1
# print(ans)
# print()
for (a, b), (l, m) in data.items():
    ans *= (power_2[l]+power_2[m]-1) % mod
    # print(power_2[l]+power_2[m]-1)
    # print(ans)
    # print()

ans = ans - 1  # removed not selected
ans += zero_zero
print(ans % mod)
# count_pp = 0
# count_pm = 0
# ans = 0
# while(1):
#     pp_tmp = plus_plus[count_pp]
#     pm_tmp = plus_minus[count_pm]

#     print("pp_tmp", pp_tmp)
#     print("pm_tmp", pm_tmp)

#     if pp_tmp[0]*pm_tmp[0] + pp_tmp[1]*pm_tmp[1] == 0:
#         pp_mag, pm_mag = 1, 1  # magnitude
#         while(1):
#             if count_pp < len(plus_plus)-1:
#                 if plus_plus[count_pp] == plus_plus[count_pp+1]:
#                     pp_mag += 1
#                     count_pp += 1
#                 else:
#                     break
#             else:
#                 break
#         while(1):
#             if count_pm < len(plus_minus)-1:
#                 if plus_minus[count_pm] == plus_minus[count_pm+1]:
#                     pm_mag += 1
#                     count_pm += 1
#                 else:
#                     break
#             else:
#                 break
#         ans += pp_mag*pm_mag

#     elif pp_tmp[2]*pm_tmp[2] > -1:
#         count_pp += 1

#     elif pp_tmp[2]*pm_tmp[2] < -1:
#         count_pm += 1

#     if count_pp == len(plus_plus)-1:
#         break
#     if count_pm == len(plus_minus)-1:
#         break
#     print(1)

# ans += zero_zero
# n = n - zero_zero
# count = ((n % mod) * ((n-1) % mod))//2
# count -= (negative) % mod

# print(count % mod)


Measured memory_bytes: 68212
using System;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using System.Text;


class Program
{
    static void Main(string[] args)
    {
        // 入力
        int[] nm = Console.ReadLine().Split().Select(int.Parse).ToArray();
        int n = nm[0];
        int m = nm[1];
        var s = Console.ReadLine();
        var t = Console.ReadLine();

        long ans = 0;
        var ok = true;
        long lcm = Lcm(n, m);
        long gcd = Gcd(n, m);

        for (int i = 0; i < gcd; ++i)
        {
            if (i == 0)
            {
                if (s[i] != t[i])
                {
                    ok = false;
                    break;
                }
            }
            else if (s[i * n / (int)gcd] != t[i * m / (int)gcd])
            {
                ok = false;
                break;
            }
        }

        if (ok)
        {
            ans = lcm;
        }
        else
        {
            ans = -1;
        }

        // 出力
        Console.WriteLine(ans);
    }

    // 最小公倍数
    public static long Lcm(long a, long b)
    {
        return a * b / Gcd(a, b);
    }

    // ユークリッドの互除法 
    public static long Gcd(long a, long b)
    {
        if (a < b)
            // 引数を入替えて自分を呼び出す
            return Gcd(b, a);
        while (b != 0)
        {
            var remainder = a % b;
            a = b;
            b = remainder;
        }
        return a;
    }
}


Measured memory_bytes: 13792
# include <stdio.h>
# include <stdlib.h>
# define MAX 100002
int main()
{
    long n;
    int d[MAX];
    int c[MAX];
    long k;
    scanf("%ld",&n);
    for (int i = 1; i < n+1; i++)
    {
        scanf("%d",&d[i]);
    }
    //printf("%c",index);
    for (int i = 1; i < n+1; i++)
    {
        k = d[i];
        c[k] = i;
    }
    for (int i = 1; i < n+1; i++)
    {
        printf("%d ",c[i]);
    }
    
    system("pause");
    return 0;

}

Measured memory_bytes: 1784
// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#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 pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
//#define int ll
typedef int 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-7;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9+10;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int main(){
	int a,b,c;
	cin>>a>>b>>c;
	if(b-a<2*c){
		loop(i,a,b+1)cout<<i<<endl;
	}else{
		loop(i,a,a+c)cout<<i<<endl;
		loop(i,b+1-c,b+1)cout<<i<<endl;
	}
}






Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define ANS cout << ans << endl
#define all(a) a.begin(),a.end()
#define SORT(a) sort(all(a))
#define REVERSE(a) reverse(all(a))
#define int long long
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define VIin(a) for(int i=0; i<a.size(); i++) cin >> a[i]
#define OUT(a) cout << a << endl
typedef vector<int> VI;
typedef vector<VI> VVI;
const int MOD=1e9+7;
const long long INF = 1LL << 60;
/*最大公約数*/int gcd(int x, int y) { return y ? gcd(y,x%y) : x;}
/*最小公倍数*/int lcm(int a, int b) { int g = gcd(a, b); return a / g * b; }
/*素数判定*/int isPrime(int n){if(n<2){return 0;}for(int i=2; i*i<=n; i++){if(n%i==0){return 0;}}return 1;}
/*約数列挙*/vector<int> getDivisor(int n){vector<int> v; for(int i=1; i*i<=n; i++){if(n%i==0){v.push_back(i);if(i!=n/i){v.push_back(n/i);}}}sort(v.begin(),v.end()); return v;}
//----------------------------------------------
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int a,b; cin >> a >> b;
    if(b % a == 0) OUT(a+b);
    else OUT(b-a);

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main(void) {
    int N,K,i,S;
    S=0;
    unsigned int *h;
    scanf("%d",&N);
    scanf("%d",&K);
    h=(int*)malloc(sizeof(int)*N);
    for(i=0;i<N;i++){
	scanf ("%d",&h[i]);
    	}
    for(i=0;i<N;i++){
	if(h[i]>=K){
		S++;
	}
    }
    printf("%d\n",S);
    return 0;
}

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

using namespace std;

int main() {

    long long int N=0, A=0, B=0, r=0, q=0, ans=0;

    cin >> N >> A >> B;
    
    q = N / (A + B);

    r = N % (A + B);

    ans=A*q + min(A, r);

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main()
{
	
	int k, n;
	char str[100];
	
	scanf("%d %d", &n, &k);
	
	scanf("%s", str);
	
	str[k-1] = str[k-1] + 32;
	
	printf("%s", str);
	
	return 0;
}

Measured memory_bytes: 1712
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rrep(i,n) for(int (i)=((n)-1);(i)>=0;(i)--)
#define itn int
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
const long long INF = 1LL << 60;
const int MOD = 1000000007;
signed main(void){
    int n; cin>>n;
    vector <int> a(n); 
    rep(i,n) cin>>a[i];
    auto ima = max_element(all(a));
    auto imi = min_element(all(a));
    int ma = *ima, mi = *imi;
    bool pom;
    cout<<2*n-1<<endl;
    int x;
    if(abs(ma)>=abs(mi)) pom=true , x = (ima - a.begin()); else pom = false, x = imi - a.begin();
    rep(i,n) {if(pom) a[i]+= ma; else a[i]-=mi; cout<<x+1<<' '<<i+1<<endl;}
    //rep(i,n) cout<<a[i]<<endl;
    if(pom) rep(i,n-1) cout<<i+1<<' '<<i+2<<endl;
    else rrep(i,n-1) cout<<i+2<<' '<<i+1<<endl;
}


Measured memory_bytes: 256
//
//  main.cpp
//  StringTest
//
//  Created by ?????¶??? on 15/8/13.
//  Copyright (c) 2015??´ ?????¶???. All rights reserved.
//

#include <iostream>
#include <string>
using namespace std;

int main(int argc, const char * argv[]) {

    string str_1,str_2;
    
    cin >> str_1 >> str_2;

    str_1 = str_1 + str_1;
    
    int index_1 = 0;
    int index_2 = 0;
    
//    printf("str_1 length : %d\n" , static_cast<int>( str_1.length()));
    
    while (true) {
    
        
        if (str_1[index_1] == str_2[index_2]) {
            
//            printf("str_1[%d]: %c  str_2[%d]: %c \n", index_1, str_1[index_1], index_2, str_2[index_2] );
            
            index_2++;

        }else{


//            printf("str_1[%d]: %c  str_2[%d]: %c \n", index_1, str_1[index_1], index_2, str_2[index_2] );
            
            if (index_2 > 0) {
                index_1 -= index_2;
            }
            
            index_2 = 0;
        }
        
        index_1++;
        
        
        // ????¬??????¨??¨?¬????
        if (index_2 > static_cast<int>(str_2.length() - 1)){
            
            cout << "Yes" << endl;
            
            break;
        }
        // ????¬?????¬????
        if (index_1 == static_cast<int>(str_1.length() - 1)){
            
            cout << "No" << endl;
            
            break;
        }
    }
    
    return 0;
}

Measured memory_bytes: 1188
#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
#include <numeric>
#include <list>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <tuple>

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i <= (n); i++)
#define show(a, n) rep(i,n) {cout<<a[i]<<' ';} cout<<endl;

using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<long long, long long> pll;

const int INF = 1 << 30;
const long long INFL = 1LL << 62;
const int MOD = 1000000007;
const int MAX = 100000;
const int N = 100010;

int main() {
	int a[3];
	cin >> a[0] >> a[1] >> a[2];
	sort(a, a + 3);
	if(a[0] == a[1]) cout << a[2] << endl;
	else cout << a[0] << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <fstream>

using namespace std;

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

int N;
pii change(int num,int w){
  return pii(num/w,num%w);
}

int main(){

  while(cin>>N){
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    a--;b--;c--;d--;
    int res=1<<30;
    pii ps[4];
    for(int w=1;w<=N;w++){
      ps[0]=change(a,w);
      ps[1]=change(b,w);
      ps[2]=change(c,w);
      ps[3]=change(d,w);
      res=min(res,abs(ps[0].first-ps[1].first)+abs(ps[0].second-ps[1].second)
      +abs(ps[2].first-ps[3].first)+abs(ps[2].second-ps[3].second));
    }
    cout<<res<<endl;
  }
  
  return 0;
}

Measured memory_bytes: 1164
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<math.h>
#include<string>
#include <iomanip>
#include<deque>
#include<queue>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef int itn;
const ll LINF = 1e18;
const int INF = 1e8;

//マクロ定義
#define vvint(vec,n,m,l) vector<vector<int>> vec(n, vector<int>(m,l));	// lで初期化
#define vvll(vec,n,m,l) vector<vector<ll>> vec(n,vector<ll>(m,l));
#define vint vector<int>
#define pint pair<int,int>
#define rep(i,a) for(int i=0;i<(a);i++)
#define all(x) (x).begin(),(x).end()
#define debug system("pause")				//デバッグ用

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

	int n, k;
	cin >> n >> k;
	string s;
	cin >> s;
	int hanten = 0;
	int ans = 0;

	for (int i = 1; i < n - 1;)
	{
		if (hanten >= k)
		{
			break;
		}
		if (s[i - 1] == 'L')
		{
			if (s[i] == 'R')
			{
				for (int j = i + 1; j < n; j++)
				{
					if (s[j] == 'L')
					{
						hanten++;
						for (int i2 = i; i2 < j; i2++)
						{
							s[i2] = 'L';
						}
						i = j + 1;
						break;
					}
					if (j == n - 1)
					{
						i = j;
					}
				}
			}
			else
			{
				i++;
			}
		}
		else
		{
			i++;
		}

	}
	if (hanten < k)
		for (int i = 0; i < n; i++)
		{
			s[i] = 'L';
		}
	for (int i = 1; i < n; i++)
	{
		if (s[i - 1] == s[i])
			ans++;
	}

	cout << ans << endl;

}

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

#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define RREP(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define FOR(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();++i)
#define LET(x,a) __typeof(a) x(a)
//#define IFOR(i,it,c) for(__typeof((c).begin())it=(c).begin();it!=(c).end();++it,++i)
#define ALL(c) (c).begin(), (c).end()
#define MP make_pair

#define EXIST(e,s) ((s).find(e)!=(s).end())

#define RESET(a) memset((a),0,sizeof(a))
#define SET(a) memset((a),-1,sizeof(a))
#define PB push_back
#define DEC(it,command) __typeof(command) it=command

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define debug2(x) cerr << #x << " = [";REP(__ind,(x).size()){cerr << (x)[__ind] << ", ";}cerr << "] (L" << __LINE__ << ")" << endl;

const int INF=0x3f3f3f3f;

typedef long long Int;
typedef unsigned long long uInt;
typedef long double rn;

typedef pair<int,int> pii;

/*
#ifdef MYDEBUG
#include"debug.h"
#include"print.h"
#endif
*/
// }}}

int N,C,K;
vector<int> T,dp;

int main(){
	cin>>N>>C>>K;
	T.assign(N,0);
	REP(i,N)cin>>T[i];
	sort(ALL(T));
	dp.push_back(0);
	for(int i=0;i<N;i++){
		// decide dp[i+1]
		int l = 0, r = i;
		if(i-l+1<=C and T[i]-T[l]<=K){
			dp.push_back(1);
		}else{
			//l: out, r: in
			while(r-l>1){
				int m = (l+r)/2;
				if(i-m+1<=C and T[i]-T[m]<=K){
					r = m;
				}else{
					l = m;
				}
			}
//			cerr<<"id: "<<i<<" "<<l<<" "<<r<<endl;
			dp.push_back(dp[l+1] + 1);
		}
	}
//	REP(i,dp.size())cerr<<i<<" "<<dp[i]<<endl;
	cout<<dp.back()<<endl;
	return 0;
}



Measured memory_bytes: 1276
#include <stdio.h>

const int syouhai[8][3]={
	{3,3,3},
	{3,3,3},
	{3,3,3},
	{1,2,3},
	{3,3,3},
	{2,3,1},
	{3,1,2},
	{3,3,3}
};

int main(void) {
	int puttern;
	int hands[5];
	int i;
	while(1) {
		scanf("%d",&hands[0]);
		if(hands[0]==0)break;
		for(i=1;i<5;i++)scanf("%d",&hands[i]);
		puttern=0;
		for(i=0;i<5;i++)puttern|=1<<(hands[i]-1);
		for(i=0;i<5;i++)printf("%d\n",syouhai[puttern][hands[i]-1]);
	}
	return 0;
}

Measured memory_bytes: 0