akhauriyash/Code-Regression huggingface dataset:
import Data.List
import Control.Monad

gen_modifier::[(Int,Int)]->[Int]
gen_modifier ls = let srtd = sortBy (\ (_,c_1) -> \ (_,c_2) -> compare c_2 c_1) ls  in
                  concat [take b (repeat c)|(b,c)<-srtd]


solver::[(Int,Int)]->[Int]->Int
solver bcs a_s =  let sorted_as = sort a_s in
                  let incr =  (sum.takeWhile (0<).map (\ (c,a)-> c-a).zip (gen_modifier bcs)) sorted_as in
                  incr  + (sum a_s)

main::IO()
main=do
  n:m:_ <- return . map read . words =<< getLine
  a_s   <- return . map read . words =<< getLine
  bcs <- forM [1..m] (\ _ -> return . (\ (b:c:_) -> (b,c)) .  map read . words =<< getLine)
  print (solver bcs a_s)

Measured memory_bytes: 178556
N = int(input())
list = list(map(int, input().split(' ')))

ans = []
count = 0
for i in range(N):
    if i == 0:
        pass
    else:
        if list[i] <= list[i - 1]:
            count += 1
        else:
            ans.append(count)
            count = 0
ans.append(count)
print(max(ans))

Measured memory_bytes: 14252
N = int(input())
T = [int(input()) for _ in range(N)]

def Eucrid(a,b):
	if b == 0:
		return a
	return Eucrid(b,a%b)


ans = 1
for i in range(N):
	ans = (ans * T[i]) // Eucrid(ans, T[i])

print(ans)

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

int		main(void)
{
	ll n;
	ll k;
	cin >> n >> k;
	n %= k;
	while (n >= abs(n - k))
		n = abs(n - k);
	cout << n << endl;
	return (0);
}


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

#define int long long
#define itn int
#define For(i, a, b) for (int i = (a); i <= static_cast<int>(b); i++)
#define Forr(i, a, b) for (int i = (a); i >= static_cast<int>(b); i--)
#define rep(i, n) For(i, 0, n - 1)
#define repall(i, arr) for (auto& i : (arr))
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define dump(x) cerr << #x << " = " << (x) << '\n'
#define dump2(x, y) \
    cerr << #x << " = " << (x) << " " << #y << " = " << (y) << '\n'
#define SZ(x) ((int)(x).size())
#define bit(n) (1LL << (n))
constexpr int MOD = 1e9 + 7;

template <typename T>
using pq = priority_queue<T>;
template <typename T>
using pqr = priority_queue<T, vector<T>, greater<T>>;
const int INF = LLONG_MAX / 2;
using P = pair<int, int>;
using vec = vector<int>;
template <typename T>
using mat = vector<vector<T>>;

// clang-format off
template <typename T1, typename T2>
ostream& operator<<(ostream& stream, const pair<T1, T2>& p) { return stream << p.first << "," << p.second; }
template <typename T>
void print(const vector<T> vec) { rep (i, vec.size() - 1) cout << vec[i] << ' '; cout << vec[vec.size() - 1] << '\n'; }
template <typename Arg>
void print(const Arg arg) { cout << arg << '\n'; }
template <typename Head, typename... Args>
void print(const Head head, const Args... args) { cout << head << " "; print(args...); }
template <typename T, typename U>
void init(vector<T>& v, vector<U>& w) { rep (i, v.size()) cin >> v[i] >> w[i]; }
template <typename T>
void init(vector<T>& v) { rep (i, v.size()) cin >> v[i]; }
template <typename T>
T sum_(vector<T> vec, T init = 0) { return std::accumulate(all(vec), T(init)); }
template<typename T>
bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } return false; }
template<typename T>
bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } return false; }
template <typename T>
int index(const T& vec, const typename T::iterator it) { return distance(vec.begin(), it); }
template <typename T = int>
mat<T> mmat(int n, int m=0) { return mat<T>(n, vector<T>(m)); }
template <typename T = int>
vector<T> ivec(int n) { vector<T> v(n); init(v); return v; }
// clang-format on

void yn(bool tf) { print(tf ? "Yes" : "No"); }
void YN(bool tf) { print(tf ? "YES" : "NO"); }

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
// -------------------------------------------------------------------
// sort 1 2 3 4
// pqr 1 2 3 must impl >

signed main() {
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;

    int now = 0;
    int check = 0;
    rep (i, n - 1) {
        if (s[i] == s[i + 1])
            now++;
        else
            check++;
    }
    print(now + min(check, k * 2));

    return 0;
}


Measured memory_bytes: 512
import math

n, d = map(int, input().split())
x_list = []
count = 0

for i in range(n):
    x_list.append([int(i) for i in input().split()])

for i in range(len(x_list)-1):
    for j in range(i+1, len(x_list)):
        cal = 0
        for k in range(d):
            cal += (x_list[i][k] - x_list[j][k])**2
        if math.sqrt(cal) == int(math.sqrt(cal)):
            count += 1

print(count)

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

namespace Competition
{
    class Program
    {
        static void Main(string[] args)
        {
            var S = Console.ReadLine();
            var ok = true;
            for(var i = 0; i < S.Length; i++)
            {
                if ((i+1) % 2 == 0 && S[i] == 'R') ok = false;
                if ((i+1) % 2 == 1 && S[i] == 'L') ok = false;
            }
            if (ok) Console.WriteLine("Yes");
            else Console.WriteLine("No");
        }
    }
}


Measured memory_bytes: 13140
import java.util.Arrays;
import java.util.Scanner;

public class Main {
  static Scanner sc = new Scanner(System.in);

  public static void main(String[] args) {
    int N = sc.nextInt();
    long[] A = new long[3 * N];
    for (int i = 0; i < 3 * N; i++) {
      A[i] = sc.nextInt();
    }
    Arrays.sort(A);
    long ans = 0;
    for (int i = 1; i <= N; i++) {
      ans += A[3 * N - i * 2];
    }
    System.out.println(ans);
  }

}


Measured memory_bytes: 97876
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int N = scanner.nextInt();
    Set<Integer> set = new HashSet<>();
    for (int i = 0; i < N; i++) {
      set.add(scanner.nextInt());
    }
    if (set.size() == N) System.out.println("YES");
    else System.out.println("NO");
  }
}


