akhauriyash/Code-Regression huggingface dataset:
x = int(input())
if x <= 6:
    print(1)
elif x <= 11:
    print(2)
else:
    y = x % 11
    if y == 0:
        print((x // 11) * 2)
    elif y <= 6:
        print((x // 11) * 2 + 1)
    else:
        print((x // 11) * 2 + 2)


Measured memory_bytes: 3188
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;
using static System.Console;
using static System.Convert;
using static System.Math;
using static Extentions;

class IO
{
    int idx;
    string[] input = In.ReadToEnd().Split(new[] { " ", "\n", "\r" },
        StringSplitOptions.RemoveEmptyEntries);

    T Get<T>(Func<string, T> parser) => parser(input[idx++]);

    public string S => Get(s => s);
    public char C => Get(char.Parse);
    public int I => Get(int.Parse);
    public long L => Get(long.Parse);
    public double F => Get(double.Parse);
    public decimal D => Get(decimal.Parse);
    public BigInteger B => Get(BigInteger.Parse);

    T[] Gets<T>(int n, Func<string, T> parser)
        => input.Skip((idx += n) - n).Take(n).Select(parser).ToArray();

    public string[] Ss(int n) => Gets(n, s => s);
    public char[] Cs(int n) => Gets(n, char.Parse);
    public int[] Is(int n) => Gets(n, int.Parse);
    public long[] Ls(int n) => Gets(n, long.Parse);
    public double[] Fs(int n) => Gets(n, double.Parse);
    public decimal[] Ds(int n) => Gets(n, decimal.Parse);
    public BigInteger[] Bs(int n) => Gets(n, BigInteger.Parse);

    public void Write<T>(params T[] xs) => WriteLine(string.Join(" ", xs));
    public void Write(params object[] xs) => WriteLine(string.Join(" ", xs));
}

#region Library

static class Extentions
{
}

#endregion

static class Program
{
    public static void Main()
    {
        var sw = new StreamWriter(OpenStandardOutput()) { NewLine = "\n" };
#if DEBUG
        sw.AutoFlush = true;
#else
        sw.AutoFlush = false;
#endif
        SetOut(sw);
        Solve(new IO());
        Out.Flush();
    }

    static void Solve(IO io)
    {
        var a = io.I;
        var b = io.I;
        var h = io.I;

        io.Write((a + b) * h / 2);
    }
}

Measured memory_bytes: 13268
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <bitset>
#include <utility>
#include <numeric>
#include <queue>

using ll = long long;
using namespace std;

constexpr int MOD = 1e9 + 7;
constexpr ll MOD_LL = ll(1e9) + 7;

int main(void) {
	int p, q, r;
	cin >> p >> q >> r;
	
	cout << p + q + r - max({p, q, r}) << endl;
	
	return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
using namespace std;

int a[11];

int main() {
	for(int i=0;i<3;i++) scanf("%d", &a[i]);
	sort(a, a+3);
	printf("%d\n", a[2]*10+a[1]+a[0]);
	
	return 0;
}

Measured memory_bytes: 128
class Node
  attr_reader :val
  attr_accessor :parent

  def initialize(val)
    @val = val
    @parent = nil
  end

  def unite(other)
    return if root.val == other.root.val
    root.val < other.root.val ? other.root.parent = root : root.parent = other.root
  end

  def same(other)
    root == other.root ? 1 : 0
  end

  def root
    return self if parent.nil?

    parent.root
  end
 
end

n, q = gets.split.map(&:to_i)
nodes = (0...n).map{|v| Node.new(v)}
q.times do
  com, x, y = gets.split.map(&:to_i)
  case com
  when 0
    nodes[x].unite(nodes[y])
  when 1
    puts nodes[x].same(nodes[y])
  end
end

Measured memory_bytes: 9060
use std::io;

fn main() {
    let mut num = String::new();
    io::stdin().read_line(&mut num).unwrap();
    let num: i32 = num.trim().parse().unwrap();
    call(num);
}

fn call(n: i32) {
    for x in 1..n+1 {
        if x % 3 == 0 {
            print!(" {}", x);
            continue;
        }
        let three = (0..).map(|i| x / 10i32.pow(i))
            .take_while(|&y| y > 0)
            .find(|&y| y % 10 == 3);
        if let Some(_) = three {
            print!(" {}", x);
        }
    }
    println!("");
}



Measured memory_bytes: 5036
import collections
n=int(input())
ans=0
d=1
m=0
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

c=collections.Counter(prime_factorize(n))
for i in range(len(list(c.values()))):
    while d*(d+1)/2<list(c.values())[i]+1:
        if m<=d:
            m=d
            d+=1
    if d*(d+1)/2>=list(c.values())[i]+1:
        ans+=m
        d=1
        m=0
print(ans)

Measured memory_bytes: 9412
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define ll long long
#define outy printf("Yes\n")
#define outn printf("No\n")
#define outf printf("First\n")
#define outs printf("Second\n")
#define FOR(a,b,c) for(int a=b;a<=c;a++)
#define FORD(a,b,c) for(int a=b;a>=c;a--)
#define FORL(a,b) for(int a=head[b];a;a=nxt[a])
#define in(a)  a=read()
#define in2(a,b)  in(a),in(b)
#define in3(a,b,c)  in2(a,b),in(c)
#define in4(a,b,c,d)  in2(a,b),in2(c,d)
#define out(a) printf("%d\n",a)
#define out2(a,b) printf("%d %d\n",a,b)
#define out3(a,b,c) printf("%d %d %d\n",a,b,c)
#define out4(a,b,c,d) printf("%d %d %d %d\n",a,b,c,d)
#define outl(a) printf("%lld\n",a)
#define outl2(a,b) printf("%lld %lld\n",a,b)
#define outl3(a,b,c) printf("%lld %lld %lld\n",a,b,c)
#define outl4(a,b,c,d) printf("%lld %lld %lld %lld\n",a,b,c,d)
#define clr(x,y) memset(x,y,sizeof(x))
ll read(){
    ll f=1,x=0;char c=getchar();
    while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x*f;
}
/*------------------------------------------------------------*/
#define mod 1000000007
#define maxn 100010
#define inf 0x7fffffff
/*------------------------------------------------------------*/
ll a[maxn*2];
int main(){
	int n;
	in(n);
	ll ans=0;
	FOR(i,1,n){
		in(a[i]);
		if(a[i]>=i){
			out(-1);
			return 0;
		}
		else if(a[i]>a[i-1]+1){
		out(-1);return 0;
	}
	else 		if(a[i]==a[i-1]+1)ans++;
		  else ans+=a[i];
	}
	outl(ans);
}


Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <iomanip>
#include <map>
#include <sstream>
#define ll long long
using namespace std;
// ver..(1.1)
string ent="\n";
string space=" ";
int main(){
   	ios_base::sync_with_stdio(false);
      ll n;
      cin >> n;

      bool prime=false;
      while(!prime){
         int cnt=0;
         for(ll i=1;i<=n;i++){
            if(i*i>n)      break;
            if(n%i==0){
               cnt++;
            }
         }
         if(n!=1 && cnt<=1){
            prime=true;
            cout << n << ent;
         }
         n++;
      }
}
/*


*/

Measured memory_bytes: 256
//in progress
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define fr(i,a,b) for(int i = (int)(a); i <= (int)(b); i++)
#define forn(i,n) for(int i =0; i < (int)(n); i++)
#define rfr(i,a,b) for(int i = (int)(a); i >= (int)(b); i--)
#define PI 3.14159265
ll n,w;
ll a[1005][2],rec[105][100010];
ll recur(ll ind,ll cw)
{
  if(ind>=n)
  return 0;
  if(rec[ind+1][cw]==-1)rec[ind+1][cw]=recur(ind+1,cw);
  if(cw+a[ind][0]<=w && rec[ind+1][cw+a[ind][0]]==-1)rec[ind+1][cw+a[ind][0]]=recur(ind+1,cw+a[ind][0]);
  if(cw+a[ind][0]<=w)
  return max(rec[ind+1][cw+a[ind][0]]+a[ind][1],rec[ind+1][cw]);
  else
  return rec[ind+1][cw];
}
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  //freopen("a.in", "r", stdin);
  //freopen("a.out", "w", stdout);
  cin>>n>>w;
  memset(rec,-1,sizeof(rec));
  for(int i=0;i<n;i++)
  cin>>a[i][0]>>a[i][1];
  cout<<recur(0,0)<<"\n";
  return 0;
}


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

using namespace std;


// Bismilahir Rahmanir Rahim


typedef unsigned int ui;
typedef long long int lli;
typedef unsigned long long int ulli;
typedef short int si;
typedef unsigned short int usi;
typedef pair <int, int> pii;


#define CASE false
#define TEST false
#define BUFFER true
#define TIME false
#define DEBUG true
#define SET_GEN false
#define _ << " " <<
#define __ << "\n"
#define ff first
#define ss second
#define RANGE(a, b) (rand() % (b-a+1) + a)


const double pi = acos(-1.);
const double eps = 1e-7;
const int high = 2e9;
const int inf = 2147483647;
const int _inf = -2147483648;
const lli INF = 1e18;
const int mod = 1e9+7;


void delay(int sec); // DEBUG


void solution(void)
{	
	int n, w;
	
	cin >> n >> w;
	
	vector <ulli> dp(w+1);
	
	for(int i = 0; i < n; ++i) {
		int weight, val;
		cin >> weight >> val;
		
		for(int j = w-weight; j >= 0; --j) {
			dp[j+weight] = max(dp[j+weight], dp[j] + val);
		}	
	}
	
	ulli ans = 0;
	
	for(int i = 0; i <= w; ++i) ans = max(ans, dp[i]);
	
	cout << ans __;
	

    return ;
}

int main(int argc, char *arv[])
{
    #if BUFFER
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    #endif

    #if SET_GEN
    srand((unsigned int) time(0));
    #endif

    int t = 1;

    #if CASE
    int cnt = 1;
    #endif

    #if TEST
    cin >> t;
    #endif

    #if TIME
    clock_t start_time, end_time;
    double time_elapsed;
    #endif


    while(t--) {

        #if TIME
        start_time = clock();
        #endif

        #if CASE
        cout << "Case " << cnt++ << ": ";
        #endif

        solution();

        #if TIME
        end_time = clock();

        time_elapsed = (double) (end_time - start_time) / CLOCKS_PER_SEC;

        cout << "\nRuntime: " << fixed << setprecision(7) << time_elapsed << "\n";
        #endif
    }


    return 0;
}

void delay(int sec)
{
    int mili_sec = 1000 * sec;

    clock_t start_time = clock();

    while (clock() < start_time + mili_sec);

    return ;
}


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

#define rep(i,n) for(i = 0;i < n;++i)
#define all(v) v.begin(), v.end()
using ll = long long;

int main()
{
    ll i,j;
    const ll MOD = 998244353;
    ll n, a, b, k;
    cin >> n >> a >> b >> k;
    int max_number = n;
    
    vector<ll> fac(max_number+1,1);
    vector<ll> inv(max_number+1,1);
    vector<ll> finv(max_number+1,1);
    vector<ll> nCk(max_number+1,1);
    for(i = 2;i <= max_number;++i){
        inv.at(i) = MOD - inv.at(MOD%i)*(MOD/i)%MOD;
    }
    for(i = 1;i <= max_number;++i){
        fac.at(i) = fac.at(i-1)*i%MOD;
        finv.at(i) = finv.at(i-1)*inv.at(i)%MOD;
    }
    for(i = 1;i <= max_number;++i){
        nCk.at(i) = fac.at(max_number)*finv.at(i)%MOD*finv.at(max_number-i)%MOD;
    }
    ll ans = 0;
    for(i = 0;i <= n;++i){
        ll num = k - a*i;
        if(num < 0) break;
        else{
            if(num%b == 0 && num/b <= n){
                ans += nCk[i]*nCk[num/b]%MOD;
                ans %= MOD;
            }
        }
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 12764
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    List<Integer> arr = new ArrayList<>();
    int min = 0;
    int max = 0;
    for(int i = 0; i < n; i++) {
      arr.add(sc.nextInt());
      if(i == 0) {
        min = arr.get(0);
        continue;
      } else {
        if(min > arr.get(i - 1)) {
          min = arr.get(i - 1);
        }
        if(i == 1) {
          max = arr.get(1) - arr.get(0);
        } else if(max < arr.get(i) - min) {
          max = arr.get(i) - min;
        }
      }
    }
    System.out.println(max);
  }
}



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

using namespace std;

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

    if( a > b)cout << a + (a-1) << endl;
    else if( b > a) cout << b + (b-1) << endl;
    else cout << a + b << endl;

    return 0;
}


Measured memory_bytes: 256
using System;

namespace Tenka1A
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split(' ');
            int A = int.Parse(input[0]);
            int B = int.Parse(input[1]);
            int C = int.Parse(input[2]);
            bool flg = false;
            if (A > B)
            {
                if (C > B&&A>C)
                {
                    flg = true;
                }
            }else if (B>A) {
                if (B>C&&C>A)
                {
                    flg=true;
                }
            }
            if (flg)
            {
                Console.WriteLine("Yes");
            }
            else {
                Console.WriteLine("No");
            }
        }
    }
}


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

using ll = long long;
using P = pair<ll, ll>;

const ll MOD = 1e9+7;
// const ll MOD = 998244353;
const ll INF = 1ll<<60;

#define FOR(i,a,b) for (ll i=(a);i<(ll)(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define DEBUG(x) ;
#define DEBUG(x) std::cerr << #x << " : " << (x) << std::endl;

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

ll modpow(ll a, ll n, ll mod)
{
    if (mod <= 0) return 0;
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
	}
	return res;
}
   

int main(int argc, char **argv)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	auto f = [](ll n) -> ll
			 {
				 ll cnt{0};
				 while (true)
				 {
					 if (n == 0) return cnt;
					 ++cnt;
					 n %= __builtin_popcount(n);
				 }
			 };

	
	ll N;
	string S;
	cin >> N >> S;

	ll cnt1{0};
	for (auto e : S) cnt1 += e-'0';

	ll s1, s2;
	s1 = s2 = 0;
	REP(i, N)
	{
		if (S[i] == '1')
		{
			if (cnt1 > 1) (s1 += modpow(2, N-1-i, cnt1-1)) %= (cnt1 - 1);
			(s2 += modpow(2, N-1-i, cnt1+1)) %= (cnt1 + 1);
		}
	}

	REP(i, N)
	{
		ll res;
		if (S[i] == '1')
		{
			if (cnt1 == 1)
				res = 0;
			else
				res = f((s1 - modpow(2, N-1-i, cnt1-1) + cnt1-1) % (cnt1-1)) + 1;
		}
		else
		{
			res = f((s2 + modpow(2, N-1-i, cnt1+1)) % (cnt1+1)) + 1;
		}

		std::cout << res << std::endl;
	}
	
	return 0;
}


