akhauriyash/Code-Regression huggingface dataset:
/*  -*- coding: utf-8 -*-
 *
 * b.cc: 
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>

using namespace std;

/* constant */

const long long LINF = 1LL << 62;

/* typedef */

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

/* global variables */

/* subroutines */

template <typename T>
T gcd(T m, T n) {  // m > 0, n > 0
  if (m < n) swap(m, n);
  while (n > 0) {
    T r = m % n;
    m = n;
    n = r;
  }
  return m;
}

template <typename T>
void exgcd(T x, T y, T &a, T &b, T &c) {
  T r0 = x, r1 = y;
  T a0 = 1, a1 = 0;
  T b0 = 0, b1 = 1;

  while (r1 > 0) {
    T q1 = r0 / r1;
    T r2 = r0 % r1;
    T a2 = a0 - q1 * a1;
    T b2 = b0 - q1 * b1;
    r0 = r1, r1 = r2;
    a0 = a1, a1 = a2;
    b0 = b1, b1 = b2;
  }
  c = r0;
  a = a0;
  b = b0;
}

inline void setmin(ll &a, ll b) { if (a > b) a = b; }

/* main */

int main() {
  ll n;
  scanf("%lld", &n);

  if (n == 1) { puts("1"); return 0; }

  // sum_{i=1}^k i = k(k+1)/2 = n -> k(k+1)=2n

  ll n2 = n * 2, mink = LINF;
  for (ll p = 1; p * p <= n2; p++)
    if (n2 % p == 0) {
      ll q = n2 / p;
      ll a, b, c;
      exgcd(p, q, a, b, c);
      if (c == 1) {
	//printf("%lld * %lld + %lld * %lld = %lld\n", a, p, b, q, c);
	if (a == 0) setmin(mink, b * q + n2);
	else if (a < 0) setmin(mink, -a * p);
	if (b == 0) setmin(mink, a * p + n2);
	else if (b < 0) setmin(mink, -b * q);
      }

      // p*a+1=q*b or q*a+1=p*b
    }

  printf("%lld\n", mink);
  return 0;
}


Measured memory_bytes: 3824
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <math.h>
#include <queue>
using namespace std;
typedef long long ll;
#define PI 3.14159265359

ll sn(ll a, ll lim) {
    ll n = lim / a;
    ll l = n * a;
    return (a + l) * n / 2;
}

int main() {
  ll N;
  cin >> N;
  ll ans = 0;
  for (ll n = 1;n <= N;n ++) {
    ll a = N / n;
    ans += n * (a * (a+1) / 2);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3572
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
#define ALL(c) (c).begin(), (c).end()
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v, x) (std::find(v.begin(), v.end(), x) != v.end())

using namespace std;
typedef long long ll;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
const int INF = 1001001001;
const long long INFL = (1LL<<60);
const double eps = (1e-9);

int n;

// mx: どの文字まで使っていいか？ (使わなくても良い)
void dfs(string s, char mx) {
  cerr << "dfs: " << s << " " << mx << endl;
  if (s.length() == n) {
    cout << s << endl;
  } else {
    for (char c = 'a'; c <= mx; c++) {
      dfs(s + c, ((c == mx) ? (char)(mx + 1) : mx));
    }
  }
}


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

  cin >> n;
  dfs("", 'a');

  return 0;
}


Measured memory_bytes: 1536
#include<bits/stdc++.h> 
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
typedef long long ll;
using namespace std;
inline int read(){
	int n=0,f=1;char c;
	for(c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar());
	if (c=='-') c=getchar(),f=-1;
	for(;c>='0'&&c<='9';c=getchar()) n=n*10+c-48;
	return n*f;
}
const int maxn=5e5+5;
int i,j,n,head,tail;
double q[maxn][2],V,T,L,t,v;
int main(){
	n=read(),L=read();
	head=1,tail=0;
	for(;n--;){
		t=read(),v=read();
		V+=v,T+=t*v;
		for(;V>L;){
			if (V-q[head][0]>L)V-=q[head][0],T-=q[head][1]*q[head][0],head++;else{
				q[head][0]-=V-L,T-=(V-L)*q[head][1],V=L;
				break;
			}
		}
		printf("%.6lf\n",T/V);
		q[++tail][0]=v,q[tail][1]=t;
		for(;head<tail;tail--){
			if (q[tail][1]>q[tail-1][1]) break;
			q[tail-1][1]=(q[tail-1][0]*q[tail-1][1]+q[tail][0]*q[tail][1])/(q[tail-1][0]+q[tail][0]);
            q[tail-1][0]+=q[tail][0];
		}
	}
}

Measured memory_bytes: 16384
import java.util.*;
public class Main { 
	final static int maxn=(int)2e5+10;
	static int vis[]=new int [maxn];
	static int a[]=new int [maxn];
	static int b[]=new int [maxn];
	static int f[][]=new int [maxn][3];
 public static void main(String args[])
 {
	 Scanner input=new Scanner(System.in);
     String s=input.next();
     if(s.charAt(2)==s.charAt(3)&&s.charAt(4)==s.charAt(5))
    	 System.out.println("Yes");
     else
    	 System.out.println("No");
}
}

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

map<int, int> mp;
vector<int> v;

int main(){

    int n, k, a;
    scanf("%d%d", &n, &k);
    for(int i=0; i<n; ++i){
        scanf("%d", &a);
        ++mp[a];
    }

    int cnt=mp.size();
    if(cnt<=k)
        puts("0");
    else{
        long long ans=0LL;
        for(auto i:mp)
            v.push_back(i.second);
        sort(v.begin(), v.end());
        int sz=cnt-k;
        for(int i=0; i<sz; ++i)
            ans+=(1LL*v[i]);

        printf("%d", ans);
    }






    return 0;
}


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

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

  char A ,B;
  bool C = false;
  
  if (((char) N.at(0) == (char) N.at(1)) && 
      ((char) N.at(1) == (char) N.at(2))) {
    cout << "Yes" << endl;
  } else if 
     (((char) N.at(1) == (char) N.at(2)) && 
      ((char) N.at(2) == (char) N.at(3)) ) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}

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

typedef long long ll;
typedef long double ld;
// use unique(x) - removec consecutive items, returns vec.begin() + number of items
// for vector: sort(all(vec)); vec.erase(unique(all(vec)), vec.end());
// use iota(all(vec), 0) for filling a vector with 0,1,2...
// use fill(all(vec), 1) for filling a vector with 1,1,1...
// use rotate(vec.begin(), vec.begin() + 1, vec.end()) to rotate a vector | middle arg becomes first
// use merge(all(vec1), all(vec2), vec3.begin()) to merge 2 vectors, use vec3.resize(vec1.size() + vec2.size()) first
// ll pos = partition_point(all(vec), pred) - vec.begin(); bool pred(ll a){return a<3};
// print number in binary -> cout << bitset<20>(n);
#define mod 998244353

