akhauriyash/Code-Regression huggingface dataset:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())

aa = list(input())
N = len(aa)
cnt = [0]*26

for a in aa:
    cnt[ord(a)-97] += 1

ans = N*(N-1)//2+1
for n in cnt:
    ans -= n*(n-1)//2

print(ans)


Measured memory_bytes: 6048
using System;
using System.Linq;
using System.Collections.Generic;
public class Hello
{

    public static void Main()
    {
        string[] s = Console.ReadLine().Split(' ');
        int N = int.Parse(s[0]);
        int K = int.Parse(s[1]);
        string[] s_ = Console.ReadLine().Split(' ');
        int[] num = Array.ConvertAll<string, int>(s_, delegate (string value) { return int.Parse(value); });
        Array.Sort(num);
        Array.Reverse(num);
        int ans = 0;
        for (int i = 0; i < K; i++) ans += num[i];
        Console.WriteLine(ans);
    }
}

Measured memory_bytes: 13268
A,B,K = map(int,input().split())

A1 = A
A2 = min(A+K,B+1)
for i in range(A1,A2):
  print(i)

B1 = max(B-K+1,A+K)
B2 = B+1  
for i in range(B1,B2):
  print(i)
  

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

            int arr[6];
            int index;
            for(int i=1;i<=5;i++)
              {
                  cin>>arr[i];
                    if(arr[i]==0)
                     index=i;
            }

           cout<<index;
}


Measured memory_bytes: 3620
//#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"

#define rep(i,n) for(ll (i)=0;(i)<(ll)(n);(i)++)
#define all(x) (x).begin(),(x).end()

#define MOD 1000000007LL
#define INF (1LL<<60LL)
#define int long long
#define MAX_N (100001)
typedef long long ll;

using namespace std;




signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n; cin >> n;
	string s; cin >> s;
	int ans1 = 0, ans2 = 0;
	map<char, int> m;
	m['R'] = 0;
	m['G'] = 0;
	m['B'] = 0;
	rep(i, s.size()) {
		if (s[i] == 'R') {
			m['R']++;
			ans1 += m['G'] * m['B'];
		}
		else if (s[i] == 'G') {
			m['G']++;
			ans1 += m['R'] * m['B'];
		}
		else if (s[i] == 'B') {
			m['B']++;
			ans1 += m['G'] * m['R'];
		}
	}
	rep(i, s.size()) {
		int l=i-1, r=i+1;
		while (0 <= l && r < s.size()) {
			if (s[l] != s[i] && s[i] != s[r] && s[l] != s[r]) {
				ans2 += 1;
			}
			l--; r++;
		}
	}
	cout << ans1 - ans2 << endl;
}


Measured memory_bytes: 3664
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 1000000000000000000LL
#define MOD 1000000007
#define writeln(n) cout<<n<<endl;
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;
//vector<tuple<long long, long long, long long>>vec;

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

int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

using PII = pair<int, int>;

int main()
{
    int N; cin >> N;
    vector<int>odd(N/2);
    vector<int>even(N/2);
    FOR(i, 0, N / 2) {
        cin >> odd[i] >> even[i];
    }
    auto f = [](vector<int>a,int rej = -1) {
        int N = (int)a.size();
        vector<int>Map(1e5 + 10, 0);
        FOR(i, 0, N) {
            if(rej==a[i])continue;
            Map[a[i]]++;
        }
        int Max = 0;
        int id = 0;
        FOR(i, 0, 1e5 + 10) {
            if (Max < Map[i]) {
                Max = Map[i];
                id = i;
            }
        }
        return PII(N - Max,id);
    };
    int ans = 0;
    PII a1 = f(odd);
    PII a2 = f(odd, a1.second);
    PII b1 = f(even);
    PII b2 = f(even,b1.second);
    if (a1.second == b1.second) {
        ans = min(a1.first+b2.first, a2.first+b1.first);
    }
    else {
        ans = a1.first + b1.first;
    }
    cout << ans << endl;

}

Measured memory_bytes: 1280
#include <bits/stdc++.h>  // ver2.2.6
#define int long long
#define endl "\n"
#define ALL(v) (v).begin(),(v).end()
#define COUNT(a,i) upper_bound(ALL(a),i)-lower_bound(ALL(a),i)
#define Vi vector<int>
#define VVi vector<Vi>
#define Vs vector<string>
#define Pii pair<int,int>
#define VPii vector<Pii>
#define Tiii tuple<int,int,int>
#define PQi priority_queue<int>
#define PQir priority_queue<int,vector<int>,greater<int>>
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define itos to_string
#define stoi stoll
#define FI first
#define SE second
#define cYES cout<<"YES"<<endl
#define cNO cout<<"NO"<<endl
#define cYes cout<<"Yes"<<endl
#define cNo cout<<"No"<<endl
#define cyes cout<<"yes"<<endl
#define cno cout<<"no"<<endl
#define _ <<' '<<
#define sortr(v) sort(v,greater<>())
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repeq(i,a,b) for(int i=a;i<=b;i++)
#define repreq(i,a,b) for(int i=a;i>=b;i--)
#define leng(n) (int)(log10(n)+1)
#define dem(a,b) ((a+b-1)/(b))
#define Vin(a) rep(iI,0,a.size())cin>>a[iI]
#define Vout(a) rep(lZ,0,a.size()-1)cout<<a[lZ]<<' ';cout<<a.back()<<endl
#define VVout(a) rep(lY,0,a.size()){Vout(a[lY]);}
#define VPout(a) rep(lX,0,a.size())cout<<a[lX].FI<<' '<<a[lX].SE<<endl
#define Verr(a) rep(iZ,0,a.size()-1)cerr<<a[iZ]<<' ';cerr<<a.back()<<endl
#define VVerr(a) rep(iY,0,a.size()){Verr(a[iY]);}
#define VPerr(a) rep(iX,0,a.size())cerr<<a[iX].FI<<' '<<a[iX].SE<<endl
#define INF 3000000000000000000  //  3.0*10^18(MAXの1/3くらい)
#define MAX LLONG_MAX
#define MOD 1000000007  //  10^9 + 7
using namespace std;

int gcd(int a,int b){return b?gcd(b,a%b):a;}  //  最大公約数gcd
int lcm(int a,int b){return a/gcd(a,b)*b;}  //  最小公倍数lcm
void press(auto &v){v.erase(unique(ALL(v)),v.end());}  //  圧縮
int mypow(int x, int n, int m){  //  累乗x^n(mod m)  O(log(n))
if(n==0)return 1;if(n%2==0)return mypow(x*x%m,n/2,m);else return x*mypow(x,n-1,m)%m;}