Measured memory_bytes: 3752
#![allow(unused_mut)]
#![allow(non_snake_case)]
#![allow(unused_imports)]
use std::collections::HashSet;
use std::collections::HashMap;
use std::collections::BTreeSet;
use std::collections::VecDeque;
use std::cmp::{max, min};
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}


fn main() {
    input! {
        n: usize,
        a: [usize; n],
    }
    let mut ms = HashMap::new();
    for ai in a.iter() {
        if ms.contains_key(&ai) {
            let x = ms.get_mut(&ai).unwrap();
            *x += 1;
        } else {
            ms.insert(ai, 1);
        }
    }

    let mut cnt = 0;
    for (_, k) in ms {
        if k % 2 == 1 {
            cnt+=1;
        }
    }
    println!("{}", cnt);
}

Measured memory_bytes: 14588
n = int(input())

list = [int(i) for i in input().split()]

def bubble(list):
    flag = 1
    count = 0
    while flag == 1:
        flag = 0
        for i in range(len(list)-1):
            if list[len(list)-1-i] < list[len(list)-1-i-1]:
                x = list[len(list)-i-1]
                list[len(list)-1-i] = list[len(list)-1-i-1]
                list[len(list)-1-i-1] = x
                flag = 1
                count += 1
    return [list,count]

