akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define ADD(a, b) a = (a + ll(b)) % mod
#define MUL(a, b) a = (a * ll(b)) % mod
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)
#define all(a) (a).begin(), (a).end()
#define sz(v) (int)(v).size()
#define pb push_back
#define sec second
#define fst first
#define debug(fmt, ...) Debug(__LINE__, ":", fmt, ##__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<int, pi> ppi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> mat;
typedef complex<double> comp;
void Debug() {cout << '\n'; }
template<class FIRST, class... REST>void Debug(FIRST arg, REST... rest){
	cout<<arg<<" ";Debug(rest...);}
template<class T>ostream& operator<<(ostream& out,const vector<T>& v) {
	out<<"[";if(!v.empty()){rep(i,0,sz(v)-1)out<<v[i]<<", ";out<<v.back();}out<<"]";return out;}
template<class S, class T>ostream& operator<<(ostream& out,const pair<S, T>& v){
	out<<"("<<v.first<<", "<<v.second<<")";return out;}
const int MAX_N = 300010;
const int MAX_V = 100010;
const double eps = 1e-6;
const ll mod = 1000000007;
const int inf = 1 << 30;
const ll linf = 1LL << 60;
const double PI = 3.14159265358979323846;
///////////////////////////////////////////////////////////////////////////////////////////////////

int N, W;
ll dp[MAX_N];

void solve() {
	cin >> N >> W;
	rep(i, 1, W + 1) dp[i] = -linf;

	rep(i, 0, N) {
		ll w, v; cin >> w >> v;
		rer(j, W, 0) {
			if(j + w <= W) {
				MAX(dp[j + w], dp[j] + v);
			}
		}
	}
	ll res = -linf;
	rep(i, 0, W + 1) MAX(res, dp[i]);
	cout << res << "\n";
}

int main() {
#ifndef LOCAL
	ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    cout << fixed;
	cout.precision(20);
	srand((unsigned int)time(NULL));
#ifdef LOCAL
	//freopen("in.txt", "wt", stdout); //for tester
    freopen("in.txt", "rt", stdin);
#endif	
	solve();
#ifdef LOCAL
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
	return 0;
}



Measured memory_bytes: 1024
#include<iostream>

/**
 * @brief プログラムのエントリーポイントです
 * 
 * @return int 終了後、0を返却しなければなりません。
 */
int main()
{
    // 入力
    std::string N;
    std::cin >> N;

    for(int i = 0; i < N.length(); ++i)
    {
        if(N[i] == '7')
        {
            std::cout << "Yes" << std::endl;
            return 0;
        }
    }

    // 出力
    std::cout << "No" << std::endl;
    return 0;
}


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

#define endl "\n"

#define pi 2*acos(0)
#define INF 1e16
#define MIN 1e-9
#define min(a,b) (((a)<(b))?(a):(b))
#define max(a,b) (((a)>(b))?(a):(b))
#define m_p make_pair
#define p_b push_back
#define ff first
#define ss second
#define n_p(a) next_permutation(all(a))
#define all(v) v.begin(),v.end()
#define ii pair<int, int>
#define vi vector<int>
#define vii vector<ii>
#define vvi vector<vi>
#define rev(s) reverse(all(s))
#define ull unsigned long long
#define ll long long
#define MOD 1000000007
#define mem(a,k) memset(a,k,sizeof a)
#define REP(i, a, b) for (int i = int(a); i <= int(b); i++)
#define u_b(X,V) upper_bound(X.begin(),X.end(),V)
#define l_b(X,V) lower_bound(X.begin(),X.end(),V)
#define cnt(s,c) count(all(s),c)

//bitwise helpers
#define isOn(S, j) (S & (1 << j))
#define setBit(S, j) (S |= (1 << j))
#define clearBit(S, j) (S &= ~(1 << j))
#define toggleBit(S, j) (S ^= (1 << j))
#define lowBit(S) (S & (-S))
#define setAll(S, n) (S = (1 << n) - 1)

#define modulo(S, N) ((S) & (N - 1))
#define isPowerOfTwo(S) (!(S & (S - 1)))
#define nearestPowerOfTwo(S) ((int)pow(2.0, (int)((log((double)S) / log(2.0)) + 0.5)))
#define turnOffLastBit(S) ((S) & (S - 1))
#define turnOnLastZero(S) ((S) | (S + 1))
#define turnOffLastConsecutiveBits(S) ((S) & (S + 1))
#define turnOnLastConsecutiveZeroes(S) ((S) | (S - 1))

using namespace std;

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

    int t;

    //cin >> t;
    t = 1;
    for(int test = 1; test <= t ; test++) {
        int A, B, T, cnt = 0, res = 0;
        cin >> A >> B >> T;
        cnt = A;
        while(cnt <= (T * 1.0 + 0.5)) {
            cnt += A;
            res += B;
        }
        cout << res << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define szof(s) (int)s.size()
#define pb push_back
#define int long long
#define all(s) s.begin(), s.end()
#define pii pair<int, int>
#define fr first
#define sc second

using namespace std;
const int N = (int)2e5 + 5;

vector <int> a, b;

bool small(vector <int> a, vector <int> b) {
  for (int i = 0; i < a.size(); i++) {
    if (a[i] != b[i]) {
      return a[i] < b[i];
    }
  }
  return true;
}

void solve() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    int x;cin >> x;
    a.pb(x);
  }
  for (int i = 1; i <= n; i++) {
    int x;cin >> x;
    b.pb(x);
  }
  vector <int> pos;
  for (int i = 1; i <= n; i++) {
    pos.pb(i);
  }

  if (!small(a, b)) {
    swap(a, b);
  }

  int l, r, cnt = 0;
  do {
    cnt++;
    if (pos == b) {
      r = cnt;
      break;
    }
    if (pos == a) {
      l = cnt;
    }
  } while (next_permutation(all(pos)));
  cout << max(0LL, r - l);
}

main() {
  solve();
}


Measured memory_bytes: 256
void main() {
    int[] tmp = readln.split.to!(int[]);
    int a = tmp[0], b = tmp[1];
    int coin;
    foreach (i; 0 .. 2) {
        if (a > b) {
            coin += a;
            --a;
        } else {
            coin += b;
            --b;
        }
    }
    coin.writeln;
}

import std.stdio;
import std.string;
import std.array;
import std.conv;
import std.algorithm;
import std.range;
import std.math;
import std.container;
import std.typecons;

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e18+7;

