akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define rep(i,n) FOR(i,0,n)
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define vint vector<int>
#define vdouble vector<double>
#define vstring vector<string>
using namespace std;

#include<map>
#include<set>
#include<queue>

typedef long long ll;
typedef unsigned long long ull;

const int MAX_N = 1000000;
const int INFTY = (1 << 21); // 2097152
// const ll INFTY = (1LL << 60);
const ll MD = 1000000007LL;
// fprintf(stderr, "%d %lld \n", x, xll);

class Data{

public:
	ll dist;
	int from, to;
	Data(ll dist, int from, int to) {
		this->dist = dist;
		this->from = from;
		this->to = to;
	}

	bool operator < (const Data &d) const{
		return dist < d.dist;
	}
	bool operator >(const Data &d) const{
		return dist > d.dist;
	}
};

int N;
ll D[300][300];

int main() {
	cin >> N;
	priority_queue<Data, vector<Data>, greater<Data>> pq;

	rep(i, N)
		rep(j, N){
			ll d; cin >> d;
			if(i < j) {
				pq.push(Data(d, i, j));
				D[i][j] = d;
				D[j][i] = d;
			}
		}

	ll ret = 0;
	while(!pq.empty()){
		Data d = pq.top(); pq.pop();
		int flg = 1;
		rep(i, N) if(i != d.from && i != d.to) {
			if(D[d.from][i] + D[i][d.to] == d.dist) flg = min(flg, 0);
			if(D[d.from][i] + D[i][d.to] < d.dist) flg = min(flg, -1);
		}
		if(flg == 1) ret += d.dist;
		if(flg == -1) {
			cout << -1 << endl;
			return 0;
		}
	}

	cout << ret << endl;
}

Measured memory_bytes: 2040
import math
N=int(input())
a=int(math.log(N,26))

