akhauriyash/Code-Regression huggingface dataset:
'''
　 ∧_,,∧    究極奥義「WAがACになーれ！！」
　（`・ω・)つ━☆・*。
　⊂　　 ノ 　　　・゜+.
　 し’´Ｊ　　*・ 
'''
import sys
input = sys.stdin.readline
class UnionFind():
   # 作りたい要素数nで初期化
   # 使用するインスタンス変数の初期化
   def __init__(self, n):
       self.n = n
       # root[x]<0ならそのノードが根かつその値が木の要素数
       # rootノードでその木の要素数を記録する
       self.root = [-1]*(n+1)
       # 木をくっつける時にアンバランスにならないように調整する
       self.rnk = [0]*(n+1)
   # ノードxのrootノードを見つける
   def Find_Root(self, x):
       if(self.root[x] < 0):
           return x
       else:
           # ここで代入しておくことで、後の繰り返しを避ける
           self.root[x] = self.Find_Root(self.root[x])
           return self.root[x]
   # 木の併合、入力は併合したい各ノード
   def Unite(self, x, y):
       # 入力ノードのrootノードを見つける
       x = self.Find_Root(x)
       y = self.Find_Root(y)
       # すでに同じ木に属していた場合
       if(x == y):
           return
       # 違う木に属していた場合rnkを見てくっつける方を決める
       elif(self.rnk[x] > self.rnk[y]):
           self.root[x] += self.root[y]
           self.root[y] = x
       else:
           self.root[y] += self.root[x]
           self.root[x] = y
           # rnkが同じ（深さに差がない場合）は1増やす
           if(self.rnk[x] == self.rnk[y]):
               self.rnk[y] += 1
   # xとyが同じグループに属するか判断
   def isSameGroup(self, x, y):
       return self.Find_Root(x) == self.Find_Root(y)
   # ノードxが属する木のサイズを返す
   def Count(self, x):
       return -self.root[self.Find_Root(x)]

n,m,k=map(int,input().split())
f=[set() for i in range(n)]
h=UnionFind(n)
for i in range(m):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    f[a].add(b)
    f[b].add(a)
    h.Unite(a,b)
ans=[h.Count(i)-len(f[i])-1 for i in range(n)]
for i in range(k):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    if h.isSameGroup(a,b):
        ans[a]-=1
        ans[b]-=1
print(*ans)

Measured memory_bytes: 109024
#include<bits/stdc++.h>
using namespace std; 
int main()
{

	
		int n,count=0;
	cin>>n;
	int a[n];
	for(int i=0;i<n;i++)
	cin>>a[i];
	
	
    	sort(a,a+n);
		count=a[n/2]-a[n/2-1];
		cout<<count<<endl;
	
}

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

int main() {
  long long int N, M;
  cin >> N >> M;
  
  if (M > 2 * N) {
    cout << N + (M - 2 * N) / 4 << endl;
  }
  else {
    cout << M / 2 << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int MAXn = 1e5 + 10;
typedef pair<int, int> pii;
vector<pii> g[MAXn];
bool color[MAXn];
int n;
void dfs(int v, int par, long long sum) {
	color[v] = sum % 2;
	for (pii tmp : g[v])
		if (tmp.first != par)
			dfs(tmp.first, v, sum + tmp.second);
}

int main() {
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int v, w, u;
		cin >> v >> u >> w;u--;v--;
		g[v].push_back(pii(u, w));
		g[u].push_back(pii(v, w));
	}
	dfs(0, -1, 0);
	for (int i = 0; i < n; i++)
		cout << color[i] << '\n';
}


Measured memory_bytes: 8064
#include <bits/stdc++.h>
using namespace std;
template<class T> ostream& operator<<(ostream &os, vector<T> V) { os << "[ "; for(auto v : V) os << v << " "; return os << "]"; }
template<class T> ostream& operator<<(ostream &os, set<T> S){ os << "{ "; for(auto s:S) os<<s<<" ";return os<<"}"; }
template<class L, class R> ostream& operator<<(ostream &os, pair<L,R> P) { return os << "(" << P.first << "," << P.second << ")";}
template<class L, class R> ostream& operator<<(ostream &os, map<L,R> M) { os << "{ "; for(auto m:M) os<<"("<<m.first<<":"<<m.second<<") "; return os<<"}"; }
#ifdef LMAO
    #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
    template <typename Arg1>
    void __f(const char* name, Arg1&& arg1){cerr << name << " : " << arg1 << endl;}
    template <typename Arg1, typename... Args>
    void __f(const char* names, Arg1&& arg1, Args&&... args){ const char* comma = strchr(names + 1, ','); cerr.write(names, comma - names) << " : " << arg1<<" | "; __f(comma+1, args...); }
#else
    #define trace(...) 42
#endif
#define ff first
#define ss second
#define pb push_back
#define eb emplace_back
#define endl "\n"
#define tcase int tt; cin>>tt; while(tt--)
#define tcase2 int tt; cin>>tt; for(int qq=1;qq<=tt;qq++)
#define all(x) x.begin(), x.end()
typedef long long int ll;
typedef  unsigned long long int ull;
typedef long double ld;
const int MAX = 1000010;
const int MOD2 = 998244353;
const int MOD = 1000000007; 
const int INF = 1e8;    
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const ld EPS = 1e-7;
#define forn(i, n) for(int i = 0; i < (int)n; i++)
#define forne(i, a, b) for(int i = a; i <= b; i++)   
/*****************start************/

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);cout<<fixed<<setprecision(25);cerr<<fixed<<setprecision(10);
    int n,W;
    cin>>n>>W;
    vector<ll> u(n),w(n);
    vector<ll> dp;
    for(int i=0;i<n;i++)
    {
        cin>>w[i]>>u[i];
    }
    dp.resize(W+1,0ll);    
    for(int j=0;j<n;j++)
    {
        for(int i=W-w[j];~i;i--)
            dp[i+w[j]]=max(dp[i+w[j]],dp[i]+u[j]);
    }
    ll ans=0;
    for(int i=0;i<=W;i++)
        ans=max(dp[i],ans);
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 3988
//shuffle

