akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>  
#include <ext/pb_ds/tree_policy.hpp>   
using namespace std;
using namespace __gnu_pbds;  
typedef tree<int, null_type, less<int>, rb_tree_tag,  tree_order_statistics_node_update>  ordered_set; 
#define num 1000000007
//#define num 998244353
#define REP(i,a,n) for(ll i=a;i<n;i++)
#define inarr(i,a,n,A) for(ll i=a;i<n;i++) { cin>>A[i]; }
#define vll vector<long long>
#define pii pair <int,int>
#define pll pair<long long, long long>
#define vpii vector< pair <int,int>>
#define vpll vector< pair<long long, long long>>
#define avg(a,b) ((a)+(b))/2
#define pb push_back
#define pob pop_back
#define sf int flag=0     //Remember semicolon
#define assmin(a,b) if(b<=a) { a=b; }
#define assmax(a,b) if(b>=a) { a=b; }
#define f first
#define s second
#define fix(f,n) std::fixed<<std::setprecision(n)<<f
#define all(x) x.begin(), x.end()
#define M_PI 3.14159265358979323846
#define epsilon (long double)(0.00000000001)
#define side 1e9
#define watch(x) cout << (#x) << " is " << (x) << endl
typedef long long ll;

ll mod(ll a, ll b)
{
	if(a%b<0)
	{
		return a%b + b;
	}
	return a%b;
}
 
 
ll mod_exp(ll a, ll b, ll c)
{
	ll res=1;
	a=a%c;
	while(b>0)
	{
		if(b%2==1)
		{
			res=(res*a)%c;
		}
		b/=2;
		a=(a*a)%c;
	}
	return res;
}
ll mymod(ll a,ll b)
{
    return ((a%b)+b)%b;
}
bool prime[200001];
void SieveOfEratosthenes() 
{ 
    memset(prime, true, sizeof(prime)); 
    prime[1]=false;
    for (int p=2; p*p<=200000; p++) 
    { 
        if (prime[p] == true) 
        { 
            for (int i=p*p; i<=200000; i += p) 
                prime[i] = false; 
        } 
    } 
    return;
}
ll powe[100005];
void power()
{
    powe[0]=1;
    REP(i,1,100005)
    {
        powe[i]=mymod(2*powe[i-1],num);
    }
}
ll gcdExtended(ll,ll,ll *,ll *);
ll modInverse(ll a, ll m) 
{ 
    ll x, y; 
    ll g = gcdExtended(a, m, &x, &y); 
        ll res = (x%m + m) % m;
        return res;
} 
ll gcdExtended(ll a, ll b, ll *x, ll *y) 
{ 
    if (a == 0) 
    { 
        *x = 0, *y = 1; 
        return b; 
    } 
    ll x1, y1; 
    ll gcd = gcdExtended(b%a, a, &x1, &y1); 
    *x = y1 - (b/a) * x1; 
    *y = x1; 
    return gcd; 
}
struct node
{
	vll adj;
    ll waysblack;
    ll wayswhite;
};
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s,t;
    cin>>s>>t;
    if(t.substr(0,s.size())==s)
    {
        cout<<"Yes\n";
    }
    else
    {
        cout<<"No\n";
    }
    return 0;
}




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


def solve(N: int, K: int):
    result = 0
    for i in range(1, N + 1):
        # print(i)
        if i < K:
            count = math.ceil(math.log2(K / i))
            result += (1 / N) * 0.5 ** (count)
        else:
            result += 1 / N
    print(result)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    solve(N, K)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3060
s = gets.chomp.chars
n = s.length
cnt = 0
for i in 1..(n-1)
    if s[i] == s[i-1]
        if s[i] == '1'
            s[i] = '0'
            cnt += 1
        else
            s[i] = '1'
            cnt += 1
        end
    end
end
puts cnt

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

int main() {
  int n[5];

  for (int i = 0; i < 5; i++) {
    cin >> n[i];
  }
  sort(n, n + 5);
  
  cout << n[4] << " " << n[3] << " " << n[2] << " " << n[1] << " " << n[0] << endl;
}

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

template <typename T>
struct edge
{
    int src, to;
    T cost;

    edge(int to, T cost) : src(-1), to(to), cost(cost) {}

    edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}

    edge &operator=(const int &x)
    {
        to = x;
        return *this;
    }

    operator int() const { return to; }
};

template <typename T>
using Edges = vector<edge<T>>;
template <typename T>
using WeightedGraph = vector<Edges<T>>;
using UnWeightedGraph = vector<vector<int>>;
template <typename T>
using Matrix = vector<vector<T>>;

template <typename G>
struct DoublingLowestCommonAncestor
{
    const int LOG;
    vector<int> dep;
    const G &g;
    vector<vector<int>> table;

    DoublingLowestCommonAncestor(const G &g) : g(g), dep(g.size()), LOG(32 - __builtin_clz(g.size()))
    {
        table.assign(LOG, vector<int>(g.size(), -1));
    }

    void dfs(int idx, int par, int d)
    {
        table[0][idx] = par;
        dep[idx] = d;
        for (auto &to : g[idx])
        {
            if (to != par)
                dfs(to, idx, d + 1);
        }
    }

    void build()
    {
        dfs(0, -1, 0);
        for (int k = 0; k + 1 < LOG; k++)
        {
            for (int i = 0; i < table[k].size(); i++)
            {
                if (table[k][i] == -1)
                    table[k + 1][i] = -1;
                else
                    table[k + 1][i] = table[k][table[k][i]];
            }
        }
    }

    int query(int u, int v)
    {
        if (dep[u] > dep[v])
            swap(u, v);
        for (int i = LOG - 1; i >= 0; i--)
        {
            if (((dep[v] - dep[u]) >> i) & 1)
                v = table[i][v];
        }
        if (u == v)
            return u;
        for (int i = LOG - 1; i >= 0; i--)
        {
            if (table[i][u] != table[i][v])
            {
                u = table[i][u];
                v = table[i][v];
            }
        }
        return table[0][u];
    }
};

