akhauriyash/Code-Regression huggingface dataset:
package main

import (
	"bufio"
	"fmt"
	"io"
	"math"
	"math/big"
	"os"
)

var scan *bufio.Scanner
var reader io.Reader
var writer io.Writer

func init() {
	scan = bufio.NewScanner(os.Stdin)
	reader = os.Stdin
	writer = os.Stdout
	scan.Split(bufio.ScanWords)
}

func main() {
	solve()
}

func solve() {
	var a, b int
	fmt.Scan(&a, &b)
	g := gcd(a, b)
	res := divR(g)
	fmt.Print(res)
}

func divR(x int) int {
	res := 0
	di := div(x)
	for _, i := range di {
		tmp := div(i)
		if len(tmp) == 1 || len(tmp) == 2 {
			res++
		}
	}
	return res
}

func div(x int) []int {
	var di []int
	for i := 1; i*i <= x; i++ {
		if x%i == 0 {
			di = append(di, i)
			if i*i != x {
				di = append(di, x/i)
			}
		}
	}
	return di
}

func gcd(x, y int) int {
	var m, n int
	if x > y {
		m = x
		n = y
	} else {
		m = y
		n = x
	}
	for m%n != 0 {
		var tmp int
		tmp = m % n
		m = n
		n = tmp
	}
	return n
}

func cin(a ...interface{}) {
	for i := 0; i < len(a); i++ {
		doScan(a[i])
	}
	return
}
func doScan(a interface{}) {
	switch a.(type) {
	case *[]int:
		s := *a.(*[]int)
		for i := 0; i < len(s); i++ {
			fmt.Fscan(reader, &s[i])
		}
	case *[]string:
		s := *a.(*[]string)
		for i := 0; i < len(s); i++ {
			fmt.Fscan(reader, &s[i])
		}
	default:
		fmt.Fscan(reader, a)
	}
	return
}

func print(a ...interface{}) {
	fmt.Fprint(writer, a...)
}

func println(a ...interface{}) {
	fmt.Fprintln(writer, a...)
}

func max(x int, y ...int) int {
	res := float64(x)
	for _, z := range y {
		res = math.Max(res, float64(z))
	}
	return int(res)
}

func min(x int, y ...int) int {
	res := float64(x)
	for _, z := range y {
		res = math.Min(res, float64(z))
	}
	return int(res)
}

func abs(x int) int {
	return int(math.Abs(float64(x)))
}

func sqrt(x int) int {
	return int(math.Sqrt(float64(x)))
}

func int2Int(x int) big.Int {
	var res big.Int
	res.SetInt64(int64(x))
	return res
}


Measured memory_bytes: 7680
#include <iostream>
#include <algorithm>
#include <utility>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <math.h>
#include <string.h>
#include <iomanip>
#include <numeric>
#include <cstdlib>
#include <cstdint>
#include <cmath>
#include <functional>
#include <limits>
#include <cassert>
#include <bitset>

using namespace std;

/* template */

using ll = long long;

void debug_out() { std::cout << std::endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cout << H << " ";
  debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cout << "debug: "; debug_out(__VA_ARGS__)
#else
#define debug(...) 
#endif

#define rep(i, a, n) for (int i = (int)(a); i < (int)(n); i++)
#define rrep(i, a, n) for (int i = ((int)(n-1)); i >= (int)(a); i--)
#define Rep(i, a, n) for (long long i = (long long)(a); i< (long long)(n); i++)
#define RRep(i, a, n) for (long long i = ((long long)(n-1ll)); i>=(long long)(a); i--)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()

template <typename T>
std::ostream& operator<<(std::ostream& os, std::vector<T> vec) {
  for (std::size_t i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");
  return os;
}

struct Edge{
    int to;
    ll weight;
    Edge(int t, ll w) : to(t), weight(w){ }
};

struct edge{
    int from;
    int to;
    ll weight;
    edge(int f,int t,ll w) : from(f), to(t), weight(w){ }
};


using Graph = vector<vector<Edge>>;
using graph = vector<vector<int>>;
using edges = vector<edge>;

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;
}

template <class T>
T lcm(T a, T b){
    return (a*b)/gcd(a,b);
}

ll ctoi(char c) {
	switch (c) {
	case '0': return 0; case '1': return 1; case '2': return 2;
	case '3': return 3; case '4': return 4; case '5': return 5;
	case '6': return 6; case '7': return 7; case '8': return 8;
	case '9': return 9;  default: return 0;
	}
}

constexpr ll LNF = 1LL<<50;

constexpr int INF = 1e9+7;

const long double PI=3.14159265358979323846;


vector<int> dx = {1,0,-1,1,-1,0};
vector<int> dy = {1,1,1,0,0,-1};

/* template */

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int l,r,d; cin >> l >> r >> d;
    int ans = r/d - (l-1)/d;
    cout << ans << endl;
}

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


def solve(r: int, D: int, x: int):
    for i in range(10):
        x = r * x - D
        print(x)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    r = int(next(tokens))  # type: int
    D = int(next(tokens))  # type: int
    x = int(next(tokens))  # type: int
    solve(r, D, x)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3060
using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.Text;
using System.Text.RegularExpressions;
using System.Linq;
using System.IO;

class Program
{
    static void Main(string[] args)
    {
        new Magatro().Solve();
    }
}

public class Scanner
{
    private StreamReader Sr;

    private string[] S;
    private int Index;
    private const char Separator = ' ';

    public Scanner(Stream source)
    {
        Index = 0;
        S = new string[0];
        Sr = new StreamReader(source);
    }

    private string[] Line()
    {
        return Sr.ReadLine().Split(Separator);
    }

    public string Next()
    {
        string result;
        if (Index >= S.Length)
        {
            S = Line();
            Index = 0;
        }
        result = S[Index];
        Index++;
        return result;
    }
    public int NextInt()
    {
        return int.Parse(Next());
    }
    public double NextDouble()
    {
        return double.Parse(Next());
    }
    public long NextLong()
    {
        return long.Parse(Next());
    }
    public decimal NextDecimal()
    {
        return decimal.Parse(Next());
    }
    public string[] StringArray(int index = 0)
    {
        Next();
        Index = S.Length;
        return S.Skip(index).ToArray();
    }
    public int[] IntArray(int index = 0)
    {
        return StringArray(index).Select(int.Parse).ToArray();
    }
    public long[] LongArray(int index = 0)
    {
        return StringArray(index).Select(long.Parse).ToArray();
    }
    public bool EndOfStream
    {
        get { return Sr.EndOfStream; }
    }
}

