akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
string S;
int a[100000];
signed main()
{
	ios_base::sync_with_stdio(false);
	int N;	cin >> N;
	int L = 0,R = N - 1,mid;
	int T = 0;
	// check L
	T++;
	cout << L << endl << flush;
	cin >> S;
	if(S[0] == 'M')
	{
		a[L] = -1;
	}
	else if(S[0] == 'F')
	{
		a[L] = 1;
	}
	else
	{
		//is Vacant
		exit(0);
	}
	// check R
	T++;
	cout << R << endl << flush;
	cin >> S;
	if(S[0] == 'M')
	{
		a[R] = -1;
	}
	else if(S[0] == 'F')
	{
		a[R] = 1;
	}
	else
	{
		//is Vacant
		exit(0);
	}

	// Checking by Binary Search
	while(L + 1 < R && T < 21)
	{
		T++;
		mid = (L + R)/2;
		cout << mid << endl << flush;
		cin >> S;
		if(S[0] == 'M')
		{
			a[mid] = -1;
		}
		else if(S[0] == 'F')
		{
			a[mid] = 1;
		}
		else
		{
			//is Vacant
			exit(0);
		}
		//
		if((R - mid - 1)&1){
            if(a[mid] == a[R]){
                R = mid;
            }
            else{
                L = mid;
            }
        }
        else{
            if(a[R] != a[mid]){
                R = mid;
            }
            else{
                L = mid;
            }
        }
	}
}

Measured memory_bytes: 980
#include "bits/stdc++.h"
#define REP(i, n) for(int i = 0; i < int(n); i++)
#define FOR(i,n,m) for(int i = int(n); i < int(m); i++)
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 6;
const ll LLINF = 1e18 + 1;

// 0-indexedとして使う
// 実装は1-indexed
template< typename T >
struct BinaryIndexedTree {
    std::vector< T > data;

    BinaryIndexedTree(int sz) {
        data.assign(++sz, 0);
    }

    // [0,k]
    inline T sum(int k) {
        T ret = 0;
        for (++k; k > 0; k -= k & -k) ret += data[k];
        return (ret);
    }

    // [left,right]
    inline T sum(int left, int right) {
        return sum(right) - sum(left - 1);
    }

    // k番目にxを加算
    // 負の数も可
    inline void add(int k, T x) {
        for (++k; k < data.size(); k += k & -k) data[k] += x;
    }

    // k番目の値 0-indexed
    // 値 = index, 個数 = data[index]
    // 0がdata[0]個, 1がdata[1]個...
    int get(ll k) {
        ++k;
        int res = 0;
        int N = 1; while (N < (int)data.size()) N *= 2;
        for (int i = N / 2; i > 0; i /= 2) {
            if (res + i < (int)data.size() && data[res + i] < k) {
                k = k - data[res + i];
                res = res + i;
            }
        }
        return res + 1;
    }

    void print() {
        std::cout << "[ ";
        for (int i = 0; i < data.size() - 1; i++) {
            std::cout << sum(i, i);
            if (i < data.size() - 2) cout << ", ";
        }
        std::cout << " ]" << endl;
    }
};

int main() {
    int n, q; cin >> n >> q;
    BinaryIndexedTree<ll> bit(n);
    REP(i, q) {
        int com, x, y; scanf("%d %d %d", &com, &x, &y);
        if (com == 0) bit.add(x-1, y);
        else printf("%lld\n", bit.sum(x-1,y-1));
    }
    return 0;
}


Measured memory_bytes: 3604
/************************************
/ AUTHOR : YATHARTH GOSWAMI         /  
/ ALIAS : hacker_yg                 /
/ INSTITUTE : IIT Kanpur            /
************************************/
//          TEMPLATE                //

#include <bits/stdc++.h>

#define ll long long
#define MOD 1000000007
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define PI 3.14159265359

using namespace std;

/*ll powMod(ll a, ll y)
{
    ll ans = 1;
    
    while (y > 0) 
    { 
        if (y & 1) 
            ans = (ans*a) % MOD; 
  
        y = y>>1;
        a = (a*a) % MOD; 
    } 
    return ans;
}*/

/*ll modInv(ll a)
{
    return powMod(a, MOD-2);	
}*/

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




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

int main(){
	int b1,b2,b3,i ;
	cin >> b1 >> b2 >> b3;
	b1 = b1*7 + b2*3 + b3;
	if(b1 == 7){ cout << "Close" <<endl;}
	if(b1 == 3){ cout << "Close" <<endl;}
	if(b1 == 10){ cout << "Open" <<endl;}
	if(b1 == 1){ cout << "Open" <<endl;}
	if(b1 == 0){ cout << "Close" <<endl;}
	
	return 0;
	}

Measured memory_bytes: 1156
N,C=gets.split(" ").map &:to_i
I=N.times.map{gets.split(" ").map &:to_i}
M,S,r,I[N]=[[0,0]],[0],0,[C,0]
I.each_with_index{|v,i|S[i+1]=S[i]+v[1];M[i+1]=[S[i+1]-v[0],M[i][0]].max,[S[i+1]-2*v[0],M[i][1]].max}
(0..N).map{|i|o=S[N]-S[i];r=[r,o+M[i][0]-2*(C-I[i][0]),o+M[i][1]-C+I[i][0]].max}
puts r

Measured memory_bytes: 18476
#include<stdio.h>

int main(void)
{
 	int a, b;
	int d, r;
	double f;
	
	
	scanf("%d %d", &a, &b);
	
	//?¨????
	d = a / b;
	r = a % b;
	f = double(a) / b;
	
	printf("%d %d %f\n", d, r, f);
	
	return 0;
   
}

Measured memory_bytes: 2660
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author EigenFunk
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        BNiceShopping solver = new BNiceShopping();
        solver.solve(1, in, out);
        out.close();
    }

    static class BNiceShopping {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int A = in.nextInt();
            int B = in.nextInt();
            int M = in.nextInt();
            int[] as = new int[A];
            int minA = Integer.MAX_VALUE;
            for (int i = 0; i < A; i++) {
                as[i] = in.nextInt();
                minA = Math.min(as[i], minA);
            }
            int[] bs = new int[B];
            int minB = Integer.MAX_VALUE;
            for (int i = 0; i < B; i++) {
                bs[i] = in.nextInt();
                minB = Math.min(bs[i], minB);
            }
            int min = minA + minB;
            for (int i = 0; i < M; i++) {
                int x = in.nextInt();
                int y = in.nextInt();
                int c = in.nextInt();
                min = Math.min(as[x - 1] + bs[y - 1] - c, min);
            }
            out.println(min);
        }

    }
}



