akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <stdio.h>
#include <vector>

using namespace std;

#define max 100001

string str;
/*
	dp[インデックス][最後に踏んだ足][左足の番号][右足の番号]
*/

int min(int p, int q){
	if( p > q ) return q;
	return p;
}

int main(void){
	//FILE* fp_in = freopen("data.txt", "r", stdin);

	int dp[2][2][9][9];

	while( 1 ) {
		str = "";
		cin >> str;
		if( str == "#" ) break;
		int arrow = str[0] - '1';

		for(int i = 0; i < 2; i++)
			for(int j = 0; j < 9; j++)
				for(int k = 0; k < 9; k++)
					for(int l = 0; l < 2; l++)
						dp[l][i][j][k] = 1 << 30;

			for(int j = 0; j < 9; j++) { 
				dp[1][1][j][arrow] = 0;
				dp[1][0][arrow][j] = 0;
			}

		for(int i = 1; i < str.length(); i++) {
			arrow = str[i] - '1';

			for(int j = 0; j < 2; j++)
				for(int k = 0; k < 9; k++)
					for(int l = 0; l < 9; l++)
						dp[0][j][k][l] = dp[1][j][k][l];

			for(int j = 0; j < 2; j++)
				for(int k = 0; k < 9; k++)
					for(int l = 0; l < 9; l++)
						dp[1][j][k][l] = 1 << 30;

			//i-1番目と同じ足を出す
			//左足
			for(int j = 0; j < 9; j++)
				for(int k = 0; k < 9; k++)
					if( arrow % 3 <= k % 3 && j != k && j % 3 <= k % 3 && arrow != k )
						dp[1][0][arrow][k] = min( dp[0][0][j][k] + 1, dp[1][0][arrow][k] );
			for(int j = 0; j < 9; j++)
				for(int k = 0; k < 9; k++)
					if( arrow % 3 >= j % 3 && j != k && j % 3 <= k % 3 && arrow != j )
						dp[1][1][j][arrow] = min( dp[0][1][j][k] + 1, dp[1][1][j][arrow] );
			//i-1番目と異なる足を出す
			for(int j = 0; j < 9; j++)
				for(int k = 0; k < 9; k++)
					if( arrow % 3 <= k % 3 && j != k && j % 3 <= k % 3 && arrow != k )
						dp[1][0][arrow][k] = min( dp[0][1][j][k], dp[1][0][arrow][k] );
			for(int j = 0; j < 9; j++)
				for(int k = 0; k < 9; k++)
					if( arrow % 3 >= j % 3 && j != k && j % 3 <= k % 3 && arrow != j )
						dp[1][1][j][arrow] = min( dp[0][0][j][k], dp[1][1][j][arrow] );
		}

		int min = 1 << 30;
		//cout << str << endl;

 		for(int i = 0; i < 2; i++)  
			for(int j = 0; j < 9; j++)
				for(int k = 0; k < 9; k++)
					if( dp[1][i][j][k] < 1 << 30 ) {
						if(min > dp[1][i][j][k] ) min = dp[1][i][j][k];
					}
		cout << min << endl;


	}


	//while(1){}
	return 0;
}

Measured memory_bytes: 1320
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            String s = sc.next();
            if (map.keySet().contains(s)) {
                map.put(s, map.get(s) + 1);
            } else {
                map.put(s, 1);
            }
        }
        int max = 0;
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            max = Math.max(max, entry.getValue());
        }
        Map<String, Integer> sorted = new TreeMap<>(map);
        for (Map.Entry<String, Integer> entry : sorted.entrySet()) {
            if (entry.getValue() != max) {
                continue;
            }
            System.out.println(entry.getKey());
        }
        sc.close();
    }
}

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

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

int main()
{
    int A1, A2, A3;
    cin >> A1 >> A2 >> A3;
    cout << max({A1, A2, A3}) - min({A1, A2, A3}) << endl;
}