int main()
{
    int N, Q;
    scanf("%d", &N);
    UnWeightedGraph g(N);
    for (int i = 0; i < N; i++)
    {
        int k;
        scanf("%d", &k);
        while (k--)
        {
            int c;
            scanf("%d", &c);
            g[i].push_back(c);
        }
    }
    DoublingLowestCommonAncestor<UnWeightedGraph> lca(g);
    lca.build();
    scanf("%d", &Q);
    while (Q--)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        printf("%d\n", lca.query(x, y));
    }
}


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

#define ln                '\n'
#define all(dat)           dat.begin(), dat.end()
#define loop(i, to)        for (int i = 0; i < to; ++i)
#define cont(i, to)        for (int i = 1; i <= to; ++i)
#define circ(i, fm, to)    for (int i = fm; i <= to; ++i)
#define foreach(i, dat)    for (__typeof(dat.begin()) i = dat.begin(); i != dat.end(); ++i)

typedef long long          num;

using namespace std;

const int nsz = int(2e5), lgsz = 60;
int n, to[nsz + 5][lgsz + 5];
num k;

int inline go(int fm, num len) {
	circ (k, 0, lgsz) {
		if (len >> k & 1)  fm = to[fm][k];
	}
	return fm;
}

int main() {
	ios::sync_with_stdio(0);
	cin >> n >> k;
	cont (i, n) {
		cin >> to[i][0];
	}
	cont (k, lgsz) {
		cont (i, n) {
			to[i][k] = to[to[i][k - 1]][k - 1];
		}
	}
	cout << go(1, k) << ln;
}

Measured memory_bytes: 54436
X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A = sorted(A, reverse=True)
B = sorted(B, reverse=True)
C = sorted(C, reverse=True)

D = []
for i in range(X):
    for j in range(Y):
        D.append(A[i] + B[j])

D.sort(reverse=True)
E = []
for i in range(min(K, len(D))):
    for j in range(Z):
        E.append(D[i] + C[j])

E.sort(reverse=True)
for i in range(K):
    print(E[i])

Measured memory_bytes: 147776
"use strict";

function _slicedToArray(arr, i) { return _arrayWithHoles(arr) || _iterableToArrayLimit(arr, i) || _nonIterableRest(); }

function _nonIterableRest() { throw new TypeError("Invalid attempt to destructure non-iterable instance"); }

function _iterableToArrayLimit(arr, i) { var _arr = []; var _n = true; var _d = false; var _e = undefined; try { for (var _i = arr[Symbol.iterator](), _s; !(_n = (_s = _i.next()).done); _n = true) { _arr.push(_s.value); if (i && _arr.length === i) break; } } catch (err) { _d = true; _e = err; } finally { try { if (!_n && _i["return"] != null) _i["return"](); } finally { if (_d) throw _e; } } return _arr; }

function _arrayWithHoles(arr) { if (Array.isArray(arr)) return arr; }

!function () {
  function splitNum(line) {
    return (Array.isArray(line) ? line : line.split(/\s+/)).map(function (n) {
      return parseInt(n);
    });
  }

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

  !function (input) {
    var lines = input.split("\n");

    var _splitNum = splitNum(lines[0]),
        _splitNum2 = _slicedToArray(_splitNum, 1),
        N = _splitNum2[0];

    var A = splitNum(lines[1]).slice(0, N);
    console.log(A.reduce(gcd));
  }(require("fs").readFileSync("/dev/stdin", "utf8"));
}();


Measured memory_bytes: 30784
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
using namespace std;
using ll = long long;
int h[100000];
int main(){
    int n;
    cin >> n;
    rep(i,n)cin >> h[i];
    rep(i,n-2){
        auto ri = n-2-i;
        if(h[ri]>1+h[ri+1]){
            cout << "No" << endl;
            return 0;
        }
        if(h[ri]==1+h[ri+1])h[ri]--;
    }
    cout << "Yes" << endl;
    return 0;
}

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

using namespace std;

