akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<unordered_map>
#include<set>
#include<algorithm>
#include<functional>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cassert>
#include<ctime>
using namespace std;

#define mind(a,b) (a>b?b:a)
#define maxd(a,b) (a>b?a:b)
#define absd(x) (x<0?-(x):x)
#define pow2(x) ((x)*(x))
#define rep(i,n) for(int i=0; i<n; ++i)
#define repr(i,n) for(int i=n-1; i>=0; --i)
#define repl(i,s,n) for(int i=s; i<=n; ++i)
#define replr(i,s,n) for(int i=n; i>=s; --i)
#define repf(i,s,n,j) for(int i=s; i<=n; i+=j)
#define repe(e,obj) for(auto e : obj)

#define SP << " " <<
#define COL << " : " <<
#define COM << ", " <<
#define ARR << " -> " <<
#define PNT(STR) cout << STR << endl
#define POS(X,Y) "(" << X << ", " << Y << ")"
#define DEB(A) " (" << #A << ") " << A
#define DEBREP(i,n,val) for(int i=0; i<n; ++i) cout << val << " "; cout << endl
#define ALL(V) (V).begin(), (V).end()
#define INF 1000000007
#define INFLL 1000000000000000007LL
#define EPS 1e-9

typedef unsigned int uint;
typedef unsigned long ulong;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
#define P_TYPE int
typedef pair<P_TYPE, P_TYPE> P;
typedef pair<P, P_TYPE> PI;
typedef pair<P_TYPE, P> IP;
typedef pair<P, P> PP;
typedef priority_queue<P, vector<P>, greater<P> > pvqueue;

#define N 22
#define MOD 1000000007
#define N0 (1 << 21)

int n;
int a[N][N];

ll memo[N][N0];
ll dfs(int i, int state) {
  ll r = 0;
  if(i == n) return 1;
  if(memo[i][state] != -1) {
    return memo[i][state];
  }
  rep(j, n) {
    if(a[i][j] && ((state & (1 << j)) == 0)) {
      r = (r + dfs(i+1, state | (1 << j))) % MOD;
    }
  }
  return memo[i][state] = r;
}

int main() {
  cin >> n;
  rep(i, n) rep(j, n) cin >> a[i][j];
  rep(i, n) rep(j, 1<<n) memo[i][j] = -1;
  cout << dfs(0, 0) << endl;
  return 0;
}

Measured memory_bytes: 346368
#include<iostream> 
#include<iomanip> 
#include<vector> 
#include<map> 
#include<set> 
#include<algorithm> 
#include<numeric> 
#include<limits> 
#include<bitset> 
#include<functional> 
#include<type_traits> 
#include<queue> 
#include<stack> 
#include<array> 
#include<random> 
#include<utility> 
#include<cstdlib> 
#include<ctime>
#define INT_MAX 2147483647
#define _LIBCPP_DEBUG 0
#define _GLIBCXX_DEBUG
#define rep(i,n) for (int i = 0; i < (n); ++i)	
using namespace std;


int max(int a,int b) {
	int max;
	if (a > b) max = a;
	else max = b;
	return max;
}
int min(int a, int b) {
	int min;
	if (a < b) min = a;
	else min = b;
	return min;
}


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

	int sum = 0;

	if (a + b >= k) {
		if (a < k)
			sum = a;
		else
			sum = k;
	}
	else {
		sum = a + a + b - k;
	}

	cout << sum << endl;
}

Measured memory_bytes: 3192
#include <iostream>
#include<vector>
#include <math.h>
#include<stdio.h>
#include <climits>
#include<algorithm>
#include<string>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define LL  long long 
#define Pi 3.14159265358979;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int i = 0, j = 0;//ループ用配列

	string s;
	int favorite = 753 , d=0;
	int a, b, c;
	int ans = 1001001001;

	cin >> s;

	rep(i, s.size()-2) {
		a = s[i] - 48;
		b = s[i+1] - 48;
		c = s[i+2] - 48;
		d = a * 100 + b * 10 + c;

		if (abs(favorite - d) < ans)ans = abs(favorite - d);
	}
	cout << ans << "\n";

}


Measured memory_bytes: 256
#  dictionary

import sys

my_dict = dict()
n = int(input())

for i in range(n):
    query,value = sys.stdin.readline().split()
    if query == "insert":
        my_dict[value] = True
    elif query == "find":
        if value in my_dict:
            print("yes")
        else:
            print("no")


Measured memory_bytes: 33444
#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
    int N,K;
    cin >> N >>K ;
    vector<int> H(N);
    for (int i = 0; i < N ; i++) {
        cin >> H.at(i);
    }
    sort(H.begin(),H.end());
    long long count=0;
    for (int i = 0; i < N-K; i++)
    {
        count = count + H[i];
    }
    cout << count;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n; string s; cin>>n>>s;
	if(n%2==1) {printf("No"); return 0;}
	for(int i=0;i<n/2;i++) if(s[i]!=s[i+n/2]) {printf("No"); return 0;}
	printf("Yes");
}

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

int main() {

	int x, y;

	while (true) {
	
		cin >> x >> y;

		if (x == 0 && y == 0) break;

		if (x > y) swap(x, y);

		cout << x << " " << y << endl;
	
	}
	return 0;
}

Measured memory_bytes: 2964
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
typedef vector<int> VI;
typedef pair<int, int> pii;
typedef priority_queue<int> PQ;
template<class T>bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
#define fore(i,a) for(auto &i:a)
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
//vector<vector<int> > dp;
//vector<vector<vector<int> > > vvvi;
//dp=vector<vector<int> >(N, vector<int>(M,0));
//vector<pair<int,int> > v;
//v.push_back(make_pair(x,y));
//priority_queue<int,vector<int>, greater<int> > q2;



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

	int H, N;
	cin >> H >> N;
	VI A(N);
	REP(i, N)cin >> A[i];
	int sum = 0;
	REP(i, N)sum += A[i];



	if (sum >= H)cout << "Yes" << endl;
	else cout << "No" << endl;

	return 0;
}



Measured memory_bytes: 1152
from math import sqrt


