akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <vector>
#include <regex>
#include <map>
#include <set>
#include <iomanip>

using namespace std;
using ll = long long;

int main(){
    int N,D,X;
    cin >> N >> D >> X;
    
    int A;
    int choco = N;
    for(int i=0;i<N;i++){
        cin >> A;
        for(int j=1;j*A+1<=D;j++){
            if(j*A+1<=D){
                choco++;
            }
            }
        }
    
    cout << choco+X << endl;
    return 0;
}


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

using namespace std;
typedef long long int ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef pair<int, int> P;
typedef pair<ll, ll> PL;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define fst first
#define snd second
#define pf push_front
#define pb push_back
#define eb emplace_back
#define ALL(obj) (obj).begin(), (obj).end()
#define debug(x) cout << #x << ": " << x << endl
#define out(x) cout << x << endl
//#define int long long int
const int MOD = 1000000007;
const ll LINF = (ll)1e18 - 1;
const int INF = 1e9 - 1;
const double EPS = 0.000000001;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

signed main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n, a, b;
  cin >> n >> a >> b;
  int ans = min(n * a, b);
  out(ans);
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,h;
    cin>>n>>h;
    vector<int>arr(n),brr(n);
    int maxx =0;
    for(int i=0; i<n; i++)
    {
        cin>>arr[i]>>brr[i];
        maxx = max(maxx,arr[i]);
    }
    sort(brr.rbegin(),brr.rend());
    int cnt =0;
    for(int i=0; i<n; i++)
    {
        if(brr[i]>=maxx)
        {
            cnt++;
            h-=brr[i];
            if(h<=0)
            {
                cout<<cnt<<endl;
                return 0;
            }
        }
    }
    if(h%maxx==0)
    {
        cnt+=h/maxx;
        cout<<cnt<<endl;
    }
    else
    {
        cnt+=h/maxx+1;
        cout<<cnt<<endl;
    }
}


Measured memory_bytes: 1024
#include <iostream>
#include <cstdio>
#include <math.h>
#include <algorithm>
#include <cstdlib>
#include <string>
using namespace std;

int main(){
    int x1,y1,x2,y2,x3,y3,x4,y4;
    cin>>x1>>y1>>x2>>y2;
    x4=x1+y1-y2;
    y4=y1+x2-x1;
    x3=x2+y1-y2;
    y3=y2+x2-x1;

    cout<<x3<<" "<<y3<<" "<<x4<<" "<<y4;
    
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
 
using namespace std;
 
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(vector<vector<T>> x){cerr<<"\n{"; int f=x.size();for(int i=0;i<f;i++){cerr<<"("; int g=x[i].size(); for(auto j:x[i]){cerr<<j; (--g!=0)?cerr<<",":cerr<<"";}cerr<<")\n";}cerr<<"}";}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void __print(vector<bool> x){cerr<<"{";int f=x.size();for(auto i:x){cerr<<i;(--f !=0)?cerr<<",":cerr<<"";}cerr<<"}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
 
#ifndef ONLINE_JUDGE
#define trace(x...) cerr << "[" << #x << "] = [", _print(x)
#else
#define trace(x...)
#endif
 
template<typename... T>
void read(T&... args) {
    ((cin >> args), ...);
}
 
template<typename... T>
void writ(T&&... args) {
    ((cout << args << " "), ...);
}
#define ull unsigned long long
#define ll long long
#define MOD 1000000007
#define INF (ll)1e18
#define IINF (int)1e9
#define EPS 1e-9

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n; cin>>n;
    int t=0;
    bool flag=false;
    for(int i=0;i<n;i++){
        int x,y; cin>>x>>y;
        if(y>x) swap(y,x);
        if(x-y==0){
            t++;
            if(t==3){
                flag=true;
            }
        }
        else{
            t=0;
        }
    }
    if(flag) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}



Measured memory_bytes: 3652
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        double  r = sc.nextDouble();
        double x = Math.PI;
        double area = r * r * x;
        double length = 2 * r * x;
        String kara = " ";
        System.out.printf("%.6f",area);
        System.out.print(kara);
        System.out.printf("%.6f",length);
        
    }
}


Measured memory_bytes: 28060
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const int INF = 1 << 29;
const int MOD = 1000000007;

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

    // 通路を表す隣接リスト
    vector<vector<int>> graph(n);
    int a, b;
    rep(i, m) {
        cin >> a >> b;
        a--;
        b--;
        // 繋がっている部屋を追加
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    // DFSのためのデータ構造
    // 部屋の深さ
    vector<int> depth(n, -1);
    queue<int> que;
    // BFSで最短路を復元する様子を図示すると木として表現できる
    // 一つ上の部屋
    vector<int> parent(n, -1);

    // 初期条件
    // スタートの部屋1
    depth[0] = 0;
    // 部屋1は距離0
    que.push(0);

    // BFS開始
    while (!que.empty()) {
        int v = que.front();
        que.pop();

        // 部屋vに対して繋がっている部屋を見ていく
        for (int nv : graph[v]) {
            // 既に調べてある場合は次の部屋へ
            if (depth[nv] != -1) continue;
            // 調べてないのなら距離を更新
            depth[nv] = depth[n] + 1;
            // 一つ上の部屋の番号を覚えておく
            parent[nv] = v;
            // キューに追加
            que.push(nv);
        }
    }

    // 必ず存在する
    cout << "Yes" << endl;
    for (int i = 1; i < n; i++) {
        cout << parent[i] + 1 << endl;
    }
}


Measured memory_bytes: 10636
from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from functools import lru_cache
import math

