akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<long long> vll;
typedef vector<int> vi;
typedef pair<int, int> pi;

#define pb push_back

#define rep(i, l, n) for (int i = (l); i < n; i++)
#define rep_cs(i, l, n) for (int i = (l); i <= n; i++)

#define rep_d(j, n) for (int j = n; j >= 0; j--)
#define rep_d_op(j, n, a) for (int j = n; j >= a; j--)

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

const int MOD = 1000000007;

const vector<int> dx = {1, 0};
const vector<int> dy = {0, 1};
const ll INF = 1LL << 60;

// int max = *std::max_element(vec.begin(), vec.end());
// int sum = accumulate(list, list + size, 0);

int GCD(int a, int b) { return b ? GCD(b, a % b) : a; }

using Graph = vector<vector<int>>;

Graph G;

vector<bool> seen;
void dfs(const Graph &G, int v)
{
    seen[v] = true;

    for (auto next_v : G[v])
    {
        if (seen[next_v])
            continue;
        dfs(G, next_v);
    }
}

int main()
{
    ll N, W;
    cin >> N >> W;
    ll w[110], v[110];
    rep(i, 0, N) cin >> w[i] >> v[i];

    ll dp[110][110000] = {0};

    rep(i, 0, N)
    {
        rep_cs(sum_weight, 0, W)
        {
            if (sum_weight - w[i] >= 0)
            {
                chmax(dp[i + 1][sum_weight], dp[i][sum_weight - w[i]] + v[i]);
            }
            chmax(dp[i + 1][sum_weight], dp[i][sum_weight]);
        }
    }
    cout << dp[N][W] << endl;
}

Measured memory_bytes: 94720
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define all(x) (x).begin(),(x).end()
const int INF=1e9+5;
const int N=2e5+5;
const int mod=1e9+7;

int n,x,y;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>x>>y;
	vector<int> ans(n+5,0);
	for(int i=1;i<n;++i){
		for(int j=i+1;j<=n;++j){
			int dist=min(abs(i-x)+abs(j-y)+1,abs(i-j));
			++ans[dist];
		}
	}
	for(int i=1;i<n;++i) cout<<ans[i]<<endl;
	return 0;
}


Measured memory_bytes: 256
MOD = 998244353

N,M,K = map(int,input().split())

ans = 0
NCi = 1#nからi選ぶ組み合わせ
for i in range(0,K+1,1):
    ans = (ans + M * pow(M-1,N-1-i,MOD)*NCi)%MOD
    NCi = (NCi*(N-1-i) * pow((i+1),MOD-2,MOD))%MOD

print(ans)

Measured memory_bytes: 73156
#include <set>
#include <array>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <vector>
#include <tuple>
#include <string>
#include <math.h>
#include <time.h>
#include <bitset>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <limits>
#include <climits>
#include <numeric>
#include <functional>

#define lnd '\n'
// #define reverse(i, n) for(ll i = n-1; i >= 0; --i)
#define from(i, n) for (ll i = 0; i < n; ++i)
#define loop(i, n) for(ll i = 0; i < n; i++)
#define REPN(i, n) for (ll i = 1; i <= n; ++i)
#define ALL(s) (s).begin(), (s).end()
#define rALL(s) (s).rbegin(), (s).rend()
#define sz(s) (int)(s).size()
#define mk make_pair
#define pb push_back
#define sqr(s) ((s) * (s))

using namespace std;

typedef long long ll;
typedef long long int lli;
typedef long double ld;
typedef unsigned long long ull;
typedef unsigned int ui;

template <class T>
T GCD (T a, T b) {
  if(a == 0) return b;
  return GCD(b%a, a);
}

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

template <class T>
T modpow(T x, T p){
    T res = 1;
    while(p > 0){
        if(p&1) res *= x;
        x *= x;
        p /= 2;
    }
    return res;
}

template <class T>
T modpow(T x, T p, ll mod){
    T res = 1;
    while(p > 0){
        if(p&1) res = (res*x)%mod;
        x = (x*x)%mod;
        p /= 2;
    }
    return res%mod;
}

template <class T>
void print(T a[], ll n){
    for (ll i = 0; i < n; i++) std::cout << a[i] << ' ';
    cout << endl;
}

template<class T>
void printc(T c){
    for(auto const& v: c) std::cout << v << ' ';
    cout << endl;
}

struct HASH{
  size_t operator()(const pair<long,long>&x)const{
    return hash<long long>()(((long long)x.first)^(((long long)x.second)<<32));
  }
};

bool pair_sort(const pair<int, int> &p1, const pair<int,int> &p2){
    if(p1.first != p2.first) return p1.first < p2.first;
    else return p1.second < p2.second;
}

const int INF = std::numeric_limits<int>::max();
const ll M_INF = std::numeric_limits<ll>::min();
const ll LL_INF = std::numeric_limits<ll>::max();

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

ll result[200005] = {0};
void fact(ll n) {
   if (n >= 0) {
      result[0] = 1;
      for (ll i = 1; i <= n; ++i) {
         result[i] = i * result[i - 1];
      }
   }
}

void solution(){
  ll x;
  cin >> x;
  ll a = 100;
  ll y = 0;
  while(a < x){
    a += a/100;
    y++;
  }

  cout << y << endl;
}     



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

map<ll, ll> m;
int n;
ll s = 0;

int main() {
	cin >> n;
	m[s]++;
	for (int i = 0; i < n; ++i) {
		int x; cin >> x;
		s += x;
		m[s]++;
	}

	ll ans = 0;
	for (auto it : m) {
		ans += (it.second)*(it.second-1)/2;
	}

	cout << ans << endl;
}

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

int main() {
  int l,r,d;cin>>l>>r>>d;
  int cnt=0;
  for(int i=l;i<=r;i++){
    if(i%d==0)cnt++;
  }
  cout<<cnt<<endl;
}

Measured memory_bytes: 3632
#include <ctime>
#include <iomanip>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <list>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
using namespace std;

#define int long long
#define INF 1e18
#define EPS 1e-9
#define NIL -1
#define N 100

signed main() {
    int n, k; cin >> n >> k;
    vector<int> a(n); for(int i = 0; i < n; i++) cin >> a[i];

    if((n - 1) % (k - 1) == 0) {
        cout << (n - 1) / (k - 1) << endl;
        return 0;
    } else {
        cout << (n - 1) / (k - 1) + 1 << endl;
        return 0;
    }
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    for(int i=0; i< n+1; i++){
        if(n < i*i){
            cout << (i-1)*(i-1) << endl;
            return 0;
        }else if(n == i*i){
            cout << i*i << endl;
            return 0;
        }
    }
    cout << n << endl;
    return 0;
}