def f(b, n):
    if n < b:
        return n
    else:
        return f(b, n//b) + n % b


def divisors(P):
    res = set([])
    for i in range(1, P+1):
        if i**2 > P:
            break
        else:
            if P % i == 0:
                res.add(i)
                res.add(P//i)
    return res


def main():
    N = int(input())
    S = int(input())
    res = 10**18
    if N <= 10**6:
        for b in range(2, N+2):
            if f(b, N) == S:
                res = b
                break
        if res < 10**18:
            print(res)
        else:
            print(-1)
            return

    else:
        #N > 10**6
        for b in range(2, 10**6+2):
            if f(b, N) == S:
                res = b
                break
        if res < 10 ** 18:
            print(res)
            return
        else:
            if N < S:
                print(-1)
                return
            elif N == S:
                print(N+1)
                return
            else:
                div = divisors(N-S)
                for y in div:
                    sub_res = y + 1
                    if f(sub_res, N) == S:
                        res = min(res, sub_res)
                        
                if res < 10**18:
                    print(res)
                else:
                    print(-1)
                return

if __name__ == "__main__":
    main()
    



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

int main(){
    ll n;cin>>n;
    ll ans;cin>>ans;
    rep(i,n-1){
        ll c;cin>>c;
        ans=__gcd(ans,c);
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    long long am;
    cin>>n>>am;
    long long int sum=0;
    long long a[n];
    for(int i=0; i<n; i++)
    {
        cin>>a[i];
        sum=sum+a[i];
    }
    long long  int ans=n;
    long long mini=*min_element(a,a+n);
    ans=ans+((long long)(am-sum)/mini);
    cout<<ans;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,N) for(ll (i)=0;(i)<(N);(i)++)
#define chmax(x,y) x=max(x,y)
#define chmin(x,y) x=min(x,y)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int mod = 1000000007;

int main() {
  int n;
  cin >> n;
  rep(i, n) {
    int a;
    cin >> a;
    if (a % 2 == 1) {
      cout << "first" << endl;
      return 0;
    }
  }
  cout << "second" << endl;
}

Measured memory_bytes: 3628
#include<cstdio>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<cstring>
#include<iostream>
#define IOS ios::sync_with_stdio(0);cin.tie(0)
#define MEM(X,Y) memset(X,Y,sizeof(Y))
#define FRE freopen("abc.in", "r", stdin)
long long int gcd(long long int a, long long int b) { return b ? gcd(b, a % b) : a; }
using namespace std;


int main(void)
{
	long long int a, b, c;
	scanf("%lld%lld%lld", &a, &b, &c);
	if (a + b >= c)
		printf("No");
	else
	{
		if (4 * a * b < (c - b - a) * (c - b - a))
			printf("Yes");
		else
			printf("No");
	}
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
typedef long long ll;
const int INF = 1000100000;
#define rep(i,n) for(int i=0;i<n;++i)

int main(){
  ll h,w;
  cin >>h >> w;
  char a[h+2][w+2];
  rep(i,w+2){
    a[0][i]='#';
    a[h+1][i]='#';
  }
  rep(i,h){
    a[i+1][0]='#';
    a[i+1][w+1]='#';
    rep(j,w){
      cin >> a[i+1][j+1];
    }
  }

  rep(i,h+2){
    rep(j,w+2){
      cout << a[i][j] << flush;
    }
    cout << endl;
  }
}


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

#define pb push_back
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,n,s) for(int i=(s);i<(n);i++)
#define rrep(i,n) for(int i=(n-1);i>=0;i--)
#define rreps(i,n,s) for(int i=s;i>=n;i--)
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 (a>b) { a=b; return 1; } return 0; }

using ll = long long;
using namespace std;
constexpr long long MAX = 5100000;
constexpr long long INF = 1LL << 60;
constexpr int MOD = 1000000007;
int main(){
cin.tie(0);
ios::sync_with_stdio(false);

int n;
cin>>n;
map<char,ll> dic;
rep(i,n){
    string s;
    cin>>s;
    dic[s[0]]++;
}

string march="MARCH";
ll ans=0;
rep(i,5){
    reps(j,5,i+1){
        reps(k,5,j+1){
            char c1=march[i];
            char c2=march[j];
            char c3=march[k];
            ans+=dic[c1]*dic[c2]*dic[c3];
        }
    }
}
cout<<ans<<endl;
return 0;
}

Measured memory_bytes: 3608
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<utility>
#include<cmath>
#include<climits>
#include<queue>
#include<stack>
#include<numeric>
#include<set>
#include<iomanip>
using namespace std;


typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)


int main(){
  int n, x;
  cin >> n >> x;
  vector<int> l(n);

  rep(i, n) cin >> l[i];

  int s = 0;
  int ans = 1;
  for(int i = 0; s <= x && i < n; ++i){
    s += l[i];
    if(s <= x){
        ans++;
    }

  }

  cout << ans << endl;

}


Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		//数値
		int n = Integer.parseInt(sc.next());
		
		if(n<1000) {
			System.out.println("ABC");
		}else {
			System.out.println("ABD");
		}
     }
}

Measured memory_bytes: 35592
#include<iostream>
using namespace std;
int main(){
  string s;
  int len;
  cin >> s;
  len =  s.length();
  int count = 0;

  if (len % 2 == 0){
    for (int i=0;i<len/2; i++){
      if (s[i] != s[len - 1 - i])
        count++;
    }
  }

  else{
    for (int i=0;i<(len-1)/2; i++){
      if (s[i] != s[len - 1 - i])
        count++;
    }
  }

  cout << count;

  return 0;
}

Measured memory_bytes: 256
import math


def resolve():
    import sys
    input = sys.stdin.readline
    # row = [int(x) for x in input().rstrip().split(" ")]
    # n = int(input().rstrip())
    import heapq  # heapqライブラリのimport
    nx = [int(x) for x in input().rstrip().split(" ")]
    x = nx[1]
    a_list = [int(x) for x in input().rstrip().split(" ")]

    heapq.heapify(a_list)
    ans = 0
    while len(a_list) > 0:
        a = heapq.heappop(a_list)

        if len(a_list) == 0:
            if(x == a):
                ans += 1
            break
        if x >= a:
            ans += 1
            x -= a
        else:
            break


    print(ans)

if __name__ == "__main__":
    resolve()


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

const ll MX = 1e18;

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

  vector<ll> a(n);
  ll ans = 1;
  REP(i, n){
    cin >> a[i];
    if(a[i] == 0) {
      cout << 0 << endl;
      return 0;
    }
  }

  REP(i,n){

    //かけてから判定するとオーバーフローしてしまう．
    // if(ans > MX){
    //   cout << -1 << endl;
    //   return 0;
    if(MX/ans < a[i]){
      cout << -1 << endl;
      return 0;

    }
    ans *= a[i];
  }


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

