akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pii pair <int, int>
#define pll pair <ll, ll>
#pragma 03
using namespace std;
char shift(char begin, int n){
	int x = begin - 'A';
	x += n; x %= 26;
	char k = x + 'A';
	return k;
}
int main(){ 
	int n;
	string s;
	cin >> n >> s;
	for (int i = 0; i<s.length(); i++){
		cout << shift(s[i], n);
	}
    return 0; 
} 

Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
#define MAX 1000000000000

vector<pair<ll, ll>> prime_factorize(ll N) {
    vector<pair<ll, ll>> res;
    for(ll a = 2; a * a <= N; ++a) {
        if(N % a != 0) continue;
        ll ex = 0; //指数
        //割り切れる限り割り続ける
        while(N % a == 0) {
            ++ex;
            N /= a;
        }
        //結果をpush
        res.push_back({a, ex});
    }
    //残った数について
    if(N != 1) res.push_back({N, 1});
    return res;
}


int main() {
  ll N;
  cin >> N;
  
  auto pf = prime_factorize(N);
  ll res = 0;
  for(auto p : pf) {
      ll e = p.second;
      ll tmp = 0, cur = 1;
      while(e >= cur) {
          e -= cur++;
          tmp++;
      }
      res += tmp;
  }
  
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 3632
#include <iostream>

int main(){
   int N, D, X;
   std::cin >> N >> D >> X;
   int A;
   int sum = 0;
   for(int i=0; i<N; ++i){
      std::cin >> A;
      sum += (D-1)/A + 1;
   }

   std::cout << sum + X << std::endl;

   return 0;

}


Measured memory_bytes: 256
def solve():
    MOD = 10 ** 9 + 7
    H, W = map(int, input().split())
    maze = ['' for _ in range(H)]
    for i in range(H):
        maze[i] = input()

    dp = [[0] * W for _ in range(H)]
    for i in range(H):
        if maze[i][0] == '.':
            dp[i][0] = 1
        else:
            break
    for i in range(W):
        if maze[0][i] == '.':
            dp[0][i] = 1
        else:
            break

    for i in range(1, H):
        for j in range(1, W):
            if maze[i][j] != '#':
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
                dp[i][j] %= MOD
    print(dp[H-1][W-1])


if __name__ == '__main__':
    solve()


Measured memory_bytes: 51440
def gcd(a,b):
    rem = a % b
    while rem != 0:
        a = b
        b = rem
        rem = a % b
    return b

# 最小公倍数を求める関数
def lcm(a,b):
    return int((a*b)/gcd(a,b))

n = int(input())
print(lcm(2,n))

Measured memory_bytes: 2940
package main

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

var sc = bufio.NewScanner(os.Stdin)

func inputInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func splitInt(n int) []int {
	arr := make([]int, n)
	for i := 0; i < n; i++ {
		arr[i] = inputInt()
	}
	return arr
}

type sortable [][]int

func (s sortable) Len() int {
	return len(s)
}

func (s sortable) Less(i, j int) bool {
	return s[i][0] < s[j][0]
}

func (s sortable) Swap(i, j int) {
	s[i], s[j] = s[j], s[i]
}

func main() {
	sc.Split(bufio.ScanWords)
	n := inputInt()
	as := splitInt(n)
	ords := make(sortable, n)
	for i := 0; i < n; i++ {
		ords[i] = []int{as[i], i + 1}
	}
	sort.Sort(ords)
	first := true
	for _, x := range ords {
		if !first{
			fmt.Print(" ")
		}
		fmt.Printf("%d",x[1])
		first = false
	}
}


Measured memory_bytes: 8448
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
struct bridge{
	vector<int>ord,low;
	vector<bool>art;
	vector<pair<int,int> >bridges;
	vector<vector<int> >G;
	bridge(int n_=0):ord(n_,-1),low(n_),art(n_,false),G(n_){}
	void add_edge(int u,int v)
	{
		G[u].push_back(v);
		G[v].push_back(u);
	}
	bool operator[](int a){return art[a];}
	bool is_bridge(int a,int b)
	{
		if(ord[a]>ord[b])swap(a,b);
		return ord[a]<low[b];
	}
	void dfs(int u,int p,int&k)
	{
		low[u]=ord[u]=k++;
		for(int&v:G[u])
		{
			if(ord[v]==-1)
			{
				dfs(v,u,k);
				low[u]=min(low[u],low[v]);
				art[u]=art[u]|ord[u]<=low[v];
				if(ord[u]<low[v])bridges.push_back(u<v?make_pair(u,v):make_pair(v,u));
			}
			else if(v!=p)
			{
				low[u]=min(low[u],ord[v]);
			}
		}
	}
	void build()
	{
		int k=1,cnt=0;
		low[0]=ord[0]=0;
		for(int&v:G[0])if(ord[v]==-1)
		{
			dfs(v,0,k);
			if(ord[0]<low[v])bridges.push_back(make_pair(0,v));
			cnt++;
		}
		if(cnt>=2)art[0]=true;
	}
};
#include<vector>
#include<queue>
#include<limits>
template<typename T>
vector<T>dijkstra(int s,const vector<vector<pair<int,T> > >&G,T INF=numeric_limits<T>::max())
{
	int n=G.size();
	vector<T>d(n,INF);
	vector<int>parent(n,-1);
	priority_queue<pair<T,int>,vector<pair<T,int> >,greater<pair<T,int> > >P;
	d[s]=0;
	P.push(make_pair(d[s],s));
	while(!P.empty())
	{
		pair<T,int>p=P.top();P.pop();
		int v=p.second;
		if(d[v]<p.first)continue;
		for(const pair<int,T>&e:G[v])
		{
			int u=e.first;
			T cost=d[v]+e.second;
			if(d[u]>cost)
			{
				d[u]=cost;
				parent[u]=v;
				P.push(make_pair(d[u],u));
			}
		}
	}
	return d;
}
int n,m;
main()
{
	cin>>n>>m;
	vector<vector<pair<int,long long> > >G(n),H(n);
	vector<pair<pair<int,int>,long long> >e;
	for(int i=0;i<m;i++)
	{
		int a,b,c;cin>>a>>b>>c;
		a--,b--;
		G[a].push_back(make_pair(b,c));
		H[b].push_back(make_pair(a,c));
		e.push_back(make_pair(make_pair(a,b),c));
	}
	vector<long long>dg=dijkstra(0,G,(long long)1e18);
	vector<long long>dh=dijkstra(1,H,(long long)1e18);
	bridge b(n);
	for(int i=0;i<m;i++)
	{
		if(dg[e[i].first.first]+dh[e[i].first.second]+e[i].second==dg[1])
			b.add_edge(e[i].first.first,e[i].first.second);
	}
	b.build();
	for(int i=0;i<m;i++)
	{
		if(dg[e[i].first.second]+dh[e[i].first.first]+e[i].second<dg[1])cout<<"HAPPY"<<endl;
		else if(dg[e[i].first.first]+dh[e[i].first.second]+e[i].second==dg[1]&&
			b.is_bridge(e[i].first.first,e[i].first.second))cout<<"SAD"<<endl;
		else cout<<"SOSO"<<endl;
	}
}


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

int main()
{
	string s, t;
	cin >> s >> t;
	
	bool flag = true;
	for(int i = 0; i < s.length(); i++)
	{
		if(s[i] != t[i])
		{
			flag = false;
		}
	}
	
	if(flag)
	{
		cout << "Yes" << endl;
	}
	else
	{
		cout << "No" << endl;
	}
	
	return 0;
}


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

const double PI = 3.14159265358979323846;
//using namespace boost::multiprecision;
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
#define rep(i, n) for (int i = 0; i < (n); ++i)
typedef pair<ll, ll> P;
const ll INF = 1e15;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
#define ret() return 0;

std::istream &operator>>(std::istream &in, set<int> &o) {
    ll a;
    in >> a;
    o.insert(a);
    return in;
}

std::istream &operator>>(std::istream &in, queue<int> &o) {
    ll a;
    in >> a;
    o.push(a);
    return in;
}

bool contain(set<int> &s, int a) { return s.find(a) != s.end(); }

//ifstream myfile("C:\\Users\\riku\\Downloads\\0_00.txt");
//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);
const int mod = 1000000007;
//const ll mod = 1e10;
typedef priority_queue<long long, vector<long long>, greater<long long> > PQ_ASK;


bool is_natural(int d, string a, string b) {
    if (d % 2 == 0) {
        if (a == b) return false;
    } else {
        if (a != b) return false;
    }
    return true;
}

string check(vector<string> &seats, int ceil, int floor, int mid, string v) {

    string c = seats[ceil],
            f = seats[floor],
            m = seats[mid];

    assert(c != "");
    assert(f != "");
    assert(m != "");

    int mf = mid - floor - 1;
    bool b1 = is_natural(mf, m, f);
    int cm = ceil - mid - 1;
    bool b2 = is_natural(cm, c, m);
    assert(b1 xor b2);

    if (b1) {
        return "second";
    } else {
        return "first";
    }
}

int main() {

    int n;
    cin >> n;

    vector<string> seats(n, "");

    {
        cout << 0 << endl << flush;
        string v;
        cin >> v;
        if (v == "Vacant") {
            ret();
        }
        seats[0] = v;

        cout << n - 1 << endl << flush;
        cin >> v;
        if (v == "Vacant") {
            ret();
        }
        seats[n - 1] = v;
    }

    int floor = 0, ceil = n - 1;

    while (floor + 1 < ceil) {
        int mid = (floor + ceil) / 2;
        cout << mid << endl << flush;

        string v;
        cin >> v;
        if (v == "Vacant") {
            ret();
        }

        seats[mid] = v;

        string s = check(seats, ceil, floor, mid, v);
        if (s == "second") {
            floor = mid;
        } else {
            ceil = mid;
        }
    }

    __throw_runtime_error("okasii");


}


Measured memory_bytes: 1620
#include <bits/stdc++.h>
using namespace std;
const int N=3e5+9;

int n,k,x;
int seg[4*N];

 
int get(int p,int l,int r,int a,int b){
     if(l>=a&&r<=b)return seg[p];       
     if(r<a||l>b) return 0;
    int mid=(l+r)/2;
    if(b<=mid) return get(p*2,l,mid,a,b);
    if(a>mid) return get(p*2+1,mid+1,r,a,b);
    return max(get(p*2,l,mid,a,b),get(p*2+1,mid+1,r,a,b));
}
 
void update(int p,int l,int r,int idx,int v){
    if(l==r){
        seg[p]=v;
        return ;
    }
    int mid=(l+r)/2;
    if(idx<=mid)update(p*2,l,mid,idx,v);
    else update(p*2+1,mid+1,r,idx,v);
    seg[p]=max(seg[p*2],seg[p*2+1]);
 
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    cin>>n>>k;
    for(int i=0;i<n;i++){
    	cin>>x;
    	x++;
    	int l=max(1,x-k);
    	int r=min(N,x+k);
    	int cur=get(1,1,n,x,x);
    	int go=get(1,1,N,l,r);
    	if(cur<=go)update(1,1,N,x,go+1);
    	//else update(1,1,N,x,1);
    }
    cout<<get(1,1,N,1,N)<<'\n';
}

Measured memory_bytes: 7696
using System;
using System.IO;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Numerics;
using System.Threading.Tasks;
using System.Text.RegularExpressions;
using Debug = System.Diagnostics.Debug;
using System.Runtime.CompilerServices;
using static System.Math;
using MethodImplOptions = System.Runtime.CompilerServices.MethodImplOptions;
using MethodImplAttribute = System.Runtime.CompilerServices.MethodImplAttribute;

static class P
{
    static void Main()
    {
        var rgbn = Console.ReadLine().Split().Select(int.Parse).ToArray();
        var r = rgbn[0];
        var g = rgbn[1];
        var b = rgbn[2];
        var n = rgbn[3];
        int res = 0;
        for (int i = 0; i * r <= n; i++)
        {
            for (int j = 0; i * r + j * g <= n; j++)
            {
                if ((n - (i * r + j * g)) % b == 0)
                {
                    //Console.WriteLine($"{i} {j} {(n - (i * r + j * g)) / b}");
                    res++;
                }
            }
        }
        Console.WriteLine(res);
    }
}


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

#define INF 1e9
using namespace std;
typedef long long ll;

int main() {

    int n; cin >> n;
    string s; cin >> s;

    vector<int> l(n);
    vector<int> r(n);

    l[0] = 0;

    for (int i = 0; i < n-1; ++i) {
        if (s[i] == 'W') {
            l[i+1] = l[i] + 1;
        } else {
            l[i+1] = l[i];
        }
    }

    r[n-1] = 0;

    for (int i = n-1; i > 0; --i) {
        if (s[i] == 'E') {
            r[i-1] = r[i] + 1;
        } else {
            r[i-1] = r[i];
        }
    }

    int ans = INF;
    for (int i = 0; i < n; ++i) {
        int res;
        res = l[i] + r[i];

        ans = min(ans, res);
    }

    cout << ans << endl;
}

Measured memory_bytes: 3076
#include <iostream>
#include <algorithm>
#include <bits/stdc++.h>

using namespace std;
const int p=1000000007;

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

	long long H, W;
	cin >> H >> W;

	vector<string> maze(H);
	for(auto &s : maze) cin >> s;

	vector<vector<int> > dp(H, vector<int> (W, 0));
	for(int i=0; i<W; ++i)
	{
		if(maze[0][i] == '.') dp[0][i] = 1;
		else break;
	}
	for(int i=0; i<H; ++i)
	{
		if(maze[i][0] == '.') dp[i][0] = 1;
		else break;
	}


	for(int i=1; i<H; ++i)
	{
		for(int j=1; j<W; ++j)
		{
			if(maze[i][j]=='#') continue;
			else dp[i][j] = (dp[i-1][j] + dp[i][j-1])%p;
		}
	}
	cout << dp[H-1][W-1] << endl;

	// for(auto &v : dp)
	// {
	// 	for(auto n : v) printf("%d ", n);
	// 	printf("\n");
	// }
	
	return 0;
}

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