Measured memory_bytes: 256
/*
[abc103] B - String Rotation
*/

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;

string S, T;
int N;

ll solve() {
    for (int i = 0; i < N; i++) {
        bool can = true;
        for (int j = 0; j < N; j++) {
            can = can && (S[j] == T[(i + j) % N]);
        }
        if (can) {
            return true;
        }
    }
    return false;
}

int main() {
    cin >> S;
    cin >> T;
    N = S.length();

    cout << (solve() ? "Yes" : "No") << endl;

    return 0;
}


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

public class Main {
	FastScanner in;
	PrintWriter out;

	int getAns(ArrayList<Integer> a, ArrayList<Integer> b) {
		if (a.size() > b.size()) {
			return getAns(b, a);
		}
		int res = a.size();
		int more = b.size() - a.size();
		for (int i = 0; i + 1 < b.size(); i++) {
			if (b.get(i) - b.get(i + 1) == 0 && more >= 2) {
				res++;
				i++;
				more -= 2;
			}
		}
		return res;
	}

	void solve() {
		int n = in.nextInt();
		int m = in.nextInt();
		ArrayList<Integer>[] g = new ArrayList[m];
		for (int i = 0; i < m; i++) {
			g[i] = new ArrayList<Integer>();
		}
		for (int i = 0; i < n; i++) {
			int id = in.nextInt();
			g[id % m].add(id);
		}
		for (int i = 0; i < m; i++) {
			Collections.sort(g[i]);
		}
		int res = g[0].size() / 2;
		for (int i = 1, j = m - 1; i < j; i++, j--) {
			res += getAns(g[i], g[j]);
		}
		if (m % 2 == 0) {
			res += g[m / 2].size() / 2;
		}
		out.println(res);
	}

	void run() {
		try {
			in = new FastScanner(new File("object.in"));
			out = new PrintWriter(new File("object.out"));

			solve();

			out.close();
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
	}

	void runIO() {

		in = new FastScanner(System.in);
		out = new PrintWriter(System.out);

		solve();

		out.close();
	}

	class FastScanner {
		BufferedReader br;
		StringTokenizer st;

		public FastScanner(File f) {
			try {
				br = new BufferedReader(new FileReader(f));
			} catch (FileNotFoundException e) {
				e.printStackTrace();
			}
		}

		public FastScanner(InputStream f) {
			br = new BufferedReader(new InputStreamReader(f));
		}

		String next() {
			while (st == null || !st.hasMoreTokens()) {
				String s = null;
				try {
					s = br.readLine();
				} catch (IOException e) {
					e.printStackTrace();
				}
				if (s == null)
					return null;
				st = new StringTokenizer(s);
			}
			return st.nextToken();
		}

		boolean hasMoreTokens() {
			while (st == null || !st.hasMoreTokens()) {
				String s = null;
				try {
					s = br.readLine();
				} catch (IOException e) {
					e.printStackTrace();
				}
				if (s == null)
					return false;
				st = new StringTokenizer(s);
			}
			return true;
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}
	}

	public static void main(String[] args) {
		new Thread(null, new Runnable() {
			public void run() {
				new Main().runIO();
			}
		}, "1", 1 << 26).start();
	}
}

Measured memory_bytes: 34208
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#define ll long long
#define si(n) scanf("%d",&n)
#define sl(n) scanf("%lld",&n)
#define pi(n) prllf("%d",n)
#define pl(n) prllf("%d",n)
using namespace std;

int main(){
  ll n,m;
  cin>>n;
  m=n;
  ll sum = 0;
  while(m>0){
    sum+=m%10;
    m/=10;
  }
  if(n%sum==0){
    cout<<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;
  }
}


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

int main() {
  string s, t;
  cin >> s >> t;
  int n = s.length(), m = t.length();
  int id = -1;
  for (int i = 0; i+m <= n; ++i) {
    string u = s.substr(i, m);
    bool f = true;
    rep(j, m) {
      if (u[j] != t[j] && u[j] != '?') f = false;
    }
    if (f) id = i;
  }
  if (id == -1) cout << "UNRESTORABLE" << endl;
  else {
    s.replace(id, m, t);
    replace(s.begin(), s.end(), '?', 'a');
    cout << s << endl;
  }
  return 0;
}

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

int main(){
    string s;
    cin >> s;
    int n = s.size(), cnt = 0;
    for(int i=0;i<n-1-i;++i){
        if(s[i] != s[n-1-i]) ++cnt;
    }

    cout << cnt << endl;
    
    return 0;
}

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

using namespace std;

int main(int argc, char *argv[])
{
   
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);

    int n,m;
    while (cin >> n >> m, n||m) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if ((i + j) % 2 ) {
                    cout << '.';
                } else {
                    cout << '#';
                }
            }
            cout << endl;
        }
        cout << endl;
    }
    
    return 0;
}


Measured memory_bytes: 3216
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
#include <set>
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)


int main(){
    int A,B,C,D;
    int s,g;
    cin >> A >> B >> C >> D;
    s = max(A, C);
    g = min(B, D);
    cout << max(g-s,0) << endl;

    //cout <<  (flag ? "Yes" : "No") << endl;
}


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

int main()
{
    typedef set<string> set_t;
    set_t A;
    string cmd;
    string word;
    int n; 
    cin >> n;
    for(int i=0;i<n;i++)
    {
        cin >> cmd;
        if(cmd == "insert")
        {
            cin >> word;
            A.insert(word);
        }
        else if(cmd=="find")
        {
            cin >> word;
            if(A.count(word)==0)
              cout << "no" << endl;
            else 
              cout << "yes" << endl;
        }
    }
}


Measured memory_bytes: 32624
# C
import itertools

H, W, K = map(int, input().split())
lst = [list(input()) for i in range(H)]

l1 = [i for i in range(H)]
l2 = [i for i in range(W)]

ans = 0
for i in range(H + 1):
    p1 = list(itertools.combinations(l1, i))
    for j in p1:
        for k in range(W + 1):
            p2 = list(itertools.combinations(l2, k))
            for l in p2:
                cnt = 0
                for m in range(H):
                    for n in range(W):
                        if (m not in list(j) and n not in list(l) and lst[m][n] == '#'):
                            cnt += 1
                if (cnt == K):
                    ans += 1