Measured memory_bytes: 3964
#include<stdio.h>
#include<algorithm>
using namespace std;
int main()
{
    int a[100],s,i,n;
    while(~scanf("%d",&n))
    {
        for(i=0;i<n;i++)
            scanf("%d",&a[i]);
        sort(a,a+n);
        s=a[n-1]-a[0];
        printf("%d\n",s);
    }
    return 0;
}


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

int main()
{
  char S;
  cin >> S;

  if (S == 'a' || S == 'i' || S == 'u' || S == 'e' || S == 'o')
  {
    cout << "vowel" << endl;
  }
  else
  {
    cout << "consonant" << endl;
  }
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
	Scanner sc = new Scanner(System.in);
	final int MOD = 1000000007;
	final int MAX = Integer.MAX_VALUE;
	final long LMAX = Long.MAX_VALUE;


	void doIt() {
		Set<Character> odd = new HashSet<>();
		Set<Character> even = new HashSet<>();
		odd.add('R');odd.add('U');odd.add('D');
		even.add('L');even.add('U');even.add('D');
		String s = sc.next();
		for(int i = 0; i < s.length(); i++) {
			char c = s.charAt(i);
			if(i % 2 == 0) {
				if(!odd.contains(c)) {
					System.out.println("No");
					return;
				}
			}
			else {
				if(!even.contains(c)) {
					System.out.println("No");
					return;
				}
			}
		}
		System.out.println("Yes");
	}


	public static void main(String[] args) {
		new Main().doIt();
	}
}


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

using namespace std;

#define int long long
#define endl '\n'
#define maxn 100010
const int MOD = 1000000007;

int mand(pair<int, int> a, pair<int, int> b) {
    return abs(a.first - b.first) + abs(a.second - b.second);
}

void solve() {
    int n;
    cin >> n;

    vector<pair<int, int>> v(n), b;
    for (int i = 0; i < n; ++i) {
        cin >> v[i].first >> v[i].second;
    }
    sort(v.begin(), v.end(), [](pair<int, int> a, pair<int, int> b) {
        return a.first + a.second < b.first + b.second;
    });
    int ans = mand(v[0], v.back());
    sort(v.begin(), v.end(), [](pair<int, int> a, pair<int, int> b) {
        return a.first - a.second < b.first - b.second;
    });
    ans = max(ans, mand(v[0], v.back()));
    cout << ans << endl;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
//    cin >> t;

    while (t--)
        solve();
    return 0;
}


Measured memory_bytes: 6360
#include <iostream>
using namespace std;
int main(void){
    int m, n, b[100], a[100][100], c[100] ={};
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> a[i][j];
        }
    }
    for(int i = 0; i < m; i++){
        cin >> b[i];
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            c[i] += a[i][j]*b[j];
        }
    }
    for(int i = 0; i < n; i++){
        cout << c[i] << endl;
    }
}


Measured memory_bytes: 3140
import scala.io.{StdIn => in}
import scala.collection.{mutable => mu}
import java.util.ArrayDeque

object Main extends App {
  val n = in.readInt

  case class edge(v:Int, d:Int)
  val tree = Array.fill(n)(mu.ListBuffer.empty[edge])

  Iterator.continually(in.readLine)
    .take(n-1)
    .map(_.split(" ").map(_.toInt))
    .foreach { case Array(v, u, d) =>
      new edge(u-1, d) +=: tree(v-1)
      new edge(v-1, d) +=: tree(u-1)
    }

  val colors = Array.ofDim[Int](n)
  val visit = Array.ofDim[Boolean](n)

  def dfs(v:Int, d:Int):Unit = {
    // val stk = mu.Stack.empty[edge]
    val stk = new ArrayDeque[edge]
    stk.push(new edge(v, d))

    while(!stk.isEmpty) {
      val v = stk.pop
      if(!visit(v.v)) {
        visit(v.v) = true
        colors(v.v) = v.d
        for(nv <- tree(v.v) if !visit(nv.v)){
          val d = (v.d + nv.d) % 2
          stk.push(new edge(nv.v, d))
        }
      }
    }
  }

  dfs(0,0)
  println(colors.mkString("\n"))
}

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

const int N=2e5+9;
int a[N],n,k;

int cal(int x){
	int res=0;
	for(int i=0;i<n;i++){
		res+=a[i]/x;
		if(a[i]%x==0)res--;
	}
	return res;
}
int32_t main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin >> n >> k;
    for(int i=0;i<n;i++)
    	cin >> a[i];
    int hi=1e10,lo=1,ans;
    while(hi>=lo){
    	int mid=(hi+lo)/2;
    	if(cal(mid)<=k)
    		ans=mid,hi=mid-1;
    	else lo=mid+1;
    }
    cout << ans;
}


Measured memory_bytes: 5080
#include<bits/stdc++.h>
using namespace std;
int main() {
  int N, banti = 1, res = 1;
  cin >> N;
  vector<int> vec(N);
  for(int i = 0; i < N; i++) cin >> vec[i];
  for(int i = 0; i < N; i++) {
    if(vec[banti-1] == 2) {
      cout << res << endl;
      return 0;
    }
    banti = vec[banti-1];
    res++;
  }
  cout << -1 << endl;
  return 0;
}
    

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

int a,b,c;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>a>>b>>c;
    swap(a,b);
    swap(a,c);
    cout<<a<<" "<<b<<" "<<c;
    
    
    
    
    return 0;
}

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

int main() {
  int N;
  cin >> N;
  vector<int> d(N);
  for (int i = 0; i < N; i++) {
    cin >> d.at(i);
  }
  
  sort(d.begin(), d.end());
  cout << d.at(N/2) - d.at(N/2-1) << endl;
}

Measured memory_bytes: 768
n=int(input())
a=list(map(int,input().split()))
color=[0]*8
over=0
cnt=0
ansmin=0
ansmax=0
for i in a:
    if i<400:
        color[0]+=1
    elif i<800:
        color[1]+=1
    elif i<1200:
        color[2]+=1
    elif i<1600:
        color[3]+=1
    elif i<2000:
        color[4]+=1
    elif i<2400:
        color[5]+=1
    elif i<2800:
        color[6]+=1
    elif i<3200:
        color[7]+=1
    else:
        over+=1