int n,a,b,qw,er,ty;
Vi ene;

bool check(int m){
  Vi next(0);
  int ex = a-b;
  rep(i,0,n){
    if(b*m >= ene[i]) continue;
    else {
      next.pb(ene[i]-b*m);
    }
  }
  if(next.size()==0) return true;
  
  int ct=0;
  rep(i,0,next.size()){
    ct += dem(next[i],ex);
  }
  if(ct <= m) return true;
  else return false;
}

int binary(){
  int l = 0;
  int L = 0,R = 10000000000,mid = (L+R)/2;
  int ans = 0;
  
  while(L<R){
    if(check(mid)) {
      R = mid;
      ans = R;
    }
    else L = mid+1;
    
    mid = (L+R)/2;
  }
  return ans;
}

signed main() {
  cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(12);
  cin >> n >> a >> b;
  
  rep(i,0,n){
    cin >> qw;
    ene.pb(qw);
  }
  //Verr(ene);
  
  int ans = binary();
  cout<<ans<<endl;
  
  return 0;
}

Measured memory_bytes: 2920
#include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <set>
#include <map>

#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define for_p(i, a, b) for(int i = a; i < b; i++)
#define for_m(i, a, b) for(int i = a - 1; i >= b; i--)

//a = s1.size();
//vector<string> s1;
//string s2 = accumulate( s1.begin(), s1.end(), string() );

using namespace std;

int main()
{
  int a = 0 , b = 0, c = 0, d = 0, e = 0, f = 0;
  int i = 0, j = 0;
  double d1 = 0, d2 = 0, d3 = 0, d4 = 0, d5 = 0, d6 = 0;
  int a1[256], a2[512], a3[1024];
  char s1[200000], s2[200000], s3[200000];
  
  cin >> a >> b;
  
  for(i = 0; i < a; i++){
    cin >> a1[i];
  }
  c++;
  for(i = 0; i < a; i++){
    if(b >= a1[i] + d){
      c++;
    }
    d += a1[i];
  }  
  cout << c << endl;
}


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

int main(){
    int n;cin>>n;
    if (n%2==0){
        cout << 0.5 << endl;
    } else {
        cout << setprecision(10) << ((n / 2) + 1) / (float)(n) << endl;
    }
    return 0;
}

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

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

    int ans = 0;
    for(int a = 1; a <= k; a++) {
        for(int b = 1; b <= k; b++) {
            for(int c = 1; c <= k; c++) {
                ans += __gcd(__gcd(a, b), c);
            }
        }
    }
    cout << ans << endl;


    
    return 0;
}

Measured memory_bytes: 3632
n=int(input())
c=list(range(1,1+2*n))
for _ in[0]*int(input()):
    k=int(input())
    if k:c=c[k:]+c[:k]
    else:
        for a,b in zip(c[:n],c[n:]):
            c+=[a,b]
        c=c[2*n:]
print(*c,sep='\n')


Measured memory_bytes: 5624
#include <iostream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;

int main(){
    string S;
    cin >> S;
    int N = S.size();
    for(int l=0; l<N; l++){
        for(int r=l; r<=N; r++){
            string T = S.substr(0, l) + S.substr(r, N-r);
            if(T == "keyence"){
                cout << "YES" << endl;
                return 0;
            }
        }
    }
    cout << "NO" << endl;
    return 0;
}

Measured memory_bytes: 256
n=int(input())
listv = [int(i) for i in input().split()]

for _ in range(n-1):
    listv = sorted(listv)
    min1 = listv[0]
    min2 = listv[1]
    listv = listv[1:]
    listv[0] = (min1+min2)/2
    
print(listv[0])

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

int main()
{
    ull N, K, Q;
    cin >> N >> K >> Q;
    vector<int> A(N, 0);
    rep(i, Q){
        ull j;
        cin >> j;
        A[j-1]++;
    }
    rep(i, N){
        if(Q - A[i] >= K)cout << "No" << endl;
        else cout << "Yes" << endl;
    }
    return 0;
}