print(ans)

Measured memory_bytes: 70500
//----------BHAVIK DIWANI(PICT_COMP)---------------
#include<bits/stdc++.h>
#include<stdlib.h>
#include<stdio.h>
#define test ll t; cin>>t; while(t--)
#define FOR(p,n) for(ll i=p;i<(ll)n;i++)
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define mod 1000000007
#define ll long long
#define int long long
#define ull unsigned long long
#define MAX 1000005
#define pb push_back
#define mkp make_pair
#define vi vector<int>
#define pii pair<int,int>
#define endl '\n'
#define vs vector<string>
#define mii map<int,int>
#define msi map<string,int>
#define vpii vector< pair<int, int > >
#define vpsi vector< pair< string ,int > >
#define forci(p,q) for(int i=p;i<q;i++)
ll gcd(ll a,ll b){ if(b==0) return a;    return gcd(b,a%b);}
ll lcm(ll a,ll b) { return (a/gcd(a,b)*b);}
ull power(ull a, ull b, ll m) {a %= m;  ull res = 1;  while (b > 0) { if (b & 1) res = res * a % m;  a = a * a % m;  b >>= 1; }  return res%m; }
/*bool prime[MAX];
ull sieve(){memset(prime,true,sizeof(prime));for(ull p=2;p*p<MAX;p++){if(prime[p]==true){for(ull i=2*p;i<MAX;i+=p){prime[i]=false;}}}prime[0]=0;prime[1]=0;
}*/
using namespace std;
int solve()
{
	int n,p;
	cin>>n>>p;
	string s;
	cin>>s;
	if(p==2)
	{
		int ans=0;
		for(int i=0;i<n;i++)
		{
			if((s[i]-'0')%2==0)		ans+=i+1;
		}
		cout<<ans;
		return 0;
	}
	if(p==5)
	{
		int ans=0;
		for(int i=0;i<n;i++)
		{
			if((s[i]-'0')%5==0)		ans+=i+1;
		}
		cout<<ans<<endl;
		return 0;
	}
	reverse(s.begin(),s.end());
	int ans[n],pref[n];
	int p2=1;
	for(int i=0;i<n;i++)
	{
		int x=(s[i]-'0')*p2;
		p2=(p2*10)%p;
		ans[i]=x;
	}
	pref[0]=ans[0]%p;
	for(int i=1;i<n;i++)
		pref[i]=(pref[i-1]+ans[i])%p;
	int sum=0;
	mii mp;
	for(int i=0;i<n;i++)
	{
		if(pref[i]==0)
			sum++;
		sum+=mp[pref[i]];
		mp[pref[i]]++;
	}
	cout<<sum<<endl;

}
signed main()
{
	fastio;
//	test
		solve();
}


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

using namespace std;

char upper(char c) {
    return c + ('A' - 'a');
}

string s1, s2, s3, ans;

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

    cin >> s1 >> s2 >> s3;

    ans = "ABC";

    ans[0] = upper(s1[0]);
    ans[1] = upper(s2[0]);
    ans[2] = upper(s3[0]);

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define fastio ios_base::sync_with_stdio(false);cin.tie(nullptr), cout.tie(nullptr)
#define endl '\n'
using namespace std;

int n, k;

void solve(){   
    cin >> n >> k;
    vector<int> heights(n);
    vector<int> dp(n, INT_MAX); 
    for(int& it : heights)
        cin >> it;
    dp[0] = 0;
    for(int i = 0; i < n; ++i){
        for(int j = i + 1; j < i + k + 1 && j < n; ++j){
            dp[j] = min(dp[j], dp[i] + abs(heights[i] - heights[j]));
        }
    }
    cout << dp[n - 1] << endl;
}
 
signed main() {
	fastio;
	// int t; cin >> t;
 
	// while(t--)
		solve();
 
	return 0;
}


Measured memory_bytes: 1792
L = int(input())
N = len(bin(L)[2:])
M = 0
Lines = []
for i in range(N-1):
    M += 2
    Lines.append((i+1,i+2,0))
    Lines.append((i+1,i+2,2**i))

tmp = 2**(N-1)
for i,j in enumerate(bin(L)[3:],1):
    if j == '1':
        M += 1
        Lines.append((N-i,N,tmp))
        tmp += 2**(N-i-1)



print(N,M)
for Line in Lines:
    print("{} {} {}".format(Line[0],Line[1],Line[2]))

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

using i64 = long long;

int main(){
  int n;
  string a, b, c;
  cin >> n >> a >> b >> c;
  int ans = 0;
  for(int i=0;i<n;++i){
    if(a[i] == b[i] && b[i] == c[i])continue;
    else if(a[i] == b[i] || b[i] == c[i] || c[i] == a[i])ans++;
    else ans += 2;
  }
  cout << ans << endl;
  
  return 0;
}

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

const int MAX_N = 2*100000;
int a[MAX_N];

int main() {
  int N;
  cin >> N;
  if (N % 2 == 0) {
    for (int i = 0; i < N; i++) {
      cin >> a[i];
    }
    for (int i = N-1; i > 0; i -= 2) {
      cout << a[i] << ' ';
    }
    for (int i = 0; i < N; i += 2) {
      cout << a[i];
      if (i != N-2) {
	cout << " ";
      }
    }
  }
  else {
    for (int i = 0; i < N; i++) {
      cin >> a[i];
    }
    for (int i = N-1; i >= 0; i -= 2) {
      cout << a[i] << ' ';
    }
    for (int i = 1; i < N; i += 2) {
      cout << a[i];
      if (i != N-2) {
	cout << " ";
      }
    }
  }
}