int main() {
	int N;
	cin >> N;
	bool b = true;
	for (int n = 0;n<N;++n) {
		int m;
		cin >> m;
		if (0 == m %2) {
			if (0 != m%3 && 0 != m%5) {
				b = false;
			}
		}
	}
	if (b) {
		cout << "APPROVED" << endl;
	}
	else{
		cout << "DENIED" << endl;
	}
	return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
#define INF 1145141919810893364
//#define INF 810114514
#define PI 3.141592653589
typedef pair<int,int> PP;
typedef long long ll;
#define int ll
#define setdouble setprecision
#define REP(i,n) for(int i=0;i<(n);++i)
#define OREP(i,n) for(int i=1;i<=(n);++i)
#define RREP(i,n) for(int i=(n)-1;i>=0;--i)
#define GOODBYE do { cout << "0" << endl; return 0; } while (false)
#define MM <<" "<<
#define Endl endl

vector<int> compress(vector<int> D){
    map<int,int> G;
    vector<int> E,r;
    int s=D.size();
    for(int i=0;i<s;i++){
        E.push_back(D[i]);
    }
    sort(E.begin(),E.end());
    int t=0;
    for(int i=0;i<s;i++){
        if(i!=0 && E[i]!=E[i-1]){
            t++;
        }
        G[E[i]]=t;
    }
    for(int i=0;i<s;i++){
        r.push_back(G[D[i]]);
    }
    return r;
}


signed main(void){
    int N,K;
    int A[214514],B[214514]={};
    cin >> N >> K;
    REP(i,N){
        cin >> A[i];
    }
    B[0]=0;
    REP(i,N){
        B[i+1]=B[i]+A[i];
        B[i+1]%=K;
    }
    REP(i,N+1){
        B[i]+=(K-(i%K));
        //B[i]++;
        B[i]%=K;
    }
    //REP(i,N+1){cout << B[i] << " ";}cout << endl;
    vector<int> D;
    REP(i,N+1){
        D.push_back(B[i]);
    }
    D=compress(D);
    vector<int> G[214514];
    int Dmx=0;
    REP(i,D.size()){
        G[D[i]].push_back(i);
        Dmx=max(Dmx,D[i]);
    }
    int Ans=0;
    REP(j,Dmx+1){
        int l=0,r=1;
        int num=0;
        while(l<G[j].size()){
            if(G[j][r]-G[j][l]<K && r!=G[j].size()){
                r++;
            }else{
                num+=(r-l-1);
                l++;
            }
        }
        Ans+=num;
    }
    cout << Ans << endl;
    return 0;
}



Measured memory_bytes: 25072
<?php /*atcoder.php*/

$at = new Atcoder();
$at->main();
unset($at);

class Atcoder{
	private function arrayIn(){
		$buf = explode(" ", fgets(STDIN));
		return $this->killNewLine($buf);
	}
	private function killNewLine($buf = null){
		$buf = str_replace("\r\n", "", $buf);
		$buf = str_replace("\n", "", $buf);
		$buf = str_replace("\r", "", $buf);
		return $buf;
	}

	public function main(){
		$s = $this->arrayIn();
		
		$ans = 0;

		if(($s[0] * $s[2]) < $s[1]){
			echo $s[2] . "\n";
		}else{
			while(true){
				if($s[0] <= $s[1]){
					$s[1] -= $s[0];
					$ans++;
				}else{
					break 1;
				}
			}
			echo $ans . "\n";
		}
	}
}
?>


Measured memory_bytes: 4728
#include <bits/stdc++.h> 
using namespace std; 
#define io ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define rep(i,n) for (int i = 0; i < (n); ++i)

int main(void) {
    io;
    int i; cin >> i;
    cout << (i < 1200 ? "ABC" : "ARC");
    return 0;
}



Measured memory_bytes: 3612
#include <stdio.h>
#include <stdlib.h>

long com(int n, int r){
  int i;
  long p = 1;
  
  for(i = 1; i <= r; i++){
    p = p * (n - i + 1) / i;
  }

  return p;
}

int main(void){
  int n,p;
  int odd = 0;
  int even = 0;
  long res = 0;
  int i;

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

  for(i = 0; i < n;i++){
    int tmp;
    scanf("%d",&tmp);

    if(tmp % 2 == 0)
      even++;
    else
      odd++;
  }
  
  //even do not affect result
  long ev = 0;
  for(i = 0; i <= even;i++){
    ev += com(even,i);
  }
  

  //odd
  long od = 0;
  if(p == 0){
    for(i = 0; i <= odd; i+=2)
      od += com(odd,i);
  }else{
    for(i = 1; i <= odd; i += 2)
      od += com(odd,i);
  }

  

  res = od * ev;

  printf("%ld\n",res);

  return 0;
}


Measured memory_bytes: 128
//make sure to make new file!
import java.io.*;
import java.util.*;

public class Main{
   
   public static void main(String[] args)throws IOException{
      BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
      PrintWriter out = new PrintWriter(System.out);
      
      int n = Integer.parseInt(f.readLine());
      
      String s = f.readLine();
      
      if(s.length() <= n){
         out.println(s);
      } else {
         out.println(s.substring(0,n) + "...");
      }
      
      
      
      
      
      
      
      
      
      out.close();
   }
   
      
}

Measured memory_bytes: 36688
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, c) for (int i = 0; i < (int)c; i++)
#define all(v) v.begin(), v.end()
using ll = long long;
using P = pair<int, int>;
const int inf = 1000000000; //10^9
const ll MOD = 1e9 + 7;
//加算代入演算子は+=！！！！！
//int 2^31 10^9まで
int main()
{
    string o, e;
    cin >> o >> e;
    rep(i, o.length()) {
        cout << o[i];
        if(i < e.length()) cout << e[i];
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
    int a, b[a], c, d=1,e;

 scanf("%d",&a);
  for(c=0;c<a;c++){
   scanf("%d",&b[c]);
  }
  for(e=1;e<a;e++){
   if(b[0]<=b[e]){
   d = ++d;
   b[0]=b[e];
    }
  }
printf("%d",d);

return 0;

}

Measured memory_bytes: 128
using System;
using System.Linq;

namespace CSharp
{
    class Program
    {
        static void Main()
        {
            var S = Console.ReadLine().ToCharArray();

            var result = string.Empty;
            for (int i = 0; i < S.Length; i++)
            {
                for (int j = i; j < S.Length; j++)
                {
                    var temp = string.Empty;
                    for (int k = i; k <= j; k++)
                    {
                        temp += S[k];
                    }
                    if (temp.Length == temp.Count(c => c == 'A' || c == 'C' || c == 'G' || c == 'T'))
                    {
                        if (temp.Length > result.Length)
                        {
                            result = temp;
                        }
                    }
                }
            }
            Console.WriteLine(result.Length);
        }
    }
}


Measured memory_bytes: 11220
fun main(args: Array<String>) = println(run {
    val n = readLine()!!.toInt()
    val h = readLine()!!.split(" ").map { it.toInt() }

    h.mapIndexed { i, v->
        if(i==0) true
        else h.take(i).all { it<=v }
    }.count { it }

})



Measured memory_bytes: 36072
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		double r = sc.nextDouble();

		System.out.printf("%.10f %.10f\n", r*r*Math.PI, (2*r)*Math.PI);

		sc.close();

	}
}



Measured memory_bytes: 28092
#include<stdio.h>
#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
#include<map>
#include<cmath>
#include<math.h>
#include<iomanip>
 
using namespace std;
using ll = long long int;
 
int n, k;
 
int main(void) {
	cin >> n >> k;
	long double ret = 0., tmp;
	for (int i = 1; i <= n; i++) {
		int win = ceil(log2(double(k) / i));
		tmp = pow(2, -1 * win);
		if (tmp > 1.)
			tmp = 1.;
		ret += tmp;
	}
	cout << setprecision(20) << ret / n << endl;
	return 0;
}

Measured memory_bytes: 512
from collections import deque

def mk_idx(y,x):
    return y*22+x

H,W=map(int, input().split())
DINF = 100000
S = []
S.append('#' * (W+2))
for i in range(H):
    S.append('#'+ input() + '#')