public class Magatro
{
    private Scanner Cin;
    private int N;
    private int[] A;
    private int Mod = 1000000007;
    private void Scan()
    {
        Cin = new Scanner(Console.OpenStandardInput());
        N = Cin.NextInt();
    }
    public void Solve()
    {
        Scan();
        Console.WriteLine(MyMath.Factorial(N, Mod));
    }
}

static class MyMath
{
    static public long MyPower(long a, long b, long mod)
    {
        long result = 1;
        while (b > 0)
        {
            if (b % 2 == 1)
            {
                result *= a;
                result %= mod;
            }
            a *= a;
            a %= mod;
            b /= 2;
        }
        return result;
    }

    static public long Factorial(long l, long mod)
    {
        if (l == 0) return 1;
        return (Factorial(l - 1, mod) * l) % mod;
    }
}

Measured memory_bytes: 13652
#include <bits/stdc++.h>
using namespace std;
using str = string;
using ll = long long;
#define REP(i,n) for(int i=0; i<int(n); i++)
#define RREP(i,n) for(int i=int(n)-1; i>=0; i--)
#define FOR(i,f,t) for(int i=int(f); i<=int(t); i++)
#define RFOR(i,f,t) for(int i=int(f); i>=int(t); i--)
#define ALL(vec) (vec).begin(),(vec).end()
#define ASORT(vec) sort(ALL(vec))
#define DSORT(vec) sort(ALL(vec), greater<int>());
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
#define YES(ans) if(ans) cout<<"YES"<<endl; else cout<<"NO"<<endl;
#define Yes(ans) if(ans) cout<<"Yes"<<endl; else cout<<"No"<<endl;
#define yes(ans) if(ans) cout<<"yes"<<endl; else cout<<"no"<<endl;

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

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

int main() {
    int x;
    cin >> x;
    cout << 360/gcd(360, x) << endl;
}


Measured memory_bytes: 3592
import java.util.*;
public class Main{
	public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int m = sc.nextInt();
      Map<Integer,int[]> map = new TreeMap<Integer,int[]>();
      for(int i = 0;i < m;i++){
      	int[] ary = new int[2];
        ary[0]=sc.nextInt();
        ary[1]=i;
        int b = sc.nextInt();
        map.put(b,ary);
      }
      int[] pary = new int[n];
      String[] ans = new String[m];
      for(int[] num:map.values()){
      	pary[num[0]-1]++;
        ans[num[1]]=String.format("%06d%06d",num[0],pary[num[0]-1]);
      }
      StringBuilder sb = new StringBuilder();
      for(String s:ans){
      	sb.append(s+"\n");
      }
      System.out.println(sb.toString());
    }
}

Measured memory_bytes: 179696
from collections import Counter

N = int(input())
A = Counter(list(map(int, input().split())))
A = {k: v for k, v in A.items() if v >= 2}
A = sorted(A.items(), key=lambda x: x[0], reverse=True)
A.extend([(0, 0), (0, 0)])
if A[0][1] >= 4:
    print(A[0][0]**2)
else:
    print(A[0][0]*A[1][0])


Measured memory_bytes: 18600
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <cmath>
#include <set>
#include <algorithm>
#include <iomanip>

typedef long long ll;
const ll MOD = 1e9 + 7;
const long long INF = 1LL<<60;
const double PI=3.14159265358979323846;
const int NMAX=100005;
using namespace std;

vector<bool> mm(10000001,true);
vector<int> mm2(10000001,-1);

ll enum_divisors(long long N) {
    if(mm[N] == true) {
        mm2[N] = 2;
        return 2;
    }
    if(N == 1){
        mm2[1] = 1;
        return 1;
    }

    ll cnt = 1;
    ll i;
    for (i = 2; i * i <= N; ++i) {
        if(N%i == 0){
            cnt+=mm2[N/i];
            break;
        }
    }
    for(ll j = N-1; j >= 0; j--){
    }
    mm2[N] = cnt;
    cout << N << " " << cnt << endl;
    return cnt;
}