Measured memory_bytes: 2944
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+100;
const int mod = 1e9+7;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll llINF = 0x3f3f3f3f3f3f3f3f;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define fep(i,a,b) for(int i=(a);i>=(b);i--)
inline bool read(ll &num) {
    char in;bool IsN=false;
    in=getchar();
    if(in==EOF) return false;
    while(in!='-'&&(in<'0'||in>'9')) in=getchar();
    if(in=='-'){ IsN=true;num=0;}
    else num=in-'0';
    while(in=getchar(),in>='0'&&in<='9'){
            num*=10,num+=in-'0';
    } 
    if(IsN) num=-num;
    return true;
}
struct point{
    double x,y;
}s[N];
bool cmp(point a,point b){
    if(atan2(a.y,a.x)!=atan2(b.y,b.x)){
        return atan2(a.y,a.x)<atan2(b.y,b.x);
    }
    return a.x<b.x;
}
int main(){
    //freopen("1.in", "r", stdin);
    ll n;
    read(n);
    rep(i,1,n){
        cin>>s[i].x>>s[i].y;
    }
    sort(s+1,s+n+1,cmp);
    rep(i,n+1,2*n) s[i]=s[i-n];
    double ans=0;
    rep(i,1,n){
        double xx=0;
        double yy=0;
        rep(j,i,i+n-1){
            xx+=s[j].x;
            yy+=s[j].y;
            ans=max(ans,xx*xx+yy*yy);
        }
    }
    printf("%.15lf\n",sqrt(ans));
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cmath>
#include <algorithm>

// 0, 1, ... a のXOR
long long f(long long a) 
{
    if (a % 2 == 1)
    {
        // a が奇数 なので0 ^ 1 ^ 2 ... ^ a =  (0 ^ 1) ^ (2 ^ 3) ... ^ (a - 1 ^ a)
        // n ^ n + 1 (nは偶数)のペアの個数が偶数ならば0, 奇数ならば1となる
        long long terms = a + 1;
        long long p = terms / 2;
        if (p % 2 == 0) return 0;
        else return 1;
    }
    else
    {
        // a が偶数 なので0 ^ 1 ^ 2 ... ^ a =  (0 ^ 1) ^ ... ^ (a - 2 ^ a - 1) ^ a
        // n ^ n + 1 (nは偶数)のペアの個数が偶数ならば0^a, 奇数ならば1^aとなる 
        long long terms = a;
        long long p = terms / 2;
        if (p % 2 == 0) return 0 ^ a;
        else return 1 ^ a;
    }
    
}

int main()
{
    long long A, B;
    scanf("%lld %lld", &A, &B);
    long long ans = A > 0 ? f(A - 1) ^ f(B) : f(B);
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <vector>
#include <algorithm> 
#include <utility> 
#include <tuple> 
#include <cstdint> 
#include <cstdio> 
#include <map> 
#include <queue> 
#include <set> 
#include <stack> 
#include <deque> 
#include <unordered_map> 
#include <unordered_set> 
#include <bitset> 
#include <cctype> 
#include <cmath>
#include <iomanip>
#include <ctype.h>

using namespace std;
using ll = long long;
using PAIR = pair<int, int>;
using PAIRLL = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vi>;

#define TR ","
#define fi first
#define se second
#define rep(i,N) for(int i=0;i<(int)N;++i)
#define all(v) v.begin(), v.end()
#define IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)

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

ll lcm(ll x, ll y) {
    return x / gcd(x, y) * y;
}

ll waz = 76543217;

ll inv(ll x) {
    if (x == 1) { return 1; }
    if (x == 0) { return 0; }
    else {
        ll a = (waz - inv(waz % x) * (waz / x)) % waz;
        if (a >= 0) { return a; }
        else { return waz + a; }
    }
}

void printVector(const vector<int>& vec) {
    for (int value : vec) {
        cout << value << " ";
    }
    cout << endl;
}

vector<ll> p;

ll phi(ll x) {
    ll a = x;
    ll b = x;
    for (ll k = 0; k != p.size(); ++k) {
        if (a % p[k] == 0) {
            while (a % p[k] == 0) {
                a /= p[k];
            }
            b = b / p[k] * (p[k] - 1);
        }
        if (a == 1) { break; }
    }
    return b;
}

bool my_compare(pair<string, int> a, pair<string, int> b) {
    if (a.first != b.first) {
        return a.first < b.first;
    }

    if (a.second != b.second) {
        return a.second > b.second;
    }
    else {
        return true;
    }
}

int N;
vector<vector<PAIR>> v;

bool judge(int bit) {
    rep(i, N) {
        if (!(bit & (1 << i))) continue;
        for (PAIR xy : v[i]) {
            int x = xy.fi;
            int y = xy.se;
            if (y == 1 && !(bit & (1 << x))) return false;
            if (y == 0 && (bit & (1 << x))) return false;
        }
    }
    return true;
}

int main()
{
    IO;

    cin >> N;
    v.resize(N);
    rep(i, N) {
        int A; cin >> A;
        v[i].resize(A);
        rep(j, A) {
            cin >> v[i][j].fi >> v[i][j].se;
            --v[i][j].fi;
        }
    }

    int res = 0;
    for (int bit = 0; bit < (1 << N); ++bit) {
        if (judge(bit)) {
            int count = bitset<16>(bit).count();
            res = max(res, count);
        }
    }
    cout << res << endl;
}

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

class AtCoder
{
    static void Main(string[] args)
    {
        Scanner cin = new Scanner();
        string s = Console.ReadLine();
        int K = cin.Int();

        List<string> x = new List<string>();
        for(int i = 1; i <= K; i++)
        {
            for(int j = 0; j < s.Length - i + 1; j++)
            {
                x.Add(s.Substring(j, i));
            }
        }

        string[] ans = x.Distinct().OrderBy(t => t).ToArray();
        Console.WriteLine(ans[K - 1]);

        Console.ReadLine();
    }

    static void Swap<T>(ref T a, ref T b)
    {
        T tmp = a;
        a = b;
        b = tmp;
    }

    static long BinarySearch<T>(T[] array, T target) where T : IComparable<T> //2分探索
    {
        int min = 0;
        int max = array.Length - 1;

        while (true)
        {
            // 範囲内に見つからなかった
            if (max < min) return -1;
            // 範囲内の中央値と比較する
            int mid = min + (max - min) / 2;
            switch (target.CompareTo(array[mid]))
            {
                case -1:    // 中央値より小さい
                    max = mid - 1;
                    break;
                case 1:     // 中央値より大きい
                    min = mid + 1;
                    break;
                case 0:     // 見つかった
                    return mid;
            }
        }
    }
}

class Scanner //標準入力
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner()
    {
        s = new string[0];
        i = 0;
    }

    public string Next()
    {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return Next();
        i = 0;
        return s[i++];
    }

    public int Int()
    {
        return int.Parse(Next());
    }
    public int[] ArrayInt(int N, int add = 0)
    {
        int[] Array = new int[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = Int() + add;
        }
        return Array;
    }

    public long Long()
    {
        return long.Parse(Next());
    }

    public long[] ArrayLong(int N, long add = 0)
    {
        long[] Array = new long[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = Long() + add;
        }
        return Array;
    }

    public double Double()
    {
        return double.Parse(Next());
    }


    public double[] ArrayDouble(int N, double add = 0)
    {
        double[] Array = new double[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = Double() + add;
        }
        return Array;
    }
}

Measured memory_bytes: 15840
number = input()
tile = [int(i) for i in number]
even = sum(tile[0::2])
odd = sum(tile) - even
ex1 = ((len(tile) // 2) - odd) + even
ex2 = ((len(tile) - (len(tile) // 2)) - even) + odd
print(min(ex1,ex2))

Measured memory_bytes: 4340
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin >> N;
  if(N%10==3)cout<<"bon"<<endl;
  else if(N%10==0||N%10==1||N%10==6||N%10==8)cout<<"pon"<<endl;
  else cout <<"hon"<<endl;
}

Measured memory_bytes: 3608
#include <iostream>
#include <cstdint>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <cassert>

using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

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

#ifdef DEBUG
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define eprintf(...) 42
#endif

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

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

template <LL MOD=1000000007> class MODLL {
public:
  LL x;
  MODLL(const LL _x) : x(_x % MOD) {};
  MODLL operator+(const MODLL rhs) const { return MODLL(*this) += rhs; }
  MODLL operator-(const MODLL rhs) const { return MODLL(*this) -= rhs; }
  MODLL operator*(const MODLL rhs) const { return MODLL(*this) *= rhs; }
  MODLL operator/(const MODLL rhs) const { return MODLL(*this) /= rhs; }
  MODLL& operator+=(const MODLL rhs) { x += rhs.x; x %= MOD; return *this; }
  MODLL& operator-=(const MODLL rhs) { x -= rhs.x; x %= MOD; if(x<0) x += MOD; return *this; }
  MODLL& operator*=(const MODLL rhs) { x *= rhs.x; x %= MOD; return *this; }
  MODLL inv() const {
    if(x == 0) { throw "does not have inverse"; }
    LL a = x, b = MOD, u = 1, v = 0;
    while (b) {
      long long t = a / b;
      a -= t * b; swap(a, b);
      u -= t * v; swap(u, v);
    }
    u %= MOD;
    if (u < 0) u += MOD;
    return MODLL(u);
  }
  MODLL& operator/=(const MODLL rhs) { (*this) *= rhs.inv(); return *this; }
  MODLL pow(ULL n) const {
    MODLL res = 1;
    MODLL a = x;
    while (n > 0) {
      if (n & 1) res *= a;
      a = a * a;
      n >>= 1;
    }
    return res;
  }
};

typedef MODLL<> ML;


void test() {
  {
    ML x = 3;
    assert(x.pow(45).x == 644897553);
  }
  {
    for(int i=1; i<13; i++) {
      MODLL<13> x = i;
      assert( (x.inv().x * i) % 13 == 1 );
    }
  }
}


int main() {

  LL N,M;
  cin >> N >> M;

  std::vector< std::vector<int> > A(N);
  REP(s,N) { A[s].resize(M, 0); }

  REP(light, M) {
    int k;
    cin >> k;
    REP(j, k) {
      int s;
      cin >> s;
      A[s-1][light] = 1;
    }
  }

  std::vector<int> P(M);
  REP(l,M) {
    cin >> P[l];
  }

  LL ans = 0;
  REP(i, 1<<N) {
    std::vector<int> IS_ON = P;
    REP(s,N) { // s'th switch
      if( i & (1<<s) ) {
        REP(l, M) {
          IS_ON[l] += A[s][l];
        }
      }
    }
    bool all = true;
    for(int on: IS_ON) {
      if (on % 2) {
        all = false;
        break;
      }
    }
    if(all) ans++;
  }

  cout << ans << endl;

  return 0;
}



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

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

using namespace std;

int main(){
    int A, B, C, D;

    cin >> A >> B >> C >> D;

    for (int i=0; ;i++){
        if (i % 2 == 0) {
            if ( C - (i/2 + 1)*B <= 0) {
                cout << "Yes" << endl;
                break;
            }
        } else {
            if ( A - (i/2 + 1)*D <= 0) {
                cout << "No" << endl;
                break;
            }
        }
    }

    return 0;
}



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

int m, f, r;

main() {
	while (cin >> m >> f >> r, !(m == -1 && f == -1 && r == -1)) {
		if (m == -1 || f == -1) cout << 'F' << endl;
		else if (m + f >= 80) cout << 'A' << endl;
		else if (m + f >= 65) cout << 'B' << endl;
		else if (m + f >= 50) cout << 'C' << endl;
		else if (m + f >= 30) cout << (r >= 50 ? 'C' : 'D') << endl;
		else cout << 'F' << endl;
	} 	
}



Measured memory_bytes: 3076
#include<stdio.h>
#include<string.h>
#include<limits.h>
#define Size 15
long int dist[Size][Size], dp[1 << Size][Size];
int rec(int S, int v, int size);
int main(void)
{
  int i, j, n, e, s, t, d;
  scanf("%d%d\n", &n, &e);
  for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
      dist[i][j] = INT_MAX;
    }
  }
  memset(dp, -1, sizeof(dp));
  for (i = 0; i < e; i++) {
    scanf("%d%d%d", &s, &t, &d);
    dist[s][t] = d;
  }
  d = rec(0, 0, n);
  if (d == INT_MAX) printf("-1\n");
  else printf("%d\n", d);
}
int rec(int S, int v, int size)
{
  long int u, res = INT_MAX;
  if (dp[S][v] >= 0) return dp[S][v];
  if (S == (1 << size) - 2) return dp[S][v] = dist[v][0];
  for (u = 1; u < size; u++) {
    if (!(S >> u & 1)) {
      long int tmp = rec(S | 1 << u, u, size) + dist[v][u];
      if (res > tmp) res = tmp;
    }
  }
  return dp[S][v] = res;
}


Measured memory_bytes: 5652
(N,M,T),*Y=$<.map{|l|l.split.map &:to_i};X=Y.reverse;$><<(T<2?(a=(r=0..N).map{|i|1<<i-1};Y.map{|x,y|a[x]=a[y]|=a[x]};q=2**N-2;g=r.find{|i|a[i]>q})?(o=[p]*-~N;o[g]=1;X.map{|x,y|o[x]?o[y]=?^:(o[x]||=o[y];?v)}):[-1]:N<3?[-1]:X.map{|x,y|y<4&&Y[x]==Y[6-x-y]?(Y[x]=Y[y];?v):(Y[y]=Y[x];?^)}).reverse.join

Measured memory_bytes: 652908
V,E = map(int,input().split())
dist = [[float('inf')]*V for _ in range(V)]
for _ in range(E):
  s,t,d = map(int,input().split())
  s -= 1
  t -= 1
  dist[s][t] = d

# dp[mask][destination]
dp = [ [-1]*V for _ in range(1<<V) ]
VISITED_ALL = (1<<V)-1

def tsp(mask, pos):
  if mask == VISITED_ALL:
    return dist[pos][0]

  if dp[mask][pos] != -1:
    return dp[mask][pos]

  ans = float('inf')
  for city in range(V):
    if (1<<city)&mask == 0:
      newAns = dist[pos][city] + tsp(mask | (1<<city), city)
      ans = min(ans, newAns)

  dp[mask][pos] = ans
  return ans

res = tsp(1,0)
if res == float('inf'):
  print(-1)
else:
  print(res)



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

typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()
#define dump(x) cout << #x << " = " << (x) << endl
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

template<class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
	os<<"{";
	rep(i, v.size()) {
		if (i) os<<",";
		os<<v[i];
	}
	os<<"}";
	return os;
}

const int maxn = 2010;
bool wl[maxn][maxn], wr[maxn][maxn];
bitset<maxn> bwl[maxn], bwr[maxn];
bitset<maxn> can[maxn];
bool e[maxn][maxn];

int main() {
	int N; cin >> N;
	for (int i = 1; i < N; ++i) {
		string s; cin >> s;
		rep(j, i) {
			e[i][j] = (s[j] == '1');
			e[j][i] = !e[i][j];
		}
	}

	rep(i, N) {
		rep(j, N) if (e[i][j]) {
			can[i].set(j);
		}
	}

	for (int l = N-1; l >= 0; --l) {
		wl[l][l] = wr[l][l] = 1;
		bwl[l].set(l, 1);
		bwr[l].set(l, 1);

		for (int r = l+1; r < N; ++r) {
			bitset<maxn> u = can[r] & bwr[l] & bwl[r-1];
			/*
			if (u.any()) {
				puts("wo");

				cout << l << " " << r << endl;
				cout << u << endl;
			}*/

			u >>= l;
			u <<= l;
			u <<= (maxn-r);
			if (u.any()) {
				wr[l][r] = 1;
				bwr[l].set(r);
			}

			bitset<maxn> v = can[l] & bwr[l+1] & bwl[r];
			/*
			bool f = 0;
			if (v.any()) {
				puts("wo2");
				f = 1;
				cout << l << " " << r << endl;
				cout << v << endl;
			}*/
			v >>= (l+1);
			v <<= (l+1);
			v <<= (maxn-r-1);

			if (v.any()) {
				wl[l][r] = 1;
				bwl[r].set(l);
			}
			/*

			for (int m = l; m < r; ++m) {
				
				if (e[r][m] && wr[l][m] && wl[m][r-1]) {
					wr[l][r] = 1;
					break; 
				}
			}
			for (int m = l+1; m <= r; ++m) {

				if (e[l][m] && wr[l+1][m] && wl[m][r]) {
					wl[l][r] = 1;
					break; 
				}
			}*/		
		}
	}
/*
	puts("l");

	rep(i, N) {
		rep(j, N) {
			cout << wl[i][j] << " ";
		}
		cout << endl;
	}
	puts("r");

	rep(i, N) {
		rep(j, N) {
			cout << wr[i][j] << " ";
		}
		cout << endl;
	}
*/

	int ans = 0;
	rep(i, N) if (wl[i][N-1] && wr[0][i]) {
		ans++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 13568
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N, m = 0;
    long long l = 0, hl, s = 0;
    cin >> N;
    int A[N];
    for(int i = 0; i < N; i++)
    {
        cin >> A[i];
        l += A[i];
    }
    hl = l/2;
    for(int i = 0; i < N; i++)
    {
        s += A[i];
        if(s == hl && l % 2 == 0)
        {
            break;
        }
        if(s > hl || (s == hl && l % 2 == 1))
        {
            if(s - hl < hl - s + A[i] || (s - hl == hl - s + A[i] && l % 2 == 1))
            {
                m = (s - hl) * 2;
                if(l%2 == 1) m--;
                break;
            }
            else
            {
                m = (hl - s + A[i]) * 2;
                if(l%2 == 1) m++;
                break;
            }
        }
    }
    cout << m << endl;
    return 0;
}


Measured memory_bytes: 1152
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <stack>
#include <queue>
#include <complex>
#include <set>
#include <list>
#include <iomanip>
#include <map>
#include <memory.h>
 
 
 
using namespace std;
static const double EPS = 1e-9;
typedef long long ll;
typedef unsigned long long ull;
#define rep(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a,0,sizeof(a))
#define minus(a) memset(a,0xff,sizeof(a))
#define chmax(a,b) a=min((a),(b))
#define chmin(a,b) a=max((a),(b))
 
 
#define MOD 1000000007
 
typedef pair<int,int>P;
#define INF (1<<29)
 
struct edge { 
	int from, to; 
	edge (int from, int to){
		this->from=from; this->to=to;
	}
};
 
int V,E;
typedef vector<edge> edges;
vector<edges> G;

ll a,b;

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

	if(1<abs(a-b)){
		cout<<"Alice" <<endl;
	}
	else
		cout<<"Brown"<<endl;
	
	
	return 0;
}




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

const ll INF = 1001001001001001;

int main()
{
    int n;
    cin >> n;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    ll S = 0;
    rep(i, n) S += a[i];
    ll mi = S;
    ll sum = 0;
    rep(i, n) {
        sum += a[i];
        mi = min(mi, abs(sum - (S - sum)));
    }
    cout << mi << endl;
    return 0;
}


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

int main() {
	string S;
	cin >> S;
	if(S[0]=='>') S = '<' + S;
	if(S.back()=='<') S += '>';
	vector<ll> sm{0}, la;
	for(int i=1; i<S.size(); ++i){
		if(S.substr(i-1, 2)=="<>") la.push_back(i);
		if(S.substr(i-1, 2)=="><") sm.push_back(i);
	}
	sm.push_back(S.size());
	ll ans=0;
	for(int i=0; i<la.size(); ++i){
		ll x=la[i]-sm[i], y=sm[i+1]-la[i];
		if(x<y) swap(x, y);
		ans += x*(x+1)/2 + y*(y-1)/2;
	}
	cout << ans << endl;
	return 0;
}

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

//////全探索したいときに開けよ////////
vector<vector<int>> fspattern;
vector<int> fspattern_draft;
int fspcnt = 0;

void setfspattern_core(int floor,int number,int degree){
  if(floor==degree){
    fspattern.at(fspcnt) = fspattern_draft;
    fspcnt++;
  }else{
    rep(i,number){
      fspattern_draft.at(floor) = i;
      setfspattern_core(floor+1,number,degree);
    }
  }
}

void setfspattern(int number,int degree){
  int64_t array_num = 1;
  rep(i,degree){
    array_num *= number;
  }
  fspattern = vector<vector<int>>(array_num,vector<int>(degree));
  fspattern_draft = vector<int>(degree);
  setfspattern_core(0,number,degree);
}

//////nCrのmodを求めたいときに開けよ/////////
//int64_t univMod = 1000000007;
//int64_t factnum = 100000
//vector<int64_t> modfact(factnum);
//vector<int64_t> modinvfact(factnum);

/*void setmodfact(){
  for(int i=0;i<factnum;i++){
    if(i == 0){
      modfact.at(i) = 1;
    }else{
      modfact.at(i) = (modfact.at(i-1)*i)%univMod;
    }
  }
}

int64_t calcmodpower(int64_t a,int64_t n){
  int64_t res = 1;
  while(n != 0){
    if(n & 1){
      res = (res * a) % univMod;
    }
    a = (a*a) % univMod;
    n = n >> 1;
  }
  return res;
}

int64_t calcinverse(int64_t n){
	return calcmodpower(n,univMod-2);
}

void setmodinvfact(){
  for(int i=0;i<factnum;i++){
    if(i==0){
      modinvfact.at(i) = 1;
    }else{
      modinvfact.at(i) = calcmodpower(modfact.at(i),univMod-2);
    }
  }
}

int64_t calcmodcomb(int64_t n,int64_t r){
  return (((modfact.at(n)*modinvfact.at(r))%univMod)*modinvfact.at(n-r))%univMod;
}

int64_t calcmodpositive(int64_t n){
  return (n + ((abs(n)+univMod-1)/univMod)*univMod)%univMod;
}
  
    */


/*
int64_t calcGCD(int64_t a,int64_t b){
	int64_t p = a;
	int64_t q = b;
	int64_t c = a%b;
	while(c != 0){
		p = q;
		q = c;
		c = p%q;
	}
	return q;
}
*/

int main(){
  int64_t a,b,c,k;
  cin >> a >> b >> c >> k;
  int64_t sum = a+b+c;
  if(k % 2 == 0){
    cout << a-b << endl;
  }else{
    cout << b-a << endl;
  }
    
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);

    int N = scanner.nextInt();
    int M = scanner.nextInt();
    int K = scanner.nextInt();
    if (possible(N, M, K)) System.out.println("Yes");
    else System.out.println("No");
  }

  private static boolean possible(int N, int M, int K) {
    for (int x = 0; x <= N; x++) {
      int a = N - x * 2;
      int b = K - M * x;
      if (a == 0) return b == 0;
      if (b % a == 0 && b / a >= 0 && b / a <= M) return true;
    }
    return false;
  }
}