#define vi vector<int>
#define vl vector<long>
#define vvi vector<vector<int>>
#define vvl vector<vector<long>>
#define pint pair<int, int>
#define plong pair<long, long>

int main() {
    int N, X, T;
    cin>>N>>X>>T;
    cout << ((N-1)/X + 1) * T << endl;
}

Measured memory_bytes: 3584
#include <iostream>
using namespace std;
#define MAX_N 999999 + 16
 
int  prime[MAX_N];			
bool is_prime[MAX_N + 1];	
int sieve(const int& n)
{
	int p = 0;
	fill(is_prime, is_prime + n + 1, true);
	is_prime[0] = is_prime[1] = false;
	for (int i = 2; i <= n; ++i)
	{
		if (is_prime[i])
		{
			prime[p++] = i;
			for (int j = 2 * i; j <= n; j += i)
			{
				is_prime[j] = false;
			}
		}
	}
	return p;
}
 
int main(int argc, char *argv[])
{
	int n;
	while (cin >> n)
	{
		cout << sieve(n) << endl;
	}
	return 0;
}

Measured memory_bytes: 2444
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        List<Integer> excluded = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            excluded.add(in.nextInt());
        }

        while (true) {
            List<Integer> source = toNumberList(n);
            if (!contains(source, excluded)) {
                System.out.println(n);
                break;
            }
            n++;
        }

    }
    private static List<Integer> toNumberList(int n) {
        List<Integer> integers = new ArrayList<>();
        while (n != 0) {
            integers.add(n % 10);
            n /= 10;
        }
        return integers;
    }

    private static boolean contains(List<Integer> source, List<Integer> excluded) {
        return source.stream()
                .anyMatch(excluded::contains);
    }
}