for i in color:
    if i==0:
        cnt+=1
    else:
        ansmin+=1
        ansmax+=1
if ansmin==0:
    print(str(1) + " " + str(ansmax + over))
else:
    print(str(ansmin)+" "+str(ansmax+over))


Measured memory_bytes: 38512
#include <cstdio>

int H, W, h, w;
long long A[510][510];
int ok;
int ok1;
long long bs;

void solve()
{
	ok1 = 0;
	int i, j;
	for(i=0; i<H; i++){
		for(j=0; j<W; j++)
			A[i][j] = 1;
	}
	for(i=h-1; i<H; i+=h){
		for(j=w-1; j<W; j+=w){
			A[i][j] = -h*w;
		}
	}
	int sum = 0;
	for(i=0; i<H; i++){
		for(j=0; j<W; j++)
			sum += A[i][j];
	}
	if(sum > 0){
		printf("Yes\n");
		ok1 = 1;
		for(i=0; i<H; i++){
			printf("%d", A[i][0]);
			for(j=1; j<W; j++)
				printf(" %d", A[i][j]);
			printf("\n");
		}
	}
	else
		printf("No\n");
}

int suc()
{
	long long sum = 0;
	int i, j;
	for(i=0; i<H; i++){
		for(j=0; j<W; j++)
			sum += A[i][j];
	}
	if(sum <= 0)
		return 0;
	for(i=0; i+h-1<H; i++){
		for(j=0; j+w-1<W; j++){
			int k, l;
			sum = 0;
			for(k=i; k<i+h; k++){
				for(l=j; l<j+w; l++)
					sum += A[k][l];
			}
			if(sum >= 0)
				return 0;
		}
	}
	return 1;
}

void srch(int ii, int jj)
{
	if(ok==1)
		return ;
	int i;
	for(i=-3; i<=3; i++){
		A[ii][jj] = i;
		int i3 = ii;
		int j3 = jj+1;
		if(j3 == W){
			i3 ++;
			j3 = 0;
		}
		if(i3 == H){
			if(suc() )
				ok = 1;	
		}
		else
			srch(i3, j3);
	}
}

void solve2()
{
	ok = 0;
	srch(0, 0);
}

void solve1()
{
	int i, j;
	for(i=0; i<H; i++){
		for(j=0; j<W; j++)
			A[i][j] = 1*bs;
	}
	for(i=h-1; i<H; i+=h){
		for(j=w-1; j<W; j+=w){
			A[i][j] = (-h*w+1)*bs-1;
		}
	}
	long long sum = 0;
	for(i=0; i<H; i++){
		for(j=0; j<W; j++)
			sum += A[i][j];
	}
	if(sum > 0){
		//printf("Yes\n");
		ok1 = 1;
		/*for(i=0; i<H; i++){
			printf("%d", A[i][0]);
			for(j=1; j<W; j++)
				printf(" %d", A[i][j]);
			printf("\n");
		}*/
	}
	else{
		ok1 = 0;
		//printf("No\n");
	}
}

int main()
{
	scanf("%d%d%d%d", &H, &W, &h, &w);
	//solve2();
	int i, j, ii;
	for(ii=1; ii<=1000; ii++){
		bs = ii;
		solve1();
		if(ok1 == 1){
			printf("Yes\n");
			for(i=0; i<H; i++){
				printf("%lld", A[i][0]);
				for(j=1; j<W; j++)
					printf(" %lld", A[i][j]);
				printf("\n");
			}
			break;
		}
	}
	if(ii==1001)
		printf("No\n");
	//solve();
	//if(ok1 != ok)
	//	printf("Wrong\n");
	return 0;
}


Measured memory_bytes: 3200
#include<stdio.h>
#include<stdlib.h>

int main(void)
{
    int x1,y1,x2,y2,x3,y3,x4,y4,d1,d2,e1,e2;

    scanf("%d %d %d %d",&x1,&y1,&x2,&y2);

    d1=x2-x1;
    d2=y2-y1;

    e1=-d2;
    e2=d1;

    x4=x1+e1;
    y4=y1+e2;
    x3=x2+e1;
    y3=y2+e2;

    printf("%d %d %d %d",x3,y3,x4,y4);

    return 0;
}

Measured memory_bytes: 128
open System
open System.Collections.Generic

module InputUtility =
    let InputTokens = new Queue<string>()

    let EnsureInput () =
        if InputTokens.Count = 0 then
            let input = Console.ReadLine ()
            let s = input.Split ([|' '|], StringSplitOptions.RemoveEmptyEntries)
            if s.Length > 0 then
                for x in s do InputTokens.Enqueue(x)
                true
            else false
        else true

    let rec ReadNext () =
        if EnsureInput () then InputTokens.Dequeue ()
        else ReadNext ()

    let ReadNextInt () = ReadNext () |> int

    let Read2Int () = ReadNextInt (), ReadNextInt ()

    let Read3Int () = ReadNextInt (), ReadNextInt (), ReadNextInt ()

    let ReadListOf f n =
        let rec loop acc = function
            | 0 -> List.rev acc
            | c -> loop ((ReadNext () |> f) :: acc) (c-1)
        loop [] n

    let MultipleCaseWithId f =
        let caseNum = ReadNextInt ()
        let rec loop index =
            if index = caseNum then ()
            else
                f index
                loop (index + 1)
        loop 0

    let MultipleCase f = MultipleCaseWithId (fun _ -> f ())

    let ReadList n =
        let rec loop acc = function
            | 0 -> List.rev acc
            | c -> loop (ReadNext () :: acc) (c-1)
        loop [] n

open InputUtility

module ARC076 =
    let private Mod = 1000000007L

    let private Reconciled () =
        let rec g x r =
            if x = 0 then r
            else g (x - 1) (r * int64 x % Mod)
        let f x = g x 1L
        let n, m =
            let a, b = Read2Int ()
            if a > b then b, a else a, b
        if n + 1 < m then 0L
        elif n + 1 = m then
            f m * f n % Mod
        else
            2L * f n * f n % Mod
        |> printfn "%d"

    let Entry = Reconciled

ARC076.Entry ()

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

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

int intof(char c) {
    if (c=='R') return 0;
    else if(c=='G') return 1;
    else return 2; // G
}