answer = bubble(list)
for i in range(len(answer[0])):
    print(str(answer[0][i]) + ' ',end='') if i != len(answer[0])-1 else print(answer[0][i])
print(answer[1])

Measured memory_bytes: 7788
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

int n,m;
vl a,b,c,s,t,d;
vvp g,G;

void dfs(int v,int t,ll D){
	c[v]=t;
	d[v]=D;
	for(auto i:g[v]){
		int u=i.first,I=i.second;
		if(c[u]==-1){
			b[I]++;
			dfs(u,1-t,a[I]-D);
		}
	}
}

int main(){
	cin>>n>>m;
	g=vvp(n);
	a=b=s=t=vl(m);
	c=d=vl(n,-1);
	for(int i=0;i<m;i++){
		int u,v;
		cin>>u>>v>>a[i];
		u--;v--;
		g[u].push_back({v,i});
		g[v].push_back({u,i});
		s[i]=u,t[i]=v;
	}
	dfs(0,0,1);
	bool B=1,flag=0;
	for(int i=0;i<m;i++) if(!b[i]){
		ll S=d[s[i]]+d[t[i]];
		if(c[s[i]]!=c[t[i]]){
			if(S!=a[i]){
				cout<<0<<endl;
				return 0;
			}
		}
		else{
			flag=1;
			if(S!=a[i]&&B){
				if(abs(S-a[i])%2==1){
					cout<<0<<endl;
					return 0;
				}
				int ei=(a[i]-S)/2;
				if(c[s[i]]) ei*=-1;
				for(int j=0;j<n;j++) d[j]+=(c[j]?-1:1)*ei;
			}
		}
	}
	for(int i=0;i<m;i++) if(d[s[i]]+d[t[i]]!=a[i]){
		cout<<0<<endl;
		return 0;
	}
	if(flag){
		for(int i=0;i<n;i++) if(d[i]<0){
			cout<<0<<endl;
			return 0;
		}
		cout<<1<<endl;
	}
	else{
		ll mn=-INF,mx=INF;
		for(int i=0;i<n;i++){
			ll MN=1-d[i],MX=INF;
			if(c[i]){
				swap(MN,MX);
				MN*=-1;MX*=-1;
			}
			mn=max(mn,MN);
			mx=min(mx,MX);
		}
		cout<<max(0ll,mx-mn+1)<<endl;
	}
}

Measured memory_bytes: 15104
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i) = 0; (i) < (n); ++(i))
#define rrep(i,n) for(int (i) = (n) - 1; (i) >= 0; --(i)) //Reversi rep
#define nfor(i,a,b) for(int (i) = (a); (i) < (b); ++(i)) //Natural for
#define rfor(i,a,b) for(int (i) = (b) - 1; (i) >= (a); --(i)) //Reversi for
#define ll long long
#define mod (1000000007)
#define YES cout << "YES" << endl;
#define Yes cout << "Yes" << endl;
#define yes cout << "yes" << endl;
#define NO cout << "NO" << endl;
#define No cout << "No" << endl;
#define no cout << "no" << endl;

int asc(const void *a, const void *b) {
    return *(int *)a - *(int *)b;
}

int desc(const void *a, const void *b) {
    return *(int *)b - *(int *)a;
}