Measured memory_bytes: 47740
import kotlin.math.hypot

fun main() = Thread(null, ::abc174b, "(^o^)", 128 * 1024 * 1024).apply { start() }.join()

@OptIn(ExperimentalStdlibApi::class)
fun abc174b() {
    val (n, d) = readLine()!!.split(" ").map { it.toInt() }
    val xyList = List(n) {
        val (x, y) = readLine()!!.split(" ").map { it.toDouble() }
        x to y
    }

    val answer = xyList.count { (x, y) -> hypot(x, y) <= d }

    println(answer)
}


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

int main(){
  int d;
  cin >> d;
  d = 25 - d;

  cout << "Christmas";
  for(int i = 0; i < d; i++){
    cout << " " << "Eve";
  }

  cout << endl;
  return 0;
}


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

using namespace std;

int main() {
    string S;
    cin >> S;
    stack<char> st;
    for(auto &s:S){
        if(st.empty()){
            st.push(s);
        } else if(st.top() == s){
            st.push(s);
        } else{
            st.pop();
        }
    }
    cout << S.size()-st.size() << endl;
    return 0;
}

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

int a, b, c;

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


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

using namespace std;

int main(){
	set <char> a;
	char x;
	while(cin >> x){
		a.insert(x);
	}
	char chq = 'a';
	for(int i = 0;i < 26;i++){
		if(a.count(chq)) chq++;
		else{
			break;
		}
	}
	if(chq > 'z') cout << "None";
	else cout << chq;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main()
{
    ll n,m,t,a,b,s,i,max=0,c=0;
   string ch;
   cin>>ch;
   for(i=0;i<ch.length();i++){
    if(ch[i]=='R')
        c++;
    else
        c=0;
    if(c>max)
        max=c;
   }
   cout<<max<<endl;
}


Measured memory_bytes: 3620
n,a,*l=map(int,open(0).read().split())
R=2500
dp=[[0]*R*2,[0]*R*2]
dp[0][0]=1
t=0
for i in range(n):
  u=1-t
  for s in range(-R,R):
    dp[u][s]=dp[t][s]+dp[t][s-l[i]+a]
  t=u
print(dp[t][0]-1)

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

using namespace std;

int main(){
    int n;
    cin >> n;
    string s = "No";
    for (int i = 1; i <= 9; i++){
        if(n / i <= 9 && n % i == 0){
            s = "Yes";
            break;
        }
    }
    cout << s;
    return 0;
}


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

int n;
long long dp[4096][4096];
int a[4096], vis[4096][4096];

long long calc(int l, int r, int turn) {
    auto &y = dp[l][r];
    if(vis[l][r]) return y;
    vis[l][r] = 1;
    if(l == r) return y = (turn == 0 ? a[l] : -a[l]);
    if(turn == 0) {
        return y=max(a[l]+calc(l+1, r, 1), a[r]+calc(l, r-1, 1));
    }
    else {
        return y=min(calc(l+1, r, 0)-a[l], calc(l, r-1, 0)-a[r]);
    }
}

int main() {
    memset(dp, -1, sizeof(dp));
	cin >> n;
	for(int i=1; i<=n; ++i) {
	    cin >> a[i];
    }
	cout << calc(1, n, 0) << endl;
	return 0;
}


Measured memory_bytes: 169560
#include <iostream>
#include <math.h>
#include <algorithm>
#include <vector>
#include <numeric>
#include <string>
using namespace std;
const double PI = acos(-1.0);
const string alp = "abcdefghijklmnopqrstuvwxyz";
const string ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const int INTMAX = 2147483647;
const int INTMIN = -2147483648;
const unsigned int UINTMAX = 4294967295;
const long LONGMAX = 9223372036854775807;
const long LONGMIN = -9223372036854775808;
const unsigned long ULONGMAX = 18446744073709551615;
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n+1)
#define SUM(c) accumulate((c).begin(),(c).end(),0)
#define UNIQ(c) (c).erase(unique((c).begin(), (c).end()), (c).end());
#define Yn(b) puts(b?"Yes":"No")
#define YN(b) puts(b?"YES":"NO")