ll powmod(ll a,ll b){
	if(!b)return 1;
	if(b%2)return powmod(a*a%mod,b/2)*a%mod;
	return powmod(a*a%mod,b/2);
}

int n,s;
vector<int>nums;
// items, sum = number of subsets
// je několik subsekvencí A jejichž součet se rovná j a používaj i prvních prvků.
// každá z těch subsekvencí má nějakou délku k a vyskytuje se v 2^(n-k) podmnožinách A.
// součet počtu těchto podmnožin pro všechny tyto subsekvence je uložen v dp[i][j]
ll dp[3002][3002];

int main(){
	cin>>n>>s;nums.resize(n);
	for(int i=0;i<n;++i)cin>>nums[i];
	dp[0][0]=powmod(2,n); // existuje právě jedna podmnožina délky 0 která využívá 0 prvních prvků a vyskytuje se právě v 2^n podmnožinách
	ll div2=powmod(2,mod-2);
	for(int i=0;i<n;++i)
		for(int j=0;j<=s;++j){
			if(j+nums[i]<=s)dp[i+1][j+nums[i]]=(dp[i+1][j+nums[i]]+div2*dp[i][j])%mod;
			dp[i+1][j]=(dp[i+1][j]+dp[i][j])%mod;
//			cout<<dp[i][j]<<" ";
		}
	cout<<dp[n][s]<<endl;
}


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

int main(){
    string s;
    cin >> s;
    bool check=false;
//    if('a'<=s.at(0)) cout << 1 << endl;

    for(int i=2; i<s.size()-1; i++){
        if('a'<=s.at(i) && s.at(i)<='z'){
        }
        else if(s.at(i)=='C'){
            if(check==false){
                check=true;
            }
            else if(check==true){
                check=false;
                break;
            }
        }
        else break;
    }
    if(s.at(0)!='A') check=false;
    if('a'>s.at(1) || s.at(1)>'z') check=false;
    if('a'>s.at(s.size()-1) || s.at(s.size()-1)>'z') check=false;

    if(check==true) cout << "AC" << endl;
    else cout << "WA" << endl;
}

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

#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
#define FOR(i, k, n) for (int i = (k); i < (int)(n); ++i)
#define FOREQ(i, k, n) for (int i = (k); i <= (int)(n); ++i)
#define DEC(i, k) for (int i = (k); i >= 0; --i)
#define FORIT(i, c) for (__typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define SZ(v) (int)((v).size())
#define MEMSET(v, h) memset((v), (h), sizeof(v))
#define FIND(m, w) ((m).find(w) != (m).end())
#define ALL(c) (c).begin(), (c).end()

typedef complex<double> Point;

struct UnionFind {
  int parent[10010];
  bool unionSet(int x, int y) {
    x = root(x); y = root(y);
    if (x == y) { return true; }
    if (parent[x] > parent[y]) { swap(x, y); }
    parent[x] += parent[y];
    parent[y] = x;
    return false;
  }
  bool findSet(int x, int y) {
    return root(x) == root(y);
  }
  int root(int x) { return parent[x] < 0 ? x : parent[x] = root(parent[x]); }
};

struct Edge {
  int from;
  int to;
  double cost;
  Edge() {;}
  Edge(int from, int to, double cost) : from(from), to(to), cost(cost) {;}
  bool operator<(const Edge &rhs) const {
    return cost < rhs.cost;
  }
};

int n, m;
Point pile[10100];
vector<Edge> edges;
UnionFind uset;

int main()
{
  memset(&uset, -1, sizeof(uset));
  scanf("%d %d", &n, &m);
  REP(i, n) {
    double x, y;
    scanf("%lf %lf", &x, &y);
    pile[i] = Point(x, y);
  }
  edges.resize(m);
  REP(i, m) {
    int from, to;
    scanf("%d %d", &from, &to);
    from--; to--;
    edges[i] = Edge(from, to, abs(pile[from] - pile[to]));
  }
  sort(edges.begin(), edges.end());
  reverse(edges.begin(), edges.end());
  double ans = 0.0;
  REP(i, m) {
    if (uset.unionSet(edges[i].from, edges[i].to)) {
      ans += edges[i].cost;
    }
  }
  printf("%.3lf\n", ans);
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define Khela ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long int
#define llu long long unsigned int
#define pf printf
#define sf scanf
#define f first
#define s second
#define pb push_back
#define mk make_pair
#define pii pair<int ,int>
 
int dx8[] = {0, 0, 1, 1, 1, -1, -1, -1};
int dy8[] = {1,-1, 1, -1, 0, 0, -1, 1};
int dx4[] = {0, 0, 1, -1};
int dy4[] = {1, -1, 0, 0};
 
typedef tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
int Set(int N,int pos){return N=N | (1<<pos);}
int reset(int N,int pos){return N= N & ~(1<<pos);}
bool check(int N,int pos){return (bool)(N & (1<<pos));}
const int Max=1e9+100;
const int sz=1e3+100;
 
int main()
{
    Khela
    llu a,b,c,i,j,k,q,p,x,y,ct,ct1,m,l,r,x1,y1,mn,h,sum1,in,z,mid,n,mx;
    char ch;
    double d;
    string str1,str2,str;
    bool bl,bl1;
    int t,cs=1;
    while(cin>>n)
    {
        llu p=((n+1ll)*n)/2;
        p-=n;
        cout<<p<<endl;
    }





}

Measured memory_bytes: 384
#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left, bisect_right #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

N = int(input())
txy = [list(map(int, input().split())) for _ in range(N)]

for txyi, txyip in zip([[0, 0, 0]] + txy[:-1], txy):
    ti, xi, yi = txyi
    tip, xip, yip = txyip
    dift = tip - ti
    difd = abs(xip-xi) + abs(yip-yi)
    if difd%2 != dift%2:
        print('No')
        exit()
    if dift < difd:
        print('No')
        exit()
print('Yes')



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

int main(){
    int N;
    cin >> N;
    vector<long> A(N+1);
    vector<long> B(N);
    for(int i=0;i<N+1;++i) cin >> A[i];
    for(int i=0;i<N;++i) cin >> B[i];

    long tmp=0,cnt=0;
    for(int i=0;i<N;++i){
        if(tmp+B[i]>A[i]){
            cnt += A[i];
            tmp = min(B[i],B[i] + tmp - A[i]);
        }
        else{
            cnt += B[i] + tmp;
            tmp = 0;
        }
    }
    cout << cnt + min(A[N],tmp) << endl;
}


Measured memory_bytes: 1792
n = int(input())
N = str(n)
array = list(map(int, list(N)))
for i in range(0, len(array)):
    if array[i] == 1:
        array[i] = 9
    elif array[i] == 9:
        array[i] = 1
print(array[0], end = '')
print(array[1], end = '')
print(array[2])


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


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

    ll i,j,k,l,m,n,w,x,y,z,p,q,tmp,sum=0;
    string str;
    cin>>n;
    vector<ll> a(n+1);
    vector<ll> b(n+1);
    rep(i,n)   cin >> a[i];
        n++;
    rep(i,n){
        b[a[i]]++;
    }
    ll total=0;
    rep(i,n){
        if(b[i]==0||b[i]==1) continue;
        total+=b[i]*(b[i]-1)/2;
    }
    rep(i,n-1){
        if(b[a[i]]!=0||b[a[i]]!=1)cout<<total-b[a[i]]+1<<endl;
        else cout<<total<<endl;
    }

    return 0;
}