int N,M;
int ans;
int a[100005];

int main(){ 

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

cin>>N>>M;

int n=0;
for(int i=1; i<=sqrt(M); i++){
	if(M%i==0){
		int i1=i;
		int i2=M/i;
		a[n]=i1; n++;
		if(i1!=i2){
			a[n]=i2; n++;
		}
	}
}

for(int i=0; i<n; i++){
	int b=M/a[i];
	if(b>=N){
		ans=max(ans,a[i]);
	}
}

cout<<ans<<endl;

}


Measured memory_bytes: 256
#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(){
    int n; ll k;
    cin>>n>>k;
    map<int,ll>mp;
    rep(i,n){
        int a,b;
        cin>>a>>b;
        mp[a]+=b;
    }
    ll cnt=0;
    for(auto&p:mp){
        cnt+=p.second;
        if(cnt>=k){
            cout<<p.first<<endl;
            return 0;
        }
    }
}


Measured memory_bytes: 7520
#include "bits/stdc++.h"
using namespace std;

#define ASC(vec) vec.begin(), vec.end()		// 昇順ソート 例：sort(ASC(vec));
#define DESC(vec) vec.rbegin(), vec.rend()	// 降順ソート 例:sort(DESC(vec));
#define rep(i, n) for(int i = 0; i < n; i++)
#define Rep(i, n) for(int i = 1; i < n; i++)

const int mod = 1000000007;
const int inf = (int)1e9 + 7;
const long long INF = 1LL << 60;

using ii = pair<int, int>;
using ll = long long;
using vi = vector<int>;
using vd = vector<double>;
using vb = vector<bool>;
using vl = vector<ll>;
using vs = vector<string>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;
using vii = vector<pair<int, int>>;

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

ll GCD(ll a, ll b) { return b ? GCD(b, a % b) : a; }
ll LCM(ll a, ll b) { return (a * b) / GCD(a, b); }
int round_int(int a, int b) { return (a + (b - 1)) / b; }

constexpr array<int, 9> dx = { 0, 1, 0, -1, -1, 1, 1, -1, 0 };
constexpr array<int, 9> dy = { 1, 0, -1, 0, 1, 1, -1, -1, 0 };

// ──────────────────────────────────────────────────────────────────────────────

int main() {
	int n; cin >> n;
	vl a(n);
	rep(i, n) cin >> a[i];
	ll ans = 0;
	rep(i, 60) {
		ll x = 0;
		rep(j, n) if (a[j] >> i & 1) ++x;
		ll now = x * (n - x) % mod;
		rep(j, i) now = now * 2 % mod;
		ans += now;
		ans %= mod;
	}
	cout << ans << endl;
}

Measured memory_bytes: 2560
#include<unordered_map>
#include<iostream>
#include<algorithm>
#include<utility>
#include<climits>
#include<fstream>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<cmath>
#include<list>
#include<map>
#include<set>
#define inf 0x7f7f7f
#define p(x) (x)*(x)
#define PI 3.14159265358979
using namespace std;

typedef vector<vector<int> > vtype;
typedef long long ll;

int main()
{
	//ios::sync_with_stdio(false);
	ll n = 0, r = 0;
	cin >> n >> r;
	if(n <= 10)
		cout << r + 100 * (10 - n) << endl; 
	else
		cout << r << endl; 
    return 0;
}















Measured memory_bytes: 256
import sys
import numpy as np
from collections import deque
from itertools import combinations
sys.setrecursionlimit(10**9)



def main():
    N, K = map(int,input().split())
    p = list(map(int, input().split()))

    sum_0 = 0
    for i in range(K):
        sum_0 += p[i]


    sum_n = sum_0
    max = sum_0
    for i in range(N-K): # i+1
        sum_n = sum_n + p[i+K] - p[i]
        if max < sum_n:
            max = sum_n

    ans = (K + max) / 2
    print("{0:.6f}".format(ans))

if __name__ == "__main__":
  main()


Measured memory_bytes: 33952
N = int(input())
D = 0

for i in range(N):
    D1, D2 = map(int, input().split())
    if D == 3:
        break

    if D1 == D2:
        D += 1

    elif D1 != D2:
        D = 0

if D == 3:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 9176
#include<stdio.h>
int main(){
	int a, b;
	while(1){
		scanf("%d %d", &a, &b);
		if(a == 0 && b == 0)break;
		if(a <= b)printf("%d %d\n", a, b);
		else printf("%d %d\n", b, a);
	}
	return 0;
}


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

int main(void){
    int n;
    cin>>n;
    vector<int> c(n),s(n),f(n);
    rep(i,n-1){
        cin>>c[i]>>s[i]>>f[i];
    }
    rep(i,n){
        int t = 0;
        for(int j=i;j<n-1;j++){
            t=max(t,s[j]);
            if(t%f[j]==0){
                t += c[j];
            }else{
                t += f[j]-t%f[j] + c[j];
            }
        }
        cout<<t<<endl;
    }
    return 0;
}


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

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

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

    int N; cin >> N;
    vector<int> lis;

    int p; cin >> p;
    lis.push_back(0);
    int cnt = 1;
    for (int i = 1;i < N;i++){
        int now; cin >> now;
        if(p != now) cnt++;
        else{
            lis.push_back(cnt);
            cnt = 1;
        }
        p = now;
    }
    lis.push_back(cnt);
    lis.push_back(0);

    int ans = 0;
    for (int i = 0;i < lis.size()-2;i++){
        ans = max(lis[i]+lis[i+1]+lis[i+2], ans);
    }

    cout << ans << endl;

    return 0;

}


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

namespace solver{
  void solve(){
    int N, X, T; std::cin >> N >> X >> T;
    int ans = (N + X - 1) / X * T;
    std::cout << ans << "\n";
  }
}

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