int main(){
    long long N;
    scanf("%lld",&N);
    std::string S;
    std::cin >> S;

    int n = S.size();
    vector<vector<int>> v(3, vector<int>(n));

    REP(l, n)  {
        if (l) {
            REP(m, 3) v[m][l] = v[m][l-1];
        }
        v[intof(S[l])][l]++;
    }
    ll cnt = 0;
    for (int i = 0; i < N-2; i++)
    {
        for (int j = i+1; j < N-1; j++)
        {
            if (S[i]==S[j]) continue;
            // count k such that j<k<N && k!=2j-i && S[k] is not in {S[i], S[j]}
            int intofsk = 3 - intof(S[i]) - intof(S[j]);
            if (2*j-i>=N) cnt += (v[intofsk][N-1] - v[intofsk][j]); // j < k <= N-1
            else cnt += ((v[intofsk][2*j-i-1] - v[intofsk][j]) + (v[intofsk][N-1] - v[intofsk][2*j-i])); // j < k <= 2j+i-1, 2j+i < k <= N-1
        }
    }
    cout << cnt << endl;
    
    return 0;
}



Measured memory_bytes: 3736
#include<iostream>
#include <cmath>
#include<cstdio>
#include <string>
#include <cwchar>
#include <stdio.h>
#include <ctype.h>
using namespace std;
int main(){
string s;
cin>>s;
for(int i=0;i<s.length();i++)
{
	int a=s[i]-'0';
	if(a==7)
	{
		cout<<"Yes"<<endl;
		return 0;
	}
}
    cout<<"No"<<endl;
    return 0;
}


Measured memory_bytes: 3616
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <cmath>
#include <queue>
#include <deque>
#include <set>
#include <iomanip>
#include <utility>
#define ll long long
#define ld long double
using namespace std;

ll mod=998244353;