Measured memory_bytes: 5760
n = int(input())
lst = list(map(int, input().split()))

total = sum(lst)
ans = abs(sum(lst)-lst[0])

for i in range(1,n):
  sublist = lst[:i]
  fwd = sum(sublist)
  bck = total - fwd
  ans = min(ans, abs(fwd-bck))
print(ans)

Measured memory_bytes: 3060
#include<iostream>
using namespace std;
int main(){
  int n,m,k;
  cin>>n>>m>>k;
  int a[n]={},b[m]={};
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
for(int j=0;j<m;j++){
  cin>>b[j];
}
  long long t=0;
  for(int i=0;i<m;i++) t+=b[i];
  int j=m;
  int ans=0;
  for(int i=0;i<n+1;i++){
    while(j>0&&t>k){
      --j;
      t-=b[j];
    }
    if(t>k) break;
    ans=max(ans,i+j);
    if(i==n) break;
    t+=a[i];
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 5180
#include<cstdio>
int tb[105][105];
int main(){
    int h,w;
    int n;
    scanf("%d%d",&h,&w);
    scanf("%d",&n);
    int cnt = 0;
    for(int j=1;j<=n;j++){
        int su;
        scanf("%d",&su);
        for(int i=cnt;i<cnt+su;i++){
            if((i/w) % 2 == 0){
                tb[i/w][i%w] = j;
            }else{
                tb[i/w][w - (i%w) - 1] = j;
            }
        }
        cnt += su;
    }
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            printf("%d ", tb[i][j]);
        }
        printf("\n");
    }
}


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

int GetDigitsCount(int N) {
	int digitsCount = 0;
	while (N != 0) {
		digitsCount++;
		N /= 10;
	}
	return digitsCount;
}

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

	int ans = 0;

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

		if (GetDigitsCount(i) % 2 != 0) ans++;

	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
package main

import "fmt"

func main() {
	var N, sum int
	fmt.Scan(&N)
	a := make([]int, N)
	b := make([]int, N)
	c := make([]int, N-1)
	for i := 0; i < N; i++ {
		fmt.Scan(&a[i])
	}
	for i := 0; i < N; i++ {
		fmt.Scan(&b[i])
	}
	for i := 0; i < N-1; i++ {
		fmt.Scan(&c[i])
	}
	p := -10
	for i := 0; i < N; i++ {
		sum += b[a[i]-1]
		if p+1 == a[i] {
			sum += c[p-1]
		}
		p = a[i]
	}
	fmt.Println(sum)
}

Measured memory_bytes: 512
#include <iostream>
#include <iomanip> //! for setprecision(10)
#include <math.h>
#include <algorithm>
#include <functional> 
#include <string>
#include <vector>

#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <utility>
#include <limits.h>

using namespace std;

typedef long long LL;

#define rep(i,n) for (int i = 0; i < (n); ++i)
#define dump(c) { for (auto it = c.begin(); it != c.end(); ++it) if (it == c.begin()) cout << *it; else cout << ' ' << *it; cout << endl; } 
#define dumpMap(m) { for (auto it: m) cout << it.first << "=>" << it.second << ' '; }

const int MOD = 1000000007;

LL dp[100][100005];

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(0);
    
    int N, W;
    cin >> N >> W;
    vector<int> w(N), v(N);
    rep(i, N) cin >> w[i] >> v[i];

    for (int j = w[0]; j <= W; ++j) {
        dp[0][j] = v[0];
    }
    // rep(k, W+1) { cout << dp[0][k] << ' '; } cout << endl;
    for (int i = 1; i < N; ++i) {
        rep(j, W+1) {
            if (j < w[i]) {
                dp[i][j] = dp[i-1][j];
            } else {
                dp[i][j] = max(dp[i-1][j], v[i]+dp[i-1][j-w[i]]);
            }
        }
        // rep(k, W+1) { cout << dp[i][k] << ' '; } cout << endl;
    }

    cout << dp[N-1][W] << endl;

    return 0;
}


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

#define times(n, i) uptil(0, n, i)
#define upto(f, t, i) for(auto _##i = (t), i = decltype(_##i)(f) poi  i <= _##i poi  i++)
#define uptil(f, t, i) for(auto _##i = (t), i = decltype(_##i)(f) poi  i < _##i poi  i++)
#define downto(f, t, i) for(auto i = (f), _##i = decltype(i)(t) poi  i >= _##i poi  i--)
#define downtil(f, t, i) for(auto i = (f), _##i = decltype(i)(t) poi  i > _##i poi  i--)

#define unless(c) if(!(c))
#define until(c) while(!(c))
#define loop while(true)

#define poi ;
#define poipoi << "\n"

using namespace std;

#define fuwafuwa(n, c) dokidoki((n) + (c) - 1, c)
#define dokidoki(n, c) ((n) / (c) * (c))

template<class T> bool read(T& t){
    return cin >> t poi
}
template<class T, class...U> bool read(T& t, U&... u){
    unless(cin >> t) return false poi
    return read(u...) poi
}

template<class T> T lov_yet(T t){
    if(t) return t poi
    else return 0 poi
}

template<class T> T gcd(T a, T b){
    if(b) return gcd(b, a % b) poi
    else return a poi
}

pair<double, double> solve_linear(double a1, double b1, double c1, double a2, double b2, double c2){
    return make_pair(lov_yet((b1 * c2 - b2 * c1) / (b1 * a2 - b2 * a1)), lov_yet((a1 * c2 - a2 * c1) / (a1 * b2 - b1 * a2))) poi
}