Measured memory_bytes: 132552
#include <bits/stdc++.h>
using namespace std;
#include <iostream>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <math.h>
#include <sstream>
#include <numeric>
#include <cctype>
#include <bitset>
#include <cassert>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define SIZE 100005
#define INF 1000000000000000LL
using pint = pair<int,int>;
using vec = vector<int>;
using ll=long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    ll n; cin>>n;
    vll b(n);
    rep(i,n-1) cin>>b[i];

    ll sum=b[0]+b[n-2];
    rep(i,n-2){
        sum+=min(b[i],b[i+1]);
    }
    cout<<sum<<endl;
    }

Measured memory_bytes: 3616
n = int(input())
lis = list(map(int, input().split()))
dp = [0 for _ in range(n)]
for i,d in enumerate(dp):
    if i == 0:
        continue
    if i == 1:
        dp[1] = abs(lis[1]-lis[0])
        continue
    dp[i] = min((dp[i-2]+abs(lis[i-2]-lis[i])),(dp[i-1]+abs(lis[i-1]-lis[i])))
#print(dp)
print(dp[-1])

Measured memory_bytes: 13980
#define _USE_MATH_DEFINES
#include <math.h>
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <algorithm>

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

using namespace std;
typedef long long ll;

int main() {

    ll N;
    cin >> N;
    ll A[N];
    ll B[N];
    rep(i,N){
        cin >> A[i];
        B[i] = A[i];
    }
    sort(B,B+N);
    rep(i,N){
        if(A[i]!=B[N-1]) cout << B[N-1] << endl;
        else cout << B[N-2] << endl;
    }
    return 0;
}


Measured memory_bytes: 4736
def solve():
    N, M = map(int, input().split())
    edges = [[] for _ in [0] * N]
    for _ in [0] * M:
        a, b = map(int, input().split())
        edges[a].append(b)
        edges[b].append(a)
    for v in sorted(get_lowlink(edges, M)[1]):
        print(v)


def get_lowlink(edges, edge_num):
    import sys
    sys.setrecursionlimit(10**7)

    n = len(edges)
    order = [-1] * n
    low = [float("inf")] * n
    bridges = []
    articulations = [0] if edge_num == n-1 and len(edges[0]) > 1 else []
    append_bridge, append_articulation = bridges.append, articulations.append

    def dfs(v, prev, k):
        order[v] = low[v] = k

        is_articulation = False
        for dest in edges[v]:
            if order[dest] == -1:
                dfs(dest, v, k + 1)
                if low[v] > low[dest]:
                    low[v] = low[dest]
                if order[v] < low[dest]:
                    append_bridge((v, dest))
                is_articulation |= order[v] <= low[dest]

            elif dest != prev and low[v] > order[dest]:
                low[v] = order[dest]

        if v > 0 and is_articulation:
            append_articulation(v)

    dfs(0, 0, 0)
    return bridges, articulations


if __name__ == "__main__":
    solve()


Measured memory_bytes: 21604
#include <iostream>
#include <istream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
//#include <unordered_map>
#include <cstring>
#include <string.h>
#include <iomanip>
#include <queue>
#include <stack>
#include <list>
#include <sstream>
//#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld;

#define ALL(V) V.begin(), V.end()
#define SZ(V) (int)V.size()
#define pb push_back
#define mp make_pair
#define f first
#define s second

#define fopen freopen("substrcmp.in", "r", stdin); freopen("substrcmp.out","w", stdout)
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define FORR(i, b, a) for(int i = (b) - 1; i >= (a); --i)
#define FILL(A,value) memset(A,value,sizeof(A))
#define IOSFAST ios::sync_with_stdio(false); cin.tie(0)

const ll MOD = 1000LL * 1000 * 1000 + 7;
const int INF = 1e9;
const ll base = 1e18;
const int MAX = 1000;
const double EPS = 1e-9;
const double PI = acos(-1.);