Measured memory_bytes: 256
/*
    if you can't see the repay
    Why not just work step by step
    rubbish is relaxed
    to ljq
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <cmath>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#include <vector>
#include <stdlib.h>
#include <algorithm>
using namespace std;

#define dbg(x) cout<<#x<<" = "<< (x)<< endl
#define dbg2(x1,x2) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<endl
#define dbg3(x1,x2,x3) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<" "<<#x3<<" = "<<x3<<endl
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define lc (rt<<1)
#define rc (rt<<11)
#define mid ((l+r)>>1)

typedef pair<int,int> pll;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int _inf = 0xc0c0c0c0;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll _INF = 0xc0c0c0c0c0c0c0c0;
const ll mod =  (int)1e9+7;

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll ksm(ll a,ll b,ll mod){int ans=1;while(b){if(b&1) ans=(ans*a)%mod;a=(a*a)%mod;b>>=1;}return ans;}
ll inv2(ll a,ll mod){return ksm(a,mod-2,mod);}
void exgcd(ll a,ll b,ll &x,ll &y,ll &d){if(!b) {d = a;x = 1;y=0;}else{exgcd(b,a%b,y,x,d);y-=x*(a/b);}}//printf("%lld*a + %lld*b = %lld\n", x, y, d);
const int MAX_N = 1025;
#define MOD 1000000007
char mp[MAX_N][MAX_N];
ll dp[MAX_N][MAX_N];
int main()
{
    //ios::sync_with_stdio(false);
    //freopen("a.txt","r",stdin);
    //freopen("b.txt","w",stdout);
    int n,m;scanf("%d%d",&n,&m);
    for(int i = 1;i<=n;++i) scanf("%s",mp[i]+1);
    dp[1][1] = 1;
    for(int i = 1;i<=n;++i)
    {
        for(int j = 1;j<=m;++j)
        {
            if(mp[i][j]!='#') (dp[i][j] += dp[i-1][j] + dp[i][j-1])%=MOD;
        }
    }
    printf("%d\n",dp[n][m]);
    //fclose(stdin);
    //fclose(stdout);
    //cout << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;
    return 0;
}


Measured memory_bytes: 9472
#include<iostream>
#include<math.h>
#include<string>
#include<algorithm>
using namespace std;

int main(){
	int a,b;
	cin>>a>>b;
	bool flag=false;
	if(a%3==0)flag=true;
	if(b%3==0)flag=true;
	if((a+b)%3==0)flag=true;
	if(flag)cout<<"Possible"<<endl;
	else cout<<"Impossible"<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
using namespace std; 
int main()
{
	int n;
	cin >> n;
	int count=0;
	for(int i=1;i<=n;i++)
	{
		int a;
		cin >> a;
		if((i%2!=0)&&(a%2!=0))	count++;
	}
	cout << count;
	return 0;
}


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

# define C continue;
# define R return

# define D double
# define I insert
# define ll long long
# define ld long double

# define ull unsigned long long
# define ui unsigned int

# define pb push_back
# define pf push_front

# define vi vector < int >
# define vc vector < char >
# define vs vector < string >
# define vb vector < bool >
# define vd vector < D >
# define vll vector < ll >
# define vull vector < ull >
# define vld vector < ld >
# define PQ priority_queue

# define vvi vector < vector < int > >
# define vvb vector < vector < bool > >
# define vvc vector < vector < char > >
# define vvs vector < vs >
# define vvll vector < vector < ll > >
# define vvd vector < vector < D > >
# define vvld vector < vector < ld > >

# define all(v) (v).begin() , (v).end()
# define allrev(v) (v).rbegin() , (v).rend()
# define allcomp(v) v.begin() , v.end() , comp
# define allrevcomp(v) v.rbegin() , v.rend() , comp

# define pii pair < int , int >
# define pll pair < ll , ll >
# define pld pair < ld , ld >
# define pDD pair < D , D >

# define vpld vector < pld >
# define vpii vector < pii >
# define vpll vector < pll >
# define vpDD vector < pDD >

# define vvpii vector < vector < pii > >
# define F first
# define S second
# define mp make_pair

# define dist(a,b,p,q) sqrt((p-a)*(p-a) + (q-b)*(q-b))

# define pp(n) printf("%.10Lf",n);
# define line cout<<"\n";
# define fast ios_base::sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0);

string vow = "aeiou";
int month[] = {-1, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

const int dxhorse[] = {-2, -2, -1, -1, 1, 1, 2, 2};
const int dyhorse[] = {1, -1, 2, -2, 2, -2, 1, -1};

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

const ld pie = 3.1415926535897932384626 ;
const ll mod = 1e9 + 7 ;

/// Tip : If a and b are positive integers ; we may say - ceil (a/b) = 1 + floor ( (a-1)/b ) .

void solve ( int test_case )
{
    int n , W ;
    cin >> n >> W  ;

    const int N = 1e5 + 10 ;
    const ll inf = 1e11 + 3 ;

    vll dp ( N , inf ) ;
    dp[0] = 0 ;

    for ( int j = 0 ; j < n ; j ++ )
    {
        int w , val ;
        cin >> w >> val ;

        for ( int i = N - 1 ; i >= 0 ; i -- )
        {
            int indx = i + val ;
            if ( indx >= N ) C ;

            dp[indx] = min ( dp[indx] , dp[i] + w ) ;
        }
    }

    int ans = -100 ;

    for ( int i = 1 ; i < N ; i ++ )
    {
        if ( dp[i] <= W )
            ans = i ;
    }

    cout << ans ; line ;
}

int main()
{fast
    int t = 1;
    // cin >> t;

    for ( int i=1 ; i <= t ; i ++ ) solve ( i ) ;
    return 0;
}


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

using namespace std;

#define lli long long int
#define REP(i,s,l) for(lli i=s;i<l;i++)
#define DEBUG 0
#define INF (1LL<<50)
#define MOD 1000000007

signed main(){

	lli a,b;
	cin>>a>>b;

	cout<<((a*3+b)/2)<<endl;

	return 0;
}

Measured memory_bytes: 764
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		//int k = sc.nextInt();

		long count=0;

		if(n==m) {
			System.out.println(n*2);
		}else {
			System.out.println(Math.max(n, m)+Math.max(n, m)-1);
		}
	}
}




Measured memory_bytes: 21844
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main(){
    int n, k; cin >> n >> k;
    string s; cin >> s;
    vector<int> lens;
    if(s[0]=='0') lens.push_back(0);
    int l=1;
    for(int i=1; i<s.size(); ++i){
        if(s[i]==s[i-1]) ++l;
        else{
            lens.push_back(l);
            l=1;
        }
    }
    lens.push_back(l);
    if(s[n-1]=='0') lens.push_back(0);

    /*
    for(auto v : lens){
        cout << v << endl;
    }
    cout << "---------------" << endl;
    */

    int acc=0;
    for(int i=0; i<min((size_t)k*2+1, lens.size()); ++i){
        acc+=lens[i];
    }

    int ans=acc;
    //cout << acc << endl;
    for(int i=k*2+1; i<lens.size(); i+=2){
        acc-=lens[i-k*2]+lens[i-k*2-1];
        acc+=lens[i]+lens[i+1];
        //cout << acc << endl;
        ans=max(ans, acc);
    }

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


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

#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = (n)-1; i >= 0; i--)
using namespace std;
typedef long long ll;

const int INF = 1e9;
int n;