Measured memory_bytes: 100840
n = int(input())
p_list = list(map(int, input().split()))

res_sum = 0

for i in range(n-2):
    res = True
    p, q, r = p_list[i], p_list[i+1], p_list[i+2]
    if q == min(p, q, r):
        res = False
    elif p == min(p, q, r) and r == min(p, q, r):
        res = False
    elif p == min(p, q, r):
        if q > r:
            res = False
    else:
        if q > p:
            res = False
    if res:
        res_sum += 1

print(res_sum)


Measured memory_bytes: 38384
s = input()
t = input()
list = []

for i in range(len(s)-len(t)+1):
    n=0
    U = s[i:i + len(t)]
    for j in range(len(t)):
        if U[j] != t[j]:
            n+=1
    list.append(n)
print(min(list))


Measured memory_bytes: 9004
#include<iostream>
#include<math.h>
#include<vector>
#include<algorithm>
#include<numeric>
#include<map>
#include<queue>
using namespace std;

int gcd(int a,int b){
    if(a==0)return b;
    if(b==0)return a;

    int M=max(a,b);
    int m=min(a,b);
    return gcd(m,M%m);
}

int main(){
    int N,X,D,x[100010],dx[100010],m=2*pow(10,9);cin>>N>>X;
    for(int i=0;i<N;i++){
        cin>>x[i];
        m=min(m,abs(X-x[i]));
    }
    if(N>1){
        sort(x,x+N);
        dx[0]=x[1]-x[0];
        D=dx[0];
        for(int i=1;i<N-1;i++){
            dx[i]=x[i+1]-x[i];
            D=gcd(dx[i],D);
        }
        D=gcd(D,m);
    }
    else D=m;
    cout<<D<<endl;
    return 0;

}

Measured memory_bytes: 640
import java.io.BufferedReader
import java.io.InputStreamReader
import java.io.PrintWriter

val br = BufferedReader(InputStreamReader(System.`in`))
val out = PrintWriter(System.out)

fun main() {
    br.use { out.use {
        solve()
        out.flush()
    } }
}

fun solve() {
    val (h, w, m) = readIntegerList()
    val hw = Array(m) {
        val (h, w) = readIntegerList()
        Pair(h, w)
    }

    val mapH = mutableMapOf<Int, Int>()
    for (a in hw) {
        mapH[a.first] = (mapH[a.first] ?: 0) + 1
    }
    val maxh = mapH.values.max()!!
    val hList = mutableListOf<Int>()
    for (a in mapH) {
        if (a.value == maxh) hList.add(a.key)
    }

    val mapW = mutableMapOf<Int, Int>()
    for (a in hw) {
        mapW[a.second] = (mapW[a.second] ?: 0) + 1
    }
    val maxw = mapW.values.max()!!
    val wList = mutableSetOf<Int>()
    for (a in mapW) {
        if (a.value == maxw) wList.add(a.key)
    }

    val hwMap = mutableMapOf<Int, HashSet<Int>>()
    for (t in hw) {
        if(hwMap[t.first] != null){
            hwMap[t.first]?.add(t.second)
        } else {
            hwMap[t.first] = HashSet()
            hwMap[t.first]?.add(t.second)
        }
    }

    for (h in hList) {
        val ww = hwMap[h]!!
        if (wList.subtract(ww).size > 0) {
            out.println(maxh + maxw)
            return
        }
    }
    out.println(maxh + maxw - 1)
}



fun readInteger() = Integer.parseInt(br.readLine())
fun readLong() = java.lang.Long.parseLong(br.readLine())
fun readStringList() = br.readLine()!!.split(' ')
fun readIntegerList() = readStringList().map(Integer::parseInt)
fun readLongList() = readStringList().map(java.lang.Long::parseLong)
fun readDoubleList() = readStringList().map(java.lang.Double::parseDouble)


Measured memory_bytes: 175404
#include <stdio.h>
int main(){
    int X, N,i,j,k=0,l=0;
    int p[100];
    scanf("%d %d", &X, &N);
    for (i = 0; i < N;i++){
        scanf("%d", &p[i]);
        }
    for (i = 0; 1;i++){
        for (j =k=l= 0; j < N;j++){
            if((X-i)==p[j]){
                k++;
            }
            if((X+i)==p[j]){
                l++;
            }
        }
        if(k==0){
            printf("%d", X - i);
            break;
        }else if (l==0){
            printf("%d", X + i);
            break;
        }
    }
    return 0;
}

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

#define MAXN (100010)
#define ll long long

int n;
std::pair<int, int> pile[MAXN];
ll ans[MAXN];

int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; ++ i){
		scanf("%d", &pile[i].first);
		pile[i].second = i;
	}
	std::sort(pile + 1, n + pile + 1);
	for(int i = n, ind = n; i; -- i){
		ind = std::min(ind, pile[i].second);
		ans[ind] += (1ll) * (pile[i].first - pile[i - 1].first) * (n - i + 1);
	}
	for(int i = 1; i <= n; ++ i){
		printf("%lld\n", ans[i]);
	}
	return 0;
}

Measured memory_bytes: 2688
#include <bits/stdc++.h>
#define repp(i,l,r)for(long long i=(l);i<(r);i++)
#define rep(i,n) for (long long i = 0; i < (n); ++i)
#define per(i,n) for (long long i = (n); i >= 0; --i)
const int INF = 1 << 30;//int max
const long long int MOD = 1000000007;
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
//ミョ(-ω- ?)
int main() {
    int n;
    cin >> n;
    if(n >= 30)cout << "Yes\n";
    else cout << "No\n";
    return 0;
}

Measured memory_bytes: 3648
#include <iostream>
using namespace std;
int main()
{
    int r, c, sum = 0;
    cin >> r >> c;
    int table[r+1][c+1];
    for (int i = 0; i < r; i++)
    {
        table[i][c] = 0;
        for (int j = 0; j < c; j++)
        {
            if (i == 0)
            {
                table[r][j] = 0;
            }
            cin >> table[i][j];
            table[i][c] += table[i][j];
            table[r][j] += table[i][j];
        }
        sum += table[i][c];
    }
    table[r][c] = sum;
    for (int i = 0; i <= r; i++)
    {
        for (int j = 0; j <= c; j++)
        {
            if (j) cout << " ";
            cout << table[i][j];
        }
        cout << endl;
    }
    return 0;
}