bool isprime(int p) {
  if (p==1) return false;
  FOR(i,2,p) {
    if (p%i==0) return false;
  }
  return true;
}

int dig(int n, int a) {return n/(int)pow(10,a)%10;}
int digl(long n, int a) {return n/(long)pow(10,a)%10;}
int digsum(int n) {int r=0;REP(i,10){r+=dig(n,i);}return r;}
int digsuml(long n) {int r=0;REP(i,19){r+=digl(n,i);}return r;}
int dignum(int n) {return n?to_string(n).length():0;}
int dignuml(long n) {return n?to_string(n).length():0;}

int main(){
  int a,b,c;
  cin >> a >> b >> c;
  if ((a>=b&&b>=c)||(c>=b&&b>=a)){
    cout << abs(max({a,b,c})-b)+abs(min({a,b,c})-b);
  } else if ((b>=a&&a>=c)||(c>=a&&a>=b)){
    cout << abs(max({a,b,c})-a)+abs(min({a,b,c})-a);
  } else if ((a>=c&&c>=b)||(b>=c&&c>=a)){
    cout << abs(max({a,b,c})-c)+abs(min({a,b,c})-c);
  }
  
}

Measured memory_bytes: 256
S = input()

matrix = ['0'] * len(S)
rooms = []
left = 0
i = 0
while i < len(S):
    if S[i] == 'L':
        l = i - 1
        r = i
        while i < len(S):
            if S[i] == 'R':
                right = i - 1
                rooms.append((left, l, r, right))
                left = i
                break
            if len(S) - 1 == i:
                right = i
                rooms.append((left, l, r, right))
            i += 1
    else:
        i += 1

from math import ceil
for room in rooms:
    left, l, r, right = room
    matrix[r] = str((l - left + 1) // 2 + ceil((right - r + 1) / 2))
    matrix[l] = str((ceil((l - left + 1) / 2) + (right - r + 1) // 2))
print(' '.join(matrix))


Measured memory_bytes: 20844
import java.util.Scanner;

class Main {
	public static void main(String[] args){
		try (Scanner sc = new Scanner(System.in)){
			while (true) {
				int H = sc.nextInt();
				int W = sc.nextInt();
				if ((H == 0) && (W == 0)) break;

				for (int i=0; i<W ; i++) {
					System.out.print('#');
				}
				System.out.print('\n');

				for (int i=1; i< H - 1 ; i++) {
					System.out.print('#');
					for (int j=1; j<W - 1; j++) {
						System.out.print('.');
					}
					System.out.print('#');
					System.out.print('\n');
				}
				for (int i=0; i<W ; i++) {
					System.out.print('#');
				}
				System.out.print("\n\n");
			}
		}
	}
}


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

vector<long long> v;
void dfs(ll x, ll num, ll st, ll cc){
	if(v.size() > 100000) return;
	if(num == 0) num += x;
	else {
		num *= 10;
		num += x;
	}
	if(cc > st) return;
	if(cc == st){
		v.push_back(num);
		return;
	}
	if(x-1 >= 0) dfs(x-1,num,st,cc+1);
  	dfs(x,num,st,cc+1);
	if(x+1 <= 9) dfs(x+1,num,st,cc+1);
	return;
}

int main(){
	
	ll k; cin>>k;
	for(int i = 1; i <= 10; i++){
		for(int j = 1; j <= 9; j++){
			dfs(j,0,i,1);
		}
	}
	//sort(v.begin(),v.end());
	cout<<v[k-1]<<"\n";
}


Measured memory_bytes: 1400
fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };
    let n: usize = sc.read();
    let d: Vec<i64> = sc.vec(n);
    let mut ans: i64 = 0;
    for i in 0..n {
        for j in 0..n{
            if i == j {
                continue;
            }
            ans += d[i]*d[j];
        }
    }
    println!("{}", ans/2);
}

pub struct Scanner<R> {
    stdin: R,
}

impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n')
            .take_while(|&b| b != b' ' && b != b'\n')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
        .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}



Measured memory_bytes: 4352
(* Vicfred
 * https://atcoder.jp/contests/abc143/tasks/abc143_b
 * brute force
 * *)
Scanf.scanf "%d\n" @@ fun n ->
    let d = Array.init n @@ fun _ -> Scanf.scanf "%d " @@ fun d -> d in
    Printf.printf "%d\n" @@
    Array.fold_left (Array.fold_left ( + )) 0 @@
    Array.init n @@ fun i ->
        Array.init n @@ fun j ->
            if i <= j then 0
            else d.(i) * d.(j)



