akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mx = 1e18+10;
void solve(){
    string s,t;
    cin>>s>>t;
    int dp[s.length()+1][t.length()+1];
    memset(dp,0,sizeof(dp));
    for(int i=0;i<=s.length();i++){
        for(int j=0;j<=t.length();j++){
            if(i==0||j==0) dp[i][j]=0;
            else if(s[i-1]==t[j-1])
            dp[i][j] = 1+dp[i-1][j-1];
            else
            dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }
    int len = dp[s.length()][t.length()];
    vector<char>ans(len);
    int i=s.length();int j=t.length();
    int index=0;
    while(index<len){
        if(s[i-1]==t[j-1]){
        ans[index]=s[i-1];i--;j--;index++;}
        else if(dp[i-1][j]>=dp[i][j-1])
        i--;
        else
        j--;
    }
    reverse(ans.begin(),ans.end());
    for(auto x:ans) cout<<x;
}
int main(){
    int T=1;
    //cin>>T;
    while(T--){
        solve();
    }
    return 0;
}


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

using namespace std;
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
int n,s;
 cin>>n;
vector<int> v(n,0);
for(int i=0;i<n;i++)
cin>>v[i];
s=1000000;
for (int i = 0; i < n; i++)
{
  if (abs(accumulate(v.begin(), v.begin()+i,0)-accumulate( v.begin()+i,v.end(),0))<=s)
    s = abs(accumulate(v.begin(), v.begin() + i, 0) - accumulate(v.begin() + i, v.end(), 0));
}
cout<<s;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <bitset>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <complex>
#include <deque>
#include <valarray>
#include <unordered_map>
#include <unordered_set>
#include <array>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <chrono>
#include <random>
#include <numeric>
using namespace std;
using ll = long long;
using ld = long double;
using str = string;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vs> vvs;
typedef vector<vc> vvc;
typedef vector<vb> vvb;
using P = pair<ll,ll>;
#define REP(i, n) for (ll i = 0; i < (int)(n); i++)
#define RREP(i, n) for (ll i = (int)(n)-1; i > -1 ; i--)
#define IN(T, x) T x;cin >> x;
#define AIN(T, a, n) vector<T> a(n);REP(i, n){cin >> a[i];}
#define A2IN(T1, a, T2, b, n) vector<T1> a(n);vector<T2> b(n);REP(i, n){cin >> a[i] >> b[i];}
#define ALL(a) (a).begin(),(a).end()
#define SORT(a) sort(ALL(a))
#define RSORT(a) SORT(a);reverse(ALL(a))
#define pb push_back
#define mp make_pair
#define PF first
#define PS second
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}
template<typename A, size_t N, typename T>void Fill(A (&array)[N], const T &val){fill( (T*)array, (T*)(array+N), val );}
#define OUT(x) cout << x << endl;
#define OUTD(x) cout << fixed << x << endl;
#define BOUT(b) if(b){OUT("Yes");}else{OUT("No");}
const ll MOD = 1000000007;
const ll INF = 10e9;
#define PI 3.14159265369;
ll dx[4] = {1,-1,0,0};
ll dy[4] = {0,0,1,-1};
ll ddx[8] = {1,1,1,-1,-1,-1,0,0};
ll ddy[8] = {0,1,-1,0,1,-1,1,-1};

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

    IN(ll,N);
    AIN(ll,A,N+1);
    AIN(ll,B,N);
    ll sum = 0;
    RREP(i,N){
        if(B[i] <= A[i+1]){
            sum += B[i];
            A[i+1] -= B[i];
        }else{
            B[i] -= A[i+1];
            sum += A[i+1];
            if(B[i] <= A[i]){
                sum += B[i];
                A[i] -= B[i];
            }else{
                sum += A[i];
                A[i] = 0;
            }
        }
    }
    OUT(sum);
}

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

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
#include <string>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <climits>
#include <bitset>
#include <array>
#include <deque>
#include <queue>
#include <map>
#include <set>
#define all(x) (x).begin(),(x).end()

const int MOD = 1e9 + 7;