Measured memory_bytes: 3100
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

def main():
    a, b, c = i_map()

    if a == b:
        print(c)
    elif a ==c:
        print(b)
    else:
        print(a)

if __name__ == '__main__':
    main()


Measured memory_bytes: 77080
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#include <iostream>
#include <fstream>

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <bitset>
using namespace std;
using ll = long long;
constexpr ll INF = 1010000000000000017LL;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define all(v) v.begin(), v.end()

ll GCD(ll a, ll b) { if(b==0) return a; else return GCD(b, a%b); }
ll LCM(ll a, ll b) { return a/GCD(a,b)*b; }

class BDifferentDistribution {
public:
	void solve(std::istream& in, std::ostream& out) {
        ll n;in>>n;
        pair<ll,ll> ma;
        ma = {-1,-1};
        rep(i,n){
            ll a,b;in>>a>>b;
            ma = max(ma,{a,b});
        }
        out<<ma.first+ma.second<<endl;
	}
};


int main() {
	BDifferentDistribution solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <stdio.h>
#include <stdlib.h>
#include <cmath>

using namespace std;

int main(){
  
  int d;

  cin >> d;

  if(d == 22)
    cout << "Christmas Eve Eve Eve" <<endl;
  else if(d == 25)
    cout << "Christmas" << endl;
  else if( d == 24)
    cout << "Christmas Eve" << endl;
  else
    cout << "Christmas Eve Eve" << endl;
    

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = std::int_fast64_t;
using std::cout;
using std::cerr;
using std::endl;
using std::cin;

template<typename T>
std::vector<T> make_v(size_t a){return std::vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

int main() {
	int h, w; scanf("%d%d", &h, &w);
	std::vector<int> l(h), r(h);
	for(int i = 0; i < h; i++) {
		scanf("%d%d", &l[i], &r[i]);
		l[i]--;
	}

	using P = std::tuple<int, int, int>; // (start, offset, id);
	std::set<P> st({P{w, 1 << 30, w}});
	for(int i = 0; i < w; i++) st.insert(P{i, 0, i});

	using T = std::pair<int, int>; // (cost, id)
	std::vector<int> used(w);
	std::priority_queue<T, std::vector<T>, std::greater<T>> qu;
	for(int i = 0; i < w; i++) qu.push({0, i});


	// ans = (i + 1) + cost 
	for(int i = 0; i < h; i++) {
		auto it = st.lower_bound(P{l[i], -1, 0});
		std::vector<P> nxt;
		while(it != st.end() and std::get<0>(*it) < r[i]) {
			auto x = it;
			auto y = ++it;
			it--;

			int L = std::get<0>(*it), R = std::get<0>(*y);
			auto [start, offset, id] = *it;
			if(r[i] < R) {
				nxt.push_back(P{r[i], offset + (r[i] - L), id});
				qu.push({offset + (r[i] - L), id});
				used[id] = offset + (r[i] - L);
			} else {
				used[id] = 1 << 30;
			}

			it = st.erase(it);
		}
		for(auto v: nxt) st.insert(v);

		while(!qu.empty() and used[qu.top().second] != qu.top().first) qu.pop();
		if(qu.empty()) printf("-1\n");
		else printf("%d\n", (i + 1) + qu.top().first);
	}
	
	return 0;
}


Measured memory_bytes: 20224
def max(a,b); a > b ? a : b; end

class PQ
  attr_accessor :arr
  def initialize(arr)
    @arr = arr.sort!.reverse!
  end

  def at(i); @arr[i-1]; end
  def swap(i,j); @arr[i-1], @arr[j-1] = @arr[j-1], @arr[i-1]; end
  def size; @arr.size; end

  def half
    @arr[0] /= 2
    i = 1
    until i * 2 > size
      j,k = i*2,i*2+1
      if at(k).nil? || at(k) <= at(j)
        if at(i) <= at(j)
          swap(i,j)
          i = j
        else
          break
        end
      else
        if at(i) <= at(k)
          swap(i,k)
          i = k
        else
          break
        end
      end
    end
  end
end

N,M = gets.split.map &:to_i
A = gets.split.map &:to_i

Q = PQ.new(A)
M.times do
    Q.half
end

puts Q.arr.inject(:+)


Measured memory_bytes: 11136
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
ch, cw = ch-1, cw-1
dh, dw = map(int, input().split())
dh, dw = dh-1, dw-1
s = [list(input()) for _ in range(h)]

def bfs(sy, sx):
    que = deque([])
    que.append([sy, sx])

    while que:
        y, x = que.popleft()
        dx = [0,1,0,-1]
        dy = [1,0,-1,0]
        for i in range(4):
            ny = y+dy[i]
            nx = x+dx[i]
            if ny < 0 or ny >= h or nx < 0 or nx >= w: continue
            if s[ny][nx] == '#': continue
            if seen[ny][nx] != -1: continue
            
            seen[ny][nx] = cnt[0]
            que.append([ny, nx])
            wp.append([ny, nx])

dq = deque([])
dq.append([ch, cw])
seen = [[-1]*w for _ in range(h)]
seen[ch][cw] = 0
cnt = [0]
wp = deque([])
ok = False

while dq:
    while dq:
        y, x = dq.popleft()
        bfs(y, x)
        wp.append([y, x])    

    ok = False
    while wp:
        y, x = wp.popleft()
        for dy in range(-2, 3):
            for dx in range(-2, 3):
                if dy == 0 and dx == 0: continue
                ny = y+dy
                nx = x+dx
                if ny < 0 or ny >= h or nx < 0 or nx >= w: continue
                if s[ny][nx] == '#': continue
                if seen[ny][nx] == -1:
                    ok = True
                    seen[ny][nx] = (cnt[0]+1)
                    dq.append([ny, nx])
    if ok:
        cnt[0] += 1

if seen[dh][dw] >= 0:
    print(seen[dh][dw])
else:
    print(-1)

Measured memory_bytes: 143408
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <stdio.h>

using namespace std;

//typedefリスト
typedef vector<long long int> vint;
typedef vector<string> vstr;
typedef long long int llint;



int main(void) {
	int num,n;
	int ans = 0;
	string N;
	cin >> N;
	n=stoi(N);
	num = N.length();
	for (int i = 0; i < num; i++){
		ans += N[i] - '0';
	}
	if (n%ans == 0)cout << "Yes" << endl;
	else cout << "No" << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <math.h>

int main(void){
    int n;
    scanf("%d",&n);
    int max=0,l,sum=0;
    for (int i=0; i<n; i++){
        scanf("%d",&l);
        if (max<l){
            max=l;
        }
        sum+=l;
    }
    if (sum-max>max){
        printf("Yes\n");
    } else {
        printf("No\n");
    }
    return 0 ;
}

Measured memory_bytes: 128
N=int(input())

for a in range(1,3501):
    for b in range(1,3501):
        if (4*a*b-N*a-N*b)>0:
            c=N*a*b/(4*a*b-N*a-N*b)
            if c==int(c):
                if 4*a*b*c==N*(a*b+b*c+c*a):
                    print(a,b,int(c))
                    exit()

Measured memory_bytes: 40796
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#pragma comment(linker, "/STACK:102400000,102400000")

using namespace std;

#define For(i,forN) for(int i=0;i<(forN);i++)
#define Fori(i,si,forN) for(int i=si;i<(forN);i++)

#define pb push_back
#define sf scanf
#define pf printf

const int Maxn=110000;
int dp[Maxn][9][9][2];

bool check(int sta1,int sta2)
{
    return sta1%3 <= sta2%3;
}
char str[Maxn];
int n;

int main()
{
    while(~sf("%s",str) && str[0]!='#')
    {
        for(n=0;str[n];n++)
        str[n]--;
        Fori(z,1,n+1){
            For(i,9){
                For(j,9)
                dp[z][i][j][0]=dp[z][i][j][1]=Maxn;
            }
        }
        For(i,n){
            For(j,9)    For(k,9){
                int sta=str[i]-'0';
                //0
                if(check(sta,k))
                {
                    dp[i+1][sta][k][0]=min( dp[i+1][sta][k][0],min(dp[i][j][k][0]+1, dp[i][j][k][1]));
                }
                //1
                if(check(j,sta))
                dp[i+1][j][sta][1]=min( dp[i+1][j][sta][1],min(dp[i][j][k][1]+1, dp[i][j][k][0]));
            }
        }
        int res=Maxn;
        For(i,9)    For(j,9) For(z,2){
            res=min(dp[n][i][j][z],res);
        }
        pf("%d\n",res);
    }
}

Measured memory_bytes: 64608
//#include <bits/stdc++.h>
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
//#include "boost/multiprecision/cpp_int.hpp"
//typedef boost::multiprecision::cpp_int ll;
typedef long double dd;
//#define i_7 (ll)(1E9+7)
//#define i_7 998244353
//#define i_5 i_7-2

ll i_7=1E6+3;
ll i_5=i_7-2;

ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
typedef pair<dd,dd> d_d;
ll inf=(ll)1E16;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define fi first
#define se second
#define endl "\n"
///////////////////////////

ll po(ll i,ll p){
    if(p==0)return 1;
    else{
        i=mod(i);
        if(p==1)return i;
        if(p%2==0)return po(mod(i*i),p/2);
        return mod(i*po(i,p-1));
    }
}
ll bunbo(ll n){
    return po(n,i_5);
}


#define N 1000003
ll kai[N];
ll kai2[N];
ll bun[N];
void calc(){
    kai[0]=1;
    kai2[0]=1;
    rep(i,1,N-1){
        bun[i]=bunbo(i);
    }
    rep(i,1,N-1){
        kai[i]=mod(kai[i-1]*i);
        kai2[i]=mod(kai2[i-1]*bun[i]);
    }
}


bool ansp(){
    ll x,d,n;cin>>x>>d>>n;
    if(x==0){
        cout<<0<<endl;return 0;
    }
    if(d==0){
        cout<<mod(po(x,n))<<endl;return 0;
    }
    ll y=mod(x*bun[d]);
    ll z=y+n-1;
    if(z>=i_7){
        cout<<0<<endl;return 0;
    }
    ll ans=kai[z];
    if(y-1>=1)ans=mod(ans*kai2[y-1]);
    ans=mod(ans*po(d,n));
    cout<<mod(ans)<<endl;
    return 0;
}
int main(){fastio
    calc();
    ll que;cin>>que;
    while(que--){
        ansp();
    }
    return 0;
}


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

// #define int long long
#define rep(i, n) for (long long i = (long long)(0); i < (long long)(n); ++i)
#define reps(i, n) for (long long i = (long long)(1); i <= (long long)(n); ++i)
#define rrep(i, n) for (long long i = ((long long)(n)-1); i >= 0; i--)
#define rreps(i, n) for (long long i = ((long long)(n)); i > 0; i--)
#define irep(i, m, n) for (long long i = (long long)(m); i < (long long)(n); ++i)
#define ireps(i, m, n) for (long long i = (long long)(m); i <= (long long)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) long long(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;
using vtp = vector<tuple<ll,ll,ll>>;
using vb = vector<bool>;

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

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


signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  ll n,k; cin>>n>>k;
  vll a(n);
  rep(i,n) cin>>a[i];
  vsort(a);
  ll ans=LINF;
  rep(i,n-k+1){
    chmin(ans,a[i+k-1]-a[i]);
  }
  cout<<ans<<endl;
 }

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define isuck ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(0);
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);}

int main()
{
    isuck;
    string s;
    cin>>s;
    sort(s.begin(),s.end());
    if(s[0]==s[1] && s[2]==s[3] && s[1]!=s[2] && s.size()==4)
    {
        cout<<"Yes";
    }
    else cout<<"No";
}


Measured memory_bytes: 256
/*suri_kumkaran*/

#include <bits/stdc++.h>

using namespace std;

#define UB upper_bound
#define LB lower_bound
#define BS binary_search
#define MP make_pair
#define EB emplace_back
#define endl "\n"
#define PI 3.1415926535897932384626433832795
#define MOD 1000000007
#define F first
#define S second
#define ALL(a) (a).begin(),(a).end()
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define int long long

typedef long long int64;
typedef vector<int> VI64;
typedef vector<pair<int,int>> VII64;
typedef vector<string> VS;
typedef vector<vector<int>> VVI;

int32_t main()
{
	IOS;
	int T=1;
	//cin>>T;
	while(T--)
	{
		int n,i;
		cin>>n;
		int a[n+1];
		int dp[n+1][2];
		for(i=1;i<=n;i++)
		{
			cin>>a[i];
		}		
		dp[2][0]=a[1]+a[2];
		dp[2][1]=-(dp[2][0]);
		for(i=3;i<=n;i++)
		{
			dp[i][0]=max(dp[i-1][1],dp[i-1][0])+a[i];
			dp[i][1]=max(dp[i-1][1]+2*a[i-1],dp[i-1][0]-2*a[i-1])-a[i];
		}
		cout<<max(dp[n][0],dp[n][1])<<endl;
	}

	return 0;
}

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

int main(){
    int a,b,c;
    cin >> a >> b >> c;
    int sum = a + b + c;
    int x = max(a,max(b,c));
    if(x * 3 % 2 == sum % 2){
        cout << (x * 3 - sum) / 2 << endl;
    }else{
        cout << ((x+1) * 3 - sum) / 2 << endl; 
    }
    return 0;
}

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

int main() {
  string w; cin >> w;
  bool beauty = true;
  int cnt = 0;
  
  for (int i=0; i<w.size(); i++){
    for (int j=0; j<w.size(); j++){
      if (w.at(i) == w.at(j)){
        cnt++;
      }
    }
    if (cnt%2){
      beauty = false;
      break;
    }
    cnt = 0;
  }
  
  if (beauty) cout <<"Yes";
  else        cout <<"No";
  cout <<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;
#define PI 3.141592653589793

int main(){
  int P, Q, R; cin >> P >> Q >> R;
  int tmp = max({P, Q, R});
  int ans = P + Q + R - tmp;
  cout << ans << endl;
}

Measured memory_bytes: 256
n,m=gets.split
n=n.to_i
m=m.to_i

arr=Array.new(n,0)

m.times{
    
    a,b=gets.split
    a=a.to_i
    b=b.to_i
    arr[a-1]+=1
    arr[b-1]+=1
}

i=0
n.times{
   if arr[i]%2==1
       puts "NO"
       exit
   else
       i+=1
   end
    
}

puts "YES"


Measured memory_bytes: 2684
#include <bits/stdc++.h>
using namespace std;
int N;
string s;
int main()
{
	cin >> N;
	cin >> s;
	for (int i = 0; i < s.length(); i++)
	{
		printf("%c" , (s[i] - 'A' + N) % 26 + 'A');
	}
}

Measured memory_bytes: 256
fn qsort<T: std::cmp::PartialOrd + Copy + std::fmt::Debug>(a: &mut Vec<T>, l: usize, r: usize) {
    if l + 1 >= r {
        return;
    }
    // let p = (r + l) / 2;
    let p = r - 1;
    let e = a[p];
    a.swap(p, r - 1);
    let mut b = l;
    for i in l..r - 1 {
        if a[i] <= e {
            a.swap(i, b);
            b += 1;
        }
    }
    a.swap(b, r - 1);
    qsort(a, l, b);
    qsort(a, b + 1, r);
}

fn msort<T: std::cmp::PartialOrd + Copy + std::fmt::Debug>(a: &mut Vec<T>, l: usize, r: usize) {
    if l + 1 >= r {
        return;
    }
    let m = (l + r) / 2;
    msort(a, l, m);
    msort(a, m, r);
    // merge
    let mut b0 = l;
    let mut b1 = m;
    let mut res = vec![];
    while !(b0 == m && b1 == r) {
        if b0 == m {
            res.push(a[b1]);
            b1 += 1;
        } else if b1 == r {
            res.push(a[b0]);
            b0 += 1;
        } else {
            if a[b0] <= a[b1] {
                res.push(a[b0]);
                b0 += 1;
            } else {
                res.push(a[b1]);
                b1 += 1;
            }
        }
    }
    for i in l..r {
        a[i] = res[i - l];
    }
}

#[derive(Eq, PartialEq, Clone, Copy, Debug)]
struct Card {
    c: char,
    i: usize,
}
impl std::cmp::PartialOrd for Card {
    fn partial_cmp(&self, rhs: &Card) -> Option<std::cmp::Ordering> {
        self.i.partial_cmp(&rhs.i)
    }
}
impl std::cmp::Ord for Card {
    fn cmp(&self, rhs: &Card) -> std::cmp::Ordering {
        self.i.cmp(&rhs.i)
    }
}

fn solve() {
    let n: usize = read();
    let mut v = vec![];
    let mut vc = vec![];
    for _ in 0..n {
        let mut s: String = read();
        let c = s.pop().expect("u");
        let i = read();
        v.push(Card { c, i });
        vc.push(Card { c, i });
    }
    qsort(&mut v, 0, n);
    msort(&mut vc, 0, n);
    let mut st = true;
    for i in 0..n {
        if v[i] != vc[i] {
            println!("Not stable");
            st = false;
            break;
        }
    }
    if st {
        println!("Stable");
    }
    for e in v {
        println!("{} {}", e.c, e.i);
    }
}

fn main() {
    let stack_size = 104_857_600;
    let thd = std::thread::Builder::new().stack_size(stack_size);
    thd.spawn(|| solve()).unwrap().join().unwrap();
}

// =========
#[allow(unused_imports)]
use std::collections::{BinaryHeap, HashMap, HashSet};
#[allow(unused_imports)]
use std::process::exit;

#[allow(dead_code)]
const MOD: usize = 1000000007;

fn read<T: std::str::FromStr>() -> T {
    use std::io::Read;
    let stdin = std::io::stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

// =========



Measured memory_bytes: 16096
from collections import deque
n,m = map(int,input().split())
l = [[] for i in range(n+1)]
rl = [[-1 for i in range(n+1)] for i in range(3)]
for i in range(m):
    u,v = map(int,input().split())
    l[u].append(v)
s,t = map(int,input().split())
d = deque()
ans = -1
d.append([s,0])
rl[0][s] = 0
while len(d):
    now,count = d.popleft()
    for i in l[now]:
        if i == t and count % 3 == 2:
            ans = (count + 1)//3
            break
        else:
            if rl[(count%3 + 1)%3][i] == -1:
                d.append([i,count+1])
                rl[(count%3+1)%3][i] = count+1
    if ans >= 0:
        break
print(ans)

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

int gcd(long long int m,long long int n ){
  if(0 == m || 0 == n ) return 0;
  while(m != n){
	if (m > n) m = m - n;
	else n = n - m;
	}
  return m;
}

int main() {

  // https://beta.atcoder.jp/contests/agc028/submissions/3401275

  long long int N,M;
  string S;
  string T;
  cin >> N >> M >> S >> T;
  long long int g = gcd(N,M);
  long long int a=N/g,b=M/g;
  bool t=true;
  for(long long int i=0;i<g;i++){
    if(S[a*i] != T[b*i]){
      t=false;
      cout << -1 << endl;
      return 0;
    }
  }
  if(t) cout << N*M/g << endl;
  return 0;
}


Measured memory_bytes: 512
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
const ll inf = 1LL << 50;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
///////////////////////////////////////

int main() {
	ll H, W;
	cin >> H >> W;
	ll ans = min(H, W);
	if (H % 3 == 0 || W % 3 == 0) {
		cout << 0 << endl;
		return 0;
	}
	for (int k = 0; k < 2; ++k) {
		for (int i = 0; i < 2; ++i) {
			ll h;
			if (i == 0)h = H / 3;
			else h = H / 3 + 1;
			ll s1 = W * h;
			ll w2 = W / 2;
			ll s2 = (H - h)*w2;
			ll s3 = (H - h)*(W - w2);
			ll smax = max(s1, max(s2, s3));
			ll smin = min(s1, min(s2, s3));
			ans = min(ans, (smax - smin));
		}
		swap(H, W);
	}
	
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner((System.in));
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int d = sc.nextInt();
        
        if ((a + b) < (c + d)) {
            System.out.println("Right");
        } else if ((a + b) > (c + d)) {
            System.out.println("Left");
        } else {
            System.out.println("Balanced");
        }


		sc.close();
	}
}


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

using namespace std;

mt19937 engine(0);

template<typename T>
void quick_sort(vector<T>& a, int l, int r) {
    if (l >= r) return;
    T pivot = a[uniform_int_distribution<>(l, r)(engine)];
    int i = l, j = r;
    while (true) {
        while (a[i] < pivot) ++i;
        while (a[j] > pivot) --j;
        if (i >= j) break;
        swap(a[i], a[j]);
        ++i, --j;
    }
    quick_sort(a, l, i-1);
    quick_sort(a, j+1, r);
}


int main() {

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

    quick_sort(a, 1, n);

    int alice = 0, bob = 0;
    for (int i = 1; i <= n; ++i) {
        (i & 1 ? alice : bob) += a[n+1-i];
    }

    cout << alice - bob << endl;

    return 0;
}


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

using namespace std;

#define INF 1000000007
#define LINF (1LL << 62)
#define PI 3.14159265358979

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

inline i64 mod(i64 a, i64 m) { return (a % m + m) % m; }

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }



int a,b,c;
void solve(){
	cin >> a >> b >> c;
	
	
	cout << b/c - a/c + !(a%c) << endl;
}

int main(){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}
	
	return 0;
}

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

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

  for (int i = 0; i < (2 * a - 2); ++i) {
    cout << (b - a + 1 + i) << " ";
  }
  cout << (b + a - 1) << endl;
}