S.append('#' * (W+2))
dmax = 0
G = [ [] for _ in range( mk_idx(22,22) ) ]
for y in range(1,H+1):
    for x in range(1,W+1):
        if (S[y][x] == '.'):
            if (S[y-1][x] == '.'):  G[ mk_idx(y,x) ].append( mk_idx(y-1,x) )
            if (S[y][x-1] == '.'):  G[ mk_idx(y,x) ].append( mk_idx(y,x-1) )
            if (S[y+1][x] == '.'):  G[ mk_idx(y,x) ].append( mk_idx(y+1,x) )
            if (S[y][x+1] == '.'):  G[ mk_idx(y,x) ].append( mk_idx(y,x+1) )

for y in range(1,H+1):
    for x in range(1,W+1):
        if S[y][x] == '.':
            d = [ DINF for _ in range( mk_idx(22,22) ) ]
            d[ mk_idx(y,x) ] = 0
            q = deque( [mk_idx(y,x)] )
            while len(q) != 0:
                v = q.popleft()
                n = d[v];
                dmax = max(dmax, n)
                for nv in G[v]:
                    if d[ nv ] <= n+1 :
                        continue
                    d[ nv ] = n+1
                    q.append(nv)
print(dmax)



Measured memory_bytes: 3436
import java.util.*;

public class Main  {
   public static void main(String[] args)  {
      Scanner sc = new Scanner(System.in);
      
      
      String s = sc.next();
      String t = sc.next();
            
      if (s.equals(t.substring(0, s.length()))) {
          
         System.out.println("Yes");
         
      } else {
         System.out.println("No");         
      }
   }
}

Measured memory_bytes: 35796
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
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; }