int main(){
    ll n;
    cin >> n;
    ll ans = 0;

    for(int i = 1; i <= n; i++){
        ans += (i+(n/i)*i)*(n/i)/2;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 43452
#define _USE_MATH_DEFINES
#include <iostream>
#include <memory>
#include <memory.h>
#include <fstream>
#include <cmath>
#include <math.h>
#include <numeric>
#include <vector>
#include <stack>
#include <string>
#include <queue>
#include <sstream>
#include <cstdlib>
#include <cassert>
#include <cstdio>
#include <map>
#include <iomanip>
#include <list>
#include <cctype>
#include <algorithm>
#include <complex>

#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, m, n) for(int i = m; i < n; i++)
using namespace std;

typedef complex<double> xy_t;
typedef pair<xy_t, xy_t> line;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<double, double> Pd;
typedef pair<int, P> PP;
typedef pair<int, PP> PPP;
const int INF = 1 << 29;
const double EPS = 1E-10;

vector<pair<pair<double, int> , Pd> > ls;
bool use[300];

double calc(vector<Pd> range){
	double res = 0.0;
	sort(range.begin(), range.end());
	int sz = range.size();
	double last = -1e10;
	rep(i, sz){
		if(range[i].second > last){
			res += range[i].second - max(last, range[i].first);
			last = range[i].second;
		}
	}
	return res;
}

int main(){
	int n, sz;
	int cnt = 1;
	//ifstream in("input.txt");
	while(cin >> n && n){
		ls.clear();
		rep(i, n){
			double x, y, r;
			cin >> x >> y >> r;
			ls.push_back(make_pair(make_pair(y - r, i), Pd(x - r, x + r)));
			ls.push_back(make_pair(make_pair(y + r, i), Pd(x - r, x + r)));
		}
		sort(ls.begin(), ls.end());
		memset(use, false, sizeof(use));
		sz = ls.size();
		double pre = -1e4;
		double res = 0.0;
		rep(i, sz){
			int id = ls[i].first.second;
			double cur = ls[i].first.first;
			vector<Pd> range;
			rep(i, sz){
				if(use[ls[i].first.second]) range.push_back(ls[i].second);
			}
			res += (cur - pre) * calc(range);
			pre = cur;
			use[id] = !use[id];
		}
		std::cout << cnt++ << " " << fixed << setprecision(2) << res << endl;
	}
	//in.close();
	return 0;
}

Measured memory_bytes: 0
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
 
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
 
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
 
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define ins insert
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const int MOD = 1000000007;
const char nl = '\n';
const int MX = 100001; //check the limits, dummy
 
ll modExp(ll base, ll power) {
    if (power == 0) {
        return 1;
    } else {
        ll cur = modExp(base, power / 2); cur = cur * cur; cur = cur % MOD;
        if (power % 2 == 1) cur = cur * base;
        cur = cur % MOD;
        return cur;
    }
}

ll inv(ll base) {
    int g = MOD, r = base, x = 0, y = 1;
    while (r != 0) {
        int q = g / r;
        g %= r; swap(g, r);
        x -= q * y; swap(x, y);
    }
    return x < 0 ? x+MOD : x;
}

ll mul(ll A, ll B) {
	return (A*B)%MOD;
}

ll add(ll A, ll B) {
	return (A+B)%MOD;
}

ll dvd(ll A, ll B) {
    return mul(A, inv(B));
}

ll sub(ll A, ll B) {
    return (A-B+MOD)%MOD;
}


vi primes, leastFac;
void compPrimes(int N) {
	F0R(i, N) {
		leastFac.pb(0);
	}
	leastFac[0] = 1; leastFac[1] = 1;
	FOR(i, 2, N) {
		if (leastFac[i] == 0) {
			primes.pb(i);
			leastFac[i] = i;
		}
		for (int j = 0; j < sz(primes) && i*primes[j] < N && primes[j] <= leastFac[i]; j++) {
			leastFac[i*primes[j]] = primes[j];
		}
	}
}

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

    int N; cin >> N;
    int K; cin >> K;
    compPrimes(MX);
    int cf[MX];
    cf[0] = 0; cf[1] = 0;
    bool sf[MX];
    sf[0] = true; sf[1] = true;
    FOR(i, 2, MX) {
        cf[i] = 1 + cf[i / leastFac[i]];
        sf[i] = sf[i / leastFac[i]] && leastFac[i] != leastFac[i / leastFac[i]];
    }

    ll ans = 0;
    ll cnt[K+1];
    FOR(i, 1, K+1) {
        cnt[i] = modExp(K/i, N);
    }
    FOR(i, 1, K+1) {
        ll cur = cnt[i];
        for (int j = i * 2; j <= K; j+=i) {
            if (!sf[j/i]) continue;
            if (cf[j] % 2 == cf[i] % 2) {
                cur += cnt[j]; cur %= MOD;
            } else {
                cur -= cnt[j]; cur += MOD; cur %= MOD;
            }
        }
        ans += cur * i; ans %= MOD;
//        cout << cur << nl;
    }
    cout << ans << nl;

	return 0;
}
 
// read the question correctly (ll vs int)
// template by bqi343



Measured memory_bytes: 5136
#include<bits/stdc++.h>
using namespace std;
#define NIL -1

struct Point {
  int x, y, h;
};

int main(){
  int n;
  cin >> n;
  int x, y, h;
  Point p[n];
  for ( int i = 0; i < n; i++){
    cin >> x >> y >> h;
    p[i].x = x;
    p[i].y = y;
    p[i].h = h;
  }

  bool isCorrect;
  for ( int x = 0; x <= 100; x++){
    for ( int y = 0; y <= 100; y++){
      isCorrect = true;
      int h = NIL;
      for ( int i = 0; i < n; i++){
        if (p[i].h == 0) continue;
        if (h == NIL){
          h = abs(p[i].x - x) + abs(p[i].y - y) + p[i].h;
        }
        if (h != NIL &&max(h - abs(p[i].x - x) - abs(p[i].y - y), 0) != p[i].h ){
          isCorrect = false;
          break;
        }
      }
      for ( int i = 0; i < n; i++){
        if (p[i].h > 0) continue;
        if (max(h - abs(p[i].x - x) - abs(p[i].y - y), 0) != p[i].h ){
          isCorrect = false;
          break;
        }
      }

      if ( isCorrect ){
        cout << x << " " << y << " " << h;
        break;
      }
    }
    if ( isCorrect ){
      break;
    }
  }

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <cmath>
#include <numeric>
using namespace std;
#define rep(i,a,b) for(int64_t i=(a);i<(b);++i) // a ≦ i < b 
#define Rrep(i,a,b) for(int64_t i=(a);i>=(b);--i) // reverse repeat. a から b まで減少．
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend() //逆イテレータ
#define RANGE(a,b,c) (a).begin()+(b),(a).begin()+(c) // [b,c) イテレータ
#define INF 1000000000000000
#define MOD 1000000007
using PII = pair<int64_t, int64_t>;
using VI = vector<int64_t>;
using VVI = vector<VI>;
using VS = vector<string>;
using VP = vector<PII>;
using i64 = int64_t;
template<typename T> void invec(vector<T> &A){for(T& a : A) cin >> a;} 

struct DisjointSet {
    vector<int64_t> par; //根.連結成分の根にはその成分の要素数を符号反転して保存する．

    DisjointSet(int64_t n) : par(n, -1) {} //.0-indexed 
    void init(int64_t n) {par.assign(n, -1);}// 初期化

    int root(int64_t x) {
        if (par[x] < 0) return x; //根が負なら自身が根．
        else return par[x] = root(par[x]); //径路圧縮
    }

    // 連結判定
    bool issame(int64_t x, int64_t y) { return root(x) == root(y); }

    bool unite(int64_t x, int64_t y) { // 結合が行われればtrue.行われなければfalse.
        x = root(x); y = root(y); // 径路圧縮
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); 
        par[x] += par[y];
        par[y] = x;
        return true;
    }

    int64_t size(int64_t x){ return -par[root(x)]; }
};

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

int N, M; cin >> N >> M;
DisjointSet commu(N+M+1); // 1~Nが人、N+1~N+M+1 が言語。
rep(i, 1, N+1) {
    int K; cin >> K;
    rep(j, 0, K) {
        int L; cin >> L;
        commu.unite(L+N, i);
    }
}
rep(i, 2, N+1){
    if(!commu.issame(1, i)) {
        cout << "NO\n";
        return 0;
    }
}

cout << "YES\n";

return 0;
}
// 書いて考える．場合分け．情報整理．
// 単純に分かる量から．愚直解を実装して研究．
// 境界，出力文字列 チェック．行末にスペース入れない．
// 可読性優先．高速化次点．
// まずは全探索，分割，次にDP
// 制限を見る．境界に注意．求めたい量の変域．動かせる量．
// 偶奇，逆から，ソート，出現回数，出現位置，DP， 余事象，包除
// データ構造． 問題の特徴量．単調性，二分探索
// 存在判定：構成方法，入力の特徴
// gcd, lcm ,素因数分解．
// 例外を十分に含む一般化．想像力の限界
// 小さい系から例示
// 代数的処理．前処理によるクエリ高速化．
// 始めは過剰に例示・場合分けしてもいい．各場合を確実に対処．
// 自明な例から処理，除外．
// 小数のときは，精度の設定する．doubel 変数に数値を入力するときは 123. とする．
// テストケース作成は数表あり
// 実行エラー：vector添え字超え．0割り．



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