Measured memory_bytes: 3632
#include <iostream>
using namespace std;
int main(void){
    long long Q,H,S,D,N,sum=0;
    cin>>Q>>H>>S>>D>>N;
    N*=4;
    if(D<S*2&&D<H*4&&D<Q*8){
        sum+=(N/8)*D;
        N=N%8;
    }
    if(S<H*2&&S<Q*4){
        sum+=(N/4)*S;
        N=N%4;
    }
    if(H<Q*2){
        sum+=(N/2)*H;
        N=N%2;
    }
    sum+=N*Q;
    cout<<sum<<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int main(void){
    for(int x=1;;x++){
        int l;
        int n;
        int v[1010]={0};
        int w[1010]={0};
        int dp[10][1010]={0};
        int we[10][1010]={0};
        cin >> l;
        if(l==0)break;
        cin >> n;
        for(int i=1;i <= n;i++){
            scanf("%d,%d",&v[i],&w[i]);
        }
        for(int i=1;i <= n;i++){
            for(int j=0;j <= l;j++){
                if(j < w[i]){
                    dp[2][j] = dp[1][j];
                    we[2][j] = we[1][j];
                }
                else{
                    if(dp[1][j]>dp[1][ j-w[i] ] + v[i]){
                        dp[2][j] = dp[1][j];
                        we[2][j] = we[1][j];
                    }
                    else{
                        dp[2][j] = dp[1][ j-w[i] ] + v[i];
                        we[2][j] = we[1][ j-w[i] ]+w[i];
                    }
                }
            }
            /*for(int k=0;k<=l;k++)cout<<we[i+1][k]<<" ";
            cout<<endl;*/
            for(int k=0;k <= l;k++){
                dp[1][k] = dp[2][k];
                we[1][k] = we[2][k];
            }
        }
        /*for(int i=1;i<=n;i++){
            for(int j=0;j<=l;j++){
            cout<<dp[i][j]<<" ";
            }
            cout<<endl;
        }*/
        cout<<"Case "<<x<<":"<<endl;
        cout<<dp[2][l]<<endl;
        cout<<we[2][l]<<endl;

    }
	return 0;
}

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

bool isPrime(int num) {
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false; // 偶数はあらかじめ除く
    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2) {
      if (num % i == 0) {
        // 素数ではない
        return false;
      }
    }
    // 素数である
    return true;
}

int main() {
  int x;
  int ans = 0;
  cin >> x;
  for (int i = x; i <= 1000000; i++){
    if(isPrime(i)){
      ans = i;
      break;
    }
  } 
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int INF=999999999;

int main() {
 string S,T;
 cin>>S>>T;
 for(int i=0;i<S.size();i++){
     string K;
     K.push_back(S.at(S.size()-1));
     for(int j=0;j<S.size()-1;j++){
     K.push_back(S.at(j));
     }
     S=K;
     if(K==T){cout<<"Yes"<<endl;return 0;}}

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
const ll MOD = 1e9 + 7;
const int MAX = 1510000;
int X, Y;

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

int combi(int n, int m) {
    if (n < m) return 0;
    if (n < 0 || m < 0) return 0;
    return fac[n] * (finv[m] * finv[n - m] % MOD) % MOD;
}

void solve() {
    COMinit();
    cin >> X >> Y;
    int r = (X + Y) % 3;
    if (r != 0) {
        cout << 0 << endl;
    } else {
        int n = (X + Y) / 3;
        P min_p = P(2 * n, n);
        int m = min_p.first - X;
        cout << combi(n, m) << endl;
    }
}

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


Measured memory_bytes: 35584
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<string>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
#include<iomanip>

#define REP(i,n) for(int i=0;i<(n);i++)
#define EPS (1e-7)
#define INF (2e9)
// cout << setprecision(10)

using namespace std;
typedef long long int ll;
const ll MOD = 1000000007;

string S;
int main(void){
    cin >> S;
    if (S=="RRR") cout << 3 << endl;
    else if (S=="RRS" or S=="SRR") cout << 2 << endl;
    else if (S=="SSS") cout << 0 << endl;
    else cout << 1 << endl;
    return 0;
}



Measured memory_bytes: 3548
#include<bits/stdc++.h>
using namespace std;
int main(){
  int K;
  cin>>K;
  vector<vector<int>>list(K,vector<int>(K));
  for(int i=0;i<K;i++){
    for(int j=0;j<K;j++){
      list.at(i).at(j)=gcd(i+1,j+1);
    }
  }
  int sum=0;
  for(int i=0;i<K;i++){
    for(int j=0;j<K;j++){
      for(int k=0;k<K;k++){
        sum=sum+gcd(k+1,list.at(i).at(j));
      }
    }
  }
  cout<<sum<<endl;
}

Measured memory_bytes: 3772
#include <stdio.h>

#define MAX 100

int main(){
  int m[MAX][MAX];
  int u,k,v,n;
  int i,j;

  scanf("%d",&n);

  for (i = 0;i < n;i++)
    for (j = 0;j < n;j++)
      m[i][j] = 0;
   
  for (i = 0;i < n;i++){
    scanf("%d %d",&u,&k);

    u--;
    
    for (j = 0;j < k;j++){
      scanf("%d",&v);
      
      v--;
      m[u][v] = 1;
    }
  }

  for (i = 0;i < n;i++){
    for (j = 0;j < n;j++){
      if (j)
	printf(" ");
      
      printf("%d",m[i][j]);
    }
    printf("\n");
  }
  
  return 0;
}




Measured memory_bytes: 2112
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define rep2(i,n) for(int i=0;i<=n;i++)
#define repr(i,a,n) for(int i=a;i<n;i++)
#define all(a) a.begin(),a.end()
#define P pair<long long,long long>
#define double long double
#define INF 1e10
#define MOD 1e9+7
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; }
signed main(){
int a,b;
  cin>>a>>b;
  cout<<a+b/2;
}

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

int main(){
  string s;
  cin >> s;
  
  int a = -1;
  int z = -1;
  for(int i = 0; i < s.size(); i++){
    if(s[i] == 'A' && a == -1){
      a = i;
    }
    if(s[i] == 'Z' && i > z){
      z = i;
    }
  }
  
  cout << z - a + 1 << endl;
  
  return 0;
}

Measured memory_bytes: 640
N, K = map(int, input().split())
M = 10**9 + 7
ans = 0
for i in range(K, N+2):
    _min = (i-1)*i//2 
    _max =  (N + N-i+1) * i //2 
    ans += (_max - _min + 1) 
print(ans % M)

Measured memory_bytes: 9184
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <assert.h>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

int main() {
    int h, w;
    cin >> h >> w;
    vector<string> s(h);
    REP(i,h) cin >> s[i];

    vector<string> x(h), y(w);
    REP(i,h) REP(j,w){
        x[i] += s[i][j];
        y[j] += s[i][j];
    }

    REP(i,h) sort(ALL(x[i]));
    REP(i,w) sort(ALL(y[i]));

    VI p(h, -1), q(w, -1);

    map<string, VI> mp;
    REP(i,h){
        mp[x[i]].push_back(i);
    }

    int j = 0;
    for (auto a : mp){
        VI v = a.second;
        REP(i,v.size()/2){
            p[j] = v[2*i];
            p[h-1-j] = v[2*i+1];
            j++;
        }
        if (v.size() % 2 == 1){
            if (h % 2 == 0 || p[h/2] != -1){
                cout << "NO" << endl;
                return 0;
            }
            p[h/2] = v.back();
        }
    }

    mp.clear();
    REP(i,w){
        mp[y[i]].push_back(i);
    }

    j = 0;
    for (auto a : mp){
        VI v = a.second;
        REP(i,v.size()/2){
            q[j] = v[2*i];
            q[w-1-j] = v[2*i+1];
            j++;
        }
        if (v.size() % 2 == 1){
            if (w % 2 == 0 || q[w/2] != -1){
                cout << "NO" << endl;
                return 0;
            }
            q[w/2] = v.back();
        }
    }

    assert(*min_element(ALL(p)) == 0);
    assert(*min_element(ALL(q)) == 0);

    // for (int x : p) cout << x << " ";
    // cout << endl;
    // for (int x : q) cout << x << " ";
    // cout << endl;

    int hh = h / 2;
    int ww = w / 2;

    VI pp(hh);
    REP(i,hh) pp[i] = p[i];
    VI qq(ww);
    REP(i,ww) qq[i] = q[i];

    sort(ALL(pp));
    sort(ALL(qq));

    do{
        REP(i,hh) p[i] = pp[i];
            // for (int x : p) cout << x << " ";
            // cout << endl;
        do{
            REP(i,ww) q[i] = qq[i];
            bool ok = true;
            REP(i,h) REP(j,w){
                if (s[p[i]][q[j]] != s[p[h-1-i]][q[w-1-j]]){
                    ok = false;
                }
            }
            if (ok){
                cout << "YES" << endl;
                return 0;
            }
        }while (next_permutation(ALL(qq)));
    }while (next_permutation(ALL(pp)));

    // REP(i,h) REP(j,w){
    //     if (s[p[i]][q[j]] != s[p[h-1-i]][q[w-1-j]]){
    //         cout << "NO" << endl;
    //         return 0;
    //     }
    // }

    // cout << "YES" << endl;

    cout << "NO" << endl;

    return 0;
}


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

int main() {
    int N, T; cin >> N >> T;
    vector<int> A(N);
    rep(i, N){
        cin >> A[i];
    }

    int cnt = 1;
    int maxsa = 0;
    int maxsaz = 0;
    int mi = A[0];
    int ma = A[0];
    for (int i = 1; i < N; i++){
        if(A[i] > A[i-1]){
            if(A[i] > ma){
                ma = A[i];
                maxsa = ma - mi;
                if(maxsa > maxsaz){
                    maxsaz = maxsa;
                    cnt = 1;
                } else if(maxsa == maxsaz) {
                    cnt++;
                }
            }
        } else {
            if(mi > A[i]){
                mi = A[i];
                ma = A[i];
            }
        }
    }

    cout << cnt << endl;

    return 0;
}

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

const string YES = "Yes";
const string NO = "No";
using ll = long long;

void solve(long long X, long long Y){
    for(int i = 0;i < 1000;i++){
        for(int j = 0;j < 1000;j++){
            if(i + j == X && i * 2 + j * 4 == Y){
                cout<<"Yes"<<endl;
                return;
            }
        }
    }
    cout<<"No"<<endl;
}

int main(){
    long long X;
    scanf("%lld",&X);
    long long Y;
    scanf("%lld",&Y);
    solve(X, Y);
    return 0;
}


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

int main()
{
    int n; cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; i++) cin >> v[i];
    sort(v.begin(), v.end());

    double item = (double)v[0];
    for (int i = 1; i < n; i++) {
        item = (item + (double)v[i]) / 2.0;
    }
    cout << setprecision(10) << item << endl;
    return 0;
}