int main() {
	int N;
	string S;
	cin >> N >> S;
	vector<int> sten(N*3, 0);
	int rr=0, gg=0, bb=0, now=0;
	for(int i=0; i<N*3; ++i){
	    if(S[i]=='R') ++rr;
	    else if(S[i]=='G') ++gg;
	    else ++bb;
	    if(rr>now && gg>now && bb>now){
	        sten[i]=2;
	        ++now;
	    }
	}
	rr=gg=bb=now=0;
	for(int i=N*3-1; i>=0; --i){
	    if(S[i]=='R') ++rr;
	    else if(S[i]=='G') ++gg;
	    else ++bb;
	    if(rr>now && gg>now && bb>now){
	        sten[i]=1;
	        ++now;
	    }
	}
	ll ans=1;
	for(int i=1; i<=N; ++i) ans=(ans*i)%mod;
	map<char, int> fi, la;
	for(int i=0; i<N*3; ++i){
	    if(sten[i]==1) ++fi[S[i]];
	    else if(sten[i]==2){
	        ans=(ans*la[S[i]])%mod;
	        --la[S[i]];
	    }
	    else{
	        int p=fi['R']+fi['G']+fi['B']-fi[S[i]];
	        ans=(ans*p)%mod;
	        if(S[i]=='R'){
	            if(fi['G']>0){
	                --fi['G'];
	                ++la['B'];
	            }
	            else{
	                --fi['B'];
	                ++la['G'];
	            }
	        }
	        else if(S[i]=='G'){
	            if(fi['R']>0){
	                --fi['R'];
	                ++la['B'];
	            }
	            else{
	                --fi['B'];
	                ++la['R'];
	            }
	        }
	        else{
	            if(fi['R']>0){
	                --fi['R'];
	                ++la['G'];
	            }
	            else{
	                --fi['G'];
	                ++la['R'];
	            }
	        }
	    }
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 1796
#pragma region Include/Defines
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <limits.h>
#include <vector>
#include <stdlib.h>
#include <algorithm>
#include <memory.h>
#include <string.h>
#include <math.h>
#include <string>
#include <algorithm>
#include <functional>
#include <cassert>
#include <map>
#include <set>
#include <iostream>
#include <queue>
#include <time.h>

using namespace std;
typedef long long lli;
typedef vector<int> vi;
typedef vector<lli> vli;
typedef pair<int, int> pii;
typedef pair<lli, lli> pll;
typedef vector<pii> vpii;
typedef vector <pll> vpll;
typedef long double ld;
#define all(a) std::begin(a), std::end(a)

const int INF = 0x3f3f3f3f;
const lli LINF = 0x3f3f3f3f3f3f3f3f;

template<typename T, typename T2> inline void _max(T &a, T2 b) { a = max((T)a, (T)b); }
template<typename T, typename T2> inline void _min(T &a, T2 b) { a = min((T)a, (T)b); }

#ifdef _DEBUG
#define epr(...) fprintf(stderr,__VA_ARGS__)
#else
#define epr(...) 
#endif
#pragma endregion

const int MAX = 2e5 + 10;
int n, a[MAX];

void clear() {
}

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

void solve() {
	lli sum = 0;
	for (int i = 0; i < n; i++) sum += a[i];
	lli mind = LINF;
	lli ps = a[0];
	for (int i = 1; i < n; i++) {
		lli o = sum - ps;
		lli td = abs(o - ps);
		_min(mind, td);
		ps += a[i];
	}
	printf("%lld\n", mind);
}

int main() {
#ifdef _LOCAL_VAN
	freopen("in.txt", "r", stdin);
#endif
	while (scanf("%d", &n) == 1) {
		clear();
		read();
		solve();
#ifndef _LOCAL_VAN
		return 0;
#endif
	}
	return 0;
}

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

int main(){
    int N, M, Q_num;
    std::cin >> N >> M >> Q_num;
    
    std::vector< int > L(M);
    std::vector< int > R(M);
    std::vector< std::vector< int > > LR_cnt(N, std::vector< int >(N, 0));
    std::vector< int > P(Q_num);
    std::vector< int > Q(Q_num);
    for(int i=0; i<M; i++){
        std::cin >> L[i] >> R[i];
        LR_cnt[L[i]-1][R[i]-1]++;
    }
    for(int i=0; i<Q_num; i++){
        std::cin >> P[i] >> Q[i];
    }
    
    std::vector< std::vector< int > > LR_cnt_acc_v(N, std::vector< int >(N, 0));
    for(int i=0; i<N; i++){
        LR_cnt_acc_v[0][i] = LR_cnt[0][i];
        for(int j=1; j<N; j++){
            LR_cnt_acc_v[j][i] = LR_cnt_acc_v[j-1][i] + LR_cnt[j][i];
        }
    }
    std::vector< std::vector< int > > LR_cnt_acc(N, std::vector< int >(N, 0));
    for(int i=0; i<N; i++){
        LR_cnt_acc[i][0] = LR_cnt_acc_v[i][0];
        for(int j=1; j<N; j++){
            LR_cnt_acc[i][j] = LR_cnt_acc[i][j-1] + LR_cnt_acc_v[i][j];
        }
    }
    
    for(int i=0; i<Q_num; i++){
        if(P[i] == 1){
            std::cout << LR_cnt_acc[Q[i]-1][Q[i]-1] << std::endl;
        }else{
            std::cout << LR_cnt_acc[Q[i]-1][Q[i]-1] - LR_cnt_acc[P[i]-2][Q[i]-1] << std::endl;
        }
    }
    
    
    return 0;
    
}


Measured memory_bytes: 8484
import sys
import math
import copy
import random
import itertools
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

dic = dict()

def zalg(s):
    n = len(s)
    ret = [0] * n
    ret[0] = n
    i, j = 1, 0
    while i < n:
        while i + j < n and s[j] == s[i+j]:
            j += 1
        ret[i] = j

        if j == 0:
            i += 1
            continue

        k = 1
        while k < j and k + ret[k] < j:
            ret[i + k] = ret[k]
            k += 1

        i += k
        j -= k

    return ret

def solve(n=None, s1=None, s2=None):
    n = getN()
    s = list(getS())
    ans = 0
    for i in range(n):
        ps = s[i:]
        z = zalg(ps)
        for i, zz in enumerate(z):
            if i >= zz:
                ans = max(ans, zz)
    print(ans)

def main():
    n = getN()
    for _ in range(n):
        solve()
    return


if __name__ == "__main__":
    # main()
    solve()



Measured memory_bytes: 84784
#exec({'RUBY_THREAD_VM_STACK_SIZE'=>'100000000'},'/usr/bin/ruby', $0) if !ENV['RUBY_THREAD_VM_STACK_SIZE']
require 'prime'

def inpf() a=gets.chomp.split(" ").map(&:to_f)end

def inps() a=gets.chomp.split(" ")end

def copy(a) Marshal.load(Marshal.dump(a)) end

def kaijo(n,r = 10**9+7)(n < 2)? 1 : (2..n).inject{|memo,u|memo=(memo*u)%r} end

def na(n,d=0) Array.new(n,d)end

def na2(n,m,d=0) Array.new(n){Array.new(m,d)}end

def na3(n,m,l,d=0) Array.new(n){Array.new(m){Array.new(l,d)}}end

def inp() a=gets.chomp.split(" ").map(&:to_i)end

def r_up(a, b) (a+b-1)/b end

def sum(a) a.inject(:+) end

def big(a,b) return (a>b)? a:b end

def small(a,b) return (a<b)? a:b end

a,b,n = inp
p a*small(b-1,n)/b


Measured memory_bytes: 14428
#include <cstdio>

#define rep(i, j) FOR(i, 0, j)
#define FOR(i, j, k) for(int i = j; i < k; ++i)

using namespace std;

int main(){
  int n, m, p, x[101];
  while(scanf("%d%d%d", &n, &m, &p) && (n || m || p)){
    int sum = 0;
    rep(i, n){
      scanf("%d", x+i);
      sum += x[i];
    }

    if(x[m-1] != 0) printf("%d\n", sum *(100-p)/ x[m-1]);
    else printf("0\n");
  }
  return 0;
}

Measured memory_bytes: 1040
import * as fs from "fs";

let input = (fs.readFileSync("/dev/stdin", "utf8") as string).split("\n");
const n = +input[0];
const a: Array<number> = input[1].split(" ").map((x: string): number => +x);

let min = Infinity;
let min_i = -1;
let max = -Infinity;
let max_i = -1;
for (let i = 0; i < n; i++) {
	if (a[i] < min) {
		min = a[i];
		min_i = i;
	}
	if (a[i] > max) {
		max = a[i];
		max_i = i;
	}
}

let positive = true;
if (max < 0) positive = false;
else if (min < 0) {
	if (-min > max) positive = false;
}

const result = [];

if (positive && min < 0) {
	for (let i = 0; i < n; i++) {
		if (a[i] < 0) {
			a[i] += max;
			result.push([max_i, i]);
		}
	}
}

else if (!positive && max > 0) {
	for (let i = 0; i < n; i++) {
		if (a[i] > 0) {
			a[i] += min;
			result.push([min_i, i]);
		}
	}
}

console.error(a);

if (positive) {
	for (let i = 1; i < n; i++) {
		if (a[i - 1] <= a[i]) continue;
		a[i] += a[i - 1];
		result.push([i - 1, i]);
	}
}

else {
	for (let i = n - 2; i >= 0; i--) {
		if (a[i] <= a[i + 1]) continue;
		a[i] += a[i + 1];
		result.push([i + 1, i]);
	}
}

console.log(result.length);
for (let p of result) {
	console.log(p[0] + 1, p[1] + 1);
}

console.error(a);

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

signed main(){
  
  int X, Y;

  cin >> X >> Y;
  
  for(int i=0;i<=X;i++){
    if( i * 2 + ( X - i ) * 4 == Y ){
      cout << "Yes" << endl;
      return 0;
    }
  }

  cout << "No" << endl;
  
  return 0;
}


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

int main(){
    int A, B;
    cin >> A >> B;
    
    int sum=0;
    if(A < B){
        sum += B;
        B--;
    }else{
        sum += A;
        A--;
    }
    if(A < B){
        sum += B;
        B--;
    }else{
        sum += A;
        A--;
    }
    cout << sum << endl;
    
    
    
    return 0;
}


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

int main(void) {
  ll n,k;
  cin >> n >> k;
  ll mod = 1e9 + 7;
  ll res = 0;
  for(ll i = k;i <= n+1;++i) {
    ll begin = (i - 1) * i / 2;
    ll end = (2 * n - i + 1) * i / 2;
    ll d = (end - begin + 1) % mod;
    res = (res + d) % mod;
  }
  cout << res << endl;
  return 0;
}


Measured memory_bytes: 3608
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int N, X, Y, A[2010][2010];

    cin >> N >> X >> Y;

    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            A[i][j] = abs(i-j);
        }
    }

    A[X][Y] = A[Y][X] = 1;

    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            A[i][j] = A[j][i] = min(A[i][j], A[i][X] + 1 + A[Y][j]);
        }
    }

    int k[2010];

    for (int i = 0; i < N; i++)
    {
        k[i] = 0;
    }

    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            // cout << A[i][j] << " ";
            k[A[i][j]]++;
        }
        cout << "\n";
    }

    for (int i = 1; i < N; i++)
    {
        cout << k[i] / 2 << "\n";
    }



    return 0;
}