typedef struct{
  int t[6];
}sDice;


sDice d;

void f(int dire){
  int work;
  if(dire == 0){//S
    work = d.t[5];
    d.t[5] = d.t[1];
    d.t[1] = d.t[0];
    d.t[0] = d.t[4];
    d.t[4] = work;
  }else if(dire == 1){//W
    work = d.t[5];
    d.t[5] = d.t[3];
    d.t[3] = d.t[0];
    d.t[0] = d.t[2];
    d.t[2] = work;
  }else if(dire == 2){//N
    work = d.t[5];
    d.t[5] = d.t[4];
    d.t[4] = d.t[0];
    d.t[0] = d.t[1];
    d.t[1] = work;
  }else{
    work = d.t[5];
    d.t[5] = d.t[2];
    d.t[2] = d.t[0];
    d.t[0] = d.t[3];
    d.t[3] = work;
  }
}

int main(){
  int in[3];
  int i;
  
  for(i=0; i<6; ++i){
    scanf("%d", &d.t[i]);
  }

  scanf("%d", &in[0]);

  while(in[0]--){
    scanf("%d %d", &in[1], &in[2]);

    if(d.t[2] == in[2]){
      f(3),f(2);
    }else if(d.t[3] == in[2]){
      f(1),f(2);
    }else{
      for(i=0; i<4; ++i){
	if(in[2] == d.t[1]) break;
	f(0);
      }
    }
    
    for(i=0; i<4; ++i){
      if(in[1] == d.t[0]) break;
      f(1);
    }

    printf("%d\n", d.t[2]);
  }

  return 0;
}



Measured memory_bytes: 2744
#include <algorithm>
#include <bitset>
#include <cstdio>
#include <cassert>
#include <cmath>
#include <functional>
#include <iostream>
#include <sstream>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

typedef long long LL;
typedef pair<int, int> P;
typedef pair<LL, LL> PLL;

bool solve() {
    int n;
    cin >> n;
    if (n == -1) { return false; }
    string rev = "";
    while (n > 0) {
        int rem = n % 4;
        rev += rem + '0';
        n /= 4;
    }
    if (rev == "") rev = "0";
    reverse(begin(rev), end(rev));
    cout << rev << endl;
    return true;
}

int main() {
    while(solve());
    return 0;
}

Measured memory_bytes: 3076
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define all(n)      (n).begin(), (n).end()
#define ll long long
#define ull unsigned long long int
void solve() {
    ll n; cin >> n; vector<ll> v(n,0);
    for(int i = 0; i < n; i++){
        cin >> v[i];
    }
    sort(all(v));
    ll cnt = 0;
    for(int i = 0; i < n-2; i++){
        for(int j = i+1; j < n-1; j++){
            for(int k = j+1; k < n; k++){
                ll a = v[i], b = v[j], c = v[k];
                if(a != b && b != c && a != c){
                    if(a+b > c)cnt++; continue;
                    if(b+c > a)cnt++;continue;
                    if(a+c > b)cnt++;  continue;
                }
            }
        }
    }
    cout << cnt <<endl;

    
}
int main(){
                
        solve();
    return 0;
            
}

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