setrecursionlimit(10**6)
rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())
rlf = lambda: map(float, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')
MOD = 10**9 + 7

def main():
	n = int(rl())
	A = []
	mw, ms = 0, 0
	for _ in range(n):
		w, s, v = rli()
		mw, ms = max(mw, w), max(ms, s)
		A.append((w, s, v))
	ans = 0
	A.sort(key = lambda I: (I[0] + I[1]))
	maxs = mw + ms + 100
	dp = [0 for _ in range(maxs+1)]
	for w, s, v in A:
		for i in range(maxs, -1, -1):
			if i - w < 0: break
			if i - w > s: continue
			dp[i] = max(dp[i], dp[i-w] + v)
			ans = max(ans, dp[i])	
	print(ans)
	stdout.close()

if __name__ == "__main__":
	main()

Measured memory_bytes: 75016
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0; i<(n); i++)
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
int main(){
    string n; cin>>n;
    ll len=n.size();
  	n='0'+n;
    ll res=0;
    ll kuriagari=0;
    rep(i,len){
        ll kurai=n[len-i]-'0';
        if(kurai+kuriagari==5 && n[len-1-i]-'0'>=5){
            res+=10-kurai-kuriagari;
            kuriagari=1;
        }else if(kurai+kuriagari<=5){
            res+=kurai+kuriagari;
            kuriagari=0;
        }else if(kurai+kuriagari==10){
            kuriagari=1;
        }else{
            res+=10-kurai-kuriagari;
            kuriagari=1;
        }
    }
    if(kuriagari==1) res++;
    cout<<res<<endl;
    return 0;
}

Measured memory_bytes: 2308
h, w, a, b = map(int, raw_input().split())
mod = 1000000007
inv = [0] * (h+w)
fact = [0] * (h+w)

def ex(x, y):
    if y == 0: return 1
    elif y == 1: return x % mod
    elif y % 2 == 0: return ex(x, y/2) ** 2 % mod
    else: return ex(x, y/2) ** 2 * x % mod

# factorial
fact[0]=1
for j in range(1, h+w):
    fact[j] = fact[j-1] * j % mod

inv[h+w-1]=ex(fact[h+w-1],mod-2)
for j in reversed(range(h+w-1)):
    inv[j]=inv[j+1]*(j+1)%mod

def nck(x, y):
  return fact[x] * inv[y] * inv[x-y] % mod

su = 0

for j in range(h-a):
  su = (su+nck(b-1+j, b-1)*nck(h-1-j+w-1-b, w-1-b)) % mod

print(su)


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


int main() {
    int N, M;
    std::cin >> N >> M;
    std::vector<int> vec(N - 1, 0);
    for (int i = 0; i < M; i++) {
        int a, b;
        std::cin >> a >> b;
        a--; b--;
        if (a > b) {
            std::swap(a, b);
        }
        for (int i = a; i < b; i++) {
            vec[i]++;
        }
    }

    for (auto val : vec) {
        if (val % 2 != 0) {
            std::cout << "NO" << std::endl;
            return 0;
        }
    }
    std::cout << "YES" << std::endl;
}


Measured memory_bytes: 3788
#define _USE_MATH_DEFINES
#define INF 0x3f3f3f3f

#include <iostream>
#include <cstdio>
#include <sstream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>
#include <cctype>
#include <utility>
  
using namespace std;
  
typedef long long ll;
typedef pair <int,int> P;
  
static const double EPS = 1e-8;
  
static const int tx[] = {0,1,0,-1};
static const int ty[] = {-1,0,1,0};

int direction[1001][1001];
int dp[1001][1001];

int main(){
  int H,W,n;
  while(~scanf("%d %d %d",&H,&W,&n)){
    if(H == 0 && W == 0) break;

    memset(direction,0,sizeof(direction));
    memset(dp,0,sizeof(dp));

    for(int y=0;y<H;y++){
      for(int x=0;x<W;x++){
	scanf("%d",&direction[y][x]);
      }
    }
    
    dp[0][0] = n-1; //offset
    for(int y=0;y<H;y++){
      for(int x=0;x<W;x++){
	//dir
	//0 v
	//1 ->
	if(y+1 < H) dp[y+1][x] += (dp[y][x] + (direction[y][x] == 0 ? 1:0)) / 2;
	if(x+1 < W) dp[y][x+1] += (dp[y][x] + (direction[y][x] == 1 ? 1:0)) / 2;
      }
    }
    
    int x = 0;
    int y = 0;
    while(y < H && x < W){
      if((dp[y][x] + direction[y][x]) % 2 == 0) y++;
      else if((dp[y][x] % 2 + direction[y][x]) % 2 == 1) x++;
    }
    printf("%d %d\n",y+1,x+1);
  }
}

Measured memory_bytes: 9024
#include <bits/stdc++.h>
#define REP(i, n) for(long long i=0; i<n; i++)
#define REPR(i, n) for(long long i=n-1; i>=0; i--)
#define FOR(i, m, n) for(long long i=m; i<=n; i++)
#define FORR(i, m, n) for(long long i=m; i>=n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define VSORTR(v) sort(v.rbegin(), v.rend());
#define ALL(v) (v).begin(),(v).end()
#define FIN ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;
const ll mod = 1e9+7;
const ll inf = 1e15;


int main(){FIN

    ll a,b;cin>>a>>b;
    cout<<a*b - a - b + 1<<endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;

public class Main {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		int L = scanner.nextInt();
		String[] S = new String[N];
		Map<String, String> map = new TreeMap<String,String>();
		for(int i=0;i<N;i++) {
			S[i] = scanner.next();
			if(map.get(S[i])==null) {
				map.put(S[i], S[i]);
			}
			else {
				map.put(S[i]+i, S[i]);
			}
		}
		L=L+1;
		for(String s:map.values()) {
			System.out.print(s);
		}
		System.out.println();
		scanner.close();
	}

}


Measured memory_bytes: 23764
from itertools import zip_longest

n, m = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(m)]

A.sort()
BC.sort(key=lambda x: -x[1])

stack = []
i = 0
while len(stack) < n and i < m:
  for _ in range(BC[i][0]):
    stack.append(BC[i][1])
    if len(stack) >= n:
      break
  i += 1

ans = 0
for a, s in zip_longest(A, stack, fillvalue=0):
  ans += max(a, s)

print(ans)

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


int main() {
    string s;
    cin >> s;
    for(int i = s.length()-1;i>=0;i--){
        string base = s.substr(0,i);
        if(i%2)continue;
        string f = base.substr(0,base.length()/2);
        string b = base.substr(base.length()/2);
        if(f == b){
            cout << base.length() << endl;
            return 0;
        }
    }
    return 0;
}
/*
やっほい！
　　　　　　　やほほい！
　　　　+　　 　*
　　　 ∧∧　　. ∧∞∧　*
*　ヽ(=´ω｀)人(´ω｀*)ﾉ
　.～（ O x.） （ 　 O)～　+
。*　 　∪　　　　∪
*/

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <cstring>
#include <iostream>
#include <bits/stdc++.h>
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std;
typedef long long ll;