Measured memory_bytes: 256
n=int(input())
h=list(map(int,input().split()))
a=0
b=0
i=0
while i<n-1:
  if h[i]>=h[i+1]:
    a=a+1
    if a>b:
      b=a
  else:
    a=0
  i=i+1
print(b)

Measured memory_bytes: 14228
#include<stdio.h>
int main(void){
	char NextAlphabet[27] = {'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'};
	char Alpha;
	scanf("%c", &Alpha);
	for(int i = 0; i < 27; i++){
		if(NextAlphabet[i] == Alpha){
			printf("%c", NextAlphabet[i + 1]);
		}
	}
	return 0;
}

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

int main() {
  int N;
  cin >> N;
  string S;
  cin >> S;
  vector<int> r(N + 1), g(N + 1), b(N + 1);
  for (int i = 1; i < N + 1; i++) {
    r[i] += r[i - 1] + (S[i - 1] == 'R');
    g[i] += g[i - 1] + (S[i - 1] == 'G');
    b[i] += b[i - 1] + (S[i - 1] == 'B');
  }

  ll ans = 0;
  for (int i = 0; i < N; i++) {
    for (int j = i + 1; j < N; j++) {
      if (S[i] == S[j]) continue;
      if ((S[i] == 'R' && S[j] == 'G') || (S[j] == 'R' && S[i] == 'G')) {
        ans += b[N] - b[j + 1];
        if (2 * j - i < N && S[2 * j - i] == 'B') ans--;
      }
      if ((S[i] == 'G' && S[j] == 'B') || (S[j] == 'G' && S[i] == 'B')) {
        ans += r[N] - r[j + 1];
        if (2 * j - i < N && S[2 * j - i] == 'R') ans--;
      }
      if ((S[i] == 'B' && S[j] == 'R') || (S[j] == 'B' && S[i] == 'R')) {
        ans += g[N] - g[j + 1];
        if (2 * j - i < N && S[2 * j - i] == 'G') ans--;
      }
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3648
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll N, Q, L, R;
ll A[200500];
ll q[205000], x[200500], s[200050], t[200050];

ll f(ll now) {
    for(int i = 1; i <= Q; i++) {
        if(q[i] == 1) {
            if(now >= x[i]) {
                now = t[i] * (now + s[i]);
            }
        } else {
            if(now <= x[i]) {
                now = (now - s[i]) / t[i];
            }
        }
    }
    return now;
}

int main() {
    cin >> N >> Q >> L >> R;
    for(int i = 1; i <= N; i++) cin >> A[i];
    for(int i = 1; i <= Q; i++) {
        cin >> q[i] >> x[i] >> s[i] >> t[i];
    }
    ll overok = 1e9+1;
    ll overng = -1e9-1;
    ll underok = -1e9-1;
    ll underng = 1e9+1;
    while(overok - overng > 1) {
        ll mid = (overok + overng) / 2;
        ll tmp = f(mid);
        if(tmp > R) overok = mid;
        else overng = mid;
    }
    while(underng - underok > 1) {
        ll mid = (underok + underng) / 2;
        ll tmp = f(mid);
        if(tmp < L) underok = mid;
        else underng = mid;
    }
    //cerr << overok << " " << underok << endl;
//    cerr << f(overok) << " " << f(overng) << endl;
//    cerr << f(underok) << " " << f(underng) << endl;
    ll ans = 0;
    for(int i = 1; i <= N; i++) {
        if(A[i] < overok && A[i] > underok) {
            ans++;
            //cerr << i << endl;
        }
        //cerr << f(A[i]) << endl;
    }
    cout << ans << endl;
}


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

int dp[110][110];

int main() {
  int n;
  cin >> n;
  vector<int> r(n), c(n);
  for (int i = 0; i < n; i++) {
    cin >> r[i] >> c[i];
  }
  for (int i = 0; i < 110; i++) {
    for (int j = 0; j < 110; j++) {
      if (i == j) {
        dp[i][j] = 0;
      }
      else {
        dp[i][j] = 100000000;
      }
    }
  }
  for (int l = 2; l <= n; l++) {
    for (int i = 1; i <= n - l + 1; i++) {
      int j = i + l - 1;
      for (int k = i; k <= j - 1; k++) {
        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + r[i - 1]*c[k - 1]*c[j - 1]);
      }
    }
  }
  cout << dp[1][n] << endl;
  return 0;
}


Measured memory_bytes: 3140
/**
 * Created by Sakib on 06/11/2018.
 */
#include <bits/stdc++.h>
using namespace std;

#define fast_io ios_base::sync_with_stdio(false); cin.tie(NULL);
#define debug(args...) { dbg,args; cerr<<"\n"; }
struct debugger{
template<typename T>debugger& operator,(const T& v){cerr<<v<<" ";return *this;}}dbg;

#define Fix( x ) setprecision( x ) << fixed
#define mem( a , x ) memset( a , x , sizeof( a ) )
#define bug( a , b ) cerr<< #a <<" = "<<a<<" , "<< #b <<" = "<<b<<"\n";
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define FOR( i , a , b ) for( int i = a; i <= b; i++ )
#define ROF( i , a , b ) for( int i = a; i >= b; i-- )
#define sz( V ) (int)V.size( )
#define all( V ) V.begin( ),V.end( )
#define Found( S , val ) S.find( val ) != S.end( )
#define Unique( V ) sort( all( V ) ), V.erase( unique( all( V ) ), V.end() )
typedef pair < int , int > ii;
typedef pair < int , ii > iii;
typedef long long int LL;
typedef unsigned long long uLL;
const int inf = (int)1e9;
const LL INF = (LL)1e18;
const int N = 100005;
const int mod = 1000000007;
const double eps = 1e-8;
const double pi = acos( -1.0 );

vector <LL> yen;
LL n;
LL dp[ 15 ][ 10*N ];
int len;

void calc( ) {
    yen.pb( 1 );
    for( LL i = 6; i <= 100000; i *= 6 ) yen.pb( i );
    for( LL i = 9; i <= 100000; i *= 9 ) yen.pb( i );
    len = sz(yen);
    //cout << sz(yen) << endl;
    //for( auto x : yen ) cout << x << " ";
}
LL go( int pos , LL rem ) {
    //cout <<"rem : " << rem << endl;
    if( pos >= len ) return ( rem == 0 ? 0 : INF );
    if( rem == 0 ) return 0;
    if( rem < 0 ) return INF;
    if( dp[pos][rem] != -1 ) return dp[pos][rem];
    LL op1 = INF , op2 = INF;
    op1 = go( pos+1 , rem );
    op2 = go( pos , rem-yen[pos] )+1 ;
    //bug( op1 , op2 );
    return dp[pos][rem] = min( op1 , op2 );
}
int main( int argc, char const *argv[] ) {
    fast_io;
    calc( );
    cin >> n;
    mem( dp , -1 );
    cout << go( 0 , n ) << endl;
    return 0;
}











Measured memory_bytes: 122112
#include <bits/stdc++.h>
using intl = long long;
using ld = long double;
using namespace std;
#define rep(i, n) for(intl i = 0; i < (intl)(n); i++)
#define repd(i, n) for(intl i = (intl)(n); i >= 0; i--)
#define repi(i, a, b) for(intl i = (intl)(a); i < (intl)(b); i++)
#define repid(i, a, b) for(intl i = (intl)(a); i >= (intl)(b); i--)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define all(x) (x).begin,(x).end()
#define m0(x) memset(x,0,sizeof(x))
#define m1(x) memset(x,1,sizeof(x))
#define fill(x,y) memset(x,y,sizeof(x))
#define alength(a) (sizeof(a) / sizeof(a[0]))
#define cin(i, a) rep(i, alength(a))cin >> a[i]
#define ccin(i, j, a) rep(i, alength(a))rep(j, alength(a[i]))cin >> a[i][j]
#define debug(x) cout << #x << ":" << x << endl
#define rdebug(i,x) rep(i, alength(x))cout << #x << "[" << i << "]:" << x[i] << endl
#define sqrt sqrtl
#define int intl
#define itn intl
#define double ld
#define pb push_back
#define mp make_pair
const intl INF = 1e9;
const intl MOD = 1e9+7;
const ld eps = 1.0e-14;//-9
void fp(bool f){cout << (f ? "Yes" : "No") << endl;}
void fp(bool f, string s, string t){cout << (f ? s : t) << endl;}
intl kai(intl k){
    intl a = 1;
    for(int i = 2; i <= k; i++){
        a *= i;
    }
    return a;
}
intl gcd(intl a, intl b){
    if(!b)return a;
    return gcd(b, a % b);
}
intl digit10(intl a){
    if(!a)return 1;
    intl b = 0;
    while(a){
        a /= 10;
        b++;
    }
    return b;
}
signed main(){
    cout << fixed << setprecision(10);
    intl n;
    cin >> n;
    intl a[n];
    cin(i,a);
    intl end = alength(a);
    intl ans = -1;
    intl cnt = 0;
    intl b = 1;
    while(end != cnt){
        b = a[b - 1];
        cnt++;
        if(b == 2){
            ans = cnt;
            break;
        }
    }
    cout << ans << endl;
    return 0;
}

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

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


    long sum = 0; long left = 0;
    long res = 99999999999999999L;
    long tmp;
    for(int i=0; i<N; i++) sum += a[i];
    for(int i=0; i<N-1; i++) {
        sum -= a[i];
        left += a[i];
        tmp = abs(left-sum);
        if(tmp < res) res = tmp;
    }

    cout << res << endl;
}


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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << fixed << setprecision(10);
  cerr << fixed << setprecision(10);

  string s;
  cin >> s;

  int ss = s.size();
  int frt = 0, bck = 0;
  for (int i = 0; i < ss; ++i) {
    if (s[i] == 'A') {
      frt = i;
      break;
    }
  }
  for (int i = ss; i > frt; --i) {
    if (s[i] == 'Z') {
      bck = i;
      break;
    }
  }

  cout << bck - frt + 1 << '\n';

  return 0;
}