int main() {
  int N;
  cin >> N;
  int a = N / 1000;
  int b = (N - a*1000) / 100;
  int c = (N -a*1000 - b*100)/10;
  int d = (N -a*1000 - b*100 - c*10);

  if(a == b && b == c) {
    cout << "Yes" << endl;
  }else if(b == c && c == d){
    cout << "Yes" << endl;
  }else if(a == b && b == c && c == d){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}


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

int main() {
  std::string s;
  std::cin >> s;
  uint64_t k;
  std::cin >> k;
  for (int i = 0; i < (int)s.size(); ++i) {
    if (k == 0) {
      break;
    }
    if (s[i] + k >'z' && s[i] != 'a') {
      k -= 'z' - s[i] + 1;
      s[i] = 'a';
    }
  }
  s[s.size()-1] += k % 26;
  std::cout << s << std::endl;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  string s;
  cin >> s;
  for(int i = 0; i < s.length()-8; i++)
    cout << s[i];
  cout << endl;  
  return 0;
}

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

signed main(){
  int N,C;
  cin>>N>>C;
  std::vector<int> x(N),v(N);
  for(int i=0;i<N;i++)cin>>x[i]>>v[i];
  std::vector<int> tm(N);
  tm[0]=v[0]-x[0];
  for(int i=1;i<N;i++)tm[i]=tm[i-1]+v[i]-(x[i]-x[i-1]);
  std::vector<int> gm(N);
  gm[0]=v[N-1]-(C-x[N-1]);
  for(int i=1;i<N;i++)gm[i]=gm[i-1]+v[N-1-i]-(x[N-1-i+1]-x[N-1-i]);
  int ans=0;
  for(int i=0;i<N;i++){ans=max(ans,tm[i]);}
  for(int i=0;i<N;i++){ans=max(ans,gm[i]);}
  //cout<<111<<" "<<ans<<endl;
  std::vector<int> ge(N);
  int k=0;
  for(int i=0;i<N;i++){
    if(gm[i]>k){
      ge[i]++;
      k=gm[i];
    }
  }
  int l=N-1;
  for(int i=0;i<N;i++){
    while((ge[l]==0||l+i>=N-1)&&l>=0)l--;
    if(l<0)break;
    ans=max(ans,gm[l]+tm[i]-x[i]);
    //cout<<222<<" "<<ans<<endl;
  }

  std::vector<int> te(N);
  k=0;
  for(int i=0;i<N;i++){
    if(tm[i]>k){
      te[i]++;
      k=tm[i];
    }
  }
  l=N-1;
  for(int i=0;i<N;i++){
    while((te[l]==0||l+i>=N-1)&&l>=0)l--;
    if(l<0)break;
    ans=max(ans,tm[l]+gm[i]-(C-x[N-i-1]));
    //cout<<333<<" "<<ans<<endl;
  }
  cout<<ans<<endl;
  //for(int i=0;i<N;i++)cout<<te[i]<<" "<<ge[i]<<endl;
}


Measured memory_bytes: 4992
#include<stdio.h>

int main(void)
{
  int i, j, n;
  int rec[4][13] = {0};
  char mark[4];
  int num;

  scanf("%d", &n);

  for(i = 0; i < n; i++) {
    scanf("%s %d", mark, &num);
    if(mark[0] == 'S') rec[0][num-1]++;
    if(mark[0] == 'H') rec[1][num-1]++;
    if(mark[0] == 'C') rec[2][num-1]++;
    if(mark[0] == 'D') rec[3][num-1]++;
  }

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

  return 0;
}

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

template<typename T>
class kdtree {
    struct node { int pos, l, r; };
    int np;
    T vec;
    vector<node> tree;
public:
    kdtree(auto& P): np(0)
    {
        vec=P;
        int n=vec.size();
        tree=vector<node>(n);
        build(0, n);
    }
    int build(int l, int r, int depth=0)
    {
        if (l>=r) return -1;
        int mid=(l+r)/2;
        int t=np++;
        if (depth%2==0)
            sort(begin(vec)+l, begin(vec)+r, [](auto& a, auto& b) { return a.x<b.x; });
        else
            sort(begin(vec)+l, begin(vec)+r, [](auto& a, auto& b) { return a.y<b.y; });
        tree[t].pos=mid;
        tree[t].l=build(l, mid, depth+1);
        tree[t].r=build(mid+1, r, depth+1);
        return t;
    }
    void get(T& res, int sx, int tx, int sy, int ty, int v=0, int depth=0)
    {
        int x=vec[tree[v].pos].x;
        int y=vec[tree[v].pos].y;
        if (sx<=x && x<=tx && sy<=y && y<=ty)
            res.push_back(vec[tree[v].pos]);
        if (depth%2==0) {
            if (tree[v].l!=-1 && sx<=x) get(res, sx, tx, sy, ty, tree[v].l, depth+1);
            if (tree[v].r!=-1 && x<=tx) get(res, sx, tx, sy, ty, tree[v].r, depth+1);
        }
        else {
            if (tree[v].l!=-1 && sy<=y) get(res, sx, tx, sy, ty, tree[v].l, depth+1);
            if (tree[v].r!=-1 && y<=ty) get(res, sx, tx, sy, ty, tree[v].r, depth+1);
        }
    }
};

int main()
{
    int n; __builtin_scanf("%d", &n);

    struct point { int x, y, id; };
    vector<point> p(n);
    for(int i=0; i<n; ++i) {
        int x, y; __builtin_scanf("%d%d", &x, &y);
        p[i]={x, y, i};
    }
    kdtree<decltype(p)> t(p);

    int q; __builtin_scanf("%d", &q);
    while (q--) {
        int sx, tx, sy, ty; __builtin_scanf("%d%d%d%d", &sx, &tx, &sy, &ty);
        decltype(p) res;
        t.get(res, sx, tx, sy, ty);
        sort(begin(res), end(res), [](auto& a, auto& b){ return a.id<b.id; });
        for(auto& e: res) printf("%d\n", e.id);
        puts("");
    }
}



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

void solve(long long N, long long A, long long B, std::vector<long long> v) {
    sort(v.rbegin(), v.rend());
    ll sum = 0;
    rep(i, A) {
        sum += v[i];
    }
    cout << setprecision(10) << double(sum) / double(A) << " ";

    ll target = v[A - 1];
    ll num = 0;
    ll largeNum = 0;
    rep(i, N) {
        if (v[i] > target) {
            largeNum++;
        }
        if (target == v[i]) {
            num++;
        }
    }

    A -= largeNum;
    B -= largeNum;
    ll ans = 0;
    ll comb = 1;
    ll end = min(B, num);
    rep(i, end) {
        comb = (comb * (num - i)) / (i + 1);
        if (i >= A - 1) {
            ans += comb;
        }
        if (largeNum && i == A - 1) {
            cout << ans << endl;
            return;
        }
    }
    cout << ans << endl;
}

// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main() {
    long long N;
    scanf("%lld", &N);
    long long A;
    scanf("%lld", &A);
    long long B;
    scanf("%lld", &B);
    std::vector<long long> v(N);
    for (int i = 0; i < N; i++) {
        scanf("%lld", &v[i]);
    }
    solve(N, A, B, std::move(v));
    return 0;
}


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

using namespace std;

int main()
{
    long long n,m,x,y,z;
    cin>>x>>y>>z;

    n=x-y;
    m=z-n;
    if(m<0)
    {
        cout<<"0"<<endl;
    }
    else
    {
        cout<<m<<endl;
    }
}


Measured memory_bytes: 256
N,M = map(int, input().split())
P = list(map(int, input().split()))

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
      
uf = UnionFind(N+1)
for _ in range(M):
  x,y = map(int, input().split())
  uf.union(x,y)
  
ans = 0
for i in range(N):
  if uf.same(i+1, P[i]):
    ans += 1
      
print(ans)

Measured memory_bytes: 20272
import java.util.Scanner;

class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    long n = Long.parseLong(sc.next());
    long k = Long.parseLong(sc.next());
    long a = n - (n/k)*k;
    long b = k-a;
    System.out.print(Math.min(a,b));
    System.out.flush();
  }
}

Measured memory_bytes: 22996
import sys
input = sys.stdin.readline
n = int(input())
a = [0]*n
b = [0]*n
c = [0]*n
for i in range(n):
    a[i],b[i],c[i] = map(int,input().split())

dpa = [a[0]]+[0]*(n-1)
dpb = [b[0]]+[0]*(n-1)
dpc = [c[0]]+[0]*(n-1)
for i in range(1,n):
    dpa[i] = max(dpb[i-1],dpc[i-1]) + a[i]
    dpb[i] = max(dpc[i-1],dpa[i-1]) + b[i]
    dpc[i] = max(dpa[i-1],dpb[i-1]) + c[i]
print(max(dpa[-1],dpb[-1],dpc[-1]))

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

using namespace std;

int main()
{
  int N, M; cin >> N >> M;
  vector<int> P(M), Y(M);
  vector<vector<int>> yd(N+1, vector<int>());
  for (int i = 0; i < M; ++i) {
    cin >> P[i] >> Y[i];
    yd[P[i]].push_back(Y[i]);
  }

  for (int i = 0; i <= N; ++i) {
    sort(yd[i].begin(), yd[i].end());
  }

  for (int i = 0; i < M; ++i) {
    // cout << lower_bound(yd[P[i]].begin(), yd[P[i]].end(), Y[i]) - yd[P[i]].begin() << endl;

    stringstream ssp, ssy;
    ssp << setw(6) << setfill('0') << P[i];
    ssy << setw(6) << setfill('0') << lower_bound(yd[P[i]].begin(), yd[P[i]].end(), Y[i]) - yd[P[i]].begin() + 1;
    cout << ssp.str() + ssy.str() << endl;
  }
}