Measured memory_bytes: 1024
#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[i];
    int ans = 0;

    int j = 0;
    for(int i = 0; i < n; i++){
        if( i <= j ) continue;
        else if( j == i ) continue;
        else ans += d[j] * d[i];
        if( i == n-1 ) {
            j++;
            i = j;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 3584
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define pb push_back
const int maxn = 10000;
const int INF32 = 1'050'000'000;
const long long INF64 = 4'000'000'000'000'000'000;
const int MOD7 = 1'000'000'007;
const int MOD9 = 1'000'000'009;

void ERROR(int num) { printf("ERROR%d!\n",num); }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
int dx[8]={-1,0,1,0,1,1,-1,-1};
int dy[8]={0,-1,0,1,1,-1,1,-1};
const double PI = acos(-1);

int main(){
	double R;
	cin >> R;
	double ans = 2 * PI * R;
	//cout << ans << endl;
	printf("%.20lf",ans);
}

Measured memory_bytes: 3792
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define ld long double
#define mp make_pair

void print(auto &a)
{
    for (auto s: a) cout<<s<<' ';
    cout<<endl;
}

void get(vector<auto> &a)
{
    for (int i = 0; i<a.size(); i++) cin>>a[i];
}

int p;


int mul(int a, int b) {
    return (1LL * a%p * b%p) % p;
}

int add(int a, int b) {
    ll s = (a+b);
    s = s%p;
    if (s<0) s+=p; 
    return s;
}

int po(int a, int deg)
{
    if (deg==0) return 1;
    if (deg%2==1) return mul(a, po(a, deg-1));
    int t = po(a, deg/2);
    return mul(t, t);
}

int inv(int n)
{
    return po(n, p-2);
}



vector<int> Z(string s)
{
int n = s.length();
vector<int> z(n);
int L = 0, R = 0;
for (int i = 1; i < n; i++) {
  if (i > R) {
    L = R = i;
    while (R < n && s[R-L] == s[R]) R++;
    z[i] = R-L; R--;
  } else {
    int k = i-L;
    if (z[k] < R-i+1) z[i] = z[k];
    else {
      L = i;
      while (R < n && s[R-L] == s[R]) R++;
      z[i] = R-L; R--;
    }
  }
}
return z;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);

    int a, b, c;
    cin>>a>>b>>c;
    if (a==b&&b==c) cout<<"Yes";
    else cout<<"No";
    
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
int main(){
	int a,b,i,ans;
	char n[105];
	while(~scanf("%s",n))
	{
		a=strlen(n);
		ans=0;
		for(i=0;i<a/2;i++)
		{
			if(n[i]!=n[a-1-i])
			ans+=1;
		}
		printf("%d\n",ans);
	}
}

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

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    string s, t;
    cin >> s >> t;
    int ans = 0;
    for (int i = 0; i < s.size(); ++i) if (s[i] != t[i]) ++ans;
    cout << ans << '\n';
}

Measured memory_bytes: 3852
N = gets.to_i
a = gets.chomp.split(" ").map { |e| e.to_i }
count = 0

for i in 0..N-1 do
  ai = a[i].to_s(2).split("").map { |e| e.to_i } #２進法の配列に直す
  n = ai.length
  for j in 0..n-1 do
    if ai[n-1-j] == 0
      count += 1
    else
      break
    end
  end
end

puts count


Measured memory_bytes: 3580
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <stack>
#include <queue>
#include <set>
#include <bitset>
#include <map>
#include <unordered_map>
#include <ctime>
#include <list>
#include <numeric>
#include <utility>
#include <cassert>

#define INF 1000000000
#define LINF 9000000000000000000
#define mod 1000000007

#define rep(i,n) for(int i=0;i<int(n);i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define REP(i,a,b) for(int i=(a);i<int(b);i++)
#define all(x) (x).begin(),x.end()
#define pb push_back
#define mp make_pair

using namespace std;

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

int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int ddx[8]={-1,-1,0,1,1,1,0,-1};
int ddy[8]={0,1,1,1,0,-1,-1,-1};
bool debug=false;

/*---------------------------------------------------*/

int main(){
  int a[3];
  int cnt=0;
  cin>>a[0]>>a[1]>>a[2];
  while(a[0]!=a[1]||a[1]!=a[2]||a[2]!=a[0]){
    sort(a,a+3);
    //cout<<a[0]<<" "<<a[1]<<" "<<a[2]<<endl;
    if(a[1]!=a[2]){
      a[0]++;a[1]++;
    }else{
      a[0]+=2;
    }
    cnt++;
  }
  cout<<cnt<<endl;
  return 0;
}


Measured memory_bytes: 256
n,m = map(int,input().split())

a = []
b = []

for i in range(n):
    a.append([int(j) for j in input().split()])
for i in range(m):
    b.append(int(input()))

for i in range(n):
    c = 0
    for j in range(m):
        c += a[i][j] * b[j]
    print(c)

Measured memory_bytes: 6008
A = int(input())
B = int(input())
C = int(input())
X = int(input())

cnt = 0

for a in range(A + 1):
    for b in range(B + 1):
        for c in range(C + 1):
            if 500 * a + 100 * b + 50 * c == X:
                cnt += 1

print(cnt)


Measured memory_bytes: 3060
#include<bits/stdc++.h>
#include<iostream>
#include<vector>
using namespace std;
 
/****************************************\
| Thank you for viewing my code:)        |
| Written by RedSpica a.k.a. RanseMirage |
| Twitter:@asakaakasaka                  | 
\****************************************/
  
signed main() {
  int q;
    cin>>q;
  vector<bool> A(100100,true);
  for(int i=2;i<=100010;i++){
    int up=sqrt(i)+1;
    for(int j=2;j<up;j++){
      if(i%j==0){
         A[i]=false;
        break;
      }
    }
  }

  vector<int> B(50050);
  for(int i=3;i<=100010;i+=2){
    B[i/2]=B[(i-2)/2];
    if(A[i]&&A[(i+1)/2]){
      B[i/2]++;
    }
  }
  for(int i=0;i<q;i++){
    int l,r;
      scanf("%d%d",&l,&r);
    if(l==1){
      l+=2;
    }
    printf("%d\n",B[r/2]-B[(l-2)/2]);
  }
}


Measured memory_bytes: 896
#include<iostream>
#define rep(i,a) for(int i=0;i<a;i++)
int MOD=100000,n,m;
int main(){
    while(std::cin>>n>>m,n){
        int dp[110][110][2]={0};
        dp[1][0][0]=dp[0][1][1]=1;
        rep(i,n)rep(j,m)rep(k,2){
			(dp[i+1+k][j][0]+=dp[i][j][k])%=MOD;
			(dp[i][j+1+(1^k)][1]+=dp[i][j][k])%=MOD;
        }
		std::cout<<(dp[n][m-1][0]+dp[n-1][m][1])%MOD<<"\n";
    }
}

Measured memory_bytes: 1264
from collections import deque
import sys
sys.setrecursionlimit(10**6)

N = int(input())
E = [[] for _ in range(N)]
for _ in range(N-1):
    x,y = map(int, input().split())
    E[x-1].append(y-1)
    E[y-1].append(x-1)
    
parents = [-1]*N
q = deque()
q.append(0)
while q:
    t = q.popleft()
    for i in E[t]:
        if i == parents[t]:
            continue
        q.append(i)
        parents[i] = t
        
mod = 10**9+7
dp = [[1]*2 for _ in range(N)]
flag = [0]*N

def f(v, j):
    if flag[v]:
        return dp[v][j]
    flag[v] = 1
    for i in E[v]:
        if i == parents[v]:
            continue
        dp[v][0] *= (f(i, 0) + f(i, 1))
        dp[v][1] *= f(i, 0)
        dp[v][0] %= mod
        dp[v][1] %= mod
    return dp[v][j]

print((f(0, 0)+f(0, 1))%mod)

Measured memory_bytes: 111988
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    String S = sc.next();
    String T = sc.next();
    int ans = N;

    for (int i = 0; i < N; i++) {
      if (S.substring(i, N).equals(T.substring(0, N - i))) {
        break;
      } else {
        ans++;
      }
    }

    System.out.println(ans);

  }
}


Measured memory_bytes: 35648
use std::str::FromStr;
use std::fmt::Debug;
use std::cmp;
#[allow(dead_code)]
fn read_as_vec<T>() -> Vec<T>
where T: FromStr, <T as FromStr>::Err : Debug{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().split_whitespace().map(|c| T::from_str(c).unwrap()).collect()

}