int main() {
  cin >> n;
  vector<ll> h(n);
  rep(i, n) cin >> h[i];
  ll ans = 0;
  ll cnt = 0;
  for (int i = 1; i < n; ++i) {
    if (h[i - 1] >= h[i]) cnt++;
    else {
      ans = max(ans, cnt);
      cnt = 0;
    }
  }
  ans = max(ans, cnt);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007 

ll a[501][501];
int main() {
	ll n,m,q;
	cin>>n>>m>>q;
	for(int i=0;i<m;i++){
		ll x,z;
		cin>>x>>z;
		x--;z--;
		a[x][z]++;
	}
	for(int i=0;i<n;i++){
		for(int j=i;j<n-1;j++){
			a[i][j+1]=a[i][j+1]+a[i][j];
		}
	}
	for(int i=0;i<q;i++){
		ll x,z,ans=0;
		cin>>x>>z;
		x--;z--;
		for(int j=x;j<n;j++){
			ans+=a[j][z];
		}
		cout <<ans<<endl;
	}
	return 0;
}

Measured memory_bytes: 2816
import sys

S = sys.stdin.readline().strip()
T = sys.stdin.readline().strip()

ls = len(S)
lt = len(T)
match = 0
for i in range(ls - lt + 1):
    tmp = 0
    for j in range(lt):
        if S[i+j] == T[j]:
            tmp += 1
    match = max(match, tmp)

print(lt - match)

Measured memory_bytes: 8988
#include<iostream>
#include<string>

using namespace std;

int main() {
	
	string A;
	int find = 0;
	
	while(cin >> A) {
		
		bool test = true;
		
		if(A.size() == 1)
			find++;
			
		else {
			
		for(int i=0;i<A.size()/2;i++) {
			
			if(A[i] != A[A.size()-1-i]) {
				
				test = false;
				break;
				
			}			
			
		}
			if(test)
				find++;
	}
}
		
		cout << find << "\n";
		
	return 0;
}


Measured memory_bytes: 3192
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define REP(i,n) FOR(i,0,n)
#define FORCLS(i,a,b) for(int i = (a); i <= (b); i++)
#define REPCLS(i,n) FORCLS(i,1,n)

using Int = long long int;
Int n,a,b;
#define NMAX 100005
Int x[NMAX];

void solve() {
    cin >> n >> a >> b;
    REP(i, n) cin >> x[i];
    Int h = 0;
    REP(i, n-1){
        h += min(a * (x[i+1] - x[i]),b);
    }
    cout << h << endl;
}

#ifdef DEBUG
#define MAIN hoge
#else
#define MAIN main
#endif

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


Measured memory_bytes: 1024
# include <bits/stdc++.h>
using namespace std;
namespace Base{
	# define mr make_pair
	typedef long long ll;
	typedef double db;
	const int inf = 0x3f3f3f3f, INF = 0x7fffffff;
	const ll  infll = 0x3f3f3f3f3f3f3f3fll, INFll = 0x7fffffffffffffffll;
	template<typename T> void read(T &x){
    	x = 0; int fh = 1; double num = 1.0; char ch = getchar();
		while (!isdigit(ch)){ if (ch == '-') fh = -1; ch = getchar(); }
		while (isdigit(ch)){ x = x * 10 + ch - '0'; ch = getchar(); }
	    if (ch == '.'){
	    	ch = getchar();
	    	while (isdigit(ch)){num /= 10; x = x + num * (ch - '0'); ch = getchar();}
		}
		x = x * fh;
	}
	template<typename T> void chmax(T &x, T y){x = x < y ? y : x;}
	template<typename T> void chmin(T &x, T y){x = x > y ? y : x;}
}
using namespace Base;

const int N = 130, L = 128;
char mp[N], q[N], mx[N][N], nxt[N];
int sum, cnt, n;
bool use[N];
int query(){
	printf("? ");
	int k = strlen(q + 1);
	for (int i = 1; i <= k; i++)
		printf("%c", mp[(int)q[i]]);
	cout << endl;
	int x; read(x);
	return x;
}

void mix(char *a, char *b){
	int lb = strlen(b + 1), now = 1, l = strlen(a + 1);
	memset(nxt, 0, sizeof(nxt));
	for (int i = 0; i <= l; i++){
		bool flag = true;
		while (now <= lb && flag){	
			flag = false;
			int k = strlen(nxt + 1), ths = k + (l - i);	
			memset(q, 0, sizeof(q));
			for (int j = 1; j <= k; j++) q[j] = nxt[j];
			q[k + 1] = b[now];
			for (int j = i + 1; j <= l; j++) q[now + j] = a[j];
			int x = query();
			if (x < sum - ths){
				flag = true;
				for (int j = 1; j <= k + 1; j++) nxt[j] = q[j];
				now++;
			}
		}
		if (i != l) nxt[strlen(nxt + 1) + 1] = a[i + 1]; 
	}
	for (int i = 1; i <= lb + l; i++)
		a[i] = nxt[i];
}

int main(){
	for (int i = 'a'; i <= 'z'; i++) mp[++cnt] = i;
	for (int i = 'A'; i <= 'Z'; i++) mp[++cnt] = i;
	for (int i = '0'; i <= '9'; i++) mp[++cnt] = i;
	for (int i = 1; i <= cnt; i++){
		for (int j = 1; j <= L; j++) q[j] = i;
		int x = query();
		if (x != L){
			n++;
			for (int j = 1; j <= L - x; j++) mx[n][j] = i;
			sum = sum + (L - x);
		}
	}
	for (int t = 1; t < n; t++){
		int id1, id2, mn1 = inf, mn2 = inf;
		for (int i = 1; i <= n; i++){
			if (use[i]) continue;
			int k = strlen(mx[i] + 1);
			if (k < mn1){
				mn2 = mn1, id2 = id1;
				mn1 = k, id1 = i;
			}
			else if (k < mn2) mn2 = k, id2 = i;
		}
		mix(mx[id1], mx[id2]);
		use[id2] = true;
	}
	
	for (int t = 1; t <= n; t++){
		if (!use[t]){
			int k = strlen(mx[t] + 1);
			printf("! ");
			for (int i = 1; i <= k; i++)
				printf("%c", mp[mx[t][i]]);
		//	puts("");
		}
	}
	cout << endl;
	return 0;
}



Measured memory_bytes: 3800
#include <bits/stdc++.h>
using namespace std;
int numar_cifre(int val)
{
    int nr=0;
    while(val!=0)
    {
        nr++;
        val=val/10;;
    }
    return nr;
}
struct republica
{
    int p,y,poz;
};
republica a[100001];
int v[100001],n,m;
char s[100001][15],ch;
inline bool cmp(const republica &a,const republica &b)
{
    return a.y<b.y;
}
int main()
{
    int i,nrcval,nrcp,val,j,nr,x,c;
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        cin>>a[i].p>>a[i].y;
        a[i].poz=i;
    }
    sort(a+1,a+m+1,cmp);
    for(i=1;i<=m;i++)
    {
        val=v[a[i].p]+1;
        v[a[i].p]++;
        nrcp=numar_cifre(a[i].p);
        for(j=1;j<=6-nrcp;j++)
        {
            s[a[i].poz][j]='0';
        }
        nr=6;
        x=a[i].p;
        while(x!=0)
        {
            c=x%10;
            ch=c+'0';
            s[a[i].poz][nr]=ch;
            nr--;
            x=x/10;
        }
        nrcval=numar_cifre(val);
        for(j=7;j<=12-nrcval;j++)
        {
            s[a[i].poz][j]='0';
        }
        nr=12;
        x=val;
        while(x!=0)
        {
            c=x%10;
            ch=c+'0';
            s[a[i].poz][nr]=ch;
            nr--;
            x=x/10;
        }
    }
    for(i=1;i<=m;i++)
        cout<<s[i]+1<<"\n";
    return 0;
}


Measured memory_bytes: 4480
H, W, K = map(int, input().split())
graph = list()
for i in range(H):
  graph.append(input())
  
ans = 0
for h in range(1<<H):
  for w in range(1<<W):
    hlist = list()
    wlist = list()
    for i in range(H):
      if(h>>i & 1):
        hlist.append(i)
    for j in range(W):
      if(w>>j & 1):
        wlist.append(j)
    cnt = 0
    for i in range(H):
      for j in range(W):
        if (not i in hlist) and (not j in wlist) and graph[i][j] == '#':
          cnt += 1
    #print(hlist, wlist, cnt)
    if(cnt == K):
      ans += 1
print(ans)

Measured memory_bytes: 68576
N,M=map(int,input().split())
A=[]
for i in range(M):
    P,Y=map(int,input().split())
    A.append([P,Y,i])

ans=[""]*M
A=sorted(A, key=lambda x: x[1])
A=sorted(A,key=lambda x:x[0])

now=A[0][0]
cnt=1
for i in range(M):
    pref=str(A[i][0])
    
    if A[i][0]!=now:
        cnt=1
    year=str(cnt)
    now=A[i][0]
    cnt+=1

    ans[A[i][2]]=pref.zfill(6)+year.zfill(6)