#include<stdio.h>
#include<string.h>

int main()
{
    int i=0 ,j=0 ;
    int m=0 ,h=0 ;
    int lenn=0 ;

    char n[201] = {0} ;
    char mem1[201] = {0} ;
    char mem2[201] = {0} ;

    while (1)
    {
        m=0 ;
        memset(n ,0,sizeof n) ;
        scanf("%s" ,n) ;

        if (strcmp(n ,"-") == 0) break ;

        lenn=strlen(n) ;

        scanf("%d" ,&m) ;

        for (i=0 ;i < m ;i++)
        {
            h=0 ;
            memset(mem1 ,0,sizeof mem1) ;
            memset(mem2 ,0,sizeof mem2) ;
            scanf("%d" ,&h) ;
            strncpy(mem1 ,n ,h) ;

            for (j=0 ;j < lenn-h ;j++)
            {
                mem2[j] = n[j+h] ;
            }

            memset(n ,0,sizeof n) ;
            strcat(mem2 ,mem1) ;
            strcpy(n ,mem2) ;
        }

        printf("%s\n" ,n) ;
    }

    return 0 ;
}

Measured memory_bytes: 604
#include<iostream>

using namespace std;

int main()
{
    int n,a,mi,ma;

    cin>>n;

    int b[200001];

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

    mi=b[0];
    ma=b[1]-b[0];

    for(int i=1;i<n;i++)
    {
        ma=max(ma,b[i]-mi);
        mi=min(b[i],mi);
    }

    cout<<ma<<endl;

    return 0;
}



Measured memory_bytes: 3860
#include <iostream>
#include <queue>
#include <map>
#include <vector>
#include <algorithm>

using namespace std; using ll=long long; const ll INF=1e18; using P=pair<ll,ll>;
const ll m = 1e9+7;

int main() {
  int n; cin>>n;
  string s1,s2; cin>>s1>>s2;

  vector<ll> v;
  for(int i=0;i<n;i++) {
    if (s1[i] == s2[i]) {
      v.push_back(1);
    } else {
      v.push_back(2);
      i++;
    }
  }
  ll an=1;
  for(int i=0;i<v.size();i++) {
    if (i == 0) {
      if (v[i] == 1) an*=3;
      else an*=6;
    } else {
      if (v[i-1] == 1 && v[i] == 1) an*=2;
      else if (v[i-1] == 2 && v[i] == 1) an*=1;
      else if (v[i-1] == 1 && v[i] == 2) an*=2;
      else if (v[i-1] == 2 && v[i] == 2) an*=3; 
    }
    an%=m;
  }
  cout<<an<<endl;
}

Measured memory_bytes: 256
#define rep( i, n )		for( i = 0; i < n; i++ )

#include <bits/stdc++.h>
using namespace std;

unordered_map<string, int> m;

int main()
{
int i;
int N;
int M;
int iMax;
string S;

	ios::sync_with_stdio( false );
	cin.tie( 0 );

	cin >> N;
	rep( i, N )
	{
		cin >> S;
		m[ S ]++;
	}

	cin >> M;
	rep( i, M )
	{
		cin >> S;
		m[ S ]--;
	}

    iMax = 0;
    for( auto it = m.begin(); it != m.end(); it++ )
	{
		if( iMax < it->second ) iMax = it->second;
    }
	
	
	cout << iMax << endl;

	return 0;
}


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

int N;
int a[100010];

int main()
{
	ios::sync_with_stdio(false);
	
	cin>>N;
	for(int i=1,tmp;i<=N;i++)
	{
		cin>>tmp;
		a[tmp]++;
	}
	int cnt=0;
	for(int i=1;i<=100000;i++)
	{
		if(a[i]) cnt++;
	}
	if(cnt%2==0) cnt--;
	cout<<cnt<<endl;
	return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define PI 3.14159265359
#define NIL (-1)
#define LL long long
using namespace std;
const int64_t MOD = 1e9 + 7;
const int INF = INT_MAX;

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

	int cnt = 0;
	while (N > 0) {
		int n = N % 10;
		if (n == 2) cnt++;
		N /= 10;
	}

	cout << cnt << endl;
}

Measured memory_bytes: 3528
if __name__ == '__main__':
    a = int(input())
    list=[]
    b=0
    for i in range(11):
        b+=26**(i+1)
        list.append(b)

    count = 0
    for i in range(11):
        if a <= list[i]:
            count = i+1
            break
    ans=""
    for i in range(count):
        c = a % 26
        a = a // 26
        if c == 0:
            c=26
            a-=1
        ans= chr(96 + c) +ans

        if a == 0:
            break

    print(ans)



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

const int MAX_N = 200000;

// p[i] := i 番目の素数
vector<int> p;
// is_p[i] := i が素数のとき true
bool is_p[MAX_N+1] = {false,false};

// エラトステネスのふるい
void sieve(){
	for(int i=2 ; i <= MAX_N ; i++ )
		is_p[i] = true;
	for(int i=2 ; i*i <= MAX_N ; i++ ){
		if( is_p[i] ){
			p.push_back( i );
			for(int j = i+i ; j <= MAX_N ; j += i ){
				is_p[j] = false;
			}
		}
	}
}