Measured memory_bytes: 7808
#include<iostream>
#include<algorithm>
#include<functional>

#define MAX 100

int n,a,b,c,C[MAX+1],ans,co;

int main(){
	int c_=0;
	std::cin>>n>>a>>b>>c;
	for(int i=1;i<=n;++i){
		std::cin>>C[i];
	}
	co=c/a;
	ans=co;
	c_+=c;
	std::sort(C+1,C+n+1,std::greater<int>());
	for(int i=1;i<=n;++i){
		c_+=C[i];
		ans=std::max(c_/(i*b+a),ans);
	}
	std::cout<<ans<<std::endl;
	return 0;
}

Measured memory_bytes: 1176
fun main(args: Array<String>){
    val n = readLine()!!.toInt()
    val dict = Dict()
    repeat(n){
        val (query, s) = readLine()!!.split(' ')
        if(query == "insert"){dict.insert(s)}
        else if(query == "find") println(if (dict.find(s)) "yes" else "no")
    }
}

class Dict{
    private val arr = IntArray(30000000){ -1 }
    fun insert(element: String){
        arr[hash(element)] = 1
    }
    fun find(element: String): Boolean{
        return arr[hash(element)] == 1
    }
}

fun Int.pow(n: Int): Int = if(n == 0) 1 else this*this.pow(n-1)

fun hash(s: String): Int{
    var ret = 0
    for(i in 0 until s.length){
        val digit = when(s[i]){
            'A' -> 1
            'C' -> 2
            'G' -> 3
            'T' -> 4
            else -> 0
        }
        ret += 5.pow(i) * digit
    }
    return ret
}


Measured memory_bytes: 284068
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define dbg(...) do{cerr<<__LINE__<<": ";dbgprint(#__VA_ARGS__, __VA_ARGS__);}while(0);

using namespace std;

namespace std{template<class S,class T>struct hash<pair<S,T>>{size_t operator()(const pair<S,T>&p)const{return ((size_t)1e9+7)*hash<S>()(p.first)+hash<T>()(p.second);}};template<class T>struct hash<vector<T>>{size_t operator()(const vector<T> &v)const{size_t h=0;for(auto i : v)h=h*((size_t)1e9+7)+hash<T>()(i)+1;return h;}};}
template<class T>ostream& operator<<(ostream &os, const vector<T> &v){os<<"[ ";rep(i,v.size())os<<v[i]<<(i==v.size()-1?" ]":", ");return os;}template<class T>ostream& operator<<(ostream &os,const set<T> &v){os<<"{ "; for(const auto &i:v)os<<i<<", ";return os<<"}";}
template<class T,class U>ostream& operator<<(ostream &os,const map<T,U> &v){os<<"{";for(const auto &i:v)os<<" "<<i.first<<": "<<i.second<<",";return os<<"}";}template<class T,class U>ostream& operator<<(ostream &os,const pair<T,U> &p){return os<<"("<<p.first<<", "<<p.second<<")";}
void dbgprint(const string &fmt){cerr<<endl;}template<class H,class... T>void dbgprint(const string &fmt,const H &h,const T&... r){cerr<<fmt.substr(0,fmt.find(","))<<"= "<<h<<" ";dbgprint(fmt.substr(fmt.find(",")+1),r...);}
typedef long long ll;typedef vector<int> vi;typedef pair<int,int> pi;const int inf = (int)1e9;const double INF = 1e12, EPS = 1e-9;

int main(){
	cin.tie(0); cin.sync_with_stdio(0);
	
	string s; cin >> s;
	cout << (s.size() & 1 ^ (s[0] == s.back()) ? "First" : "Second") << endl;
	
	return 0;
}

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

int main() {
  string S;
  cin >> S;

  for (int i = 0, j = S.size() - 1; i <= j; i++, j--) {
    if (S[i] != S[j]) {
      cout << "No" << endl;
      return 0;
    }
  }

  for (int i = 0, j = (S.size() - 1) / 2 - 1; i <= j; i++, j--) {
    if (S[i] != S[j]) {
      cout << "No" << endl;
      return 0;
    }
  }

  for (int i = (S.size() + 3) / 2 - 1, j = S.size() - 1; i <= j; i++, j--) {
    if (S[i] != S[j]) {
      cout << "No" << endl;
      return 0;
    }
  }

  cout << "Yes" << endl;

  return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintStream;

class Main {

    public static void main(String[] args) throws IOException {
        doit(args, System.in, System.out);
    }

    static void doit(String[] args, InputStream in, PrintStream out)
            throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(in));
        int result = 0;
        while (true) {
            String line = reader.readLine();
            if (line == null || line.isEmpty()) {
                break;
            }
            int len = line.length();
            boolean different = false;
            for (int i = 0; i < len / 2; i++) {
                if (line.charAt(i) != line.charAt(len - i - 1)) {
                    different = true;
                    break;
                }
            }
            if (!different) {
                result++;
            }
        }
        out.println(result);
    }
}

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

#define rep2(x,fr,to) for(int x=(fr);x<(to);x++)
#define rep(x,to) for(int x=0;x<(to);x++)
#define repr(x,fr,to) for(int x=(fr);x>=(to);x--)
#define all(c) c.begin(),c.end()
#define sz(v) (int)v.size()

using namespace std;
typedef long long  ll; typedef vector<int> VI; typedef pair<int,int> pii; typedef vector<ll> VL; const int MD = 1e9 + 7;
void dbg(){cerr<<"\n";} template <class F,class ...S> void dbg(const F& f, const S&...s){cerr <<f <<": "; dbg(s...);}

int main()
{
	cin.tie(0); ios_base::sync_with_stdio(false);
	int n;
	cin >>n;
	VI a(n);
	rep(i, n) cin >>a[i];
	int cr = a[0];
	ll ans = 0;
	rep(i, n){

		if(a[i] < cr){
			ans += cr - a[i];
		}else cr = a[i];
	}
	
	cout << ans <<"\n";
	return 0;
}



Measured memory_bytes: 3988
import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        String t = sc.next();
        if (t.startsWith(s) && (t.length() == s.length()+1) ) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

Measured memory_bytes: 27004
#include <iostream>
#include <cmath>


using namespace std;


const double PI = acos(-1);	// πの定義


// S:面積 L:周辺の長さ h:高さ
int main()
{
	double a, b, c;
	int kakudo;
	double S, L, h;		// 求める答え

	cin >> a >> b >> kakudo;
	double rad = kakudo * PI / 180;

	// 三角形の面積を2つの辺とその間の角度から求める
	S = 0.5 * a * b * sin(rad);

	// 余弦定理
	c = sqrt(pow(a, 2) + pow(b, 2) - 2 * a * b * cos(rad));

	// 高さ
	h = b * sin(rad);


	/* Answer */
	cout << fixed;
	// S
	cout << S << endl;
	// L
	cout << a + b + c << endl;
	// h
	cout << h << endl;

	return 0;
}


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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

signed main(){
    int w,a,b;
    cin>>w>>a>>b;
    if(a>b)swap(a,b);

    cout<<max(0ll,b-a-w)<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define FORR(i, n) for(ll i = (ll)n - 1LL; i >= 0LL; i--)
#define rep(i, n) FOR(i, 0, n)
#define ALL(x) begin(x), end(x)
using namespace std;
using ll = long long;
constexpr ll Mod = 998244353;
constexpr ll mod = 1e9 + 7;
constexpr ll inf = 1LL << 60;
const double PI = acos(-1);
template <typename T1, typename T2> inline bool chmax(T1 &a, T2 b) {
    return a < b && (a = b, true);
}
template <typename T1, typename T2> inline bool chmin(T1 &a, T2 b) {
    return a > b && (a = b, true);
}
template <typename T> istream &operator>>(istream &is, vector<T> &v) {
    for(T &in : v)
        is >> in;
    return is;
}
template <typename T> ostream &operator<<(ostream &os, const vector<T> &v) {
    for(int i = 0; i < (int)v.size(); i++)
        os << (i ? " " : "") << v[i];
    return os;
}
/*-------------------------------------------*/

ll f(ll x) { return x * x * x * x * x; }

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

    ll x;
    cin >> x;

    for(ll a = -1000; a <= 1000; a++) {
        for(ll b = -1000; b <= 1000; b++) {
            if(f(a) - f(b) == x) {
                cout << a << " " << b << endl;
                return 0;
            }
        }
    }

    return 0;
}

Measured memory_bytes: 3536
#include <algorithm>
#include <cassert>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;

#define rep(i, n) for(ll i = 0; i < n; i++)
#define REP(i, n) for(ll i = 1; i < n + 1; i++)
#define PI 3.14159265359
#define EPS 0.0000000001
#define MOD 1000000007
//cout << std::fixed << std::setprecision(15) << y << endl;


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

    if(A + B > C + D){
        cout << "Left" << endl;
    }else if(A + B == C + D){
        cout << "Balanced" << endl;
    }else{
        cout << "Right" << endl;
    }
    
    return 0;
}

