akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
const int inf=1e5+8;
int A[inf];
int n, k;
int dp[inf];

int f(int index){
     if(index==n-1) return 0;
     int&ans=dp[index];
     if(dp[index]!=-1) return ans;

     ans=INT_MAX;
     for(int i=index+1;i<=index+k and i<n;i++){
          ans=min(ans, abs(A[index]-A[i])+f(i));
     }
     return ans;
}

int main(){
     memset(dp, -1, sizeof(dp));
     cin>>n>>k;
     for(int i=0;i<n;i++)cin>>A[i];
     cout<<f(0);
}



Measured memory_bytes: 5760
let () =
  (match (Scanf.scanf "%d %d" (fun a b -> a, b)) with
   | a, b when a = b -> "Draw"
   | 1, _ -> "Alice"
   | _, 1 -> "Bob"
   | a, b when a > b -> "Alice"
   | _ -> "Bob")
  |> print_endline

Measured memory_bytes: 384
import sys

N = int(sys.stdin.readline().rstrip())
P = [int(x) for x in sys.stdin.readline().rstrip().split()]

m = N  # iの前までの最小
cnt = 0
for i in range(N):
    if m >= P[i]:
        cnt += 1
    m = min(m,P[i])

print(cnt)

Measured memory_bytes: 32168
#include <stdio.h>
int main(void) {
	int c, ascii[127] = {0};

	while (1) {
		c = getchar();
		if (c == EOF)
			break;
		ascii[c] += 1;
	}
	for (c = 'a'; c <= 'z'; c++) {
		printf("%c : %d\n", c, ascii[c] + ascii[c-0x20]);
	}
	return 0;
}


Measured memory_bytes: 2112
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        int count = 0;
        for(int i = 0; i < n; i++ ) {
            for(int j = n - 1; j > 0; j--) {
                if(arr[j] < arr[j-1]) {
                    int v = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = v;
                    count++;
                }
            }
        }

        System.out.print(arr[0]);
        for(int i = 1; i < n; i++) {
            System.out.print(" " + arr[i]);
        }

        System.out.println();
        System.out.println(count);

    }
}

Measured memory_bytes: 26228
ans = list(map(int,input().split()))
ans.sort()
count = 0
if ans[0] == ans[1] and ans[1] == ans[2]:
    pass
else:
    count += ans[2] - ans[1]
    ans[0] += count
    if ans[0] == ans[1]:
        pass
    else:
        a = ans[2] - ans[0]
        if a%2 == 0:
            count += a//2
        else:
            count += (a+1)//2 +1
print(count)

Measured memory_bytes: 3064
#include<iostream>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<limits>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef int itn;

const int inf = numeric_limits<int>::max()/4 ;
const ll linf = numeric_limits<ll>::max()/4 ;
const ull ulinf = numeric_limits<ull>::max()/4;
const double pi = acos(-1);
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
const int dx8[8]={-1,0,1,-1,1,-1,0,1};
const int dy8[8]={-1,-1,-1,0,0,1,1,1};

#define p_queue(i) priority_queue<i> 
#define rp_queue(i) priority_queue<i, vector<i>, greater<i>> 
#define P(p) cout<<(p)<<endl
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define mod(i) ((i)%(ll)(1e9 + 7))
#define divm(a,b) (mod(a * modpow((ll)b,(ll)(1e9+5))))
#define rsort(a,b,c) sort(a, b, greater<c>())
#define vsort(v) sort(v.begin(), v.end());
#define rvsort(v) sort(v.end(), v.begin());
#define ft first
#define sd second
#define pb push_back
#define it insert
#define sz(x) ((int)(x).size())
#define lb(a,n,k) (lower_bound(a,a+n,k) - a) 
#define vlb(a,k)  (lower_bound(a.begin(),a.end(),k) - a.begin())
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define ret return