bool check(vector<P> s){
	int h = 0;
	for(P p : s){
		int b = h + p.first;
		if(b < 0) return false;
		h += p.second;
	}
	return true;
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<P> ls, rs;
	int total = 0;
	rep(i,n){
		string s;
		cin >> s;
		int h = 0, b = 0;
		for(char c : s){
			if(c == '(') ++h;
			else --h;
			chmin(b, h);
		}
		if(h > 0) ls.emplace_back(b, h);
		else rs.emplace_back(b-h, -h);
		total += h;
	}
	sort(ls.rbegin(), ls.rend());
	sort(rs.rbegin(), rs.rend());
	if(check(ls) && check(rs) && total == 0) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

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

#define fast1 ios_base::sync_with_stdio(false)
#define fast2 cin.tie(NULL)
#define ll long long

using namespace std;

int main(){

    int n;
    cin >> n;

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

    int dp[100008];
    for(int i=0;i<100008;i++){
        dp[i]=INT_MAX;
    }


    dp[0]=0;

    for(int i=0;i<n-1;i++){
        if(i==n-2){
            dp[i+1]=min(dp[i]+abs(a[i]-a[i+1]),dp[i+1]);
        }else{
            dp[i+1]=min(dp[i]+abs(a[i]-a[i+1]),dp[i+1]);
            dp[i+2]=min(dp[i]+abs(a[i]-a[i+2]),dp[i+2]);
        }
    //cout << dp[i] << " ";
    }

    cout << dp[n-1] << "\n";


    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define st first
#define nd second

using namespace std;

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

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

const int N = 100100;
int n, use[N], uz[N][12], a, b, c[N], d[N], m, q, x[N];
vector <int> v[N];

void dfs(int node, int d, int col) {
	// dbg(node, d);
	if(!use[node]) use[node] = col;
	uz[node][d] = 1;
	if(d == 0) return;

	for(auto i : v[node])
		if(uz[i][d - 1] == 0)
			dfs(i, d - 1, col);
}

int main() {
	ios_base::sync_with_stdio(false);

	cin >> n >> m;
	for(int i = 1; i <= m; i++) {
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}

	cin >> q;
	for(int i = 1; i <= q ;i++) 
		cin >> x[i] >> d[i] >> c[i];

	for(int i = 1; i <= q ;i++) 
		dfs(x[q - i + 1], d[q - i + 1], c[q - i + 1]);
	
	for(int i = 1; i <= n; i++) 
		cout << use[i] << '\n';
}	

	

Measured memory_bytes: 12792
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Print_a_Rectangle
{
    class Program
    {
        static void Main(string[] args)
        {
            List<string> inputs = new List<string>();

            while (true)
            {
                string temp = Console.ReadLine();
                if (temp.Equals("0 0"))
                {
                    break;
                }

                inputs.Add(temp);
            }

            foreach (string item in inputs)
            {
                string[] input = item.Split(' ');

                int num1 = int.Parse(input[0]);
                int num2 = int.Parse(input[1]);

                for (int i = 0; i < num1; ++i)
                {
                    for (int j = 0; j < num2; ++j)
                    {
                        Console.Write("#");
                    }
                    Console.WriteLine();
                }
                Console.WriteLine();
            }



                

            
        }
    }
}



Measured memory_bytes: 15972
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

using pi = pair<int,int>;

struct State{
    // (y,x), floor f, bit b
    int y,x,f,b;
};

inline int switch_num(char c){
    if('a'<=c && c<='j') return c-'a';
    if('A'<=c && c<='J') return c-'A';
    return -1;
}

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

const int INF = 19191919;
const int N = 50, M = 1<<10;
int d[N][N][2][M];

int main(){
    int w,h;
    cin >>w >>h;

    vector<string> m(h);
    rep(i,h) cin >>m[i];

    int s;
    cin >>s;
    vector<vector<string>> ms(s);
    rep(i,s){
        ms[i] = vector<string>(h);
        rep(j,h) cin >>ms[i][j];
    }

    queue<State> que;
    rep(i,N)rep(j,N)rep(k,2)rep(l,M) d[i][j][k][l] = INF;

    pi start, goal;
    rep(i,h)rep(j,w){
        if(m[i][j] == '%') start = {i,j};
        if(m[i][j] == '&') goal = {i,j};
    }

    auto IN = [&](int y, int x){ return 0<=y && y<h && 0<=x && x<w; };
    auto FLOOR = [&](int y, int x, int bit){
        int ret = 0;
        if(m[y][x]=='^' || ('A'<=m[y][x] && m[y][x]<='J')) ret = 1;
        rep(i,s)if(bit>>i&1){
            if(ms[i][y][x]=='*') ret = !ret;
        }
        return ret;
    };

    auto CHECK = [&](State c, State nc){
        if(d[nc.y][nc.x][nc.f][nc.b] > d[c.y][c.x][c.f][c.b]+1){
            d[nc.y][nc.x][nc.f][nc.b] = d[c.y][c.x][c.f][c.b]+1;
            que.push({nc});
        }
    };

    d[start.fi][start.se][0][0] = 0;
    que.push({start.fi, start.se, 0, 0});
    while(!que.empty()){
        State c = que.front();
        que.pop();

        // move another floor
        if(m[c.y][c.x]=='|'){
            State nc(c);
            nc.f = !nc.f;
            CHECK(c, nc);
        }

        // operate switch
        int sn = switch_num(m[c.y][c.x]);
        if(sn!=-1){
            State nc(c);
            nc.b ^= (1<<switch_num(m[c.y][c.x]));
            if(ms[sn][c.y][c.x] == '*') nc.f = !nc.f;
            CHECK(c, nc);
        }

        // move adjacent
        rep(i,4){
            State nc(c);
            nc.y += dy[i];
            nc.x += dx[i];
            if(!IN(nc.y, nc.x) || m[nc.y][nc.x]=='#') continue;

            if(m[nc.y][nc.x]=='|' || nc.f==FLOOR(nc.y,nc.x,nc.b)) CHECK(c, nc);
        }
    }

    int ans = INF;
    rep(i,2)rep(j,1<<s) ans = min(ans, d[goal.fi][goal.se][i][j]);
    if(ans == INF) ans = -1;
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 23652
N, D = map(int, input().split())
Z = []
for _ in range(N):
    ver = list(map(int,input().split()))
    Z.append(ver)

cnt = 0

for i in range(N):
    dist = (Z[i][0]**2 + Z[i][1]**2)**0.5
    if dist <= D:
        cnt += 1

print(cnt)



Measured memory_bytes: 102996
package main

import (
	"fmt"
)

func main() {
	var s string
	fmt.Scanf("%s\n", &s)
	l := len(s)
	for i := 0; i < l; i++ {
		for j := 0; j < l - i; j++ {
			if s[:i] + s[i+j:] == "keyence" {
				fmt.Println("YES")
				return
			}
		}
	}
	fmt.Println("NO")
}


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

using namespace std;

typedef long long ll;
typedef long double Double;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

// chmax, chmin
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;
}

typedef complex<double> P;

void solve(long long N, std::vector<long long> x, std::vector<long long> y) {
    vector<P> ps;
    for (int i = 0; i < N; i++) ps.emplace_back(x[i], y[i]);

    auto getTarget = [&](P p) {
        double d = -1;
        int idx;
        for (int i = 0; i < ps.size(); i++) {
            if (d < abs(ps[i] - p)) {
                d = abs(ps[i] - p);
                idx = i;
            }
        }
        return ps[idx];
    };

    double c = 1.0;
    double eps = 0.999;
    P ans = P(0, 0);
    for (int i = 0; i < 100000; i++) {
        ans += (getTarget(ans) - ans) * c;
        c *= eps;
    }
    printf("%.10lf\n", abs(ans-getTarget(ans)));
}

int main() {
    long long N;
    scanf("%lld", &N);
    std::vector<long long> x(N);
    std::vector<long long> y(N);
    for (int i = 0; i < N; i++) {
        scanf("%lld", &x[i]);
        scanf("%lld", &y[i]);
    }
    solve(N, std::move(x), std::move(y));
    return 0;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <array>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>
#include <functional>
#include <random>
#include <ctime>

using namespace std;

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << ": " << arg1 << " |";
  __f(comma + 1, args...);
}

typedef long long int64;
typedef pair<int, int> ii;
const int INF = 1 << 29;
const int MOD = 1e9 + 7;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x; }

const int N = 1e5 + 10;
char s[N];

int main() {
  int n;
  scanf("%d%s", &n, s);
  for (int i = 0; s[i]; ++i) {
    int k = s[i] - 'A';
    k = (k + n) % 26;
    s[i] = (char)('A' + k);
  }
  puts(s);
  return 0;
}


Measured memory_bytes: 256
n = int(input())
st = input()
st_split = st.split(" ")
s = st_split[0]
r = st_split[1]

newstring = ""
#zに文字を足していく
#リストS、Tについて繰り返しを用いて1文字ずつ抽出し、リストに足していく
for i in range(n):
    newstring += s[i]
    newstring += r[i]
print(newstring)

Measured memory_bytes: 3060
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <iostream>
#include <iomanip>
#include <stdlib.h>

using namespace std;

int main()
{
  long long int q,h,s,d,n;
  cin >> q >> h >> s >> d >> n;

  long long int x,y;
  x = min( s , min ( 2*q , h) * 2 );
  y = min( d , 2*x );

  long long int ans = 0;
  ans += y * ( n/2 );
  ans += x * ( n%2 );

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <cstring>
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <list>  
#include <cassert>
#include <ctime>
#include <climits>
using namespace std;  

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }

const int MAXN=9;

int D;

int d[MAXN],n;

ll mem[MAXN+1][MAXN+1][2*MAXN+1][2][2][2];

ll calc(int dl,int dh,int len,bool incarry,bool outcarry,bool canzero) {
	if(len==0) {
		assert(dl>dh);
		//if(incarry==outcarry) printf("!\n");
		return incarry==outcarry?1:0;
	}
	ll &ret=mem[dl][dh+1][len][incarry?1:0][outcarry?1:0][canzero?1:0];
	if(ret==-1) {
		assert(dh-dl+1<=len);
		bool uselft=dh-dl+1==len;
		bool usergt=dl<=dh;
		ret=0;
		//printf("calc(%d,%d,%d,%c,%c,%c)\n",dl,dh,len,incarry?'V':'x',outcarry?'V':'x',canzero?'V':'x');
		if(len==1) {
			REP(x,10) {
				int sum=x+(incarry?1:0)+(usergt?d[dh]:0);
				if(sum%10==x&&((sum>=10)==outcarry)&&(canzero||x!=0)) ++ret;
			}
		} else {
			REP(x,10) {
				int hsum=x+(incarry?1:0)+(usergt?d[dh]:0);
				int y=hsum%10;
				int lsum=y+(uselft?d[dl]:0);
				//printf("\tcalc(%d,%d,%d,%c,%c,%c): %d -> hsum=%d y=%d lsum=%d\n",dl,dh,len,incarry?'V':'x',outcarry?'V':'x',canzero?'V':'x',x,hsum,y,lsum);
				if(lsum%10==x&&((lsum>=10)==outcarry)&&(canzero||y!=0)) {
					ret+=calc(dl+(uselft?1:0),dh-(usergt?1:0),len-2,hsum>=10,false,true);
				}
				if((lsum+1)%10==x&&((lsum+1>=10)==outcarry)&&(canzero||y!=0)) {
					ret+=calc(dl+(uselft?1:0),dh-(usergt?1:0),len-2,hsum>=10,true,true);
				}
			}
		}
		//printf("calc(%d,%d,%d,%c,%c,%c)=%lld\n",dl,dh,len,incarry?'V':'x',outcarry?'V':'x',canzero?'V':'x',ret);
	}
	return ret;
}

ll solve(int D) {
	n=0; for(int x=D;x!=0;x/=10) d[n++]=x%10; reverse(d,d+n);
	//REP(i,n) printf("%d ",d[i]); puts("");

	ll ret=0;
	memset(mem,-1,sizeof(mem));
	FORE(len,n,2*n) ret+=calc(0,n-1,len,false,false,false);
	return ret;
}

void run() {
	scanf("%d",&D); 
	printf("%lld\n",solve(D));
}

int rev(int x) {
	n=0; for(;x!=0;x/=10) d[n++]=x%10; int ret=0; REP(i,n) ret=10*ret+d[i]; return ret;
}

void stress() {
	FORE(d,1,1000) {
		if(d!=900) continue;
		int lim=10000*d; ll want=0;
		FORE(i,1,lim) {
			if(i+d==rev(i)) {
				//if(d==90) printf("\t%d\n",i);
				++want;
				//lim=max(lim,1000*i);
			}
		}
		ll have=solve(d);
		if(want!=have) printf("%d: want=%lld have=%lld\n",d,want,have);
	}
}

int main() {
	run();
	//stress();
	return 0;
}


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

int main() {
    int H, W, c[10][10], ans = 0;
    cin >> H >> W;
    for(int i = 0; i < 10; ++i) {
        for(int j = 0; j < 10; ++j) {
            cin >> c[i][j];
            if(c[i][j] == 0)
                c[i][j] = 1e9;
        }
    }

    for(int k = 0; k < 10; ++k)
        for(int i = 0; i < 10; ++i)
            for(int j = 0; j < 10; ++j)
                c[i][j] = min(c[i][j], c[i][k] + c[k][j]);

    for(int i = 0; i < H; ++i) {
        for(int j = 0; j < W; ++j) {
            int A;
            cin >> A;
            if(A == -1 || A == 1)
                continue;
            ans += c[A][1];
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
import sys
from collections import defaultdict
input = sys.stdin.readline
N = int(input().strip())
A = [int(a) for a in input().strip().split()]
d = defaultdict(int)
ans = 0
for a in A:
    if d[a] < a:
        d[a] += 1
    else:
        ans += 1

for key, val in d.items():
    if val < key:
        ans += val

print(ans)

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

int count_n(int n){
    int count = 0;
    count++;
    if (n == 0)
        return 0;
    else 
        return count_n(n/10) + count; 
}

int main(){
   long long n;
   long long minm = 10000000010;
   cin >> n;
   for (int i = 1 ;i <= sqrt(n);i++){
       if((n % i) == 0){
            if(n/i < minm){
                minm = n/i;
            }
       }
   }
   cout << count_n(minm) << endl;
   

}



Measured memory_bytes: 256
#include <stdio.h>

int main(void) {
	int A[4][3][10]={0};
  int N,tou,kai,gou,nin,i,j,k;
  
  scanf("%d",&N);
    for(i=0;i<N;i++){
    	scanf("%d %d %d %d\n",&tou,&kai,&gou,&nin);
      A[tou-1][kai-1][gou-1] += nin;
    }
  
  for(i=0;i<4;i++){
  	for(j=0;j<3;j++){
    	for(k=0;k<10;k++){
        	printf(" %d",A[i][j][k]);
        }
      printf("\n");
    }
    if(i != 3) printf("####################\n");
  }
    return 0;
       
}


Measured memory_bytes: 2108
int r0,r1,r2,a0=1,a1=0,a2,b0=0,b1=1,b2,q1;
int main(){
	scanf("%d%d",&r0,&r1);
	for(;r1>0;){
		q1 = r0 / r1;
		r2 = r0 % r1;
		a2 = a0 - q1*a1;
		b2 = b0 - q1*b1;
		r0 = r1, r1 = r2;
		a0 = a1, a1 = a2;
		b0 = b1, b1 = b2;
	}
	printf("%d %d\n",a0,b0);
	return 0;
}

Measured memory_bytes: 596
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N, K =mi()
A = sorted([ii() for _ in range(N)])

tmp = float('inf')
for i in range(N-K+1):
    if A[i+K-1] - A[i] < tmp:
        tmp = A[i+K-1] - A[i]
print(tmp)


Measured memory_bytes: 8296
#include <bits/stdc++.h>
using namespace std;
typedef int64_t Int;
#define dump(x) cout << (x) << '\n'
Int mod = 1e9+7;

Int gcd(Int n, Int m) {
    Int a = max(n, m);
    Int b = min(n, m);
    return a % b == 0 ? b : gcd(b, a % b);
}

int main() {
    Int n, x;
    cin >> n >> x;
    if (n % x == 0) {
        dump((n - x) * 3LL);
        return 0;
    }
    Int res = x;
    Int tmp = n - x;
    n = x;
    x = tmp;
    if (n % x == 0) {
        dump(res + 2LL * (n / x));
        return 0;
    }
    // cout << n << " " << x << endl;
    res += x + (n / x) * (2LL * x);
    while (true) {
        tmp = n % x;
        n = x;
        x = tmp;
        // cout << n << " " << x << endl;
        if (n % x == 0) {
            res += (n / x) * (2LL * x) - x;
            break;
        }
        else {
            res += (n / x) * (2LL * x);
        }
    } 
    dump(res);
    return 0;
}

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

a = [list(map(int, input().split())) for _ in range(n)]


ans = 0
for i in range(n):
    for j in range(i+1, n):
        l = 0
        for k in range(d):
            l += (a[i][k] - a[j][k]) ** 2
        if (l ** .5).is_integer(): ans += 1

print(ans)

Measured memory_bytes: 38384
#include <bits/stdc++.h>
    using namespace std;
    typedef long long lint;
    typedef pair<int,int> pint;
    typedef vector<int> vint;
    #define rep(i, n) for(int i = 0; i < n; i++)
    #define rep2(i, m, n) for(int i = m; i < n; i++)
    #define rep3(elem, vec) for(auto elem: vec)
    #define SORT(V) sort((V).begin(),(V).end())
    #define RSORT(V) sort((V).rbegin(), (V).rend())
    #define COUT(N) cout<<fixed<<setprecision(N)
    lint gcd(int a,int b){return b?gcd(b,a%b):a;}
    lint lcm(int a,int b){return a*b/gcd(a,b);}
    lint comb(int a,int b){return b?comb(a-1,b-1)*a/b:1;}
    int dx[4] ={1,0,-1,0},dy[4] = {0,1,0,-1};
    int MOD = 1e9+7;

int main(){
    int N;
    cin >> N;
    vint A(N),B(N,0);
    rep(i,N)cin >> A[i];
    rep(i,N){
        if(i-A[i]>=0)B[i-A[i]]++;
    }
    lint a=0;
    rep(i,N){
        if(i+A[i] <N)a+=B[i+A[i]];
    }
    cout << a;
    return 0;
}

Measured memory_bytes: 4844
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<int(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define show(x) cout<< #x << " = " << x << endl
using namespace std;

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

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

int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}	

const ll mod=1e9+7;
const int INF=INT_MAX/2;
const int N_MAX=300010;

ll fact[N_MAX];
ll finv[N_MAX];
//modの掛け算
ll mul(ll x, ll y){
	return (x%mod)*(y%mod)%mod;
}
//xのy乗%mod（繰り返し二乗法)
ll powll(ll x, ll y){
	ll res=1LL;
	while(y){
		if(y&1LL){
			res*=x;
		}
		res%=mod;
		x=(x*x)%mod;
		y>>=1LL;
	}
	return res;
}
//x*(yの逆元)
ll divll(ll x,ll y){
	return (x*powll(y,mod-2))%mod;
}
//nPr%mod
ll nPr(ll n,ll r){
	if(n<r || r<0)return 0;
	return mul(fact[n],finv[n-r]);
}
//nCr%mod
ll nCr(ll n, ll r){
	if(n<r || r<0)return 0;
	return mul(mul(fact[n],finv[r]),finv[n-r]);
}
int main(){
	int n;
	cin>>n;
	string s;
	cin>>s;
	ll r=0,g=0,b=0;
	REP(i,n){
		if(s[i]=='R')r++;
		else if(s[i]=='G')g++;
		else if(s[i]=='B')b++;
	}
	ll sum=r*g*b;
	REP(i,n-2){
		for(int j=1;i+2*j<n;j++){
			if(s[i]!=s[i+j] && s[i+j]!=s[i+2*j] && s[i+2*j]!=s[i]){
				sum--;
			}
		}
	}
	cout<<sum<<endl;
	return 0;
}


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

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

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

const long long INF = 1LL << 60;

long long h[100010];
long long dp[100010];

int main() {
  int N; cin >> N;
  for (int i = 1; i <= N; i++) cin >> h[i];
  for (int i = 0; i < 100010; i++) dp[i] = INF;

  dp[1] = 0;

  for (int i = 1; i <= N; i++) {
    chmin(dp[i+1], dp[i] + abs(h[i+1] - h[i]));
    chmin(dp[i+2], dp[i] + abs(h[i+2] - h[i]));
  }

  cout << dp[N] << endl;
  return 0;
}

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

int main() {
  ll N;
  cin >> N;
  ll ans = 0;
  for (int i = 0; i < 5; i++) {
    ll A;
    cin >> A;
    ans = max(ans, (N + A - 1) / A);
  }
  cout << ans + 4 << endl;
}

Measured memory_bytes: 256
n,a,b,MOD=map(int,input().split())
def matmul(A,B):
	global MOD
	N,M,L=len(A),len(B),len(B[0])
	ret=[[0 for j in range(L)] for i in range(N)]
	for i in range(N):
		for j in range(M):
			for k in range(L):
				ret[i][k] += A[i][j]*B[j][k]%MOD
				ret[i][k] %= MOD
	return ret
ans,c=[[0,a%MOD,1]],0
for i in range(1,19):
	if not a<10**i:
		continue
	m=[[10**i%MOD,0,0],[1,1,0],[0,b%MOD,1]]
	q = -c
	c = min(((10**i-1-a)//b)+1,n)
	q += c
	while q:
		if q&1:
			ans = matmul(ans,m)
		m = matmul(m,m)
		q >>= 1
print(ans[0][0])


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using Graph = vector<vector<int>>;
const int INF = 1e9 + 1;
const ll LLINF = 1e18;
const int MOD = 1e9 + 7;

int main() {
    string S, T;
    cin >> S >> T;
    cout << T << S;
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <complex>
#include <string>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#ifndef LOCAL
#define debug(x) ;
#else
#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;

template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &p) {
  out << "{" << p.first << ", " << p.second << "}";
  return out;
}

template <typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  out << '{';
  for (const T &item : v) out << item << ", ";
  out << "\b\b}";
  return out;
}
#endif

#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 200010


int main(){
  int N;

  cin >> N;

  long double ans = 0;

  for (int i=0; i<N; i++) {
    int a;
    cin >> a;
    ans += 1.0 / a;
  }

  printf("%.10Lf\n", 1.0 / ans);

  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<queue>
#include<stack>
using namespace std;
deque<int> q;
int main()
{    int n;    
scanf("%d",&n);    
 for(int i=1;i<=n;i++) 
    {        int a;        
    scanf("%d",&a);       
     if(i%2==0)           
      q.push_front(a);       
       else           
        q.push_back(a);    }  
          if(n%2==0)    
          {       
               printf("%d",q.front());     
                  q.pop_front();  
                        while(!q.empty())  
                              {     
                                         printf(" %d",q.front());   
                                                  q.pop_front();        }  
  
                                                       
                                                        printf("\n");    }    else    {        printf("%d",q.back());        q.pop_back();        while(!q.empty())        {            printf(" %d",q.back());            q.pop_back();        }        printf("\n");    }     return 0;}


Measured memory_bytes: 2944
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <fstream>
#include <string>
#include <math.h>
#include <cstdlib>
#include <istream>
#include <sstream>
#include <cctype>
#include <iomanip>
//cout << fixed << setprecision(20) << *** << endl;
#define rep(i,N) for(int i=0;i<(int)N;++i)
typedef long long ll;
using namespace std;
int main()
{
	ll h,w;
	cin>>h>>w;
	if(w==1||h==1){
		cout<<"1"<<endl;
	}
	else{
		if((h*w)%2==0){
			cout<<(h*w)/2<<endl;
		}
		else{
			cout<<(h*w)/2+1<<endl;
		}
	}

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int limit = 200050;

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

	int a[limit];
	for(int i = 0; i < n; i++){
		cin >> a[i];
		a[i] = a[i] - i - 1;
	}

	sort(a, a + n);

	int b = (n % 2 == 0) ? a[n / 2 - 1] : a[(n + 1) / 2 - 1];

	long long f = 0;
	for(int i = 0; i < n; i++) f += abs(a[i] - b);

	cout << f << endl;

	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
//解説AC
int gcd(int a, int b){
  if (a%b == 0)return(b);
  else return(gcd(b, a%b));
}

int lcm(int a, int b){
  return a * b / gcd(a, b);
}
int main(){
  long long a, b;
  cin >> a >> b;
  long long n=lcm(a,b);
  long long g=gcd(a,b);
  string s,t;
  cin>>s>>t;
  for(int i=0;i<g;i++){
    //cout<<s[i*a/g]<<" "<<t[i*b/g]<<endl;
    if(s[i*a/g]!=t[i*b/g]){
      cout<<-1<<endl;
      return 0;
    }
  }
  cout<<n<<endl;
  return 0;
}

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

using namespace std;


int main() {
  #ifdef LOCAL
  freopen("sol.in", "r", stdin);
  freopen("sol.out", "w+", stdout);
  #endif
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<vector<int>> grid(n + 1, vector<int>(m + 1));
  for (int i = 1; i <= n; i++) {
    string s;
    cin >> s;
    for (int j = 1; j <= m; j++) {
      grid[i][j] = s[j - 1] == '.';
    }
  }
  vector<vector<int>> dp(n + 1, vector<int>(m + 1));
  dp[1][1] = 1;
  const int mod = (int) 1e9 + 7;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      if (i == 1 && j == 1) {
        continue;
      }
      dp[i][j] = grid[i][j] * (dp[i][j - 1] + dp[i - 1][j]) % mod;  
    }
  }
  cout << dp[n][m] << '\n';
  return 0;
}

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

using namespace std;

int main()
{
    int sum = 0;
    for (int i = 0; i < 3; i++)
    {
        int num;
        cin >> num;
        sum += num;
    }
    if (sum >= 22)
        cout << "bust" << endl;
    else
        cout << "win" << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <cmath>
#define ll long long

using namespace std;

long long MOD = 1000000007;

int main(){
    const double pi=3.141592653589793;
    double A,B,H,M;
    cin >> A >> B >> H >> M;
    cout << setprecision(20) << sqrt(A*A+B*B-2.0*B*A*cos(2*pi*(M/60-H/12-M/720))) << '\n';
}

Measured memory_bytes: 4264
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.OptionalInt;
import java.util.regex.Pattern;
import java.util.stream.Stream;

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

    new Main().run();
  }

  public void run() {
    
    try(BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

      int n = Integer.parseInt(br.readLine());
      String line = br.readLine();
      final Pattern delim = Pattern.compile(" ");
      int[] arrayS = delim
        .splitAsStream(line)
        .parallel()
        .mapToInt(Integer::parseInt)
        .toArray();

      OptionalInt max =
        Arrays.stream(arrayS).max();

      dispIntArray( countingSort(arrayS, max.getAsInt()) );
    }
    catch ( IOException e ) {
      System.out.println("IOException!");
    }

  }

  public int[] countingSort(int[] a, int k) {

    int   aLength = a.length;
    int[] result  = new int[aLength];
    int[] counter = new int[k+1];

    for (int var : a) {
      counter[var]++;
    }

    for (int i=1, max=k+1; i < max; i++) {
      counter[i] += counter[i-1];
    }

    for (int i=aLength-1, val=0; i>=0; i--) {
      val = a[i];
      result[counter[val]-1] = val;
      counter[val]--;
    }

    return result;
  }

  public void dispIntArray(int[] target) {
    StringBuilder s = new StringBuilder();

    for (int i : target) { s.append(i).append(" "); }
    s.setLength(s.length()-1);

    System.out.println(s);
  }
}


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

int main() {
  long double N,K;
  cin >> N >> K;
  vector<long double> V(N);
  for (int i = 0; i < N; i++)
    cin >> V.at(i);
  
  long double a = 0;
  for (int I = 0; I < K; I++) 
    a += V.at(I);
  
  long double count = a;
  long double maxcount = a;
    
  for (int j = 1; j < N - K + 1; j++) {
    count += V.at(j + K - 1) - V.at(j - 1);
    if (count > maxcount)
      maxcount = count;
  }
    
  long double ans = (maxcount + K)/2;  
   
  cout << fixed << setprecision(10);
  cout << ans << endl;
    
}


Measured memory_bytes: 3328