Measured memory_bytes: 256
N = int(input())
S =[0]*N
for i in range(N):
    S[i] = str(input())

ans = int(0)
a=int(0)
b=int(0)
c=int(0)
R=int(0)

for i in range(N):
    AB = S[i].split("AB")
    R = len(AB)-1

    ans += R
    R = 0

for i in range(N):
    if S[i].endswith('A') : a +=1
    if S[i].startswith('B') : b +=1
    if S[i].endswith('A') and S[i].startswith('B'): c +=1

if c==0 and c==a and c==b: R=0
elif c==a and c==b:
    R = min(a, b)-1
else : R=min(a, b)

ans += R

print(ans)

Measured memory_bytes: 3700
#include <iostream>
#include <string>
#include <queue>
using namespace std;
#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i,a,b) for(int i = (a); i <= (int)(b); ++i)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(v) ((int)v.size())

int main()
{
	int sum = 0;
	int N;
	cin >> N;
	int M[100001];
	REP(i,100001)M[i]=0;
	REP(i,N){
		int a;
		cin >> a;
		if(M[a]==0){
			sum++;
		}
		M[a]++;
		if(M[a]>=3){
			M[a]-=2;
		}
	}
	//２つの消したい奴の間にカードが１枚でもあれば成功。（最後に２が１つだけ残ったらアウト。）
	int two = 0;
	REP(i,100001){
		if(M[i]==2){
			two+=1;
		}
	}
	if(two%2==1){
		sum--;
	}
	
	cout << sum << endl;
    return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
template<class T>
T gcd(T a, T b){
  if(a > b) swap(a, b);
  if(a == 0) return b;
  return gcd(b % a, a);
}

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

#include <cstdio>
inline int getInt(){ int s; scanf("%d", &s); return s; }

#include <set>

using namespace std;
int c[9] = {
  2
  ,
  5
  ,
  5
  ,
  4
  ,
  5
  ,
  6
  ,
  3
  ,
  7
  ,
  6
};

int dp[10000 + 1];
char ans[10000 + 1];
int a[10];
int n, m;

int max_cnt(int rest){
  if(rest == 0){
    return 0;
  }

  if(dp[rest]) return dp[rest];

  REP(i,m){
    const int cnt = c[a[i] - 1];
    if(cnt > rest) continue;
    int ans = max_cnt(rest - cnt);
    if(ans != -1) return dp[rest] = ans + 1;
  }
  return dp[rest] = -1;
}

int main(){
  const int n = ::n = getInt();
  const int m = ::m = getInt();
  vector<pair<int, int> > v(m);
  REP(i,m){
    const int a = getInt();
    v[i] = make_pair(c[a - 1], -a);
  }
  sort(v.begin(), v.end());
  REP(i,m) ::a[i] = -v[i].second;
  // REP(i,m) printf("%d ", a[i]); puts("");

  vector<int> b(m);
  REP(i,m) b[i] = ::a[i];
  sort(b.rbegin(), b.rend());

  const int len = max_cnt(n);
  string ans(len, '0');

  int rest = n;
  REP(i,len){
    REP(j,m){
      const int cnt = c[b[j] - 1];
      if(cnt <= rest && max_cnt(rest - cnt) == len - (i + 1)){
        ans[i] = '0' + b[j];
        rest -= cnt;
        break;
      }
    }
  }

  printf("%s\n", ans.c_str());

  return 0;
}

Measured memory_bytes: 512
//MADE BY Y_is_sunshine;
//#include <bits/stdc++.h>
//#include <memory.h>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <cstdio>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define INF 0x3f3f3f3f
#define MAXN 100005

typedef long long ll;

const ll mod = 1e9 + 7;
const double PI = acos(-1);

using namespace std;

int N, M, K;

bool prime(int n){
	if(n == 2 || n == 3)
		return true;
	if(n % 6 != 1 && n % 6 != 5)
		return false;
	int t = sqrt(n);
	for(int i = 5; i <= t; i += 6){
		if(n % i == 0 || n % (i + 2) == 0)
			return false;
	}
	return true;
}

int main(void)
{
#ifdef Sunshine
	freopen("data.txt", "r", stdin);
#endif

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

	cin >> N;
	while(1){
		if(prime(N)){
			cout << N << '\n';
			break;
		}
		N++;
	}




	return 0;
}



Measured memory_bytes: 256
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws FileNotFoundException {

		//    	File file = new File("src/in.txt");
		//    	Scanner sc = new Scanner(file);

		Scanner sc = new Scanner(System.in);

		int A = sc.nextInt();
		int B = sc.nextInt();
		sc.close();

		if(A>=13) {
			System.out.println(B);
		} else {
			if(A>=6) {
				System.out.println(B/2);
			}  else {
				System.out.println("0");
			}
		}

	}
}