Measured memory_bytes: 3592
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define debug(x) cerr << #x << ": " << x << '\n';
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
ll dp[100010];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector <ll> w(n), v(m);
  for (int i = 0; i < n; ++i) {
    cin >> w[i] >> v[i];
  }
  
  for (int i = 0; i < n; ++i) {
    for (int j = m; w[i] <= j; --j) {
      dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
    }
  }
  cout << dp[m] << '\n';
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#define sync()      ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define fileIO()    freopen("input.txt", "r", stdin),freopen("output.txt", "w", stdout)
#define F           first
#define S           second
#define ers         erase
#define ins         insert
#define db          pop_back
#define pb          push_back
#define df          pop_front
#define pf          push_front
#define SZ(x)       ((ll)x.size())
#define sqr(x)      (x)*(x)
#define Blz(x)      __builtin_clz(x)
#define Brz(x)      __builtin_ctz(x)
#define Bones(x)    __builtin_popcount(x)
#define all(x)      x.begin(),x.end()
#define kill(x)     return cout<<x,0
#define dbgp(x)     cerr<< #x << " = " << x.F << ", " << x.S << endl
#define dbg(x)      cerr<< #x << " = " << x << endl
#define ddbg(i,x)   cerr<< #i << " = " << i << " / ", dbg(x[i])
#define tdbg(i,E,x) cerr<< #i << " = " << i << " / ", ddbg(E,x[i])
typedef long long                                    ll;
typedef long double                                  ld;
typedef unsigned short int                           usi;
typedef pair<long long,bool>                         plb;
typedef pair<long long,long long>                    pll;
typedef pair<int,int>                                pii;
typedef string                                       str;
typedef priority_queue<ll>                           maxheap;
typedef priority_queue<ll,vector<ll>,greater<ll>>    minheap;
typedef priority_queue<pll,vector<pll>,greater<pll>> djq;
const ll maxn=2e5+10, wax=20, inf=4e18, mod=1e9+7; const ld pi=3.14159265359, eps=1e-9;
bool mk[maxn];
int main(){
    sync();
    memset(mk,1,sizeof(mk));
    ll n,m,k,a; cin>>n>>m;
    map<ll,bool> f;
    for(int i=1;i<=n;i++){
        f.clear();
        cin>>k;
        while(k--){
            cin>>a;
            f[a]=1;
        }
        for(int i=1;i<=m;i++) mk[i]&=f[i];
    }
    ll t=0;
    for(int i=1;i<=m;i++) t+=mk[i];
    cout<<t;
    return 0;
}
/**

 (                            )   (   )
 )\ )             (      )  ( /(  () /(
(()/(  (  (    (  )\  ( /(  )\()) )\ ())
 /(_))_)  )\   )\((_) )(_))(_)\) ((_)(_)
(_)) __| ((_) ((_)| |((_)_)| |(_)| |_| |
  | (_ |/ _ \/ _ \| |/ _` || / / |  _  |
   \___|\___/\___/|_|\__,_||_\_\ |_| |_|

I'm burning in rage and hatred...
**/


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=105,inf=0x3f3f3f3f;
int read(){
	int f=1,g=0;
	char ch=getchar();
	for (;!isdigit(ch);ch=getchar()) if (ch=='-') f=-1;
	for (;isdigit(ch);ch=getchar()) g=g*10+ch-'0';
	return f*g;
}
int n,m,K,p,C[N][N],f[N][N][N][2],g[N][N][N][2];
char ch[N];
int qpow(int x,int k){
	int t=1;
	for (;k;k>>=1){
		if (k&1) t=(ll)t*x%p;
		x=(ll)x*x%p;
	}
	return t;
}
void check(int &x,int y){x=(x+y<p) ? (x+y) : (x+y-p);}
int main(){
//	freopen("a.in","r",stdin);
//	freopen("a.out","w",stdout);
	n=read();m=read();K=read();p=read();
	for (int i=0;i<=max(n,m);i++){
		C[i][0]=1;
		for (int j=1;j<=i;j++)
		C[i][j]=(C[i-1][j-1]+C[i-1][j])%p;
	}
	f[0][0][0][0]=1;
	for (int k=0;k<=K;k++){
		for (int j=0;j<=m;j++)
		g[k][0][j][0]=1,g[k][1][j][0]=(ll)qpow(K-k,j)*(qpow(k+1,m-j)-qpow(k,m-j)+p)%p;
		for (int i=0;i<=n;i++)
		g[k][i][0][1]=1,g[k][i][1][1]=(ll)(qpow(K-k,i)-qpow(K-k-1,i)+p)*qpow(k+1,n-i)%p;
		for (int i=0;i<=n;i++)
		for (int j=0;j<=m;j++){
			if (i>1) g[k][i][j][0]=(ll)g[k][i-1][j][0]*g[k][1][j][0]%p;
			if (j>1) g[k][i][j][1]=(ll)g[k][i][j-1][1]*g[k][i][1][1]%p;
		}
	}
	for (int d=0;d<K;d++){
		for (int i=0;i<=n;i++)
		for (int j=0;j<=m;j++)
		for (int k=0;i+k<=n;k++)
		check(f[d][i+k][j][1],(ll)f[d][i][j][0]*g[d][k][j][0]%p*C[n-i][k]%p);
		for (int i=0;i<=n;i++)
		for (int j=0;j<=m;j++)
		for (int k=0;j+k<=m;k++)
		check(f[d+1][i][j+k][0],(ll)f[d][i][j][1]*g[d][i][k][1]%p*C[m-j][k]%p);
	}
	printf("%d\n",f[K][n][m][0]);
	return 0;
}