double distance(const pair<double, double>& p){
    return lov_yet(sqrt(p.first * p.first + p.second * p.second)) poi
}
double distance(const pair<double, double>& a, const pair<double, double>& b){
    return distance(make_pair(a.first - b.first, a.second - b.second)) poi
}

double inner_product(const pair<double, double>& a, const pair<double, double>& b){
    return lov_yet(a.first * b.first + a.second * b.second) poi
}

double outer_product_z(const pair<double, double>& a, const pair<double, double>& b){
    return lov_yet(a.first * b.second - b.first * a.second) poi
}

int main(){
    double     x1, y1, x2, y2, x3, y3, xp, yp poi

    while(read(x1, y1, x2, y2, x3, y3, xp, yp)){
        double a = outer_product_z(make_pair(x2 - x1, y2 - y1), make_pair(xp - x1, yp - y1)),
               b = outer_product_z(make_pair(x3 - x2, y3 - y2), make_pair(xp - x2, yp - y2)),
               c = outer_product_z(make_pair(x1 - x3, y1 - y3), make_pair(xp - x3, yp - y3)) poi
        if(a * b >= 0 && b * c >= 0 && c * a >= 0)
            cout << "YES" poipoi poi
        else
            cout << "NO" poipoi poi
    }

    return 0 poi
}

Measured memory_bytes: 1188
from collections import Counter
from math import factorial
Q = 10**9+7
def primes(n):
    primfac = [0]
    d = 2
    while d*d <= n:
        while n%d == 0:
            primfac[-1] += 1
            n //= d
        d += 1
        if primfac[-1] != 0:
            primfac.append(0)
    if n > 1:
        if primfac[-1] == 0:
            primfac[-1] += 1
        else:
            primfac.append(1)
    return primfac