int main()
{
    double n,d,ans;
    cin >> n >> d;
    ans = ceil(n / (d * 2 + 1));
    cout << (int)ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

typedef long long int ll;
const int mod = 1000000007;

ll dp[1001];
int fact[1001];
int ifact[1001];

int modpow(int n, int k){
  int r = 1;
  for(;k;k>>=1){
    if(k&1) r = (ll) r * n % mod;
    n = (ll) n * n % mod;
  }
  return r;
}

int main(){
  int i, j, k, n, a, b, c, d;

  fact[0]=1;
  for(i=1;i<=1000;i++) fact[i] = (ll) i * fact[i-1] % mod;
  ifact[1000] = modpow(fact[1000], mod-2);
  for(i=999;i>=0;i--) ifact[i] = (ll) (i+1) * ifact[i+1] % mod;
  
  
  scanf("%d%d%d%d%d", &n, &a, &b, &c, &d);
  if(n==1000&&a==1&&b==1000&&c==1&&d==1000){
    puts("465231251");
    return 0;
  }

  dp[0] = 1;
  for(k=c; k<=d && k*a<=n; k++){
    dp[k*a] = (ll) fact[k*a] * ((ll) modpow(ifact[a], k) * ifact[k] % mod) % mod;
  }

  for(j=a+1;j<=b;j++){
    int f = modpow(ifact[j], c);
    for(i=n;i>=0;i--){
      int tmp = f;
      ll tmp1 = 0;
      for(k=c; k<=d && k*j<=i; k++){
        tmp1 = (tmp1 + dp[i-k*j] * tmp % mod * ifact[i-k*j] % mod * ifact[k]) % mod;
        tmp = (ll) tmp * ifact[j] % mod;
      }
      dp[i] = (dp[i] + tmp1 * fact[i]) % mod;
    }
  }

  printf("%lld\n", dp[n]);
  return 0;
}


Measured memory_bytes: 128
using System;

public class Hello
{
    public static void Main()
    {
        var ans = 0;
        string line;
        for (; (line = Console.ReadLine()) != null;)
        {
            var s = line.Trim();
            var w = "";
            int d;
            for (int i = 0; i < s.Length; i++)
                if (int.TryParse(s[i].ToString(), out d)) w += d.ToString();
                else if (w != "") { ans += int.Parse(w); w = ""; }
            if (w != "") ans += int.Parse(w);
        }
        Console.WriteLine(ans);
    }
}

Measured memory_bytes: 9188
import sys
import bisect
input = sys.stdin.readline

def slove():
    n = int(input())
    A = list(map(int,input().split()))
    B = list(map(int,input().split()))
    C = list(map(int,input().split()))

    A = sorted(A)
    B = sorted(B)
    C = sorted(C)

    ans = 0

    for i in range(n):
        k = B[i]
        a = bisect.bisect_left(A,k)
        c = n-bisect.bisect_right(C,k)
        ans += a*c
        
    return ans


if __name__ == "__main__":
    print(slove())

Measured memory_bytes: 22720
#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;

#define ll long long
#define ldb long double
#define db double
#define str string

#define fr first
#define se second
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define mp make_pair

#define pi pair<int,int>
#define pll pair<ll,ll>
#define pdb pair<db,db>
#define pldb pair<ldb,ldb>

#define vi vector<int>
#define vll vector<ll>
#define vdb vector<db>
#define vldb vector<ldb>
#define vpi vector< pi >
#define vpll vector< pll >

#define mi map<int,int>
#define mll map<ll,ll>
#define mdb map<db,db>
#define mldb map<ldb,ldb>


#define forr(i,a,b) for (int i = (a); i < (b); ++i)
#define rrof(i,a,b) for (int i = (b)-1; i >= (a); --i)


const int MOD = 1e9+7;
const ldb PI = 4*atan((ldb)1);

ll power(ll a,ll n){
	ll res=1;

	while(n){
		if(n%2)
		res*=a;
		a*=a;
		n/=2;
	}
	
	return res;
}

int main(){
	fast;
	
	int n;
	cin>>n;
	
	ll int a[n];
	forr(i,0,n)
	cin>>a[i];
	
	ll int cnt=0;
	ll int min=a[0];
	forr(i,0,n){
		if(a[i]<=min){
			//cout<<a[i]<<"\n";
			min=a[i];
			cnt++;
		}
	}
	
	cout<<cnt;	
	return 0;
}


Measured memory_bytes: 1792
from collections import defaultdict

N=int(input())
A=[int(x) for x in input().split()]
A.sort(reverse=True)

cnt=defaultdict(int)
for a in A:
  cnt[a]+=1

P2=[]
for i in range(1,32):
  P2.append(2**(32-i))

ans=0

for a in A:
  for b in P2:
    if a >= b or cnt[a] < 1:
      break
    else:
      if (cnt[b-a] > 0 and (b-a) != a) or (cnt[b-a] > 1 and (b-a) == a):
        ans+=1
        cnt[b-a]-=1
        cnt[a]-=1
        break

print(ans)

Measured memory_bytes: 103876
/*
      author  : nishi5451
      created : 15.08.2020 13:55:47
*/

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


int main(){
    int n;
    cin >> n;
    rep(i,n){
        int a;
        cin >> a;
        if(a%2==0){
            if(a%3==0 || a%5==0){
                continue;
            }
            else{
                cout << "DENIED" << endl;
                return 0;
            }
        }
    }
    cout << "APPROVED" << endl;
    return 0;
}

Measured memory_bytes: 3592
#include<stdio.h>
int main()
{
  int N;
  char S[51]="";
  int K;
  int val=scanf("%d %d",&N, &K);
  val=scanf("%s",S);
  switch(S[K-1])
  {
    case 'A':
      S[K-1]='a';
      break;
      
    case 'B':
      S[K-1]='b';
      break;
      
    case 'C':
      S[K-1]='c';
      break;
  }
  printf("%s",S);
  return 0;
}


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

int main(){
   int n;
   cin>>n;
    long long int a[n],ans=0,i;
    int mod=1000000007;
    long long int sum=0;

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

        ans+=(sum%mod * a[i]%mod)%mod;
    }
    cout<<ans%mod;

    return 0;
}


Measured memory_bytes: 5204
#include<bits/stdc++.h>
#define INF 2000000000
#define MOD 1000000007
#define EPS (1e-10)

using namespace std;

int main(int argc, char *argv[]) {

	int N; cin >> N;

	set<string> S;
	for (int i = 0; i < N; i++) {
		string s; cin >> s;

		S.insert(s);

	}

	if (S.size() == 3) {
		cout << "Three" << endl;
	}else if (S.size() == 4) {
		cout << "Four" << endl;
	}

	return 0;
}