void solve(){

}
int main(){
    ll K,A,B;
    cin >> K >> A >> B;
    ll ans = 0;
    if (B-A <= 2) {
        ans = K+1;
    } else {
        K -= (A-1);
        ans += A + (K/2)*(B-A);
        if (K % 2 == 1){
            ans++;
        }
    }
    cout << ans << endl;
        


    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <typeinfo>
#include <cxxabi.h>
#ifdef LOCAL
#include "dbgtoki.hpp"
#define DUMP(i) dump((string)TOSTRING(i), demangle(typeid(i).name()), __LINE__ , i) 
#else
#define DUMP(i)
#endif

using namespace std;
#define TOSTRING(x) #x
#define SZ(x) (int)(x).size()
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define ALL(s) (s).begin(), (s).end()
#define dis distance
#define so(V) sort(ALL(V))
#define rev(V) reverse(ALL(V))
#define uni(v) v.erase( unique(ALL(v)) , v.end());
#define pub push_back
#define sec second
#define fir first

typedef long long unsigned int llu;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vector <int> > vvi;
const int EPS = 1e-9;
const int MOD = 1e9+7;
const int INF = (1 << 30);
const double PI = acos(-1);

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	string s;
	cin >> s;
	int ans = 0;
	REP(i,6){
		if(s[i]=='1')ans++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#define _USE_MATH_DEFINES
#include <math.h>

using namespace std;

void solve()
{
	int a, b;
	char c;
	while (cin >> a >> c >> b)
	{
		if (c == '?')
		{
			return;
		}
		else if (c == '+')
		{
			cout << a + b << endl;
		}
		else if (c == '-')
		{
			cout << a - b << endl;
		}
		else if (c == '*')
		{
			cout << a * b << endl;
		}
		else if (c == '/')
		{
			cout << a / b << endl;
		}
	}
}

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

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

int main() {
    string S,T; 
    cin >> S >> T;
    int ans = 0;
    for(int i = 0; i < 3; i ++) {
        if(S.at(i) == T.at(i)) {
            ++ans;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
import sys
from functools import lru_cache

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, K, *A = map(int, read().split())

    K = list(map(int, f'{K:>040b}'))
    A_bin = [list(map(int, f'{a:>040b}')) for a in A]

    B = [0] * 40
    for a in A_bin:
        for i, bit in enumerate(a):
            B[i] += bit

    B = [1 if b < N - b else 0 for b in B]

    @lru_cache(maxsize=None)
    def rec(i, x, smaller):
        if i == 40:
            ans = 0
            for a in A:
                ans += x ^ a
            return ans
        elif smaller:
            return rec(i + 1, (x << 1) + B[i], True)
        elif K[i] <= B[i]:
            return rec(i + 1, (x << 1) + K[i], False)
        else:
            return rec(i + 1, (x << 1) + B[i], True)

    print(rec(0, 0, False))
    return


if __name__ == '__main__':
    main()


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

void solve()
{
    int n;cin>>n;ll sum=0;
    int a[n];map<int,int> m;
    for(int i=0;i<n;i++){
    cin>>a[i];m[a[i]]++;sum+=a[i];
    }
    int q,b,c;cin>>q;
    while(q--)
    {   cin>>b>>c;
        sum-=m[b]*(b-c);int x=m[b];
        m[b]=0;
        m[c]+=x;
        cout<<sum<<"\n";
    }
    
}

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


Measured memory_bytes: 8400
from sys import stdin

def getval():
    n,k = map(int,input().split())
    x = list(map(int,input().split()))
    return n,k,x

def main(n,k,x):
    idx = k-1
    ans = 0
    if x[0]>=0:
        ans = x[idx]
    elif x[idx]<=0:
        ans = abs(x[0])
    else:
        ans = min(abs(x[0]),abs(x[idx]))*2+max(abs(x[0]),abs(x[idx]))
    for i in range(k,n):
        temp = 0
        #print(ans)
        if x[i-k+1]>=0:
            temp = x[i]
        elif x[i]<=0:
            temp = abs(x[i-k+1])
        else:
            temp = min(abs(x[i]),abs(x[i-k+1]))*2+max(abs(x[i]),abs(x[i-k+1]))
        ans = min(ans,temp)
    print(ans)


if __name__=="__main__":
    n,k,x = getval()
    main(n,k,x)

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

int main()
{
	int N,K;
	int ans=1;
	
	cin >> N >> K;
	
	N-=K;
	K--;
	for(;;)
	{
		if(N<=0)
		{
			cout << ans << endl;
			return 0;
		}
		N-=K;
		ans++;
	}
	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int toInt(string s){
	int num=0;
	for(int i=0;i<s.size();i++){
		num=num*10+(s[i]-'0');
	}
	return num;
}
string toStr(int n,int a){
	string s;
	for(int i=a-1;i>=0;i--){
		int h=n/pow(10,i);
		h%=10;
		s+=(h+'0');
	}
	return s;
}
int main(){
	string s;int a;
	while(cin>>s>>a&&a!=0){
		vector<int> v;
		v.push_back(toInt(s));
		for(int i=0;i<30;i++){
			while((int)s.size()<a)s+='0';
			sort(s.begin(),s.end());
			int mini=toInt(s);
			reverse(s.begin(),s.end());
			int maxi=toInt(s);
			v.push_back(maxi-mini);
			s=toStr(maxi-mini,a);
		}
		int ans=10000,b,c;
		for(int i=0;i<v.size();i++){
			for(int j=i+1;j<v.size();j++){
				if(v[i]==v[j]&&j<ans){
					ans=i;b=v[j];c=j-i;
				}
			}
		}
		cout<<ans<<" "<<b<<" "<<c<<endl;
	}
}

Measured memory_bytes: 1280
#include "bits/stdc++.h"
using namespace std;
#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 ALL(x) (x).begin(), (x).end()  //昇順
#define RALL(x) (x).rbegin(), (x).rend() // 降順
#define SZ(x) ((int)(x).size)
const long long mod = 1e9+7;
typedef priority_queue<int> PQ;
typedef vector<long long> Vl;
typedef vector<int> VI;  // VI a(n);
typedef vector<string> VS;  
typedef vector<VS> VSS;  
typedef vector<VI> VVI;   // VVI a(n,vector<int>(m)) n * m 
typedef vector<Vl> VVl;
typedef pair<int, int> PII;
typedef vector<pair<int, int> > PS;
typedef long long ll;  //ll とdoubleは違う
// cout << << endl;
// cin >> ;
template<typename T>
T gcd(T a, T b){
	return b != 0 ? gcd(b, a % b) : a;
}    


int main(){
    ll x=0,g=0,n,w,l,r,ans,ptr=0;
    string s,s1,s2;
    cin >> n >> x;
    VI a(n);
    rep(i,n){
        cin >> a[i];
    }
    ans = abs(x-a[0]);
    for(int i=0;i<n-1;i++){
        ans = gcd(ans,abs(x-a[i+1]));
    }
    cout << ans << endl;
    return 0;

}


Measured memory_bytes: 640
#include "bits/stdc++.h"
//#define int long long
#define loop(i, a, b) for(int i = a; i < b; i++)
#define rep(i, a) loop(i, 0, a)
#define all(a) (a).begin(),(a).end()
using namespace std;
const int MOD = 1e9 + 7, INF = 1e9;
using vi = vector <int>;
using vvi = vector <vi>;
//g++ -std==c++14

signed main(){
	int n, k;
	cin >> n >> k;
	vi a(n);
	rep(i, n)cin >> a[i];
	
	set <int> arunashi;
	vi cnt;
	vi place(n);
	int  place_cnt = 0;
	rep(i, n){
		if(arunashi.find(a[i]) == arunashi.end()){
			cnt.push_back(1);
			arunashi.insert(a[i]);
			place[a[i] - 1] = place_cnt;
			place_cnt++;
		}
		else{
			cnt[place[a[i] - 1]]++;
		}
	}

	int va = arunashi.size();
	int sa = 0;
	sort(cnt.begin(), cnt.end());
	int ans = 0;
	while(va > k){
		ans += cnt[sa];
		sa++;
		va--;
	}
	cout << ans << endl;
}
		

			

Measured memory_bytes: 12020
#include <iostream>
#include <numeric>
#include <stdio.h>
#include <iomanip>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;
using ll = long long;
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
int Max(int(a), int(b), int(c)) {
	return max(max(a, b), c);
}
int Min(int(a), int(b), int(c)) {
	return min(min(a, b), c);
}





int main() {
	string s;
	int A=0, B;
	cin >>s;
	string an = "No";
	rep(i, s.size()) {
		if (s.at(i)== 'C'&&A==0) {
			A++;;
		}
		if (s.at(i) == 'F' && A == 1) {
			A++;;
		}

	}
	if (A == 2) {
		an = "Yes";
	}
	cout << an<< endl;
}

Measured memory_bytes: 384
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

struct Node{
  int keydata;
  struct Node *left,*right,*parent;
};

struct Node *root,*NIL;
void insert(int);

void preorder(struct Node *);

void inorder(struct Node *);

int main(){

  int n,i,x;
  char P[7];

 

  scanf("%d",&n);

  for(i=0;i<n;i++)
    {
      scanf("%s",P);
      if(strcmp("print",P)!=0){
	scanf("%d",&x);
	insert(x);
      }
      else
	{
	  inorder(root);
	  printf("\n");
	  preorder(root);
	  printf("\n");
	}
    }


  return 0;
}

void insert(int a)
{
  struct Node *y=NIL,*x=root;

  struct Node *z;

  z=(struct Node *)malloc(sizeof(struct Node));

  z->keydata=a;

  z->left=NIL;

  z->right=NIL;

  while(x!=NIL)
    {
      y=x;

      if(z->keydata < x->keydata) x=x->left;
      else x=x->right;
    }

  z->parent=y;

  if(y==NIL) root = z;

  else{ if(z->keydata < y->keydata) y->left = z;

  else y->right = z;
}
}
void preorder(struct Node *u){
  if (u == NIL)
    return ;
  printf(" %d",u->keydata);
  preorder(u->left);
  preorder(u->right);
}

void inorder(struct Node *u){
  if (u == NIL)
    return ;
  inorder(u->left);
  printf(" %d",u->keydata);
  inorder(u->right);
}

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

from fractions import gcd
g = gcd(A,B)

a = [1]
while g % 2 == 0:
    a.append(2)
    g //= 2
f = 3
while f * f <= g:
    if g % f == 0:
        a.append(f)
        g //= f
    else:
        f += 2
if g != 1:
    a.append(g)

print(len(set(a)))

Measured memory_bytes: 5044
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Math;

class MainClass : Scanner
{
    static void Main()
    {
        var (a, b, c) = ReadTuple<string,string,string>();
        if (a.Last() == b.First() && b.Last() == c.First())
        {
            WriteLine("YES");
        }
        else WriteLine("NO");
    }
}



class Scanner
{
    public static string RString() => Console.ReadLine();
    public static int RInt() => ReadTuple<int>();
    public static long RLong() => ReadTuple<long>();
    public static double RDouble() => ReadTuple<double>();

    public static string[] RStrings() => Console.ReadLine().Split();
    public static int[] RInts() => Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
    public static long[] RLongs() => Array.ConvertAll(Console.ReadLine().Split(), long.Parse);
    public static double[] RDoubles() => Array.ConvertAll(Console.ReadLine().Split(), double.Parse);
    public static int[] RInts(Func<string, int> func) => Console.ReadLine().Split().Select(func).ToArray();
    public static long[] RLongs(Func<string, long> func) => Console.ReadLine().Split().Select(func).ToArray();
    public static double[] RDoubles(Func<string, double> func) => Console.ReadLine().Split().Select(func).ToArray();
    //public static string[] RStrings(Func<string, string> func) => Console.ReadLine().Split().Select(func).ToArray();

    public static T1 ReadTuple<T1>()
    {
        var r = RString();
        var r1 = (T1)Convert.ChangeType(r, typeof(T1));
        return r1;
    }
    public static (T1, T2) ReadTuple<T1, T2>()
    {
        var r = RStrings();
        var r1 = (T1)Convert.ChangeType(r[0], typeof(T1));
        var r2 = (T2)Convert.ChangeType(r[1], typeof(T2));
        return (r1, r2);
    }
    public static (T1, T2, T3) ReadTuple<T1, T2, T3>()
    {
        var r = RStrings();
        var r1 = (T1)Convert.ChangeType(r[0], typeof(T1));
        var r2 = (T2)Convert.ChangeType(r[1], typeof(T2));
        var r3 = (T3)Convert.ChangeType(r[2], typeof(T3));
        return (r1, r2, r3);
    }
    public static (T1, T2, T3, T4) ReadTuple<T1, T2, T3, T4>()
    {
        var r = RStrings();
        var r1 = (T1)Convert.ChangeType(r[0], typeof(T1));
        var r2 = (T2)Convert.ChangeType(r[1], typeof(T2));
        var r3 = (T3)Convert.ChangeType(r[2], typeof(T3));
        var r4 = (T4)Convert.ChangeType(r[3], typeof(T4));
        return (r1, r2, r3, r4);
    }
}


Measured memory_bytes: 26300
using System;
using System.Diagnostics;
using System.IO;
using System.Text;
using System.Linq;
using System.Collections.Generic;
using System.Text.RegularExpressions;

class Program
{
    const string Yes = "Yes";
    const string No = "No";
    const long Mod = 1000000007;

    static void Main(string[] args) {
#if DEBUG
        MyDebugger.Test(process, "../TextFile1.txt");
#else
        object ret = process(new StreamReader(Console.OpenStandardInput()));
        Console.WriteLine(ret);
#endif
    }

    static object process(TextReader input) {
        var n = int.Parse(input.ReadLine());

        if (n < 4) return 1;

        var r = 0;

        for(int i=2; i <= (int)Math.Sqrt(n)+1; i++) {
            int y = i*i;
            while(y<=n) {
                r = Math.Max(r, y);
                y *= i;
            }
        }

        return r;
    }
}


Measured memory_bytes: 11092
#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
using namespace std;

struct UnionFind{
    vector<long long> par;
    vector<long long> size;

    UnionFind(long long n) : par(n){
        //initialization
        for(long long i = 0; i < n; i++){
            par[i] = i;
        }
        size.resize(n, 1);
    }

    long long root(long long x){
        if(par[x] == x){
            return x;
        }
        return par[x] = root(par[x]);
    }

    void unite(long long x, long long y){
        long long rx = root(x);
        long long ry = root(y);
        if(rx == ry){
            return;
        }

        par[rx] = ry;
        size[ry] += size[rx]; 
    }

    bool same(long long x, long long y){
        long long rx = root(x);
        long long ry = root(y);
        return rx == ry;
    }

    long long treeSize(long long x){
        //group size
        return size[root(x)];
    }
};

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

    UnionFind tree(n);

    set<long long> T;

    for(long long i = 0; i < m; i++){
        long long a, b;
        cin >> a >> b;
        a--;
        b--;
        tree.unite(a, b);
    }

    for(long long i = 0; i < n; i++){
        T.insert(tree.root(i));
    }

    cout << T.size() - 1 << endl;
    return 0;
}

Measured memory_bytes: 8288
#include <iostream>
#include <stdio.h>
using namespace std;
int main()
{
	int A, B;
	int T;
	cin >> A >> B >> T;
	int t, total = 0;

	for (t = A; t < T+1; t += A) {
		total += B;
	}
	cout << total;

	return 0;
}

Measured memory_bytes: 256
S = int(input())
m = 1000000007
ans = [-1] * 2001
ans[1] = 0
ans[2] = 0
ans[3] = 1
ans[4] = 1
ans[5] = 1
if S <= 5:
    print(ans[S])
else:
    cs = 0
    for i in range(6,S+1):
        cs = (cs+ans[i-3]) % m
        ans[i] = (cs+1) % m
    print(ans[S])

Measured memory_bytes: 9212
#include "bits/stdc++.h"
#define YES "YES"
#define NO "NO"
#define YESNO OUT(three(solve(),YES,NO))
#define ECHO OUT(solve())
#define three(A,B,C) ((A)?(B):(C))
#define FOR(i,a,b)  for(LL i=(a);i< (LL)(b);i++)
#define EFOR(i,a,b) for(LL i=(a);i<=(LL)(b);i++)
#define RFOR(i,a,b) for(LL i=(b);i>=(LL)(a);i--)
#define REP(i,b) FOR(i,zero,b)
#define rep REP
#define EREP(i,b) EFOR(i,zero,b)
#define RREP(i,b) RFOR(i,b,zero)
#define ALL(c) c.begin(),c.end()
#define UNIQUE(c) sort(ALL(c));c.erase(unique(ALL(c)),c.end())
#define MAX(c) (*max_element(ALL(c)))
#define MIN(c) (*min_element(ALL(c)))
#define MP make_pair
#define FI first
#define SE second
#define SI(x) (LL(x.size()))
#define PB push_back
#define DEBUG(a) OUT(a)
#define DEBUG2(a,b) OUT2(a,b)
#define cat cout << __LINE__ << endl
#define OUT(a) cout << (a) << endl
#define OUT2(a,b) cout << (a) <<" "<<(b) << endl
#define zero 0LL
#define all ALL
#define pb emplace_back
#define eb pb
#define int long long
using namespace std;
template<typename T> inline void maximize(T &a, T b) { a = max(a, b); }
template<typename T> inline void minimize(T &a, T b) { a = min(a, b); }
template<typename T> inline bool middle(T a, T b, T c) { return b <= a && a <= c; }
template<class T> inline bool MX(T &l, const T &r) { return l < r ? l = r, 1 : 0; }
template<class T> inline bool MN(T &l, const T &r) { return l > r ? l = r, 1 : 0; }
typedef int LL;
typedef double ld;
typedef int ut;
typedef vector<ut> VI;
typedef vector<VI> VII;
typedef pair<ut, ut> pr;
typedef pair<ut, pr> ppr;
typedef vector<pr> Vpr;
typedef vector<ppr> Vppr;
typedef tuple<int, int, int, int> tapu;
typedef vector<tapu> Vtapu;
typedef priority_queue<tapu, Vtapu, greater<tapu> > PQ;
inline void outputVI(VI x) { REP(i, SI(x)) { cout << three(i, " ", "") << x[i]; }OUT(""); }
const int SIZE1 = 3e5 + 1000;
const int SIZE2 = 5010;
const int SIZE3 = 430;
const int SIZE = SIZE1;
const int MAPSIZE = 40;
const LL p = 7 + 1e9;
const LL INF = 1LL << 60;
const long double EPS = 1e-7;
typedef pair<ld, ut> pld;
 

signed main(){
  LL N;
  cin >> N;
  LL q,x;
  LL pros=1,sums=0;
  REP(i,N){
    cin >>  q >> x;
    if(q==1){
      pros*=x;
      sums*=x;
    }
    if(q==2){
      sums+=x;
    }
    
    if(q==3){
      sums-=x;
    }
  }
  cout << -sums << " " << pros << endl;
  return 0;
}



Measured memory_bytes: 3120
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
static const int MAX = 100000;
static const int NIL = -1;

int n;
vector<int> G[MAX];
int color[MAX];

void dfs(int r, int c)
{
	stack<int> S;
	S.push(r);
	color[r]=c;
	while(!S.empty())
	{
		int u=S.top();
		S.pop();
		for(int i=0; i<G[u].size(); i++)
		{
			int v=G[u][i];
			if(color[v]==NIL)
			{
				color[v]=c;
				S.push(v);
			}
		}
	}
}

void assignColor()
{
	int id=1;
	for(int i=0; i<n; i++)
	{
		color[i]=NIL;
	}
	for(int u=0; u<n; u++)
	{
		if(color[u]==NIL)
		{
			dfs(u, id++);
		}
	}
}

int main()
{
	int s, t, m, q;
	cin>>n>>m;
	for(int i=0; i<m; i++)
	{
		cin>>s>>t;
		G[s].push_back(t);
		G[t].push_back(s);
	}
	
	assignColor();
	cin>>q;
	
	for(int i=0; i<q; i++)
	{
		cin>>s>>t;
		if(color[s]==color[t])
		{
			cout<<"yes"<<endl;
		}
		else
		{
			cout<<"no"<<endl;
		}
	}
	return 0;
}


Measured memory_bytes: 8976
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)     for(int i = 0; i < (int)(n); i++)
#define rep2(i, m, n) for(int i = m; i < (int)(n); i++)
#define MOD 1000000007
#define Graph vector<vector<int>>

int main() {
  int P[5];
  int K;
  cin >> P[4] >> P[3] >> P[2] >> P[1] >> P[0] >> K;
  
  bool ans = false;
  rep(i,5){
    rep2(j,i+1,5){
      if((P[i] - P[j]) > K) ans = true;
    }
  }
  
  if(ans){
    printf(":(");
  }else{
	printf("Yay!");    
  }

  return 0;
}


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

using namespace std;

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

const double PI = 3.1415926535897932384626433832795;

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

int gcd(int x, int y) { return y ? gcd(y, x % y) : abs(x); }
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : abs(x); }
int lcm(int x, int y) { return x / gcd(x, y) * y; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }

template< typename T >
T extgcd(T a, T b, T &x, T &y) {
	T d = a;
	if (b != 0) {
		d = extgcd(b, a % b, y, x);
		y -= (a / b) * x;
	} else {
		x = 1;
		y = 0;
	}
	return d;
}

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

	ll a, b, x, y;
	cin >> a >> b;

	extgcd(a, b, x, y);
	cout << x << " " << y << endl;
	return 0;
}



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

int main() {
  int N;
  cin >> N;
  
  vector<int> vec(46300);
  for (int i = 0; i < 46300; i++) {
    vec.at(i) = i*1.08;
  }
  
  for (int i = 0; i < 46300; i++) {
    if (vec.at(i) == N){
      cout << i << endl;
      break;
    }
    else if (vec.at(i) > N){
      cout << ":(" << endl;
      break;
    }
  }
}
  

Measured memory_bytes: 384
n,m = gets.split.map(&:to_i)

arr = []

n.times{
  arr<<gets.split.map(&:to_i)}
 
arr2=arr.map{ |i| i[0]+i[1]-i[2]}.sort.reverse[0..m-1].inject(:+)
arr3=arr.map{ |i| i[0]-i[1]+i[2]}.sort.reverse[0..m-1].inject(:+)
arr4=arr.map{ |i| i[0]-i[1]-i[2]}.sort.reverse[0..m-1].inject(:+)
arr5=arr.map{ |i| -i[0]+i[1]+i[2]}.sort.reverse[0..m-1].inject(:+)
arr6=arr.map{ |i| -i[0]+i[1]-i[2]}.sort.reverse[0..m-1].inject(:+)
arr7=arr.map{ |i| -i[0]-i[1]+i[2]}.sort.reverse[0..m-1].inject(:+)
arr8=arr.map{ |i| -i[0]-i[1]-i[2]}.sort.reverse[0..m-1].inject(:+)
arr1=arr.map{ |i| i[0]+i[1]+i[2]}.sort.reverse[0..m-1].inject(:+)

if m!=0

p [arr1,arr2,arr3,arr4,arr5,arr6,arr7,arr8].max
else
    p 0
end


Measured memory_bytes: 2040
#include <algorithm>
#include <climits>
#include <deque>
#include <iostream>
#include <map>
#include <math.h>
#include <set>
#include <string.h>
#include <utility>
#include <vector>
using namespace std;

#define dlog(str) cout << "====" << str << endl;
#define INF 999999999
#define MOD 1000000007
#define REP(i, n) for(int i = 0, i##_l = (n); i < i##_l; i++)
#define REPR(i, n) for(int i = n - 1; 0 <= i; i--)
#define FOR(i, s, e) for(int i = s; i <= e; i++)
#define FORR(i, s, e) for(int i = s; e <= i; i--)
#define LLI long long int
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define bit(a, shift) ((a>>shift)&1))
#define ALL(v) (v).begin(), (v).end()
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort((v).rbegin(), (v).rend())
// int 2.14E±9    lli 9.2E±18    double 1.7E±380

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> v(M);
    vector<int> m(N + 1);

    REP(i, M) { cin >> v[i]; }

    m[0] = 1;
    m[1] = 1;
    REP(i, N - 1) {
        m[i + 2] = m[i + 1] + m[i];
        m[i + 2] %= MOD;
    }
    LLI sum = 1;
    int pre = 0;
    REP(i, M) {
        int a = (v[i] - 1) - pre;
        if(pre == v[i])
            sum *= 0;
        if(pre - 1 != v[i]) {
            sum *= m[a];
            sum %= MOD;
        }
        pre = v[i] + 1;
    }
    sum *= m[max(N - pre, 1)];
    sum %= MOD;
    cout << sum;
    return 0;
}