int main() {
    int N, K, i, j, ans=0;

    cin >> N >> K;

    vector<int> d(K+1);
    vector<vector<int> > A(K+1, vector<int>(N+1, 0));
    vector<int> ns(N+1, 0);

    for(i=1; i<=K; i++) {
        cin >> d[i];
        for(j=1; j<=d[i]; j++) {
            cin >> A[i][j];
            ns[A[i][j]]++;
        }
    }

    for(i=1; i<=N; i++) {
        if(ns[i] == 0) {
            ans++;
        }
    }

    cout << ans << endl;
    
}

Measured memory_bytes: 3644
class BigCombination(object):
    __slots__ = ["mod", "factorial", "inverse"]

    def __init__(self, mod: int = 10**9+7, max_n: int = 10**6):
        fac, inv = [1], []
        fac_append, inv_append = fac.append, inv.append

        for i in range(1, max_n+1):
            fac_append(fac[-1] * i % mod)

        inv_append(pow(fac[-1], mod-2, mod))

        for i in range(max_n, 0, -1):
            inv_append(inv[-1] * i % mod)

        self.mod, self.factorial, self.inverse = mod, fac, inv[::-1]

    def get_combination(self, n, r):
        return self.factorial[n] * self.inverse[r] * self.inverse[n-r] % self.mod

    def get_permutation(self, n, r):
        return self.factorial[n] * self.inverse[n-r] % self.mod

import math
Big = BigCombination()
n, d = map(int, input().split())
def cal(a,b):
    m = min(a,b)
    M = max(a,b)
    res = 0
    T = (m+M)//3
    if (a+b)%3 == 0 and M<=m*2:
        res = 2*M - m
        res = res// 3
        k = Big.get_combination(T, res)
        print(k)
        
    else:
        print(0)

cal(n,d)

Measured memory_bytes: 90044
#include <iostream>
using namespace std;
int main(void){
    int N;
    cin >> N;
    
    int d[N];
    for(int i = 0;i < N;i++) { cin >> d[i]; }
    
    int swap;
    for(int i = 0;i < N - 1;i++) {
        for(int j = 0; j < N - 1 - i;j++) {
            if(d[j] > d[j + 1]) {
                swap = d[j];
                d[j] = d[j + 1];
                d[j + 1] = swap;
            }
        }
    }
    
    int dan = 1;
    for(int i = 0;i < N - 1;i++){
        if(d[i] != d[i + 1]) dan++;
    }
    
    cout << dan;
    
    return 0;
}


Measured memory_bytes: 256
import java.util.*;
import java.lang.*;

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
    	Scanner in = new Scanner(System.in);
		int week = in.nextInt();
		int dept = 100000;
		
		for (int i = 0; i < week; i++) {
			// 利子の計算
			dept = (int)(dept * 1.05);
			// 1,000円未満は切り上げ
			if (dept % 1000 != 0) {
				dept = (dept / 1000) * 1000;
				dept += 1000;
			}
		}
		
		System.out.println(dept);
		
	}
}

Measured memory_bytes: 17276
#include <algorithm>
#define _USE_MATH_DEFINES
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include<list>
#include<map>
#include<utility>
#include<tuple>
#include<numeric>
#include<set>

#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(a) a.begin(),a.end()
using namespace std;