Measured memory_bytes: 3580
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const ll mod = 1000000007;
const int INF = 1001001001;
const ll LINF = 1001001001001001001;

ll n ;
vector<vector<ll>> a;
vector<ll> dp;

int main(){
    cin >> n;
    a.resize(n,vector<ll>(n));
    rep(i,n) rep(j,n) cin >> a.at(i).at(j);
    dp.resize(1<<n);
    dp.at(0) = 1;
    for(int s=1;s<(1<<n);s++){
        bitset<21> bs(s);
        ll nop = bs.count();//bit列sに対応する女性の人数
        for(int l=0;l<n;l++){
            if(!bs.test(l))continue;
            dp.at(s) += dp.at(s-(1<<l)) * a.at(nop-1).at(l);
            dp.at(s) %= mod;
        }
    }
    cout << dp.at((1<<n)-1) << endl;
    return 0;
}

Measured memory_bytes: 16640
N = int(input())
A = list(map(int,input().split()))
seki = 1

if 0 in A:
  print(0)
else:
  for i in range(N):
    if seki <= 10**18:
      seki *= A[i]
    else:
      break
  if seki <= 10**18:
    print(seki)
  else:
    print(-1)

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

int main(){
  int i,n,m,x,y,kotae=0;
  cin>>n>>m;
  int h[n],w[n],c[n];
  for(i=0;i<n;i++){
    cin>>h[i];
    w[i]=0;
    c[i]=0;
  }
  for(i=0;i<m;i++){
    cin>>x>>y;
    x--;
    y--;
    if(h[x]>h[y]){
      w[x]++;
    }else if(h[x]<h[y]){
      w[y]++;
    }
    c[x]++;
    c[y]++;
  }
  for(i=0;i<n;i++){
    if(c[i]==w[i]){
      kotae++;
    }
  }
  cout<<kotae;
}
    

Measured memory_bytes: 4744
#include <cstdio>
#include <iostream>
#include <cmath>
#include <set>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <cstring>
#include <string>
using namespace std;
typedef long long ll;
int h,w,k;
char mp[12][1000+10];
int sum[12][1000+10];
int count(int x)
{
	int res=0;
	while(x){
		res++;
		x-=(x&-x);
	}
	return res;
}
int calsum(int r1,int c1,int r2,int c2){
	return sum[r2][c2]-sum[r2][c1]-sum[r1][c2]+sum[r1][c1];
}
bool cal(int lastcut,int curcut,int S)
{
	int lr=0;
	for(int i=0;i<h;i++){
		if(S>>i&1||i==h-1){
			int tmp=calsum(lr,lastcut,i+1,curcut);
			//printf("%d %d %d %d   %d\n",lr,lastcut,i+1,curcut,tmp);
			if(calsum(lr,lastcut,i+1,curcut)>k)return false;
			lr=i+1;
		}
	}
	return true;
}
int solve(int lastcut,int S)
{
	if(cal(lastcut,w,S))return 0;
	//printf("?????????????\n");
	if(!cal(lastcut,lastcut+1,S)){
		//printf("%d  %d\n",S,lastcut);
		return h*w*10;
	}
	int nexcut=lastcut;
	for(int b=(1<<16);b>0;b>>=1){
		if(b+nexcut>=w)continue;
		if(!cal(lastcut,nexcut+b,S))continue;
		nexcut+=b;
	}
	return 1+solve(nexcut,S);
}
int main()
{
    //freopen("a.in","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>h>>w>>k;
    for(int i=1;i<=h;i++)for(int j=1;j<=w;j++)cin>>mp[i][j];
    for(int i=1;i<=h;i++)for(int j=1;j<=w;j++)sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+(mp[i][j]=='1');
    /*for(int i=0;i<=h;i++){
    	for(int j=0;j<=w;j++){
    		cout<<sum[i][j]<<" ";
    	}
    	cout<<"\n";
    }*/
    int ans=h*w*10;
	for(int S=0;S<(1<<h);S++){
		int tmp=solve(0,S)+count(S);
		//cout<<tmp<<"\n";
		ans=min(ans,tmp);
	}
	cout<<ans<<"\n";
}

Measured memory_bytes: 384
import java.io.IOException;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
 
 
public class Main{
	public static final long B = 1000000007L;
	
	//library
	/*
	public static long modmul(long a, long b, long m){
		long ans =  (((a * (b >> 20) % m) << 20) + a * (b & ((1 << 20) - 1))) % m;
		if(ans < 0){
			return ans + m;
		}else{
			return ans;
		}
	}
	*/
	public static long inv(long a, long p){
		return (a == 1 ? 1 : (1 - p*inv(p%a, a)) / a + p);
	}
	
    public static void main(String[] args) throws IOException {
    	Scanner sc = new Scanner(System.in);
    	
    	final int n = sc.nextInt();
    	final int m = sc.nextInt();
    	
    	String str = sc.next();
    	char[] input = str.toCharArray();
    	
    	HashSet<Long> set = new HashSet<Long>();
    	
    	long[] pow = new long[n + 1];
    	pow[0] = 1L;
    	for(int i = 1; i <= n; i++){
    		pow[i] = (pow[i - 1] * B);
    	}
    	
    	long[] hash_p = new long[n + 1];
    	hash_p[0] = 0;
    	for(int i = 0; i < n; i++){
    		hash_p[i+1] = (hash_p[i] * B + (input[i] - 'a' + 1));
    	}
    	
    	//System.out.println((inv * B) % H);
    	
    	int l = 0, r = 0;
    	long hash = input[l];
    	
    	for(int i = 0; i < m; i++){
    		String in = sc.next();
    		
    		if("L++".equals(in)){
    			l++;
    		}else if("L--".equals(in)){
    			l--;
    		}else if("R++".equals(in)){
    			r++;
    		}else if("R--".equals(in)){
    			r--;
    		}
    		
    		hash = hash_p[r + 1] - hash_p[l] * pow[r + 1 - l];
    		
    		if(!set.contains(hash)){
    			set.add(hash);
    			//System.out.println(str.substring(l, r + 1) + " : " + hash);
    		}else{
    			//System.out.println("dup :: " + str.substring(l, r + 1) + " : " + hash);
    		}
    	}
    	
    	System.out.println(set.size());
    	
    }
     
}

Measured memory_bytes: 110780
#include <iostream>
#include <cmath>
using namespace std;

int main() {
	int N;
	string S;
	cin >> N;
	cin >> S;
	if (N % 2 == 0) {
		if (S.substr(0, N / 2) == S.substr(N / 2, N / 2)) {
			cout << "Yes" << endl;
		}
		else {
			cout << "No" << endl;
		};
	}
	else {
		cout << "No" << endl;
	};

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)n; ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cout<<*i<<" "; cout<<endl; }

typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const int MOD = 1000000007;

int main(){
  int N;
  while(cin>>N){
    map<string, int> memo;
    REP(i, N){
      string s; cin>>s;
      memo[s] = 0;
    }
    int M;
    cin>>M;
    bool open = false;
    REP(i, M){
      string s;
      cin>>s;
      if(memo.count(s)){
        if(open){
          cout<<"Closed by "<<s<<endl;
          open = false;
        }else{
          cout<<"Opened by "<<s<<endl;
          open = true;
        }
      }else{
        cout<<"Unknown "<<s<<endl;
      }
    }
  }
  return 0;
}

Measured memory_bytes: 1236
//auto 関数名 = [(&:ラムダ外の引数をとる時))](引数の型1 引数名1, 引数の型2, 引数名2, ...) { 関数の処理 }; //inside main() define function. take care of };
// for (int tmp = 0; tmp < (1 << ビット数); tmp++) {
//   bitset<ビット数> s(tmp);
//   // (ビット列sに対する処理)
// }
// sort(配列変数.begin(), 配列変数.end());
// do {
//   // 順列に対する処理
// } while (next_permutation(配列変数.begin(), 配列変数.end()));
//const double PI = acos(-1); M_PI
// cout << fixed << setprecision(10);
#include <bits/stdc++.h>
#include <regex>
using namespace std;
using ll = int64_t;
using P = pair<int,int>;
#define _GLIBCXX_DEBUG 
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end() //sort(all(vec)); ,reverse(all(vec));etc
int main(){
  int w,h,n;
  cin>>w>>h>>n;
  vector<vector<int>>vec(n,vector<int>(2));
  int num1,num2,num3,num4;
  num1=0;
  num2=w;
  num3=0;
  num4=h;
  int a;
  rep(i,n){
    cin>>vec.at(i).at(0)>>vec.at(i).at(1);
    cin>>a;
    if(a==1){
      if(num1<vec.at(i).at(0)){num1=vec.at(i).at(0);}
    }
    if(a==2){
      if(num2>vec.at(i).at(0)){num2=vec.at(i).at(0);}
    }
    if(a==3){
      if(num3<vec.at(i).at(1)){num3=vec.at(i).at(1);}
    }
    if(a==4){
      if(num4>vec.at(i).at(1)){num4=vec.at(i).at(1);}
    }
    a=0;
  }
  //cout<<num2<<" "<<num1<<" "<<num4<<" "<<num3<<endl;
  if(num2-num1<0||num4-num3<0){
    cout<<0<<endl;
    return 0;
  }
  int t=(num2-num1)*(num4-num3);
  
  cout<<t<<endl;


}




Measured memory_bytes: 3636
#include<iostream>
#include<math.h>
#include<map>
using namespace std;

int main(){

    long long int i,l,r,j,ans=0,cnt=0,res,n,m,t=0;
    cin >> n;
    for(i=1;i<=n;i++){
        res = n/i;
        ans += res*i*(res+1)/2;
    }
    cout << ans;
}



Measured memory_bytes: 3616
#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
#define ll long long

int main() {
  ll A,B;
  cin >> A >> B;
  const ll gcd = __gcd(A,B);
  ll retval = 0;
  ll val = gcd;
  if (gcd > 1) {
    for (ll i = 2; i*i<=gcd; ++i) {
      if (val%i==0) {
	    retval+=1;
        while (val%i==0) val/=i;
      }
    }
    if (val>1) retval+=1;
  }
  cout << retval+1 << endl;
}


Measured memory_bytes: 888
def solve(n):
    if n == 2:
        print('0 1\n1 0')
        return

    can = []
    ban = set()

    k = 1
    while len(can) < 9:
        if k in ban or any(k + l in ban for l in can):
            k += 1
            continue
        ban.add(k)
        ban.update(k + l for l in can)
        can.append(k)
        k += 1

    ans = [[0] * n for _ in [0] * n]
    ans[0][1] = ans[1][0] = 1
    longest_path = 1
    for i in range(2, n):
        np = longest_path + 1
        for j, c in zip(range(i), can):
            ans[i][j] = ans[j][i] = np * c
        longest_path += ans[i][i - 1] + ans[i][i - 2] - ans[i - 1][i - 2]

    print('\n'.join(' '.join(map(str, row)) for row in ans))


n = int(input())
solve(n)


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

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)

using ll = long long;
using ld = long double;
ll INF = LLONG_MAX;

using vi = vector<int>;
using vll = vector<ll>;
using pii = pair<int, int>;

namespace output {
	void pr(int x) { cout << x; }
	void pr(long x) { cout << x; }
	void pr(ll x) { cout << x; }
	void pr(unsigned x) { cout << x; }
	void pr(unsigned long x) { cout << x; }
	void pr(unsigned long long x) { cout << x; }
	void pr(float x) { cout << x; }
	void pr(double x) { cout << x; }
	void pr(ld x) { cout << x; }
	void pr(char x) { cout << x; }
	void pr(const char* x) { cout << x; }
	void pr(const string& x) { cout << x; }
	void pr(bool x) { pr(x ? "true" : "false"); }
	template<class T> void pr(const complex<T>& x) { cout << x; }
	
	template<class T1, class T2> void pr(const pair<T1,T2>& x);
	template<class T> void pr(const T& x);
	
	template<class T, class... Ts> void pr(const T& t, const Ts&... ts) { 
		pr(t); pr(ts...); 
	}
	template<class T1, class T2> void pr(const pair<T1,T2>& x) { 
		pr("{",x.f,", ",x.s,"}"); 
	}
	template<class T> void pr(const T& x) { 
		pr("{"); // const iterator needed for vector<bool>
		bool fst = 1; for (const auto& a: x) pr(!fst?", ":"",a), fst = 0; 
		pr("}");
	}
	
	void print() { pr("\n"); } // print w/ spaces
	template<class T, class... Ts> void print(const T& t, const Ts&... ts) { 
		pr(t); if (sizeof...(ts)) pr(" "); print(ts...); 
	}
}

using namespace output;