Measured memory_bytes: 1024
#include<iostream>
using namespace std;
int main(){
	double a[2],b[2],c[2],d[2];
	while(cin >>a[0]>>a[1]>>b[0]>>b[1]>>c[0]>>c[1]>>d[0]>>d[1]){
		if(a[0] == b[0] && c[1] == d[1]){cout <<"YES"<<endl;}
		else if(a[1] == b[1] && c[0] == d[0]){cout <<"YES"<<endl;}
		else{
			double tab,tcd;
			tab = (a[1]-b[1])/(a[0]-b[0]);
			tcd = (c[1]-d[1])/(c[0]-d[0]);
			if(tab*tcd == -1){cout <<"YES"<<endl;}
			else{cout <<"NO"<<endl;}
		}
	}
	return 0;
}

Measured memory_bytes: 0
import java.util.*;

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

    int n = sc.nextInt();
    String s = sc.next();
    String t = sc.next();
    
    for(int i = 0; i < n; i++){
      sb.append(s.charAt(i));
      sb.append(t.charAt(i));
    }

    String ans = sb.toString();
    System.out.println(ans);
  }
}


Measured memory_bytes: 21332
n , d = map(int, input().split())
info = [list(map(int, input().split())) for i in range(n)]
cnt = 0
for i in range(n):
    for j in range(i+1, n):
        ans = 0
        for k in range(d):
            ans += (info[i][k] - info[j][k])**2
        ans = ans ** (0.5)
        # print(ans)
        if ans == int(ans):
            cnt += 1