def saiki(nokori):
    if(nokori<26):

        return aru_list[nokori]
    else:
        return saiki(nokori//26)+aru_list[nokori%26]

koremade=0
nokori=N
count=0

while(1):
    if(nokori-26**(count+1)==0):

        break
    elif(nokori-26**(count+1)<0):
        break
    else:
        nokori=nokori-26**(count+1)

    count=count+1
count=count+1


nokori=nokori-1

aru_list=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
b=''
ans=saiki(nokori)


while(1):
    if(len(ans)==count):
        print(ans)
        exit()
    else:
        ans='a'+ans


Measured memory_bytes: 62584
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <chrono>
#include <climits>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

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

template <class T1, class T2>
istream& operator >> (istream& in, pair<T1, T2> &p)
{
	in >> p.first >> p.second;
	return in;
}

template <class T>
istream& operator >> (istream& in, vector<T> &v)
{
	for (T &x : v)
		in >> x;
	return in;
}

template <class T>
ostream& operator << (ostream& out, const vector<vector<T>> &v)
{
	for (const vector<T> &x : v)
		out << x << '\n';
	return out;
}

template <class T>
ostream& operator << (ostream& out, const vector<T> &v)
{
	for (const T &x : v)
		out << x << ' ';
	return out;
}

long long gcd (long long a, long long b)
{
	if (b > a)
		swap(a, b);
	return (b ? gcd(b, a % b) : a);
}

using ll   = long long;
using pii  = pair<int, int>;
using pll  = pair<long long, long long>;
using tiii = pair<pair<int, int>, int>;
using vi   = vector<int>;
using vl   = vector<long long>;
using vvi  = vector<vector<int>>;
using vvl  = vector<vector<long long>>;

#define F          first
#define S          second
#define First      first.first
#define Second     first.second
#define Third      second
#define mp         make_pair
#define rep(i,a,b) for (int i = (a); i < (b); i++)
#define per(i,b,a) for (int i = (b); i > (a); i--)
#define all(x)     x.begin(), x.end()
#define ret(x)     return cout << x, 0;
#define throwex    throw runtime_error ("Found the error.");

const int h = 1000000007;

signed main()
{
	ios::sync_with_stdio(false);
	#ifdef ONLINE_JUDGE
	cin.tie(nullptr);
	cout.tie(nullptr);
	cerr.setstate(ios::failbit);
	#endif

	ll h1, m1, h2, m2, k;
	cin >> h1 >> m1 >> h2 >> m2 >> k;
	h2 -= k / 60;
	m2 -= k % 60;
	if(m2 < 0)
		m2 += 60, h2 -= 1;
	if(h1 > h2 or (h1 == h2 and m1 > m2))
		ret(0);
	cerr << h2 << ' ' << m2 << '\n';
	cout << max(0LL, (h2 - h1) * 60 + m2 - m1) << '\n';
}


Measured memory_bytes: 3648
#include <algorithm>
#include <iostream>
#include <set>

using namespace std;

bool table[50001];
set<int> primes;

int main() {
  table[2] = true;
  for (int i = 3; i <= 50000; i += 2)
    table[i] = true;
  for (int i = 3; i <= 223; i += 2)
    if (table[i])
      for (int j = 3 * i; j <= 50000; j += 2 * i)
        table[j] = false;
  primes.insert(2);
  for (int i = 3; i <= 50000; i += 2)
    if (table[i])
      primes.insert(i);
  for (;;) {
    int n;
    cin >> n;
    if (!n) return 0;
    int r = 0;
    for (set<int>::iterator p = primes.begin(); p != primes.end(); ++p)
      if (2 * *p > n)
        break;
      else if (primes.count(n-*p))
        r++;
    cout << r << endl;
  }
  return 0;
}

Measured memory_bytes: 1076
/***"In the name of Allah(swt), the most gracious, most merciful. Allah(swt) blesses with knowledge whom he wants."***/
/*** "ALHAMDULILLAH for Everything..." ***/
#include<bits/stdc++.h>
using namespace std;
#define  fastt       ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define  ll         long long
#define  debug      printf("Come here!")
#define  inf        1000000000000000000
#define  pb         push_back
#define  mp         make_pair
#define  sz(a)      a.size()
#define  mem(a,b)   memset(a,b,sizeof(a))
#define  clr(x)     x.clear()
#define  ff         first
#define  ss         second
#define  case(x)    cout << "Case " << x <<": "

#define  md         1000000007
#define  pi         acos(-1.0)
#define  cos(a)     cos(a*pi/180)
#define  sin(a)     sin(a*pi/180)
#define  tan(a)     tan(a*pi/180)
#define  cosi(a)    acos(a)/(pi/180)
#define  sini(a)    asin(a)/(pi/180)
#define  tani(a)    atan(a)/(pi/180)

#define  vl         vector <ll>
#define  vs         vector <string>
#define  vc         vector <char>
#define  vpll       vector < pair <ll, ll> >
#define  vpsl       vector < pair <string, ll> >
#define  vpls       vector < pair <ll, string> >
#define  pql        priority_queue<ll>
#define  minpql     priority_queue<ll,vector<ll>,greater<ll> >

#define  setbits(x)     __builtin_popcountll(x)
#define  zerobits(x)    __builtin_ctzll(x)

#define toll(a) atoll(a.c_str())
string tostr(ll a) {stringstream rr;rr<<a;return rr.str();}
ll pow(ll c,ll d){return d==0?:c*pow(c,d-1);}
ll gcd(ll a,ll b) {return b==0? a:gcd(b,a%b);}
ll lcm(ll a,ll b) {return ((a*b)/gcd(a,b));}

/* mpp.max_load_factor(0.25); mpp.reserve(1024); */
/* cout << fixed << setprecision(12);*/

int main()
{


        ll k, i, j, x, yy, p=0, s=0, h, f=0;
        long double n, m, y;
        cin>>n>>m;
        y=n*m+0.001;
        yy = y;

        cout<<yy<<endl;

    return 0;
}



Measured memory_bytes: 3768
use std::io::{BufRead, BufWriter, Write};

fn main() {
    let stdin = std::io::stdin();
    let stdout = std::io::stdout();
    solve(&mut stdin.lock(), &mut BufWriter::new(stdout.lock()));
}

fn solve<R: BufRead, W: Write>(stdin: &mut R, stdout: &mut BufWriter<W>) {
    let (h, w, _k): (usize, usize, usize) = stdin.gets().split(' ').values();
    let map = stdin.lines().take(h).map(|x| x.unwrap().into_bytes()).collect::<Vec<_>>();
    let mut head = 0;
    for i in 0..h {
        if map[i].contains(&b'#') {
            head = i;
            break;
        }
    }
    let mut ans = vec![vec![0; w]; h];
    let mut count = 1;
    for i in head..h {
        if !map[i].contains(&b'#') {
            for j in 0..w {
                ans[i][j] = ans[i - 1][j];
            }
            continue;
        }
        let mut first = true;
        for j in 0..w {
            if map[i][j] == b'#' {
                if first {
                    first = false;
                } else {
                    count += 1;
                }
            }
            ans[i][j] = count;
        }
        count += 1;
    }
    for i in 0..h {
        let ii = std::cmp::max(i, head);
        for j in 0..w {
            write!(stdout, "{} ", ans[ii][j]).unwrap();
        }
        writeln!(stdout, "").unwrap();
    }
}

trait Gets { fn gets(&mut self) -> String; }
impl<T: std::io::BufRead> Gets for T {
    fn gets(&mut self) -> String { self.lines().next().unwrap().unwrap() } }

trait Values<T> { fn values(&mut self) -> T; }
impl<'a, I, T1, T2, T3> Values<(T1, T2, T3)> for I
    where I: Iterator<Item=&'a str>,
          T1: std::str::FromStr, T1::Err: std::fmt::Debug,
          T2: std::str::FromStr, T2::Err: std::fmt::Debug,
          T3: std::str::FromStr, T3::Err: std::fmt::Debug {
    fn values(&mut self) -> (T1, T2, T3) {
        (self.next().unwrap().parse().unwrap(),
         self.next().unwrap().parse().unwrap(),
         self.next().unwrap().parse().unwrap())
    }
}


Measured memory_bytes: 4860
// AtCoder Regular Contest 078
// D - Fennec VS. Snuke

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;


const int MAX_N = 100000;

int N;
vector<int> G[MAX_N];
int par[MAX_N];
int depth[MAX_N];
int size[MAX_N];

void dfs(int v) {
    depth[v] = (par[v] < 0) ? 0 : depth[par[v]] + 1;
    size[v] = 1;
    for (int to : G[v]) {
        if (to == par[v]) {
            continue;
        }
        par[to] = v;
        dfs(to);
        size[v] += size[to];
    }
}

int main() {

    int m;
    int a, b;

    cin >> N;
    for (int i = 0; i < N - 1; i++) {
        cin >> a >> b;
        a--; b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    par[0] = -1;
    dfs(0);

    m = N - 1;
    for (int i = 0; i < (depth[N - 1] + 1) / 2 - 1; i++) {
        m = par[m];
    }

    cout << ((N - size[m] > size[m]) ? "Fennec" : "Snuke") << endl;

    return 0;

}





Measured memory_bytes: 11520
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.util.InputMismatchException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskC solver = new TaskC();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskC {
        public static final String UNRESTORABLE = "UNRESTORABLE";

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            String s = in.nextString();
            String t = in.nextString();

            if (t.length() > s.length()) {
                out.println(UNRESTORABLE);
                return;
            }

            int d = s.length() - t.length();
            out:
            for (int i = 0; i <= d; i++) {
                for (int j = 0; j < t.length(); j++) {
                    if (s.charAt(s.length() - 1 - i - j) == '?') continue;

                    if (s.charAt(s.length() - 1 - i - j) != t.charAt(t.length() - 1 - j)) continue out;
                }

                char[] ans = new char[s.length()];
                for (int j = 0; j < s.length(); j++) {
                    if (s.length() - t.length() - i <= j && j < s.length() - i) {
                        ans[j] = t.charAt(j - (s.length() - t.length() - i));
                    } else {
                        if (s.charAt(j) == '?') {
                            ans[j] = 'a';
                        } else {
                            ans[j] = s.charAt(j);
                        }
                    }
                }
                out.println(String.valueOf(ans));
                return;
            }

            out.println(UNRESTORABLE);
        }

    }

    static class InputReader {
        BufferedReader in;
        StringTokenizer tok;

        public String nextString() {
            while (!tok.hasMoreTokens()) {
                try {
                    tok = new StringTokenizer(in.readLine(), " ");
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
            }
            return tok.nextToken();
        }

        public InputReader(InputStream inputStream) {
            in = new BufferedReader(new InputStreamReader(inputStream));
            tok = new StringTokenizer("");
        }

    }
}



Measured memory_bytes: 21332
def main():
    n = int(input())
    l = list(map(int, input().split()))
    ans = 1
    
    if 0 in l:
      print(0)
      return
 
    for x in l:
        ans = ans*x
        if(ans > 1000000000000000000):
            print(-1)
            return
    print(ans)
 
main()


Measured memory_bytes: 21584
import java.util.Scanner;

public class Main {

	private void solve() {
		Scanner in = new Scanner(System.in);
		long N = in.nextInt();
		double d_k = 0;
		long i_k = 0;
		for (long i = 1; i <= 3500; i++) {
			for (long j = 1; j <= 3500; j++) {
				if(4*i*j - N*i - N*j == 0) continue;
				d_k = (double)(N*i*j) / (4*i*j - N*i - N*j);
				i_k = N*i*j / (4*i*j - N*i - N*j);
				if(d_k == i_k && i_k >= 0 && i_k <= 3500){
					System.out.println(i+" "+j+" "+i_k);
					//System.out.println(4*i*j*i_k);
					//System.out.println(N*(i*j+j*i_k+i_k*i));
					return;
				}
			}
		}
		
	}

	public static void main(String[] args) {
		new Main().solve();
	}
}

Measured memory_bytes: 22996
#include<stdio.h>

struct pair
{
	int key;
	int bi;
};

void quicksort(struct pair data[],int left,int right);

int main()
{
    int n,m,i,j,a,b,flag=0,ans=0;
	struct pair arr[100000];
	int kenarr[100000][2];
	//int ans=0;
	scanf("%d %d",&n,&m);
	for(i=0;i<m;i++)
	{
		scanf("%d %d",&(arr[i].key),&(arr[i].bi));
	}
	quicksort(arr,0,m-1);
	

	for(i=0;i<m;i++)
	{
		if(ans==(n-2))break;
		a=arr[i].key;
		b=arr[i].bi;
		if(i==0)
		{
			kenarr[0][0]=a;
			kenarr[0][1]=b;
		}
		else
		{
			flag=0;
			for(j=0;j<=ans;j++)
			{
				if((kenarr[j][1]>a)&&(kenarr[j][0]<b))
				{
					flag=1;
					if(kenarr[j][0]<a)kenarr[j][0]=a;
					if(kenarr[j][1]>b)kenarr[j][1]=b;
				}
				if(flag)break;
			}
			if(!flag)
			{
				ans++;
				kenarr[ans][0]=a;
				kenarr[ans][1]=b;
			}
		}
	}
	
	//for(i=0;i<ans+1;i++)printf("%d,%d\n",kenarr[i][0],kenarr[i][1]);
	printf("%d",ans+1);
}


void quicksort(struct pair data[],int left,int right)
{
	int i,j;
	struct pair std,work;
	if(left<right)
	{
		i=left,j=right;
		std=data[(i+j)/2];//基準
		do
		{
			while(data[i].key < std.key)i++;
			while(data[j].key > std.key)j--;
			if(i<=j)
			{
				if(i<j)
				{
					work=data[i];
					data[i]=data[j];
					data[j]=work;
				}
				i++; j--;
			}
		}while(i<=j);
		if(left<j)quicksort(data,left,j);
		if(i<right)quicksort(data,i,right);
	}
}


Measured memory_bytes: 896
#include <iostream>
#include <cstring>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <math.h>
#include <string>
#include <map>
#include <cstdlib>
#include <sstream>
#include <bitset>
using namespace std;

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



int main()
{
    int x;
    cin >> x;
    if(x>=30) cout << "Yes" << endl;
    else cout << "No" << endl;




    return 0;
}

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

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)n; i++)
#define vec vector
#define ll long long