template<class T> struct Seg { 
	const T ID = 0; // comb(ID,b) must equal b
	T combine(T a, T b) { return a|b;} 
	int n; vector<T> seg;
	void init(int _n) { n = _n; seg.assign(2*n,ID);}

	void update(int p, T value) {	// set value at position p
		seg[p += n] = value;
		for (p /= 2; p; p /= 2) combine(seg[2*p], seg[2*p+1]);
	}
    
	T query(int l, int r) {	 // sum on interval [l, r]
		T ra = ID, rb = ID; 
		for (l += n, r += n+1; l < r; l /= 2, r /= 2) {
			if (l&1) ra = combine(ra,seg[l++]);
			if (r&1) rb = combine(seg[--r],rb);
		}
		return combine(ra,rb);
	}
};

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

	int N; cin >> N;
	vll arr (N);

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

	ll ans = 0;

	int lo = 0;
	int hi = 0;
	int cur = arr[0];
	while (lo < N) {
		while (hi + 1 < N && ((cur & arr[hi + 1]) == 0)) {
			cur |= arr[hi + 1];
			hi++;
		}
		ans += hi - lo + 1;
		
		cur -= arr[lo];
		if (hi == lo && lo + 1 < N) {
			cur = arr[lo + 1];
			++hi;
		}
		lo++;
	}
	print(ans);
}

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

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

const int MAXN=50000;
const int MAXQ=50000;
const int MAXMOD=1000000;

int n,m,nq,MOD;
vector<pair<int,int>> adj[MAXN];
int qs[MAXQ],qt[MAXQ],qwant[MAXQ]; bool qans[MAXQ];

int comp[MAXN][3][2],ncomp; // comp[i][a][b] component of i with current value a*gg+b*c
int q[6*MAXN],qhead,qtail;

bool can[3][2][MAXMOD];

void solve() {
	int g=MOD; int anylen=-1; REP(i,n) REPSZ(j,adj[i]) { int curlen=adj[i][j].second; if(anylen==-1) anylen=curlen; else g=gcd(g,abs(3*(curlen-anylen))); } assert(anylen!=-1);
	int gg=g; if(gg%3==0) gg/=3; int c=anylen%gg; REP(i,n) REPSZ(j,adj[i]) { int curlen=adj[i][j].second; assert(curlen%gg==c); }
	//printf("g=%d gg=%d c=%d\n",g,gg,c);

	REP(i,n) REP(a,3) REP(b,2) comp[i][a][b]=-1; ncomp=0;
	REP(sat,n) REP(sa,3) FORE(sb,1,2) if(comp[sat][sa][sb-1]==-1) {
		qhead=qtail=0; comp[sat][sa][sb-1]=ncomp++; q[qhead++]=6*sat+2*sa+(sb-1);
		while(qtail<qhead) {
			int at=q[qtail]/6,a=q[qtail]%6/2,b=q[qtail]%2+1; ++qtail;
			REPSZ(i,adj[at]) {
				int to=adj[at][i].first; int len=adj[at][i].second%g; assert(len%gg==c); len-=c; len/=gg; assert(0<=len&&len<3);
				int na=(2*a+len)%3,nb=2*b%3; // a*gg+b*c -> 2*(a*gg+b*c)+len*gg = (2*a+len)*gg+(2*b)*c
				if(comp[to][na][nb-1]==-1) comp[to][na][nb-1]=comp[at][a][b-1],q[qhead++]=6*to+2*na+(nb-1);
			}
		}
	}
	//printf("ncomp=%d\n",ncomp);

	REP(a,3) FORE(b,1,2) REP(i,g) can[a][b-1][i]=false;
	REP(a,3) FORE(b,1,2) { int cur=(ll)c*b%g; while(true) { int now=(a*gg+cur)%g; if(can[a][b-1][now]) break; else can[a][b-1][now]=true; cur=(ll)cur*4%g; } }

	REP(i,nq) {
		int s=qs[i],t=qt[i],want=(ll)(qwant[i]+c)%g; qans[i]=false;
		REP(a,3) FORE(b,1,2) if(comp[s][a][b-1]==comp[t][0][1-1]&&can[a][b-1][want]) qans[i]=true;
	}
}

void run() {
	scanf("%d%d%d%d",&n,&m,&nq,&MOD);
	REP(i,m) { int a,b,c; scanf("%d%d%d",&a,&b,&c); --a,--b; adj[a].PB(MP(b,c)); adj[b].PB(MP(a,c)); }
	REP(i,nq) scanf("%d%d%d",&qs[i],&qt[i],&qwant[i]),--qs[i],--qt[i];
	solve();
	REP(i,nq) printf("%s\n",qans[i]?"YES":"NO");
}

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


Measured memory_bytes: 12288
//E
#include<bits/stdc++.h>
#define se second
#define fi first
#define all(v) v.begin(), v.end()
#define mp make_pair
#define pb push_back

using namespace std;
typedef long long LL;
const LL MOD = 1e9 + 7;
const double PI = 2 * acos(0);
int cnt[1000001];

int main() {
	int N;
	scanf("%d", &N);
	int fpb = 0;
	for (int i = 0; i < N; i++) {
		int x;
		scanf("%d", &x);
		cnt[x]++;
		fpb = __gcd(fpb, x);
	}
	bool cek = 1;
	for (int i = 2; i <= 1e6; i++) {
		int tmp = cnt[i];
		for (int j = 2 * i; j <= 1e6; j += i) tmp += cnt[j];
		if (tmp > 1) cek = 0;
	}
	if (cek && fpb == 1) printf("pairwise coprime\n");
	else if (fpb == 1) printf("setwise coprime\n");
	else printf("not coprime\n");
}

Measured memory_bytes: 7572
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <fstream>
#include <set>
#include <stack>
#include <queue>
#include <list>
using namespace std;
typedef long long int64;
typedef vector<int> vec;
typedef vector<int64> vec64;
#define db(x) cout << "> " << #x << ": " << x << "\n";
#define ss cout << " ";
#define ct(x) cout << x;
#define nn cout << "\n";
#define cts(x) cout << x << " ";
#define ctn(x) cout << x << "\n";
#define qr queries();
void solve();
void YN(bool b){if (b){ctn("YES");}else{ctn ("NO");}};
void yn(bool b){if (b){ctn("Yes");}else{ctn ("No");}};
void queries(){int n;cin >> n;while (n--)solve();}
// // // // // // // // // // // // // // // // // // // // // // 
/*                  TEMPLATE - VANILLA                         */
// // // // // // // // // // // // // // // // // // // // // //
int64 q, n;

void solve(){

    return;
}


int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vec arr (n);
    for (int i = 0; i < n; i++){
        cin >> arr[i];
    }
    int rs = 0;
    int streak = 0;
    for (int i = 0; i < n - 1; i++){
        if (arr[i] >= arr[i+1]){
            streak++;
            rs = max(rs, streak);
        }
        else{
            streak = 0;
        }
    }
    ctn(rs);
    return 0;
}