Measured memory_bytes: 21844
/*------------------------------------
........Bismillahir Rahmanir Rahim....
..........created by Abdul Aziz.......
------------------------------------*/
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <unordered_map>
#include <queue>
#define   mod  998244353
#define   int  long long 
#define   ld   long double
#define   pb   push_back
#define   vi  vector<int> 
#define   dbg(x)  cerr << #x << " = " << x << '\n'
#define   sz(x)  (int)x.size()
#define   all(a) (a.begin(),a.end())
#define   ff   first
#define   ss   second
#define   pii  pair<int,int> 
#define   lcm(a,b) (a*b)/__gcd(a,b) 
using namespace std;


int n=100000;
bool  p[100005];
void  seive(){
    p[0]=p[1]=true;
    for (int i=4;i<=n;i+=2) p[i]=true;
    for (int i=3;i*i <= n;i += 2){
        if (p[i] == false)
        for (int j=i*i;j<=n;j+= i*2)
                p[j] = true;
    }
}
vi pref(100005,0);
inline void solve(){
    seive();
    for (int i=2;i<=100000;i++){
        if (p[i]==false and p[(i+1)/2]==false){
            pref[i]=1;
        }
    }
    for (int i=2;i<=100000;i++)
        pref[i] += pref[i-1];
    int q; cin>>q;
    while (q--){
        int l,r; 
        cin >> l >> r ; 
        cout << (pref[r]-pref[l-1]) << endl;
    }
    
}