Measured memory_bytes: 23252
# 解説AC、辺の張り方が難しすぎる
from collections import deque
INF = 1 << 23


class Dinic:
    def __init__(self, N):
        self.N = N
        self.G = [[] for _ in range(self.N)]

    def add_edge(self, u, v, cap):
        self.G[u].append([v, cap, len(self.G[v])])
        self.G[v].append([u, 0, len(self.G[u])-1])

    def bfs(self, s):
        self.level = [-1] * self.N
        que = deque([s])
        self.level[s] = 0
        while que:
            u = que.popleft()
            for (v, cap, _) in self.G[u]:
                if cap > 0 and self.level[v] < 0:
                    self.level[v] = self.level[u] + 1
                    que.append(v)

    def dfs(self, u, t, f):
        if u == t:
            return f
        for i in range(self.progress[u], len(self.G[u])):
            self.progress[u] = i
            (v, cap, rev) = self.G[u][i]
            if cap > 0 and self.level[u] < self.level[v]:
                d = self.dfs(v, t, min(f, cap))
                if d > 0:
                    self.G[u][i][1] -= d
                    self.G[v][rev][1] += d
                    return d
        return 0

    def max_flow(self, s, t):
        flow = 0
        INF = 10**9
        while True:
            self.bfs(s)
            if self.level[t] < 0:
                return flow
            self.progress = [0] * self.N
            current_flow = self.dfs(s, t, INF)
            while current_flow > 0:
                flow += current_flow
                current_flow = self.dfs(s, t, INF)


def main():
    H, W = (int(i) for i in input().split())
    A = [input() for i in range(H)]
    F = Dinic(H+W+2)  # 0,1,...,W-1,0,..,H-1,s,t
    s = H+W
    t = H+W+1
    Sh, Sw = -1, -1
    Th, Tw = -1, -1
    for h in range(H):
        for w in range(W):
            if A[h][w] == "S":
                Sh, Sw = h, w
                F.add_edge(s, h+W, INF)
                F.add_edge(s, w, INF)
            elif A[h][w] == "T":
                Th, Tw = h, w
                F.add_edge(h+W, t, INF)
                F.add_edge(w, t, INF)
            if A[h][w] != ".":
                F.add_edge(h+W, w, 1)
                F.add_edge(w, h+W, 1)
    if Sh == Th or Sw == Tw:
        return print(-1)

    print(F.max_flow(s, t))


if __name__ == '__main__':
    main()


Measured memory_bytes: 79004
#include <stdio.h>
#include <math.h>

int main(){
    int n,x[100],y[100];
    int i;
    double ma=0,eu=0,m3=0,ch=0,di;
    scanf("%d",&n);
    for(i=0;i<n;i++)scanf("%d",&x[i]);
    for(i=0;i<n;i++)scanf("%d",&y[i]);
    for(i=0;i<n;i++){
        di = fabs(x[i]-y[i]);
        ma += di;
        eu += di*di;
        m3 += di*di*di;
        if(ch<di)ch = di;
    }
    printf("%f %f %f %f\n",ma,sqrt(eu),pow(m3,1./3),ch);
}

Measured memory_bytes: 1100
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const static ll INF = 1e15;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
// __uint128_t
const ll MOD = 1e9+7;


int main(){
    int N, M; cin >> N >> M;
    vector<int> A(N), B(N), C(M), D(M), ans(N);
    for(int i = 0; i < N; i++) cin >> A[i] >> B[i];
    for(int i = 0; i < M; i++) cin >> C[i] >> D[i];

    for(int i = 0; i < N; i++){
        int dis = 1e9, cp = 1;
        int a = A[i], b = B[i];
        for(int j = 0; j < M; j++){
            int c = C[j], d = D[j];
            int temp = abs(c-a) + abs(d-b);
            if(temp < dis) {
                dis = temp;
                cp = j+1;
            }
        }
        ans[i] = cp;
    }
    for(auto x : ans) cout << x << endl;

}