// N より大きい任意の2つ素数を足したものの中で P 番目に小さい数値を返す
int M(int N, int P){
	int pi[100];
	priority_queue<int, vector<int>, greater<int> > q;
	int pn = 0;
	for(int i = N+1 ; pn < P ; i++ ){
		if( is_p[i] ){
			pi[pn++] = i;
		}
	}
	for(int i=0 ; i < P ; i++ ){
		for(int j=i ; j < P ; j++ ){
			q.push( pi[i] + pi[j] );
		}
	}
	int result;
	for(int i=0 ; i < P ; i++ ){
		result = q.top(); q.pop();
	}
	return result;
}

int main(){
	int n,p;
	sieve();
	while( cin >> n >> p , n != -1 ){
		cout << M(n,p) << endl;
	}
}

Measured memory_bytes: 1156
using System;
namespace AtCoder
{

    class Program
    {
        static void Main(string[] args)
        //static void dummy()
        {
            // 入力データパース
            string szInput = Console.ReadLine();
            int nTotal = szInput.Length;

            int startIdx = szInput.IndexOf('A');
            int length = 0;
            for( int i=startIdx + 1; i < nTotal; ++i)
            {
                if('Z' != szInput[i]) { continue; }

                length = i - startIdx + 1;
            }

            Console.WriteLine(length);
        }
    }
}


Measured memory_bytes: 3416
#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<cstring>
#include<string>
#include<cmath>
#include<ctime>
#include<algorithm>
#define LL long long
#define PII pair<int,int>
#define pi acos(-1.0)
#define lowbit(x) x&(-x)
using namespace std;

const int inf=2e9+10;
int m,n;
int X1[110],Y1[110],X2[110],Z2[110];

double width(int* X,int* Y,int s,double x){
    double lb=(double)inf,ub=(double)(-inf);
    for(int i=0;i<s;i++){
        double x1=X[i],y1=Y[i],x2=X[(i+1)%s],y2=Y[(i+1)%s];
        if((x1-x)*(x2-x)<=0 && x1!=x2){
            double y=y1+(y2-y1)*(x-x1)/(x2-x1);
            lb=min(lb,y);
            ub=max(ub,y);
        }
    }
    return max(0.0,ub-lb);
}

void solve(){
    int min1=inf,max1=-inf;
    for(int i=0;i<m;i++){
        min1=min(min1,X1[i]);
        max1=max(max1,X1[i]);
    }
    int min2=inf,max2=-inf;
    for(int i=0;i<n;i++){
        min2=min(min2,X2[i]);
        max2=max(max2,X2[i]);
    }
    vector<int> xs;
    for(int i=0;i<m;i++) xs.push_back(X1[i]);
    for(int i=0;i<n;i++) xs.push_back(X2[i]);
    sort(xs.begin(),xs.end());
    double res=0.0;
    for(int i=0;i+1<m+n;i++){
        double a=xs[i],b=xs[i+1],c=(a+b)/2;
        if(min1<=c && c<=max1 && min2<=c && c<=max2){
            double fa=width(X1,Y1,m,a)*width(X2,Z2,n,a);
            double fb=width(X1,Y1,m,b)*width(X2,Z2,n,b);
            double fc=width(X1,Y1,m,c)*width(X2,Z2,n,c);
            res+=(b-a)/6*(fa+4*fc+fb);
        }
    }
    printf("%.6f\n",res);
}

int main(void){
    while(scanf("%d %d",&m,&n)!=EOF && (m || n)){
        for(int i=0;i<m;i++) scanf("%d %d",&X1[i],&Y1[i]);
        for(int i=0;i<n;i++) scanf("%d %d",&X2[i],&Z2[i]);
        solve();
    }
    return 0;
}


Measured memory_bytes: 3288
#include <bits/stdc++.h>
using namespace std;
int main(){
  int64_t N, K;
  cin >> N >> K;
  vector<int> vec(N);
  for(int i=0; i<N; i++){
    cin >> vec[i];
    vec[i]--;
  }
  vector<bool> seen(N,false);
  vector<int> route(0);
  route.push_back(0);
  int loop_start = -1;
  int pos = 0;
  
  for(int i=0; i<N; i++){
    if(seen[vec[pos]]){
      for(int j=0; j<route.size(); j++){
        if(route[j] == vec[pos]){
          loop_start = j;
        }
      }
      break;
    }
    route.push_back(vec[pos]);
    seen[pos] = true;
    pos = vec[pos];
  }
  
  
  /*for(int i=0; i<route.size(); i++){
    cout << route[i] << endl;
  }*/
  
  //cout << route.size() << " " << loop_start << endl;
  
  if(K < route.size()){
    cout << route[K] + 1 << endl;
  }
  else{
    K -= loop_start;
    int R = route.size();
    R -= loop_start;
    //cout << R << endl;
    K %= R;
    cout << route[loop_start + K] +1 << endl;
  }
} 

Measured memory_bytes: 5068
#include<iostream>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>

using namespace std;

#define int long long
#define endl "\n"

constexpr long long INF = (long long)2e9;
constexpr long long MOD = 1'000'000'007; 

int N, A, B;
vector<int> h;

int check(int m){
	// vector<int> temp(h);
	int con = 0;
	
	for(int i = 0; i < N; i++){
		int temp  = h[i] - m * B;
		
		if(temp >= 1) {
			con += (temp + (A-B) - 1)/(A-B);
			// con += (h[i] + A - 1)/A;
			// if(h[i] - m * A >= 1) con++;
		}
	}
	// cout<<"m = "<<m<<" con = "<<con<<endl;
	// return con;
	return con > m;
}
	
signed main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);
	

	
	cin>>N>>A>>B;
	
	h.resize(N);
	
	for(int i = 0; i < N; i++){
		cin>>h[i];
	}
	
	int l = 0, h = INF, m;
	
	while(l+1<h){
		m = (l + h)>>1;
		
		if(check(m)) {
			l = m;
		} else {
			h = m;
		}
	}
	
	cout<<h<<endl;
	
	return 0;
}

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