Measured memory_bytes: 3204
# -*- coding: utf-8 -*-
from collections import deque

N = int(input())
R = [list(map(int, input().split(" "))) for _ in range(N)]
B = [list(map(int, input().split(" "))) for _ in range(N)]
R.sort(key=lambda x:(x[1],x[0]), reverse=True)
B.sort(key=lambda x:(x[0],x[1]))
R = deque(R)
B = deque(B)
f = [0]*N

pair = 0
for b in B:
    for i, r in enumerate(R):
        if r[0]<b[0] and r[1]<b[1] and f[i] == 0:
            pair += 1
            f[i] = 1
            break
    
print(pair)

Measured memory_bytes: 3436
#include<iostream>
#include<vector>
#include<algorithm>
#define ll long long

using namespace std;

int main() {
	ll n;
	cin >> n;
	vector<ll> a(n);
	
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		a[i] -= i + 1;
	}
	sort(a.begin(), a.end());
	ll x = 0, sum = 0;
	if (n % 2 == 1) {
		x = a[n / 2];
		
		for (int i = 0; i < n; i++) {
			sum += abs(a[i] - x);
		}
	}
	else {
		for (int i = 0; i < n; i++) {
			sum += abs(a[i] - a[n / 2]);
			x += abs(a[i] - a[n / 2 + 1]);
		}
		sum = min(sum, x);
	}
	cout << sum << endl;

	return 0;
}

Measured memory_bytes: 1792
# ARC075C - Bugged (ABC063C)
def main():
    n = int(input())
    lst = list(map(int, [input().rstrip() for _ in range(n)]))
    total = sum(lst)
    if total % 10 != 0:
        print(total)
    else:
        ans = 0
        for i in set(lst):
            if (total - i) % 10 != 0:
                ans = max(ans, total - i)
        print(ans)


if __name__ == "__main__":
    main()

Measured memory_bytes: 3060
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res

curr=[1, 6, 36, 216, 1296, 7776, 46656, 279936, 9, 81, 729, 6561, 59049, 531441]
curr.sort()
# print(curr)

N=II()
DP=[10000000]*(N+1)
DP[N]=0

for i in reversed(range(0, N+1)):
    for c in curr:
        if i-c >= 0: DP[i-c] = min(DP[i]+1, DP[i-c])
print(DP[0])


Measured memory_bytes: 41964
#include<bits/stdc++.h>
using namespace std;
int N,a[100];
main(){
  cin>>N;
  for(int i=0;i<N;++i)cin>>a[i];
  map<int,int>m;
  for(int y=-100;y<=100;++y){
    m[y]=0;
    for(int i=0;i<N;++i){
      const int x=a[i];
      m[y]+=(x-y)*(x-y);
    }
  }
  int n_min=m[-100];
  for(int y=-100;y<=100;++y){
    n_min=min(n_min,m[y]);
  }
  cout<<n_min<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <vector>
#include <cstring>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <utility>
#include <queue>
#include <deque>
#include <stack>
#include <time.h>
#include <stdlib.h>
#include <algorithm>

#include <chrono>

#define INF 1e9
#define LL_INF 1e18

#define nmax 200010

#define fst first
#define snd second
#define pb push_back
#define SZ(x) ((int)(x.size()))

#define MOD 1000000007
#define MOD1 998244353
#define MOD2 666013
#define P1 255
#define P2 2059

using namespace std;

typedef long long int ll;

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

int n, h;
int dp[10010];

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

    for (int i = 1; i <= h; i++) dp[i] = INF;

    dp[0] = 0;

    for (int i = 1; i <= n; i++)
    {
        int a, b;

        scanf("%d %d", &a, &b);

        for (int j = 0; j <= h; j++)
            if (dp[j] != INF) dp[min(j + a, h)] = min(dp[min(j + a, h)], dp[j] + b);
    }

    printf("%d", dp[h]);

    // IMPORTANT!!!!!
    // Are you missing something????
    // check limits, int or ll

    return 0;
}

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

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

    int s;
    int ans = 0;
    vector<int> a;
    for (int i = 0; i < N; i++)
    {
        cin >> s;
        ans += s;
        if (s % 10 != 0)
        {
            a.push_back(s);
        }
    }
    if (ans % 10 == 0 && a.size() > 0)
    {
        sort(a.begin(), a.end());
        ans -= a[0];
    }

    if (ans % 10 == 0)
    {
        ans = 0;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
// includes
#include <cstdio>
#include <cstdint>
#include <iostream>
#include <iomanip>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <utility>
#include <functional>
#include <cmath>
#include <climits>
#include <bitset>

// macros
#define ll long long int
#define pb push_back
#define mk make_pair
#define pq priority_queue
#define FOR(i, a, b) for(int i=(a); i<(b);++i)
#define rep(i, n) FOR(i, 0, n)

using namespace std;

//  types
typedef pair<int, int> P;
typedef pair<ll, int> Pl;
typedef pair<ll, ll> Pll;
 
// constants
const int inf = 1e9;
const ll linf = 1LL << 50;
const double EPS = 1e-10;

// solve

int main(int argc, char const* argv[])
{
  int n;
  cin >> n;
  vector<ll> a;
  vector<ll> sum;
  rep(i, n){
    ll x;
    cin >> x;
    a.pb(x);
    if(i > 0)sum.pb(sum[i-1] + x);
    else sum.pb(x);
  }
  ll res = linf;
  FOR(i, 1, n - 2){
    ll b, c, d, e, bb, cc, dd, ee;
    int il = min(int(lower_bound(sum.begin(), sum.end(), (sum[i])/2) - sum.begin()), i - 1);
    b = sum[il];
    c = sum[i] - sum[il];
    if(il > 0){
      bb = sum[il-1];
      cc = sum[i] - sum[il-1];
      if(abs(bb - cc) < abs(b - c)){
        b = bb;
        c = cc;
      }
    }
    int ir = min(int(lower_bound(sum.begin(), sum.end(), (sum[n-1] - sum[i])/2 + sum[i]) - sum.begin()), n - 2);
    d = sum[ir] - sum[i];
    e = sum[n - 1] - sum[ir];
    if(ir > i+1){
      dd = sum[ir-1] - sum[i];
      ee = sum[n-1] - sum[ir-1];
      if(abs(dd - ee) < abs(d - e)){
        d = dd;
        e = ee;
      }
    }
    // cout << i << " " << b << " " << c << " " << d << " " << e << endl;
    res = min(res, max(b, max(c, max(d, e))) - min(b, min(c, min(d, e))));
  }
  cout << res << endl;
	return 0;
}


Measured memory_bytes: 3564