for i in range(M):
    print(ans[i])

Measured memory_bytes: 36700
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define rep2(i,a,b) for(ll i=a;i<=b;++i)
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep3(i,a,b) for(ll i=a;i>=b;i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pq priority_queue
#define pb push_back
#define eb emplace_back
#define vec vector<int>
#define vecll vector<ll>
#define vecpii vector<pii>
#define vec2(a,b) vector<vec>(a,vec(b))
#define vec2ll(a,b) vector<vecll>(a,vecll(b))
#define vec3(a,b,c) vector<vector<vec>>(a,vec2(b,c))
#define vec3ll(a,b,c) vector<vector<vecll>>(a,vec2ll(b,c))
#define fi first
#define se second
#define endl "\n"
#define all(c) begin(c),end(c)
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define lb(c,x) distance(c.begin(),lower_bound(all(c),x))
#define ub(c,x) distance(c.begin(),upper_bound(all(c),x))
#define MM " "
#define INF 100000000
using namespace std;
int in() {int x;cin>>x;return x;}
ll lin() {ll x;cin>>x;return x;}
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;}
template<class T> inline void print(pair<T,T> p){cout<<"("<<p.first<<","<<p.second<<") ";}
template<class T> inline void print(vector<pair<T,T>> v){for(auto e:v)print(e); cout<<endl;}
template<class T> inline void print(T v){for(auto e:v)cout<<e<<" ";cout<<endl;}





void go();

int main(){
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);cout<<fixed<<setprecision(15);
    int tc=1;
    // tc=in();
    while(tc--){
        go();
    }
    return 0;
}

ll MOD=998244353;
const int N=1100000;
 


ll inv[N],comb[N],prd[N],invprd[N];
void calc_inv(){
    inv[1]=1;
    rep2(i,2,N-1){
        inv[i]=inv[MOD%i]*(MOD-MOD/i)%MOD;
    }
    return;
}
void calc_product(){
    prd[0]=prd[1]=1;
    invprd[0]=invprd[1]=1;
    rep2(i,2,N-1){
        prd[i]=prd[i-1]*i%MOD;
        invprd[i]=inv[i]*invprd[i-1]%MOD;
    }
    return ;
}

void calc(){calc_inv();calc_product();}




ll dp[6100][2100];

void go(){
    int n=in();
    MOD=in();
    calc();
    dp[n*3][0]=prd[n*3];
    rep3(i,n*3,1){
        rep(j,n+1){
            if(i>=3){
                dp[i-3][j+1]=(dp[i-3][j+1]+dp[i][j]*inv[i]%MOD)%MOD;
            }
            if(i>=2){
                dp[i-2][j+1]=(dp[i-2][j+1]+dp[i][j]*inv[i]%MOD)%MOD;
            }
            dp[i-1][j]=(dp[i-1][j]+dp[i][j]*inv[i]%MOD)%MOD;
        }
    }
    ll ans=0;
    rep(i,n+1)ans=(ans+dp[0][i])%MOD;
    cout<<ans<<endl;
}

Measured memory_bytes: 128512
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <algorithm>
#include <cmath>
#include <iomanip>
 
 
int main()
{
    int n; std::cin >> n;
    std::map<std::string, int> pool;
    for(int i=0; i<n; i++)
    {
        std::string temp;
        std::cin >> temp;
        pool[temp]++;
    }
    
    int maxv = 0;
    for(const auto& x : pool)
    {
        int v = x.second;
        maxv = std::max(maxv, v);
    }

    for(auto it = pool.begin(); it!=pool.end(); it++)
    {
        if(it->second == maxv)
        {
            std::cout << it->first << std::endl;
        }
    }

    return 0;
}

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

using namespace std;
using ll = long long;
const double pi = acos(-1);
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
	REP(i, v.size()) { if (i)os << " "; os << v[i]; }return os;
}
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v) {
	REP(i, v.size()) { if (i)os << endl; os << v[i]; }return os;
}

const ll INF = LLONG_MAX;
ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;

#define int long long

inline void my_io() {

	std::ios::sync_with_stdio(false);

	std::cin.tie(0);

	cout << fixed << setprecision(16);

	//cout << setprecision(10) << scientific << ans << endl;
}

signed main() {
	string s, t;

	cin >> s >> t;

	ll ans = 0;

	REP(i, 3) {
		if (s[i] == t[i]) {
			ans++;
		}
	}

	cout << ans << endl;
}

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


class Program
{
    static void Main(string[] args)
    {
        int K = int.Parse(Console.ReadLine());
        string[] AB = Console.ReadLine().Split(' ');
        int A = int.Parse(AB[0]);
        int B = int.Parse(AB[1]);

        string answer = "NG";
        for(int i=A; i<=B; i++){
            if(i%K == 0){
                answer = "OK";
            }
        }
        Console.WriteLine(answer);
    }
}

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

void fnInput(int& rnTax8per, int& rnTax10per)
{
  cin >> rnTax8per >> rnTax10per;
}
  
int fnNonTaxKinGet(int nTax8per, int nTax10Per)
{
  vector<int> vnNonTaxKin(10);

  int nNonTax10per = nTax10Per * 10;
  for (int i = 0; i < vnNonTaxKin.size(); i++)
    vnNonTaxKin[i] = nNonTax10per++;

  for (int i = 0; i < vnNonTaxKin.size(); i++)
    if ((int)(vnNonTaxKin[i] * 0.08) == nTax8per)
      return vnNonTaxKin[i];

  return -1;
}
  