print(cnt)

Measured memory_bytes: 38384
#include <iostream>
#include <unordered_map>
#include <vector>

int main()
{
    std::string s, t;
    std::cin >> s >> t;

    std::unordered_map<char, std::vector<int>> char_pos;

    for (int i = 0; i < s.length(); i++) {
        char_pos[s[i]].push_back(i);
    }

    for (int i = 0; i < s.length(); i++) {
        char_pos[s[i]].push_back(i + s.length());
    }

    long long ans = 0;
    int ptr = 0;
    for (auto c : t) {
        if (char_pos[c].empty()) {
            std::cout << -1 << std::endl;
            return 0;
        }

        ptr = *lower_bound(char_pos[c].begin(), char_pos[c].end(), ptr) + 1;

        if (ptr >= s.length()) {
            ptr -= s.length();
            ans += s.length();
        }
    }

    ans += ptr;
    std::cout << ans << std::endl;
}


Measured memory_bytes: 1724
#include <iostream>
#include <cstdlib>
using namespace std;
#define INF 1000000010

int main(void){
  long N,M,K;
  cin>>N>>M>>K;
  long* A = (long*)malloc(sizeof(long)*(N+1));
  long* B = (long*)malloc(sizeof(long)*(M+1));
  for(int i=0;i<N;i++){
    cin>>A[i];
  }
  A[N]=INF;
  for(int i=0;i<M;i++){
    cin>>B[i];
  }
  B[M]=INF;
  long a=0;
  long t=0;
  for(long i=0;t+A[i]<=K;i++){
    t+=A[i];
    a++;
  }
  long b=0;
  long retval=a+b;
  while(a>=0 and b>=0){
    if(t+B[b]<=K){
      t+=B[b];
      b++;
    }
    else{
      a--;
      t-=A[a];
    }
    if(a>=0){
      retval=max(retval,a+b);
    }
  }

  cout<<retval<<endl;
  return 0;
}