Measured memory_bytes: 3636
N = int(input())
A = list(map(int, input().split(' ')))

lst = A[:]
B = [0]
for i in range(1, len(A)):
  if lst[i] < lst[i-1]:
	  B.append(lst[i-1] - lst[i])
	  lst[i] = lst[i-1]
  else:
    B.append(0)
    
print(sum(B))

Measured memory_bytes: 32164
n = int(input())
h = list(map(int, input().split()))

dp = [0] * n
dp[1] = abs(h[1] - h[0])


for i in range(2, n):
  dp[i] = min(dp[i-2] + abs(h[i] - h[i-2]), dp[i-1] + abs(h[i]- h[i-1]))

print(dp[n-1])

Measured memory_bytes: 13980
#include<stdio.h>
#include<string.h>

int main(void){
  char Rankstack[512]={0},str[512]={0};
  int nowrank=0,i,j,k,l;
  scanf("%511s",str);
  l=strlen(str);
  for(i=0;i<l;i++){
    if(str[i]=='m'){
      Rankstack[++nowrank]=1;
    }else if(str[i]=='e'){
      if(Rankstack[nowrank]==1){
	Rankstack[nowrank]=2;
      }else{
	puts("Rabbit");
	return 0;
      }
    }else if(str[i]=='w'){
      if(Rankstack[nowrank]==2){
	Rankstack[nowrank--]=3;
      }else{
	puts("Rabbit");
	return 0;
      }
    }
    if(nowrank==0 && i!=l-1){
      puts("Rabbit");
      return 0;
    }
  }
  puts("Cat");
  return 0;
}

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

bool check(string s,string t){
    vector<int> pos[26];
    REP(i,s.size()){
        pos[s[i]-'a'].push_back(i);
    }
    bool ok=true;
    REP(i,26){
        int sz=pos[i].size();
        REP(j,sz-1){
            if(t[pos[i][j]]!=t[pos[i][j+1]]) ok=false;
        }
    }
    return ok;
}

signed main()
{   
    string s,t; cin>>s>>t;
    if(check(s,t) and check(t,s))
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
}

Measured memory_bytes: 4180
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <string>
using namespace std;

typedef long long int ll;

int main() {

	int a = 0, b = 0;
	
	cin >> a;//a人

	b = a / 3;
	a = a % 3;
	
	if (b >= 1) {
		cout << b << endl;
	}
	else {
		cout << 0 << endl;
	}





	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    void run() {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int p = scan.nextInt();
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (scan.nextInt() % 2 == 1) count++;
        }
        long sum = 0;
        if (p == 0) sum++;
        for (int i = 1; i <= count; i++) {
            if (p == 1) {
                if (i % 2 == 1) {
                    sum += combination(count, i);
                }
            } else {
                if (i % 2 == 0) {
                    sum += combination(count, i);
                }
            }
        }
        System.out.println((long)(sum * Math.pow(2, n - count)));
    }
    
    long combination(int n,int m) {
        long c = 1;
        m = ( n - m < m ? n - m : m );
        for( int ns = n - m + 1, ms = 1; ms <= m; ns ++, ms ++ ) {
            c *= ns;
            c /= ms;
        }
        return c;
    }
    public static void main(String[] args) {
//        System.out.println(new Main().combination(5, 3));
        new Main().run();
    }
}


Measured memory_bytes: 21844
typedef long long ll;
#include <bits/stdc++.h>
using namespace std;
int main() {
    ll A[3];
    std::cin >> A[0]>>A[1]>>A[2];
    
    ll ans=300;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            for (int k = 0; k < 3; k++) {
                if(i==j || j==k || k==i){
                    continue;
                }
                ans=min(ans,(ll)abs(A[j]-A[i])+(ll)abs(A[j]-A[k]));
            }
        }
    }
    std::cout << ans << std::endl;
}


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

int main(){
  
  int n;

  while(cin>>n){

    int cnt=0;
    
    for(int a=0;a<10;a++){
      if(a>n) continue;
      for(int b=0;b<10;b++){
	if(a+b>n) continue;
	for(int c=0;c<10;c++){
	  if(a+b+c>n) continue;
	  for(int d=0;d<10;d++){
	    if(a+b+c+d==n)
	      cnt++;
	  }
	}
      }
    }

    cout<<cnt<<endl;
    
  }

}