int main()
{
  int nTax8per, nTax10Per;

  fnInput(nTax8per, nTax10Per);
  cout << fnNonTaxKinGet(nTax8per, nTax10Per) << endl;

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string str;
  cin >> str;
 
  int counter = 1;
  bool is_not_easy = false;
  
  for (int i = 0; i < str.size(); i++){
    char c = str[counter-1];
    if (counter % 2 == 0){
      if (c != 'L' && c != 'U' && c != 'D'){
        is_not_easy = true;
      }
    }else{
      if (c != 'R' && c != 'U' && c != 'D'){
        is_not_easy = true;
      }
    }
    counter += 1;
  }
  
  if (is_not_easy){
  	cout << "No" << endl;
  }else{
  	cout << "Yes" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
from collections import deque
N=int(input())
S=list(map(int,list(input())))

RL=list(range(0,10))
LL=list(range(0,10))
ans=0
for x in RL:
    for i,c in enumerate(S):
        if c==x:
            x_i=i
            break
    else:continue
    for y in LL:
        for i,c in enumerate(S[::-1]):
            if c==y:
                y_i=N-i-1
                break
        else:continue
        if x_i<y_i:
            ans+=len(set(S[x_i+1:y_i]))
print(ans)

Measured memory_bytes: 3956
#include <vector>
#include <numeric>
#include <iostream>

using namespace std;
struct _ { ios_base::Init i; _() { ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL); } } _;

vector<long long> spf(1e7 + 1, 0);

int main() {

	long long n; cin >> n;

	iota(spf.begin(), spf.begin() + n + 1, 0);

	for (long long i = 2; i * i <= n; i++) {
		for (long long j = i * i; j <= n; j += i) spf[j] = min(spf[j], i);
	}

	long long ans = 0;

	for (long long i = 1; i <= n; i++) {
		long long x = i, cnt = 1;
		while (x != 1) {
			long long pfac = spf[x], temp = 0;
			while (x % pfac == 0) x /= pfac, temp++;
			cnt *= (temp + 1);
		}
		ans += (i * cnt);
	}

	cout << ans;


	return 0;
}

Measured memory_bytes: 81256
#include<iostream>
#include<string>
using namespace std;
int main(){
  string s,t;cin >> s >> t;bool ok = true;
  int n = t.size(),i,j;int als[26],alt[26];
  for(i=0;i<26;i++) als[i] = alt[i] = -1;
  for(i=0;i<n;i++){
    if(als[s[i]-'a'] >= 0 && als[s[i]-'a'] != t[i]-'a'){
      cout << "No" << endl;return 0;
    } else als[s[i]-'a'] = t[i]-'a';
    if(alt[t[i]-'a'] >= 0 && alt[t[i]-'a'] != s[i]-'a'){
      cout << "No" << endl;return 0;
    } else alt[t[i]-'a'] = s[i]-'a';
  }
  cout << "Yes" << endl;
}

Measured memory_bytes: 776
#include <bits/stdc++.h>
#define PI 3.1415926535897932
#define _GLIBCXX_DEBUG
using namespace std;
int main() {
  
  int a,b,c,d;
  cin>>a>>b>>c>>d;
  
  int x=c-a;
  int y=d-b;
  
  cout<<c-y<<" "<<d+x<<" "<<a-y<<" "<<b+x<<endl;
}


Measured memory_bytes: 3604
N=int(input())
L=list(map(int,input().split()))
c=0
for k in range(N):
    for j in range(k):
        if L[j]!=L[k]:
            for i in range(j):
                if L[i]!=L[j] and L[i]!=L[k] and L[i]+L[j]>L[k] and L[j]+L[k]>L[i] and L[i]+L[k]>L[j]:
                    c+=1
print(c)

Measured memory_bytes: 9188
n,a,b = map(int,input().split())
sum = 0
for i in range(n):
	s = i+1
	x = s%10
	y = ((s-x)%100)
	z = ((s-x-y)%1000)
	w = ((s-x-y-z)%10000)
	q = ((s-x-y-z-w)%100000)
	t = x+y//10+z//100+w//1000+q//10000
	if a<=t<=b:
		sum += s
print(sum)

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

/*
1≤N≤2×105
0≤K≤2×105
1≤Hi≤109
All values in input are integers.
Input
Input is given from Standard Input in the following format:

N K
H1 … HN

*/
unsigned long Fennec_fight(vector<int>& monsters, int& K)
{
   if(monsters.size()<=K) return 0;
   sort(monsters.begin(),monsters.end(),[](int& A, int& B){ return A>B;});
   unsigned long strikes=0;
   for(int i=K; i<monsters.size();i++) 
   {
   		strikes+=monsters[i];
   }
   return strikes;
   
}

int main()
{
   int K, N,m;
   vector<int> monsters(N);
   cin>> N >> K;
   for(int i=0; i<N;i++) 
   {
   	cin>>m;
   	monsters.push_back(m);
   }
   
  cout<< (unsigned long)Fennec_fight(monsters,K)<<endl;
  return 0;

}

Measured memory_bytes: 34944
/*
      author : nishi5451
      created: 12.08.2020 11:39:54
*/

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


int main(){
    int h1,m1,h2,m2,k;
    cin >> h1 >> m1 >> h2 >> m2 >> k;
    int ans = (h2-h1-1)*60+(m2+60-m1);
    cout << ans-k << endl;
    return 0;
}


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

using namespace std;

const int maxn = 1e5 + 5;

int a[maxn];
int main() {
	int n;
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
	int cnt = 0;
	for(int i = 1; i <= n - 1; i++) {
		if(a[i] == i) {
			if(a[i + 1] == i + 1) {
				swap(a[i], a[i + 1]);
				i++;
			} else {
				swap(a[i], a[i + 1]);
			}
			cnt++;
		}
	}
	if(a[n] == n) cnt++;
	cout << cnt << endl;
	return 0;
}

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

using ll = long long;
using vint = vector<int>;
using vvint = vector<vint>;
using pint = pair<int, int>;
using vpint = vector<pint>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
#define repi(n) for (int i = 0; i < n; i++)
#define repj(n) for (int j = 0; j < n; j++)
#define repk(n) for (int k = 0; j < n; k++)
#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, a, b) for (int i = a; i < b; i++)
#define repv(itr) for (auto&& v : itr)
#define swap(x, y)    \
  {                   \
    auto ___temp = x; \
    x = y;            \
    y = ___temp;      \
  }

const int dx[] = {-1, 0, 0, 1, -1, -1, 1, 1};
const int dy[] = {0, -1, 1, 0, -1, 1, -1, 1};
template <typename T>
T minptr(T begin, T end) {
  T re = begin;
  for (T i = begin + 1; i != end; i++) {
    if (*i < *re) re = i;
  }
  return re;
}
template <typename T>
T maxptr(T begin, T end) {
  T re = begin;
  for (T i = begin + 1; i != end; i++) {
    if (*i > *re) re = i;
  }
  return re;
}
int __vmax(int x) {
  return INT_MAX;
}
double __vmax(double x) {
  return 1e+300;
}
ll __vmax(ll x) {
  return LLONG_MAX;
}
int __vmin(int x) {
  return INT_MIN;
}
double __vmin(double x) {
  return -1e+300;
}
ll __vmin(ll x) {
  return LLONG_MIN;
}
template <typename T>
vector<T> lis(T begin, T end, bool allowequal = false, bool lds = false) {
  using V = typename iterator_traits<T>::value_type;
  int n = end - begin;
  vector<V> a(n, lds ? __vmin(*begin) : __vmax(*begin));
  vector<int> id(n);
  if (lds && allowequal) {
    for (int i = 0; i < n; i++) {
      id[i] = n - 1 -
              (lower_bound(a.rbegin(), a.rend(), begin[i]) - 1 - a.rbegin());
      a[id[i]] = begin[i];
    }
  } else if (lds) {
    for (int i = 0; i < n; i++) {
      id[i] = n - 1 -
              (upper_bound(a.rbegin(), a.rend(), begin[i]) - 1 - a.rbegin());
      a[id[i]] = begin[i];
    }
  } else if (allowequal) {
    for (int i = 0; i < n; i++) {
      id[i] = upper_bound(a.begin(), a.end(), begin[i]) - a.begin();
      a[id[i]] = begin[i];
    }
  } else {
    for (int i = 0; i < n; i++) {
      id[i] = lower_bound(a.begin(), a.end(), begin[i]) - a.begin();
      a[id[i]] = begin[i];
    }
  }
  int m = *maxptr(id.begin(), id.end());
  vector<T> re(m + 1);
  for (int i = n - 1; i >= 0; i--) {
    if (id[i] == m) re[m--] = begin + i;
  }
  return re;
}
template <typename T>
T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
}