Measured memory_bytes: 6708
#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
#include <tuple>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <array>
#include <valarray>
#include <climits>

using namespace std;

using ll = long long;

int main()
{
    int N;
    scanf("%d\n", &N);
    const ll NN = static_cast<ll>(N) * (N + 1) / 2;
    vector<int> A(N);
    ll A_mod = 0;
    int times = 0;
    for (int i = 0; i < N; ++i){
        int Ai;
        scanf("%d", &Ai); getchar();
        A[i] = Ai;
        A_mod += Ai;
        while (A_mod >= NN){
            A_mod -= NN;
            ++times;
        }
    }
    if (A_mod != 0){
        puts("NO");
        return 0;
    }
    vector<ll> B(N);
    B[0] = (A[N - 1] - A[0]) + times;
    for (int i = 1; i < N; ++i) B[i] = (A[i - 1] - A[i]) + times;
    int total = 0;
    for (auto& Bi : B){
        if (Bi < 0 || Bi % N){
            puts("NO");
            return 0;
        }else{
            total += (Bi / N);
        }
    }
    if (total == times){
        puts("YES");
    }else{
        puts("NO");
    }
}


Measured memory_bytes: 1536
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
using namespace std;

int dx8[] = {0,1,1,1,0,-1,-1,-1};
int dy8[] = {1,1,0,-1,-1,-1,0,1};