Measured memory_bytes: 18048
N = int(input())
*A, = map(int, input().split())
 
def partition(A, p, r):
    x = A[r]
    i = p
    for j in range(p, r):
        if A[j] <= x:
            A[i], A[j] = A[j], A[i]
            i += 1
    A[i], A[r] = A[r], A[i]
    return i
 
j = partition(A, 0, N-1)
print(*(str(x) if i != j else "[%d]" % x for i, x in enumerate(A)))



Measured memory_bytes: 16396
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    x = LI()
    L = NI()
    m = N.bit_length()
    f = [[N-1] * N for _ in range(m)]
    j = 0
    for i in range(N-1):
        while x[i] + L >= x[j+1]:
            j += 1
            if j >= N-1: break
        else:
            f[0][i] = j
            continue
        break
    for k in range(1,m):
        for i in range(N):
            f[k][i] = f[k-1][f[k-1][i]]

    for _ in range(NI()):
        ans = 0
        a,b = _LI()
        if a > b: a,b = b,a

        for k in range(m-1,-1,-1):
            if f[k][a] < b:
                a = f[k][a]
                ans += 2**k
        print(ans+1)



if __name__ == '__main__':
    main()

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

#define FOR(i,a,b) for(int i=a;i<b;i++)
#define For(i,a) FOR(i,0,a)
#define REP(a) For(i,a)

typedef long long ll;

using namespace std;

int main(){
	int times;
	while(1){
	  ll ans[2]={};
		scanf("%d",&times);
		if(times==0)break;
		REP(times){
			ll tmp[2];
			scanf("%d %d",&tmp[0],&tmp[1]);
			if(tmp[0]<tmp[1])ans[1]+=tmp[0]+tmp[1];
			else if(tmp[0]>tmp[1])ans[0]+=tmp[0]+tmp[1];
			else{ans[0]+=tmp[0];ans[1]+=tmp[1];}
		}
		printf("%d %d\n", ans[0], ans[1]);
	}
	return 0;
}


Measured memory_bytes: 3148
e=enumerate
n,s,q,*k=open(0).read().split()
n=int(n)
m,c,x=eval('[0]*-~n,'*3)
for i,t in e(s,1):
  m[i]=m[i-1]+('M'==t)
  f='C'==t
  c[i]=c[i-1]+f
  x[i]=x[i-1]+f*m[i]
for k in map(int,k):
  a=0
  for i,t in e(s):
    j=min(n,i+k)
    if'D'==t:a+=x[j]-x[i]-(c[j]-c[i])*m[i]
  print(a)

Measured memory_bytes: 85020
package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	as := make([]int, n+1)
	mm := make(map[int]int)
	var a int
	for i := 1; i <= n; i++ {
		fmt.Scan(&a)
		as[i] = a
		nx := i + a + 1
		if n < nx {
			continue
		}
		mm[nx]++
	}

	ans := 0
	for i := 1; i <= n; i++ {
		a := as[i]
		c := mm[i-a+1]
		if 0 < c {
			ans += c
		}
	}

	fmt.Println(ans)
}


Measured memory_bytes: 16088
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <math.h>
#include <sstream>
#include <iterator>

using namespace std;

#define endl ("\n")
#define pi (3.141592653589)
#define mod 1000000007
#define int int64_t
#define float double
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(c) c.begin(), c.end()
#define min3(a, b, c) min(c, min(a, b))
#define min4(a, b, c, d) min(d, min(c, min(a, b)))
#define rrep(i, n) for(int i=n-1;i>=0;i--)
#define rep(i,n) for(int i=0;i<n;i++)
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)

struct debugger
{
    template<typename T> debugger& operator , (const T& v)
    {    
        cerr<<v<<" ";    
        return *this;    
    }
} dbg;

int32_t main() 
{
    fast;
	int N, M;
    cin >> N >> M;
    int number = 0;
    while(M--){
        int n; cin >> n;
        number+=n;
    }
    if(number > N){
        cout << -1 << endl;
    } else{
        cout << N-number << endl;
    }

}




Measured memory_bytes: 3636
def gcd(a, b):
  if b == 0:
    return a
  ret = gcd(b, a%b)
  return ret

n = int(input())
a = list(map(int, input().split()))
l = [0 for i in range(n)]
r = l[:]

for i in range(1, n):
  l[i] = gcd(l[i-1], a[i-1])
  r[-i-1] = gcd(r[-i], a[-i])
ans = 0
for i in range(n):
  ans = max(ans, gcd(l[i], r[i]))
print(ans)

Measured memory_bytes: 14076