int main() {
  int a, b, c, d, e, k;
  cin >> a >> b >> c >> d >> e >> k;
  cout << (e - a > k ? ":(" : "Yay!") << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <complex>
#include <string>
#include <sstream>
#include <limits>
#include <numeric>
#include <algorithm>
#include <functional>

using namespace std;

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

	string N;
	cin >> N;

	bool check = true;
	for (int i = 1; i < N.size(); i++)
	{
		if (N[i] != '9')
		{
			check = false;
			break;
		}
	}

	if (check)
	{
		cout << (N[0] - '0') + (N.size() - 1) * 9;
	}
	else
	{
		cout << (N[0] - '0') - 1 + (N.size() - 1) * 9;
	}

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<string>
//#include <boost/math/common_factor.hpp> 
using namespace std;
 
typedef long long ll;
#define endl "\n"
#define pb push_back
#define fp(i,a,b) for(int i=a;i<b;++i)
#define fq(i,a,b) for(int i=a;i<=b;++i)
#define fst ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)


int main() {
    ll a,b,c,d;
    cin>>a>>b>>c>>d;
    cout<<max({a*c,b*d,a*d,b*c});
}

Measured memory_bytes: 3648
#include<stdio.h>
#define INF 10000000
int min(int,int);
void warshall_floyd(void);

int graph[21][21],visit[21][21];
int V;

int main(void){
  int i,j,road,a,b,c,d;
  int x1,x2,y1,y2;
  for(i=0;i<21;i++){
    for(j=0;j<21;j++){
      graph[i][j]=INF;
      visit[i][j]=0;
    }
  }
  
  scanf("%d",&V);
  scanf("%d",&road);
  for(i=0;i<road;i++){
    scanf("%d,%d,%d,%d",&a,&b,&c,&d);
    graph[a][b]=c;
    graph[b][a]=d;
  }
  scanf("%d,%d,%d,%d",&x1,&x2,&y1,&y2);
  warshall_floyd();

    printf("%d\n",y1-(graph[x1][x2]+graph[x2][x1])-y2);

  return 0;
}

int min(int x,int y){
  return (x>y)?y:x;
}

void warshall_floyd(){
  int i,j,k;
  for(k=0;k<=V;k++)
    for(i=0;i<=V;i++)
      for(j=0;j<=V;j++)
	graph[i][j]=min(graph[i][j],graph[i][k]+graph[k][j]);
}

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

int main(){

  string _S, T, ans_S;
  cin >> _S >> T;
  bool exist = false;
  int len_s = _S.length(), len_t = T.length();

  for (int i = len_s - len_t; i >= 0; --i){
    for (int j = 0; j < len_t; ++j){
      if (_S[i + j] != '?' && _S[i + j] != T[j]) break;
      if (j == len_t - 1){
        ans_S = _S.replace(i, len_t, T);
        exist = true;
      }
    }
    if (exist) break;
  }

  if (!exist){
    cout << "UNRESTORABLE" << endl;
  }else{
    for (int i = 0; i < len_s; ++i){
      if (ans_S[i] == '?') ans_S[i] = 'a';
    }
    cout << ans_S << endl;
  }  
}

Measured memory_bytes: 256
#include <bitset>
#include <cmath>
#include <cstdint>
#include <iostream>
#include <vector>

using namespace std;

int Count(const vector<string>& grid, const bitset<6>& rows, const bitset<6>& cols) {
  int result = 0;
  for (size_t h = 0; h < grid.size(); ++h) {
    if (rows.test(h)) {
      continue;
    }
    for (size_t w = 0; w < grid[0].size(); ++w) {
      if (!cols.test(w) && grid[h][w] == '#') {
        ++result;
      }
    }
  }
  return result;
}

int main() {
  int H, W, K;
  cin >> H >> W >> K;
  vector<string> grid(H);
  for (int h = 0; h < H; ++h) {
    cin >> grid[h];
  }
  int result = 0;
  for (int h = 0, end_h = 2 << H-1; h < end_h; ++h) {
    bitset<6> rows(h);
    for (int w = 0, end_w = 2 << W-1; w < end_w; ++w) {
      bitset<6> cols(w);
      if (Count(grid, rows, cols) == K) {
        ++result;
      }
    }
  }
  cout << result << endl;
  
  return 0;
}


Measured memory_bytes: 3600
# ABC103-D

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

ab.sort(key=lambda x: x[1])

ans = 1
bridge = ab[0][1] - 1

for pair in ab:
    if bridge < pair[0]:
        bridge = pair[1] - 1
        ans += 1

print(ans)


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

typedef long lint;
typedef long long llint;

// static const int MAX = 1e6;
// static const int NIL = -1;
// static const ll INF = 1<<21;
// static const ll MOD = 1e9 + 7;

bool compPair(const pair<int, int>& arg1, const pair<int, int>& arg2) { return arg1.first > arg2.first; }
template<class T> void chmax(T& a, T b) { if (a < b) { a = b; } }
template<class T> void chmin(T& a, T b) { if (a > b) { a = b; } }


int main(void) {
    llint n, m;
    cin >> n >> m;

    llint tmp = 1, ans=1, tmpmax;
    tmpmax = m/n;

    queue<llint> div;
    
    while(tmp*tmp<=m) {
        if(m%tmp==0) {
            div.push(tmp);
            div.push(m/tmp);
        }
        tmp++;
    }

    llint d;
    while(!div.empty()) {
        d = div.front(); div.pop();
        if(d<=tmpmax) ans = max(ans, d);
    }

    cout << ans << endl;

    return 0;
}


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

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

    int start, end, res;

    if (A < C) {
        start = C;
    } else {
        start = A;
    }

    if (B < D) {
        end = B;
    } else {
        end = D;
    }

    res = end - start;

    if (res < 0) res = 0;

    cout << res << endl;

    return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using static System.Console;
namespace AtCoder.AGC011
{
    static class Colorful_Creatures
    {
        public static void Main()
        {
            var n = long.Parse(ReadLine().Trim());
            var creatures = ReadLine().Trim().Split(' ').Select(i => long.Parse(i)).OrderBy(i => i).ToArray();
            WriteLine(solve(creatures));
        }
        static long solve(long[] creatures)
        {
            var sumCreatures = new long[creatures.Length];
            for (var i = 1; i < sumCreatures.Length; ++i)
                sumCreatures[i] = sumCreatures[i - 1] + creatures[i - 1];
            for (var i = 1; i <= creatures.Length; ++i)
            {
                if (creatures[creatures.Length - i]  > 2 * sumCreatures[sumCreatures.Length - i]) return i;
            }
            return creatures.Length;
        }
    }
}


Measured memory_bytes: 30576
#include<stdio.h>

int main(){
    int N, A;
    char str[100];

    scanf("%d %d", &N, &A);
    scanf("%s", str);

    if(str[A-1] == 'A'){
        str[A-1] = 'a';
    }
    if(str[A-1] == 'B'){
        str[A-1] = 'b';
    }
    if(str[A-1] == 'C'){
        str[A-1] = 'c';
    }

    printf("%s", str);

    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define pb push_back
#define pair pair<int,int>
#define ll long long
#define f first
#define se second
using namespace std;
double pi=acos(-1.0);
int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int n;
  cin>>n;
  int v[n][3];
  for(int i=0;i<n;i++)
    for(int j=0;j<3;j++)
      cin>>v[i][j];
  int dp[n][3];
  memset(dp,0,sizeof(dp));
  dp[0][0]=v[0][0];dp[0][1]=v[0][1];dp[0][2]=v[0][2];
  for(int i=1;i<n;i++)
    for(int j=0;j<3;j++)
      for(int k=0;k<3;k++)
        if(k!=j)
        dp[i][j]=max(dp[i][j],dp[i-1][k]+v[i][j]);
  cout<<max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2]));
}

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