int main(){
    int h, w;
    cin >> h >> w;
    string board[60];
    for (int i = 0; i < h; i++) {
        cin >> board[i];
    }
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if(board[i][j] == '#')continue;

            int bomb = 0;
            for (int d = 0; d < 8; d++) {
                int dy = i + dy8[d];
                int dx = j + dx8[d];

                if(dy < 0 || dy >= h) continue;
                if(dx < 0 || dx >= w) continue;
                if(board[dy][dx] == '#') bomb++;
            }
            board[i][j] = char(bomb + '0');
        }
    }
    for (int i = 0; i < h; i++) {
        cout << board[i] << endl;
    }
    return 0;
}


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

#define endl '\n'

using namespace std;

vector<string> equation;
void split(string str)
{
    istringstream ss(str);

    do {
        string word;
        ss >> word;
        equation.push_back(word);
    } while (ss);
}

int toInteger(string s)
{
    stringstream num(s);
    int n = 0;
    num >> n;
    return n;
}

int main()
{
    string s;
    getline(cin, s);
    split(s);

    stack<long long> calculation;
    int first, second;
    for(size_t i = 0; i < equation.size() - 1; i++)
    {
        if(equation[i] == "+")
        {
            second = calculation.top();
            calculation.pop();
            first = calculation.top();
            calculation.pop();

            calculation.push(first + second);
        }
        else if(equation[i] == "-")
        {
            second = calculation.top();
            calculation.pop();
            first = calculation.top();
            calculation.pop();

            calculation.push(first - second);
        }
        else if(equation[i] == "*")
        {
            second = calculation.top();
            calculation.pop();
            first = calculation.top();
            calculation.pop();

            calculation.push(first * second);
        }
        else
        {
            calculation.push(toInteger(equation[i]));
        }
    }
    cout << calculation.top() << endl;

    return 0;
}



Measured memory_bytes: 3184
n=int(input())
List=[]
for i in range(n):
    a=int(input())
    List.append(a)
mylist=sorted(List)
max_num=mylist[-1]
max_num_2=mylist[-2]
for i in range(n):
    if List[i]!=max_num:
        print(max_num)
    else:
        print(max_num_2)

Measured memory_bytes: 19168
#include <iostream>
#include <vector>
#include <set> 
#include <map>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
typedef long long int ll;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,k;
    cin>>n>>k;
    ll arr[n+1];
    for(int i=1;i<=n;i++)cin>>arr[i];
    ll mul=1;
    for(int i=k+1,j=1;i<=n;i++,j++){
        if(arr[i]<=arr[j]){
            cout<<"No"<<endl;
        }
        else cout<<"Yes"<<endl;
        //mul=mul2;
    }
    //cout<<(flag?"Yes":"No");
    return 0;
}