int a[200000];
int n;
int main()
{
	IOSFAST;
	cin >> n;
	ll ans = 0;
	FOR(i,0,n)
	{
		cin >> a[i];
	}
	ll sum = 0;
	FOR(i,0,n)
	{
		if (a[i] == 0)
		{
			ans+=sum/2;
			sum = 0;
		}
		sum+=a[i];
	}
	cout << ans+sum/2 << endl;
	return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define MOD			1000000007
#define FOR(i,l,r)	for(int i=l;i<=r;i++)
#define REP(i,n)	for(int i=1;i<=n;i++)
#define REP0(i,n)	for(int i=0;i<n;i++)
#define PB			push_back
#define MP			make_pair
#define PII			pair<int,int>
#define VI			vector<int>
#define ALL(x)		(x).begin(),(x).end()
string s,t;
int main(){
	cin>>s>>t;
	int cnt=0;
	for(int i=0;i<3;i++)	if(s[i]==t[i])	cnt++;
	cout<<cnt<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<vector>
typedef long long int ll;
#define REP(i, n) for(int i = 0; i < (n); i++)
#define FOR_IN(i, a, b) for(int i = (a); i < (b); i++)
#define BETWEEN(x, a, b) ((x) >= (a) && (x) <= (b))
#define BIT(b, i) (((b) >> (i)) & 1)
#define LOG_F 1
#define LOG(...) if(LOG_F) fprintf(stderr, __VA_ARGS__)

using namespace std;

ll pow(int x, int n){
  return n == 0 ? 1 : x * pow(x, n - 1);
}


/*

 */
int n,a,b;

int main(){
  cin>>n>>a>>b;
  if (abs(a-b)%2 == 0) {
    cout<<"Alice\n";
  } else {
    cout<<"Borys\n";
  } 

  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


int N,S,W,Q;
int sequence[100000];
map<int,int> MAP;

void func(){

	int g = S;
	for(int i=0; i<N; i++) {
		sequence[i] = (g/7) % 10;
		if( g%2 == 0 ) { g = (g/2); }
		else           { g = (g/2) ^ W; }
	}

	int num = 0,ans = 0;

	if(Q == 2 || Q == 5){
		for(int i = 0; i < N; i++){
			if(sequence[i] != 0)num++;
			if(sequence[i]%Q == 0)ans += num;
		}
		printf("%d\n",ans);
		return;
	}

	MAP.clear();
	MAP[0] = 1;

	int amari = 0,mult = 1;
	for(int i = N-1; i >= 0; i--){
		amari += (mult*sequence[i])%Q;
		amari %= Q;
		if(sequence[i] != 0){
			ans += MAP[amari];
		}
		mult = (10*mult)%Q;
		MAP[amari]++;
	}
	printf("%d\n",ans);
}

int main(){

	while(true){
		scanf("%d %d %d %d",&N,&S,&W,&Q);
		if(N == 0 && S == 0 && W == 0 && Q == 0)break;

		func();
	}

	return 0;
}

Measured memory_bytes: 7760
#include<iostream>
#include<cmath>
#include<map>
#include<vector>
#include<queue>
#include<cassert>
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdio>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define inf (1<<29)

using namespace std;

struct P
{
  int suit,value;
  P(int suit=inf,int value=inf):suit(suit),value(value){}
  bool operator < (const P& a)const
  { return (suit!=a.suit?suit<a.suit:value<a.value); }
  bool operator == (const P& a)const
  { return suit == a.suit && value == a.value; }
};

typedef vector<P> vP;
typedef vector<vP> vvP;
typedef vector<int> vi;
typedef vector<vi> vvi;
map<vvP,int> mincost;
/*
void print(vector<vP> &vvp)
{
  cout << "print-----" << endl;
  rep(i,vvp.size())
    {
      rep(j,vvp[i].size())
	{
	  if(vvp[i][j] == P(inf,inf))
	    cout << "(x,x) "; 
	  else 
	  cout << "(" << vvp[i][j].suit << "," << vvp[i][j].value << ") ";
	}
      cout << endl;
    }
  cout << endl;
}
*/
bool check(vvP &v)
{
  rep(y,4)
    {
      rep(x,8)
	{
	  if(x == 7)
	    {
	      if(!(v[y][x] == P(inf,inf))) return false;
	      continue;
	    }
	  if(!(v[y][x].suit == y+1 && v[y][x].value == x+1)) return false;
	}
    }
  return true;
}


struct Pox
{
  vvP state;
  int cost;
  vi gap;
  Pox(vvP state,int cost=inf):state(state),cost(cost){ gap.clear(); }
  bool operator < (const Pox& a)const
  { return cost > a.cost; }
};

void bfs(vvP &vec)
{
  priority_queue<Pox> Q;
  Pox poxas7 = Pox(vec,0);

  rep(y,4)rep(x,8)if(vec[y][x] == P(inf,inf))poxas7.gap.push_back(x+y*8);

  Q.push(poxas7);
  mincost.clear();
  mincost[vec] = 0;

  while(!Q.empty())
    {
      Pox pox = Q.top(); Q.pop();

      if(check(pox.state))
	{
	  cout << pox.cost << endl;
	  return;
	}

      int pos[5][8];
      rep(y,4)rep(x,8)if(pox.state[y][x] == P(inf,inf)){}
      else pos[pox.state[y][x].suit][pox.state[y][x].value] = x + y * 8;

      rep(i,4)
	{
	  vi gaps = pox.gap;
	  int x = pox.gap[i] % 8;
	  int y = pox.gap[i] / 8;
	  P p = pox.state[y][x-1];

	  p.value++;
	  if(p.value >= 8)continue;
	  assert(x-1 >= 0);
	  int nx = pos[p.suit][p.value] % 8;
	  int ny = pos[p.suit][p.value] / 8;

	  vvP np = pox.state;
	  swap(np[y][x],np[ny][nx]);

	  Pox npox = Pox(np,pox.cost+1);

	  gaps[i] = nx + ny  * 8;
	  npox.gap = gaps;
	  
	  if(mincost.find(np) == mincost.end())
	    {
	      mincost[np] = pox.cost + 1;
	      Q.push(npox);
	    }		  
	  else if(mincost[np] > pox.cost + 1)
	    {
	      mincost[np] = pox.cost + 1;
	      Q.push(npox);
	    }
	}
    }
  cout << -1 << endl;
}

void compute(vvP &vec)
{
  bfs(vec);
}

int main()
{
  int T;
  while(cin >> T)
    {
      while(T--)
	{
	  mincost.clear();
	  vvP vec(4,vP(8));
	  int ps[5][2];
	  rep(i,4)
	    {
	      rep(j,7)
		{
		  int num;
		  scanf("%d",&num);
		  vec[i][j+1].suit = floor(num/10.0);
		  vec[i][j+1].value = num%10;
		  if(vec[i][j+1].value == 1)
		    {
		      ps[vec[i][j+1].suit][0] = j+1;
		      ps[vec[i][j+1].suit][1] = i;
		    }
		}
	    }
	  
	  REP(i,1,5)
	    {
	      int x = ps[i][0], y = ps[i][1];
	      swap(vec[i-1][0],vec[y][x]);
	    }      
	  
	  compute(vec);
	}
    }
  return 0;
}

Measured memory_bytes: 34268
def main():
    N, K = map(int, input().split())
    mod = 10**9 + 7
    r = 0
    D = [0] * (K + 1)
    for i in reversed(range(1, K + 1)):
        D[i] = pow(K // i, N, mod) - sum(D[::i])
    return sum(i * j for i, j in enumerate(D)) % mod

print(main())


Measured memory_bytes: 12048
#include <bits/stdc++.h>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
#define pi 3.14159265358979323846264338327950L
using namespace std;

int main() {
  int64_t N, M, ans=1, L=1000000007;
  cin >> N >> M;
  if (abs(N-M)>1) {
    ans=0;
  }
  else if (abs(N-M)==1) {
    for (int i=1; i<=N; i++) {
      ans*=i;
      ans%=L;
    }
    for (int j=1; j<=M; j++) {
      ans*=j;
      ans%=L;
    }
  }
  else {
    for (int i=1; i<=N; i++) {
      ans*=i;
      ans%=L;
    }
    for (int j=1; j<=M; j++) {
      ans*=j;
      ans%=L;
    }
    ans*=2;
    ans%=L;
  }
  cout << ans << endl;
}

Measured memory_bytes: 3592
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> mp;
ll inf =  1e9;


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


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

using namespace std;
typedef long long ll;
#define rep(i,j,n) for (int i = j; i < (n); i++)
#define CLR(mat) memset(mat, 0, sizeof(mat))
#define IN(a, b, x) (a<=x&&x<b)
#define out(ans) cout << ans << endl
typedef pair<ll,ll>P;
const ll mod=1e9+7;
const ll INF = 1e9;

const int MAX = 510000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main(){

  ll n,k;cin>>n>>k;

  COMinit();

  rep(i,0,k){
    out((COM(n-k+1,i+1)*COM(k-1,i))%mod);
  }

  return 0;
}


Measured memory_bytes: 12160
#include<iostream>
using namespace std;
int H, W, N, linenow, rownow;

int main(){
	int a[10001], hw[101][101];
	cin >> H >> W >> N;
	linenow = 0;
	rownow = -1;
	for(int i = 0;i < N;i ++) cin >> a[i];
	for(int i = 0;i < N;i ++){
		for(int j = 0;j < a[i];j ++){
			rownow++;
			if(rownow == W){
				rownow = 0;
				linenow ++;
			}
			hw[linenow][rownow] = i + 1;
		}
	}
	for(int i = 0;i < H / 2;i ++){
		int temp;
		for(int j = 0;j < W / 2;j ++){
			temp = hw[2 * i + 1][j];
			hw[2 * i + 1][j] = hw[2 * i + 1][W - 1 - j];
			hw[2 * i + 1][W - 1 - j] = temp;
		}
	}
	for(int i = 0;i < H;i ++){
		for(int j = 0;j < W;j ++){
			cout << hw[i][j];
			if(j != W - 1) cout << ' ';
		}
		cout << endl;
	}
	return 0;
}

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

class Myon
{
    public Myon() { }
    public static int Main()
    {
        new Myon().calc();
        return 0;
    }

    Scanner cin;
    Func cin2;
    void calc()
    {
        cin = new Scanner();
        cin2 = new Func();
        int N=cin.nextInt();
        Console.Write("ABC");
        Console.WriteLine(N);
        
    }
}



class Scanner
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner()
    {
        s = new string[0];
        i = 0;
    }

    public string next()
    {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return next();
        i = 0;
        return s[i++];
    }

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

    public long nextLong()
    {
        return long.Parse(next());
    }

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

    public double nextDouble()
    {
        return double.Parse(next());
    }


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

class Answer
{
    public void Int2DArrayAns(int[,]x,char c)
    {
        for(int i=0;i<x.GetLength(0);i++)
        {
            for(int j=0;j<x.GetLength(1)-1;j++)
            {
                Console.Write(x[i,j]);
                Console.Write(c);
            }
            Console.WriteLine(x[i,x.GetLength(1)-1]);
        }
    }
    public void Char2DArrayAns(char[,]x,char c)
    {
        for(int i=0;i<x.GetLength(0);i++)
        {
            for(int j=0;j<x.GetLength(1)-1;j++)
            {
                Console.Write(x[i,j]);
                Console.Write(c);
            }
            Console.WriteLine(x[i,x.GetLength(1)-1]);
        }
    }
}

class Func
{
    public long GCDLong(long a, long b)
    {
        while(a!=0)
        {
          long t=a;
          a=b%a;
          b= t;
        }
      
        return b;        
    }
}

Measured memory_bytes: 11220
#include <bits/stdc++.h>
#define inc(l,i,r) for (int i=l;i<=r;i++)
#define dec(r,i,l) for (int i=r;i>=l;i--)
#define mid ((l+r)>>1)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define pii pair<int,int>
#define ___ putchar(10);
#define N 200200
using namespace std;
typedef long long ll;

ll ans;
int n, tmp;
char s[N];

int main() {
	scanf("%s",s+1);  n = strlen(s+1);
	inc(1,i,n) {
		if (s[i] == 'B') ++tmp;
		else ans += tmp;
	} printf("%lld\n",ans);
}

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

int dp[105][10010];

int main(){
    int n,x;
    cin>>n>>x;
    vector<int>v(n),w(n);
    for(int i=0; i<n; ++i)cin>>v[i]>>w[i];
    for(int i=0; i<105; ++i){
        for(int j=0; j<10010; ++j){
            dp[i][j]=0;
        }
    }
    for(int i=0; i<n; ++i){
        for(int j=0; j<=x; ++j){
            if(j-w[i]>=0){
                dp[i+1][j]=max(dp[i+1][j],dp[i][j-w[i]]+v[i]);
            }
           dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
        }
    }
    cout<<dp[n][x]<<endl;
}


Measured memory_bytes: 7216
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define NO NULL
struct node{
  int key;
  struct node *p,*l,*r;
};
typedef struct node *Node;
Node root;
 
void insert(int k){
  Node y=NO;
  Node x=root;
  Node z;
  z=malloc(sizeof(struct node));
  z->key=k;
  z->l=NO;
  z->r=NO;
  while(x!=NO){
    y=x;
    if(z->key < x->key)x=x->l;
    else x=x->r;
  }
  z->p=y;
  if(y==NO)root=z;
  else if(z->key<y->key)y->l=z;
  else y->r=z;
}
void in(Node u){
  if(u==NO)return;
  in(u->l);
  printf(" %d",u->key);
  in(u->r);
}
void pre(Node u){
  if(u==NO)return;
  printf(" %d",u->key);
  pre(u->l);
  pre(u->r);
}
int main(void){
  int n,i,j;;
  char str[20];
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%s",str);
    if(str[0]=='i'){
      scanf("%d",&j);
      insert(j);
    }
    else{
      in(root);
      printf("\n");
      pre(root);
      printf("\n");
    }
  }
  return 0;
}



Measured memory_bytes: 25132
#include<bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
template<class T> istream& operator >> (istream& s, vector<T>& v)
{ for (T& x: v) { s >> x; } return s;}

int main(){
    int n,m,c; cin >> n >> m >> c;
    vector<int> b(m);
    rep(i,m) cin >> b[i];
    int ans = 0;
    rep(i,n){
        int sum = 0;
        rep(i,m){
            int x; cin >> x;
            sum += x*b[i];
        }
        sum += c;
        if(sum > 0) ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define reps(i,s,n) for(int i=(s); i<(n); i++)
#define all(v) v.begin(),v.end()
#define outve(v) for(auto i : v) cout << i << " ";cout << endl
#define outmat(v) for(auto i : v){for(auto j : i) cout << j << " ";cout << endl;}
#define in(n,v) for(int i=0; i<(n); i++){cin >> v[i];}
#define out(n) cout << (n) << endl
#define fi first
#define se second
#define pb push_back
#define si(v) int(v.size())
#define len(v) int(v.length())
#define lob(v,n) lower_bound(all(v),n)
#define lobi(v,n) lower_bound(all(v),n) - v.begin()
#define upb(v,n) upper_bound(all(v),n)
#define upbi(v,n) upper_bound(all(v),n) - v.begin()
#define mod 1000000007
#define infi 1900000000
#define infl 1100000000000000000
#define cyes cout << "Yes" << endl
#define cno cout << "No" << endl
#define csp << " " <<
#define outset(n) cout << fixed << setprecision(n);
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vs = vector<string>;
using vc = vector<char>;
using vd = vector<double>;
using vvd = vector<vector<double>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vvp = vector<vector<pair<int,int>>>;
template<typename T> using ve = vector<T>;
template<typename T> using pq2 = priority_queue<T>;
template<typename T> using pq1 = priority_queue<T,vector<T>,greater<T>>;
template<typename T> bool chmax(T &a, T b) {if(a < b) {a = b;return 1;}return 0;}
template<typename T> bool chmin(T &a, T b) {if(a > b) {a = b;return 1;}return 0;}




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

    int N,K;
    cin >> N >> K;
    
    vi P(N);
    vl C(N);
    
    in(N,P);
    in(N,C);
    
    rep(i,N) P[i]--;
    
    ll ans = -infl;
    
    rep(i,N){
        
        ll a = 0;
        int rn = 0;
        int pos = i;
        
        while (1) {
            pos = P[pos];
            a += C[pos];
            chmax(ans,a);
            rn++;
            if(rn >= K) break;
            if(i == pos) break;
        }
        
        if(a <= 0) continue;
        
        int t = K/rn;
        
        if(t == 0) continue;
        
        a = a*(ll)(t-1);
        
        chmax(ans,a);
        
        rep(j,K-(t-1)*rn){
            pos = P[pos];
            a += C[pos];
            chmax(ans,a);
        }
        
    }
    
    cout << ans << endl;
    
    
    

    return 0;
}


Measured memory_bytes: 3692
#include <bits/stdc++.h>
#define int long long
#define rng(i, l, r) for (size_t i = (l); i < (r); ++i)
#define rep(i, n) rng(i, 0, n)
#define gnr(i, l, r) for (size_t i = (r)-1; i >= (l); i--)
#define per(i, b) gnr(i, 0, b)
#define ALL(obj) (obj).begin(), (obj).end()    //1,2,3,...
#define rALL(obj) (obj).rbegin(), (obj).rend() //...,3,2,1
using namespace std;
const int INF = 1e18;
const int MOD = 1000000007;

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
void solve()
{

    // remove the bottom 3 lines when you submit this code.
    std::ifstream in("sample.txt");
    std::cin.rdbuf(in.rdbuf());

    cin.tie(0);
    ios::sync_with_stdio(false);

    int n;
    cin >> n;
    int H[n];
    rep(i, n) cin >> H[i];
    for (int i = 0; i < n; i++)
    {
        if (i == 0)
        {
            H[i]--;
        }
        else
        {
            if (H[i - 1] <= H[i] - 1)
            {
                H[i]--;
            }
            else
            {
                //do nothing
            }
        }
    }
    bool isOK = true;
    rep(i, n - 1)
    {
        if (!(H[i] <= H[i + 1]))
            isOK = false;
    }
    cout << ((isOK) ? "Yes" : "No") << endl;
}

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

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

typedef long long ll;
#define all(x) (x).begin(),(x).end()

template<typename T>
T mod(T a, T b){
    return (a + b) % b;
}

template<typename T>
T gcd(T a, T b){
    if (b == 0) return a;
    return gcd(b, a % b);
}

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

// n を素因数分解
map<ll, ll> factor(ll n){
    map<ll, ll> mp;
    for (ll i = 2; i*i <= n; i++) {
        while (n % i == 0) {
            mp[i]++;
            n /= i;
        }
    }

    if (n > 1) {
        mp[n]++;
    }

    return mp;
}

// 文字列に "hoge" が含まれているか
// string str = "hogepiyo";
// if (str.find("hoge") != string::npos) {
//     cout << "文字列が含まれています" << endl;
// }

// char to string
// char c = 'a';
// string str = {c};

char janken(char c) {
    if (c == 'r') {
        return 'p';
    } else if (c == 's') {
        return 'r';
    } else {
        return 's';
    }
}

ll R, S, P;
ll score(char c) {
    if (c == 'r') {
        return R;
    } else if (c == 's') {
        return S;
    } else if (c == 'p'){
        return P;
    } else {
        return 0;
    }
}

void solve(){
    int N, K;
    cin >> N >> K;

    cin >> R >> S >> P;

    string T;
    cin >> T;

    vector<char> str(N);
    for (int i = 0; i < K; i++) {
        str[i] = janken(T[i]);
    }

    for (int i = K; i < N; i++) {
        char opthand = janken(T[i]);
        if (str[i-K] == opthand) {
            str[i] = 'x';
        } else {
            str[i] = opthand;
        }
    }

    ll ans = 0;
    for (int i = 0; i < N; i++) {
        ans += score(str[i]);
    }

    cout << ans << endl;

    return;
}

int main(int argc, char const* argv[])
{
    solve();
    return 0;
}


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

int main(){
  string s, t;
  cin >> s >>t;
  t.pop_back();
  if (s == t) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 3624
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<cassert>
#define PB push_back
#define MP make_pair
#define sz(v) (in((v).size()))
#define forn(i,n) for(in i=0;i<(n);++i)
#define forv(i,v) forn(i,sz(v))
#define fors(i,s) for(auto i=(s).begin();i!=(s).end();++i)
#define all(v) (v).begin(),(v).end()
using namespace std;
typedef long long ll;
int main(){	
  ll a, T;
  cin >> a >> T;
  ll temp;
  cin >> temp;
  ll ans = T;
  ll cur = T;
  for (int i = 1; i < a; i++) {
  	cin >> temp;
  	if (temp < cur) {
	  	ans += temp + T - cur;
	  	cur = temp + T;
  	} else {
		cur = temp + T;
		ans += T;  	
  	}
  }
  cout << ans<< "\n";
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(k,i,n) for(ll i=k;i<n;++i)
int main(void){
    ll n;
    cin>>n;
    vector<ll>a(n),b(n);
    rep(0,i,n)cin>>a[i]>>b[i];
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    if(n%2==1){
        cout<<b[(n-1)/2]-a[(n-1)/2]+1;
    }else{
        cout<<(b[(n-1)/2]+b[(n-1)/2+1]-a[(n-1)/2]-a[(n-1)/2+1])+1;
    }
}


Measured memory_bytes: 6344
#include <cmath>
#include <chrono>
#include <random>
#include <ctime>
#include <algorithm>
#include <iosfwd>
#include <iostream>
#include <list>
#include <ostream>
#include <streambuf>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;

typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define fori(i, n) for(ll i = 0; i < (n); ++i)
#define forI(i, n) for(ll i = 1; i <= (n); ++i)
#define pll pair<ll, ll>
#define ff first
#define ss second

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")

#define pt pair<ll, ll>
#define x first
#define y second

pll operator+ (pll a, pll b){ return {a.x + b.x, a.y + b.y}; }

ll rand0m() {
    return (ull(rand()) << 15ull | ull(rand()));
}                   //[0 ... n)
ll rand0m(ll x) {
    return rand0m() % x;
}               //[0 ... n)
ll rand0m(ll minn, ll maxx) {
    return rand0m(maxx - minn + 1) + minn;
}   //[minn ... maxx]

const ll MAXN = 1e5 + 1;
const ll mod = 1e9 + 7;
const ll INF = 2e9 + 1000;

ll n, m;
ll dp[3010][3010];
ll a[3010];

void solve(){
    cin >> n;
    fori(i, n) cin >> a[i];
    bool first = n % 2 == 1;
    forI(len, n){
        if(first)
            fori(i, n){
                if(i + len - 1 < n) dp[i][len] = dp[i][len - 1] + a[i + len - 1];
                if(i + 1 < n && (i + len - 1 >= n || dp[i][len] < dp[i + 1][len - 1] + a[i])) dp[i][len] = dp[i + 1][len - 1] + a[i];
            }
        else
            fori(i, n){
                if(i + len - 1 < n) dp[i][len] = dp[i][len - 1] - a[i + len - 1];
                if(i + 1 < n && (i + len - 1 >= n || dp[i][len] > dp[i + 1][len - 1] - a[i])) dp[i][len] = dp[i + 1][len - 1] - a[i];
            }
        first = !first;
    }
    cout << dp[0][n];
}

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

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    //stress();
    solve();
}

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

using namespace std;

int main() {
	int k, n;
	string s,check,z;
	cin >> n >> s >> k;
	check = s[k-1];
	for (int i = 0; i < n; i++) {
		if (check[0] != s[i]) {
			z = "*";
			s[i] = z[0];
		}
	}
	cout << s << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h> 
using namespace std;
using ll = long long;
template<typename T> using v2 = vector<vector<T>>;
template<typename T> inline v2<T> fill(int r, int c, const T& t){ return v2<T>(r, vector<T>(c, t)); }
#define F first
#define S second

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

    vector<pair<int, int>> p(n);
    for(int i = 0; i < n; ++i) cin >> p[i].F >> p[i].S;

    vector<int> xpy(n), xmy(n);
    for(int i = 0; i < n; ++i){
        int x = p[i].F, y = p[i].S;
        xpy[i] = x+y;
        xmy[i] = x-y;
    }
    sort(xpy.begin(), xpy.end());
    sort(xmy.begin(), xmy.end());

    int ans = max(xpy[n-1]-xpy[0], xmy[n-1]-xmy[0]);
    cout << ans << "\n";
}

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

Measured memory_bytes: 6360
N, M, C = map(int, input().split())
B = list(map(int, input().split()))
ans = 0
for _ in range(N):
    A = list(map(int, input().split()))
    r = C
    for a, b in zip(A,B):
        r += a*b
    if r > 0:
        ans += 1
print(ans)

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

typedef unsigned long long ll;
typedef pair<ll,ll> pi;
typedef vector <ll> vi;
typedef vector <pi> vpi;
#define f first
#define s second
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0)
#define int ll
#define MOD 1000000007
#define maxn 200001
int N, A[maxn],ss[maxn];

int32_t main()
{
    cin>>N;
    FOR(i,0,N-1) cin>>A[i];
    ss[0] = 0;
    FOR(i,1,N-1){
		ss[i] = (ss[i-1] + A[i-1]) % MOD;
	}
	
	int ans = 0;
	
	FOR(i,0,N-1){
		//cout<<(ss[i] * A[i]) % MOD;
		ans += (ss[i] * A[i]) % MOD; ans %= MOD;
	}
	
	cout<<ans;
    
}


Measured memory_bytes: 6744
N, K = map(int, input().split())
l = [0]*N
cnt = 0
for i in range(K):
    D = int(input())
    a = list(map(int, input().split()))
    for d in range(D):
        l[a[d]-1] += 1
for i in l:
    if i == 0:
        cnt += 1
print(cnt)

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

int main()
{
  string s,t;
  cin>>s>>t;
  int n = s.length();
  long long ans = 0 ;
  for(int i = 0 ; i < n ; i++)
  {
    if(s[i] == t[i])
    {
      ans++;
    }
    
  }
   cout<<ans<<endl; 
}

Measured memory_bytes: 384
#include<stdio.h>
#include<vector>
#include<iostream>
#include<algorithm>
#include<iterator>
#include<queue>
#include<set>

using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0;i<(int)(n);i++)

class Graph{
    public:
    typedef struct Edge{
        ll from, to, cost;
        Edge(ll f, ll t, ll c): from(f),to(t),cost(c){}
    } Edge;

    bool isDirected;
    ll INF = 1LL << 62;
    ll v; // 頂点数
    std::vector<Edge> edges;  // 辺のリスト
    std::vector<std::vector<std::pair<ll,ll>>> list;  // 隣接リスト v,cost
    //std::vector<std::vector<ll>> matrix; // 隣接行列

    Graph() : isDirected(false){ init(0); }
    Graph(ll n, bool isDirected=false) : isDirected(isDirected) { init(n); }
    void init(ll n){
        v=n;
        edges.clear();
        list.assign(n, std::vector<std::pair<ll,ll>>());
        //matrix.assign(n, std::vector<ll>(n, INF));
    }
    void connect(ll from, ll to){
        con(from, to, 1);
        if(!isDirected) con(to, from, 1);
    }
    void connect(ll from, ll to, ll cost){
        con(from, to, cost);
        if(!isDirected) con(to, from, cost);
    }
    void con(ll from, ll to, ll cost){
        edges.push_back(Edge(from,to,cost));
        list[from].push_back(std::make_pair(to, cost));
        //matrix[from][to] = cost;
    }
};

class LowestCommonAncestor{ // 根付き木の最小共通祖先(ダブリング) 構築O(VlogV) query O(logV)
    public:
    int LOG = 1;
    Graph G;
    std::vector<ll> depth;
    std::vector<std::vector<ll>> table; // table[k][v] : vから2^k回親をたどったnode

    LowestCommonAncestor(Graph G) : G(G), depth(G.v, 0){
        ll val = 1;
        while(val < G.v) {val <<= 1; LOG++;}
        table.assign(LOG, std::vector<ll>(G.v, -1));
    }
    void dfs(ll idx, ll parent, ll dep){
        table[0][idx] = parent;
        depth[idx] = dep;
        for(auto to : G.list[idx]){
            if(to.first != parent) dfs(to.first, idx, dep+1);
        }
    }
    void build(){
        dfs(0, -1, 0);
        for(ll k=0; k+1<LOG; k++){
            for(ll i=0; i<table[k].size(); i++){
                if(table[k][i] == -1) table[k+1][i] = -1;
                else table[k+1][i] = table[k][table[k][i]];
            }
        }
    }
    ll query(ll u, ll v){
        if(depth[u] > depth[v]) std::swap(u,v);
        for(ll i=LOG-1; i>=0; i--){
            if(((depth[v] - depth[u]) >> i ) & 1) v = table[i][v];
        }
        if(u==v) return u;
        for(ll i=LOG-1; i>=0; i--){
            if(table[i][u] != table[i][v]){
                u = table[i][u];
                v = table[i][v];
            }
        }
        return table[0][u];
    }
};

int main(){
    ll n,q,k,c,u,v;
    cin >> n;
    Graph G(n, false);
    REP(i,n){
        cin >> k;
        REP(j,k){
            cin >> c;
            G.connect(i, c);
        }
    }
    LowestCommonAncestor lca(G);
    lca.build();
    cin >> q;
    REP(i,q){
        cin >> u >> v;
        cout << lca.query(u,v) << endl;
    }
    return 0;
}


Measured memory_bytes: 54524
#include<stdio.h>

int main(void)
{
	int a, b, c, d;
	int n;

	while(scanf("%d", &n) != EOF)
	{
		int cnt = 0;
			for(a = 0; a < 10; ++a)
				for(b = 0; b < 10; ++b)
					for(c = 0; c < 10; ++c)
						for(d = 0; d < 10; ++d)
							if((a + b + c + d) == n)
								++cnt;
			printf("%d\n", cnt);
	}

	return 0;
}

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

std::vector<int> BIT;//その位置までの良い石の数の区間和
std::vector<int> color;
std::vector<int> right;//色番号ごとの良い石の場所

int RegionSum(int l,int r);
int getSum(int r);
void addBIT(int idx,int value);

int main(){
    int N,Q;
    std::cin >> N >> Q;
    BIT.resize(N+1,0);
    color.resize(N+1,0);
    right.resize(N+1,-1);

    for(int i=1;i<=N;i++){
        std::cin >> color[i];
    }

    std::vector<std::vector<int>> QueryL_(N+1);
    std::vector<std::vector<int>> QueryID(N+1);

    for(int i=0;i<Q;i++){
        int l,r;
        std::cin >> l >> r;
        QueryID[r].push_back(i);
        QueryL_[r].push_back(l);
    }

    std::vector<int> ans(Q);

    //BITの更新と答えの取得。BITは左から順番にi番目を更新していき更新するごとにiを右端とするクエリの答えを取得する
    for(int i=1;i<=N;i++){
        //BITの更新
        if(right[color[i]] != -1)
            addBIT(right[color[i]],-1);//すでにcolor[i]の良い石がある場合は前回までの良い石の位置までのBITを1減らす
        right[color[i]] = i;
        addBIT(i,1);
        //クエリごとの答えの取得
        for(int j=0;j<QueryL_[i].size();j++){
            ans[QueryID[i][j]] = RegionSum(QueryL_[i][j],i);//QueryL_[i][j]:区間右側をiとするクエリ集合のj番目のクエリのl
        }
    }

    for(int i=0;i<Q;i++){
        std::cout << ans[i] << std::endl;
    }

    return 0;
}

int RegionSum(int l,int r){
    return getSum(r) - getSum(l-1);
}

int getSum(int r){
    int Sum=0;
    for(int i=r;i>0;i-=i&(-i)){
        Sum += BIT[i];
    }
    return Sum;
}

void addBIT(int idx,int value){
    for(int i=idx;i<=BIT.size()-1;i+=i&(-i)){
        BIT[i] += value;
    }
    return;
}

Measured memory_bytes: 53040
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
signed main(){
  int a,b,c,d;
  cin>>a>>b;
  if(a>=0 && b<=0){
    cout<<a-b<<"\n";
  }
  else{
    if(a*b>=a+b){
      cout<<a*b<<"\n";
    }
    else{
      cout<<a+b<<"\n";
    }
  }

  return(0);
}

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

int main(){
    int a[3];
    scanf("%d %d %d", &a[0], &a[1], &a[2]);
    for(int i = 0; i < 3; i++){
        for(int j = 0; j + 1 < 3 - i; j++){
            if(a[j] > a[j + 1]){
                int k = a[j];
                a[j] = a[j + 1];
                a[j + 1] = k;
            }
        }
    }

    printf("%d %d %d\n", a[0], a[1], a[2]);
    return 0;
}

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

class Program
{
	static int minNum = 1;
	static int maxNum = 200;

	static void Main(string[] args)
	{
		// 整数の入力
		int a = int.Parse(Console.ReadLine());

		if (!chectNum(a))
		{
			Console.WriteLine("入力値が不正です。");
		}

		try
		{
			// スペース区切りの整数の入力
			var input = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
			if (input.Any(x => x > 1000000000))
			{
				Console.WriteLine("入力値が不正です");
			}
			else
			{
				var answer = checkCount(input, 0);
				Console.WriteLine(answer);
			}
		}
		catch (Exception ex)
		{
			Console.WriteLine("入力値が不正です");
		}
	}

	private static int checkCount(int[] targetList, int count)
	{
		// 全て偶数の場合同じ処理を繰り返す
		if (targetList.All(x => x % 2 == 0))
		{
			targetList = targetList.Select(i => i / 2).ToArray();
			count = checkCount(targetList, ++count);
		}
		return count;
	}

	// 入力チェック1
	private static bool chectNum(int target)
	{
		return minNum <= target && target <= maxNum;
	}

}

Measured memory_bytes: 13396
import numpy as np

n, a = map(int, input().split())
x = np.array(list(map(int, input().split())))

dp = {0:1}
for y in x-a:
    for k, v in dp.copy().items():
        dp[y+k] = dp.get(y+k, 0) + v

print(dp[0]-1)


Measured memory_bytes: 12504
#include <bits/stdc++.h>
#include <chrono>
#define watch(x) cout << (#x) << " is " << (x) << endl
#define eps 1e-9

typedef long long ll;

using namespace std;

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

int main()

{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int arr[5], k;

    for (int i = 0; i < 5; i++) {

        cin >> arr[i];
    }

    cin >> k;

    sort (arr, arr+5);

    if (arr[4]-arr[0] > k) cout << ":(";
    else cout << "Yay!";

    return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define REP(i, n) for (int i = 1; i <= n; i++)
static const int inf = 1 << 30;

int main(void) {
  int N, K;
  cin >> N >> K;
  long long sum = 0;

  if (K >= 0) {
    REP(b, N) {
      sum += ((N / b) * max(b - K, 0));
      sum += (max((N % b) - K + 1, 0));
    }
  }
  if (K == 0)
    sum -= N;
  cout << sum << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define IN(a) scanf("%d",&a);
#define OUT(a) printf(a);
#define REP(i,n) for (int i=0;i<(n);i++)
#define BR break;

using namespace std;

int main(){
	int inputcase[10000][2],counter=0;

	REP(i,10000){
		IN(inputcase[i][0])
		IN(inputcase[i][1])
		if (inputcase[i][0]==0 && inputcase[i][1]==0)
			BR
		counter++;
	}

	REP(j,counter){
		if (inputcase[j][0]>inputcase[j][1])
			swap(inputcase[j][0],inputcase[j][1]);
		printf("%d %d\n",inputcase[j][0],inputcase[j][1] );
	}

	return 0;
 }

Measured memory_bytes: 1208
N, K = [int(c) for c in input().split()]

prob = 0

s = 1
while N*s<K:
    s*=2

t = 0
for i in range(N,0,-1):
    if i*s>=K:
        t+=1
    else:
        s*=2
        t=t*2+1
        
print('{:.10f}'.format(t/s/N))

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

using namespace std;
#define ll long long
#define ld long double
#define PI 3.141592653L
#define F first;
#define S second;
#define MP make_pair;
const ll INF = (ll)1e18;
const int N = 2e5 + 5;
const ll MOD = 1e9 + 7;

int parent[N];

int gcd(int a, int b) { 
    if (a == 0) 
        return b;  
    return gcd(b%a, a);  
} 
   
int lcm(int a, int b) {  
    return (a*b)/gcd(a,b);  
} 

ll pow(ll x, ll y, ll p) {
    if(y == 0) return 1;
    ll res = 1;
    x %= p;
    if(x == 0) return 0LL;
    while(y > 0) {
        if(y & 1) res = (res*x) % p;
        y >>= 1;
        x = (x*x) % p;
    }
    return res;
}

int find(int x) {
    return x == parent[x] ? x : parent[x] = find(parent[x]);
}

int main()
{
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
    string s;
    cin >> s;
    int n = s.length();
    for(int i=0;i<n-1;i++) {
        if(s[i] == '?') {
            if(s[i+1] == 'D' && s[i-1] != 'P') s[i] = 'P';
            else s[i] = 'D';
        }
    }
    if(s[n-1] == '?') s[n-1] = 'D';
    cout << s << endl;
    return 0;
}


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

using namespace std;

struct Dice{
	int P[6];
	void Roll(char a){
		
	int top;
	
	switch(a) {
		
		case 'E':
		top = P[0];
		P[0] = P[3];
		P[3] = P[5];
		P[5] = P[2];
		P[2] = top;
		break;
		
		case 'W':
		top = P[0];
		P[0] = P[2];
		P[2] = P[5];
		P[5] = P[3];
		P[3] = top;
		break;
		
		case 'S':
		top = P[0];
		P[0] = P[4];
		P[4] = P[5];
		P[5] = P[1];
		P[1] = top;
		break;
		
		case 'R':
		top = P[1];
		P[1] = P[2];
		P[2] = P[4];
		P[4] = P[3];
		P[3] = top;
		break;
		
		default :
		top = P[0];
		P[0] = P[1];
		P[1] = P[5];
		P[5] = P[4];
		P[4] = top;
		break;	
	}	
}
	int Top() {
    return P[0];
  }
  	int Right(){
    return P[2];
  }
  	int Left(){
    return P[3];
  }
  	int Front(){
    return P[1];
  }
};

bool Test(Dice A,Dice B);

int main() {
	
	int n;
	Dice S[100];
	bool flag[2];
	
	cin >> n;
	
		
		for(int i=0;i<n;i++)
		for(int j=0;j<6;j++)
		cin >> S[i].P[j];
		
	flag[1] = true;
	
  	for(int i=0;i<n-1;i++){
  		
    for(int j=i+1;j<n;j++){
    	
      flag[0] = false;
      
    for(int k=0;k<4;k++){
    	
    	S[j].Roll('R');
    	
    for(int l=0;l<4;l++){
    	
      S[j].Roll('N');
      if(Test ( S[i], S[j] )) 
	  flag[0] = true;
    }
      }
      S[j].Roll('E');
      for(int a=0;a<4;a++){
      	
    S[j].Roll('N');
    if(Test ( S[i], S[j] ) ) 
	flag[0] = true;
    
    }
       
      S[j].Roll('W');
      S[j].Roll('W');
      for(int a=0;a<4;a++){
    S[j].Roll('N');
    if(Test ( S[i], S[j] ) ) 
	flag[0] = true;
      }
      if(flag[0]) 
	  flag[1] = false;
    }
  }
  
  	if( flag[1] )
  	cout << "Yes\n";
  	
  	else
  	cout << "No\n";
  
	return 0;
}

bool Test(Dice A,Dice B) {
  for(int i=0;i<6;i++) 
  if(A.P[i]!=B.P[i]) 
  return false;
  return true;
}



Measured memory_bytes: 3092