ll modpow(ll i,ll j){ ll tmp=1; while(j){ if(j%2)tmp=mod(tmp*i);i=mod(i*i);j/=2;}return tmp;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

//ll ncr[100][100];
//ll nCr(int n, int r){if(n==r) ret ncr[n][r] = 1; if(r==0) ret ncr[n][r] = 1; if(r==1) ret ncr[n][r] = n;if(ncr[n][r]) ret ncr[n][r]; ret ncr[n][r] = nCr(n-1,r) + nCr(n-1,r-1);}

//ll npr[100][100]={};
//ll nPr(int n,int r){if(npr[n][r])ret npr[n][r];if(r==0)ret npr[n][r] = 1;if(r==1)ret npr[n][r] = n;ret npr[n][r] = n * nPr(n-1,r-1);}

//ll nHr(int n,int r){ret nCr(n+r-1,r);}

///////////////////////////////////////////////////////////////////////////
string s,t;

int che(int sn){
    rep(i,0,sz(t)){
        if(t[i] == s[i+sn] || s[i+sn] == '?'){
            
        }else{
            ret 0;
        }
    }
    ret 1;
}

int main(){

	cin >> s >> t;
    string tt = "";
    int f = 0;
    for(int i = sz(s)-sz(t); i >= 0; i--){
        if(che(i) == 1){
          //  P(i);
            s.erase(i);
            s += t;
            f = 1;
            break;
        }else{
            tt = s[i+sz(t)-1] + tt;
        }
    }
    if(f == 0){
        P("UNRESTORABLE");
        ret 0;
    }
    s += tt;
  //  P(s);

    rep(i,0,sz(s)){
        if(s[i] == '?')cout << 'a';
        else cout << s[i];
    }
    cout << endl;
    
	return  0;
}

Measured memory_bytes: 256
package main

import(
    "fmt"
)



func main() {
    var a,b,c int64
    fmt.Scan(&a,&b,&c)
    d:=a*c-b
    for i := 0; i < 10; i++{
        fmt.Println(d)
        d = a*d-b
    }
}





func abs32(a int) int {
    if a<0{
        return -a
    }
    return a
}

func abs64(a int64) int64 {
    if a<0{
        return -a
    }
    return a
}

func min32(a, b int) int {
    if a >= b {
        return b
    }
    return a
}

func max32(a, b int) int {
    if a >= b {
        return a
    }
    return b
}

func min64(a, b int64) int64 {
    if a >= b {
        return b
    }
    return a
}

func max64(a, b int64) int64 {
    if a >= b {
        return a
    }
    return b
}

func gcd(a, b int64) int64 {
    if a % b == 0 {
        return b
    } else {
        return gcd(b, a%b)
    }
}

func lcm(a, b int64) int64 {
    return a / gcd(a, b) * b
}


Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <queue>

#define rep(i, n) for(int i = 0; i < (int)(n); i++)

using namespace std;

int main(){
    int n; cin >> n;
    string s; cin >> s;
    vector<int> leftwest(n,0);
    vector<int> righteast(n,0);
    long long max = n;
    rep(i, n) {
        if(i == 0)
            continue;
        if(s[i-1] == 'W')
            leftwest[i] = leftwest[i-1] + 1;
        else
            leftwest[i] = leftwest[i-1];
    }
    for(int i = n-2; i >=0; i--){
        if(s[i+1] == 'E')
            righteast[i] = righteast[i+1] + 1;
        else
            righteast[i] = righteast[i+1];
    }
    rep(i, n) {
        if(i == 0){
            if(max > righteast[i])
                max = righteast[i];
        } else if(i == n-1) {
            if(max > leftwest[i])
                max = leftwest[i];
        } else {
            if(max> righteast[i] + leftwest[i])
                max = righteast[i]  + leftwest[i];
        }
    }
    cout << max << endl;

}



Measured memory_bytes: 3076
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <utility>
#include <set>
#include <stack>
#include <climits>
#include <cmath>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define rep1(i,n) for(int i=1, i##_len=(n); i<=i##_len; ++i)
#define reps(i,s,n) for(int i=s, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define MEMSET(v, h) memset((v), h, sizeof(v))
//#include <boost/multiprecision/cpp_dec_float.hpp>
//#include <boost/multiprecision/cpp_int.hpp>
typedef long long ll;
const char sp = ' ';


using namespace std;

int main(void){
    ll N, p;
    ll dp10[300000], dpS[300000];
    ll kosu[10001];
    MEMSET(kosu, 0);
    string S;
    cin>>N>>p;
    cin>>S;
    dp10[0]=1; dpS[0]=(S[N-1]-'0')%p;
    if(p==2){
        ll count=0;
        rep(i, N){
            ll th=S[N-1-i]-'0';
            if(th%2==0) count+=(N-i);
        }
        cout<<count<<endl;
        return 0;
    }
    if(p==5){
        ll count=0;
        rep(i, N){
            ll th=S[N-1-i]-'0';
            if(th%5==0) count+=(N-i);
        }
        cout<<count<<endl;
        return 0;
    }
    //cout<<dpS[0]<<endl;
    rep(i, N){
        ll th=S[N-i-1]-'0';
        //cout<<th<<endl;
        if(i==0) continue;
        dp10[i]=(dp10[i-1]*10)%p;
        dpS[i]=(dpS[i-1]+th*dp10[i])%p;
        //cout<<dpS[i]<<sp<<dp10[i]<<endl;
    }
    rep(i, N){
        kosu[dpS[i]]++;
    }
    //cpp_int count=0;
    ll count=0;
    rep(i, p){
        count+=(kosu[i]*(kosu[i]-1))/2;
        //cout<<i<<":"<<sp<<kosu[i]<<endl;
    }
    count+=kosu[0];
    cout<<count<<endl;
    return 0;
}


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

#define debug(x) cerr << #x << " = " << x << endl;
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define FOR(it, b, e) for (typeof(b) it = (b); it != (e); ++it)
#define MSET(c, v) memset(c, v, sizeof(c))

const int INF = 0x3F3F3F3F; 
const int NEGINF = 0xC0C0C0C0;
const int NULO = -1;
const ll mod = 1e9 + 7;
const double EPS = 1e-10;

inline int cmp(double x, double y = 0) 
{  
  if(fabs(x - y) < EPS)
    return 0;
  return x > y ? 1 : -1;
}

ll exp(ll a, ll b)
{
  ll ans = 1;
  while(b)
  {
    if(b & 1)
      ans = (ans * a) % mod;
    a = (a * a) % mod;
    b >>= 1;
  }
  return ans;
}

const int maxn = 2e5 + 10;
ll fat[maxn], inv[maxn];

ll C(int n, int k)
{
  if(n < k) 
    return 0;
  if(n < 0 || k < 0) 
    return 0;
  return (((fat[n] * inv[k]) % mod) * inv[n - k]) % mod;
}

void initFactorials()
{
  fat[0] = 1;
  inv[0] = 1;
  for(int i = 1; i < maxn; i++)
  {
    fat[i] = (i * fat[i-1]) % mod;
    inv[i] = exp(fat[i], mod - 2);
  }
}

int a[maxn];

int main()
{
  ios::sync_with_stdio(0);
  int n,m;
  cin >> n >> m;
  priority_queue<int>pq;
  for(int i = 0; i < n; i++)
  {
    cin >> a[i];
    pq.push(a[i]);
  }

  while(m--)
  {
    int b = pq.top();
    pq.pop();
    pq.push(b/2);
  }

  ll ans = 0;
  while(pq.size())
  {
    ans += pq.top();
    pq.pop();
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 4344
#include <bits/stdc++.h>
#ifdef JLOCAL
#include "stress.h"
#endif
using namespace std;

#define rep(i, z, n) for (int i = (z); i < int(n); ++i)
#define repr(i, n, z) for (int i = int(n) - 1; i >= (z); --i)
#define shl(n) (1 << (n))
#define hbit(n, i) (((n) >> (i)) & 1)

#define STRESS 0
using lint = long long;
template <typename T> using vc = std::vector<T>;

void solve(istream& cin, ostream& cout) {
    int n;
    cin >> n;
    cout << n / 3;
}

int main() {
#if !defined(JLOCAL) || !STRESS
#ifdef JLOCAL
    freopen("input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    solve(cin, cout);
#else
    srand();
    for (int ti = 0; ti < 100; ti++) {
        stress::gen();
        stress::stupid();
        ifstream in("input.txt");
        ofstream out("output.txt");
        solve(in, out);
        out.flush();
        stress::check();
    }
    cout << "ok" << endl;
#endif
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<string.h>
#include<complex>
#include<math.h>
#include<queue>
#include<time.h>
using namespace std;
typedef long long int llint;
typedef vector<int> vint;
typedef vector<llint> vllint;
typedef vector<pair<int, int>> vpint;
typedef vector<pair<llint, llint>> vpllint;
#define rep(i,n) for(int i=0;i<n;i++)
#define drep(i,n) for(int i=n-1;0<=i;i--)
#define yes(ans) if(ans)cout<<"yes"<<endl;else cout<<"no"<<endl;
#define Yes(ans) if(ans)cout<<"Yes"<<endl;else cout<<"No"<<endl;
#define YES(ans) if(ans)cout<<"YES"<<endl;else cout<<"NO"<<endl;
#define POSSIBLE(ans) if(ans)cout<<"POSSIBLE"<<endl;else cout<<"IMPOSSIBLE"<<endl;

class UnionFind {
public:
	//親の番号を格納する。親だった場合は-(その集合のサイズ)
	vector<int> Parent;

	//作るときはParentの値を全て-1にする
	//こうすると全てバラバラになる
	UnionFind(int N) {
		Parent = vector<int>(N, -1);
	}

	//Aがどのグループに属しているか調べる
	int root(int A) {
		if (Parent[A] < 0) return A;
		return Parent[A] = root(Parent[A]);
	}

	//自分のいるグループの頂点数を調べる
	int size(int A) {
		return -Parent[root(A)];//親をとってきたい
	}

	//AとBをくっ付ける
	bool connect(int A, int B) {
		//AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
		A = root(A);
		B = root(B);
		if (A == B) {
			//すでにくっついてるからくっ付けない
			return false;
		}

		//大きい方(A)に小さいほう(B)をくっ付けたい
		//大小が逆だったらひっくり返しちゃう。
		if (size(A) < size(B)) swap(A, B);

		//Aのサイズを更新する
		Parent[A] += Parent[B];
		//Bの親をAに変更する
		Parent[B] = A;

		return true;
	}
};

//aとbの最大公約数を求めるよ
long long GCD(long long a, long long b) {
	if (b == 0) return a;
	else return GCD(b, a % b);
}

// 返り値: a と b の最大公約数
// ax + by = gcd(a, b) を満たす (x, y) が格納される
long long extGCD(long long a, long long b, long long& x, long long& y) {
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	long long d = extGCD(b, a % b, y, x);
	y -= a / b * x;
	return d;
}

bool check(pair<int,int>a, pair<int,int>b) {
	if (a.first == b.first) {
		return a.second > b.second;
	}
	else {
		return a.first < b.first;
	}
}

int main() {
	int a, b;
	cin >> a >> b;
	if (a <= b) {
		cout << a << endl;
	}
	else {
		cout << a - 1 << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void){

  int a,b,c,d;

  //input
  scanf("%d %d %d %d",&a,&b,&c,&d);

  if (abs(a-c)<=d){
    printf("Yes\n");
  }else if(abs(a-b)<=d && abs(b-c)<=d){
    printf("Yes\n");
  }else{
    printf("No\n");
  }


  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7;

signed main()
{
	IO_OP;
	
	string s;
	cin >> s;
	int ans = 0;
	for(char c:s) {
		ans += (c-'0');
	}	
	if(ans%9) cout << "No" << endl;
	else cout << "Yes" << endl;
	
}





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

#define REP(i,n) for(int i=0; i < (n); ++i)
#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)

using ll = long long;
#define INF 1e9


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

  if(A <= C && C <= B){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
using System;
using System.Linq;
using System.Collections.Generic;

namespace Algorithm
{
    class Program
    {
        static List<Node> T = new List<Node>();
        static int[] D;
        static void Main(string[] args)
        {
            var n = int.Parse(Console.ReadLine());
            D = new int[n];
            int d = 0, v = 0, c = 0, l = 0, r = 0;

            for (var i = 0; i < n; i++)
            {
                T.Add(new Node());
                T[i].Parent = null;
                T[i].Left = null;
                T[i].Right = null;
            }

            for (var i = 0; i < n; i++)
            {
                var t = Console.ReadLine().Split().Select(int.Parse).ToArray();
                v = t[0];
                d = t[1];
                for (var j = 0; j < d; j++)
                {
                    c = t[2+j];
                    if (j == 0) T[v].Left = c;
                    else T[l].Right = c;
                    l = c;
                    T[c].Parent = v;
                }
            }

            for (var i = 0; i < n; i++)
                if (T[i].Parent == null) r = i;

            Rec(r, 0);

            for (var i = 0; i < n; i++) Print(i);

        }

        static void Rec(int u, int p)
        {
            D[u] = p;
            if (T[u].Right != null) Rec((int)T[u].Right, p);
            if (T[u].Left != null) Rec((int)T[u].Left, p + 1);
        }

        static void Print(int u)
        {
            var i = 0;
            var c = 0;
            Console.Write($"node {u}: parent = {T[u].Parent??-1}, depth = {D[u]}, ");
            if (T[u].Parent == null) Console.Write("root, ");
            else if (T[u].Left == null) Console.Write("leaf, ");
            else Console.Write("internal node, ");

            Console.Write("[");
            for (int? x = 0, y = T[u].Left; y != null; x++, y = T[(int)y].Right)
            {
                if (x > 0) Console.Write(", ");
                Console.Write(y);
            }
            Console.WriteLine("]");
        }
    }

    class Node
    {
        public int? Parent { get; set; }
        public int? Left { get; set; }
        public int? Right { get; set; }
    }
}



Measured memory_bytes: 39708
import math
def cal_dis(a,b):
    out = 0
    for i in range(len(a)):
        out += (a[i]-b[i])**2
    return out


n,d = map(int,input().split())
points = []
for i in range(n):
    points.append(list(map(int,input().split())))

cnt = 0
for i in range(n):
    for j in range(i+1,n):
        distanse = cal_dis(points[i],points[j])
        if math.sqrt(distanse)%1 ==0:
            cnt += 1

print(cnt)

Measured memory_bytes: 3064
H, W = map(int,input().split())
S = [list(input()) for i in range(H)]

ans_h = []
for h in range(H) :
    flag = False
    for w in range(W) :
        if S[h][w] == "#" :
            flag = True
    if flag == True :
        ans_h.append(h)

ans_w = []
for w in range(W) :
    flag = False
    for h in range(H) :
        if S[h][w] == "#" :
            flag = True
    if flag == True :
        ans_w.append(w)

for h in ans_h :
    for w in ans_w :
        print(S[h][w], end="")
    print("")


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

using namespace std;

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

  vector<int> res(n);
  for (int i = 0; i < n; i++) {
    for (int j = n - 1 - i; j >= 0; j--) {
      if (a[j] == j + 1) {
        res[i] = j + 1;
        a.erase(a.begin() + j);
        break;
      }
    }
    if (a.size() == n - i) {
      cout << "-1\n";
      return 0;
    }
  }
  
  for (int i = n - 1; i >= 0; i--) {
    cout << res[i] << '\n';
  }
  return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define rep(i, n) for(int(i) = 0; (i) < (n); (i)++)
#define FOR(i, m, n) for(int(i) = (m); (i) < (n); (i)++)
#define All(v) (v).begin(), (v).end()
#define pb push_back
#define MP(a, b) make_pair((a), (b))
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int INF = 1 << 30;
const ll LINF = 1LL << 60;
const int MOD = 1e9 + 7;

int main() {
    int A, B, C;
    cin >> A >> B >> C;
    if((A == B && B != C) || (A == C && B != C) || (C == B && B != A)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 3604
#include<iostream><string>
using namespace std;
int main(){

  int A,B;
  cin>>A>>B;
  string S;
  cin>>S;
  for(int i=0;i<=A+B;i++){
  
    if(i==A){
    
      if(S[i]!='-'){
      
        cout<<"No";
        return 0;
      }
    }
    else{
    
      if(S[i]=='0'||S[i]=='1'||S[i]=='2'||S[i]=='3'||S[i]=='4'||S[i]=='5'||S[i]=='6'||S[i]=='7'||S[i]=='8'||S[i]=='9'){
      
      }
      else{
      
        cout<<"No";
        return 0;
      }
    }
  }
  cout<<"Yes";
  return 0;
}

Measured memory_bytes: 3604
K = int(input())
i = 1
y = 1
if K== 1:
  print(1)
elif K%2 == 0 or K%5 == 0:
  print(-1)
#elif K%3 == 0:
#  print(3)
elif K== 7:
  print(1)
else:
  if K%7 == 0:
    K = K//7
  while True:
    i += 1
    y = ((y*10)%K) + 1
    y = y%K
    if y == 0:
      break
  print(i)

Measured memory_bytes: 9116
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <math.h>
using namespace std;
 
const int MAX_N=10000;
unsigned long long int a,b;

unsigned long long gcd(unsigned long long a,unsigned long long b){
	if(b) return gcd(b,a%b);
	else return a;
}

unsigned long long lcm(unsigned long long a,unsigned long long b){
	return (a/gcd(a,b))*b;
}

int main(){
	while(cin >> a >> b){
		cout << gcd(a,b) << " " << lcm(a,b) << endl;
	}
	return 0;
}

Measured memory_bytes: 3088
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
n,q = map(int,input().split())
tree = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)

ans = [0 for _ in range(n)]
for _ in range(q):
    p,x = map(int,input().split())
    p -= 1
    ans[p] += x

#入力

def dfs(pre,now,w):
    ans[now] += w
    for i in tree[now]:
        if i != pre:
            dfs(now,i,ans[now])

dfs(-1,0,0)

print(*ans)

Measured memory_bytes: 230920
#![allow(dead_code,unused_variables,unused_imports)]
use proconio::{fastout, input};
use proconio::marker::Chars;
use std::cmp::{max,min};
use std::collections::{HashSet,HashMap};

#[fastout]
fn main() {
    input!{
        n:usize,
        a:[usize;n],
    }
    let mut m : HashMap<usize,usize> = HashMap::new();
    for i in 0..n{
        let tmp = m.entry(a[i]).or_insert(0);
        *tmp += 1;
    }

    let c : HashSet<_> = a.iter().collect();

    let mut table = vec![true;1_000_010];
    for e in &c{
        for j in 2..=(1_000_000/ *e){
            let tmp = *e * j;
            table[tmp] = false;
        }
    }

    let mut cnt = 0;
    for i in 0..n{
        if table[a[i]] && m[&a[i]] == 1{
            cnt += 1;
        }
    }
    
    println!("{}",cnt);
}

fn lower_bound(x: &Vec<usize>, key:usize) -> usize{
    let mut l = 0;
    let mut r = x.len();

    while l+1 < r{
        let mid = (r-l)/2 + l;

        if key < x[mid]{
            r = mid;
        }else{
            l = mid;
        }
    }
    l
}

Measured memory_bytes: 12344
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define yesno(flg) if(flg){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define MAX_N 1002
#define i197 1000000007

using namespace std;
typedef long long ll;
typedef pair<ll,ll> P1;
typedef pair<int,int> Pi;
typedef pair<double,Pi> Pdi;
typedef pair<ll,int>Pli;
typedef pair<P1,ll> P2;
typedef pair<string,string> Ps;
const ll INF=1000000000000000001;
struct edge{int to,cost;};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
struct Road{double cost;int a,b;};
struct pos{
	// 1 変数を入れる;
	int x,y,sx,sy,cost;
};
ll d[100001]={};

int main() {

	int n,q;
	cin>>n;

	ll t=0;
	rep(i,n){
		int a;
		cin>>a;
		d[a]++;
		t+=a;
	}
	cin>>q;

	rep(i,q){
		int b,c;
		cin>>b>>c;
		d[c]+=d[b];
		t+=d[b]*(c-b);
		d[b]=0;
		cout<<t<<endl;
	}

	return 0;
}


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

int main() {
	int n,t ;
	cin >> n >> t;
	int res = 100000;
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		if (t >= b)res = min(res, a);
	}
	if (res == 100000)cout << "TLE" << endl;
	else cout << res << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
typedef long long ll;
using namespace std;
const ll mod=1000000007;
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    ll n;
    cin>>n;
    ll a[n+1];
    a[0]=0;
    for(int i=1;i<=n;i++){
    	cin>>a[i];
    	a[i]+=a[i-1];
    }
    sort(a,a+n+1);
    ll num=0,ans=0;
    for(int i=1;i<=n;i++){
    	if(a[i]==a[i-1]){
    		num++;
    	}else{
    		num=0;
    	}
    	ans+=num;
    	//if(a[i]==0)ans++;
    }
    cout << ans<<endl;
    return 0;
}


Measured memory_bytes: 1792
//BISMILLAHIR-RAH-MANIR-RAHIM.
//ABU AYUB MD AHMADUL(CEO-PEREGRINE SPHERE).
//FORMER CEO-SPACEH(2019).
//DEPT.OF CSE,SUST//2018-19.
//------------------------------------------\\
//PRE-CODE========>
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
#include<vector>
#include<math.h>
#include<numeric>
#include<stack>
#include<queue>
#include<string>
#include<algorithm>
#include<map>
#define mp make_pair
#define ins insert
#define lli long long int
#define ll long long
#define pb push_back
#define loop1(i,l,n) for(i=l;i<=n;i++)
#define loop0(i,l,n) for(i=l;i<n;i++)
#define inf (1<<28)
#define pi 3.1415926536
const int MAX=1e6+9;
set<int>ist;
map<string,int>msi;
map<string,string>mss;
map<int,string>mis;
map<int,int>mii;
pair<int,int>pii;
vector<int>v;
vector<pair<int,int> >vv;
int cc[]= {1,-1,0,0};
int rr[]= {0,0,1,-1};
//BIPARTITE GRAPH FUCTION========>
/*
int cnt[2];
int vertices[MAX];
void Bipartite(int node,int pnode,int color)
{
    cnt[color]++;
    for (int i=0;i<vertices[node].size();i++)
    {
        if (vertices[node][i]!=pnode)
        {
            Bipartite(vertices[node][i],node,!color);
        }

    }
}
*/
//REAL TIME BINARY SERACH FUNCTION========>
/*
int Bsearch(int left,int right,int query,int n)
{
    int mid=left+(right-left)/2;
    if(query<mid)
    {
        return Bsearch(left,mid-1,query,n);
    }
    else if(query>mid)
    {
        return Bsearch(mid+1,right,query,n-1);
    }
    else
    {
        return n;
    }
}
*/
//DECIMAL TO BINARY DECODING========>
/*
ll D2B(ll dec)
{
    ll digit[32]={};
    ll i = 0;
    while (dec > 0)
    {
        [i] = n % 2;
        n = n / 2;
        i++;
    }

}
*/
//BINARY TO DECIMAL DECODING========>
/*
ll b2d(ll bin)
{
    ll digit,sum=0,h=0;
    while(bin!=0)
    {
        digit=bin%10;
        sum+=digit*pow(2,h++);
        bin/=10;
    }
    return sum;
}
*/
//DFS FUNCTION=========>
/*
int visited[MAX];
vector<int>adj[MAX];
int weight[MAX];
void dfs(int v)
{
    visited[v] = 1;
    for (auto j: adj[v])
    {
        if (!visited[j])
        {
            dfs(j);
        }
    }
}
*/
//------------------------------------------\\
//LAUNCHING SHARK-20========>
void BACKSLASH()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    int t;
    double n,d;
    cin>>n>>d;
    double cnt=0;
    for(int i=0;i<n;i++)
    {
        double x,y;
        cin>>x>>y;
        double ans=ceil(sqrt((x*x)+(y*y)));
        if(ans<=d)
        {
            cnt++;
        }
    }
    cout<<cnt<<endl;

}
//MAIN FUNCTION========>
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    BACKSLASH();

    return 0;
}
//------------------------------------------\\
//ABOUT THE SERIES========>
//THE BUTTERFLY SERIES-(MAY-2020).
//SPONSERED BY QUANTUM SPACE(CEO-NAIMUL ISLAM).
//CONTROLLER=>SAFIA BEGUM(CEO-BACKS/ASH).
//ADVISOR=>NASRULLAH SAMI(CEO-FALCON AXIS).
//CO-CHIEF ADVISOR=>G.M NAYEEM(CEO-TECH FRIGATE).
//PRESIDENT=>SAMIA PREITY(CEO-FASTEX AND SPAIT).



Measured memory_bytes: 3856
#include <stdio.h>
#include <algorithm>
int n;
int d[100000];
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", d + i);
	}
	std::sort(d, d + n);
	printf("%d\n", d[n / 2] - d[(n / 2) - 1]);
}

Measured memory_bytes: 512
#include<stdio.h>

int main(){
  int a[] = {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};
  int k;
  
  scanf("%d", &k);
  printf("%d", a[k-1]);
  
  return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

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

    vector<int> t(n-1);
    for(int i=0; i<n-1; ++i)
        cin >> t[i];

    vector<vector<int> > dp(n/2+1, vector<int>(2, INT_MAX/2));
    dp[0][0] = 0;
    for(int i=0; i<n-1; ++i){
        vector<vector<int> > nextDp(n/2+1, vector<int>(2));
        for(int j=0; j<=n/2; ++j){
            nextDp[j][0] = dp[j][1] + t[i];
            nextDp[j][1] = dp[j][1];
            if(j > 0){
                nextDp[j][0] = min(nextDp[j][0], dp[j-1][0]);
                nextDp[j][1] = min(nextDp[j][1], dp[j-1][0] + t[i]);
            }
        }
        dp.swap(nextDp);
    }

    int ret = min(dp[n/2-1][0], dp[n/2][1]);
    cout << ret << endl;
}

Measured memory_bytes: 1188
#include<stdio.h>
#include<string.h>

int main(void)
{
	char str[1200];
	int i, length;

	fgets(str, 1200, stdin);

	length = strlen(str);
	for(i = 0; i < length; i++)
	{
		if ( str[i] >= 'a' && str[i] <= 'z')
			str[i] -= 32;
		else if ( str[i] >= 'A' && str[i] <= 'Z')
			str[i] += 32;
	}
	printf("%s", str);
	return 0;
}


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

int main() {
    int N;
    cin >> N;
    vector<int> a(N);
    for (int i = 0; i < N; i++)
    {
        cin >> a[i];
    }
    int index = 1, num = 0;
    while(1)
    {
        index = a[index - 1];
        if(index == 2)
        {
            cout << num + 1;
            return 0;
        }
        if(num > 100000)
        {
            cout << -1;
            return 0;
        }
        num++;
    }
}


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

int main()
{
  int p, q;
  while (cin >> p >> q) {
    int loop = -1;
    vector<int> rem;
    rem.push_back(p%q);
    while (p != 0) {
      p *= 10;
      int tmp = p / q;
      p %= q;
      cout << tmp;
      if (find(rem.begin(), rem.end(), p) != rem.end()) {
	loop = find(rem.begin(), rem.end(), p) - rem.begin();
	break;
      }
      rem.push_back(p);
    }
    cout << endl;

    if (loop != -1) {
      for (int i = 0; i < loop; ++i)
	cout << " ";
      for (int i = loop; i < rem.size(); ++i)
	cout << "^";
      cout << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 0
#include "bits/stdc++.h"
using namespace std;
 
////////////// Prewritten code follows. Look down for solution. ////////////////

#define fs first
#define sc second
#define pb push_back
#define len(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()

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

const ll LINF = 1e18;
const int INF = 1e9;
const int MOD = 1e9+7;

/// command for char arrays with spaces -> scanf(" %[^\n]", texto);
 
////////////////////////// Solution starts below. //////////////////////////////

const int N = 1e5+5;

int main(){

	int h, n, a, sum = 0;
	scanf("%d %d", &h, &n);
	for(int i = 1; i <= n; i++){
		scanf("%d", &a);
		sum += a;
	}

	if(sum < h) printf("No\n");
	else printf("Yes\n");
	
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll e[10000000];
int main()
{
    ll n;
    cin>>n;
    for(ll i=1; i<=100; i++)
        for(ll j=1; j<=100; j++)
            for(ll k=1; k<=100; k++)
                e[i*i+j*j+k*k+i*j+i*k+j*k]++;
    for(ll i=1; i<=n; i++)
        cout<<e[i]<<endl;
    return 0;

}


Measured memory_bytes: 4088
import           Control.Applicative
import           Control.Monad
import           Control.Monad.State

deleteFirst :: Eq a => a -> [a] -> [a]
deleteFirst _ [] = []
deleteFirst a (t : ts) | a == t    = ts
                       | otherwise = t : deleteFirst a ts

main = do
  n <- readLn
  s <- take n . map (read :: String -> Int) . words <$> getLine
  q <- readLn
  t <- take q . map (read :: String -> Int) . words <$> getLine
  let res = foldl (\acc o -> deleteFirst o acc) s t
  print $ (length s) - (length res)



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

using ll = long long;
const long long MOD = 1000000007;

// まずはdp[N][K]というので考えてみる
// 例えばA=dp[3][50], B=dp[2][50]を比べると、(残り50個、今の制約が3と2)
// A = dp[1][49] + dp[2][49] + .. dp[N/3][49]
// B = dp[1][49] + dp[2][49] + .. dp[N/3][49] + dp[N/3+1][49] + .. + dp[N/2][49]
// よって
// B = A + dp[N/3+1][49] + .. dp[N/2][49]
// ところで、 dp[N/3+1][49] = dp[N/2][49]である
// なぜなら隣りにおけるのは2までなので
// よって
// B = A + (N/2 - N/3) * dp[N/2][49]である

// また、上のように大きいnが参照できない場合
// dp[N][K] = dp[1][K-1]である

// 実際にdp[N]は状態数が多すぎるので、
// x^2 > Nならばdp[x] = dp[1][N/x]というふうに割り当てる(x^2<=Nならばdp[0][x])
// 以下略

ll N;
ll n;
#define ROOT 35000
ll dp[2][ROOT][101];
void setv(int i, int j, int k, ll v, char mark=' ') {
    dp[i][j][k] = v;
}
ll solve(ll K) {
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < 2; i++) 
        for (int j = 0; j < ROOT; j++)
            dp[i][j][0] = 1;
    for (int k = 1; k <= K; k++) {
        // 大きい数から
        // i = 1
        // -- j == N (1,1)
        setv(1, 1, k, dp[0][1][k-1]);
        // -- j = N-1 .. N/n
        for (ll j = 2; j <= n; j++) {
            ll a = N/(j-1);
            ll b = N/j;
            setv(1, j, k, (dp[1][j-1][k] + ((N/b - N/a) * dp[0][j][k-1]) % MOD) % MOD, '-');
        }
        // i = 0
        for (ll j = n; j >= 1; j--) {
            if ((j + 1) * (j + 1) > N) {
                setv(0, j, k, (dp[1][N/(j+1)][k] + ((N/j - N/(j+1)) * dp[1][j][k-1]) % MOD) % MOD, '*');
            }
            else {
                setv(0, j, k, (dp[0][j+1][k] + ((N/j - N/(j+1)) * dp[1][j][k-1]) % MOD) % MOD, 'x');
            }
        }
    }
    return dp[0][1][K];
}

int main(){
    scanf("%lld",&N);
    n = (ll)sqrt(N);
    long long K;
    scanf("%lld",&K);
    ll res = solve(K);
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 55424
n = int(input())
txy = [[int(i) for i in input().split()] for j in range(n)]

now = [0,0]
time = 0

for i in range(n):
    if abs(now[0]-txy[i][1]) + abs(now[1]-txy[i][2]) <= txy[i][0]:
        if (now[0]+now[1]) % 2 == (txy[i][1]+txy[i][2]+txy[i][0]-time) % 2:
            now[0] = txy[i][1]
            now[1] = txy[i][2]
            time = txy[i][0]
            #print(txy[i],time,now)
        else:
            print("No")
            exit()
    else:
        print("No")
        exit()
        
print("Yes")

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

using namespace std;

#define lli long long int
#define REP(i,s,n) for(int i=s;i<n;i++)
#define MOD 1000000007
#define NUM 2520
#define INF (1LL<<50)
#define DEBUG 0
#define mp(a,b) make_pair(a,b)
#define SORT(V) sort(V.begin(),V.end())
#define PI (3.141592653589794)

signed main(){

	lli n,m;
	cin>>n>>m;

	map<lli,vector<lli>> d;
	priority_queue<lli> task;

	REP(i,0,n){
		lli a,b;
		cin>>a>>b;
		d[m-a].push_back(b);
	}

	lli ans = 0;
	for(lli now = m;now>=0;now--){
		for(auto e:d[now])task.push(e);

		if(task.size()==0)continue;
		if(now>m)continue;
		ans += task.top();
		task.pop();
	}
	cout<<ans<<endl;

	return 0;

}

Measured memory_bytes: 10880
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>
#include <queue>
#include <string>
#include <cstring>
#include <numeric>
#include <cstdlib>
#include <cmath>
using namespace std;

typedef long long ll;

#define INF 10e10
#define rep(i,n) for(int i=0; i<n; i++)
#define rep_r(i,n,m) for(int i=m; i<n; i++)
#define END cout << endl
#define MOD 1000000007
#define pb push_back
// 昇順sort
#define sorti(x) sort(x.begin(), x.end())
// 降順sort
#define sortd(x) sort(x.begin(), x.end(), std::greater<int>())

int main() {
  int n;
  cin >> n;
  vector<ll> a(n,0);

  rep(i,n) {
    ll tmp; cin >> tmp;
    a[i] = tmp;
  }

  ll res = 0;
  for (int i = 0; i < n; ++i) {
    if (i == 0) {
      if (a[i] >= 2) {
        res += a[i] / 2;
        a[i] = a[i] % 2;
      }
    } else {
      if (a[i-1] > 0) {
        if (a[i] >= a[i-1]) {
          res += a[i-1];
          a[i] -= a[i-1];
          a[i-1] = 0;
          if (a[i] >= 2) {
            res += a[i] / 2;
            a[i] %= 2;
          }
        } else {
          res += a[i];
          a[i-1] -= a[i];
          a[i] = 0;
        }
      } else {
        if (a[i] >= 2) {
          res += a[i] / 2;
          a[i] %= 2;
        }
      }
    }
  }

  cout << res << endl;
}


Measured memory_bytes: 1024
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] sa = br.readLine().split(" ");
		int n = Integer.parseInt(sa[0]);
		int m = Integer.parseInt(sa[1]);
		Hen[] arr = new Hen[m];
		for (int i = 0; i < m; i++) {
			sa = br.readLine().split(" ");
			Hen h = new Hen();
			h.l = Integer.parseInt(sa[0]) - 1;
			h.r = Integer.parseInt(sa[1]) - 1;
			h.c = Integer.parseInt(sa[2]);
			arr[i] = h;
		}
		br.close();

		Arrays.parallelSort(arr);

		long[] d = new long[n];
		Arrays.fill(d, Long.MAX_VALUE);
		d[0] = 0;
		for (int i = 0; i < m; i++) {
			Hen h = arr[i];
			if (d[h.l] == Long.MAX_VALUE) {
				System.out.println(-1);
				return;
			}
			long alt = d[h.l] + h.c;
			for (int j = h.r; j > h.l; j--) {
				if (d[j] <= alt) {
					break;
				}
				d[j] = alt;
			}
		}
		if (d[n - 1] == Long.MAX_VALUE) {
			System.out.println(-1);
		} else {
			System.out.println(d[n - 1]);
		}
	}

	static class Hen implements Comparable<Hen> {
		int l, r, c;

		@Override
		public int compareTo(Hen o) {
			if (l != o.l) {
				return l - o.l;
			}
			if (c != o.c) {
				return c - o.c;
			}
			return r - o.r;
		}
	}
}


Measured memory_bytes: 47760
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,x,l=1,ans=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x;
		if(x==l){
			l++;
		}else ans++;
	}
	if(ans==n){
		cout<<-1;
	}
	else cout<<ans;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <string>
#include <vector>
#include <math.h>
#include <queue>
#include <map>
const int MOD = 1e9+7;
typedef long long ll;
using namespace std;

int main(){
	int n;
	cin >> n;
	vector<int> d(n);
	for (int i = 0; i < n; i++){
		cin >> d[i];
	}
	sort(d.begin(), d.end());

	cout << d[n/2] - d[n/2-1] << endl;
	return 0;
}

Measured memory_bytes: 640
#include <stdio.h>
#include <string.h>

typedef long long int lint;

int main(void)
{
    int n, i, j;
    int ids[4000];
    lint staff[4001];
    int id, value, no;
    int ok;

    while (scanf("%d", &n),n){
        memset(staff, 0, sizeof(staff));
        memset(ids, 0, sizeof(ids));
        for (i = 0; i < n; i++){
            scanf("%d %d %d", &id, &value, &no);
            staff[id] += (lint)value * no;
            for (j = 0; j < 4000; j++){
                if (ids[j] == 0){
                    ids[j] = id;
                    break;
                }
                else if (ids[j] == id) break;
            }
        }
        ok = 0;
        for (j = 0; ids[j] != 0; j++){
            if (staff[ids[j]] >= 1000000){
                ok = 1;
                printf("%d\n", ids[j]);
            }
        }
        if (ok == 0){
            puts("NA");
        }
    }

    return (0);
}

Measured memory_bytes: 668
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn=100005;
const int logn=20;

int n,q,l,sec,st[maxn],ed[maxn];
int up[maxn][logn];
vector<int>G[maxn];

void dfs(int u,int p) {
	st[u]=sec++;
	up[u][0]=p;
	for (int i=1;i<=l;i++)
		up[u][i]=up[up[u][i-1]][i-1];
	for (int v:G[u])
		if (v!=p) dfs(v,u);
	ed[u]=sec;
}

bool upper(int u,int v) {
	return st[u]<st[v] && ed[u]>=ed[v];
}

int lca(int u,int v) {
	if (u==v) return u;
	if (upper(u,v)) return u;
	if (upper(v,u)) return v;
	for (int i=l;i>=0;i--) 
		if (!upper(up[u][i],v))
			u=up[u][i];
	return up[u][0];
}

int main() {
	cin>>n;
	for (int i=0;i<n;i++) {
		int m; cin>>m;
		for (int j=0;j<m;j++) {
			int v; cin>>v;
			G[i].pb(v);
		}
	}
	while ((1<<l)<=n) l++;
	dfs(0,0);
	cin>>q;
	for (int i=0;i<q;i++) {
		int u,v; cin>>u>>v;
		cout<<lca(u,v)<<'\n';
	}
}


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

int main(){
    string str;
    int res=0;
    cin >> str;
    for(auto& ch : str){
        res+=ch-'0';
        res%=9;
    }
    cout << (res ? "No" : "Yes");
        
    return 0;
}

Measured memory_bytes: 3720
#include<stdio.h>
int main()
{
    int n,i;
    scanf("%d",&n);
    double a[n],sum=0,j;
    for(i=1; i<=n; i++)
    {
        scanf("%lf",&a[i]);
        sum=sum+(1/a[i]);
    }
    j=1/sum;
    printf("%lf\n",j);

}


Measured memory_bytes: 128
N, M = map(int,input().split())
a = [int(input()) for _ in range(M)]

dev = 1000000007
dp = [0 for _ in range(N+1)]
dp[0] = 1
dp[1] = 1

fall = [1 for _ in range(N+1)]

for i in range(M):
    fall[a[i]] = 0

for i in range(1,N):
    dp[i+1] = dp[i]*fall[i] + dp[i-1]*fall[i-1]
    dp[i+1] %= dev

print(dp[N])

Measured memory_bytes: 9592
#include<bits/stdc++.h>
using namespace std;
int main(){
    string a;
    cin>>a;
    int cnt=0;
    for(int i=0;i<a.size();i++){
        if(a[i]=='C'){
            cnt=1;
        }
        if(a[i]=='F'&&cnt){
            cout<<"Yes";
            return 0;
        }
    }
    cout<<"No";
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <limits>
#include <random>
#include <complex>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <tuple>
using namespace std;
typedef long long ll;
#define REP(i,n) for (int i = 0; i < n; i++)
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;

int main ()
{
    ll N;
    cin >> N;
    vector < ll > A(N);
    REP(i,N) cin >> A[i];

    set<int> div;
    for (int j = 0; j < 2; j++) {
        for (int i = 1; i * i <= A[j]; i++) {
            if (A[j] % i == 0) {
                div.insert(A[j] / i);
                div.insert(i);
            }
        }
    }

    int ans = 0;
    for (auto x: div) {
        int cnt = 0;
        for (int i = 0; i < A.size(); i++) {
            if (A[i] % x == 0) {
                cnt++;
            }
        }
        if (cnt >= N - 1) {
            ans = max(ans, x);
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <map>
#include <utility>

using namespace std;

int main(void) {
    int n;
    cin >> n;
    map<int,int> mp;
    for (int i=0; i<n; i++) {
        int a; cin >> a;
        mp[a-1]++;
        mp[a]++;
        mp[a+1]++;
    }

    int ans = 0;
    for (auto p : mp) {
        ans = max(ans, p.second);
    }

    cout << ans << endl;
}


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

int N, I[200000];
int R;

int main() {
  cin >> N;
  for(int i = 0; i < N; ++i) {
    int p; cin >> p; --p; I[p] = i;
  }
  int prev = 1000000, count = 1;
  for(int p = 0; p < N; ++p) {
    if(prev < I[p]) ++count;
    else count = 1;
    prev = I[p]; R = max(R, count);
  }
  cout << N - R << endl;
  return 0;
}


Measured memory_bytes: 1024
//Author: A_S_M_M@sud_P@rvez
#include<bits/stdc++.h>
using namespace std;
#define    MP ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define    For(i,n) for(int i=0;i<n;i++)
#define    forn(i,n) for(int i=1;i<=n;i++)
#define    fors(i,s) for(int i=0;i<s.size();i++)
#define    all(v) v.begin(),v.end()
#define    gcd(a, b) __gcd(a , b)
#define    lcm(a,b) (a*(b/__gcd(a,b)))
#define    test   int t;cin>>t;for(int l=0;l<t;l++)
#define    min3(a,b,c)     min(a,min(b,c))
#define    max3(a,b,c)     max(a,max(b,c))
#define    min4(a,b,c,d)   min(min(a,b),min(c,d))
#define    max4(a,b,c,d)   max(max(a,b),max(c,d))
#define    nl     "\n"
#define    End    return 0 
#define    gt     greater<int>()
#define    ll     long long 
#define    mp     make_pair
#define    pb     push_back
#define    vi     vector<int>
#define    vl     vector<ll>
#define    mod    1000000007
#define    sp(n)  fixed<<setprecision(n)
#define    pi     acos(-1)

int main()
{
MP;
    //test
    {
        int a,b,c,n,f=0;
        cin>>a>>b>>c>>n;
        For(i,n)
        {
            while(a>=b)b*=2,f++;
            while(b>=c)c*=2,f++;
        }
        if(f>n)cout<<"No";
        else cout<<"Yes";
    }

End;
}


Measured memory_bytes: 3624
// AOJ 1276

#include <iostream>

using namespace std;

bool prime[2000000];
void makeprime()
{
	fill(prime, prime + 2000000, true);
	prime[0] = prime[1] = false;
	for (int i = 4; i < 2000000; i+=2) prime[i] = false;
	for (int i = 3; i*i <= 2000000; i += 2){
		if (prime[i]){
			for (int j = i*2; j < 2000000; j += i){
				prime[j] = false;
			}
		}
	}

	return;
}

int main(void)
{
	makeprime();

	int k;
	while (cin >> k, k){
		int a = 0, b = 0;
		for (int i = k; i < 2000000; i++){
			if (prime[i]){
				a = i;
				break;
			}
		}
		for (int i = k; 0 <= i; i--){
			if (prime[i]){
				b = i;
				break;
			}
		}
		cout << a - b << endl;

	}

	return 0;
}

Measured memory_bytes: 3112
def main():
    S = input()
    lens = len(S)

    patterns = []
    ans = 0

    if lens == 1:
        ans = int(S)
    else:
        for i in range(2 ** (lens-1)):
            x = format(i, 'b').zfill(lens-1)
            stmt = S[0]
            for i, xi in enumerate(x):
                if xi == '1':
                    stmt += '+'
                stmt += S[i+1]
            ans += eval(stmt)
    print(ans)

if __name__ == "__main__":
    main()

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

int main()
{
   int n,m,i,j,k;string s;
   cin>>s;n=s.size();
   bool f=true;
   if(s[0]!='A') f=false;
   int c=0;
   for(i=1;i<n;i++)
   {
       if(int(s[i])<96 && s[i]!='C') {f=false;break;}

       if(s[i]=='C' && (i==1 || i==n-1)) {f=false;break;}

       if(i>=2 && i<=n-2)
       {
           if(s[i]=='C') c++;
       }
   }
   if(c!=1) f=false;
   if(f) cout<<"AC";
   else cout<<"WA";
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,i,s=1,flak=1,y;
    cin>>n;
    if(n==2 || n==3)
    {
        cout<<n<<endl;
        s=0;
    }
    else
    {
    while(s!=0)
    {
       y=n;
        for(i=2;i<n;i++)
        {
            if(n%i==0)
            {
                flak=0;
               break;
            }
        }
    if(flak!=0)
    {
        s=0;
        cout<<y<<endl;
        break;
    }
    else
    {
        n++;
        flak=1;
    }
    }
    }

    return 0;
}


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

int main(void){
    string s,t; cin >> s >> t;
    vector<string> ans;
    int l = s.size() - t.size() + 1;
    for(int i = 0; i < max(l,0); i++){
        string tmp = s;
        for(int j = 0; j < t.size(); j++){
            if(i + j > s.size() - 1)break;
            if(tmp[i+j] == t[j] || tmp[i+j] == '?')tmp[i+j] = t[j];
            else break;
            if(j == t.size() - 1){
                for(int k = 0; k < tmp.size(); k++){
                    if(tmp[k] == '?')tmp[k] = 'a';
                }
                ans.push_back(tmp);
            }
        }
    }
    sort(ans.begin(),ans.end());
    if(ans.size()!=0)cout << ans[0] << endl;
    else cout << "UNRESTORABLE" << endl;
    
    
    
}


Measured memory_bytes: 3604
#include <stdio.h>
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int cmp(string a, string b)
{
    return a < b;
}

int main(void)
{
    string str[105];
    int n;

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

    for (int i = 0; i < n - 1; i++)
    {
        if (str[i][str[i].length() - 1] != str[i + 1][0])
        {
            printf("No\n");
            return 0;
        }
    }
    sort(str, str + n, cmp);
    for (int i = 0; i < n - 1; i++)
    {
        if (str[i] == str[i + 1])
        {
            printf("No\n");
            return 0;
        }
    }
    printf("Yes\n");
    return 0;

}

Measured memory_bytes: 256
def getinputdata():

    array_result = []    
    array_result.append(input().split(" "))

    flg = True

    try:
        while flg:

            data = input()

            if(data != ""):
                
                array_result.append(data.split(" "))

                flg = True

            else:

                flg = False
    finally:

        return array_result

arr_data = getinputdata()

a = int(arr_data[0][0])
b = int(arr_data[0][1])

print("Yay!" if a<=8 and b<=8 else ":(")

Measured memory_bytes: 3060