Measured memory_bytes: 3036
#include<bits/stdc++.h>
#define LL long long
#define int long long
inline LL read(){
	char c=getchar();while (c!='-'&&(c<'0'||c>'9'))c=getchar();
	LL k=0,kk=1;if (c=='-')c=getchar(),kk=-1;
	while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();return kk*k;
}using namespace std;
void write(LL x){if (x<0)x=-x,putchar('-');if (x/10)write(x/10);putchar(x%10+'0');}
void writeln(LL x){write(x);puts("");}
int n,x,y,ans,sum,ff;
signed main(){
	n=read();sum=1e15;ff=0;
	for (int i=1;i<=n;i++){
		x=read();y=read();if (x!=y)ff=1;ans+=x;if (x>y)sum=min(sum,y);
	}if (!ff)writeln(0);else writeln(ans-sum);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using llpair=pair<ll,ll>;
using llvec=vector<ll>;
using llmat=vector<vector<ll>>;
#define llmattp(name,a,b,num) name(a,vector<ll>(b,num))
#define LLINF 1LL<<60
#define ABS(x) ( (x)>0 ? (x) : -(x) )

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

ll gcd(ll a, ll b) {
	if(a==0||b==0) return 0;
	if(a<b) swap(a,b);
	ll tmp = a%b;
	while(tmp!=0) {
		a = b;
		b = tmp;
		tmp = a%b;
	}
	return b;
}

ll factorial(ll x) {
	ll f=1;
	for(ll i=2; i<x; i++) {
		f*=i;
	}
	return f;
}

ll nPr(ll n, ll r) {
	ll result=1;
	for(ll i=r+1; i<=n; i++) result*=i;
	return result;
}

ll nCr(ll n, ll r) {

	if (n == 0) { return 0; }
	if (r == 0) { return 1; }
	if (r == 1) { return n; }
	if (n == r) { return 1; }

	if (r > n / 2) { r = n / 2; }

	double result = 1;
	for (double i = 1; i <= r; i++) {
		result *= (n - i + 1) / i;
	}

	return (ll)result;
}

bool IsPrime(ll num) {
	if (num < 2) return false;
	else if (num == 2) return true;
	else if (num % 2 == 0) return false; // 偶数はあらかじめ除く

	double sqrtNum = sqrt(num);
	for (ll i = 3; i <= sqrtNum; i += 2)
	{
		if (num % i == 0)
		{
			// 素数ではない
			return false;
		}
	}

	// 素数である
	return true;
}

ll GreaterBinarySearch(ll *array, ll key, ll max, ll min) {
	if(array[max]<array[min]) {
		return NULL;
	} else {
		ll mid = max + (min-max)/2;
		if(array[mid]<key) {
			return GreaterBinarySearch(array,key,max,mid-1);
		} if(array[mid]>key) {
			return GreaterBinarySearch(array,key,mid+1,min);
		} else {
			return mid;
		}
	}
}

int main() {
	string a,b,c; cin>>a>>b>>c;
	cout<<'A'<<b.at(0)<<'C'<<endl;
}


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

const int MAXN = 100005;

int n, u[MAXN], v[MAXN], d[MAXN];

struct node {
	int to, next, dis;
} edge[MAXN*2];
int head[MAXN], top = 0;
inline void push(int i, int j, int d)
{ edge[++top] = (node) {j, head[i], d}, head[i] = top; }

int siz[MAXN], max_siz[MAXN];
long long ans = 0;

void dfs(int nd, int f, int last = 0)
{
	siz[nd] = 1;
	max_siz[nd] = 0;
	for (int i = head[nd]; i; i = edge[i].next) {
		int to = edge[i].to;
		if (to == f) continue;
		dfs(to, nd, edge[i].dis);
		siz[nd] += siz[to];
		max_siz[nd] = max(max_siz[nd], siz[to]);
	}
        max_siz[nd] = max(max_siz[nd], n-siz[nd]);
}

long long dfs_calc(int nd, int f, long long d)
{
	long long ans = 2*d;
	for (int i = head[nd]; i; i = edge[i].next) {
		int to = edge[i].to;
		if (to == f) continue;
		ans += dfs_calc(to, nd, d+edge[i].dis);
	}
	return ans;
}

int main()
{
	ios::sync_with_stdio(false);
	cin >> n;
	int min_siz = 1e8;
	for (int i = 1; i < n; i++) {
		cin >> u[i] >> v[i] >> d[i];
		push(u[i], v[i], d[i]), push(v[i], u[i], d[i]);
	}
	dfs(1, 0);
	for (int i = 1; i <= n; i++) min_siz = min(min_siz, max_siz[i]);
	int rt, cnt = 0;
	for (int i = 1; i <= n; i++)
		if (max_siz[i] == min_siz) {
			rt = i;
			cnt++;
		}
	long long cur = dfs_calc(rt, 0, 0);
	int min_d = 1e9;
	for (int j = head[rt]; j; j = edge[j].next) {
		if (cnt == 1) 
			min_d = min(min_d, edge[j].dis);
		else if (max_siz[edge[j].to] == max_siz[rt])
			min_d = edge[j].dis;
	}
	cout << cur-min_d << endl;
	return 0;
}


Measured memory_bytes: 8960
#include "bits/stdc++.h"
#define FI first.first
#define SE first.second
#define TH second
#define fi first
#define se second
#define th second

using namespace std;

template<typename T>
string to_string(const vector<T>& vc, int w) {
	if(vc.empty()) return "";
	if(w + 1 == vc.size()) return to_string(vc[w]);
	return to_string(vc[w]) + "," + to_string(vc, w + 1);
}

template<typename T>
string to_string(const vector<T>& vc) {
	return "{" + to_string(vc, 0) + "}";
}

void debug_out() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
 
#ifdef DEBUG
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

class DebugStream {}LOG;
template <typename T>DebugStream &operator<<(DebugStream &s, const T&) { return s; }
#ifdef DEBUG
#define LOG clog
#endif

typedef long long ll;
typedef pair<ll, ll> ii;
typedef long double ld;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const int maxN = 5e5 + 9, maxV = 1e6 + 9, MOD = 1e9 + 7, SQ = 335, lg = 20, bs = 29;

vector<int> adj[maxN];
int n, q, ans[maxN], ri[maxN];

int qry(const vector<int>& fen, int w) {
	int ret = 0;
	for(; w > 0; w -= w&-w) ret += fen[w];
	return ret;
}

void upd(vector<int>& fen, int w, int x) {
	for(; w < fen.size(); w += w&-w) fen[w] += x;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	#endif

	cin >> n >> q;
	vector<int> arr(n), fen(n + 1);
	for(auto& el: arr) cin >> el;
	for(int i = 0, lf; i < q; i++) {
		cin >> lf >> ri[i];
		adj[lf - 1].push_back(i);
	}

	map<int, int> mp;
	for(int i = n - 1; i >= 0; i--) {
		if(mp.count(arr[i])) {
			upd(fen, mp[arr[i]] + 1, -1);
		}
		mp[arr[i]] = i;
		upd(fen, i + 1, 1);
		for(auto qr: adj[i])
			ans[qr] = qry(fen, ri[qr]);
	}
	for(int i = 0; i < q; i++)
		cout << ans[i] << '\n';
}



Measured memory_bytes: 55784
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n; cin >> n;
    int c = 0;
    set<int> s;
    for(int i = 0; i < n; i++){
        int num; cin >> num;
        if(s.find(num) != s.end()){s.erase(num); c--;}
        else{s.insert(num); c++;}
    }
    cout << s.size() << endl;
}

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

int main() {
  int n, s, d = 0;
  cin >> n >> s;
  rep(i, s){
    d += pow(100, n);
    if(d % int(pow(100, n+1)) == 0) d += pow(100, n);
  }
  cout << d << endl;
  return 0;
}

Measured memory_bytes: 384
/******************************************************************************

                         بسم الله الرحمن الرحيم
                     Author: Mst: Mhamuda Khatun
                               RUCSE27

*******************************************************************************/

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define ll long long
#define pi 2*acos(0.0)
#define f first
#define s second
#define pb push_back
#define gap ' '
#define fastio {ios_base::sync_with_stdio(false);cin.tie(NULL);}
#define mod 1000000007
#define MAX 1000000000000
#define N 305

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

    c=b%k;

    if(b-c>=a)
        cout<<"OK";
    else
        cout<<"NG";

    cout<<"\n";
    return 0;   //:D
}