#define ll long long int
#define f(i,x,n)  for(int i=x;i<n;i++)
#define FASTIO cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
#define sz(a) int((a).size())
#define mod 1000000007
#define inf LLONG_MAX
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
template <typename T>
inline T gcd(T a, T b) { while (b != 0) swap(b, a %= b); return a; }

template <typename T>
inline void seethis(vector<T>vect)
{
    for(T x:vect)
        cout<<x<<" ";
    cout<<"\n";
}

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cerr << *it << " = " << a << endl;
    err(++it, args...);
}
//LCM
int lcm(int a, int b) {  return a * (b / gcd(a, b)); }

//For sort by second
bool cmp(const pair<int,int> &a)
{ return a.first<a.second; }

//Tree
/* const int MAXN = 1e5 + 5;
vector<ll> adj[MAXN];*/

//ModPower
ll modpower(ll a,ll b,ll c)
{
    ll res=1;
    while(b)
    {
        if(b&1LL)
            res=(res*a)%c;
        a=(a*a)%c;
        b>>=1;
    }
    return res;
}

int main()
{
    FASTIO;
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    int n;
    double maxd;
    cin>>n>>maxd;
    int ans=0;
    for(int i=0;i<n;i++)
    {
        double x,y;
         cin>>x>>y;

        double d= x*x + y*y;
        d=sqrt(d);

        if(d<=maxd)
            ans++;

    }

    cout<<ans<<"\n";
    return 0;
}

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

int main() {
string S;
int N;
cin >> N >> S;
int count = 0;
int C = 0;
int a;
  for(int i = 0; i < 1000; i++){
  a = i; 
    for(int j = 0; j < N; j++){
      
      if(C == 2){
      i %= 10;//iをiの三桁目の数に変換
        if((int)S.at(j) - 48 == i){
        C++;}else C += 0;}
      
      if(C == 1){
      i = (i%100)/10;//iをiの二桁目の数に変換
        if((int)S.at(j) - 48 == i ){
        C++;}else C += 0;}
  
      if(C == 0){
       i = i/10/10;//iをiの最高位の数に変換
         if((int)S.at(j) - 48 == i){
         C++;}else C += 0;}
       
      if(C == 3){
      count++;
      C = 0;
      i = a;
      break;}
  
      if(j == (N - 1)){
        C = 0;}
      i = a;
    }}
  cout << count << endl;}

Measured memory_bytes: 256
def dfs(g, v, i):
    if len(v) == len(g) - 1: return 1
    v.add(i)
    c = 0
    for u in g[i]:
        if u not in v: c += dfs(g, v, u)
    v.remove(i)
    return c

n, m = map(int, input().split())
g = [list() for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)
print(dfs(g, set(), 0))


Measured memory_bytes: 3064
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#define rep(i,a,n) for(ll i =(a);i<(n);i++)
#define urep(i,a,n) for(ll i = (a);i>=(n);i--)
#define all(x) (x).begin(),(x).end()
#define INF 1e9
const int mod = 1e9 + 7;
typedef long long ll;
using namespace std;
ll dx[4] = { 1,-1,0,0 };
ll dy[4] = { 0,0,1,-1 };
ll N, M, Q, H, W, D, L, R,K;
ll A;
ll B[200001];
ll ans;
string S;
char s[52][52];
ll gcd(ll a, ll b) {
	if (b == 0)return a;
	else return gcd(b, a%b);
}


int main() {
	cin >>K;
	ll a = K / 2;
	ll b = (K + 1) / 2;
	cout << a * b;
	cin >> ans;
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		if (N%K==0) {
			System.out.println(0);
		} else {

			System.out.println(1);
		}

	}
}

Measured memory_bytes: 23764
#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; i++)
using namespace std;

const int maxn = 105;
bool G[maxn][maxn], vis[maxn];
int n, m, ans, lk[maxn];

struct node {
    int x, y;
}a[maxn], b[maxn];

bool Find(int x) {
    rep(i, 1, n)
        if (G[x][i] && !vis[i]) {
            vis[i] = true;
            if (lk[i] == 0 || Find(lk[i])) {
                lk[i] = x;
                return true;
            }
        }
    return false;
}