def combination(a,b):
    return ( (factorial(a)//factorial(b))//factorial(a-b))%Q
N, M = map( int, input().split())
C = primes(M)
ans = 1
if N == 1:
    print(1)
else:
    for x in C:
        ans = (ans * combination(x+N-1,N-1))%Q
    print(ans)

Measured memory_bytes: 114384
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <stdlib.h>
#include <string>
#include <utility>
#include <vector>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define loop(i, x, n) for (int i = (x); i < (n); i++)
#define all(v) (v).begin(), (v).end()
#define int long long
using namespace std;
const int MOD = 1e9 + 7;
const int INF = 1e18;
template<typename T> void cmax(T &a, T b) { a = max(a, b); }
template<typename T> void cmin(T &a, T b) { a = min(a, b); }

signed main() {
  int H, W, h, w;
  cin >> H >> W >> h >> w;
  cout << H * W - (h * W + w * H - h * w) << endl;
  return 0;
}


Measured memory_bytes: 256
a,b,c,x,y=map(int,input().split())
ans=10**18
for i in range(0,2*max(x,y)+2,2):
  X,Y=x,y
  X-=i//2
  Y-=i//2
  X=max(0,X)
  Y=max(0,Y)
  ans=min(ans,a*X+b*Y+c*i)
print(ans)

Measured memory_bytes: 3064
#include<iostream>
#include<string>
using namespace std;
int main() {
	int a, b,h,  kazu;
	int  ans[1000];
	kazu = 0;
	while (1) {
		cin >> a >> b;
		if (a == 0) {
			goto a;
		}
		h = 0;
		kazu = kazu + 1;
		if (a >= 2) {
			h = 31;
		}
		if (a >= 3) {
			h = h + 29;
		}
		if (a >= 4) {
			h = h + 31;
		}
		if (a >= 5) {
			h = h + 30;
		}
		if (a >= 6) {
			h = h + 31;
		}
		if (a >= 7) {
			h = h + 30;
		}
		if (a >= 8) {
			h = h + 31;
		}
		if (a >= 9) {
			h = h + 31;
		}
		if (a >= 10) {
			h = h + 30;
		}
		if (a >= 11) {
			h = h + 31;
		}
		if (a >= 12) {
			h = h + 30;
		}
		h = h + b;
		while (h > 7) {
			h = h % 7;
		}
		ans[kazu] = h;
		
	}
a:;
	for (int x = 1; x <= kazu; x++) {
		if (ans[x] == 0) {
			cout << "Wednesday" << endl;
		}
			if (ans[x] == 1) {
				cout << "Thursday" << endl;
			}
		if (ans[x] == 2) {
			cout << "Friday" << endl;
		}
		if (ans[x] == 3) {
			cout << "Saturday" << endl;
		}
		if (ans[x] == 4) {
			cout << "Sunday" << endl;
		}
		if (ans[x] == 5) {
			cout << "Monday" << endl;
		}
		if (ans[x] == 6) {
			cout << "Tuesday" << endl;
		}
	}
}


Measured memory_bytes: 2988
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;

public class Main {
    public void solve(BufferedReader stdin, PrintWriter stdout) throws NumberFormatException, IOException {
        long n = Long.parseLong(stdin.readLine());
        long a = ((100 * n) % 108 == 0) ? 100 * n / 108 : 100 * n / 108 + 1;
        long b = ((100 * (n + 1)) % 108 == 0) ? 100 * (n + 1) / 108 - 1 : 100 * (n + 1) / 108;

        if (a <= b) {
            stdout.println(a);
        } else {
            stdout.println(":(");
        }
    }


    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter stdout = new PrintWriter(System.out, false);
        new Main().solve(stdin, stdout);
        stdout.flush();
    }
}


Measured memory_bytes: 23508
#include <bits/stdc++.h>
using namespace std;
void Main();

using i8  = int8_t;   /* -128 ~ 127 */
using u8  = uint8_t;  /* 0 ~ 255 */
using i16 = int16_t;  /* -32,768 ~ 32,767 */
using u16 = uint16_t; /* 0 ~ 65,535 */
using i32 = int32_t;  /* -2,147,483,648 ~ 2,147,483,647 */
using u32 = uint32_t; /* 0 ~ 4,294,967,295 */
using i64 = int64_t;  /* -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807 */
using u64 = uint64_t; /* 0 ~ 18,446,744,073,709,551,615 */
using f32 = float;    /* (-3.4 * 10^38) ~ (3.4 * 10^38) */
using f64 = double;   /* (-1.7 * 10^308) ~ (1.7 * 10^308) */
using f80 = __float80;

template <class T> using Vec = vector<T>;

/* 定数 */
constexpr i64 INF = 1010000000000000017;
constexpr i64 MOD = 1e9 + 7;
constexpr f64 EPS = 1e-12;
constexpr f64 PI = 3.14159265358979323846;

#define ALL(v) v.begin(), v.end()

#define GCD(a, b) __gcd(a, b) /* 最大公約数 */
#define LCM(a, b) a / __gcd(a, b) * b /* 最小公倍数 */

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

void Main() {
    string S;
    u32 Q;
    cin >> S;
    cin >> Q;
    bool r = false;
    string ls, rs;
    for (int i = 0; i < Q; i++) {
        u32 T;
        cin >> T;
        if (T == 1) r = !r;
        else if(T == 2) {
            u32 F;
            char C;
            cin >> F >> C;
            if (r) {
                if (F == 1) rs = rs + C;
                else if (T == 2) ls = C + ls;
            } else {
                if (F == 1) ls = C + ls;
                else if (T == 2) rs = rs + C;
            }
        }
    }
    string res = ls + S + rs;
    if (r) reverse(ALL(res));
    cout << res << endl;
}


Measured memory_bytes: 1420
def prime_eratosthenes_edit(n):
    prime_list = []
    num_set = set()
    for i in range(2, 10 ** 6):
        if i not in num_set:
            prime_list.append(i)
            if n <= i:
                return i
            for j in range(i * i, 10 ** 6, i):
                num_set.add(j)


print(prime_eratosthenes_edit(int(input())))

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

using namespace std;

using ll = long long;
using ld = long double;

using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vs = vector<string>;

typedef pair<ll, ll> P;

#define bit(n) (1LL << (n))

//#define int long long

#define all(v) v.begin(), v.end()
#define sortAl(v) sort(all(v))
#define sortAlr(v)          \
  sort(v.begin(), v.end()); \
  reverse(v.begin(), v.end())

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

#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define FORm(i, m) for (auto i = m.begin(); i != m.end(); i++)

template <class T>
inline void chmax(T &a, T b) {
  a = std::max(a, b);
}
template <class T>
inline void chmin(T &a, T b) {
  a = std::min(a, b);
}

#define mod (ll)(1e9 + 7)
#define INF LLONG_MAX

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(20);

  ll n;
  cin >> n;

  vll v(n);
  rep(i, n) {
    cin >> v[i];
  }

  rep(i, n) {
    ll tmp;
    cin >> tmp;
    v[i] -= tmp;
  }

  ll ans = 0;

  rep(i, n) {
    if (v[i] > 0) {
      ans += v[i];
    }
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
import java.io.*;
import  java.util.*;
import static java.lang.System.in;

public class Main{
    static int n,m;
    static long[] head,pos;
    public static void main(String[] args)throws IOException{
        Scanner sc = new Scanner(System.in);
        //BufferedReader reader = new BufferedReader(new InputStreamReader(in));
        //String[] buf = reader.readLine().split(" ");
        char b = sc.next().charAt(0);
        char ans;
        if(b=='A') ans = 'T';
        else if(b=='T') ans ='A';
        else if(b=='C') ans = 'G';
        else ans = 'C';
        System.out.println(ans);
    }
}


Measured memory_bytes: 21844
class UnionFind(object):
    def __init__(self, N):
        self.parent = [-1] * N #parent[i] は(i+1)番目の要素が含まれる要素数の(-1)倍
    #要素が負-->その数を親とするグループに属する要素の数×(-1)
    #要素が正-->親のindex

    #Aがどのグループに属しているかを調べる
    def root(self, A):
        if self.parent[A-1] < 0: #負の数-->その数は親
            return A
        self.parent[A-1] = self.root(self.parent[A-1]) #負では無い時、親の場所が入っているから、親が属しているグループを、自分自身に入れる(一度確認したところは直接親を見れるようにする)
        return self.parent[A-1] #親の位置を返す

    #Aが含まれているグループに属している数を返す
    def size(self, A):
        return -1 * self.parent[self.root(A)-1]

    #AとBをくっ付ける
    def connect(self, A, B):
        A = self.root(A) #Aを含むグループの親を返す
        B = self.root(B) #Bを含むグループの親を返す
        if A == B: #親が同じならなにもしない
            return False
        
        #大きい方(A)に小さい方(B)をつなぎたい
        if self.size(A) < self.size(B): #大小関係が逆の時は入れ替える
            A, B = B, A
        
        self.parent[A-1] += self.parent[B-1] #大きい方に小さい方を加える　（負の数＋負の数 = 新しいグループに含まれる数×(-1)）
        self.parent[B-1] = A #加えられた親の値を、加えた先の親の位置に書き変える
        return True
    
    def same(self, A, B):
        if self.root(A) == self.root(B):
            return True
        else:
            return False

N = int(input())

lst = []
l_append = lst.append
for i in range(N):
    x, y = map(int, input().split())
    l_append([x, y, i])
# print (lst)
edge = []
e_append = edge.append
lst.sort(key = lambda x: x[0])
for i in range(1, N):
    e_append([lst[i-1][2], lst[i][2], min(abs(lst[i-1][0]-lst[i][0]), abs(lst[i-1][1]-lst[i][1]))])
# print (edge)
lst.sort(key = lambda x: x[1])
for i in range(1, N):
    e_append([lst[i-1][2], lst[i][2], min(abs(lst[i-1][0]-lst[i][0]), abs(lst[i-1][1]-lst[i][1]))])
# print (edge)
edge.sort(key = lambda x: x[2])

uni = UnionFind(N)
ans = 0
for i in edge:
    if not uni.same(i[0], i[1]): #違うグループのとき
        uni.connect(i[0], i[1])
        ans += i[2]
print (ans)

Measured memory_bytes: 142372
import Control.Monad

find n i = do
  if i > 0 then
      if i `mod` 10 == 3 then putStr $ " " ++ show n else find n (i `div` 10)
  else
      return ()

call n i = do
  if i <= n then do
    if i `mod` 3 == 0 then putStr $ " " ++ show i else find i i
    call n (i+1)
  else return ()

main = do
  s <- getLine
  let n = read s::Int
  call n 1
  putStrLn ""

Measured memory_bytes: 3980
using System;

namespace atcoderA
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            int[] input = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
            int N = input[0];
            int K = input[1];
            Console.WriteLine(N % K == 0 ? 0 : 1);
        }
    }
}

Measured memory_bytes: 11092
<?php

$n = trim(fgets(STDIN));

$count = 0;
for($i=0;$i<$n;$i++){
    
    $input_array = explode(" ", fgets(STDIN));
    if(trim($input_array[0]) == trim($input_array[1])){
        $count++;
    }else{
        $count = 0;
    }
    
    if($count==3){
        break;
    }
    
}

if($count == 3){
    echo 'Yes';
}else{
    echo 'No';
}

?>


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

using namespace std;

void solve() {
    long long N;
    cin >> N;
    vector<long long> A(N);
    for (long long i = 0; i < N; i++)
    {
        cin >> A[i];
    }
    long long a_max = 0, ans = 0;
    for (long long i = 0; i < N; i++)
    {
        if (a_max > A[i])
        {
            ans += a_max - A[i];
        }
        a_max = max(a_max, A[i]);
    }
    
    cout << ans << endl;
}

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