int main(void)
{
	int n;
	cin >> n;
	vec<int> a(n);
	rep(i, n) cin >> a[i];

	int min = 1;
	ll ans = 0;
	rep(i, n) {
		if (a[i] != min) ans += (ll)((a[i] - 1) / min);
		else min++;
		if (i == 0) min = 2;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 640
import sys
readline = sys.stdin.readline

class WeightedUnionFind:
    def __init__(self, n):
        self.parents = [i for i in range(n)]
        self.rank = [0] * n
        self.weight = [0] * n  # 根への距離を管理

    def find(self, x):
        if self.parents[x] == x:
            return x
        else:
            y = self.find(self.parents[x])
            # 親への重みを追加しながら根まで走査
            self.weight[x] += self.weight[self.parents[x]]
            self.parents[x] = y
            return y

    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        # xの木の高さ < yの木の高さ
        if self.rank[rx] < self.rank[ry]:
            self.parents[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        # xの木の高さ ≧ yの木の高さ
        else:
            self.parents[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            # 木の高さが同じだった場合の処理
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)

    # xからyへのコスト
    def diff(self, x, y):
        return self.weight[x] - self.weight[y]

def main():
    N, M = map(int, readline().rstrip().split())    
    uf = WeightedUnionFind(N)

    for _ in range(M):
        l, r, d = map(int, readline().rstrip().split())
        l -= 1
        r -= 1
        if uf.same(l, r):
            if uf.diff(l, r) != d:
                print('No')
                return

        uf.union(l, r, d)
    
    print('Yes')

if __name__ == '__main__':
    main()

Measured memory_bytes: 84068
n = int(input())
a = list(map(int, input().split()))
if n % 2 == 0:
    x = 0
    for i in a:
        x ^= i
    for i in a:
        print(x ^ i)
else:
    p = []
    x = 0
    for i in a[:n - 1]:
        x ^= i
    for i in a[:n - 1]:
        p.append(x ^ i)
    x = a[0]
    for i in p[1:]:
        x ^= i
    p.append(x)
    print(*p)


Measured memory_bytes: 94160
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define all(x) x.begin(), x.end()
typedef long long ll;

int main() {
    int N; cin >> N;
    vector<int> A(N);
    for(int i = 0; i < N; ++i) {
        A[i] = i + 1;
    }
    vector<int> P(N), Q(N);
    for(int i = 0; i < N; ++i) cin >> P[i];
    for(int i = 0; i < N; ++i) cin >> Q[i];
    int idx = 0, p = -1, q = -1;
    do {
        bool equalP = true, equalQ = true;
        for(int i = 0; i < N; ++i) {
            if(A[i] != P[i]) equalP = false;
            if(A[i] != Q[i]) equalQ = false;
        }
        if(equalP) p = idx; 
        if(equalQ) q = idx; 
        ++idx;
    } while(next_permutation(all(A)));
    cout << abs(p - q) << endl;
}

Measured memory_bytes: 256
#input of int(split by space)
def get_i()
  return gets.chomp.split(" ").map(&:to_i)
end
#input of float(split by space)
def get_f()
  return gets.chomp.split(" ").map(&:to_f)
end
#input of string(split by space)
def get()
  return gets.chomp.split(" ")
end
#input of string(split per one character)
def get_nsp()
  return gets.chomp.split("")
end
#yes or no decision
def yn_judge(bool,y="Yes",n="No")
  return bool ? y : n 
end
#create of array
def array(size1,init=nil,size2=-1)
  if size2==-1
      return Array.new(size1){init}
  else
      return Array.new(size2){Array.new(size1){init}}
  end
end

def max(a,b)
    return a>b ? a : b
end

def min(a,b)
    return a>b ? b : a
end

INF=Float::INFINITY

N,A,B,C=get_i
l=array(N)
N.times do|i|
    l[i]=gets.to_i
end
ans=INF
(4**N).times do|bit|
  type=Array.new(4){[]}
  t=bit
  N.times do|i|
      type[t%4]<< i
      t/=4
  end
  next unless type[0].size>0 and type[1].size>0 and type[2].size>0
  val=0
  val+=(type[0].size-1)*10+(A-type[0].inject(0){|res,x| res+=l[x]}).abs
  val+=(type[1].size-1)*10+(B-type[1].inject(0){|res,x| res+=l[x]}).abs
  val+=(type[2].size-1)*10+(C-type[2].inject(0){|res,x| res+=l[x]}).abs
  ans=min(ans,val)
end
puts ans

Measured memory_bytes: 14292
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
using ll = long long;

int main() {
    int n, i;
    cin >> n >> i;
    i--;

    int j = n - 1 - i;

    cout << j + 1 << endl;

    return 0;
}

Measured memory_bytes: 256
A, B, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = min(a) + min(b)
for _ in range(M):
    x, y, c = map(int, input().split())
    if a[x-1] + b[y-1] -c < ans:
        ans = a[x-1] + b[y-1] -c
print(ans)


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

int main() {
    string s, s_left = "", s_right = "";
    int q, t, f, rev = 0;
    char c;
    cin >> s;
    scanf("%d", &q);
    while (q--) {
        scanf("%d", &t);
        if (t == 1) {
            rev ^= 1;
        } else {
            scanf("%d %c", &f, &c);
            --f;
            if (rev ^ f) {
                s_right += c;
            } else {
                s_left += c;
            }
        }
    }
    if (rev) {
        for (int i = s_right.length() - 1; i >= 0; --i) {
            printf("%c", s_right[i]);
        }
        for (int i = s.length() - 1; i >= 0; --i) {
            printf("%c", s[i]);
        }
        for (int i = 0; i < s_left.length(); ++i) {
            printf("%c", s_left[i]);
        }
    } else {
        for (int i = s_left.length() - 1; i >= 0; --i) {
            printf("%c", s_left[i]);
        }
        for (int i = 0; i < s.length(); ++i) {
            printf("%c", s[i]);
        }
        for (int i = 0; i < s_right.length(); ++i) {
            printf("%c", s_right[i]);
        }
    }
    printf("\n");
    return 0;
}


Measured memory_bytes: 1088
#include<stdio.h>
#include<stdlib.h>
#define MAX 20000 

typedef struct{
  int top;        
  int S[MAX];
}Stack;

void initialize(Stack *st)
{
  st->top = 0;
  st->S[st->top] = 0;
}

int isEmpty(Stack *st)
{
  return st->top == 0;
}

int isFull(Stack *st)
{  
  return st->top >= MAX - 1;
}

void push(int x, Stack *st)
{
  if (isFull(st)) 
    exit(1);

  st->top++;
  st->S[st->top] = x;
}

int pop(Stack *st) {
  if (isEmpty(st)) exit(1);

  st->top--;
  return st->S[st->top+1];
}


int main(void)
{
  Stack st1;     // '\' の開始位置を格納するスタック
  Stack st2_j;   // 各水たまりの最も左の'\' の位置を格納するスタック
  Stack st2_a;   // 各水たまりの水量を格納するスタック

  initialize(&st1);
  initialize(&st2_j);
  initialize(&st2_a);

  char c;
  int sum = 0;  // 水たまりの総水量

  // 地形を読み込み，各水たまりの水量を計算
  for (int i = 0; (c = getchar()) != EOF; i++) {
    if (c == '\\') push(i, &st1);
    else if (!isEmpty(&st1) && c == '/') {
      // 水たまりの総水量 sum を更新(write your code)
      int j = pop(&st1);
      sum += i - j;
      
      // st2_j と st2_a を用いて水たまりの水量を更新 
      int a = i - j;   // 更新する水たまりの水量を a に格納していく
      while (!isEmpty(&st2_j) && st2_j.S[st2_j.top] > j) {  // 最も左の '\' の位置が j よりも大きい場合，以下を繰り返す
        a += pop(&st2_a);// 水たまりの水量を求めていく (write your code)
        pop(&st2_j);
      }
      // 更新した水たまりの「最も左の'\' の位置」および「水量」を更新 (write your code)
      push(a, &st2_a);
      push(j, &st2_j);
    }
  }

  printf("%d\n", sum);       // 水たまりの総水量を出力
  printf("%d", st2_a.top);   // 水たまりの個数を出力

  // 各水たまりの水量を断面図の左から出力(スタックの底から出力)
  for (int i = 1; i <= st2_a.top; i++) 
    printf(" %d", st2_a.S[i]);  
  printf("\n");

  return 0;
}


Measured memory_bytes: 2108
#include "bits/stdc++.h"
using namespace std;


int main()
{
	int64_t a, b, n;
	cin >> a >> b >> n;

	int64_t x;
	x = min(b - 1, n);

	int64_t ans = (a * x / b) - a * (x / b);

	cout << ans << endl;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(V) V.begin(),V.end()
#define MOD 1000000007

ll A[200010], C[200010];

int main() {
	ll N, K;
	cin >> N >> K;
	for (ll i = 1;i <= N;i++) {
		cin >> A[i];
	}
	for (int i = 0;i < 200010;i++)C[i] = -1;
	C[1] = 0;
	ll d = 1, n = 1;
	while (1) {
		n = A[n];
		if (C[n] != -1) {
			K -= C[n];
			d -= C[n];
			break;
		}
		C[n] = d;
		if (d == K)break;
		d++;
	}
	K %= d;
	for (ll i = 1;i <= K;i++) {
		n = A[n];
	}
	cout << n << endl;
}


Measured memory_bytes: 6696
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  vector<int> vec(N);
  for (int i = 0; i < N; i++) {
    cin >> vec.at(i);
  }
  sort(vec.begin(), vec.end());
 
  int sum = vec.size();
  
  for (int i = 0; i < N - 1; i++) {
    if (vec.at(i) == vec.at(i + 1)) sum -= 1;
  }
  cout << sum;
}
  


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

int main(){
  int N,K; //Nが値段、Kが嫌いな個数
  cin >> N >> K;
  vector<int> vec(K);
  for(int i = 0; i < K; i++){
    cin >> vec.at(i);
  }
  
  while(1){
    int m,ck=0;
    m=N;
    while(m){
      int r;
      r = m % 10;
      ck = 0;
      for(int i = 0; i < K; i++){
        if(r == vec.at(i)){
          ck = 1;
          break;
        }
      }
      if(ck == 1){
        break;
      }
      m /= 10;
    }
    if(ck == 0){
      cout << N << endl;
      break;
    }
    else{
      N++;
    }
  }
}

Measured memory_bytes: 256
#define rep(i, a, b) for(int i = a; i < (int)(b); i++)
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
template<class T> inline void chmax(T &a, const T &b) {if(a < b) a = b;}
template<class T> inline void chmin(T &a, const T &b) {if(a > b) a = b;}
const long long INF = 1LL<<60;
const long long MOD = (ll)1e9+7;
const long long MAX = (ll)1e5+1000;

map< long long, int > prime_factor(long long n) {
  map< long long, int > ret;
  for(long long i = 2; i * i <= n; i++) {
    while(n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if(n != 1) ret[n] = 1;
  return ret;
}

// テーブルを作る前処理
long long fac[MAX], finv[MAX], inv[MAX];
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}


int main(void) {
   ll N,M;
   cin>>N>>M;
   auto ret = prime_factor(M);
   COMinit();
   ll ans = 1;
   for (auto el:ret) {
      int n = el.second + N -1;
      int m = el.second;
      // cout<<COM(n,m)<<endl;
      // cout<<el.first<<" "<<el.second<<endl;
      ans *= COM(n,m)%MOD;
      ans%=MOD;
   }
   ans += MOD;
   ans %= MOD;
   cout<<ans<<endl;



   return 0;
}

Measured memory_bytes: 2560
#include<iostream>
#include<string>
using namespace std;
int main(){
 int N;
 string S;
 cin>>N>>S;
for(int i=0;i<S.size();i++){
  S.at(i)=(S.at(i)-'A'+N)%26+'A';
  cout<<S.at(i);
}
 cout<<endl;
}


Measured memory_bytes: 256
import numpy as np
def resolve():
    MOD = 10 ** 9 + 7
    n, m = map(int, input().split())
    a = [int(input()) for _ in range(m)]

    dp = np.array([1] * (n + 1))
    dp[a] = 0

    for i in range(2, n + 1):
        if dp[i] != 0:
            dp[i] = np.sum(dp[i - 2:i]) % MOD

    print(dp[n])
    
resolve()

Measured memory_bytes: 17796
#include"bits/stdc++.h"
#include<unordered_set>
#include<unordered_map>
#include<random>
using namespace std;
typedef long long ll;
const ll MOD = (ll)(1e9+7);
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
int dx[4]={ 1,0,-1,0 };
int dy[4]={ 0,1,0,-1 };

int H, W;
int cost[10][10];

signed main(){
    cin >> H >> W;

    rep(i, 10){
        rep(j, 10){
            cin >> cost[i][j];
        }
    }

    rep(i, 10){
        rep(j, 10){
            rep(k, 10){
                cost[j][k] = min(cost[j][k], cost[j][i]+cost[i][k]);
            }
        }
    }

    int ans = 0;
    rep(i, H){
        rep(j, W){
            int A;
            cin >> A;
            if(A == -1) continue;
            ans += cost[A][1];
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
from math import sqrt,gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint
from statistics import mean,median,mode
import sys
sys.setrecursionlimit(10 ** 6)

INF = float("inf")

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    # lsはソート済みであること
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

def I():
    return int(input())

def MI():
    return map(int,input().split())

def RI():
    return list(map(int,input().split()))

def CI(n):
    return [ int(input()) for _ in range(n) ]

def LI(n):
    return [ list(map(int,input().split())) for _ in range(n) ]

def S():
    return input()

def MS():
    return input().split()

def RS():
    return list(input())

def CS(n):
    return [ input() for _ in range(n) ]

def LS(n):
    return [ list(input()) for _ in range(n) ]

# ddict = defaultdict(lambda: 0)
# ddict = defaultdict(lambda: 1)
# ddict = defaultdict(lambda: int())
# ddict = defaultdict(lambda: list())
# ddict = defaultdict(lambda: float())

n = I()

a = floor(sqrt(n*2))
b = a + 1

if a*b==n*2:
    print("Yes")
    print(b)
    d = [ [0]*a for _ in range(b) ]
    for i in range(1,a+1):
        d[i-1][i-1] = i
        d[i][i-1] = i
    # pprint(d)
    c = b
    for i in range(b):
        for j in range(a):
            if d[i][j]==0:
                d[i][j] = c
                d[j+1][i] = c
                c += 1
    # pprint(d)
    for i in range(b):
        print(a,end=" ")
        myoutput(d[i],space=True)
else:
    print("No")

Measured memory_bytes: 75256
#include <bits/stdc++.h>
#define rep(i,a,b) for(ll i=ll(a);i<ll(b);i++)
#define irep(i,a,b) for(ll i=ll(a);i>=ll(b);i--)
#define pb push_back
#define mp make_pair
#define F .first
#define S .second 
using ll=long long;
using ld=long double;
using namespace std;
const ll mod=1e9+7;

main(){
    string s;
    cin>>s;
    ll ans=s.length()-2;
    cout<<s[0]<<ans<<s[s.length()-1];
}




Measured memory_bytes: 256
N = int(input())
A = list(map(int,input().split()))
ans = [0 for _ in range(N)]
l = 0
r = N - 1
flg = 1
for i in range(N - 1, -1, -1):
    if flg:
        flg = 0
        ans[l] = A[i]
        l += 1
    else:
        flg = 1
        ans[r] = A[i]
        r -= 1
print(*ans)

Measured memory_bytes: 114476
import java.util.Scanner;

//Secret Number
public class Main{

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int s = 0;
		while(sc.hasNext()){
			char[] m = sc.next().toCharArray();
			for(int i=0;i<m.length;i++){
				if(Character.isDigit(m[i])){
					int x = m[i++]-'0';
					while(i<m.length&&Character.isDigit(m[i])){
						x*=10;
						x+=m[i++]-'0';
					}
					s+=x;
				}
			}
		}
		System.out.println(s);
	}
}

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

int main() {
  int n, m;
  cin >> n >> m;
  
  int a;
  int sum = 0;
  vector<int> product(n);
  for (int i = 0; i < n; i++) {
    cin >> a;
    product.at(i) = a;
    sum += a;
  }
  
  int criteria = (sum + 4 * m - 1) / (4 * m);
  int count = 0;
  for (int i = 0; i < n; i++) {
    if (product.at(i) >= criteria) {
      count++;
    }
  }
  
  if (count >= m) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(void) {

	int H, W;
	while(true) {
		cin >> H >> W;
		if(H == 0 && W == 0)	break;

		for(int i=0;i<H;i++) {
			for(int j=0;j<W;j++) {
				cout << "#";
			}
			cout << endl;
		}

		cout << endl;
	}

	return 0;
}

Measured memory_bytes: 1152
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Main{
	public static void main(String[] args){
		BufferedReader reader =
				new BufferedReader(new InputStreamReader(System.in));
		
		try{
			int n = Integer.parseInt(reader.readLine());
			
		for(int i = 0; i < n; i++){
			
			String str = reader.readLine();
			
			str = str.replaceAll("Hoshino","Hoshina");
			
			System.out.println(str);
			
		}
		}catch(IOException e){
		}
	}
}

Measured memory_bytes: 16960
#include<queue>
#include<bitset>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAXN = 100000+9;
int K;
bitset<MAXN> inque;
int dis[MAXN];
queue<int> que;

void SPFA(){
	dis[0]=K;
	for(int i=1;i<K;i++)
		dis[i]=i;
	for(int i=0;i<K;i++){
		que.push(i);
		inque[i]=1;
	}
	while(!que.empty()){
		int fro=que.front();que.pop();inque[fro]=0;
		for(int i=0;i<9;i++){
			int val=(fro*10+i)%K;
			if(dis[val]>dis[fro]+i){
				dis[val]=dis[fro]+i;
				if(!inque[val]){
					inque[val]=1;
					que.push(val);
				}
			}
		}
	}
}

int main(){
	scanf("%d",&K);
	SPFA();
	printf("%d\n",dis[0]);
	return 0;
}


Measured memory_bytes: 1024
#include <stdio.h>
int main(){
  int n,a=0;
  scanf("%d",&n);
  char s[1000];
  scanf("%s",s);
  if(n%2==1) a=1;
  else{
  	for(int i=0;i<n/2;i++){
    	if(s[i]!=s[i+n/2]) a=1;
  	}
  }
  if(a==0) printf("Yes\n");
  else printf("No\n");
  return 0;
}

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

int ways(int n,int x){
	int a=0;
	for(int i=1;i<=n-2;i++) for(int j=i+1;j<=n-1;j++) for(int k=j+1;k<=n;k++) if(i+j+k==x) a++;
	return a;
}

int main(){
	int i,n,x,a[10000];
	for(i=0;;i++){
		cin>>n>>x;
		if(!n) break;
		a[i]=ways(n,x);
	}
	for(int j=0;j<i;j++) cout<<a[j]<<endl;
	return 0;
}



Measured memory_bytes: 3104
N,P=[int(i) for i in input().split()]
wb=[[int(j) for j in input().split()] for i in range(N)]
xs = [(100-P)*w+P*b for w,b in wb]
xs.sort()
xs.reverse()

score=0
for i in range(N):
    score-=P*wb[i][1]
for i in range(N):
    score+=xs[i]
    if score>=0:
        print(i+1)
        break


Measured memory_bytes: 26356
X,N = map(int,input().split())

if N == 0:
  print(X)
else:
  p = list(map(int,input().split()))
  for i in range(100):
    a = X + i
    b = X - i
    if b not in p:
      print(b)
      break
    if a not in p:
      print(a)
      break

Measured memory_bytes: 9184
#include<bits/stdc++.h>
#define MAX 1000
#define mp make_pair
using namespace std;
typedef pair<int,int> pii;
int n,m,a[MAX+5][MAX+5];
int dir1[4]={0,0,-1,1},dir2[4]={1,-1,0,0};
queue<pii>q;
int out(int x,int y)
{
	return x<1||y<1||x>n||y>m;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1; i<=n; i++)
	{
	cin.ignore();
    for(int j=1; j<=m; j++)
	{
	scanf("%c",&a[i][j]);
	if(a[i][j]=='#') q.push(mp(i,j)); 
    }
    }
    int sz=q.size(),cnt=0;
    while(!q.empty())
    {
    	int x=q.front().first,y=q.front().second; q.pop();
    	if(!sz) cnt++,sz=q.size();
    	else sz--;
    	for(int i=0; i<4; i++)
    	{
    		int xs=x+dir1[i],ys=y+dir2[i];
    		if(out(xs,ys)||a[xs][ys]=='#') continue;
			q.push(mp(xs,ys)); a[xs][ys]='#';
    	}
    }
    printf("%d",cnt);
	return 0;
}

Measured memory_bytes: 12304
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    INF = 10**18    

    # 最小消費MP
    def rec(i, a, b, c):# i:現在使った本数　a,b,c：現在の竹の長さ
        # 全て竹使ったら理想とのズレを魔法1,2で埋めてく
        if i == N:
            if not a or not b or not c:
                return INF
            return abs(a-A)+abs(b-B)+abs(c-C)
        
        # 竹不採用
        res = rec(i+1, a, b, c)
        # a採用
        if a >= 1:
            res = min(res, rec(i+1, a+L[i], b, c)+10)
        else:
            res = min(res, rec(i+1, a+L[i], b, c))
        # b採用
        if b >= 1:
            res = min(res, rec(i+1, a, b+L[i], c)+10)
        else:
            res = min(res, rec(i+1, a, b+L[i], c))
        
        # c採用
        if c >= 1:
            res = min(res, rec(i+1, a, b, c+L[i])+10)
        else:
            res = min(res, rec(i+1, a, b, c+L[i]))

        return res

    N, A, B, C = map(int, input().split())
    L = [int(input()) for _ in range(N)]

    print(rec(0, 0, 0, 0))

resolve()

Measured memory_bytes: 45020
import numpy as np

N = int(input())
A = []
B = []

for i in range(N):
  a, b = map(int, input().split())
  A.append(a)
  B.append(b)
A = np.array(A)
B = np.array(B)

J = np.argsort(np.array(B))
A = A[J]
B = B[J]

A = np.cumsum(A)

ans = np.min(B - A)

if (ans < 0):
  print('No')
else:
  print('Yes')


Measured memory_bytes: 28064
using System;
using System.Collections.Generic;
using System.Linq;
using static Input;

public class Prog
{
    public struct Pair { public int x, y; public Pair(int x, int y) { this.x = x; this.y = y; } }
    public static void Solve()
    {
        int M = NextInt(), D = NextInt();
        int ans = 0;
        for (int i = 1; i <= M; i++)
            for (int j = 22; j <= D; j++) {
                if (j % 10 <= 1) continue;
                int b = 1;
                foreach (char c in j.ToString()) b *= int.Parse(c.ToString());
                if (b == i) ans++;
            }
        Console.WriteLine(ans);
    }
    public static void Main()
    {
        var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
        Console.SetOut(sw);
        Solve();
        Console.Out.Flush();
    }
}
public class Input
{
    public const long MOD = 1000000007;
    public const int INF = 1000000007;
    private static Queue<string> q = new Queue<string>();
    private static void Confirm() { if (q.Count == 0) foreach (var s in Console.ReadLine().Split(' ')) q.Enqueue(s); }
    public static int NextInt() { Confirm(); return int.Parse(q.Dequeue()); }
    public static long NextLong() { Confirm(); return long.Parse(q.Dequeue()); }
    public static string NextString() { Confirm(); return q.Dequeue(); }
    public static double NextDouble() { Confirm(); return double.Parse(q.Dequeue()); }
    public static int[] LineInt() { return Console.ReadLine().Split(' ').Select(int.Parse).ToArray(); }
    public static long[] LineLong() { return Console.ReadLine().Split(' ').Select(long.Parse).ToArray(); }
    public static string[] LineString() { return Console.ReadLine().Split(' ').ToArray(); }
    public static double[] LineDouble() { return Console.ReadLine().Split(' ').Select(double.Parse).ToArray(); }
}


Measured memory_bytes: 13268
li = []
for i in range(5):
    li.append(int(input()))

li2 = [];ans = 0
for i in li:
    if i%10 == 0:
        ans += i
    else:
        ans += i + (10-i%10)
        li2.append(i%10)
if li2 != []:
    ans -= 10-min(li2)

print(ans)



Measured memory_bytes: 2940
#include <cstdio>

typedef long long ll;

ll gcd(ll x, ll y)
{
    if (x < 0) return gcd(-x, y);
    if (y < 0) return gcd(x, -y);
    if (x < y) return gcd(y, x);
    if (y == 0) return x;
    return gcd(y, x % y);
}

int main()
{
    ll N, X;
    ll x[100000];
    scanf("%lld %lld", &N, &X);
    for (ll i = 0; i < N; i++) {
        scanf("%lld", &x[i]);
        x[i] -= X;
    }
    ll ans = 0;
    for (ll i = 0; i < N; i++) {
        ans = gcd(x[i], ans);
    }
    printf("%lld\n", ans);
    
}


Measured memory_bytes: 896
n = int(input())
a = [int(i) for i in input().split()]
x,y = a[0],sum(a)-a[0]
answer = abs(x-y)
for i in range(1,n-1):
	x += a[i]
	y -= a[i]
	if answer > abs(x-y):
		answer = abs(x-y)
print(answer)


Measured memory_bytes: 24832
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
const ll LL_MAX=LLONG_MAX;

struct In{
    template<typename T>
    operator T(){
        T x;
        cin >> x;
        return x;
    }
};
In in;

template <typename T,typename U>
void forin(T* x,U n){
    for (U i=0;i<n;i++) cin >> x[i];
}

template <typename T>
int div1(T x) {
    return x%1000000007;
}

template <typename T>
void out(T x){
    cout << x << endl;
}

template <typename T>
T gcd(T x,T y){
    if (y == 0) return x;
    return gcd(y,x%y);
}

template <typename T>
T lcm(T x,T y){
    return x*y/gcd(x,y);
}

int main(){
    int n=in,k=in;
    vector<int> p(n);
    for (int i=0;i<n;i++) cin >> p[i];
    sort(p.begin(),p.end());
    int ans=0;
    for (int i=0;i<k;i++){
        ans+=p[i];
    }
    cout << ans << endl;
}

Measured memory_bytes: 3628
#include <stdio.h>
    int main() {
    int a, b, c;
    scanf("%d", &a);
    scanf("%d", &b);
    scanf("%d", &c);
    a = c - a;
    if (a <= b && a >= 0) {
    printf("YES\n");
    } else if (a > b || a < 0) {
    printf("NO\n");
    } return 0;
    }  

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define pb push_back

using namespace std;
typedef long long ll;

const int P=1e9+7,N=2333;
int fpow(int a,int t){static int r;for(r=1;t;t>>=1,a=(ll)a*a%P)if(t&1)r=(ll)r*a%P;return r;}

int n,k,m,ve[N],f[N],ans;

int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i*i<=n;i++)if(n%i==0){ve[++m]=i;if(i*i<n)ve[++m]=n/i;}
	sort(ve+1,ve+m+1);
	for(int i=1;i<=m;i++){
		f[i]=fpow(k,(ve[i]+1)/2);
		for(int j=1;j<i;j++)if(ve[i]%ve[j]==0)f[i]=(f[i]-f[j]+P)%P;
		if(ve[i]&1)ans=(ans+(ll)ve[i]*f[i])%P;
		else ans=(ans+(ll)(ve[i]>>1)*f[i])%P;
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
    int n;
    cin>>n;
    long long a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int q;
    cin>>q;
    while(q--)
    {
        int b,e,k;
        cin>>b>>e>>k;
        int val=0;
        for(int i=b;i<e;i++)
        {
            if(a[i]==k)
            {
                val++;
            }
        }
        cout<<val<<endl;
    }
    return 0;
}



Measured memory_bytes: 3108
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
#define rep(i,n) for (ll i=0;i<n;++i)
#define rep2(i,a,b) for (ll i=a;i<b;++i)
const ll MOD=1000000007;
string alp="abcdefghijklmnopqrstuvwxyz";

int main(){
    int N;
    cin >> N;
    vector<int> a(N);
    int m=N,M=0;
    rep(i,N){
        cin >> a[i];
        m=min(m,a[i]);
        M=max(M,a[i]);
    }
    if (M-m>1){
        cout << "No" << endl;
    }
    else if (M==m){
        if (N>=M*2||M==N-1){
            cout << "Yes" << endl;
        }
        else {
            cout << "No" << endl;
        }
    }
    else {
        int count=0;
        rep(i,N){
            if (a[i]==m){
                count++;
            }
        }
        if (M<=count){
            cout << "No" << endl;
        }
        else if (M*2-count<=N){
            cout << "Yes" << endl;
        }
        else {
            cout << "No" << endl;
        }
    }
}

Measured memory_bytes: 640
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <time.h>
#include <math.h>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <iterator>
#include <sstream>
#include <string>
#include <bitset>
using namespace std;
#define FOR(I,F,N) for(int I = F; I < (int)(N); I++)
#define rep(i, n) FOR(i, 0, n)
#define FIN(V) cout<<V<<endl
#define pb push_back
#define INF (1 << 30)

template<typename T>
void remove(vector<T>& vector, unsigned int index){
vector.erase(vector.begin() + index);
}

typedef pair<int, int> P;
typedef long long ll;
typedef priority_queue<int> pq;
int StrToInt(string);
string IntToStr(int);
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int N, C;
int a[32];
int dp[1<<16][32];
int pop[32];

int solve(int score, int n){
	if(n == N)return 0;
	if(dp[score][n] >= 0)return dp[score][n];
	int tmp = score|a[n];
	int result = 0;
	for(int i = 0; i < C; i++){
		int tmp2 = tmp & pop[i];
		int cnt = __builtin_popcount(tmp2);
		result = max(result, solve(tmp-tmp2, n+1)+cnt);
	}

	return dp[score][n] = result;
}

int main(void){
	while(cin >> N >> C, N|C){
		rep(i,1<<16)rep(j,32)dp[i][j] = -1;
		fill_n(pop, 32, 0);
		fill_n(a, 32, 0);
		
		for(int i = 0; i < N; i++){
			for(int j = 0; j < 16; j++){
				bool x;
				if(cin >> x){
					a[i] |= (x<<j);
				}
			}
		}
		for(int i = 0; i < C; i++){
			for(int j = 0; j < 16; j++){
				bool x;
				if(cin >> x){
					pop[i] |= (x << j);
				}
			}
		}
		cout << solve(0, 0) << endl;
	}
	return 0;
}



int StrToInt(string s){
	stringstream ss;
	ss << s;
	int val;
	ss >> val;
	return val;
}
string IntToStr(int i){
	stringstream ss;
	ss << i;
	return ss.str();
}

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

using namespace std;

int main() {
	int n, k;
	scanf("%d%d", &n, &k);
	
	double res = 0;
	
	for (int i = 1; i <= n; i++) {
		double p = 1.0;
		int cnt = 0;
		int tmp = i;
		
		while (tmp <= k - 1) {
			p /= 2;
			tmp *= 2;
			cnt++;
		}
		
		p /= n;
		
		res += p;
	}
	
	printf("%.12lf\n", res);
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
int main(){
  int N;
  cin>>N;
  vector<pair<int,int>> A;
  for(int i=0;i<N;i++){
    int a;
    cin>>a;
    A.emplace_back(a,i+1);
  }
  sort(A.begin(),A.end());
  for(int i=0;i<N-1;i++){
    cout<<A[i].second<<" ";
  }
  cout<<A[N-1].second<<endl;
  return 0;
}

Measured memory_bytes: 1780
#include<bits/stdc++.h>
using namespace std;
bool vis[30100];
int s[30100];
int main(){
//	freopen("B.in","r",stdin);
	int n;
	scanf("%d",&n);
	if(n==3){
		printf("2 5 63\n");
		return 0;
	}
	if(n>=15000){
		for(int i=1;i<=30000;i++)
			if(i%2==0||i%3==0)
				vis[i]=1;
		int res=20000-n;
		for(int i=1;i<=30000;i++){
			if(!res) break;
			if(i%6==0){
				vis[i]=0;
				res--;
			}
		}
		for(int i=1;i<=30000;i++)
			if(vis[i])
				printf("%d ",i);
		printf("\n");
		return 0;
	}
	s[1]=3,s[2]=9,s[3]=2;
	for(int i=4;i<=n;i++)
		s[i]=(i-2)*2;
	int sum=0;
	for(int i=1;i<=n;i++)
		sum+=s[i];
	while(sum%3!=0){
		s[n]+=2;
		sum+=2;
	}
	for(int i=1;i<=n;i++)
		printf("%d ",s[i]);
	printf("\n");
	return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <string>
#include <cstring>
#include <complex>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
#define mp make_pair

const int N = 100100;
const int K = 20;

vector<int> g[N];
vector<pii> dp[N];
vector<pii> a[K];
int n;

void dfs(int v, int par)
{
    int d = 0;
    for (int u : g[v])
    {
        if (u == par) continue;
        dfs(u, v);
        d = max(d, dp[u][0].second);
    }
    for (int i = 0; i < K; i++)
        a[i].clear();
    for (int u : g[v])
        if (u != par)
            a[dp[u][0].second].push_back(mp(u, 0));
//    printf("solving %d\n", v);
    int goodLen = 0;
    int goodD = d + 1;
    while(true)
    {
//        printf("d = %d\n", d);
        if (d < 0)
        {
            break;
        }
        if (a[d].empty())
        {
            while(d > 0 && a[d - 1].empty()) d--;
            goodLen = dp[v].size();
            goodD = d;
            d--;
            continue;
        }
        if ((int)a[d].size() >= 2)
        {
            break;
        }
        int u = a[d][0].first;
        int p = a[d][0].second;
//        printf("%d %d\n", u, p);
        dp[v].push_back(dp[u][p]);
        p++;
        if (p < (int)dp[u].size())
            a[dp[u][p].second].push_back(mp(u, p));
        d--;
    }
    while((int)dp[v].size() > goodLen) dp[v].pop_back();
    dp[v].push_back(mp(v, goodD));
    return;
}

int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    scanf("%d", &n);
    for (int i = 1; i < n; i++)
    {
        int v, u;
        scanf("%d%d", &v, &u);
        v--;u--;
        g[v].push_back(u);
        g[u].push_back(v);
    }
    dfs(0, -1);
    printf("%d\n", dp[0][0].second);

    return 0;
}

Measured memory_bytes: 27648