Measured memory_bytes: 3572
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long lli;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const lli INF = 1e18;
int n;
lli a[maxn];

lli pre[maxn], su[maxn];

void ReadInput()
{
    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> a[i];
}

void Init()
{
    pre[0] = 0;
    for(int i = 1; i <= n; ++i)
        pre[i] = pre[i - 1] + a[i];
    su[n + 1] = 0;
    for(int i = n; i > 0; --i)
        su[i] = su[i + 1] + a[i];
}

void Solve()
{
    lli ans = INF;
    for(int i = 1; i < n; ++i)
    {
        lli L = pre[i], R = su[i + 1];
        ans = min(ans, abs(L - R));
    }
    cout << ans << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ReadInput();
    Init();
    Solve();
}


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

struct UnionFind{
    vector<int> p;
    int n;
    UnionFind(int s) : n(s){
        p.resize(n);
        for(int i = 0; i < n; i++)  p[i] = i;
    }

    int findSet(int x){
        if(p[x] != x){
            p[x] = findSet(p[x]);
        }
        return p[x];
    }

    void unite(int x, int y){
        x = findSet(x), y = findSet(y);
        if(x == y)  return;
        p[x] = y;
    }
};

int main(){
    int n, m;
    cin >> n >> m;
    UnionFind uf(n);
    int a, b;
    while(m-- > 0){
        cin >> a >> b;
        uf.unite(--a, --b);
    }
    int cnt[1000] = {};
    for(int i = 0; i < n; i++)  cnt[uf.findSet(i)]++;
    int ans = 0;
    for(int i = 0; i < n; i++)  ans += (cnt[i]>0)*(2*(cnt[i]>1)-1);
    cout << abs(ans) << endl;
    return 0;
}


Measured memory_bytes: 3144
#include <stdio.h>
#include <iostream>

using namespace std;

int main(void){
	int t, n, c, d, i, j, h, l;
	scanf("%d",&t);
	for(i = 0;i < t;i++){
		scanf("%d",&n);
		c = d = 0;
		scanf("%d",&h);
		l = h;
		for(j = 1;j < n;j++){
			scanf("%d",&h);
			if(l > h)
				d = max(d, l - h);
			else if(l < h)
				c = max(c, h - l);
			l = h;
		}
		printf("%d %d\n",c,d);
	}
	return 0;
}

Measured memory_bytes: 1188
n = int(input())
s = [input() for _ in range(n)]

s_sort = sorted(s)

s_num = [1]*n

for i in range(1,n):
    if s_sort[i] == s_sort[i-1]:
        s_num[i] += s_num[i-1]

Maxnum = max(s_num)

index_num = [n for n, v in enumerate(s_num) if v == Maxnum]

[print(s_sort[i]) for i in index_num]


Measured memory_bytes: 36224
#include<bits/stdc++.h>
#define LL long long

using namespace std;
const int N=2e5+10;
int rd()
{
    int x=0,w=1;char ch=0;
    while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+(ch^48);ch=getchar();}
    return x*w;
}
int to[N<<1],nt[N<<1],hd[N],dg[N][2],tot=1;
void adde(int x,int y)
{
    ++tot,to[tot]=y,nt[tot]=hd[x],hd[x]=tot;
    ++tot,to[tot]=x,nt[tot]=hd[y],hd[y]=tot;
}
char cc[N];
int n,m,tt;
bool v[N];

int main()
{
////////////////
    n=rd(),m=rd();
    scanf("%s",cc+1);
    for(int i=1;i<=m;++i)
    {
	int x=rd(),y=rd();
	adde(x,y);
	++dg[x][cc[y]-'A'],++dg[y][cc[x]-'A'];
    }
    queue<int> q;
    for(int i=1;i<=n;++i)
	if(!dg[i][0]||!dg[i][1]) v[i]=1,q.push(i);
    while(!q.empty())
    {
	int x=q.front();
	q.pop();
	++tt;
	for(int i=hd[x];i;i=nt[i])
	{
	    int y=to[i];
	    --dg[y][cc[x]-'A'];
	    if(!v[y]&&!dg[y][cc[x]-'A']) v[y]=1,q.push(y);
	}
    }
    puts(tt==n?"No":"Yes");
    return 0;
}




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

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

    long long a[n+1], b[n];

    for(long long i = 0; i <= n; i++){
        cin >> a[i];
    }

    for(long long i = 0; i < n; i++){
        cin >> b[i];
    }

    long long count = 0;
    long long zanki;
    for(long long i = 0; i <= n; i++){
        if(i == 0){
            count += min(a[i], b[i]);
            zanki = max((long long)0, b[i] - a[i]);
        }
        else if(1 <= i and i < n){
            count += min(a[i], b[i]+zanki);
            if(a[i] < zanki){
                zanki = b[i];
            }
            else{
                zanki = max((long long) 0, b[i] - a[i]+zanki);
            }

        }
        else if(i == n){
            count += min(a[i], zanki);
        }
    }

    cout << count << endl;

    return 0;
}

Measured memory_bytes: 1792
#include <algorithm>
#include <bitset>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <stack>
#include <string>
#include <utility>
#include <vector>

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

using namespace std;

template <typename T> void output(T, int);
template <typename T> T max(T, T);
int gcd(int a, int b);

int main() {
    // source
    int n;
    cin >> n;
    int a[n];
    rep(i, n) { cin >> a[i]; }
    sort(a, a + n);

    int ans = a[n - 1] - a[0];
    cout << ans << endl;
    return 0;
}

template <typename T> void output(T a, int precision) {
    if (precision > 0) {
        cout << setprecision(precision) << a << "\n";
    } else {
        cout << a << "\n";
    }
}

template <typename T> T max(T a, T b) {

    if (a > b) {
        return a;
    } else {
        return b;
    }
}

template <typename T> T min(T a, T b) {

    if (a < b) {
        return a;
    } else {
        return b;
    }
}

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


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<ll,ll> P;
#define M 1000000007
int main(){
  int n,c=0;
  cin>>n;
  vector<int> v(n);
  for(int i=0;i<n;i++){
    cin>>v[i];
    if(i>1){
      if(v[i]>v[i-1]&&v[i-1]>v[i-2]||v[i]<v[i-1]&&v[i-1]<v[i-2]) c++;
    }
  }
  cout<<c;
}

Measured memory_bytes: 256