Measured memory_bytes: 4756
//Sani buyuk Osman Pasa Plevneden cikmam diyor.
//FatihSultanMehmedHan
//Abdulhamid Han Elmuzaffer Daima
//Bismillahirrahmanirrahim

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>

using namespace std;

typedef long long int lo;
typedef pair< int,int > PII;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid (start+end)/2
#define ort (bas+son)/2

const lo MAX = -1000000000000000000; 
const lo MIN = 1000000000000000000; 
const lo inf = 1000000000; 
const lo KOK = 100000; 
const lo LOG = 30; 
const lo li = 100005; 
const lo mod = 1000000007; 

int n,m,cev,b,a[li],k;
string s,ss,sss;
vector<int> v;

inline int solve(){
	cin>>s>>ss;
	if(s.size()>ss.size()){
		cout<<"GREATER\n";return 0;
	}
	if(s.size()<ss.size()){
		cout<<"LESS\n";return 0;
	}
	if(s>ss){
		cout<<"GREATER\n";return 0;
	}
	if(s<ss){
		cout<<"LESS\n";return 0;
	}
	cout<<"EQUAL\n";
	return 0;
}

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


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;
int main(){
	int n,m;
	cin>>n>>m;
	char c[50][50];
	char d[50][50];
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin>>c[i][j];
		}
	}
	for(int i=0;i<m;i++){
		for(int j=0;j<m;j++){
			cin>>d[i][j];
		}
	}
	for(int i=0;i<=n-m;i++){
		for(int j=0;j<=n-m;j++){
			for(int o=0;o<m;o++){
				for(int p=0;p<m;p++){
					if(c[i+o][j+p]!=d[o][p])goto a;
				}
			}
			cout<<"Yes"<<endl;
			return 0;
			a:;
		}
	}
	cout<<"No"<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define REP(i,n) for (int i = 1; i < (int)(n); i++)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define vout(x) rep(i,x.size()) cout << x[i] << " "
template<class T> bool chmin(T &a, T b) {if(a>b) {a=b;return 1;}return 0;}
template<class T> bool chmax(T &a, T b) {if(a<b) {a=b;return 1;}return 0;}
using namespace std;
using vint = vector<int>;
using vvint = vector<vector<int>>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<int,int>;
const int inf = 1e9;
const ll inf_l = 1e18;
const int MAX = 1e5;

int main() {
    int n, k; cin >> n >> k;
    vint a(n);
    rep(i,n) cin >> a[i];
    rep(i,k) {
        vint imos(n+1,0);
        rep(j,n) {
            imos[max(j-a[j],0)]++;
            imos[min(j+a[j]+1,n)]--;
        }
        vint a_tmp(n,imos[0]);
        set<int> st;
        REP(i,n) {
            int x = a_tmp[i-1] + imos[i];
            a_tmp[i] = x;
            st.insert(x);
        }
        swap(a_tmp,a);
        if (st.size() == 1 && a[0] == n) break;
    }
    rep(i,n) cout << a[i] << " ";
}

Measured memory_bytes: 8372
#ABC079 C bit全探索
A, B, C, D = input()
for i in range(2**3):
    op = ['+']*3
    for j in range(3):
        if (i >> j) & 1:
            op[j]='-'
    if eval(A+op[0]+B+op[1]+C+op[2]+D) ==7:
        print(A+op[0]+B+op[1]+C+op[2]+D+'=7' )
        break

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

int min(int a,int b){
  if(a < b){
    return a;
  }
  return b;
}

int main(void){
  int N;
  scanf("%d",&N);

  char s[10];
  int ans = 0;
  int firstB = 0,endA = 0,both = 0;
  for (int i = 0; i < N; i++) {
    scanf("%s",s);
    int flag = 0;
    if(s[0] == 'B' && s[strlen(s)-1] == 'A') both++;
    else if(s[0] == 'B') firstB++;
    else if(s[strlen(s)-1] == 'A') endA++;
    for (int j = 0; j < strlen(s); j++) {
      if(s[j] == 'A') flag = 1;
      else if(flag == 1 && s[j] == 'B'){
        ans++;
        flag = 0;
      }else flag = 0;
    }
  }

  if(both == 0) ans += min(firstB,endA);
  else{
    if(firstB+endA > 0) ans += both+min(firstB,endA);
    else ans += both-1;
  }

  printf("%d\n",ans);

  return 0;
}

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

ans = 0
while True:
    flg = True
    for i in range(n):
        # i = 0
        if a[i]%2 == 0:
            a[i] = a[i]/2
        else:
            flg = False
    if flg:
        ans += 1
    else:
        break
print(ans)


Measured memory_bytes: 2940
#include<stdio.h>

long long int gcm(long long a,long long b){
	long long r,tmp;
	if(a<b){
		tmp=a;
		a=b;
		b=tmp;
	}
	
	r=a%b;
	while(r!=0){
		a=b;
		b=r;
		r=a%b;
	}
	return b;
}