signed main()
{
    int n=1; // cin>>n;
    while (n--) solve();
    return 0;
}


Measured memory_bytes: 3780
#include <iostream>
#include <vector>
#include <set>
using namespace std;
#define MAX (100000)

vector<int> G[MAX];
int N;
bool visited[MAX];
int prenum[MAX],parent[MAX],lowest[MAX],timer;

void dfs(int current,int prev){
    prenum[current]=lowest[current]=timer;
    timer++;
    
    visited[current]=true;
    
    int next;
    
    for(int i=0;i<G[current].size();i++){
        next=G[current][i];
        if(!visited[next]){
            parent[next]=current;
            
            dfs(next,current);
            
            lowest[current]=min(lowest[current],lowest[next]);
        }else if(next!=prev){
            lowest[current]=min(lowest[current],prenum[next]);
        }
    }
}

void art_points(){
    for(int i=0;i<N;i++)visited[i]=false;
    timer=1;
    
    dfs(0,-1);
    
    set<int> ap;
    
    int np=0;
    for(int i=1;i<N;i++){
        int p=parent[i];
        if(p==0)np++;
        else if(prenum[p]<=lowest[i])ap.insert(p);
    }
    if(np>1)ap.insert(0);
    for(set<int>::iterator it=ap.begin();it!=ap.end();it++){
        cout<<*it<<endl;
    }
}