Measured memory_bytes: 5232
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <deque>
#include <queue>
#include <cctype>
#include <cstdio>
#include <math.h>
#include <set>
#include <stack>
#include <cstring>
#include <iomanip>
#define INF 1000000000
#define MOD 1000000007
using namespace std;
using ll = long long;
int main() {
    int n,m;
    cin >> n >> m;
    int n_ans = 0;
    int m_ans = 0;
    for(int i = 1; i < n;i++){
        n_ans += n - i;
    }
    
    for(int i = 1; i < m;i++){
        m_ans += m - i;
    }
    cout << n_ans + m_ans << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
using namespace std;
const long long mod = 998244353;
inline long long mp(long long b, long long e) {
	if (e == 0) return 1;
	long long a = mp(b, e / 2);
	a = a * a % mod;
	if (e & 1) a = a * b % mod;
	return a;
}
int main() {
	long long N, M, K, ans = 0;
	scanf("%lld %lld %lld", &N, &M, &K);
	long long fac[N + 1], rev[N + 1];
	fac[0] = 1;
	for (int i = 1; i <= N; ++i) fac[i] = i * fac[i - 1] % mod;
	for (int i = 0; i <= N; ++i) rev[i] = mp(fac[i], mod - 2);
	for (int i = 0; i <= K; ++i) {
		ans += M * mp(M - 1, N - i - 1) % mod * fac[N - 1] % mod * rev[N - i - 1] % mod * rev[i] % mod;
		ans %= mod;
	}
	printf("%lld", ans);
	return 0;
}

Measured memory_bytes: 4852
#![allow(unused_imports)]
use std::io::{ self, Write };
use std::str::FromStr;
use std::cmp::{ min, max };
use std::collections::{ BinaryHeap, VecDeque };

#[allow(unused_macros)]
macro_rules! trace {
    ($var:expr) => {
        let _ = writeln!(&mut std::io::stderr(), ">>> {} = {:?}", stringify!($var), $var);
    };
    ($($args:expr),*) => { trace!(($($args),*)) }
}

#[allow(unused_macros)]
macro_rules! put {
    ($var:expr) => {
        let _ = writeln!(&mut std::io::stdout(), "{}", $var);
    };
    ($var:expr, $($args:expr),*) => {
        let _ = write!(&mut std::io::stdout(), "{} ", $var);
        put!($($args),*);
    };
}

fn main() {
    let mut sc = Scanner::new();
    let n: usize = sc.cin();
    let xs: Vec<i64> = (0..n).map(|_|sc.cin()).collect();

    let mut memo = vec![vec![None; 3001]; 3001];
    {
        let mut stack = vec![];
        stack.push((0, n));
        while let Some((l, r)) = stack.pop() {
            if memo[l][r] != None {
                continue;
            }
            if l == r {
                memo[l][r] = Some(0);
                continue;
            }
            if l + 1 == r {
                memo[l][r] = Some(xs[l]);
                continue;
            }
            if memo[l+1][r] != None && memo[l][r-1] != None {
                let a = memo[l+1][r].unwrap();
                let b = memo[l][r-1].unwrap();
                memo[l][r] = Some(max(xs[l] - a, xs[r-1] - b));
            } else {
                stack.push((l, r));
                if memo[l+1][r] == None { stack.push((l+1, r)); }
                if memo[l][r-1] == None { stack.push((l, r-1)); }
            }
        }
    }
    put!(memo[0][n].unwrap());
}

#[allow(dead_code)]
struct Scanner { stdin: io::Stdin, buffer: VecDeque<String>, }
#[allow(dead_code)]
impl Scanner {
    fn new() -> Scanner { Scanner { stdin: io::stdin(), buffer: VecDeque::new() } }
    fn reserve(&mut self) {
        while self.buffer.len() == 0 {
            let mut line = String::new();
            let _ = self.stdin.read_line(&mut line);
            for w in line.split_whitespace() {
                self.buffer.push_back(String::from(w));
            }
        }
    }
    fn cin<T: FromStr>(&mut self) -> T {
        self.reserve();
        match self.buffer.pop_front().unwrap().parse::<T>() {
            Ok(a) => a,
            Err(_) => panic!("parse err")
        }
    }
}


Measured memory_bytes: 166140
using System;
using System.Collections;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Collections.Generic;
using System.Threading.Tasks;

class Program
{
	static int N, M;
	static int[][] dp;
	static List<int>[] pathList;
	static bool[] already;
	static Queue<int> nextStart;
	static Queue<int> nextGoal;

	//探索
	static void Search(int start, int before){
		foreach(int goal in pathList[start]){
				if(!already[goal]){
						//startにが次の地点にとってのgoalとなる
						dp[goal][0] = start;
						dp[goal][1] = dp[start][1] + 1;

						//探索済みを示す
						already[goal] = true;

						//キューに追加
						nextStart.Enqueue(goal);
						nextGoal.Enqueue(start);
				}
		}

		//キューが空の場合、終了
		if(nextStart.Count() <= 0){
				return;
		}
		//次に探すべき地点を検索
		else{
				int nextS = nextStart.Dequeue();
				int nextB = nextGoal.Dequeue();
				Search(nextS, nextB);
		}
	}

	//Main
	static void Main(string[] args)
	{
		//読み込む
		string[] S = Console.ReadLine().Split(' ');
		N = int.Parse(S[0]);
		M = int.Parse(S[1]);
		pathList = new List<int>[N];
		dp = new int[N][];
		already = new bool[N];

		nextStart = new Queue<int>();
		nextGoal = new Queue<int>();

		//初期化
		for(int i=0; i<N; i++){
				pathList[i] = new List<int>();
				dp[i] = new int[2];
		}

		//読み込む
		for(int i=0; i<M; i++){
				string[] line = Console.ReadLine().Split(' ');
				int Ai = int.Parse(line[0]);
				int Bi = int.Parse(line[1]);

				pathList[Ai-1].Add(Bi-1);
				pathList[Bi-1].Add(Ai-1);
		}

		//0から探す
		already[0] = true;
		Search(0,0);

		bool possible = true;

		for(int i=1; i<N; i++){
				if(already[i] = false){
						possible = false;
						break;
				}
		}
		if(possible){
			Console.WriteLine("Yes");
			for(int i=1; i<N; i++){
					Console.WriteLine(dp[i][0]+1);
			}
		}
		else{
			Console.WriteLine("No");
		}
	}
}



Measured memory_bytes: 53732
#include <bits/stdc++.h>
#define REP(i, n) for(int i=0; i<(int)(n); i++)
#define REP1(i,a,b) for(int i=a; i<=(int)(b); i++)
#define ALL(x) begin(x),end(x)
#define PB push_back
using namespace std;
typedef int64_t LL;
typedef vector<int> VI;
typedef pair<int,int> PII;

template<class T> inline bool chmax( T &a, const T &b ) { return b>a ? a=b,true : false; }
template<class T> inline bool chmin( T &a, const T &b ) { return b<a ? a=b,true : false; }
template<class T> using MaxHeap = priority_queue<T>;
template<class T> using MinHeap = priority_queue<T, vector<T>, greater<T>>;
template<class T, class F=less<T>> void sort_uniq( vector<T> &v, F f=F() ) {
    sort(begin(v),end(v),f);
    v.resize(unique(begin(v),end(v))-begin(v));
}

const int N=1e6+5;
int a[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    string x;
    cin >> n >> x;
    // init
    // vector<LL> a(n+1);
    for ( int i=1; i<=n; i++ ) {
        a[i]=a[i%__builtin_popcount(i)]+1;
    }

    LL M=0;
    REP(i,n) if ( x[i]=='1' ) M++;

    vector<LL> ans(n);
    if ( M<n ) {
        LL p=1;
        LL res=0;
        for ( int i=n-1; i>=0; i-- ) {
            if ( x[i]=='1' ) {
                res+=p%(M+1);
            }
            p=(LL)p*2%(M+1);
        }

        p=1;
        for ( int i=n-1; i>=0; i-- ) {
            if ( x[i]=='0' ) {
                LL y=(res+p)%(M+1);
                ans[i]=a[y]+1;
            }
            p=p*2%(M+1);
        }
    }
    if ( M>1 ) {
        LL p=1;
        LL res=0;
        for ( int i=n-1; i>=0; i-- ) {
            if ( x[i]=='1' ) {
                res+=p%(M-1);
            }
            p=(LL)p*2%(M-1);
        }

        p=1;
        for ( int i=n-1; i>=0; i-- ) {
            if ( x[i]=='1' ) {
                LL y=(res-p)%(M-1);
                if ( y<0 ) y+=M-1;
                ans[i]=a[y]+1;
            }
            p=p*2%(M-1);
        }
    }
    REP(i,n) cout << ans[i] << '\n';
    return 0;
}


Measured memory_bytes: 5980
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <climits>
#include <bitset>
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pair<int,int>> vpii;
typedef vector<vector<int>> vvi;
typedef vector<vector<char>> vvc;
typedef vector<vector<string>> vvs;
#define rep(i,n) for(int i=0;i<n;i++)
#define fin(ans) cout<<(ans)<<endl
#define P 1000000007
#define STI(s) atoi(s.c_str())//string to int
#define mp(p,q) make_pair(p,q)
#define Sort(a) sort(a.begin(),a.end())
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
const int INF = INT_MAX;
const long long LLINF = 1LL<<60;
//g++ -std=c++1z temp.cpp
//./a.exe

ll gcd(ll c, ll d) { return d ? gcd(d, c%d) : c;}
ll lcm(ll c, ll d) { return c / gcd(c,   d) * d;}


int main(void){ios::sync_with_stdio(false);cin.tie(0);
//////////////////////////////////////////////////////
int n,h[1000]={},H=0,ans = 0;
cin >> n;
rep(i,n){
    cin >> h[i];
}
rep(i,n){
    if (h[i] >= H)
    {
        ans++;
        H = h[i];
    }
    
}
cout << ans << endl;







//////////////////////////////////////////////////////
return 0;}

Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
  int x1, x2, y1, y2, dx, dy;
  scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
  dx = x2 - x1;
  dy = y2 - y1;
  printf("%d %d %d %d", x2 - dy, y2 + dx, x1 - dy, y1 + dx);
	return 0;
}