int main(){
	int N;
	scanf("%d",&N);
	long long A[N];
	for(int i=0;i<N;i++)scanf("%lld",&A[i]);
	long long ans=A[0];
	for(int i=0;i<N-1;i++)ans=gcm(ans,A[i+1]);
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 896
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public class MainClass
{
	public const long Giri = 1000000007;


	public static void Main(string[] args)
	{
		var n = Console.ReadLine().ToLong();
		
		var divisor = new List<long>();
		long min = n;
		for(long i = 1; i * i <= n; i++)
		{
			if(n % i == 0)
			{
				min = Math.Min(min, Math.Max(i.ToString().Length, (n/i).ToString().Length));
			}
		}
		
		Console.WriteLine(min);
	}
	
	static long GCD(long a, long b)
	{
		var v = new[] { a, b };
		while (v[1] != 0) { v = new[] { v[1], v[0] % v[1] }; }
		return v[0];
	}
	public static string[] Input() { return Console.ReadLine().Split(' '); }
	public static int Clamp(int val, int max, int min = 0) { return Math.Min(max, Math.Max(min, val)); }
}

public static class Smarter
{
	public static int ToInt(this string str) { return int.Parse(str); }
	public static long ToLong(this string str) { return long.Parse(str); }
	public static int[] ToInt(this string[] str)
	{
		var r = new int[str.Length];
		for(int i = 0; i < str.Length; i++) r[i] = str[i].ToInt();
		return r;
	 }
}



Measured memory_bytes: 11220
#include<bits/stdc++.h>
using namespace std;
int main() {
    long long a, b, c, d; cin >> a >> b >> c >> d;
    if(a >= 0) {
        if(d < 0) {
            cout << a*d << endl;
        }
        else {
            cout << b*d << endl;
        }
    }
    else if(b >= 0 && 0 - a <= b - 0) {
        if(0 - c > d - 0) {
            cout << max(b*d, a*c) << endl;
        }
        else if(d <= 0) {
            cout << a*c << endl;
        }
        else {
            cout << b*d << endl;
        }
    }
    else if(b >= 0 && 0 - a > b - 0) {
        if(c >= 0) {
            cout << b * d << endl;
        }
        else if(0- c < d - 0) {
            cout << max(a*c, b*d) << endl;
        }
        else {
            cout << a*c << endl;
        }
    }
    else {
        if(0 <= c) {
            cout << b*c << endl;
        }
        else {
            cout << a*c << endl;
        }
    }
}

Measured memory_bytes: 3628
from collections import deque
s = input()
q = int(input())
inv = False
pr, su = deque(), deque()
for _ in range(q):
    query = input()
    if query[0] == '1':
        inv = not inv
    else:
        _, f, c = query.split()
        if inv:
            if f == '1': su.append(c)
            else: pr.append(c)
        else:
            if f == '1': pr.append(c)
            else: su.append(c)
ans = ''.join(pr)[::-1] + s + ''.join(su)
print(ans[::-1] if inv else ans)

Measured memory_bytes: 12260
from fractions import gcd


def cnt_div2(x):
    ret = 0
    while x % 2 == 0:
        ret += 1
        x //= 2

    return ret


n, m = map(int, input().split())
a = list(map(int, input().split()))

aa = [e // 2 for e in a]

cnt = cnt_div2(aa[0])
for e in aa:
    if cnt_div2(e) != cnt:
        print(0)
        exit()


def lcm(x, y):
    return x // gcd(x, y) * y


c = 1
for e in aa:
    c = lcm(c, e)

ans = m // c
print((ans + 1) // 2)


Measured memory_bytes: 16308
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
  int N, X;
  cin >> N >> X;
  int L[N];
  for(int i=0; i<N; i++) {
    cin >> L[i];
  }
  int cnt=0;
  for(int i=0; i<N+1; i++) {
    if(cnt+L[i]<=X) {
      cnt+=L[i];
    }
    else {
      cout << i+1 << endl;
      return 0;
    }
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const ll INF = 100000000;
#define rep1(i, n) for (ll i=0; i<(n); i++) 
#define rep2(i, k, n) for (ll i=k; i<(n); i++)


int main() {
    ll n;
    cin >> n;
    vector<ll> a(n+1, 0), b(n+10, 0);
    rep2(i, 2, n+1) {
        cin >> a[i];
        b[a[i]]++;
    }
    rep2(i, 1, n+1){
        cout << b[i] << endl;
    }
}

Measured memory_bytes: 6428
#include <bits/stdc++.h>
using namespace std;
using ll =long long;
#define all(v) v.begin(),v.end()
 
int main() {
 ll N,W;
  cin>>N>>W;
  vector<pair<ll,ll>> vec(N);
  for(ll i=0;i<N;i++) {
ll w,v;
    cin>>w>>v;
    vec[i]=make_pair(w,v);
  }
  
  vector<vector<ll>> dp(N+1,vector<ll>(W+1,0));
 for(ll i=N-1;i>=0;i--) {
for(ll j=0;j<=W;j++) {
if(vec[i].first>j) {
dp[i][j]=dp[i+1][j];
}
  else {
    dp[i][j]=max(dp[i+1][j],dp[i+1][j-vec[i].first]+vec[i].second);
  }
}
 }
  
  
  cout<<dp[0][W]<<endl;
}


  

Measured memory_bytes: 83152
n, m, X, Y = map(int, input().split())

x = list(map(int, input().split()))
y = list(map(int, input().split()))
x.append(X)
y.append(Y)
x.sort()
y.sort()
if y[0] - x[-1] >= 1:
    print("No War")
else:
    print("War")  

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

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

#define FOR(i, n, m) for (ll(i) = (m); (i) < (n); ++(i))
#define REP(i, n) FOR(i, n, 0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll)1e15;

string S[7] = {"SUN", "MON", "TUE", "WED", "THU", "FRI", "SAT"};
int main()
{
    string T;
    cin >> T;
    REP(i, 7)
    {
        if (T == S[i])
        {
            ll j = 7 - i;
            cout << j << endl;
            break;
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <functional>
#include <limits.h>
#include <set>
#include <map>
#include <tuple>
using namespace std;



#define ll long long
#define ull unsigned long long
#define rep(i,N) for (ll i=0;i<N;i++)
#define loop(i,N,M) for(ll i=N;i<M;i++)
#define MAX(v) *max_element(v.begin(),v.end())
#define MIN(v) *min_element(v.begin(),v.end())
#define SORTL2S(type,v) sort(v.begin(),v.end(),greater<type>())
#define SORTS2L(type,v) sort(v.begin(),v.end())
#define SORTMF(v,func) sort(v.begin(),v.end(),func)
#define MP(a,b) make_pair(a,b)

ll debugFlag = false;
template<typename T> void debug(T&);
template<typename T> void debug(T&, bool);
template<typename T> void debug(vector<T>&);
template<typename T> void debug(vector<T>&, bool);
template<typename T, typename U> void debug(pair<T, U>&);
template<typename T, typename U> void debug(pair<T, U>&, bool);

template<typename T>
void debug(T& obj) {
	debug(obj, true);
}

template<typename T>
void debug(T& obj, bool lnFlag) {
	if (!debugFlag) return;
	cout << obj;
	if (lnFlag) cout << endl;
}

template<typename T>
void debug(vector<T>& obj) {
	debug(obj, true);
}

template<typename T>
void debug(vector<T>& obj, bool lnFlag) {
	if (!debugFlag) return;
	cout << "[";
	rep(i, obj.size()) {
		if (i != 0) cout << ",";
		debug(obj[i], false);
	}
	cout << "]";
	if (lnFlag) cout << endl;
}

template<typename T, typename U>
void debug(pair<T, U>& obj) {
	debug(obj, true);
}

template<typename T, typename U>
void debug(pair<T, U>& obj, bool lnFlag) {
	if (!debugFlag) return;
	cout << "(";
	debug(obj.first, false);
	cout << ",";
	debug(obj.second, false);
	cout << ")";
	if (lnFlag) cout << endl;
}

vector<bool> human;
ll N;
vector<vector<pair<ll, ll>>> say;
ll honest;
ll ans;

void calc(int num) {

	if (num < N) {
		human[num] = true;
		honest+=1;
		calc(num + 1);
		human[num] = false;
		honest-=1;
		calc(num + 1);
		return;
	}

	bool flag = true;
	rep(i, N) {
		if (human[i] == false) continue;

		rep(j, say[i].size()) {

			if (human[say[i][j].first - 1] == false && say[i][j].second == 1) flag = false;
			if (human[say[i][j].first - 1] == true && say[i][j].second == 0) flag = false;

		}

	}

	if (flag) ans = max(ans, honest);

}

void solve() {
	
	cin >> N;
	human.resize(N, true);
	say.resize(N, vector<pair<ll, ll>>());
	rep(i, N) {
		ll A;
		cin >> A;
		say[i].resize(A);
		rep(j, A) cin >> say[i][j].first >> say[i][j].second;
	}

	honest = 0;
	ans = 0;

	calc(0);

	cout << ans;


}


int main(int argc, char* argv[]) {
	if (argc == 2 && string(argv[1]) == "debug") debugFlag = true;
	solve();
	return 0;
}


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

#define rep(x,n) for(int x=0;x<n;x++)

string cal(string s){
	int cnt=0;
	int f=0;
	rep(i,s.size()){
		if(s[i]=='A' && f%2==0)f=1;
		if(s[i]=='Z' && f%2==1){
			f=0;
			cnt++;
		}
	}
	if(cnt==0)return "-1";
	string res="";
	rep(i,cnt)res+="AZ";
	return res;
}

int main(){
	
	for(string s;cin>>s;)cout<<cal(s)<<endl;
	
	return 0;
}


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

int main()
{
    int a;
    cin >> a;
    vector<double> g(a);
    double ans;
    for (int i = 0; i < a; i++)
    {
        cin >> g.at(i);
        ans += 1 / g.at(i);
    }
    ans = 1 / ans;
    cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define SORT(c) sort((c).begin(),(c).end())
#define IINF INT_MAX
#define LLINF LLONG_MAX
#define DEBUG false
 
typedef long long ll;
typedef pair<int, int> ii;

int small[] = {0, 20, 19, 20, 19, 20, 19, 20, 19, 20, 19};
int bigy = 20 * 10;
int smally = (19 + 20) * 5;

int main() {
	
	vector<ll> cnt(600000);
	
	REP(i, 2, 1001){
		REP(j, 0, i-1){
			cnt[(i * (i+1) / 2) - (j * (j+1) / 2)]++;
		}
	}
	
	int n;
	while(cin >> n, n){
		cout << cnt[n] << endl;
	}

	return 0;
}

Measured memory_bytes: 7268
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <cmath>
#include <iomanip>
#include <bitset>
#include <string>
#include <stdlib.h>
using namespace std;
//cout <<  << endl;
typedef long long int ll;
typedef long double ld;

int main(){
    ll a,b,c;
    cin >> a >> b >> c;
    cout << (a-b+1)*(a-c+1) << endl;
    return 0;
}


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

using ll = long long int;

const int MAX = (int)(1e5 + 5);
const ll INF = (ll)(1e10 + 5);

const int MAX_N = (int)(5e2 + 5);
const int MAX_C = (int)(3e1 + 5);

int n, c;

int d_arr[MAX_C][MAX_C], c_arr[MAX_N][MAX_N];

int cnt[3 + 5][MAX_C];

ll ans = INF;

int main(void) {
  // Here your code !
  scanf("%d %d", &n, &c);
  for (int i = 1; i <= c; ++i) for (int j = 1; j <= c; ++j) {
    scanf("%d", &(d_arr[i][j]));
  }

  for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) {
    scanf("%d", &(c_arr[i][j]));
  }

  for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) {
    cnt[(i + j) % 3][c_arr[i][j]] += 1;
  }

  for (int i = 1; i <= c; ++i) {
    for (int j = 1; j <= c; ++j) {
      if (i == j) continue;
      for (int k = 1; k <= c; ++k) {
        if (i == k || j == k) continue;

        ll tmp = 0;

        for (int l = 1; l <= c; ++l) {
          tmp += cnt[0][l] * d_arr[l][i];
        }

        for (int l = 1; l <= c; ++l) {
          tmp += cnt[1][l] * d_arr[l][j];
        }

        for (int l = 1; l <= c; ++l) {
          tmp += cnt[2][l] * d_arr[l][k];
        }

        ans = min(ans, tmp);
      }
    }
  }

  printf("%lld\n", ans);

  return 0;
}


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

typedef struct R{
  int id;
  string name;
  int score;
    
} R;

bool comp(R lhs, R rhs){
  if(lhs.name != rhs.name) return lhs.name < rhs.name;
  else return lhs.score > rhs.score;
}

int main()
{
  int N;
  vector<R> rest;
  cin >> N;

  rep(i,N){
    R r;
    r.id = i+1;
    cin >> r.name >> r.score;
    rest.push_back(r);
  }

  sort(rest.begin(), rest.end(), comp);

  rep(i,N){
    cout << rest[i].id << endl;
  }
}

Measured memory_bytes: 256
# include <bits/stdc++.h>
# define ll int64_t
# define rep(i,n) for(ll i=0;i<n;i++)
# define rrep(i,n) for(ll i=1;i<=n;i++)
# define ALL(x) (x).begin(), (x).end()
# define SZ(x) ((int)(x).size())
# define pb push_back
# define mod 1000000007
# define vec vector
#define dump(x) cerr<<#x<<"="<<x<<endl

using namespace std;

bool compare_by_b(pair<string,ll> a,pair<string,ll> b){
    if(a.second != b.second) return a.second<b.second;
    else return a.first<b.first;
}

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

ll factorial(ll n){
    ll x=1;
    rrep(i,n) (x*=i)%=mod;
    return x;
}

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

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

//累乗だってさ
ll modpow(ll a,ll n,ll mod1) {
    ll res=1;
    while(n>0){
        if(n&1) res=res*a%mod1;
        a = a*a%mod1;
        n >>= 1;
    }
    return res;
}

ll combination(ll n,ll r){
    ll sum=1;
    rrep(i,min(r,n-r)) (sum*=(n-i+1))%=mod;
    return sum;
}

//逆元だってさ
ll modinv(ll a,ll mod1) {
    return modpow(a, mod1 - 2, mod1);
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    ll k,sum=0;
    cin>>k;
    for(ll i=1;i<=k;i++){
        for(ll j=1;j<=k;j++){
            for(ll m=1;m<=k;m++){
                ll a=gcd(i,j);
                sum+=(gcd(a,m));
            }
        }
    }
    cout<<sum<<endl;
    return 0;
}


Measured memory_bytes: 3656