int main(void){
    int m;
    cin>>N>>m;
    for(int i=0;i<m;i++){
        int s,t;
        cin>>s>>t;
        G[s].push_back(t);
        G[t].push_back(s);
    }
    art_points();
    
}



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

int main() {
    ll N;
    cin >> N;
    vector<ll> a(N);
    rep(i, N) cin >> a[i];
    ll x = 0;
    rep(i, N) { x = x + pow(-1, i) * a[i]; }
    cout << x << " ";
    rep(i, N - 1) {
        cout << 2 * a[i] - x << " ";
        x = 2 * a[i] - x;
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 4048
s = input()
q = int(input())
for i in range(q):
    order = input().split()
    a = int(order[1])
    b = int(order[2])
    if order[0] == "print":    
        print(s[a: b+1])
    elif order[0] == "reverse":
        rev_text = s[a: b+1]
        s = s[0: a] + rev_text[::-1] + s[b+1:]
    else:
        p = order[3]
        s = s[0: a] + p + s[b+1:]





Measured memory_bytes: 5608
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string.h>

using namespace std;
typedef pair<int, int> P;
int dp[201][201];

void solve()
{
	int D, N;
	cin >> D >> N;
	vector<int> temperature(D);
	for (int i = 0; i < D; ++i)
	{
		cin >> temperature[i];
	}
	vector<P> A(N);
	vector<int> C(N);
	for (int i = 0; i < N; ++i)
	{
		cin >> A[i].first >> A[i].second >> C[i];
	}
	memset(dp, 0, sizeof(dp));
	int ans = 0;
	for (int i = 1; i < D; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			if (A[j].first <= temperature[i] && temperature[i] <= A[j].second)
			{
				for (int k = 0; k < N; ++k)
				{
					if (A[k].first <= temperature[i - 1] && temperature[i - 1] <= A[k].second)
					{
						dp[i][j] = max(dp[i][j], dp[i - 1][k] + abs(C[j] - C[k]));
						ans = max(ans, dp[i][j]);
					}
				}
			}
		}
	}
	cout << ans << endl;
}

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

Measured memory_bytes: 1364
import java.util.Scanner;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		long p=1;
		for(int i=1;i<=N;i++){
			p=(p*i)%1000000007;
		}
			System.out.println(p);
		sc.close();
	}
}