using namespace std;

template <typename T,typename E>
struct SegmentTree{
  typedef function<T(T,T)> F;
  typedef function<T(T,E)> G;
  int n;
  F f;
  G g;
  T d1;
  vector<T> dat;
  SegmentTree(int n_,F f,G g,T d1,
	      vector<T> v=vector<T>()){
    this->f=f;
    this->g=g;
    this->d1=d1;
    init(n_);
    if(n_==(int)v.size()) build(n_,v);
  }
  void init(int n_){
    n=1;
    while(n<n_) n*=2;
    dat.clear();
    dat.resize(2*n-1,d1);
  }
  void build(int n_, vector<T> v){
    for(int i=0;i<n_;i++) dat[i+n-1]=v[i];
    for(int i=n-2;i>=0;i--)
      dat[i]=f(dat[i*2+1],dat[i*2+2]);
  }
  void update(int k,E a){
    k+=n-1;
    dat[k]=g(dat[k],a);
    while(k>0){
      k=(k-1)/2;
      dat[k]=f(dat[k*2+1],dat[k*2+2]);
    }
  }
  T query(int a,int b,int k,int l,int r){
    if(r<=a||b<=l) return d1;
    if(a<=l&&r<=b) return dat[k];
    T vl=query(a,b,k*2+1,l,(l+r)/2);
    T vr=query(a,b,k*2+2,(l+r)/2,r);
    return f(vl,vr);
  }
  T query(int a,int b){
    return query(a,b,0,0,n);
  }
};

int main(){
    int n, m;
    cin >> n >> m;
    int64_t INF = 1e17;
    vector<array<int, 3>> Q(m);

SegmentTree<int64_t,int64_t> rmq(n,
			   [](int64_t a,int64_t b){return min(a,b);},
			   [](int64_t a,int64_t b){return b;},
			   INF);

    
    for (int i = 0; i < m; i++){
        cin >> Q[i][0] >> Q[i][1] >> Q[i][2];
    }

    sort(Q.begin(), Q.end());


    rmq.update(0, 0);
    for (int i = 0; i < m; i++){
        int64_t l = Q[i][0] - 1, r = Q[i][1] - 1, c = Q[i][2];
        int64_t a = rmq.query(r, n);
        int64_t s = rmq.query(l, n);
        rmq.update(r, min(a, s + c));
    }

    int64_t ans = rmq.query(n - 1, n);
    cout << (ans == INF ? -1 : ans) << endl;
}

Measured memory_bytes: 3456
#include <stdio.h>
#include <stdlib.h>
#define rep(i,l,r)for(int i=(l);i<(r);i++)

typedef struct tuple{int x,y;}T;

int qidx[500010];
T query[500010];//[x,y]
int qcmp(const void*p,const void*q){
	if(query[*(int*)p].y<query[*(int*)q].y)return -1;
	if(query[*(int*)p].y>query[*(int*)q].y)return 1;
	return 0;
}

//セグ木ここから
//*
//↓ここを変える
typedef struct atai{int a;}atai;
atai xx(atai x,atai y){
	atai r;
	r.a=x.a+y.a;
	return r;
}
atai aid={0};
//↑ここを変える

int segNUM;
atai *segN,*seg;
void seguse(int n){
	segN=(atai*)calloc(2*n,sizeof(atai));
	segNUM=n;
	seg=segN+segNUM;
	rep(i,1,2*segNUM)segN[i]=aid;
}
//seg[]に値を与えてから初期化
void seginit(){for(int node=segNUM-1;node;node--)segN[node]=xx(segN[node*2],segN[node*2+1]);}
void segupdate(int node,atai x){
	//seg[node]をxに更新
	node+=segNUM;
	segN[node]=x;
	while(node/=2)segN[node]=xx(segN[node*2],segN[node*2+1]);
}

atai segcalcsub(int l,int r,int k,int cl,int cr){
	if(l>=r)return aid;
	//完全に含むとき
	if(l<=cl&&cr<=r)return segN[k];

	int cm=(cl+cr)/2;
	//左側だけ
	if(r<=cm)return segcalcsub(l,r,2*k  ,cl,cm);
	//右側だけ
	if(cm<=l)return segcalcsub(l,r,2*k+1,cm,cr);
	//両方
	return xx(segcalcsub(l,r,2*k,cl,cm),segcalcsub(l,r,2*k+1,cm,cr));
}
atai segcalc(int l,int r){return segcalcsub(l,r,1,0,segNUM);}
//セグ木ここまで
//*/


int diff[500010];//色c[i]の右端がdiff[i]からiに変わった
int c[500010];
int pos[500010];
int ans[500010];
int main(){
	int n,q;
	scanf("%d%d",&n,&q);
	rep(i,1,n+1)scanf("%d",c+i);
	rep(i,0,q)scanf("%d%d",&query[i].x,&query[i].y);
	
	//クエリをrの昇順にソート
	rep(i,0,q)qidx[i]=i;
	qsort(qidx,q,sizeof(int),qcmp);
	
	//右端を構築
	rep(i,1,n+1){
		diff[i]=pos[c[i]];
		pos[c[i]]=i;
	}
	
	//クエリに答える
	int*qi=qidx;
	seguse(1<<19);
	rep(r,1,n+1){
		atai x={1};
		segupdate(r,x);
		segupdate(diff[r],aid);
		while(qidx-qi<q&&query[*qi].y==r){
			ans[*qi]=segcalc(query[*qi].x,query[*qi].y+1).a;
			qi++;
		}
	}
	rep(i,0,q)printf("%d\n",ans[i]);
}

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