#[allow(dead_code)]
fn read_as_string() -> String{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

fn main(){
    let line = read_as_vec::<usize>();
    let (n, k) = (line[0], line[1]);
    let mut a = read_as_vec::<i64>();
    a.sort();
    // let n0 = a.iter().filter(|x| **x == 0).count();
    // let ap = a.iter().cloned().filter(|x| *x > 0).collect::<Vec<i64>>();
    // let am = a.iter().cloned().filter(|x| *x < 0).collect::<Vec<i64>>();
    let (mut left, mut right): (i64, i64) = (-1_000_000_000_000_000_000, 1_000_000_000_000_000_000);
    while left +1 < right{
        let mid = (left+right)/2;
        let mut c: usize = 0;
        for i in 0..n{
            if a[i] < 0{
                let (mut left, mut right): (usize, usize) = (i, n);
                while left +1< right{
                    let mi = (left+right)/2;
                    if a[mi] * a[i] >= mid{
                        left = mi;
                    }else{
                        right = mi;
                    }
                }
                c += n - right;
            }else if a[i] == 0{
                if mid > 0{
                    c += n - i -1;
                }
            }else{
                let (mut left, mut right): (usize, usize) = (i, n);
                while left +1< right{
                    let mi = (left+right)/2;
                    if a[mi] * a[i] >= mid{
                        right = mi;
                    }else{
                        left = mi;
                    }
                }
                c += left - i;
            }
        }
        if c < k{
            left = mid;
        }else{
            right = mid;
        }
    }

    println!("{}", left);
}


Measured memory_bytes: 10492
# Problem: https://atcoder.jp/contests/agc027/tasks/agc027_a
# Python 3rd Try

import sys
# from collections import defaultdict
# import heapq,copy
# from collections import deque


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


def LI(): return list(map(int, sys.stdin.readline().split()))


def LLI(rows_number): return [LI() for _ in range(rows_number)]


def solver(childs, candies, happyNumber):
    result = 0
    happyNumber.sort()
    for ch_i in range(0, childs, +1):
        candies = candies - happyNumber[ch_i]
        if 0 <= candies:  # まだまだお菓子には余裕があります
            result = result + 1
        else:  # これ以上菓子が配れない
            return result
    # 全部終わってキッカリで無ければ最後の一人が不満
    if 0 != candies:
        return result - 1
    return result


if __name__ == "__main__":
    N, x = MI()
    AI = LI()
    print("{}".format(solver(N, x, AI)))


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

using namespace std;

long long mini2(long long h,long long w)
{
	long long ans=h*w*5;
	long long a;
	long long s1,s2,s3;
	for(int i=1;i<h;i++)
	{
		s1=i*w;
		s2=(h-i)*(w/2);
		s3=h*w-s1-s2;
		a=max(max(s1,s2),s3)-min(min(s1,s2),s3);
		if(ans>a)
		{
			ans=a;
		}
	}
	return ans;
}

long long mini1(long long h,long long w)
{
	long long ans=h*w*5;
	long long a;
	long long s1,s2,s3;
	for(int i=1;i<h;i++)
	{
		s1=i*w;
		s2=((h-i)/2)*w;
		s3=h*w-s1-s2;
		a=max(max(s1,s2),s3)-min(min(s1,s2),s3);
		if(ans>a)
		{
			ans=a;
		}
	}
	return ans;
}

int main()
{
	long long h,w;
	long long ans;
	cin>>h>>w;
	ans=min(min(mini1(h,w),mini2(h,w)),min(mini1(w,h),mini2(w,h)));
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
// AOJ 0245: Time Sale
// 2017.12.16 bal4u@uu

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

#define QMAX 100000
typedef struct { char r, c, t; int d, b; } Q;
Q q[QMAX+2]; int top, end;
typedef struct { int d, s, e; } G;
G sell[10];
signed char map[21][21];
char mk[21][21][101][1024];
char buf[50], *p;
int mv[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};

int in()
{
	int n = 0;
	while (*p >= '0') n = 10*n + (*p++ & 0xf);
	p++;
	return n;
}

int main()
{
	int X, Y, r, c, n, i, j, sr, sc, max, ans;
	int d, t, b, r2, c2;

	while (fgets(p=buf, 10, stdin) && *p != '0') {
		X = in(), Y = in();
		for (r = 0; r < Y; r++) {
			fgets(p=buf, 50, stdin);
			for (c = 0; c < X; c++) {
				if (*p == '.') map[r][c] = -1;
				else if (*p == 'P') sr = r, sc = c, map[r][c] = -1;
				else map[r][c] = *p & 0xf;
				p += 2;
			}
		}
		fgets(p=buf, 5, stdin);
		n = *p & 0xf, max = 0;
		for (i = 0; i < n; i++) {
			fgets(p=buf, 50, stdin);
			j = in();
			sell[j].d = in(), sell[j].s = in(), sell[j].e = t = in();
			if (t > max) max = t;
		}

		ans = 0;
		memset(mk, 0, sizeof(mk));
		q[0].r = sr, q[0].c = sc, q[0].t = 0, q[0].d = 0, q[0].b = 0;
		top = 0, end = 1;
		while (top != end) {
			r = q[top].r, c = q[top].c, t = q[top].t, d = q[top].d, b = q[top].b;
			if (++top == QMAX) top = 0;

			if (t > max) continue;

			if (mk[r][c][t][b]) continue;
			mk[r][c][t][b] = 1;
			if (d > ans) ans = d;

			for (i = 0; i < 4; i++) {
				r2 = r + mv[i][0], c2 = c + mv[i][1];
				if (r2 < 0 || r2 >= Y || c2 < 0 || c2 >= X) continue;
				if ((j = map[r2][c2]) >= 0) {
					if (!(b & (1 << j)) && sell[j].s <= t && t < sell[j].e) {
						d += sell[j].d;
						b |= 1 << j;
					}
				}
			}
			for (i = 0; i < 4; i++) {
				r2 = r + mv[i][0], c2 = c + mv[i][1];
				if (r2 < 0 || r2 >= Y || c2 < 0 || c2 >= X || map[r2][c2] >= 0) continue;
				q[end].r = r2, q[end].c = c2, q[end].t = t+1, q[end].d = d, q[end].b = b;
				if (++end == QMAX) end = 0;
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

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

#if __has_include("print.hpp")
  #include "print.hpp"
#endif

#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define MOD 1000000007

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


int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> v(n);
  vector<ll> m(n);
  ll count = 0;
  for (int i = 0; i < n; i++) {
    cin >> v[i];
    if(i % 2 == 0) count += v[i];
    else count -= v[i];
  }
  m[0] = count;
  for (int i = 0; i < n-1; i++) {
    m[i+1] = (v[i]*2 - m[i]);
  }

  for(auto a : m){
    cout << a << ' ';
  }
  cout << endl;
}


Measured memory_bytes: 2560
#include<stdio.h>
int main()
{ int a[4],i=0,x;
   scanf("%d",&x);
	   for(i=0;i<4;i++)
	   { a[i]=x%10;
		   x=x/10;}

   if(a[0]==a[1] || a[1]==a[2] || a[2]==a[3])
	   printf("Bad\n");
   else
	   printf("Good\n");
   return 0;
}


Measured memory_bytes: 128
#include<iostream>
using namespace std;
int main()
{
  int n;
  cin>>n;
  long long int count =0;
  for(int i=1;i<=n;i++)
  {
        if(i%3==0 || i%5==0)
        continue;
        else
        count+=i;
  }
  cout<<count<<endl;
}

Measured memory_bytes: 3636
import heapq
import numpy as np
N, M = map(int,input().split())

A = np.array(list(map(int, input().split())))
A *= -1
A = list(A)
heapq.heapify(A)

while M:
    a_max = heapq.heappop(A)
    heapq.heappush(A, -(-1 * a_max // 2))
    M -= 1

print(sum(np.array(A) * -1))

Measured memory_bytes: 23136
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner (new InputStreamReader (System.in));
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		
		System.out.println (c + " " + a + " " + b);
	}
}


Measured memory_bytes: 23764
#include<iostream>
 
int main(){
  int N,M,X, Less=0, More=0,A;
  std::cin >>N>>M>>X;
  for(int i=0;i<M;i++){
    std::cin>>A;
    if(X<A)More++;
    if(X>A)Less++;
  }
  std::cout << ((More<Less)?More:Less);
  return 0;
}

Measured memory_bytes: 256
s = gets.chomp
t = gets.chomp
def theend; puts -1; exit; end
pos = Hash.new{|h,k| h[k]=[]}
s.each_char.with_index do |c, i|
  pos[c] << i
end
l = 0
prev_i = pos[t[0]][0] rescue theend
t[1..-1].each_char do |c|
  j = pos[c].bsearch {|x| x > prev_i} rescue theend
  prev_i = j || pos[c][0]
  l += 1 if !j
end

p s.size * l + (prev_i + 1) rescue theend

Measured memory_bytes: 3324
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
int n,score[5],result,r0,bonus;
vector <vector<int> > a(5,vector<int>(5)),check(5,vector<int>(5));

bool in(int y,int x){
  if(-1<y&&y<5 && -1<x&&x<5) return 1;
  else return 0;
}

bool sc(){
  vector <vector<int> > t0(5,vector<int>(5,0));
  for(int i=0;i<5;i++){
    int j=0;
    for(;j<5;){
      int pj=j;
      for(;j+1<5&&check[i][j]==check[i][j+1];) j++;
      if(j+1-pj>=3) for(;pj<=j;pj++) t0[i][pj]=1;
      j++;
    }
  }
  for(int j=0;j<5;j++){
    int i=0;
    for(;i<5;){
      int pi=i;
      for(;i+1<5&&check[i][j]==check[i+1][j];) i++;
      if(i+1-pi>=3) for(;pi<=i;pi++) t0[pi][j]=1;
      i++;
    }
  }
  int flag=0;
  for(int i=0;i<5;i++) for(int j=0;j<5;j++){
      if(t0[i][j]&&check[i][j]){
	r0+=t0[i][j]*bonus*score[check[i][j]-1];
	check[i][j]=0,flag++;
      }
    }
  
  for(int j=0;j<5;j++){
    int ni=5;
    for(int i=4;i>-1;i--){
      if(check[i][j]) check[--ni][j]=check[i][j];
    }
    for(int i=0;i<ni;i++) check[i][j]=0;
  }
  // cout<<r0<<endl;
  
  return flag;

}

void dfs(int sw,int y,int x,int d){

  //  cout<<sw<<" "<<y<<" "<<x<<" "<<d<<endl;
  
  if(sw>n) return;
  check=a;
  r0=0;
  bonus=1;
  while(sc()) bonus++; 
  result=max(result,r0);
  
  for(int k=0;k<4;k++){
    if(~d&&(d+2)%4==k) continue;
    int ny=y+dy[k],nx=x+dx[k];
    if(!in(ny,nx)) continue;

    swap(a[y][x],a[ny][nx]);
    dfs(sw+1,ny,nx,k);
    swap(a[y][x],a[ny][nx]);
  }
  
}

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

  for(;cin>>n;){
    if(n==-1) break;
    result=0;
    for(int i=0;i<5;i++) for(int j=0;j<5;j++) cin>>a[i][j];
    for(int i=0;i<5;i++) cin>>score[i];
    
    for(int i=0;i<5;i++) for(int j=0;j<5;j++) dfs(0,i,j,-1);
    
    cout<<result<<endl;
  }
    return 0;
}



Measured memory_bytes: 3148
#include<stdio.h>

int main()
{
    int str[10];
    int i = 0;
    int j, ch, ans, res;
    while((ch = fgetc(stdin)) != '\n'){
        str[i] = ch - '0';
        i++;
    }
    res = 753;
    for(j = 0; j < i-2; j++){
        ans = str[j]*100 + str[j+1]*10 + str[j+2] - 753;
        if(ans < 0) ans = -ans;
        if(ans < res) res = ans;
    }

    printf("%d\n", res);
    return 0;
}

Measured memory_bytes: 128
#include <iostream>
using namespace std;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define REP(i, n) FOR(i,0,n)


int main()
{
    int N, a, ans = 0;
    cin >> N;
    REP(_, N)
    {
        cin >> a;
        ans += (a & 1);
    }
    cout << (ans & 1 ? "NO" : "YES") << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(void){
  int x1,y1,x2,y2;
  cin >> x1 >> y1 >> x2 >> y2;
  cout << x2+y1-y2 << ' ' << y2-x1+x2 << ' ' << x1+y1-y2 << ' ' << y1-x1+x2 << endl;
  return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fod(i,a,b) for(int i=a;i>=b;--i)
#define N 3005
#define mo 1000000007
using namespace std;
int f[N][2*N][2],n,m;
int main()
{
    cin>>n>>m;
    f[0][0][1]=1;
    fo(i,1,n) f[0][i][0]=1;
    int ans=0;
    fo(i,1,m)
    {
        fo(j,0,n)
        {
            fo(p,0,1)
            {
                if(j) (f[i][j-1][p|(j==1)]+=f[i-1][j][p])%=mo,(f[i][j][p|(j==1)]+=f[i-1][j][p])%=mo;
                if(j<n) (f[i][j+1][p]+=f[i-1][j][p])%=mo,(f[i][j][p|(j==0)]+=f[i-1][j][p])%=mo;
            }
        }
    }
    fo(i,0,n) (ans+=f[m][i][1])%=mo;
    printf("%d\n",ans);
}

Measured memory_bytes: 139648
/*Author : Hrishi*/

/*When I wrote this, only God and I understood what I was doing.
Now, only God knows.*/

#include <bits/stdc++.h>

#define ll long long
#define vi vector<int>
#define vl vector<ll>
#define pi pair<int,int>
#define pl pair<ll,ll> 
#define ff first
#define ss second
#define PB push_back
#define F(i,L,R) for(auto i=L; i<R ;i++)
#define FR(i,R,L) for(auto i=R;i>L;i--)
#define all(x) (x).begin(),(x).end()
#define show(x) cout<<(#x)<<" = "<<(x)<<"\n";
#define show2(x,y) cout<<(#x)<<" = "<<(x)<<" & "<<(#y)<<" = "<<(y)<<"\n";
#define show3(x,y,z) cout<<(#x)<<" = "<<(x)<<" & "<<(#y)<<" = "<<(y)<<" & "<<(#z)<<" = "<<(z)<<"\n";
#define endln "\n"
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
#define M 1000000000000000000

using namespace std;

int main() 
{
	fastio;
	long double a,b;
	cin>>a>>b;
	long double ans = a*b;
	ll p = floor(ans);
	
	cout<<p;
}




Measured memory_bytes: 3760
//package atcoder;

import java.util.*;

public class Main {

    private static final int MAX = 1000000;     // Wa want a solution with time O(Sqrt(N)) = O(Sqrt(10^12)) = 10^6.

    private static final int[] lp = new int[MAX + 1];
    private static final List<Integer> pr = new ArrayList<>();

    static {            // fast Eratosthenes sieve
        for (int i = 2; i <= MAX; ++i) {
            if (lp[i] == 0) {
                lp[i] = i;
                pr.add(i);
            }
            for (int j = 0; j < pr.size() && pr.get(j) <= lp[i] && i*pr.get(j) <= MAX; ++j) {
                lp[(i * pr.get(j))] = pr.get(j);
            }
        }
    }

    public static void main (String[] args) {

        final Scanner in = new Scanner(System.in);
        long N = in.nextLong();

        final long B = (long)Math.sqrt(N) + 1;
        long count = 0;

        for (int prime = 2; prime <= Math.min(B, MAX); ++prime) {
            if (lp[prime] == prime && (N > 0) && (N % prime == 0)) {
                long z = prime;
                while ((N > 0) && (N % z == 0)) {   // try all z = prime, prime^2, prime^3, ...
                    count++;
                    N = N/z;
                    z = z*prime;
                }

                while ( (N > 0) && (N % prime == 0) ) {  // exhaust prime as a factor of N
                    N = N/prime;
                }
            }
        }

        if (N > 1) {
            count++;
        }

        System.out.println(count);
    }
}

Measured memory_bytes: 43776
#include<bits/stdc++.h>
#include<cmath>
#define pb push_back
#define ld long double
#define mp make_pair
#define vl vector<ll> 
#define vd vector<double>
#define vld vector<long double>
#define ll long long int
#define pl pair<ll, ll>
#define all(a) a.begin(), a.end()
#define forr(i, n) for(ll i=0; i<n; i++) 
#define forr1(i, n) for(ll i=1; i<=n; i++)
using namespace std;
const ld PI =3.1415926535897923846;
const ll MOD = 1000000007;
const ll N=998244353;
ll power(ll x,ll n){ll res=1;while(n>0){if(n&1) res=res*x%MOD;x=x*x%MOD;n>>=1;}return res;}
ll modinverse(ll a){return power(a, MOD-2);}
void solve()
{
    ll a, b;
    cin>>a>>b;
    cout<<6-a-b<<endl;
}
int main()
{
	#ifndef ONLINE_JUDGE
        // for getting input from input.txt
        freopen("input.txt", "r", stdin);
        // for writing output to output.txt
        freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll test=1;
    //cin>>test;
    while(test--)
    {
        solve();
    }
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}

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

#define int long long
#define ll unsigned long long
#define pb push_back
#define mp make_pair
#define veci vector<int>
#define pii pair<int,int>
#define reset(a, b) memset(a, b, sizeof(a))
#define rep(i,b) for(int i=0; i<b; i++)
#define repi(i,a,b) for(int i=a; i<=b; i++)
#define repd(i,a,b) for(int i=a; i>=b; i--)
#define fi first 
#define se second
#define all(v) v.begin(),v.end()

int mod=1e9+7;

int powerm(int x,int y, int M){ int res=1; while(y){ if(y&1) res=(res*x)%M; y=y>>1; x=(x*x)%M;} return res%M; }
int  power(int x,int y){ int res=1; while(y){ if(y&1) res=(res*x); y=y>>1; x=(x*x);} return res; }
bool isprime(int n) { if (n <= 1) return false; if (n <= 3) return true; if (n % 2 == 0 || n % 3 == 0) return false; for (int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false; return true; }
/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/


signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int T;
    T=1;
//    cin>>T;
while(T--){
    int n;
    cin>>n;
    int a[15];
    a[0]=0;
    a[1]=26;
    repi(i,2,12){
        a[i]=power(26,i)+a[i-1];
    }
    int count;
    int t;
    int s;
    repd(i,12,0){
        if(n>a[i]){
            t=n-a[i];
            count = i+1;
            s=i;
            break;
        }
    }
    int j=count-1;
    rep(i,count){
        int b;
        if(t%power(26,j)==0) b=t/power(26,j)-1;
        else b=t/power(26,j);
        char ans = 'a'+b;
        cout<<ans;
        t-=b*power(26,j);
        j--;
    }
}
    
    return 0;
}

Measured memory_bytes: 3540
#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

#define FOR(i,k,n) for (int (i)=(k); (i)<(n); ++(i))
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fst first
#define snd second
#define all(v) begin(v), end(v)
#define debug(x) cerr<< #x <<": "<<x<<endl
#define debug2(x,y) cerr<< #x <<": "<< x <<", "<< #y <<": "<< y <<endl

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef vector<vector<ll> > vvll;
typedef vector<char> vc;
typedef vector<vector<char> > vvc;
typedef vector<double> vd;
typedef vector<vector<double> > vvd;
template<class T> using vv=vector<vector< T > >;
typedef deque<int> di;
typedef deque<deque<int> > ddi;
typedef deque<bool> db;
typedef deque<deque<bool> > ddb;

// cout pair
template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p) {
  s << p.first << " " << p.second << "\n"; return s;
}

// cout vector<pair>
template<typename T1, typename T2> ostream& operator<<(ostream& s, const vector<pair<T1, T2> >& vp) {
  int len = vp.size(); s << "\n";
  for (int i = 0; i < len; ++i) { s << vp[i]; }
    s << "\n"; return s;
}

// cout vector
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
  int len = v.size(); s << "\n";
  for (int i = 0; i < len; ++i) {
    s << v[i]; if (i < len - 1) s << "\t";
  }
  s << "\n"; return s;
}

// cout deque
template<typename T> ostream& operator<<(ostream& s, const deque<T>& v) {
  int len = v.size(); s << "\n";
  for (int i = 0; i < len; ++i) {
    s << v[i]; if (i < len - 1) s << "\t";
  }
  s << "\n"; return s;
}

// cout 2-dimentional vector
template<typename T> ostream& operator<<(ostream& s, const vector< vector<T> >& vv) {
  int len = vv.size();
  for (int i = 0; i < len; ++i) { s << vv[i]; }
  return s;
}

// cout 2-dimentional deque
template<typename T> ostream& operator<<(ostream& s, const deque< deque<T> >& vv) {
  int len = vv.size();
  for (int i = 0; i < len; ++i) { s << vv[i]; }
  return s;
}

int main() {
  int n, d1, x;
  cin >> n >> d1 >> x;;

  vector<double> a(n+1);
  a[n] = d1;
  vector<double> dx(n+1);
  dx[n] = x;

  double ans = 0.0;
  for (int i = n; i >= 2; --i) {
    a[i-1] = (2*i+2)*a[i] + 5*dx[i];
    a[i-1] /= (2*i);
    dx[i-1] = (2*i+4)*dx[i];
    dx[i-1] /= (2*i);
    double ans_sub = (a[i] * 2 + dx[i] * (2*i-1)) / 2;
    ans += ans_sub;
  }
  ans += a[1] + dx[1]/2;
  printf("%.12f\n", ans);

  return 0;
}


Measured memory_bytes: 3328
#include <bits/stdc++.h>
 
using namespace std;
 
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=(s);i<(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(n);i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define Eunique(v) v.erase(unique(all(v)),v.end())
#define pvec(v) rep(i,v.size()){cout << v[i] << " ";};cout<<endl;
#define pb push_back
#define pf push_front
#define mod 1e9+7
 
typedef vector<int> vi;
typedef vector<string> vs;
typedef long long ll;
typedef vector<ll> vll;

const double pi = acos(-1.0);
 
ll gcd(ll x, ll y) { return (y == 0) ? x : gcd(y, x % y); }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }

bool IsPrime(int num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false;

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            return false;
        }
    }
    return true;
}

int main()
{
    ll n,ans=0;
    cin >> n;
    vll a(3*n);
    rep(i,3*n) cin >> a[i];
    sort(rall(a));
    for(int i=1;i<2*n;i+=2) ans+=a[i];
    cout << ans << endl;
	return 0;
}

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

int main() {
  int n;
  cin>>n;
  vector<pair<int,int>> a[100005];
  vector<int> co(100005,-1);
  queue<int> q;

  for (int i=0; i<n-1; i++) {
    int u,v,w;
    cin>>u>>v>>w;
    u--; v--;
    a[u].push_back(make_pair(v,w));
    a[v].push_back(make_pair(u,w));
  }
  
  q.push(0);
  co[0]=0;
  while (q.size()) {
    int now=q.front();
    q.pop();
    for (int i=0; i<a[now].size(); i++) {
      int now2=a[now][i].first;
      if (co[now2]!=-1) continue;
      if (a[now][i].second%2==0) co[now2]=co[now];
      else co[now2]=(co[now]+1)%2;
      q.push(now2);
    }
  }
  for (int i=0; i<n; i++) {
    cout<<co[i]<<endl;
  }
  return 0;
}



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

using namespace std;

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

    if (n == 1) {
        cout << 1 << endl;
        return 0;
    }

    int ans = 0;
    for (int i=0; i<n-1; i++) {
        ans++;
        while(i<n-1 && a[i] == a[i+1]) i++;
        if (i>=n-1) continue;
        if (a[i] < a[i+1])
            while (i<n-1 && a[i]<=a[i+1]) i++;
        else if (a[i] > a[i+1])
            while (i<n-1 && a[i]>=a[i+1]) i++;
        if (i == n-2) ans++;
    }
    
    cout << ans << endl;
}


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

int main() {
  int N;
  cin >> N;
  vector<int> diam(N);
  for(int i=0; i<N; i++)
    cin >> diam.at(i);
  
  sort(diam.begin(), diam.end());
  
  int x=1;
  for(int i=0; i<N-1; i++)
    if(diam.at(i)!=diam.at(i+1))
      x++;
  cout << x << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int main()
{
    long long int a,b,ans;
    scanf("%lld %lld",&a,&b);
    long long int a1=a,b1=b,gcd,lcm;
    while((a1%=b1)&&(b1%=a1));
    gcd = a1+b1;
    lcm = a*b/gcd;
  printf("%lld\n",lcm);
  return 0;
}


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

int even(int n) {
  return (n % 2 == 0) ? 1 : 0;
}

int main() {
  int i;
  long long int n, u_val[100000], v_val[100000], w_val[100000];
  scanf("%lld", &n);
  for(i = 0; i < n - 1; i++) {
    scanf("%lld %lld %lld", &u_val[i], &v_val[i], &w_val[i]);
    u_val[i]--;
    v_val[i]--;
  }

  long long int *ans;
  ans = (long long int*)malloc(sizeof(long long int) * n);
  for(i = 0; i < n; i++) ans[i] = -1;

  int node1 = u_val[0];
  int node2 = v_val[0];
  int dist = w_val[0];
  ans[node1] = 0;
  if(even(dist)) ans[node2] = ans[node1];
  else           ans[node2] = 1 - ans[node1];

  int count = 0;
  while(1) {
    for(i = 1; i < n; i++) {
      node1 = u_val[i];
      node2 = v_val[i];
      dist  = w_val[i];
      if(ans[node1] != -1 || ans[node2] != -1) {
        if(ans[node1] != -1 && ans[node2] == -1) {
          if(even(dist)) ans[node2] = ans[node1];
          else           ans[node2] = 1 - ans[node1];
        } else if(ans[node1] == -1 && ans[node2] != -1) {
          if(even(dist)) ans[node1] = ans[node2];
          else           ans[node1] = 1 - ans[node2];
        }
      }
    }
    for(i = 0; i < n; i++) {
      if(ans[i] == -1) count++;
    }
    if(count == 0) {
      break;
    }
    count = 0;
  }

  for(i = 0; i < n; i++) printf("%lld\n", ans[i]);

  free(ans);

  return 0;
}


Measured memory_bytes: 3456
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define pi pair<int,int>
#define pl pair<ll,ll>
#define pd pair<double,double>
#define ld long double
#define pld pair<ld,ld>
#define lg length()
#define sz size()
#define pb push_back
#define MAXN 100005
#define INF 1000000005
#define LINF 1000000000000000005
#define x1 xdddddddddddddddddd
#define y1 ydddddddddddddddddd
#define eps 0.0000000000000000001

ll n,a,b,k,mod=998244353,f[300005],v[300005],ans;

ll pwr(ll a, ll p){
    if(!p) return 1;
    ll t=pwr(a,p/2);
    t=t*t%mod;
    if(p%2) return t*a%mod;
    else return t;
}

ll C(ll n, ll k){
    return f[n]*v[k]%mod*v[n-k]%mod;
}

int32_t main(){
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    cin >> n >> a >> b >> k;
    f[0]=1; v[0]=1;
    for(ll i=1;i<=n;i++){
        f[i]=(f[i-1]*i)%mod;
        v[i]=pwr(f[i],mod-2);
    }
    for(ll i=0;i<=n;i++){
        if(k>=a*i && (k-a*i)%b==0 && (k-a*i)/b<=n){
            ll j=(k-a*i)/b;
            ans+=C(n,i)*C(n,j);
            ans%=mod;
        }
    }
    cout << ans;
}


Measured memory_bytes: 4992
K, N = map(int, input().split())
Alst = list(map(int, input().split()))
zero = Alst[0] + K
M = 0
now = Alst[0]
for i in Alst:
    dis = i - now
    if dis > M:
        M = dis
    now = i

last = zero - now
if last > M:
    M = last

print(K - M)

Measured memory_bytes: 32328
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  int a[n], b[n];
  int as = 0, bs =0, ans = 0;
  for(int i=0; i<n; ++i) cin >> a[i];
  for(int i=0; i<n; ++i){ cin >> b[i]; bs += b[i]; }
  for(int i=0; i<n; ++i){
    as += a[i];
    if(i != 0) bs -= b[i-1];
    ans = max(ans, as+bs);
  }
  cout << ans << endl;
}

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

void solve()
{
	string s;
	cin >> s;
	int x = 0;
	for(int i = 0; i < s.size(); i++)
	{
		x = (x + (s[i] - '0')) % 9;
	}
	if(x == 0) cout << "Yes\n";
	else cout << "No\n";
}

int main() 
{
    int t = 1;
//    cin >> t;
    while(t--)
    {
    	solve();
	}
} 


Measured memory_bytes: 3752
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCorder
{
	public class Program
	{
		const long MOD = 1000000007;

		static void Main(string[] args)
		{
			var cin = new Scanner2();
			int n = cin.Int();
			int max = 55555;
			bool[] isPrime = new bool[max + 1];
			for (int i = 2; i < max; i++) {
				isPrime[i] = true;
			}

			for (int i = 2; i * i <= max; i++) {
				for (int j = i + 1; j < max; j++) {
					if (j % i == 0) {
						isPrime[j] = false;
					}
				}
			}

			int cnt = 0;
			int index = 2;
			List<int> ans = new List<int>();
			while (cnt < n) {
				if (isPrime[index] && index % 5 == 1) {
					ans.Add(index);
					++cnt;
				}

				++index;
			}

			Console.WriteLine(string.Join(" ", ans.Select(x => x.ToString())));
		}
	}


	public class Scanner2
	{
		private readonly char[] delimiter_ = new char[] { ' ' };
		private readonly string filePath_;
		private string[] buf_;
		private int index_;
		Func<string> reader_;

		public Scanner2(string file = "")
		{
			if (string.IsNullOrWhiteSpace(file)) {
				reader_ = Console.ReadLine;
			} else {
				filePath_ = file;
				var fs = new StreamReader(file);
				reader_ = fs.ReadLine;
			}
			buf_ = new string[0];
			index_ = 0;
		}

		public string Next()
		{
			if (index_ < buf_.Length) {
				return buf_[index_++];
			}

			string st = reader_();
			while (st == "") {
				st = reader_();
			}

			buf_ = st.Split(delimiter_, StringSplitOptions.RemoveEmptyEntries);
			if (buf_.Length == 0) {
				return Next();
			}

			index_ = 0;
			return buf_[index_++];
		}

		public int Int() => int.Parse(Next());
		public long Long() => long.Parse(Next());
		public double Double() => double.Parse(Next());

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

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

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

		public void Save(string text)
		{
			if (string.IsNullOrWhiteSpace(filePath_)) {
				return;
			}

			File.WriteAllText(filePath_ + "_output.txt", text);
		}
	}
}

Measured memory_bytes: 11284
#include<bits/stdc++.h>
using namespace std;
string a[105];
int n,m;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)cout<<a[i];
}

Measured memory_bytes: 256
d, g = [int(i) for i in input().split()]
p, c = [0] * d, [0] * d
for i in range(d):
    p[i], c[i] = [int(j) for j in input().split()]

ans = float('inf')
for bit in range(1 << d):
    tot = 0
    num = 0
    for i in range(d):
        if bit >> i & 1:
            tot += c[i] + p[i]*100*(i + 1)
            num += p[i]
    if tot >= g:
        ans = min(ans, num)
    else:
        for i in reversed(range(d)):
            if bit >> i & 1:
                continue
            for j in range(p[i]):
                if tot >= g:
                    break
                tot += 100 * (i + 1)
                num += 1
        ans = min(ans, num)
print(ans)


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

int main() {
  int A,B;
  string S;
  cin>>A>>B>>S;
  for(int i=0;i<A+B+1;i++){
    if(i!=A&&S.at(i)=='-'){
      cout<<"No"<<endl;
      break;
    }
    else if(i==A&&S.at(i)!='-'){
      cout<<"No"<<endl;
      break;
    }
    else if(i==A+B){
      cout<<"Yes"<<endl;
    }
  }
}

Measured memory_bytes: 256