Measured memory_bytes: 128
A,B,C,D = map(int,input().split())
#N=int(input())
#A = list(map(int,input().split()))
#S=str(input())
flag=True
while C>0 and A>0:
    C-=B
    if C<=0:
        print('Yes')
        exit()

    A-=D
    if A<=0:
        print('No')
        exit()


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

constexpr int inf = 0x3f3f3f3f;
constexpr ll linf = 0x3f3f3f3f3f3f3f3fLL;

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

    int n, m; cin >> n >> m;
    ll t = 0;
    for (int i = 0; i < m; i++) {
        int a; cin >> a;
        t += a;
    }
    if (t > n) cout << -1 << endl;
    else cout << n - t << endl;
    return 0;
}


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

int main(){
    ll n,m;
    cin>>n>>m;
    vector<ll> h(n);
    rep(i,n) cin>>h[i];
    vector<vector<ll>> adj(n);
    ll a,b;
    rep(i,m){
        cin>>a>>b;
        a--; b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    vector<bool> IsGood(n,1);
    rep(i,n){
        if(IsGood[i]){
            rep(j,adj[i].size()){
                if(h[i]>h[adj[i][j]]) IsGood[adj[i][j]]=0;
                else if(h[i]==h[adj[i][j]]) IsGood[i]=IsGood[adj[i][j]]=0;
                else IsGood[i]=0;
            }
        }
    }
    ll ans=0;
    rep(i,n) ans+=IsGood[i];
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 9860
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <stack>
using namespace std;
typedef long long int ll;

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	string s,t; cin >> s >> t;
	int q; cin >> q;
	int n=s.size(),m=t.size();
	vector<int> cnt(n+1,0),cnt2(m+1,0);
	for(int i=0;i<n;i++){
		cnt[i+1]=cnt[i]+1+(s[i]=='B');
	}
	for(int i=0;i<m;i++){
		cnt2[i+1]=cnt2[i]+1+(t[i]=='B');
	}
	while(q--){
		int a,b,c,d; cin >> a >> b >> c >> d;
		int x=cnt[b]-cnt[a-1];
		int y=cnt2[d]-cnt2[c-1];
		if(x%3==y%3){
			cout << "YES" << endl; 
		}else{
			cout << "NO" << endl;
		}
	}
}



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

int n,k,pos=1,ans=0;

signed main()
{
	cin>>n>>k;
	while (1)
	{
		if (pos>n)  break;
		else
		{
			pos*=k;
			ans++;
		}
	}
	cout<<ans<<endl;
	return 0;
}

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

int main()
{
	ios::sync_with_stdio(false);
	
	string s;
	cin>>s;
	long long int y=0;
	
	for(int i=0;i<s.size()-1;i++)
	{
		if(s[i]==s[i+1])
		{
			cout<<i+1<<" "<<i+2<<endl;
			y++;
			break;
		}
		if(i+2<s.size())
		{
			if(s[i]==s[i+2]&&s[i+1])
			{
				y++;
				cout<<i+1<<" "<<i+3<<endl;
				break;
			}
		}
	}
	
	if(y==0)
		cout<<-1<<" "<<-1<<endl;
	
	return 0;
}

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

#define mod 1000000007

using namespace std;
typedef long long ll; 
 
int main(void){
	
	int R;
	
	cin >> R;
	
	if(R < 1200)
		cout << "ABC";
	else if(R < 2800)
		cout << "ARC";
	else
		cout << "AGC";
	
	return 0;
}

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

using namespace std;

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

    int x, y, a, b, C;
    cin >> x >> y >> a >> b >> C;
    int r[a], g[b], c[C];
    long long smallest[x + y + 1], ans, pre = 0, sumX = 0, sumY = 0;

    for (int i = 0; i < a; i++)
        cin >> r[i];
    for (int i = 0; i < b; i++)
        cin >> g[i];
    for (int i = 0; i < C; i++)
        cin >> c[i];
    sort(r, r + a, greater<int>());
    sort(g, g + b, greater<int>());
    sort(c, c + C, greater<int>());

    for (int i = 0; i < x; i++)
        sumX += r[i];
    for (int i = 0; i < y; i++)
        sumY += g[i];

    smallest[0] = 0;
    int i = x - 1, j = y - 1;

    ans = sumX + sumY;
    for (int k = 1; k <= x + y && k <= C; k++) {
        smallest[k] = smallest[k - 1];
        if (i < 0)
            smallest[k] += g[j--];
        else if (j < 0)
            smallest[k] += r[i--];
        else {
            if (r[i] < g[j])
                smallest[k] += r[i--];
            else
                smallest[k] += g[j--];
        }
        pre += c[k - 1];
        ans = max(ans, sumX + sumY - smallest[k] + pre);
    }

    cout << ans << '\n';

    return 0;
}

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

int main() {
    string a, b, c, ans="   ";
    cin >> a >> b >> c;
    ans.at(0)=(a.at(0)-'a'+'A');
    ans.at(1)=(b.at(0)-'a'+'A');
    ans.at(2)=(c.at(0)-'a'+'A');
    printf("%s\n", ans.c_str());
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define rep(i, n) for(int i = 0; i < n; i++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fi first
#define se second
#define pb push_back
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF = (1<<30) - 1;
const ll LINF = (1LL<<60) - 1;
const ll mod = 1000000007;

void solve() {
    int n;cin >> n;
    ll ans = 0;
    rep(i, n + 1) {
        if (i % 5 == 0 || i % 3 == 0) continue;
        ans += i;
    }
    cout << ans << endl;
    return;
}

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


Measured memory_bytes: 3632