int main(){
  int N,alice=0,bob=0;
  cin >> N;
  vector <int> card(N);
  for (int i=0;i<N;i++){
    cin >> card.at(i);
  }
  sort(card.begin(),card.end());
  reverse(card.begin(),card.end());
  
  for(int i=0;i<N;i++){
    if(i%2==0)
      alice+=card.at(i);
    else
      bob+=card.at(i);
  }
  cout << alice-bob<<endl;
}

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

typedef long long ll;
using namespace std;
bool comp(string v1, string v2)
{
	return (strlen(v1.c_str()) < strlen(v2.c_str()));
}
unsigned long long power(unsigned long long a, unsigned long long b)
{
	unsigned long long pow = 1;
	while (b)
	{
		if (b & 1)
		{
			pow = pow * a;
			--b;
		}
		a = a * a;
		b = b / 2;
	}
	return pow;
}

bool is2s(ll a)
{
	return (ceil(log2(a)) == floor(log2(a)));
}


int main()
{

	ll l, n;
	vector<string>v;
	cin >> n >> l;
	for (ll i = 0; i < n; i++)
	{
		string s;
		cin >> s;
		v.push_back(s);
	}
	sort(v.begin(), v.end());
	for (ll i = 0; i < n; i++)
	{
		cout << v[i];
	}
	cout << endl;
	v.clear();
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <sstream>
#include <cmath>

using namespace std;

int main(int argc, const char * argv[]) {
    int N, Q; cin >> N >> Q;
    string S; cin >> S;
    vector<int> indices;
    int prev_a = -1;
    for (int i = 0; i < N; i++) {
        if (S[i] == 'A') {
            prev_a = i;
        } else if (S[i] == 'C' && prev_a >= 0) {
            indices.push_back(prev_a);
            prev_a = -1;
        } else {
            prev_a = -1;
        }
    }
    string ret = "";
    stringstream ss(ret);
    for (int i = 0; i < Q; i++) {
        int l, r;
        cin >> l >> r;
        
        auto l_iter = lower_bound(indices.begin(), indices.end(), l - 1);
        auto r_iter = lower_bound(indices.begin(), indices.end(), r - 1);
        ss << r_iter - l_iter << endl;
    }
    cout << ss.str() << endl;

    return 0;
}


Measured memory_bytes: 2612
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_map>
#include <cmath>

using namespace std;

typedef long long int int64;

int main(int argc, char **argv)
{
    int64 a, b, c;
    cin >> a >> b >> c;
    if (c <= a + b) cout << "No" << endl;
    else {
        int64 ans = (c * c) + (a + b) * (a + b) - 2 * c * (a + b) - 4 * a * b;
        if (ans > 0) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}


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

using namespace std;

#define rep(i,n) for(int i=0;i<(n);i++)
#define repa(i,a,n) for(int i=(a);i<(n);i++)
#define rrep(i,n) for(int i=n;i>=0;i--)
#define rrepa(i,a,n) for(int i=n;i>=(a);i--)
#define all(a) (a).begin(),(a).end()
#define MOD 1000000007
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
#define vc vector

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<int,int> pi;

int main(){

    int k,x;cin>>k>>x;

    if(500*k>=x)cout<<"Yes\n";
    else cout<<"No\n";

    return 0;

}

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

int64_t ggd(int64_t num1, int64_t num2) {
  int64_t a, b;
  if (num1 > num2) {
    a = num1;
    b = num2;
  } else {
    a = num2;
    b = num1;
  }

  int64_t r = a % b;
  while (r != 0) {
    a = b;
    b = r;
    r = a % b;
  }

  return b;
}

int64_t lcm(int64_t num1, int64_t num2) {
  return num1 * num2 / ggd(num1, num2);
}

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

  int64_t ans = lcm(a, b);
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
typedef long long ll;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
int n, m, k;
ll work(int n, int m) {
	ll ans = 0;
	for (int i = 0; i <= n - 2; i++)
	for (int j = 1; j <= m - 1 && i * j <= 2 * k + m; j++) {
		int tmp = 2 * k + __gcd(i, m) - i * j - 2;
		if (tmp >= 0) {
			int limit = min(n - 1 - i, tmp / m + 1);
			ans += (limit - (m * limit - __gcd(limit, j) - __gcd(limit + i, m - j) > tmp)) * (1 + (i != 0));
		}
	}
	return ans;
}
int main() {
	read(n), read(m), read(k);
	cout << work(n, m) * 2 + work(m, n) * 2 << endl;
	return 0;
}


Measured memory_bytes: 3636
/*
author: shah_entrance
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
  ll n,a,b;
  cin>>n>>a>>b;
  cout<<min(a,b)<<" ";
  if((a+b)>n)
    cout<<(a+b)-n<<endl;
  else
    cout<<"0"<<endl;
  return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

class Main{
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int a=sc.nextInt();
		int b=sc.nextInt();

		if(a<=8 && b<=8) {
			System.out.println("Yay!");
		}
		else {
			System.out.println(":(");
		}
	}
}

Measured memory_bytes: 22996
#include <bits/stdc++.h>
#define rep(i, n) for(int i= 0; i < (n); i++)
using ll= long long int;
using namespace std;
ll mod= 1e9 + 7;



int main() {
  int k,s;
  cin >> k >> s;
  ll ans=0;
  for(int x=0;x<=k;x++){
    for(int y=0;y<=k;y++){
      if(s-x-y<=k && s-x-y>=0)ans++;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
class UnionFind():
    def __init__(self, n):
        self.par = []
        for i in range(n+1):
            self.par.append(i)

    def find(self, x):
        if(self.par[x] == x):
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def same(self,x, y):
        return self.find(x) == self.find(y)

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if(x == y) :
            return
        self.par[x] = y




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

uf = UnionFind(n);

for _ in range(m):
    x, y = map(int, input().split())
    uf.union(x, y)


count = 0
for index in range(n):
    start = index + 1
    to = p[index]
    if uf.same(start, to):
        count += 1
print(count)


Measured memory_bytes: 14452
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  int a = n/1000;
  int b = n%1000/100;
  int c = n%100/10;
  int d = n%10;
  //  cout << a << b << c << d <<endl;
  if(a == b && a == c){
      cout << "Yes" << endl;
  }else if(b == c && b == d){
      cout <<"Yes"<<endl;
  }else{
    cout <<"No"<<endl;
  }
}

Measured memory_bytes: 256