Measured memory_bytes: 23636
/* template.cpp [[[ */
#include <bits/stdc++.h>
using namespace std;
#define get_macro(a, b, c, d, name, ...) name
#define rep(...) get_macro(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep(...) get_macro(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__)
#define rep1(n) rep2(i_, n)
#define rep2(i, n) rep3(i, 0, n)
#define rep3(i, a, b) rep4(i, a, b, 1)
#define rep4(i, a, b, s) for (ll i = (a); i < (ll)(b); i += (ll)s)
#define rrep1(n) rrep2(i_, n)
#define rrep2(i, n) rrep3(i, 0, n)
#define rrep3(i, a, b) rrep4(i, a, b, 1)
#define rrep4(i, a, b, s) for (ll i = (ll)(b) - 1; i >= (ll)(a); i -= (ll)s)
#define each(x, c) for (auto &&x : c)
#define fs first
#define sc second
#define all(c) begin(c), end(c)
using ui = unsigned;
using ll = long long;
using ul = unsigned long long;
using ld = long double;
const int inf = 1e9 + 10;
const ll inf_ll = 1e18 + 10;
const ll mod = 1e9 + 7;
const ll mod9 = 1e9 + 9;
const int dx[]{-1, 0, 1, 0, -1, 1, 1, -1};
const int dy[]{0, -1, 0, 1, -1, -1, 1, 1};
template<class T, class U> void chmin(T &x, const U &y){ x = min<T>(x, y); }
template<class T, class U> void chmax(T &x, const U &y){ x = max<T>(x, y); }
struct prepare_ { prepare_(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(12); } } prepare__;
/* ]]] */

int main(){
  int n, k, x, y;
  cin >> n >> k >> x >> y;
  int s = 0;
  rep(i, n) s += i < k ? x : y;
  cout << s << endl;
}



Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <complex>
using namespace std;

typedef long long ll;
typedef pair<int,int> P;

#define all(c) (c).begin(),(c).end()
#define pb push_back
#define mp make_pair
#define ERASE(v,i) (v).erase(remove(all(v),i),(v).end())
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define each(it,c) for(typeof((c).begin()) it=(c).begin();it!=(c).end();++it)
#define debug(x) cerr<<#x<<" = "<<(x)<<endl;
#define LINE cerr<<"LINE: "<<__LINE__<<endl;

inline int toInt(string s){int v;istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x){ostringstream sout;sout<<x;return sout.str();}
template<class T> void preview(T a,T b){for(T it=a;it!=b;++it)cerr<<*it<<" ";cerr<<endl;}

const int INF = 100000000;
const double PI = acos(-1.0), EPS = 1e-10;

int main() {
	for(string line; getline(cin, line);) {
		rep(i,line.length()) if(line[i] == ',') line[i] = ' ';
		istringstream is(line);
		int num;
		double height, weight;
		is >> num >> weight >> height;
#if 0
		debug(num)
		debug(height)
		debug(weight)
		cerr << weight / (height * height) << endl;
#endif
		if(weight / (height * height) >= 25) cout << num << endl;
	}
	return 0;
}

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

int main() {
	int x, y, w, h, r;
	cin >> w >> h >> x >> y >> r;

	if ((x <= w - r) && (x >= r) && (y <= h - r) && (y >= r)) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}


Measured memory_bytes: 3100
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1e6+5;
int tab[MAXN];
map <string,int> mp;

int main(){
    ios::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
    int n,m;
    string s;
    cin >> n;
    for(int i=0;i<n;i++){
		cin >> s;
		mp[s]++;
	}
	cin >> m;
	for(int i=0;i<m;i++){
		cin >> s;
		mp[s]--;
	}
	int res=0;
	for(auto i:mp)
		res=max(res,i.second);
	cout << res;
}


Measured memory_bytes: 256
n, k = map(int, input().split())
x = list(map(int, input().split()))

dist = float('inf')
for i in range(n-(k-1)):
    l = x[i]
    r = x[i+k-1]
    temp = min(abs(l), abs(r)) + abs(l-r)
    dist = min(dist, temp)

print(dist)



Measured memory_bytes: 14224
C=3.times.map { gets.chomp.split.map(&:to_i) }

# 各行の最小値を減算
3.times do |i|
  m=C[i].min
  3.times do |j|
    C[i][j]-=m
  end
end

# 列の数値が異なった場合、Noを出力
3.times do |i|
  if C[0][i]!=C[1][i] || C[1][i]!=C[2][i]
    puts 'No'
    exit
  end
end

puts 'Yes'

Measured memory_bytes: 1788