int main() {
    scanf("%d", &n);
    memset(G, false, sizeof(G));
    rep(i, 1, n) scanf("%d%d", &a[i].x, &a[i].y);
    rep(i, 1, n) scanf("%d%d", &b[i].x, &b[i].y);
    rep(i, 1, n)
        rep(j, 1, n) {
            if (a[i].x < b[j].x && a[i].y < b[j].y)
                G[i][j] = true;
        }
    rep(i, 1, n) {
        memset(vis, false, sizeof(vis));
        if (Find(i)) ans++;
    }
    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


def gcd(x, y):
    """greatest common divisor of x and y"""
    while y:
        x, y = y, x % y
    return x


lcm = lambda a, b: a * b // gcd(a, b)


def main():
    a, b, c, d = map(int, input().split())
    a -= 1

    cm = lcm(c, d)

    dc = (b // c) - (a // c)
    dd = (b // d) - (a // d)
    dcd = (b // cm) - (a // cm)

    print((b - a) - ((dc + dd) - dcd))


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()


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

template <int MOD>
struct ModInt {
    using lint = long long;
    int val;

    // constructor
    ModInt(lint v = 0) : val(v % MOD) {
        if (val < 0) val += MOD;
    };

    // unary operator
    ModInt operator+() const { return ModInt(val); }
    ModInt operator-() const { return ModInt(MOD - val); }
    ModInt inv() const { return this->pow(MOD - 2); }

    // arithmetic
    ModInt operator+(const ModInt& x) const { return ModInt(*this) += x; }
    ModInt operator-(const ModInt& x) const { return ModInt(*this) -= x; }
    ModInt operator*(const ModInt& x) const { return ModInt(*this) *= x; }
    ModInt operator/(const ModInt& x) const { return ModInt(*this) /= x; }
    ModInt pow(lint n) const {
        auto x = ModInt(1);
        auto b = *this;
        while (n > 0) {
            if (n & 1) x *= b;
            n >>= 1;
            b *= b;
        }
        return x;
    }

    // compound assignment
    ModInt& operator+=(const ModInt& x) {
        if ((val += x.val) >= MOD) val -= MOD;
        return *this;
    }
    ModInt& operator-=(const ModInt& x) {
        if ((val -= x.val) < 0) val += MOD;
        return *this;
    }
    ModInt& operator*=(const ModInt& x) {
        val = lint(val) * x.val % MOD;
        return *this;
    }
    ModInt& operator/=(const ModInt& x) { return *this *= x.inv(); }

    // compare
    bool operator==(const ModInt& b) const { return val == b.val; }
    bool operator!=(const ModInt& b) const { return val != b.val; }

    // I/O
    friend std::istream& operator>>(std::istream& is, ModInt& x) noexcept { return is >> x.val; }
    friend std::ostream& operator<<(std::ostream& os, const ModInt& x) noexcept { return os << x.val; }
};

constexpr int MOD = 1e9 + 7;
using mint = ModInt<MOD>;

template <class T>
struct Combination {
    int max_n;
    std::vector<T> f, invf;

    explicit Combination(int n)
        : max_n(n), f(n + 1), invf(n + 1) {
        f[0] = 1;
        for (int i = 1; i <= n; ++i) {
            f[i] = f[i - 1] * i;
        }

        invf[max_n] = f[max_n].inv();
        for (int i = max_n - 1; i >= 0; --i) {
            invf[i] = invf[i + 1] * (i + 1);
        }
    }

    T fact(int n) const { return f[n]; }
    T invfact(int n) const { return invf[n]; }
    T perm(int a, int b) const {
        return a < b || b < 0 ? T(0) : f[a] * invf[a - b];
    }
    T comb(int a, int b) const {
        return a < b || b < 0 ? T(0) : f[a] * invf[a - b] * invf[b];
    }
};

Combination<mint> C(3000000);

void solve() {
    int lx, ly, rx, ry;
    std::cin >> lx >> ly >> rx >> ry;

    std::cout << C.comb(rx + ry + 2, rx + 1) -
                     C.comb(rx + ly + 1, rx + 1) -
                     C.comb(lx + ry + 1, lx) +
                     C.comb(lx + ly, lx)
              << std::endl;
}

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

    solve();

    return 0;
}


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

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

    int N;
    cin >> N;
    vector<bool> A(N + 1, false);
    for (int i = 0; i < N; i++) {
        int a;
        cin >> a;
        // 同じだとtrue
        A[i] = a == i + 1;
    }
    int ans = 0;
    for (int i = 0; i < N; i++) {
        if (A[i]) {
            ans++;
            A[i] = false;
            A[i + 1] = false;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <tuple>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;

vvl G;
vl dp;  // dp[v] : vを根とする部分木のトーナメントの深さの最小値

void dfs(ll v, ll p = -1) {
    // 行きの処理はこのへんに書く
    vl vec;  // vの子のdp値を要素とするvector
    for(auto u : G[v]) {
        if(u == p) {
            continue;
        }
        dfs(u, v);
        // 帰りの処理はこのへんに書く
        vec.pb(dp[u]);
    }
    sort(rall(vec));
    rep(i, vec.size()) {
        chmax(dp[v], vec[i] + i+1);
    }
}

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

    vl a(n);
    exrep(i, 1, n-1) {
        cin >> a[i];
        a[i]--;
    }

    G.resize(n);
    exrep(v, 1, n-1) {
        G[v].pb(a[v]);
        G[a[v]].pb(v);
    }

    dp.resize(n);
    const ll root = 0;
    dfs(root);

    out(dp[root]);
    re0;
}

Measured memory_bytes: 18176
#include <bits/stdc++.h>
using namespace std;
typedef long long   signed int LL;
typedef long long unsigned int LU;
#define incII(i, l, r) for(int i = (l)    ; i <= (r); ++i)
#define incID(i, l, r) for(int i = (l)    ; i <  (r); ++i)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); --i)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); --i)
#define inc(i, n)  incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define dec(i, n)  decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)
#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
template<typename T> bool setmin  (T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmax  (T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
LL mo(LL a, LL b) { assert(b > 0); a %= b; if(a < 0) { a += b; } return a; }
LL fl(LL a, LL b) { assert(b > 0); return (a > 0 ? a / b : (a - b + 1) / b); }
LL ce(LL a, LL b) { assert(b > 0); return (a < 0 ? a / b : (a + b - 1) / b); }
#define bit(b, i) (((b) >> (i)) & 1)
#define BC __builtin_popcountll
#define SC(T, v) static_cast<T>(v)
#define SI(v) SC(int, v.size())
#define SL(v) SC( LL, v.size())
#define RF(e, v) for(auto & e: v)
#define ei else if
#define UR assert(false)

// ---- ----

int n, k;

int main() {
	cin >> n >> k;
	
	cout << (n >= 2 * k - 1 ? "YES" : "NO") << endl;
	
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstring>
using namespace std;

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

int n;
int g[500][500];
int flow[500][500];
bool visited[500];

bool aug(int s, int t) {
  visited[s] = 1;
  if (s==t) return 1;
  REP(i,n) {
    if (g[s][i]-flow[s][i]>=1 && !visited[i]) {
      if (aug(i, t)) {
        flow[s][i]++;
        flow[i][s]--;
        return 1;
      }
    }
  }
  return 0;
}
bool augment(int s, int t) {
  memset(visited,0,sizeof(visited));
  return aug(s,t);
}


int main() {
  int m,q;
  cin >> n >> m >> q;
  
  REP(i,m) {
    int f,t;
    cin >> f>>t;
    f--;t--;
    g[f][t] = 1;
    g[t][f] = 1;
  }
  int ans = 0;
  while(1) {
    if (!augment(0,n-1))
      break;
    ans++;
  }
  
  REP(i,q) {
    int m,a,b;
    cin >>m>>a>>b;
    a--;b--;
    if (m==1) {
      g[a][b] = 1;
      g[b][a] = 1;
      if (augment(0,n-1))
        ans++;
    } else {
      g[a][b] = 0; g[b][a] = 0;
      if (flow[a][b] == -1) swap(a,b);
      if (flow[a][b] == 1) {
        flow[a][b] = flow[b][a] = 0;
        if (!augment(a,b)) {
          augment(n-1, b);
          augment(a, 0);
          ans--;
        }
      }
    }
    cout << ans << endl;
  }
}

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

int dp[100000];

vector<int>G[100000];

int func(int n){
    if(dp[n]!=0)
        return dp[n];
    int ans=-1;
    for(int i=0;i<G[n].size();i++)
        ans=max(ans,func(G[n][i]));
    return dp[n]=ans+1;
}

signed main(){
    int n,m,x,y;
    cin>>n>>m;
    while(cin>>x>>y)
        G[--x].push_back(--y);
    int ans=0;
    for(int i=0;i<n;i++)
        ans=max(ans,func(i));
    cout<<ans<<endl;
}


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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

struct UnionFind {
    vector<int> par;
    vector<int> rank;
    vector<int> size;
    vector<vector<int>> group;

    UnionFind(int n = 1) {
        init(n);
    }

    void init(int n = 1) {
        par.resize(n + 1);
        rank.resize(n + 1);
        size.resize(n + 1);
        group.resize(n + 1);
        for (int i = 0; i <= n; ++i) {
            par[i] = i;
            rank[i] = 0;
            size[i] = 1;
            group[i].push_back(i);
        }
    }

    int find(int x) {
        if (par[x] == x) {
            return x;
        } else {
            int r = find(par[x]);
            return par[x] = r;
        }
    }

    bool is_same(int x, int y) {
        return find(x) == find(y);
    }

    bool unit(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        } else {
            if (rank[x] < rank[y]) {
                swap(x, y);
            }
            if (rank[x] == rank[y]) {
                ++rank[x];
            }
            par[y] = x;
            size[x] += size[y];
            return true;
        }
    }

    int get_size(int x) {
        return size[find(x)];
    }

    void merge_tech(int x, int y) {
        x = find(x);
        y = find(y);
        if (group[x].size() > group[y].size()) {
            swap(x, y);
        }
        copy(group[y].begin(), group[y].end(), back_inserter(group[x]));
        group[y].clear();
        par[y] = x;
    }
};

template<typename T>
struct edge {
    int from, to;
    T cost;
};

template<typename T>
T kruskal(vector<edge<T>> &edges, int V) {
    sort(edges.begin(), edges.end(), [](const edge<T> &a, const edge<T> &b) {
        return a.cost < b.cost;
    });
    UnionFind unionFind(V);
    T res = 0;
    for (edge<T> &e: edges) {
        if (unionFind.unit(e.to, e.from)) {
            res += e.cost;
        }
    }
    return res;
}

void Main() {
    ll V, E;
    cin >> V >> E;
    vector<edge<ll>> graph;
    rep(i, E) {
        int s, t, w;
        cin >> s >> t >> w;
        graph.push_back({s, t, w});
    }
    ll ans = kruskal(graph, V);
    cout << ans << '\n';
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
    return 0;
}



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

int main(){
  int n;
  cin >> n;
  vector<int> A(n);
  rep(i, n) cin >> A[i];
  int ch = 0;
  rep(i, n-2){
    if(A[i]<A[i+1]&&A[i+1]<A[i+2]) ch++;
    else if(A[i]>A[i+1]&&A[i+1]>A[i+2]) ch++;
  }
  cout << ch << endl;
}

Measured memory_bytes: 256
function Main(input) {
    input = input.split(" ");
    var k = input[0];
    var n = input[1];

    if (500*k >= n) {
        console.log("Yes");
    } else {
        console.log("No");
    }
  }
   
  Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 7372
package main

import (
	"fmt"
	"os"
	"strings"
)

var N string

func main() {
	fmt.Scan(&N)
	digits := make([]int, 4)
	for i, c := range N {
		digits[i] = int(c - '0')
	}
	fmt.Fprintln(os.Stderr, digits)
	for bit := 0; bit < (1 << 3); bit++ {
		ans := digits[0]
		str := make([]string, 0, 10)
		str = append(str, fmt.Sprint(digits[0]))

		for i := 0; i < 3; i++ {
			if (bit>>uint(i))&1 == 1 {
				ans += digits[i+1]
				str = append(str, "+")
			} else {
				ans -= digits[i+1]
				str = append(str, "-")
			}
			str = append(str, fmt.Sprint(digits[i+1]))
		}
		if ans == 7 {
			str = append(str, "=7")
			fmt.Println(strings.Join(str, ""))
			return
		}
	}
}

func todigits(n, base int) (digits []int) {
	for n > 0 {
		digits = append(digits, n%base)
		n /= base
	}
	m := len(digits)
	for i := 0; i < (m+1)/2; i++ {
		digits[i], digits[m-1-i] = digits[m-1-i], digits[i]
	}
	return
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int t=0;
    char v=getchar();
    while(v<'0')v=getchar();
    while(v>='0'){
        t=(t<<3)+(t<<1)+v-48;
        v=getchar();
    }
    return t;
}
long long n,m;
int main(){
    n=read();m=read();
    if(n>1&&m>1)
    printf("%lld",(n*m+1)/2);
    else puts("1");
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define scanVec(vec , n) for(int i = 0; i < n ; i++){ cin>>vec[i];}
#define printVec(vec , n) for(int i = 0; i < n ; i++){ cout<<vec[i]<<" ";}
#define S second
#define F first
const int  MOD = 1e9 + 7;
const int  N = 1e5 + 7;
vector<int> g[N];
ll dp[N][2];

void dfs(int u , int p){

    dp[u][0] = dp[u][1] = 1;
    for(int i = 0; i < g[u].size() ; i++){
        int v = g[u][i];
        if(v == p) continue;
        dfs(v,u);
        dp[u][0] = (dp[u][0]*((dp[v][0]+dp[v][1])%MOD))%MOD;
        dp[u][1] = (dp[u][1]*dp[v][0])%MOD;
    }
}


//  a d f j k  l  ;
int main(){
    ios::sync_with_stdio(0);  cin.tie(0);
    int n , x , y;
    cin>>n;
    for(int i = 0 ; i < n-1 ; i++){
        cin>>x>>y;
        g[x].pb(y);
        g[y].pb(x);
    }
    if(n == 1) {
        cout<<2<<endl;
        return 0;
    }
    dfs(1,0);
    cout << (dp[1][0] + dp[1][1])%MOD << endl;

    return 0;
}

Measured memory_bytes: 14208
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using VI = vector<ll>;
using VV = vector<VI>;
using VS = vector<string>;

// tourist set
template <typename A, typename B>
string to_string(pair<A, B> p);

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);

string to_string(const string& s) {
  return '"' + s + '"';
}

string to_string(const char* s) {
  return to_string((string) s);
}

string to_string(bool b) {
  return (b ? "true" : "false");
}

string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}

template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}

template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}

void debug_out() { cerr << '\n'; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
// tourist set end

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

#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i,b) FOR(i, 0, b)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<'\n'
#define p2(s, t) cout << (s) << " " << (t) << '\n'
#define br() p("")
#define pn(s) cout << (#s) << " " << (s) << '\n'
#define p_yes() p("YES")
#define p_no() p("NO")
#define SZ(x) ((int)(x).size())
#define SORT(A) sort(ALL(A))
#define RSORT(A) sort(ALL(A), greater<ll>())

void no(){p_no(); exit(0);}
void yes(){p_yes(); exit(0);}

const ll mod = 1e9 + 7;
const ll inf = 1e18;
const double PI = acos(-1);

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

    // input
    char a, b; cin >> a >> b;

    if(a==b){
      p("=");
    }
    else if(a>b){
      p(">");
    }
    else{
      p("<");
    }
    
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvi vector<vector<int> >
#define vvl vector<vector<ll> >
#define vl vector<ll>
typedef long long int ll;
typedef long double ld;
using namespace std;

int main(int argc, char const *argv[]) {
  string s;
  std::cin >> s;
  ll ans;
  if(s=="SUN") ans = 7;
  else if(s=="MON") ans = 6;
  else if(s=="TUE") ans = 5;
  else if(s=="WED") ans = 4;
  else if(s=="THU") ans = 3;
  else if(s=="FRI") ans = 2;
  else ans = 1;
  std::cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 888
#include <stdio.h>
#include <ctype.h>

#define STRMAX 101

int parseerror( char c );
int expression();
int term();
int number();
int factor();

char str[STRMAX] = {}, *tp;

int parseerror( char c )
{
	printf( "[ERROR] Parser cant parse %c\n", c );
	return -1;
}


// B;MB'1i;;$N<0$r%Q!<%9$7$FCM$rJV$9
int expression()
{
	int ret = term();

	for ( ; ; ) {
		if ( *tp == '+' ) {
			tp++;
			ret += term();
		} else if ( *tp == '-' ) {
			tp++;
			ret -= term();
		} else {
			break;
		}
	}
	return ret;
}

// B>h;;=|;;$N<0$r%Q!<%9$7$FCM$rJV$9
int term()
{
	int ret = factor();
	for ( ; ; ) {
		if ( *tp == '*' ) {
			tp++;
			ret *= factor();
		} else if ( *tp == '/' ) {
			tp++;
			ret /= factor();
		} else {
			break;
		}
	}
	return ret;
}

// B?t;z$NNs$r%Q!<%9$7$FCM$rJV$9
int number()
{
	int ret = 0;
	while ( isdigit( *tp ) ) {
		ret *= 10;
		ret += *tp - '0';
		tp++;
	}
	return ret;
}

// B3g8LIU$-J8;zNs$r%Q!<%9$9$k
int factor()
{
	int ret;
	if ( *tp == '(' ) {
		tp++;
		ret = expression();
		tp++; // )B$rHt$P$9
	} else {
		ret = number();
	}

	return ret;
}

int main()
{
	int n;
	int answer = 0;

	scanf( "%d\n", &n );
	while ( n > 0 ) {
		fgets( str, 100, stdin );
		tp = str;
		answer = expression();	
		printf( "%d\n", answer );	
		n--;
	}

	return 0;
}



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

string to_string(string s) {
  return '"' + s + '"';
}

string to_string(const char* s) {
  return to_string((string) s);
}

string to_string(bool b) {
  return (b ? "true" : "false");
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

void test_case() {
  int n, m;
  cin >> n >> m;
  vector<int> cost(m + 1);
  vector<vector<int>> locks(m + 1);
  for (int i = 1; i <= m; ++i) {
    int a, b;
    cin >> a >> b;
    cost[i] = a;
    locks[i].resize(b);
    for (auto& l : locks[i]) {
      cin >> l;
      --l;
    }
  }
  const long long LIM = 1e12;
  const int TAR = (1 << n) - 1;
  vector<vector<long long>> dp(m + 1, vector<long long>(1 << n, -1));
  function<long long(int, int)> solve = [&](int ind, int mask) {
    if (ind == m + 1) {
      return (mask == TAR ? 0 : LIM);
    }
    auto& ans = dp[ind][mask];
    if (ans == -1) {
      ans = LLONG_MAX;
      ans = min(ans, solve(ind + 1, mask));
      for (auto& l : locks[ind]) {
        mask |= 1 << l;
      }
      ans = min(ans, cost[ind] + solve(ind + 1, mask));
    }
    return ans;
  };
  long long ans = solve(1, 0);
  if (ans >= LIM) {
    ans = -1;
  }
  cout << ans << "\n";
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  test_case();
  return 0;
}


Measured memory_bytes: 32512
//In the name of God
//SMani24
#include<bits/stdc++.h>
using namespace std;

int x;

bool prime(int x) {
	if (x == 0 || x == 1)
		return 0;
	if (x == 2)
		return 1;
	for (int i = 2; i * i <= x; i++)
		if (!(x % i))
			return 0;
	return 1;
}
int main() {
	cin >> x;
	while (!prime(x))
		x++;
	cout << x << endl;
	return 0;
}


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

#define MAX_N 100'000
#define MAX_Q 100'000

using namespace std;

int R[MAX_Q];

int main() {
  int N, Q;
  string S;
  cin >> N >> Q >> S;
  vector<int> V;
  for (int i = 0; i < N - 1; ++i) {
    if (S.substr(i, 2) == "AC") {
      V.push_back(i);
    }
  }
  for (int i = 0; i < Q; ++i) {
    int l, r;
    cin >> l >> r;
    if (V.size() > 0) {
      --l;
      --r;
      auto low = lower_bound(V.begin(), V.end(), l);
      auto up = upper_bound(V.begin(), V.end(), r - 1) - 1;
      R[i] = (int)(up - V.begin()) - (int)(low - V.begin()) + 1;
    } else {
      R[i] = 0;
    }
  }
  for (int i = 0; i < Q; ++i) {
    printf("%d\n", R[i]);
  }
}

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

using ll = long long int;
using P = pair<ll,ll>;
constexpr int INF = 1<<30;

int main() {
    int n, s[2];
    cin >> n >> s[0] >> s[1];
    s[0]--; s[1]--;
    vector<vector<int> > g(n), d(2,vector<int>(n, INF));
    for(int i=0;i<n-1;i++){
        int a, b;
        cin >> a >> b;
        a--; b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    if(n%2){
        cout << "No" << endl;
        return 0;
    }
    for(int i=0;i<2;i++){
        d[i][s[i]] = 0;
        queue<int> que;
        que.push(s[i]);
        while(!que.empty()){
            int u = que.front();
            que.pop();
            for(auto v : g[u]){
                if(d[i][v] > d[i][u]+1){
                    d[i][v] = d[i][u]+1;
                    que.push(v);
                }
            }
        }
    }

    vector<bool> visited(n);
    visited[s[0]] = true;
    visited[s[1]] = true;
    int p[2] = {s[0], s[1]};
    bool ok = true;
    for(int i=0;i<n/2-1;i++){
        for(int j=0;j<2;j++){
            int ma = 0, nxt = -1;
            for(auto v : g[p[j]]){
                if(!visited[v] && d[j^1][v] > ma){
                    nxt = v;
                    ma = d[j^1][v];
                }
            }
            if(nxt == -1){
                ok = false;
                break;
            }
            visited[nxt] = true;
            p[j] = nxt;
        }
        if(!ok) break;
    }
    cout << (ok ? "Yes" : "No") << endl;
    return 0;
}



Measured memory_bytes: 8952
n=int(input())
a=list(map(int,input().split()))

import numpy as np

c=np.cumsum(a)
s=sum(a)

ans=float('inf')
index=0
for i in range(n):
    if abs(2*c[i]-s)<ans:
        ans=abs(2*c[i] - s)
        index = i

print(ans)

Measured memory_bytes: 37844
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
using namespace std;


int main(){
	int n;
    char a;

    cin >> n;
    for(int i=0;i<n;i++){
        cin >> a;
        if(a=='Y'){
            printf("Four\n");
            return 0;
        }
    }

    printf("Three\n");

	return 0;
}


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

int main()
{
  int64_t X;
  int64_t A,B;
  cin >> X;
  bool ans=false;
  
  for(A=-119;A<=119;A++){
    for(B=-119;B<=119;B++){
      if(pow(A,5)-pow(B,5)==X){
        ans=true;
        break;
      }
    }
      if(ans==true)
        break;
  }
  cout <<A<<" "<<B<<endl;
}

Measured memory_bytes: 4088
#include<stdio.h>
int main(void){
  
  int a,b;
  int x,y;
  int flag = 0;
  
  scanf("%d %d",&a,&b);
  
  for(x=0;x<100;x++){
    for(y=0;y<100;y++){
      if(x+y == a && 2*x+4*y == b) {
        flag = 1;
        break;
      }
    }
  }
  printf("%s",flag==1 ? "Yes" : "No");
  
 return 0; 
}

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



int main() {
	int N;
	cin >> N;
	vector<int>X(N);
	rep(0, N) {
		cin >> X[i];
	}
	rep(0, N) {
		if (X[i] % 2 == 0) {
			if (X[i] % 5 == 0)continue;
			else if (X[i] % 3 == 0)continue;
			else cout << "DENIED" << endl; return 0;
		}
	}
	cout << "APPROVED" << endl;
}


Measured memory_bytes: 256