Measured memory_bytes: 3780
#include<iostream>
#include<vector>
#include<cmath>
#include<string>
#include<algorithm>
#include<map>
#include<utility>
#include<cstdio>
#include<bits/stdc++.h>

using namespace std;
using ll = long long;
const long long INF = 1LL<<60;

typedef pair<ll,ll> Pair;

int main(){

ll A,B,C,K;
ll ans=0;

cin >> A >> B >> C >> K;

if(K - A >= 0){
    ans += A;
    K -= A;
}
else{
    ans+=K;
    K = 0;
}

if(K - B >= 0)    K -= B;
else K = 0;


if(K - C >= 0){
    ans -= C;
    K -= C;
} 
else{
    ans-=K;
    K = 0;
}

cout << ans << endl;

return 0;

}

Measured memory_bytes: 3648
#include<iostream>
#include<string>
#include<vector>
#include<iomanip>
#include<algorithm>
#include<queue>
#include<stack>
#include<list>
#include<map>
#include<deque>
#include<math.h>
using namespace std;
#define ll long long
int main(){
    ll A,P;
    cin >> A >> P;
    cout << (3*A+P)/2;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long a,b,x;
	cin>>a>>b;
	x=a-1;
	if(a<=b)
	cout<<a<<endl;
	else
	{
		if(a>b)
		cout<<x<<endl;
		
	}
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int check(int *a, int x)
{
	int i = 0;
	while (a[i])
	{
		if (x == a[i])
			return 1;
		i++;
	}
	return (0);
}

int		main(void)
{
	int n,m,x;
	scanf("%d%d%d", &n, &m, &x);
	int a[m];
	int i = 0;
	int count1 = 0;
	int count2 = 0;
	while (i < m)
		scanf("%d", &a[i++]);
	i = x;
	int zero = a[0] - 1;
	if (x <= n)
	{
		while (i < n)
		{
			if (check(a, i))
				count1++;
			i++;
		}
	}
	else
	{
		while (i > n)
		{
			if (check(a, i))
				count1++;
			i--;
		}
	}
	i = x;
	if (i < zero)
	{
		while (i < zero)
		{
			if (check(a, i))
				count2++;
			i++;
		}
	}
	else
	{
		while (i > zero)
		{
			if (check(a, i))
				count2++;
			i--;
		}
	}
	if (count1 < count2)
		printf("%d\n", count1);
	else
		printf("%d\n", count2);
	return (0);
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const int INF=1001001001;
 
int main() {
  int h,a;
  cin>>h>>a;
  int ans=h/a;
  if(h%a!=0) ans++;
  cout<<ans<<endl;
 
 
 
}

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

int int_sort( const void * a , const void * b ) {
  if( *(int*)a < *(int*)b ) {
    return -1;
  } else if( *(int*)a == *(int*)b ) {
    return 0;
  }
  return 1;
}

int main(void) {
  int N, K;
  scanf("%d %d", &N, &K);

  int H[100000];
  for(int i = 0; i < N; i++) {
    scanf("%d", &H[i]);
  }
  qsort((void*)H, N, sizeof(H[0]), int_sort);

  int min = H[K-1] - H[0];
  for(int i = K; i < N; i++) {
    int tmp = H[i] - H[i - K + 1];
    if(tmp < min)
      min = tmp;
  }
  printf("%d\n", min);
  
  return 0;
}


Measured memory_bytes: 892
// 2012/11/09 Tazoe

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

const int INF = 1000000000;

int main()
{
	while(true){
		int n, m;
		cin >> n >> m;

		if(n==0 && m==0)
			break;

		int C[100][100];
		int T[100][100];
		for(int i=0; i<m; i++){
			for(int j=0; j<m; j++){
				if(i==j){
					C[i][j] = T[i][j] = 0;
				}
				else{
					C[i][j] = T[i][j] = INF;
				}
			}
		}

		for(int i=0; i<n; i++){
			int a, b, c, t;
			cin >> a >> b >> c >> t;

			C[a-1][b-1] = C[b-1][a-1] = c;
			T[a-1][b-1] = T[b-1][a-1] = t;
		}

		for(int h=0; h<m; h++){
			for(int i=0; i<m; i++){
				for(int j=0; j<m; j++){
					C[i][j] = min(C[i][j], C[i][h]+C[h][j]);
					T[i][j] = min(T[i][j], T[i][h]+T[h][j]);
				}
			}
		}

		int k;
		cin >> k;

		for(int i=0; i<k; i++){
			int p, q, r;
			cin >> p >> q >> r;

			if(r==0){
				cout << C[p-1][q-1] << endl;
			}
			else{
				cout << T[p-1][q-1] << endl;
			}
		}
	}

	return 0;
}



Measured memory_bytes: 3156