Measured memory_bytes: 3824
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
    ll n;
    cin>>n;
    ll ans=1e17;
    for(int i=1;i<=sqrt(n);i++)
    {
        if(n%i==0)
        {
            ans=min(ans,i-1+n/i-1);

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


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
"""
@author: H_Hoshigi
"""
def main():
    N = int(input())
    b_lsit = list(map(int, input().split()))

    flag = True
    answer_list = []
    while flag and b_lsit:
        #print(b_lsit)
        for i in range(len(b_lsit)-1, -2, -1):
            if i == -1:
                flag = False
                break
            elif b_lsit[i] == i+1:
                answer_list.append(b_lsit.pop(i))
                break

    if flag:
        for b in answer_list[::-1]:
            print(b)
    else:
        print(-1)

    return

if __name__ == "__main__":
    main()



Measured memory_bytes: 9168
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;

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

  ll a, b, x;
  cin >> a >> b >> x;

  ll countB = b / x + 1;
  ll countA = (a > 0 ? (a - 1) / x + 1 : a);

  cout << countB - countA << endl;

  return 0;
}

Measured memory_bytes: 256
S = input()
N = len(S)
ans = "Yes"
for i in range(N):
    j = N - i - 1
    if not S[i] == S[j]:
        ans = "No"
for i in range((N-1)//2):
    j = (N-1)//2 - i - 1
    if not S[i] == S[j]:
        ans = "No"
for i in range((N+3)//2 - 1, N):
    j = N - i - 1
    if not S[i] == S[j]:
        ans = "No"
print(ans)

Measured memory_bytes: 3064
import java.util.*;

public class Main{
    public static void main(String[] args){

        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();

        if(a<c){
            if(c<b){
                System.out.println("Yes");
            }else{
                System.out.println("No");
            }
        }else if(b<c){
            if(c<a){
                System.out.println("Yes");
            }else{
                System.out.println("No");
            }
        }else{
            System.out.println("No");
        }


       

    }
}

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

int main(){
	int n, a, b, base, top[100];
	
	scanf(" %d", &n);
	scanf(" %d %d", &a, &b);
	scanf(" %d", &base);
	for(int i=0; i<n; ++i) scanf(" %d", &top[i]);
	
	sort(top, top+n, greater<int>());
	
	double max=(double)base/a;
	
	for(int i=0; i<n; ++i){
		double tmp=base;
		for(int j=0; j<=i; ++j) tmp+=top[j];
		tmp/=(double)a+b*(i+1);
		
		if(tmp>max) max=tmp;
	}
	
	printf("%ld\n", (long)max);
	return 0;
}

Measured memory_bytes: 1204
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from math import floor

a, b, n = map(int, readline().split())
print(floor(a * min(b - 1, n) / b) - a * floor(min(b - 1, n) / b))


Measured memory_bytes: 9072
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lvector vector<ll> 
#define rep(i,n) for(ll (i)=0; i<(n); ++(i))
#define print(a) cout << (a) << endl

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll n,k,s;cin>>n>>k>>s;
  lvector ans(n,0);
  if(k==0) {
    lvector ans_(n,s/2+2);
    ans=ans_;
  }
  else {
    lvector ans_(n,s);
    ans=ans_;
    if(n-k<s) for(ll i=k;i<n;++i) ans[i]=1;
    else{
      if(s==1) {
        for(ll i=k;i<n;++i) ans[i]=2;
      }
      else {
        for(ll i=k;i<n;++i) {
          if(i%2==0) ans[i]=1;
          else ans[i]=s+1;
        }
      }
    }
  }
  rep(i,n) cout<<ans[i]<<" ";cout<<endl;
  return 0;
}

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

using namespace std;

int main(){
    int n,x;
    cin >> n >> x;

    vector<int> l(n);
    for(int i=0; i<n; i++){
        cin >> l[i];
    }

    int distance = 0,cnt=0;
    for(int i=0;i <=n; i++){
        if(distance > x){
            break;
        }
        cnt++;
        if(i==n){
            break;
        }
        distance += l[i];
    }

    cout << cnt << endl;
}

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

int main(){
  int N;
  cin >> N;
  for (int i=0;i<N;i++){
    string S;
    cin >> S;
    if (S == "Y"){
      cout<<"Four"<<endl;
      break;
    }
    else if(i == N-1){
      cout << "Three" <<endl;
    }
  }
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include <string.h>
#include <stdio.h>
#include <math.h>
#include <set>
#include <queue>
#include <stack>
#include <map>

using namespace std;
typedef long long LL;
const int INF = int(1e9);
const int MAX = 1000020;
LL N;
LL a[MAX],b[MAX],c[MAX];

void Cin(LL a[])
{
    for(int i = 1;i<=N;i++)
        cin>>a[i];
}

int main()
{
    cin>>N;
    Cin(a),Cin(b),Cin(c);
    sort(a+1,a+1+N),sort(b+1,b+1+N),sort(c+1,c+1+N);
    LL sum = 0;
    LL ai = 0,ci = 0;
    for(int i = 1;i<=N;i++){
        while(a[ai+1]<b[i]&&ai+1<=N)
            ai++;
        while(c[ci+1]<=b[i]&&ci+1<=N)
            ci++;
       // cout<<ai<<" "<<ci<<endl;
        sum += ai*(N-ci);
    }

    cout<<sum<<endl;

    return 0;
}



Measured memory_bytes: 9216
from collections import Counter
import string
H,W = list(map(int,input().split()))


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

c= Counter("".join(a))


if H==1 or W==1:
    allow1 =H %2 + W%2 -1
    allow2 = (H+W-1)//2
else:
    allow1 = 1 if H%2 and W%2 else 0
    allow2 = H%2*W//2 + W%2*H//2

for s in string.ascii_lowercase:
    count = c[s]
    if count%4==0:
        continue

    elif count%4==2:
        allow2 -=1

    elif count%4 ==1:
        allow1 -=1
    elif count%4==3:
        allow1 -=1
        allow2 -=1

if allow1>=0 and allow2 >=0:
    print("Yes")
else:
    print("No")
#print(allow1,allow2)

Measured memory_bytes: 4020
#include <stdio.h>

int main(){
  int n;
  int cards[4][13];
  char suit;
  int number;

  for(int i = 0; i < 4; i++){
	for(int j = 0; j < 13; j++){
	  cards[i][j] = 0;
	}
  }

  scanf("%d", &n);

  for(int i = 0; i < n; i++){
	scanf("%*c");/* scanf に残った改行を読み飛ばす*/
	scanf("%c %d", &suit, &number);
	if(suit == 'S'){cards[0][number - 1] = 1;}
	if(suit == 'H'){cards[1][number - 1] = 1;}
	if(suit == 'C'){cards[2][number - 1] = 1;}
	if(suit == 'D'){cards[3][number - 1] = 1;}
  }

  for(int i = 0; i < 4; i ++){
	for(int j = 0; j < 13; j++){
	  if(cards[i][j] == 0){
		switch(i){
		case 0:
		  printf("S %d\n", j + 1);
		  break;
		case 1:
		  printf("H %d\n", j + 1);
		  break;
		case 2:
		  printf("C %d\n", j + 1);
		  break;
		case 3:
  		  printf("D %d\n", j + 1);
		  break;
		default:
		  break;
		}
	  }
	}
  }

  return 0;
}


Measured memory_bytes: 2108
primes = [2,3,5,7,11,13,17,19,23,29,31]

memo1 = {}
def factorization(n):
    result = []
    for prime in primes:
        while n % prime == 0:
            n = n / prime
            result.append(prime)
    if n != 1:
        result.append(n)
    return result

def num_of_factors(l):
    if l == []:
        return 1
    if len(l) == 1:
        return 2
    p2num = {}
    for prime in l:
        if prime not in p2num:
            p2num[prime] = 2
        else:
            p2num[prime] += 1
    return reduce(lambda x,y: x * y,p2num.values())

def factors_of_factorials(n):
    l = []
    for i in range(1,n+1):
        l += factorization(i)
    return num_of_factors(l) % (10**9 + 7)


n = int(raw_input())
print factors_of_factorials(n)

Measured memory_bytes: 2820
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define all(a) a.begin(), a.end()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
using namespace std;

int main(){

    int N, K;
    cin >> N >> K;
    K++;

    vector<int> a(N), b(N);
    rep(i, N)cin >> a[i] >> b[i];

    long long ans = 0;
    vector<int> use(N);
    iota(all(use), 0);
    
    for(int digit = 30; digit >= 0; digit--){
        int bit = (1 << digit);
        if(bit & K){
            long long sum = 0;
            rep(i, (int)use.size()){
                if(!(bit & a[use[i]]))sum += b[use[i]];
            }
            chmax<long long>(ans, sum);
        } else {
            vector<int> tmp;
            rep(i, (int)use.size()){
                if(!(bit & a[use[i]]))tmp.push_back(use[i]);
            }
            use = tmp;
        }
    }

    cout << ans << endl;
    return 0;

}

Measured memory_bytes: 2384
N,K = map(int,input().split())
p = list(map(int,input().split()))
E = sum(p[0:K])
a = E
for i in range (0,N-K):
  E = E - p[i] + p[i+K]
  if E == max(a,E):
    a = E
    
print((a+K)/2)

Measured memory_bytes: 71792
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        long N = stdIn.nextLong();
        long A = stdIn.nextLong();
        long B = stdIn.nextLong();
        stdIn.close();

        long Count = 0;

        if (N % (A + B) > A) {
            Count = A * (N / (A + B)) + A;
        } else {
            Count = A * (N / (A + B)) + (N % (A + B));
        }

        System.out.println(Count);
    }
}

Measured memory_bytes: 22612
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <utility>
using namespace std;
using ll = long long;
 
int main() {
	int x;
	cin >> x;
	if (x == 7 || x == 5 || x== 3) cout << "YES" << endl;
	else cout << "NO" << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#include <cmath>
#include <queue>
#include <limits>
#include <map>
#include <cassert>
#include <functional>
#include <iterator>
using namespace std;
using VI = vector<long>;

int main() {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    cout << a * b << endl;
}


Measured memory_bytes: 256
#pragma warning(disable:4996)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define _USE_MATH_DEFINES
#include <math.h>
#include <float.h>

#pragma region 定義
typedef long long  ll;
typedef unsigned long long  ull;


#define _itoa(A,N) sprintf(A, "%d", N);

int i_dsort(const void* a, const void* b);
int i_asort(const void* a, const void* b);

int  _gcd(int a, int b);
int  _swp(int* a, int* b);
int _cknum(char* a, int n);
int _atoi(char* s, int len);

int s_asort(const void* a, const void* b);
int s_dsort(const void* a, const void* b);

//昇順
int s_asort(const void* a, const void* b) {
	return(strcmp((char*)a, (char*)b));
}
int s_dsort(const void* a, const void* b) {
	return(strcmp((char*)b, (char*)a));
}

int i_dsort(const void* a, const void* b) {
	return(*(int*)b - *(int*)a);
}
int i_asort(const void* a, const void* b) {
	return(*(int*)a - *(int*)b);
}

int _gcd(int a, int b) {
	int r, tmp;
	if (a < b) { tmp = a; a = b; b = tmp; }
	r = a % b;
	while (r) {
		if (!r) break;
		a = b; b = r;
		r = a % b;
	}
	return(b);
}
// puts("Yes\n") puts("No\n")
// scanf("%d.%d") 浮動小数点入力を整数２つで得る


//#define pai  3.1415926535 
//#define  _USE_MATH_DEFINES でM_PIが使える

#define deg_rad(X)  (X*(M_PI/180))


int _swp(int* a, int* b)
{
	int tmp;
	tmp = *b; *b = *a; *a = tmp;
	return 0;
}
#define _abs(x) ((x)>0?(x):-(x))
#define _min(x,y) ((x)<(y)?(x):(y))
#define _max(x,y) ((x)<(y)?(y):(x))

int _cknum(char* a, int n) {
	int i;
	char t = '0';

	for (i = 0; i < n; i++) {
		if (a[i] < '0' || a[i]>'9') return 1;
	}
	return 0;
}


int _atoi(char* s, int len) {
	char tmp[20];
	memcpy(tmp, s, len);
	tmp[len] = 0x00;
	return (atoi(tmp));
}

//素因数分解　pf素数が入る　pc 素数の数
ll _pfact(ll a);
static ll pf[100000000];
static ll pc;

ll _pfact(ll a) {
	long i, r;
	if (a % 2 == 0) {
		pf[pc] = 2; pc++;
		return(_pfact(a / 2));
	}
	r = sqrt(a);
	for (i = 3; i <= r; i += 2) {
		if (a % i == 0) {
			pf[pc] = i; pc++;
			return(_pfact(a / i));
		}
	}
	if (a != 1) {
		pf[pc] = a; pc++;
	}
	return 0;

}


#pragma endregion


//ABC  171 B

int main(void) {
	int      n,k,i;
	int      p[1001];

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

	for (i = 0; i < n; i++) 
		scanf("%d", &p[i]);

	qsort(p, n, sizeof(int), i_asort);
	int ans = 0;
	for (i = 0; i < k; i++) {
		ans += p[i];
	}


	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 2184
def main():
    n, k = [int(e) for e in input().split()]
    h = [int(e) for e in input().split()]
    dp = [0] * n
    for i in range(1, n):
        dp[i] = min(dp[j] + abs(h[j] - h[i]) for j in range(max(i - k, 0), i))
    print(dp[n-1])
main()

Measured memory_bytes: 13980
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<string> VS;
typedef vector< vector<int> > VVI;
typedef vector< vector<ll> > VVL;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(a) (a).begin(),(a).end()
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound

int main(){
  int N;
  cin>>N;
  VI A(N);
  rep(i,N) cin>>A[i];
  sort(all(A));
  VL X(N);
  X[0]=A[0];
  rep(i,N-1) X[i+1]=X[i]+A[i+1];
  int ans=1;
  rep(i,N-1){
    if(A[N-1-i]>X[N-2-i]*2) break;
    ans++;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 1408
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
#include<iostream>
#include<cstring>
using namespace std;
template<class _T>inline void read(_T &_a)
{
    bool f=0; char _c=getchar(); _a=0;
    while(_c<'0'||_c>'9'){ if(_c=='-') f=1; _c=getchar(); }
    while(_c>='0'&&_c<='9'){ _a=(_a<<3)+(_a<<1)-'0'+_c; _c=getchar(); }
    if(f) _a=-_a;
}

const int MAXN=200005;
int n,a[MAXN];
bool vis[MAXN],flag;
long long k,zq,t[MAXN];

void dfs(int rt,long long cnt)
{
    if(flag&&vis[rt])
    {
        zq=cnt-t[rt];
        cnt+=(k-cnt)/zq*zq;
        flag=false;
    }
    if(cnt==k) { printf("%d",rt); return ; }
    t[rt]=cnt;
    vis[rt]=true;
    dfs(a[rt],cnt+1);
}

void dfs2(int rt,int cnt)
{
    if(cnt==k) { printf("%d",rt); return ; }
    dfs2(a[rt],cnt+1);
}

int main()
{
    read(n); read(k);
    for (int i=1;i<=n;++i) read(a[i]);
    flag=true;
    dfs(1,0);
    return 0;
}

Measured memory_bytes: 6300
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
import bisect
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#############
# Main Code #
#############

sx,sy,tx,ty = inputIL()

X = tx-sx
Y = ty-sy

print("U"*Y+"R"*X+"D"*Y+"L"*(X+1)+"U"*(Y+1)+"R"*(X+1)+"D"+"R"+"D"*(Y+1)+"L"*(X+1)+"U")

Measured memory_bytes: 66156
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <string>
#include <functional>
#include <utility>
#include <queue>
#include <vector>
#include <string>
#include <stack>
#define rep(i,n) for(ll i=0;i<n;i++)
using namespace std;
typedef long long int ll;
const ll  MOD = 1000000007;
typedef pair<ll,ll> P;

int N,M;
vector<int> vec[100100];
int Q;
queue<int> que;
int ans[100100];
int in_v[100100],in_d[100100],in_c[100100];
int max_d[100100];

void bfs(int v ,int d, int c){
  if(max_d[v] >= d) return;
  que.push(v);
  if(ans[v] == 0){
    ans[v] = c;
  }
  max_d[v] = d;
  while(!que.empty() && d>0){
    int l=que.size();
    d--;
    rep(i,l){
      int tmp = que.front();
      que.pop();
      int l2 = vec[tmp].size();
      rep(j,l2){
        int pos = vec[tmp][j];
        if(max_d[pos] >= d) continue;
        if(ans[pos] == 0){
          ans[pos] = c;
        }
        max_d[pos] = d;
        que.push(pos);
      }
    }
  }

  while(!que.empty()){
    que.pop();
  }
}
int main(){
  cin >> N >> M;
  rep(i,M){
    int a,b;
    cin >> a >> b;
    vec[a].push_back(b);
    vec[b].push_back(a);
  }
  cin >> Q;
  rep(i,Q){
    cin >> in_v[i] >> in_d[i] >> in_c[i];
  }
  rep(i,N+1){
    max_d[i] = -1;
  }
  for(int i=Q-1;i>=0;i--){
    bfs(in_v[i],in_d[i],in_c[i]);
    /*
    rep(j,N){
      cerr << ans[j+1] << endl;
    }
    cerr << endl;
    */
  }
  rep(i,N){
    cout << ans[i+1] << endl;
  }
}


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

int main(){
int N , K , shoki = 1;
cin >> N >> K;
for (int i = 0; i < N; i++){
  if((2 * shoki) < (shoki +K)) shoki = shoki * 2;
  else shoki += K;
}

cout << shoki << endl;
  return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define ms(x, n) memset(x,n,sizeof(x));
typedef  long long LL;
const LL maxn = 100010;
const int NIL = -1;


struct node{    //左子右兄弟表示法
    int p, l, r;
}T[maxn];
int D[maxn]; //所有节点的深度
void print(int u){
    //打印u节点的相关信息
    printf("node %d: parent = %d, depth = %d, ", u, T[u].p, D[u]);
    if(T[u].p==NIL) printf("root, ");
    else if(T[u].l==NIL) printf("leaf, ");
    else printf("internal node, ");

    printf("[");
    for(int i = T[u].l, j = 0; i!=NIL; i=T[i].r, j++){
        if(j==0) printf("%d", i);
        else printf(", %d", i);
    }
    printf("]\n");
}
void setDepth(int u, int p){
    D[u] = p;
    if(T[u].r!=NIL) setDepth(T[u].r, p);
    if(T[u].l!=NIL) setDepth(T[u].l, p+1);
}
int main()
{
    int id, k, cur, l, N, root;
    cin >> N;
    for(int i = 0; i <= N; i++)
        T[i].l = T[i].r = T[i].p = NIL; //初始化

    for(int i = 1; i <= N; i++){
        cin >> id >> k;
        for(int j = 1; j <= k; j++){
            cin >> cur;
            if(j==1) T[id].l = cur;
            else T[l].r = cur;
            l = cur;
            T[cur].p = id;
        }
    }
    for(int i = 0; i < N; i++)
        if(T[i].p==NIL) root = i;

    setDepth(root, 0);
    for(int i = 0; i < N; i++)
        print(i);

	return 0;
}




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

int main() {
  int N;
  cin >> N;
  for (int i = 0; i < N; i++) {
    char S;
    cin >> S;
    if (S == 'Y') {
      cout << "Four" << endl;
      return 0;
    }
  }
  cout << "Three" << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdint>
using namespace std;
using dlong = long long int;

int main(){
    dlong n,num,k,count;
    cin >> n;
    if(n%2 == 1){cout<< 0; return 0;}
    num=n;
    int p=1;
    while(num/5>=1){p++;num=num/5;}
    k = 5;
    count=0;
    for(int i=0;i<=p;i++){
        count += n/k/2;
        k *= 5;
    }
    cout << count ;
    return 0;
}

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

using namespace std;

int main(){
  int k;
  vector<int> data;
  string str, _str;
  string::iterator i, j;

  while(1){
    getline(cin, str);
    if(str == "END OF INPUT") break;

    i = str.begin();
    while(1){
      j = find(i, str.end(), ' ');
      copy(i, j, back_inserter(_str));
      data.push_back(_str.size());
      _str.clear();
      if(j == str.end()) break;
      i = j+1;
    }

    for(k=0; k<data.size(); ++k)
      cout << data[k];
    cout << endl;

    data.clear();
  }

  return 0;
}

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

int main() {
	int A,B,C,D; cin >>A>>B>>C>>D;
	complex<int> W(A,B),X(C,D),Y,Z,i(0,1);
	Y = X + (X-W)*i;
	Z = Y - (X-W);
	cout << Y.real() << " " << Y.imag() << " " << Z.real() << " " << Z.imag() << endl;
}

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

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

using namespace std;

typedef long long ll;

vector<string> split(const string &str, char sep)
{
    vector<string> v;
    stringstream ss(str);
    string buffer;
    while( getline(ss, buffer, sep) ) {
        v.push_back(buffer);
    }
    return v;
}

int main()
{
    int K;
    cin >> K;
    const string S = "1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51";
    vector<string> splitS = split(S, ' ');
    string ans = splitS[K - 1];
    int size = ans.size();
    for (int i = 0; i < size; ++i)
    {
        char c = ans[i];
        if (c != ',') cout << c;
     }
}


Measured memory_bytes: 256
// スタックサイズ: 100MB

#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <unordered_map>
#include <string>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <functional>
#include <numeric>
#include <iomanip>
#include <queue>
#include <list>
#include <set>
using namespace std;

typedef int64_t ll;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
const ll INF = 1000000000000000000;
#define fori(i, a, b) for (ll i = (a); i < (b); ++i)
#define ford(i, a, b) for (ll i = (b - 1); (a) <= i; --i)
#define rep(i, n) fori(i, 0, n)
#define all(v) (v).begin(), (v).end()
#define fst first
#define snd second
ll pw(ll x, ll y) { ll r = 1;  rep(i, y) { r *= x; }; return r; }


int main() {
	
	ll N, C;
	cin >> N >> C;
	vll x(N + 2, 0), v(N + 2, 0);
	rep(i, N) cin >> x[i + 1] >> v[i + 1];
	x[N + 1] = C;

	vll rx(N + 2, 0), max_rx(N + 2, 0);
	fori(i, 1, N + 1) {
		rx[i] = rx[i - 1] - x[i] + x[i - 1] + v[i];
		max_rx[i] = max(max_rx[i - 1], rx[i]);
	}
	vll lx(N + 2, 0), max_lx(N + 2, 0);
	ford(i, 1, N + 1) {
		lx[i] = lx[i + 1] + x[i] - x[i + 1] + v[i];
		max_lx[i] = max(max_lx[i + 1], lx[i]);
	}

	ll ans = -INF;
	fori(i, 0, N + 1) ans = max(ans, rx[i] - x[i] + max_lx[i + 1]);
	ford(i, 1, N + 2) ans = max(ans, lx[i] - C + x[i] + max_rx[i - 1]);
	cout << ans << endl;
}

Measured memory_bytes: 4992
#include <vector>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <cstdlib>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define REP(i,n) for(int i=0;i<n;i++)
#define SORT(c) sort((c).begin(),(c).end())
#define ALL(a) (a).begin(),(a).end()

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

  int a,b;
  cin >> a >> b;
  int maxButton = max(a, b);

  int ans = maxButton * 2;
  if(a != b) {
    ans--;
  }

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


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

int main(){
  int a,b;
  bool f,g;

  g = true;
  while(1){
    cin >> a >> b;
    if(!a && !b)break;

    if(!g)cout << endl;

    f = false;
    for(int i=a;i<=b;i++){
      if( !(i%400) ){
	cout << i << endl;
	f = true;
      }else if( !(i%100) ){
      }else if( !(i%4) ){
	cout << i << endl;
	f = true;
      }
    }
    if(!f)cout << "NA" << endl;
    g = false;
  }
}

Measured memory_bytes: 0
#
n = int(input())
dic  = {}
a = [None] * n
for i in range(n):
    c, key, val = (input() + " 0").split()[:3]
    if c == "0":
        dic[key] = val
    else:
        a[i] = dic[key]

for x in a:
    if x is not None:
        print(x)



Measured memory_bytes: 43416
works = gets.chomp.to_i.times.map { |list, _| 
  a, b = gets.chomp.split(' ').map(&:to_i)
  { time: a, limit: b }
}

works.sort_by! { |w| w[:time] }
works.sort_by! { |w| w[:limit] }

worktime = 0
result = (works.reduce(-1) do |buffer, work|
  worktime += work[:time]
  break -1 if worktime > work[:limit] && buffer < work[:time]
  next (buffer - work[:time]) if buffer < work[:time]
  work[:limit] - worktime
end)

puts result == -1 ? "No" : "Yes"


Measured memory_bytes: 67852