Measured memory_bytes: 16000
#include<bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define tc int t; cin>>t; while(t--)
#define mod 1000000007
 
using namespace std;
 
void fastio(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
}
 
int main(){
    fastio();
    int n,p=0;
    string s;
    cin>>n>>s;
    if(s.length()%2!=0)cout<<"No";
    else{
         for(int i=0;i!=s.length()/2;i++){
        if(s[i]!=s[i+s.length()/2])p=1;
        }
        if(p==1)cout<<"No";
        else cout<<"Yes";
    }
    
	return 0;
}

Measured memory_bytes: 256
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author tommy6073
 */

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

class COtoshidama {
public:
    void solve(std::istream& in, std::ostream& out) {
        int N;
        ll Y;
        in >> N >> Y;

        int x = -1, y = -1, z = -1;
        bool found = false;
        for (int i = 0; i <= N && !found; ++i) {
            for (int j = 0; j <= N; ++j) {
                if (i + j > N) {
                    continue;
                }
                int k = N - i - j;
                if ((10000 * j + 5000 * i + 1000 * k) == Y) {
                    found = true;
                    x = j;
                    y = i;
                    z = k;
                    break;
                }
            }
        }

        out << x << ' ' << y << ' ' << z;
    }
};


int main() {
	COtoshidama solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 256
#include <stack>
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <functional>
#include <string>
#include <cstdlib>
#include <numeric>
#include <cstdbool>
#include <map> 
#include<set>
#include<queue>

typedef long long ll;


#define rep(i,n) for(ll i=0;i<n;i++)
using namespace std;

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 long long INF = 1000000000000000;
const ll inf = -1e18;
typedef pair<int, int> P;
ll ma = 1000000000 + 7;
ll h, w, n,k,m; string s,t;
char maze[60][60];
int dis[101][101]; int graph[50][50]; bool vis[50];
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
ll gcd(ll x, ll y) {
	if (x % y == 0) return y;
	return gcd(y, x % y);

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

int main() {
	cin >> s;
	stack<char> x;
	rep(i, s.size()) {
		if (s[i] == 'S') x.push(s[i]);
		else if (s[i] == 'T' && x.size() == 0 || s[i] == 'T' && x.top() == 'T') x.push(s[i]);
		else if (s[i] == 'T' && x.top() == 'S') {
			x.pop();
		}
	}
	cout << x.size() << endl;
}



Measured memory_bytes: 644
#include <stdio.h>
#include <stdlib.h>
 int main(void) {
  long int n,k;
    scanf("%ld %ld",&n,&k );
   if (n%k>labs(k-n%k)) {
    printf("%ld",labs(k-n%k)) ;
   }
else{
  printf("%ld",labs(n%k) );
}
  return 0;
}


Measured memory_bytes: 128
#ifndef LOCAL
#pragma GCC optimize("O3")
#endif
#include "bits/stdc++.h"
using namespace std;
#define sim template <class c
#define ris return *this
#define dor > debug &operator<<
#define eni(x)                                                                    \
    sim > typename enable_if<sizeof dud<c>(0) x 1, debug &>::type operator<<(c i) \
    {
sim > struct rge
{
    c b, e;
};
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c *x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug
{
#ifdef LOCAL
    ~debug()
    {
        cerr << endl;
    }
    eni(!=) cerr << boolalpha << i;
    ris;
} eni(==) ris << range(begin(i), end(i));
}
sim, class b dor(pair<b, c> d)
{
    ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d)
{
    *this << "[";
    for (auto it = d.b; it != d.e; ++it)
        *this << ", " + 2 * (it == d.b) << *it;
    ris << "]";
}
#else
    sim dor(const c &)
    {
        ris;
    }
#endif
}
;
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(0);
#define endl '\n'
typedef long long ll;
typedef long double ld;
const ll MOD = 1e9 + 7;
const ll N = 1e5 + 10;

int main()
{
    fastio int x;
    cin >> x;
    int arr[x];
    for (int i = 0; i < x; i++)
    {
        cin >> arr[i];
    }
    int sum = 0;
    for (int i = 0; i < x; i++)
        for (int j = i+1; j < x; j++)
            sum += arr[i] * arr[j];
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<numeric>
#include<map>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i = 0;i<((int)(n));i++)
#define reg(i,a,b) for(int i = ((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(int i = ((int)(b));i>=((int)(a));i--)
typedef long long ll;
typedef pair<ll, ll> mp;
ll mod=1e9+7;
ll inf=1e18;

//AC

int main(void){
	bool can=true;
	ll n,m,a,b,c,d[100010][2],ans;
	vector<ll> v[100010],s[100010];
	priority_queue<mp> Q;
	rep(i,100010){
		d[i][0]=inf;
		d[i][1]=inf;
	}
	cin>>n>>m;
	rep(i,m){
		cin>>a>>b>>c;
		v[a].push_back(b);
		v[b].push_back(a);
		s[a].push_back(c);
		s[b].push_back(c);
	}
	//点1の数をtとして，
	//機数点目はt-d[i][0],偶数点目はd[i][1]-t
	//これらは1以上である必要あり（tに関する条件が出る）
	d[1][0]=0;
	Q.push(make_pair(1,0));
	while(!Q.empty()){
		mp t=Q.top();Q.pop();
		ll p=t.first, mode=t.second;
		rep(i,v[p].size()){
			ll q=v[p][i];
			if(d[q][1-mode]==inf){
				d[q][1-mode]=s[p][i]-d[p][mode];
				Q.push(make_pair(q,1-mode));
			}else if(d[q][1-mode]!=s[p][i]-d[p][mode]){
				can=false;
				break;
			}
		}
		if(!can)break;
	}
	//全ての条件が出揃ったので上界と下界を求めてansを計算
	if(!can){
		ans=0;
	}else{
		//点1に書かれてる数字の上界・下界，考えられるt
		ll largest=inf,smallest=1,t=-1;
		reg(i,1,n){
			largest=min(largest,d[i][1]-1);
			smallest=max(smallest,-d[i][0]+1);
			if(d[i][0]!=inf && d[i][1]!=inf){
				if((d[i][1]-d[i][0])%2==0 && (d[i][1]-d[i][0])>0){
					if(t==-1){
						t=(d[i][1]-d[i][0])/2;
					}else if(t!=(d[i][1]-d[i][0])/2){
						can=false;
					}
				}else{
					can=false;
				}
			}
		}
		// printf("%lld,%lld\n",largest,smallest);
		ans=max((ll)0,largest-smallest+1);
		if(t!=-1){
			if(smallest<=t && t<=largest){
				ans=1;
			}else{
				ans=0;
			}
		}
		if(!can)ans=0;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 16488
#include <iostream>
using namespace std;
 
int main()
{
  string c;
  cin >> c;
  if (c >= "a" && c <= "z")
  {
    cout << "a" ;
  }
  else if (c >= "A" && c <= "Z")
  {
    cout << "A" ;
  }
  else
  {
  
  }


} 

Measured memory_bytes: 3624
#include <iostream>
#include <iomanip>
#include <fstream>
#include <string>
#include <vector>
#include <array>
#include <map>
#include <set>
#include <stack>
#include <cstdint>
#include <cmath>
#include <algorithm>
#include <utility>
#include <numeric>
#include <functional>
#include <cassert>

using namespace std;
typedef int64_t ll;
typedef uint64_t ull;

constexpr ll INF = 1e+14;

void solve(istream &cin) {
    ll N;
    if (!(cin >> N)) { return; }
    ll maxW;
    cin >> maxW;
    vector<ll> w, v;
    ll sumv = 0;
    for (int i = 0; i < N; ++i) {
        ll tw, tv;
        cin >> tw >> tv;
        w.push_back(tw);
        v.push_back(tv);
        sumv += tv;
    }
    vector<vector<ll>> dp(N+1, vector<ll>(sumv+1, INF));
    dp[0][0] = 0;

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j <= sumv; ++j) {
            dp[i+1][j] = dp[i][j];
            if(v[i] <= j){
                dp[i+1][j] = min(dp[i][j], dp[i][j-v[i]] + w[i]);
            }
        }
    }
    for (int i = sumv; i >= 0 ; --i) {
        if(dp.back()[i] <= maxW) {
            cout << i << endl;
            break;
        }
    }
}

int main(int argc, char *argv[]) {
    string FileName("EDPC"), Modifier("MEPH_");
    string ExecutionName = Modifier + FileName;
    string sub(argv[0]);
    // /home/USER/.../MEPH_X -> MEPH_X
    if (sub.size() > ExecutionName.size())
        sub = sub.substr(sub.size() - ExecutionName.size(), ExecutionName.size());

    cout << setprecision(16) << scientific;
    if (sub != ExecutionName) {
        cin.tie(0);
        ios::sync_with_stdio(false);
        while (cin) { solve(cin); }
    } else {
        cerr << sub << " test" << endl;
        string inFile = FileName + ".txt";
        auto fs = fstream(inFile, fstream::in);
        while (fs) { solve(fs); }
    }
}


Measured memory_bytes: 80256
#include<stdio.h>
int main(){
  int a, b, c, S, M, L, t;
  S = M = L = 0;
  while(1){
    scanf("%d %d %d", &a, &b, &c);
    if(c<a){t=c;c=a;a=t;}
    if(c<b){t=c;c=b;b=t;}
    if(!(a+b>c && b+c>a && c+a>b))break;
    t=c*c-a*a-b*b;
    if(t<0)S++;if(t==0)M++;if(t>0)L++;
  }
  printf("%d %d %d %d\n", S+M+L, M, S, L);
  return 0;
}


Measured memory_bytes: 2020
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func nextInt() int {
	var i int
	if sc.Scan() {
		if num, err := strconv.Atoi(sc.Text()); err == nil {
			i = num
		}
	}
	return i
}

func nextString() string {
	var s string
	if sc.Scan() {
		s = sc.Text()
	}
	return s
}

func main() {
	sc.Split(bufio.ScanWords)
	n := nextInt()
	var ac, wa, tle, re int
	for i := 0; i < n; i++ {
		c := nextString()
		if c == "AC" {
			ac++
		} else if c == "WA" {
			wa++
		} else if c == "TLE" {
			tle++
		} else if c == "RE" {
			re++
		}
	}
	fmt.Println("AC x " + strconv.Itoa(ac))
	fmt.Println("WA x " + strconv.Itoa(wa))
	fmt.Println("TLE x " + strconv.Itoa(tle))
	fmt.Println("RE x " + strconv.Itoa(re))
}


Measured memory_bytes: 1772
//package abc134;
import java.io.*;
import java.util.*;

public class Main {
	// ------------------------
	
	public static void main(String[] args) {
		MyScanner sc = new MyScanner();
		out = new PrintWriter(new BufferedOutputStream(System.out));
		// ------------------------
		int n=sc.nextInt();
		int[]a=new int[n];
		for(int i=0;i<n;i++)
			a[i]=sc.nextInt();
		int[]x=new int[n];
		int m=0;
		HashSet<Integer>set=new HashSet<Integer>();
		for(int i=n-1;i>=0;i--){
			if((a[i]+x[i])%2==1){
				m++;
				set.add(i+1);
				addTo(x,i+1);
			}
		}
		System.out.println(m);
		for(int i:set)
			System.out.print(i+" ");
		// ------------------------
		out.close();
	}
	//------------------------
	private static void addTo(int[]x,int n){
		for(int i=1;i<=Math.sqrt(n);i++)
			if(n%i==0){
				x[i-1]++;
				if(i!=n/i)
				x[n/i-1]++;
			}
	}
	public static PrintWriter out;
	public static class MyScanner {
		BufferedReader br;
		StringTokenizer st;
		public MyScanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
		long nextLong() {
			return Long.parseLong(next());
		}
		double nextDouble() {
			return Double.parseDouble(next());
		}
		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return str;
		}
	}
}


Measured memory_bytes: 52684