int main()
{
	int n, T;
	cin >> n >> T;
	int ans = 1001;
	int c, t;
	rep(i, n) {
		cin >> c;cin >> t;
		if (t <= T) {
			ans = min(ans, c);
		}
	}
	if (ans == 1001) {
		cout << "TLE" << endl;
	}
	else {
		cout << ans << endl;
	}
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
struct P
{
    //string r;
    int x,y,z;

    bool operator<(const P &a)const{
       // if(y!=a.y)
       // return y>a.y;
       return x>a.x;
//        return z>a.z;
    }
};
struct S
{
    //double a;
    int x,y;
};
vector<P> v[510];

int a,b,c,i,k,d,n,p,m,e,dy[15]={0,0,-1,1},dx[15]={-1,1};
int l[5010][1102];
int o[3013];
int dz[10]={0,0,0,0,1,-1};

long long x,y,z,mod=1000000007;
P u[1021600];
int j[40040];
queue<int> q;
queue<int> q1;
stack<int> s,s1;
//queue<P> q;

//deque<int> de;
//'1'==49;
//'A'==65;
//'a'==97;
//unordered_
//map<int,long long > p;
string r;
//char r[1000310];
//char r1[1000222];
bool as(P a,P b)
{
    return max(a.x,-a.x)<max(b.x,-b.x);
}



int g(int a,int b)
{
    n=l[a][0]*l[a][3]+l[a][2]*l[b][1]+l[b][0]*l[a][1]-(l[a][1]*l[a][2]+l[a][3]*l[b][0]+l[b][1]*l[a][0]);
    m=l[a][0]*l[a][3]+l[a][2]*l[b][3]+l[b][2]*l[a][1]-(l[a][1]*l[a][2]+l[a][3]*l[b][2]+l[b][3]*l[a][0]);
    if(n*m<0) return 0;
    return 1;
}

int f(int a)
{
    if(j[a]==a) return a;
    return j[a]=f(j[a]);
}

int main()
{
    scanf("%d %d",&a,&b);
    if(a%b==0) puts("-1");
    else printf("%d",a);
}



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

#define ull unsigned long long
#define ll long long
#define ld long double
#define endl << "\n"
#define sp << " "
#define spp << " " <<
#define allv(v) v.begin(),v.end()
#define lmax 9223372036854775807
#define lmin -9223372036854775807
#define lopi() for(i=0;i<n;++i)
#define loi(a,b) for(i=a;i<b;++i)
#define lopj() for(j=0;j<n;++j)
#define loj(a,b) for(j=a;j<b;++j)
#define ft first
#define sd second
#define pb push_back
#define pf push_pront
#define mod 1000000007
#define lower(str) transform(str.begin(), str.end(), str.begin(), ::tolower);
#define upper(str) transform(str.begin(), str.end(), str.begin(), ::toupper);
#define mset(a,b) memset(a,b,sizeof(a))
#define crap ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define PI acos(-1)

int main(){
//	crap ;
    int timer;
    // cin >>timer;
    timer=1 ;
    while(timer--){
    	ll n,m,i,j,k,a,b ;
    	cin >>k>>n;
        set<ll> st ;
        for(i=1;i<=101;++i)
            st.insert(i) ;
    	for(i=0;i<n;++i){
    		cin >>j ;
    		st.erase(j) ;
    	}
        ll dif=k,ans=0 ;
        for(auto tt:st){
            if( dif > abs(tt-k) ){
                dif = abs(tt-k) ;
                ans = tt ;
            }
        }
        cout << ans endl ;
    }
}


Measured memory_bytes: 3640
import java.util.Arrays;
import java.util.*;
public class Main{
  public static void main(String args[]){
    Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      String ans = "Three";
      for(int i=0;i<n;i++){
        if(sc.next().equals("Y")){
          ans = "Four";
          break;
        }
      }
      System.out.println(ans);
    }
}


Measured memory_bytes: 21844
#include <stdio.h>

int main(){
  
  int a , b , c , d;
  
  scanf("%d %d %d" , &a , &b , &c);
  
  if (a > b) {
    d = a;
    a = b;
    b = d;
  }
  
  if (b > c) {
    d = b;
    b = c;
    c = d;
  }
  
  if (a > b) {
    d = a;
    a = b;
    b = d;
  }
  
  printf("%d %d %d\n" , a , b , c);
  
  return 0;
}

Measured memory_bytes: 596
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define repi(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i,a) repi(i,0,a)
#define repdi(i,a,b) for(ll i=(a)-1;i>=(b);--i)
#define repd(i,a) repdi(i,a,0)
#define itr(it,a) for( auto it = (a).begin(); it != (a).end(); ++it )
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

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

constexpr ll INF = 1ll<<60;

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

template<class S, class T>
std::ostream& operator<< ( std::ostream& out, const std::pair<S,T>& a )
{ std::cout << '(' << a.first << ", " << a.second << ')'; return out; }

template<class T>
std::ostream &operator<< ( std::ostream& out, const std::vector<T>& a )
{ std::cout << '['; rep( i, a.size() ){ std::cout << a[i]; if( i != a.size()-1 ) std::cout << ", "; } std::cout << ']'; return out; }

ll K;
bool used[1000010];

int main()
{
  std::cin >> K;

  ll n = 7;
  ll ans = 1;

  n %= K;

  while( true ) {
    if( used[n] ) {
      puts("-1");

      return 0;
    }

    if( !n ) {
      std::cout << ans << std::endl;

      return 0;
    }

    used[n] = true;
    ++ans;
    n = (n*10)%K;
    n = (n+7)%K;
  }

  return 0;
}

Measured memory_bytes: 4552
using System;

public class hello
{
    public static void Main()
    {
        while (true)
        {
            string[] line = Console.ReadLine().Trim().Split(' ');
            var n = int.Parse(line[0]);
            var m = int.Parse(line[1]);
            if (n == 0 && m == 0) break;
            var r = new string[n, 3];
            for (int i = 0; i < n; i++)
            {
                line = Console.ReadLine().Trim().Split(' ');
                for (int j = 0; j < 3; j++) r[i, j] = line[j];
            }
            getAns(r, n, m);
        }
    }
    static bool check(string r, string t)
    {
        for (int i = 0; i < 8; i++)
            if (r[i] != '?' && r[i] != t[i]) return false;
        return true;
    }
    static void getAns(string[,] r, int n, int m)
    {
        var count = 0;
        var ans = "";
        for (int i = 0; i < m; i++)
        {
            var s = Console.ReadLine().Trim();
            string[] line = s.Split(' ');
            var t1 = line[0];
            var t2 = line[1];
            var ok = false;
            for (int j = 0; j < n; j++)
                if (r[j, 0] == "permit")
                {
                    if (check(r[j, 1], t1) && check(r[j, 2], t2)) ok = true;
                }
                else
                {
                    if (check(r[j, 1], t1) && check(r[j, 2], t2)) ok = false;
                }
            if (ok) { count++; ans += s + "\n"; }
        }
        Console.WriteLine(count);
        Console.Write(ans);
    }
}


Measured memory_bytes: 32220
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <iostream>
#include <utility>
#include <vector>
#include <list>
#include <algorithm>
using namespace std;

int main()
{
    long long int N;
    scanf("%lld", &N);

    long long maximam;
    scanf("%lld", &maximam);
    long long minimam = maximam;

    for (long long i = 1; i < N; i++)
    {
        long long A;
        scanf("%lld", &A);
        maximam = max(maximam, A);
        minimam = min(minimam, A);
    }

    printf("%lld", maximam - minimam);
}


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

int main(void)
{
    int n;
    cin >> n;
    vector<long long int>a;
    for(int i=0;i<n;i++)
    {
        long long int t = 0ll;
        cin >> t;
        a.push_back(t);
    }
    // a1(a2+a3+a4+...+aN) + a2(a3+a4+a5+...+aN)
    long long int mod = 1000000007;
    long long int itr_sum = a[n-1];
    long long int ans = 0;
    for(int i=n-2;i>=0;i--)
    {
        ans += (itr_sum*a[i])%mod;
        ans %= mod;
        itr_sum += a[i];
        itr_sum = itr_sum%mod; 
    }
    cout <<ans;
    return 0;
}


Measured memory_bytes: 5260
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;

struct DATA{
  int n;
  string s;
};

void Devide(vector<string>&, string);
void Search(vector<DATA>&, string);
void Print(vector<DATA>);
bool Compare(const DATA&, const DATA&);

int main(){
  int i, n;
  string s;
  vector<string> _data;
  vector<DATA> data;

  while(1){
    cin >> n;
    if(n == 0) break;

    for(i=-1; i<n; ++i){
      getline(cin, s);
      if(i != -1) Devide(_data, s);
    }
    cin >> s;
    for(i=0; i<_data.size(); ++i){
      if(_data[i][0] == s[0])
	Search(data, _data[i]);
    }

    if(data.size() == 0){
      cout << "NA" << endl;
    }else{
      sort(data.begin(), data.end(), Compare);
      Print(data);
    }

    _data.clear();
    data.clear();
  }
  return 0;
}

void Devide(vector<string>& data, string s){
  string str;
  string::iterator i, j;
  i = s.begin();
  while(1){
    j = find(i, s.end(), ' ');
    copy(i, j, back_inserter(str));
    data.push_back(str);
    if(j == s.end()) break;
    i = j+1;
    str.clear();
  }
}

void Search(vector<DATA>& data, string s){
  int i, x;
  DATA _data;
  for(i=0, x=0; i<data.size(); ++i){
    if(s == data[i].s){
      ++data[i].n;
      x = 1;
      break;
    }
  }
  if(x == 0){
    _data.n = 1;
    _data.s = s;
    data.push_back(_data);
  }
}

void Print(vector<DATA> data){
  int i;
  if(data.size() < 5){
    for(i=0; i<data.size()-1; ++i)
      cout << data[i].s << " ";
    cout << data[data.size()-1].s << endl;
  }else{
    for(i=0; i<4; ++i)
      cout << data[i].s << " ";
    cout << data[4].s << endl;
  }
}

bool Compare(const DATA& x, const DATA& y){
  if(x.n == y.n)
    return x.s < y.s;
  else
    return x.n > y.n;
}

Measured memory_bytes: 964
#include <iostream>
#include <algorithm>
#include <math.h> 
#include <string>
#include <iomanip>
#include <vector>
#include <chrono>
#include <cstdlib>
#include <bitset>
using namespace std;

int main(){
    int n;
    int a[30];
    int b[30];
    int c[30];
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < n; i++) cin >> b[i];
    for(int i = 0; i < n-1; i++) cin >> c[i];

    int total = 0;
    for(int i = 0; i < n; i++) total += b[a[i]-1];
    //cout << total << endl;

    for(int i = 0; i < n-1; i++){
        if(a[i+1]-a[i] == 1) total += c[a[i]-1];
    }
    cout << total << endl;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define MOD 1000000007
#define PI 3.141592653589793
int dx[] = {0,1,-1,0,1,-1,1,-1};
int dy[] = {1,0,0,-1,1,-1,-1,1};

int main(){
    int n;
    cin >> n;
    vector<string> v(n);
    for(int i = 0; i < n; i++)
        cin >> v[i];
    map<char, int> m;
    for(auto s: v){
        map<char, int> m2;
        for(auto c: s){
            m2[c]++;
        }
        for(auto p: m2){
            if(m[p.first] == 0 || m[p.first] > p.second)
                m[p.first] = p.second;
        }
    }
    for(auto s: v){
        for(auto p: m){
            if(s.find(p.first) == string::npos)
                m[p.first] = 0;
        }
    }
    string ans = "";
    for(auto p: m){
        for(int i = 0; i < p.second; i++)
            ans += p.first;
    }
    sort(ans.begin(), ans.end());
    cout << ans << endl;
}


Measured memory_bytes: 764
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
ll H[200005];
int main() {
  ios::sync_with_stdio(false);
  int N, K;
  cin >> N >> K;
  for (int i = 0; i < N; i++) {
    cin >> H[i];
  }
  sort(H, H+N);
  ll S = 0;
  for (int i = 0; i < N - K; i++) {
    S += H[i];
  }
  cout << S << endl;
}

Measured memory_bytes: 1792
import Control.Applicative
import Data.ByteString.Char8 (ByteString)
import qualified Data.ByteString.Char8 as B
import Data.List
import Data.Char (isSpace)

main :: IO ()
main = solve <$> tail <$> f >>= putStrLn
  where
    f = readil B.readInt <$> B.getLine

solve :: [Int] -> String
solve as = f (0, 0, 0, 0, 0) . map (\x -> (head x, length x)) . group $ as
  where
    f (pl, bs, hs, pk, dp) xs@((h1,_):(h2,l2):(h3,_):_)
      | h2 > h1 && h2 > h3 && l2 > 1 = f (pl+1, bs, hs, pk, dp) (tail xs)
      | h2 < h1 && h2 < h3 && l2 > 1 = f (pl, bs+1, hs, pk, dp) (tail xs)
      | ((h1 < h2 && h2 < h3) || (h1 > h2 && h2 > h3)) && l2 > 1 = f (pl, bs, hs+1, pk, dp) (tail xs)
      | h2 > h1 && h2 > h3 = f (pl, bs, hs, pk+1, dp) (tail xs)
      | h2 < h1 && h2 < h3 = f (pl, bs, hs, pk, dp+1) (tail xs)
      | otherwise = f (pl, bs, hs, pk, dp) (tail xs)
    f (pl, bs, hs, pk, dp) _ = unwords . map show $ [pl, bs, hs, pk, dp]

readil :: Integral a =>  (ByteString -> Maybe (a, ByteString)) -> ByteString -> [a]
readil f = unfoldr g
  where
    g s = do
      (n, s') <- f s
      return (n, B.dropWhile isSpace s')



Measured memory_bytes: 9220
#include <iostream>
#include <utility>
#include <map>
#include <vector>
#include <algorithm>
#include <queue>
#include <math.h>
#include <stack>
#include <set>
#include <deque>
#include <cmath>

using namespace std;
typedef long long ll;
ll mod = 1e9+7;
//ll mod = 998244353;
#define rep(i,n) for(int i = 0; i < (n); ++i)

int main() {
    int n;
    cin >> n;
    vector<int> l(n);
    rep(i, n) cin >> l[i];
    sort(l.begin(), l.end());
    int ans = 0;
    rep(i, n) {
        for (int j = i + 1; j < n; ++j) {
            int idx = lower_bound(l.begin(), l.end(), l[i] + l[j]) - l.begin() - 1;
            ans += max(0, idx - j);
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3600
/*BISMILLAH
THE WHITE WOLF*/

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

#define io ios_base::sync_with_stdio(false);
#define ll long long
#define ull unsigned long long
#define vi vector<int>
#define vll vector<long long>
#define pb push_back
#define mod 1000003
#define pii pair<int, int>

int main()
{
    int n, m;
    cin >> n >>m;
    int dp[n][m]; char inp[n][m];
    for(int i  =0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            cin >> inp[i][j];
            if(inp[i][j]=='.')
                dp[i][j] = 0;
            else
                dp[i][j]  =1;
        }
    }
    for(int i = 1; i < m; i++)
    {
        if(inp[0][i-1] == '#')
            dp[0][i] = dp[0][i-1];
        else
            dp[0][i] +=dp[0][i-1];
        //cout <<"i: " <<0<<" j: " << i << " dp: " << dp[0][i] << endl;
    }
    for(int i = 1; i < n; i++)
    {
        if(inp[i-1][0] == '#')
            dp[i][0] = dp[i-1][0];
        else
           dp[i][0] += dp[i-1][0];
        //cout <<"i: " <<i<<" j: " << 0<< " dp: " << dp[i][0] << endl;
    }

    for(int i = 1; i < n;i++)
    {
        for(int j =1; j< m; j++)
        {
            int up, down;
            if(inp[i-1][j] == '#')
                up = dp[i-1][j];
            else
                up = dp[i-1][j] + dp[i][j];
            if(inp[i][j-1] == '#')
                down = dp[i][j-1];
            else
                down = dp[i][j-1] + dp[i][j];
            dp[i][j] = min(up, down);
            //cout <<"i: " << i << " j; " << j << " up: " << up << " down: " << down <<" dp: "<<dp[i][j] <<endl;
        }
    }
    cout << dp[n-1][m-1];
    return 0;
}

Measured memory_bytes: 256
/*
 *  Created on: 29 / 8 / 2020
 *  Author:     Eslam Waheed
 */

#define _CRT_SECURE_NO_WARNINGS
//#define __USE_MINGW_ANSI_STDIO

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

#define Eslam__Waheed ios_base::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);

#define ll   long long
#define ull  unsigned ll
#define ld   long double

#define all(c)   c.begin(), c.end()
#define rall(c)  c.rbegin(), c.rend()
#define stp(n)   cout << fixed << setprecision(n);
#define iq(v)    v.resize(unique(v.begin(),v.end())-v.begin())
#define sz(s)    s.size()
#define endl     '\n'

//ll gcd(ll a, ll b) { return !b ? abs(a) : gcd(b, a % b); }
//ll lcm(ll a, ll b) { return abs(a / gcd(a, b)) * b; }

//const ld PI = acos(-1);
const ll mod = 1e9 + 7;
//const ld EPS = 1e-8;
/*
 you can ^_^ (•‿•)

( إن الله وملائكته يصلون على النبي يا أيها الذين آمنوا صلوا عليه وسلموا تسليما )
*/
int main()
{
	//stp(0)
	Eslam__Waheed;
	ll n; cin >> n;
	vector<ll>v(n);
	for (auto& it : v)
	{
		cin >> it;
	}
	vector<ll>temp(v);
	for (int i = n - 1; i > 0; i--)
	{
		v[i - 1] += v[i];
	}
	ll ans = 0;
	for (int i = 0; i < n - 1; i++)
	{
		ans = ((ans % mod) + ((v[i + 1] % mod) * (temp[i] % mod)) % mod) % mod;
	}
	cout << ans;
}

Measured memory_bytes: 6344
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;


int main(){
int n;
  cin>>n;
  int N =n%10;
  if(N ==3){
    cout << "bon"<<endl;
  }else if(N ==0 ||N ==1||N==6||N==8){
    cout <<"pon"<<endl;
  }else{
    cout <<"hon"<<endl;
  }
}

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

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
const int INF = 1<<29;

typedef pair<int,int> pii;

int sum[33][33];
int ba[33][33];
int h,w,s;
int S;
pii memo[33][33][33][33];

int sum2(int x1,int y1, int x2,int y2){
  int res = sum[x2][y2];
  if (x1) res -= sum[x1-1][y2];
  if (y1) res -= sum[x2][y1-1];
  if (x1&&y1) res += sum[x1-1][y1-1];
  return res;
}

pii solve(int x1,int y1, int x2,int y2) {
  if (memo[x1][y1][x2][y2].first >= 0) return memo[x1][y1][x2][y2];
  if (S - sum2(x1,y1,x2-1,y2-1) > s) return pii(0,0);
  
  int res = 1;
  int hoge = s - (S - sum2(x1,y1,x2-1,y2-1));
  for (int x=x1+1; x<x2; ++x) {
    pii aa = solve(x1, y1, x, y2);
    pii bb = solve(x, y1, x2, y2);
    int a = aa.first, b = bb.first;
    if (a&&b) {
      if (res < a+b) {
        res = a+b;
        hoge = min(aa.second, bb.second);
      } else if (res == a+b) {
        hoge = max(hoge, min(aa.second,bb.second));
      }
    }
  }
  for (int y=y1+1; y<y2; ++y) {
    pii aa = solve(x1, y1, x2, y);
    pii bb = solve(x1, y, x2, y2);
    int a = aa.first, b = bb.first;
    if (a&&b) {
      if (res < a+b) {
        res = a+b;
        hoge = min(aa.second, bb.second);
      } else if (res == a+b) {
        hoge = max(hoge, min(aa.second,bb.second));
      }
    }
  }
  return memo[x1][y1][x2][y2] = pii(res,hoge);
}

int main() {

  while(cin >> h>>w>>s,h) {

    REP(y,h) {
      REP(x,w) {
        cin >> ba[x][y];
      }
    }

    REP(y,h) {
      REP(x,w) {
        int tmp = ba[x][y];
        if (x) tmp += sum[x-1][y];
        if (y) tmp += sum[x][y-1];
        if (x&&y) tmp -= sum[x-1][y-1];
        sum[x][y] = tmp;
      }
    }
    S = sum[w-1][h-1];
    REP(x1,w)REP(x2,w+1)REP(y1,h)REP(y2,h+1)
      memo[x1][y1][x2][y2] = pii(-1,0);
    pii res = solve(0,0,w,h);
    cout << res.first << " "  << res.second << endl;
  }
}

Measured memory_bytes: 9000
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i, a, b) for(ll i = (ll)a; i <= (ll)b; i++)
#define DEC(i, a, b) for(ll i = (ll)a; i >= (ll)b; i--)
typedef pair<ll, ll> pi;
typedef pair<ll, pi> pii;
#define f first
#define s second
#define pb push_back

ll h, w, ans;

int main() {
	cin >> h >> w;
	if (h == 1 or w == 1) cout << 1;
	else cout << (h*w+1)/2;
}


Measured memory_bytes: 256
#include<cstdio>
using namespace std;
int main(){
    int n,t,x,y;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&t,&x,&y);
        if(x+y>t)        {
            printf("No\n");
            return 0;
        }
        if((x+y)%2==0&&t%2==1){
            printf("No\n");
            return 0;
        }
        if((x+y)%2==1&&t%2==0){
            printf("No\n");
            return 0;
        }
    }
    printf("Yes\n");
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define int long long
#define double long double
#define mod 1000000007
#define F first
#define S second
#define P pair<long long,long long>
#define all(a) a.begin(),a.end()
#define INF 1000000000000000000
using namespace std;

signed main(){
    int n; cin>>n;
    string s; cin>>s;
    int a=0,b=0;
    rep(i,n){
        if(s.at(i)=='R')a++;
        else b++;
    }
    cout<<((a>b)?"Yes":"No")<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;

int main()
{
	int a,b;
	string s;
	stringstream ss;
	cin>>s;
	ss<<s.substr(0,2);
	ss>>a;
	ss.clear();
	ss<<s.substr(2,2);
	ss>>b;
	if(a>=1&&a<=12&&b>=1&&b<=12)cout<<"AMBIGUOUS"<<endl;
	else if(b>=1&&b<=12)cout<<"YYMM"<<endl;
	else if(a>=1&&a<=12)cout<<"MMYY"<<endl;
	else cout<<"NA"<<endl;
	return 0;
}


Measured memory_bytes: 256
/*
 ID: bradyawn
 PROG: contest
 LANG: C++11
 */

#include <iostream>
#include <algorithm>
#include <iomanip>
#include <fstream>
#include <vector>
#include <deque>
#include <string>
#include <cmath>
#include <map>
#include <utility>
#include <algorithm>
#include <set>
#include <ctime>
#include <queue>
#include <stack>
#include <bitset>
#include <random>
#include <cstring>

using namespace std;

typedef long long ll;
typedef pair<int,int> i2;
typedef pair<ll,ll> ll2;

int main()
{
    //ifstream inf("");
    //ofstream outf("");
    //cout << setprecision(10);
    ios_base::sync_with_stdio(0); cin.tie(0);
    
    int n;
    cin >> n;
    
    vector<int> a(n);
    vector<int> b(n);
    multiset<int> d;
    
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];
    
    for (int i = 0; i < n; i++) d.insert(a[i]-b[i]);
    
    d.erase(0);
    
    while (!d.empty())
    {
        if (*d.begin() > 0)
        {
            cout << "No\n";
            return 0;
        }
        
        if (d.size() == 1)
        {
            cout << "Yes\n";
            return 0;
        }
        
        int gotem = *d.begin();
        int getem = *d.rbegin();
        
        d.erase(d.begin());
        d.erase(--d.end());
        
        int diff = min(abs(gotem/2), abs(getem));
        diff = max(diff, 1);
        
        gotem += 2*diff;
        getem -= diff;
        
        d.insert(gotem);
        d.insert(getem);
        
        d.erase(0);
    }
    
    cout << "Yes\n";
    
    return 0;
    
}




Measured memory_bytes: 768
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif

// C++
#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>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif




#define int long long
#define rng(i,l,r) for(size_t i=(l);i<(r);++i)
#define rep(i,n) rng(i,0,n)
#define gnr(i,l,r) for(size_t i=(r)-1;i>=(l);i--)
#define per(i,b) gnr(i,0,b)
#define ALL(obj) (obj).begin(), (obj).end()   //1,2,3,...
#define rALL(obj) (obj).rbegin(), (obj).rend()//...,3,2,1

using namespace std;
//using ll = long long;


const int MOD = 1000000007;
const int INF = 1e18;

const int dx4[4] = {1, 0, -1, 0};
const int dy4[4] = {0, 1, 0, -1};
const int dx8[8] = {1,1,0,-1,-1,-1,0,1};
const int dy8[8] = {0,1,1,1,0,-1,-1,-1};

const double pi = acos(-1);



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


using Graph = vector<vector<int>>;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
//*max_element(ALL(vector))
//count(ALL(vector),num) -> n



int notCD(int x,int c, int d){
    if(x<=0) return 0;
    int cdlcm = c*d/gcd(c,d);
    return (x - (x/c + x/d - x/cdlcm));
}


void solve(){
    
    // remove the bottom 3 lines when you submit this code.
    std::ifstream in("sample.txt");
    std::cin.rdbuf(in.rdbuf());

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

    int a,b,c,d; cin >> a >> b >> c >> d;
    
    cout << notCD(b, c, d) - notCD(a-1, c, d) << endl;
    
    
    
  
}



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



Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<cassert>
#include<math.h>
#include<complex>
#include<algorithm>
#include<utility>
#include<queue>
#include<string.h>
#include<string>
#include<set>
#include<map>
#include<unordered_map>
#include<functional>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const ll INF=2e18;
const ll MOD=1e9+7;

ll N,K;
ll a[100010],b[100010];
int main(){
    cin>>N>>K;
	ll maxA=0;
    for(ll i=0;i<N;i++){
		cin>>a[i]>>b[i];
		maxA=max(maxA,a[i]);
    }
	ll maxBit=0;
	for(ll i=0;(1ll<<i)<=maxA;i++){
		if((1ll<<i)&maxA)maxBit=i;
	}
	maxBit=30;
	ll ans=0;
	for(ll i=0;i<N;i++){
		bool f=true;
		for(ll bit=0;bit<=maxBit;bit++){
			if( ((1ll<<bit)&K)==0 && ((1ll<<bit)&a[i])!=0 ){
				f=false;
				break;
			}
		}
		if(f)ans+=b[i];
	}
	for(ll bit=maxBit;bit>=0;bit--){
		if(((1ll<<bit)&K)==0)continue;
		ll sum=0;
		for(ll i=0;i<N;i++){
			if((1ll<<bit)&a[i])continue;
			bool f=true;
			for(ll j=maxBit;j>bit;j--){
				if( ((1ll<<j)&K)==0 && ((1ll<<j)&a[i])!=0 ){
					f=false;
					break;
				}
			}
			if(f)sum+=b[i];
		}
		ans=max(sum,ans);
	}
	cout<<ans;
    return 0;
}

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

int main() {
    int N;
    while (cin >> N, N) {
        vector<int> order(N), serv(N);
        for (int i = 0; i < N; i++) {
            char c;
            int hh, mm;
            cin >> hh >> c >> mm >> serv[i];
            if (hh < 3) hh += 24;
            order[i] = 60 * hh + mm;
            if (mm > serv[i]) {
                int count = 0;
                while ((mm + count) % 60 != serv[i]) count++;
                serv[i] = count;
            } else {
                serv[i] = serv[i] - mm;
            }
        }

        int Ls = 11 * 60;
        int Le = 15 * 60;
        int Ds = 18 * 60;
        int De = 21 * 60;
        int Ms = 21 * 60;
        int Me = 26 * 60;
        int Lt, Lf, Dt, Df, Mt, Mf;
        Lt = Lf = Dt = Df = Mt = Mf = 0;

        for (int i = 0; i < N; i++) {
            if (Ls <= order[i] && order[i] < Le) {
                if (serv[i] <= 8) Lt++;
                else Lf++;
            }
            if (Ds <= order[i] && order[i] < De) {
                if (serv[i] <= 8) Dt++;
                else Df++;
            }
            if (Ms <= order[i] && order[i] < Me) {
                if (serv[i] <= 8) Mt++;
                else Mf++;
            }
        }

        cout << "lunch ";
        if (Lt + Lf)
            cout << (int)(100 * (double)(Lt) / (Lt + Lf)) << endl;
        else cout << "no guest" << endl;
        cout << "dinner ";
        if (Dt + Df)
            cout << (int)(100 * (double)(Dt) / (Dt + Df)) << endl;
        else cout << "no guest" << endl;
        cout << "midnight ";
        if (Mt + Mf)
            cout << (int)(100 * (double)(Mt) / (Mt + Mf)) << endl;
        else cout << "no guest" << endl;
    }

    return 0;
}

Measured memory_bytes: 3080
#include<bits/stdc++.h>
#define rep(i, n) for(int (i)=0 ;i <(n); ++(i))
#define REP(i,m,n) for(int (i) = (m); (i) <= (n); ++(i))
#define yorn(f) puts((f)?"Yes":"No")
#define YORN(f) puts((f)? "YES":"NO")
typedef long long ll;
using namespace std;

int main() {
  int n;
  cin >> n;
  vector<string> s(n);
  rep(i, n) cin >> s[i]; 
  int m;
  cin >> m;
  vector<string> t(m);
  rep(i, m) cin >> t[i];

  unordered_map<string, int> mp;
  rep(i, n) mp[s[i]]++;
  rep(i, m) mp[t[i]]++;

  int ans = 0;
  for(auto p : mp) {
    int sump = 0;
    int sums = 0;
    string str = p.first;
    rep(i, n) {
      if(s[i] == str) sump++;
    }
    rep(i, m) {
      if(t[i] == str) sums++;
    }
    int tmp = sump - sums;
    ans = max(ans, tmp);
  }

  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>

using namespace std;
typedef long long ll;

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

    if (N % 2 != 0) cout << "No" << endl;
    else if (S.substr(0, N / 2) == S.substr(N / 2, N)) cout << "Yes" << endl;
    else cout << "No" << endl;
//    cout << S.substr(0, N / 2) << endl;
//    cout << S.substr(N / 2, N) << endl;
}

Measured memory_bytes: 256
#pragma gcc optimize("Ofast")

#include "bits/stdc++.h"
using namespace std;
typedef int64_t lld;
typedef pair<int,int> pii;
typedef pair<lld,lld> pll;
typedef pair<int,pll> pip;
typedef pair<pll,int> ppi;
typedef pair<lld,pll> plp;
typedef pair<pll,lld> ppl;
typedef pair<pll,pll> ppp;
template<typename T>
using maxHeap = priority_queue<T,vector<T>,less<T>>;
template<typename T>
using minHeap = priority_queue<T,vector<T>,greater<T>>;
#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define endl '\n'
#define jizz cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
inline void input(int &_x) {
    _x = 0;
    int _tmp = 1; char _tc = getchar();
    while((_tc < '0' || _tc > '9') && _tc != '-') _tc = getchar();
    if(_tc == '-') _tc = getchar(), _tmp = -1;
    while(_tc >= '0' && _tc <= '9') _x = _x*10+(_tc-48), _tc = getchar();
    _x *= _tmp;
}
inline void output(int _x) {
    char _buff[20]; int _f = 0;
    if(_x == 0)putchar('0');
    while(_x > 0)
    {
        _buff[_f++] = _x%10+'0';
        _x /= 10;
    }
    for(_f-=1; _f >= 0; _f--)
        putchar(_buff[_f]);
    putchar('\n');
}
template<typename Iter>
ostream& _out(ostream &s, Iter b, Iter e) {
    s<<"[";
    for ( auto it=b; it!=e; it++ ) s<<(it==b?"":" ")<<*it;
    s<<"]";
    return s;
}
template<class T1,class T2>
ostream& operator<<(ostream& out, pair<T1,T2> p) {
    return out << '(' << p.first << ", " << p.second << ')';
}
template<typename T>
ostream& operator <<( ostream &s, const vector<T> &c ) {
     return _out(s,c.begin(),c.end());
 }
#ifdef erd1
    #define pprint(x) cerr<<__PRETTY_FUNCTION__<<":"<<__LINE__<<" - "<<(#x)<<"="<<(x)<<endl
#else
    #define pprint(x)
#endif

// code starts here
vector<vector<pii>> G;
vector<int> cnt,gone;
vector<pii> E;

bool dfs(int x, int e){
    gone[x] = 1;
    for(auto i: G[x]){
        if(i.ss == e || gone[i.ff] == 2)
            continue;
        if(gone[i.ff] == 1)
            cnt[E[i.ss].ff]++;
        else if(dfs(i.ff,i.ss))
            cnt[i.ff]++, E[i.ss] = {i.ff, x};
        else
            cnt[x]++, E[i.ss] = {x, i.ff};
    }
    gone[x] = 2;
    return cnt[x]%2;
}

signed main(){
    int n, m;
    cin >> n >> m;
    G.resize(n+1);gone.resize(n+1);cnt.resize(n+1);
    for(int i = 0; i < m; i++){
        int a,b;
        cin >> a >> b;
        G[a].pb({b,i});
        G[b].pb({a,i});
        E.pb({a,b});
    }
    if(m%2)return cout << -1 << endl, 0;
    assert(!dfs(1,-1));
    for(auto i: E)cout << i.ff << " " << i.ss << endl;
}


Measured memory_bytes: 17780