akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long LL;
typedef long double LD;

LL inf = 1000000000000;
LL mod = 1000000007;

int main()
{
	string s;

	cin >> s;

	string t(s.size(), 'x');
	cout << t << "\n";


	
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func main() {
	sc.Split(bufio.ScanWords)
	a := next()
	b := next()
	fmt.Print(do(float64(a), float64(b)))
}

func next() int64 {
	sc.Scan()
	i, err := strconv.ParseInt(sc.Text(), 10, 64)
	if err != nil {
		panic(err)
	}
	return i
}

func do(a, b float64) float64 {
	at := float64(a) / 0.08
	bt := float64(b) / 0.1
	work := math.Ceil(maxf(at, bt))
	baseValue := math.MaxFloat64
	for true {
		if work*0.08 < a || work*0.1 < b {
			break
		}
		if int64(math.Floor(work*0.08)) == int64(a) && int64(math.Floor(work*0.1)) == int64(b) {
			baseValue = work
		}
		work--
	}
	if baseValue == math.MaxFloat64 {
		return -1
	}
	return baseValue
}

func maxf(a, b float64) float64 {
	if a > b {
		return a
	}
	return b
}

Measured memory_bytes: 640
N, C, K = map(int, input().split())
t_list = [int(input()) for i in range(N)]

t_list.sort()

count = 0
passenger = 0
time = 0

for t in t_list:
    if passenger == 0:
        passenger += 1
        count += 1
        time = t
    elif 1 <= passenger < C:
        if t - time <= K:
            passenger += 1
        else:
            passenger = 1
            count += 1
            time = t
    else:
        passenger = 1
        count += 1
        time = t

print(count)

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

struct my{
  pair<int,int> top;
  pair<int,int> sec;
};

int main() {
  int n,k; cin >>n >>k;
  vector<int> h(n);
  for (int i=0; i<n; i++) cin >>h.at(i);
  sort(h.begin(), h.end());
  int ans = 1000000000;
  for (int i=0; i<n-k+1; i++){
    ans = min(ans, h.at(i+k-1)-h.at(i));
  }
  cout <<ans;
  cout <<endl;
}


Measured memory_bytes: 640
import java.util.*;
import java.io.*;

public class Main{
    static int solve(int P, int sumA, int sumB, int sumC, int cntA, int cntB, int cntC){
        if (P == n){
            if (sumA == 0 || sumB == 0 || sumC == 0) return (1 << 30);
            return (cntA - 1) * 10 + Math.abs(sumA - a) +
                   (cntB - 1) * 10 + Math.abs(sumB - b) +
                   (cntC - 1) * 10 + Math.abs(sumC - c);
        }
        return Math.min(
            Math.min(
                solve(P+1, sumA + v[P], sumB, sumC, cntA + 1, cntB, cntC),
                solve(P+1, sumA, sumB + v[P], sumC, cntA, cntB + 1, cntC)
            ),
            Math.min(
                solve(P+1, sumA, sumB, sumC + v[P], cntA, cntB, cntC + 1),
                solve(P+1, sumA, sumB, sumC, cntA, cntB, cntC)
            )
        );
    }
    static int a, b, c, n, v[] = new int[10];
    public static void main(String[] args) {
        FastReader in = new FastReader();
        n = in.nextInt();
        a = in.nextInt();
        b = in.nextInt();
        c = in.nextInt();
        for (int l = 0; l < n; ++l){
            v[l] = in.nextInt();
        }
        System.out.println(solve(0, 0, 0, 0, 0, 0, 0));
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}

Measured memory_bytes: 22484
import java.util.*;
 
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		String S = sc.next();
		String[] str = new String[N];
		int count=0;
      
		for(int i=0; i<N; i++){
			str[i] = String.valueOf(S.charAt(i));
			if(i==0||!(str[i].equals(str[i-1]))){
				count++;
            }
        }
		
		System.out.println(count);
    }
}


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

using namespace std;

#define int 		long long
#define endl		"\n"
#define mod			1000000007
#define inf			1e12
#define IOS			ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)

int32_t main() {

	IOS;

	int n;
	cin >> n;

	if (n % 2 == 0 || n % 5 == 0) {
		cout << "-1\n";
		return 0;
	}

	int c = 1, temp = 7;

	while (temp % n) {
		temp = (temp * 10 + 7) % n;
		c++;
	}

	cout << c << endl;

	return 0;
}

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

int main(){
  int X,N;
  cin >> X >> N;
  
  if(N==0){
    cout << X <<endl;
    return 0;
  }
  
  vector<int>num(N);
  vector<int>copy(N);
  for(int i=0;i<N;i++){
    cin >> num.at(i);
    copy.at(i)=num.at(i);
    num.at(i)=abs(X-num.at(i));
  }
  sort(num.begin(),num.end());
  
  for(int i=0;i<N;i++){
    if(num.at(i)==(i+1)/2){
      continue;
    }
    else{
      int flag=0;
      for(int j=0;j<N;j++){
        if(X-((i+1)/2)==copy.at(j)){
          flag=1;
        }
      }
      if(flag==1){
        cout << X+((i+1)/2) << endl;
        return 0;
      }
      else if(flag==0){
        cout << X-((i+1)/2) << endl;
        return 0;        
      }
    }
  }
  
  int flag=0;
  for(int j=0;j<N;j++){
    if(X-((N+1)/2)==copy.at(j)){
      flag=1;
    }
  }
  if(flag==1){
    cout << X+((N+1)/2) << endl;
    return 0;
  }
  else if(flag==0){
    cout << X-((N+1)/2) << endl;
    return 0;        
  }
}

Measured memory_bytes: 3632
Option Explicit On
Option Strict On

Imports System.Collections.Generic

Module Module1

    Sub Main()

        Dim X As Integer = CInt(Console.ReadLine())
        Dim R As Integer = X
        Dim s As New List(Of Integer)
        Dim i As Integer

        Do

            For i = 2 To R
                If R Mod i <> 0 Then
                    s.Add(i)
                Else
                    Exit For
                End If
            Next

            If i >= R AndAlso s.Count() > 0 Then
                Exit Do
            End If

            If R = 2 Then
                Exit Do
            End If

            R += 1
            s.Clear()

        Loop

        Console.WriteLine(R)
        ’Console.ReadLine()

    End Sub

End Module



Measured memory_bytes: 13280
#include<bits/stdc++.h>
using namespace std;
int a[210005],p[200005];
long long ans;
int main()
{
	int n;
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	bool f=true;
	for (int i=1;i<=n;i++)
	{
		if (a[i]>i-1 || i>1 && a[i-1]<a[i]-1) {f=false;break;}	
		p[i-a[i]]=a[i];
	}	
	for (int i=1;i<=n;i++)
		ans=ans+p[i];
	if (!f) printf("-1");
	 	else printf("%lld",ans);
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
            using namespace std;
             
            int main(){
              //int w,h,tmp;
              string s,t;
              cin >> s;
              int ans = 0;
              t = "YAKI";
              //for(int i=0; i<s.size(); i++)
              if(s.substr(0,4)==t.substr(0,4)) cout << "Yes" << endl;
              else cout << "No" << endl;
              //cout << ans << endl;
            }

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

using namespace std;



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

    vector<long long>a(n);

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

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

    vector<long long> r(10000,1);

    int count = 0;
    for(long long i=1;i*i<=a.at(0);i++){
        if(a.at(0)%i==0){
            r.at(2*count) = i;
            r.at(2*count+1) = a.at(0)/i;
            count++;
        }
    }

    sort(r.begin(),r.end(),greater<long long>());



    int test = 1;
    long long cv;

    for(int i=0;i<r.size();i++){
        if(test==1) {
            for (int j = 1; j < n; j++) {
                if (a.at(j) % r.at(i) != 0) {
                    test = 1;
                    break;
                }
                if(j==(n-1)&&a.at(j)%r.at(i)==0){
                    test = 0;
                    cv = r.at(i);
                }
            }
        }else{
            break;
        }
    }

    cout<<cv<<endl;


}


Measured memory_bytes: 1152
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>

using namespace std;

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = n;i >= m;i--)
#define REPO(i, n) for(int i = 1;i <= n;i++)
#define ll long long
#define INF 1999999999
#define MINF -1999999999
#define ALL(n) n.begin(),n.end()
#define MP make_pair

unsigned gcd(unsigned a, unsigned b) {
	if (a < b) gcd(b, a);
	unsigned r;
	while ((r = a % b)) {
		a = b;
		b = r;
	}
	return b;
}

int main() {
	int n,k,ng = INF,a;
	cin >> n >> k;
	REP(i, n) {
		cin >> a;
		if (ng == INF) ng = max(a, k) - min(a, k);
		ng = gcd(ng, max(a, k) - min(a, k));
	}
	cout << ng << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<math.h>
using namespace std;
#define ll long long

int main(){
    ll N,a[5],ans;
    ll minn = 0x7fffffffffffffff;
    scanf("%lld",&N);
    for(int i = 0;i < 5;i++){
        scanf("%lld",&a[i]);
        if(minn > a[i])minn = a[i];
    }
    //printf("this\n");
    //printf("minn = %I64d\n",minn);
    if(N <= minn){
        printf("5\n");
    }
    else{
        ans = 4 + (N + minn - 1)/minn;
        printf("%lld\n",ans);
    }
    return 0;
}



Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
int search(int d,int* arr,int k){
  int flag=0;
  for(int i=0;i<k;i++){
    if(d==arr[i]){
      flag=1;
      break ;
    }
  }
  return flag;
}
int main(){
  int n,k;
  scanf("%d %d\n",&n,&k);
  int arr[k];
  int i;
  for(i=0;i<k;i++){
    scanf("%d ",&arr[i]);
  }
  int t=n;
  int g,d,m=1;
  while(m!=0){
    g=t;
    while(g!=0){
      d=g%10;
      m= search(d,&arr,k);
      if(m==1){
        break;
      }
      g=g/10;
    }
    if(m==0){
      printf("%d\n",t);
      exit(0);
    }
    else t++;
  }
  printf("-1");
  return ;
}

Measured memory_bytes: 1680
object Main {

  def main(args: Array[String]): Unit = {
    val sc = new java.util.Scanner(System.in)

    val N = sc.nextInt()
    val P = Array.fill(N)(sc.nextInt()).toIndexedSeq
    val Q = Array.fill(N)(sc.nextInt()).toIndexedSeq

    // 辞書順にpermutationを出して, PとQが出現したタイミングを記録しておいて, その差分を求める
    val r = ((1 to N).permutations.indexWhere(_ == P) - (1 to N).permutations.indexWhere(_ == Q)).abs
    println(r)
  }

}


Measured memory_bytes: 59972
#include<bits/stdc++.h>
#define N 10
using namespace std;
int n,m,d[N],ans;
map<char,int> c;
set<char> ish;
bool used[N];
bool q[N];
string s;
int p[N];

void func(int x){
  if(x==m){
    int f=0,sum=0;
    for(int i=0;i<m;i++){
      if(!d[i]&&q[i])f=1;
      sum+=p[i]*d[i];
    }
    if(f)return;
    if(!sum)ans++;
    return;
  }
  for(int i=0;i<10;i++){
    if(used[i])continue;
    d[x]=i;
    used[i]=true;
    func(x+1);
    used[i]=false;
  }
}

int main(){
  while(1){
    cin>>n;
    if(!n)break;
    for(int i=0;i<n;i++){
      cin>>s;
      for(int j=s.size()-1,k=1;j>=0;j--,k*=10){
	if(!j&&s.size()!=1)ish.insert(s[j]);
	if(c.find(s[j])==c.end())
	  if(i!=n-1)c[s[j]]=k;
	  else c[s[j]]=-k;
	else
	  if(i!=n-1)c[s[j]]+=k;
	  else c[s[j]]-=k;
      }
    }
    memset(q,0,sizeof(q));
    map<char,int>::iterator ite;
    int k=0;
    for(ite=c.begin();ite!=c.end();ite++,k++){
      p[k]=(*ite).second;
      if(ish.find((*ite).first)!=ish.end())
	q[k]=true;
    }
    m=c.size();
    ans=0;
    func(0);
    cout<<ans<<endl;
    ish.clear();
    c.clear();
  }
  return 0;
}

Measured memory_bytes: 3020
N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))


a, b = [0], [0]
for i in range(N):
    a.append(a[i] + A[i])
for i in range(M):
    b.append(b[i] + B[i])


ans, j = 0, M
anss = []
for i in range(1+N):
    if a[i] > K:
        break
    while 1:
        if a[i] + b[j] <= K:
            break
        j -= 1
    
    ans = max(ans, i+j)
    
            
print(ans)


Measured memory_bytes: 126816
#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;
typedef tuple<int,int,int> state;
long double pi = acos(-1);
const int INF = 1001001001;


// 最小公倍数を求める
int euqlid (int a, int b){
  int temp;
  temp = a % b;
  if(temp == 0)return b;
  return euqlid(b,temp);
}
ll conbination(ll a,ll b){
  ll u = 1;
  ll d = 1;
  while(b != 0){
    u *= a;
    d *= b;
    a--;
    b--;
  }
  return u / d;
}
int strtoint(char s){
  return (int(s-'0'));
}
char changeS(char alpha){
  if(0x41 <= alpha and alpha <= 0x5A)return (alpha + 0x20);
  else if(0x61 <= alpha and alpha <= 0x7A)return (alpha - 0x20);
  return alpha;
}
int fact(int n){
  if(n == 1)return 1;
  return n * fact(n-1);
  }
int ceil(int a,int b){
  // a/bの切り上げを考える
  return (a+b-1)/b;
}

int main() {
  int a, b;
  cin >> a >>b;
  cout << a * b << endl;
}


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

#define ll long long

ll doo(ll x){
	return x*(x - 1)/2;
}

int main()
{
	ll n;	cin >> n;
	vector <ll> a(n);	

	ll count[200001];	memset(count, 0, sizeof(count));

	// ll tot = 0;
	for (ll i = 0; i < n; i ++){
		cin >> a[i];
		count[a[i]] += 1;
		// tot += a[i];
	}

	ll pc;
	for (auto i : count){
		pc += doo(i);
	}


	// cout << pc << "\n";

	for (ll i = 0; i < n; i ++){
		cout << pc - doo(count[a[i]]) + doo(max(0*1ll, count[a[i]] - 1)) << "\n";
	}
}

Measured memory_bytes: 5760
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;cin>>n;
	int a[n+1]={0};int i,j,k;
	for(i=0;i<n;i++)
	cin>>a[i];
	int count=0;
	for(i=0;i<n-2;i++)
	{
		for(j=i+1;j<n-1;j++)
		{
			for(k=j+1;k<n;k++)
			{
				if(a[i]!=a[j]&&a[j]!=a[k]&&a[k]!=a[i]&&a[i]+a[j]>a[k]&&a[i]+a[k]>a[j]&&a[j]+a[k]>a[i]&&a[i]-a[j]<a[k]&&a[i]-a[k]<a[j]&&a[j]-a[k]<a[i]&&a[j]-a[i]<a[k]&&a[k]-a[i]<a[j]&&a[k]-a[j]<a[i])
				count++;
			}
		}
	}
	cout<<count<<endl;
	return 0;
}

Measured memory_bytes: 3628
S = input()
T_list = ['dream', 'eraser', 'dreamer', 'erase']
S = S[::-1]
while len(S) > 0:
    if S[:5] == 'maerd' or S[:5] == 'esare':
        S = S[5:]
    elif S[:6] == 'resare':
        S = S[6:]
    elif S[:7] == 'remaerd':
        S = S[7:]
    else:
        break
if len(S) > 0:
    print('NO')
else:
    print('YES')

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

int main(){

	#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	#endif

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

	int n; cin >> n;

	cout << (1000 - n%1000)%1000 << endl;

	return 0;
}

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

using namespace std;
 
#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()
#define _P(...) (void)fprintf(stderr, __VA_ARGS__)

typedef int64_t ll; typedef vector<int> VI; typedef pair<int,int> pii;
const ll mod = 1e9+7;

void dbg(){ cerr << "\n"; }  
template <typename T,typename ...T2>
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }



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

	string s;
	cin >>s;
	bool ok=0;
	rep(i, 2){
		if(s[i]==s[i+1] && s[i]==s[i+2]) ok=1;
	}
	cout << (ok? "Yes":"No") <<"\n";
	return 0;
}

Measured memory_bytes: 256
/*
  "I knew I shouldn't have
   gotten out of bed today."
   - Squidward Tentacles
*/
#include<iostream>
#include<algorithm>
#include<bitset>
#include<cmath>
#include<cstring>
#include<climits>
#include<numeric>

#include<deque>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<unordered_map>
// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>

#include<fstream>
#include<chrono>
using namespace std;
// using namespace __gnu_pbds;

#define int          long long
#define ld           long double
#define pii          pair<int,int>
#define vi           vector<int>
#define maxheap      priority_queue<int>
#define minheap      priority_queue<int,vi,greater<int>>
#define pb           push_back
#define mp           make_pair
#define ff           first
#define ss           second
#define endl         '\n'
#define rep(i,s,e)   for(int i=s;i<=e;i++)
#define brep(i,s,e)  for(int i=s;i>=e;i--)
#define all(x)       (x).begin(),(x).end()
#define ball(x)      (x).rbegin(),(x).rend()
#define sz(x)        (int)x.size()
#define mem(x,y)     memset(x,y,sizeof(x))
#define pbds         tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define VR46         ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int MOD = 1e9+7;
ld EPS = 1e-12;

int lcm(int a, int b)
{
    int g = __gcd(a,b);
    return (a*b)/g;
}

signed main()
{
    VR46 ofstream out("output.txt");
    // auto start = chrono::high_resolution_clock::now();

    // GANDU TEST CASE BNAKE TEST KRLE
    // OUT OF BOUNDS BHI DEKHLIO CHUTIYE
    int t = 1;
    // cin>>t;
    rep(test,1,t)
    {
        int a, b;
        cin>>a>>b;
        cout<< lcm( a,b ) <<endl;
    }

    // auto stop = chrono::high_resolution_clock::now();
    // auto duration = chrono::duration_cast<chrono::milliseconds>(stop - start); 
    // cout<<"Time taken by function: "<<duration.count()<<" milliseconds"<<endl;

    // *( hsh.find_by_order(k) ) kth smallest, from 0
    // hsh.order_of_key(k) num of ele str less than k
    // change less to less_equal for multiset pbds
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
char s[432000];
int main(){
	scanf("%s",s+1);
	int len=strlen(s+1);
	int ans=0;
	for (int i=2;i<=len;i++)
	if (s[i]!=s[i-1]) ans++;
	printf("%d",ans);
}


Measured memory_bytes: 3856
def calculate(arr):
    length = len(arr)
    s1 = (length // 2) - 1
    s2 = (length // 2)

    if arr[s2] == arr[s1]:
        return 0
    else:
        return arr[s2] - arr[s1]

N = int(input())

if N == 0:
    result = 0
else:
    list = list([int(s) for s in  input().split(" ")])
    list.sort()
    result = calculate(list)

print(result)

Measured memory_bytes: 14428
#![allow(unused_imports, unused_macros, dead_code)]

macro_rules! min {
    ($x:expr) => ($x);
    ($x:expr, $($ys:expr),*) => {{
        let t = min!($($ys),*);
        if $x < t { $x } else { t }
    }}
}
macro_rules! max {
    ($x:expr) => ($x);
    ($x:expr, $($ys:expr),*) => {{
        let t = max!($($ys),*);
        if $x > t { $x } else { t }
    }}
}

macro_rules! ewriteln {
    ($($args:expr),*) => { let _ = writeln!(&mut std::io::stderr(), $($args),*); };
}
macro_rules! trace {
    ($x:expr) => { ewriteln!(">>> {} = {:?}", stringify!($x), $x) };
    ($($xs:expr),*) => { trace!(($($xs),*)) }
}
macro_rules! put {
    ($x:expr) => { println!("{}", $x) };
    ($x:expr, $($xs:expr),*) => { print!("{} ", $x); put!($($xs),*) }
}

const M: i64 = 1_000_000_007;

fn main() {
    let mut sc = Scanner::new();
    let n: isize = sc.cin();
    let ell: isize = sc.cin();
    put!(n*(n-1)/2+n*ell - (0..n).map(|i|(ell + i)).min_by_key(|x|x.abs()).unwrap())
}

use std::io::{self, Write};
use std::str::FromStr;
use std::collections::VecDeque;

struct Scanner { stdin: io::Stdin, buffer: VecDeque<String>, }
impl Scanner {
    fn new() -> Self { Scanner { stdin: io::stdin(), buffer: VecDeque::new() } }
    fn cin<T: FromStr>(&mut self) -> T {
        while self.buffer.len() == 0 {
            let mut line = String::new();
            let _ = self.stdin.read_line(&mut line);
            for w in line.split_whitespace() {
                self.buffer.push_back(String::from(w));
            }
        }
        self.buffer.pop_front().unwrap().parse::<T>().ok().unwrap()
    }
}


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

namespace lec4C
{
    class Program
    {
        const  int PN = 1056563;
        public static string[] dic = new string [PN];

        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            for (int i = 0; i < n; i++)
            {
                string [] input = Console.ReadLine().Split(' ');
                if (input[0] == "insert")
                {
                    Insert(input[1]);
                }
                else if(input[0] == "find")
                {
                    if (Find(input[1]) == true)
                    {
                        Console.WriteLine("yes");
                    }
                    else
                    {
                        Console.WriteLine("no");
                    }
                }
            }

            Console.ReadLine();

        }

        static bool Find (string t)
        {
            ulong key = ConvertKey(t) ,i =0;
            while (true)
            {
                ulong h = (H1(key) + i * H2(key)) % PN;
                if (dic[h] == t) { return true; }
                else if (dic[h] == null)
                {
                    return false;
                }
                i++;
            }
        }

        static void Insert(string t)
        {
            ulong key = ConvertKey(t) , i =0;
            while(true)
            {
                ulong h =( H1(key) + i * H2(key))% PN;
                if(dic[h] == t) { return; }
                else if (dic[h] == null)
                {
                    dic[h] = t;
                    return;
                }
                i++;
            }
        }

        static ulong H1(ulong k) { return k % PN; }
        static ulong H2(ulong k) { return 1 + (k % (PN - 1)); }

        static ulong  CnvChar(char i)
        {
            if(i == 'A') { return 1; }
            else if (i == 'C') { return 2; }
            else if (i == 'G') { return 3; }
            else if (i == 'T') { return 4; }
            return 0;
        } 
        static ulong ConvertKey(string s)
        {
            ulong key = 0 ,x = 1;
            foreach(var i in s)
            {
                key += x * (CnvChar(i));
                x *=5;
            }
            return key;
        }
    }
}



Measured memory_bytes: 42104
#include <iostream>
#include <algorithm>
#include <iterator>

#include <vector>
#include <queue>
#include <unordered_map>

using namespace std;

int main(){
    uint64_t N;
    cin>>N;
    uint64_t answer = N*(N-1)/2;
    cout<<answer<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll GCD(ll x,ll y){
    if(y == 0) return x;
    else return GCD(y,x%y);
}

int main() {
    ll N,K;
    cin >> N >> K;
    cout << min(N%K,K-N%K) << endl;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define repr(i, n) REPR(i, n, 0)
#define REPR(i, s, e) for(int i=(int)(s-1); i>=(int)(e); i--)
#define pb push_back
#define all(r) r.begin(),r.end()
#define rall(r) r.rbegin(),r.rend()
#define fi first
#define se second

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const ll INF = 1e9;
const ll MOD = 1e9 + 7;
const double EPS = 1e-8;

template<typename T> T chmax(T& a, const T& b){return a = (a > b ? a : b);}
template<typename T> T chmin(T& a, const T& b){return a = (a < b ? a : b);}



int main(){
    int n, k;
    cin >> n >> k;
    vector<int> score(3);
    rep(i, 3) cin >> score[i];
    string s;
    cin >> s;
    vector<string> t(k);
    rep(i, n) {
        t[i%k] += s[i];
    }
    // rep(i, s.size()) cout << 
    auto calc = [&](const string& s) {
        int n = s.size();
        vector<vi> dp(n+1, vi(3, 0));
        rep(i, n) {
            if(s[i] == 'r') {
                chmax(dp[i+1][0], max(dp[i][1], dp[i][2]));
                chmax(dp[i+1][1], max(dp[i][0], dp[i][2]));
                chmax(dp[i+1][2], max(dp[i][0], dp[i][1])+score[2]);
            }
            if(s[i] == 's') {
                chmax(dp[i+1][0], max(dp[i][1], dp[i][2])+score[0]);
                chmax(dp[i+1][1], max(dp[i][0], dp[i][2]));
                chmax(dp[i+1][2], max(dp[i][0], dp[i][1]));
            }
            if(s[i] == 'p') {
                chmax(dp[i+1][0], max(dp[i][1], dp[i][2]));
                chmax(dp[i+1][1], max(dp[i][0], dp[i][2])+score[1]);
                chmax(dp[i+1][2], max(dp[i][0], dp[i][1]));
            }
        }
        // cout << s << endl;
        // rep(i, n+1) {
        // 	rep(j, 3) cout << " " << dp[i][j];
        // 	cout << endl;
        // }
        return max({dp[n][0], dp[n][1], dp[n][2]});
    };
    ll ans = 0LL;
    rep(i, t.size()) ans += calc(t[i]);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 5888
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;

int main() {
  int N;
  while (cin >> N, N) {
    auto xs = vector<int>(N + 4);
    auto ys = vector<int>(N + 4);
    auto window = vector<P>(N);
    for (int i = 0; i < N; ++i) {
      int x, y; cin >> x >> y;
      window[i] = {x, y};
      xs[i] = x;
      ys[i] = y;
    }

    auto curtain = vector<P>(4);
    for (int i = 0; i < 4; ++i) {
      int a, b; cin >> a >> b;
      curtain[i] = {a, b};
      xs[N + i] = a;
      ys[N + i] = b;
    }

    sort(begin(xs), end(xs)); xs.erase(unique(begin(xs), end(xs)), end(xs));
    sort(begin(ys), end(ys)); ys.erase(unique(begin(ys), end(ys)), end(ys));

    auto cover = [](vector<P> &v, double X, double Y) {
      int res = 0;
      for (int cur = 0; cur < v.size(); ++cur) {
        int nxt = (cur + 1) % v.size();
        int sx, sy, tx, ty;
        tie(sx, sy) = v[cur];
        tie(tx, ty) = v[nxt];
        if (sx == tx && X < sx) {
          int ly = min(sy, ty);
          int uy = max(sy, ty);
          if (ly < Y && Y < uy) ++res;
        }
      }
      return res % 2 == 1;
    };

    int ans = 0;
    for (int i = 0; i < xs.size() - 1; ++i) {
      for (int j = 0; j < ys.size() - 1; ++j) {
        int S = (xs[i + 1] - xs[i]) * (ys[j + 1] - ys[j]);
        double px = (xs[i] + xs[i + 1]) / 2.0;
        double py = (ys[j] + ys[j + 1]) / 2.0;
        if (cover(window, px, py) && !cover(curtain, px, py)) ans += S;
      }
    }
    cout << ans << endl;
  }
  return 0;
}



Measured memory_bytes: 3148
#include <iostream>

using namespace std;

int main()
{
	while (1){
		int n, m, bu[510] = {0}, a[10010] = {0}, b[10010] = {0}, ans = 0;
		int bui[510] = {0};
		cin >> n >> m;

		if (m == 0) break;

		for (int i = 0; i < m; i++){
			cin >> a[i] >> b[i];
			if (a[i] == 1) bu[b[i]]++;
		}
		for (int i = 1; i <= n; i++){
			if (bu[i] >= 1){
				for (int j = 1; j <= m; j++){
					if (a[j] == i){
						bui[b[j]]++;
					}
					if (b[j] == i){
						bui[a[j]]++;
					}
				}
			}
		}
		for (int i = 2; i <= n; i++){
			if (bu[i] >= 1 || bui[i] >= 1) ans++;
		}
		cout << ans << endl;
	}
	return 0;
}

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

using namespace std;
int main()
{
    string s;
    cin >> s;

    if (s[0] == 'A') {
        if (isupper(s[1]) || isupper(s[s.size()-1])) {
            cout << "WA\n";
            return 0;
        }
        else {
                int c = 0;
                for (int i = 2; i < s.size()-1; i++) {
                    if (s[i] == 'C')
                        c++;
                }
                if (c != 1) {
                    cout << "WA\n";
                    return 0;
                }
                
                for (int i = 0; i < s.size(); i++) {
                    if (s[i] != 'A' && s[i] == 'B' && isupper(s[i])) {
                        cout << "WA\n";
                        return 0;
                    }
                        
                }
                cout <<"AC\n";
        }
        
    }
    else
        {
        cout << "WA\n";
    }
    return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<61);
const int inf=(1<<30);
const int nmax=1e5+50;
const int mod=1e9+7;
using namespace std;
string s;
int i,x;
int main()
{
    //freopen("dijkstra.in","r",stdin);
    //freopen("dijkstra.out","w",stdout);
    ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
    cin>>s>>x;
    for(i=0;i<s.size();i+=x)cout<<s[i];
    cout<<endl;
    return 0;
}


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

int main(void) {
    int n;
    string s;

    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;
    cin >> s;
    cout << (n % 2 == 0 && s.substr(0, n / 2) == s.substr(n / 2, n)? "Yes" : "No") << "\n";
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include<math.h>
int main(void){
   double x1,x2,y1,y2, a;
   scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);
   a=(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
   a=sqrt(a);
   printf("%f", a);
   return 0;
}



Measured memory_bytes: 2104
def ds(n):
    tmp_n = n
    dsum = 0
    while tmp_n > 0:
        dsum = dsum + tmp_n%10
        tmp_n = tmp_n // 10
    return dsum

N = int(input())

if N % ds(N) == 0:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 2940
#ABC 084 D
def primes(n):
    is_prime = [1] * (n + 1)
    is_prime[0] = 0
    is_prime[1] = 0
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = 0
    return [is_prime[i] for i in range(n + 1)]

era=primes(10**5)
like=[0]*(10**5)        #2は2017に似ていない
for i in range(3,10**5,2):
    if era[i] and era[int((i+1)/2)]:
        like[i]=1

cusum=[0]*(10**5)
for i in range(3,10**5,2):
    cusum[i]=cusum[i-2]+like[i]

q=int(input())
for _ in range(q):
    l,r=map(int,input().split(' '))
    if l==1:
        print(cusum[r])
    else:
        print(cusum[r]-cusum[l-2])

Measured memory_bytes: 6792
#include <iostream>
#include <string>
#include <cstdlib>
#include <vector>
#include <array>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>
#define _USE_MATH_DEFINES
#include <cmath>
#include <climits>
#include <cstdio>
#include <iomanip>
#include <utility>
#include <unordered_map>

using namespace std;
typedef long long int ll;

#define SP(x) setprecision((int)x)
#define ALL(v) v.begin(), v.end()

/* デカい配列はここで宣言 */

int main(int argc, char const *argv[])
{
    string s;
    cin >> s;
    vector<ll> v(s.size() + 1, 0);

    ll _max = 0;
    ll stk = 0;

    if (s[0] == '<')
    {
        v[0] = 0;
    }
    else
    {
        stk++;
    }

    ll ans = 0;

    for (ll i = 1; i < s.size(); i++)
    {
        if (s[i - 1] == '>' && s[i] == '<')
        {
            v[i] = 0;
            // stkの数に応じてansに足してもよいかも
            ans += stk * (stk - 1) / 2;
            ans += max(_max, stk); // maxかstkの大きいほう？
            _max = 0;
            stk = 0;
        }
        else if (s[i - 1] == '<' && s[i] == '<')
        {
            v[i] = v[i - 1] + 1;
            ans += v[i];
            _max++;
        }
        else if (s[i - 1] == '>' && s[i] == '>')
        {
            // v[i]決まらない
            stk++;
        }
        else if (s[i - 1] == '<' && s[i] == '>')
        {
            // v[i]決まらない
            stk++;
            _max++;
        }
    }

    if (s[s.size() - 1] == '>')
    {
        v[s.size()] = 0;
        // stkの数に応じてansに足してもよいかも
        ans += stk * (stk - 1) / 2;
        ans += max(_max, stk); // maxかstkの大きいほう？
    }
    else
    {
        v[s.size()] = v[s.size() - 1] + 1;
        ans += v[s.size()];
    }

    cout << ans << endl;
}

Measured memory_bytes: 4740
#include <stdio.h>

int main(int argc, const char * argv[]) {
    
    int A = 0;
    int B = 0;
    int N = 0;
    int result = 0;
    int resultAncer = 0;
    
    scanf("%d",&N);
    
    result = 0;
    A = 1; //1
    B = N - 1; //14
    
    while (A > 9) {
        result = result + A % 10;
        A = A / 10;
    }
    result = result + A;
    
    while (B > 9) {
        result = result + B % 10;
        B = B / 10;
    }
    result = result + B;
    
    resultAncer = result;
    
    
    for (int i = 2; i < N; i++) {
        result = 0;
        A = i; //1
        B = N - i; //14
        
        while (A > 9) {
            result = result + A % 10;
            A = A / 10;
        }
        result = result + A;
        
        while (B > 9) {
            result = result + B % 10;
            B = B / 10;
        }
        result = result + B;
        
        if (result < resultAncer) {
            resultAncer = result;
        }
    }
    
    printf("%d",resultAncer);
    
    return 0;
}


Measured memory_bytes: 128
//大文字->小文字 tolower(),逆はtoupper()
//int a = stoi(c); 文字列をintへ
//途中の出力をそのまま残さない
//数値計算 個数以外はdouble
//map<キー,値> p は辞書。p[キー] = 値
//map 全探索
//auto begin = p.begin(), end = p.end();
//for (auto it = begin; it != end; it++) {}
//mapのキー：it->first mapのバリュー：it->second
//絶対値 abs()
//入力は空白で切れる
//大文字判定 isupper(文字) 小文字判定 islower(文字)
//do{}while(next_permutation(ALL(配列)))
//while(N)で回すとき、Nはコピーを作っておく
//小文字に対応する文字コード：S[i] - 'a'
//文字コード→小文字：(char)(数字+'a')
//グラフの距離:隣接行列で扱う
//等価なものに変換する思考
//bool型　初期値はTrue
//島渡りの問題：中間ノードに着目
#include <bits/stdc++.h>
#define rep(i,N) for(int i = 0; i < N;i++)
#define ALL(a) (a).begin(),(a).end()
#define ll long long int
using namespace std;

// K進数でのNの桁数
ll dig(ll N,ll K) {
	ll dig = 0;
	while (N) {
		dig++;
		N /= K;
	}
	return dig;
}
// a,bの最大公約数
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b,a%b);
}

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

//nC2の計算
ll C(ll N) {
	return N * (N - 1) / 2;
}

//円周率
const double PI = 3.14159265358979323846;

int main() {
	ll N; cin >> N;
	vector<ll> a(N); rep(i, N)cin >> a[i];

	sort(ALL(a));

	vector<ll> cnt(a[N - 1] + 1);
	rep(i, N) cnt[a[i]]++;
	

	ll mx = cnt[0] + cnt[1];
	for (int i = 1; i <= a[N - 1]; i++) {
		if (i == a[N - 1]) {
			mx = max(mx, cnt[i - 1] + cnt[i]);
			continue;
		}
		mx = max(mx, cnt[i - 1] + cnt[i] + cnt[i + 1]);
	}

	cout << mx << endl;
}


Measured memory_bytes: 1792
#include <stdio.h>

int main(void){
  char o[55] = { '\0' };
  char e[55] = { '\0' };
  scanf("%s", o);
  scanf("%s", e);
  int flag = 1;
  int oc = 0;
  int ec = 0;
  while(o[oc] != '\0') oc++;
  while(e[ec] != '\0') ec++;
  if(oc == ec){
    for(int i = 0; i < oc; i++) printf("%c%c", o[i], e[i]);
  }else{
    for(int i = 0; i < ec; i++) printf("%c%c", o[i], e[i]);
    printf("%c", o[oc - 1]);
  }
  printf("\n");
  return 0;
}


Measured memory_bytes: 128
import sys
N,M = map(int,input().split())
if (N,M) == (1,0):
    print('0')
    sys.exit(0)
res = ['a' for _ in range(N)]
for i in range(M):
  s,c = map(int,input().split())
  if res[s-1] != 'a' and res[s-1] != str(c):
    print('-1')
    sys.exit(0)
  else:
    res[s-1] = str(c)
for i in range(N):
    if res[i] == 'a':
        if i == 0:
            res[i] = '1'
        else:
            res[i] = '0'
st = ''
for i in range(N):
  st += res[i]
if st[0] == '0' and len(st) > 1:
  print('-1')
  sys.exit(0)
print(st)

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

using namespace std;

int main()
{
    long long a,b,c,ans,i,m,n;
    while(scanf("%lld%lld%lld",&a,&b,&c)==3)
    {
        if(a>=b&&a>=c)
        {
            m=(a/2)*b*c;
            n=(a-(a/2))*b*c;
            ans=abs(n-m);
        }
        else if(b>=a&&b>=c)
        {
            m=(b/2)*a*c;
            n=(b-(b/2))*a*c;
            ans=abs(n-m);
        }
        else if(c>=a&&c>=b)
        {
            m=(c/2)*a*b;
            n=(c-(c/2))*a*b;
            ans=abs(n-m);
        }

        printf("%lld\n",ans);

    }


    return 0;
}


Measured memory_bytes: 256
def gdc_euclid(u, v):
    r = 0
    while 0 != v:
        r = u % v
        u = v
        v = r
    return u


# 最大公約数を出す問題かな？
if __name__ == '__main__':
    n = int(input())
    monsters = list(map(int, input().split()))

    before = 0
    for a in monsters:
        if before == 0:
            before = a
        else:
            before = gdc_euclid(a, before)

    print(before)


Measured memory_bytes: 15020
def divisor(n):
    # nの約数列挙
    ass = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            ass.append(i)
            if i**2 == n:
                continue
            ass.append(n//i)
    return ass  # sortされていない


N = int(input())
*a, = map(int, input().split())
a = [0]+a
b = []
c = [0]*(N+1)

for i in range(N, 0, -1):
    if c[i] % 2 != a[i]:
        b.append(i)
        for d in divisor(i):
            if i % d == 0:
                c[d] += 1

print(len(b))
if len(b) > 0:
    print(*b)


Measured memory_bytes: 73948
#include <iostream>
#include <vector>
#define llint long long

using namespace std;

llint N;
llint a[1005];
vector<llint> ovec, evec, vec;
vector<llint> ans;

int main(void)
{
	cin >> N;
	bool flag = false;
	for(int i = 1; i <= N; i++){
		cin >> a[i];
		if(a[i] >= 0) flag = true;
	}
	
	if(!flag){
		llint max_val = -1e18, max_i;
		for(int i = 1; i <= N; i++){
			if(max_val < a[i]){
				max_val = a[i];
				max_i = i;
			}
		}
		cout << max_val << endl;
		cout << N-1 << endl;
		for(int i = N; i > max_i; i--) cout << i << endl;
		for(int i = 1; i < max_i; i++) cout << 1 << endl;
		return 0;
	}
	
	llint odd = 0, even = 0;
	for(int i = 1; i <= N; i++){
		if(a[i] < 0) continue;
		if(i % 2) odd += a[i], ovec.push_back(i);
		else even += a[i], evec.push_back(i);
	}
	
	cout << max(odd, even) << endl;
	if(odd > even) for(int i = 0; i < ovec.size(); i++) vec.push_back(ovec[i]);
	else for(int i = 0; i < evec.size(); i++) vec.push_back(evec[i]);
	
	//for(int i = 0; i < vec.size(); i++) cout << vec[i] << " "; cout << endl;
	
	llint dif = 0;
	for(int i = N; i > vec.back(); i--){
		ans.push_back(i);
	}
	for(int i = 1; i < vec[0]; i++){
		ans.push_back(1);
		dif++;
	}
	for(int i = 0; i < vec.size()-1; i++){
		llint span = vec[i+1] - vec[i];
		for(int j = 0; j < (span+1)/2; j++){
			ans.push_back((vec[i] + vec[i+1]) / 2 - dif);
			dif++;
		}
		dif = vec[i+1]-1;
	}
	
	cout << ans.size() << endl;
	for(int i = 0; i < ans.size(); i++){
		cout << ans[i] << endl;
	}
	return 0;
}

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

ll fanc(ll n) {
  if (n==1) return 1ll;
  return n*fanc(n-1)%MOD;
}

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

  ll ans;
  if (abs(n-m)<=1) {
    ans=fanc(n)*fanc(m)%MOD;
    if (abs(n-m)==0) ans=ans*2%MOD;
  }
  else ans=0;

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

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

//INSERT ABOVE HERE
signed main(){
  Int n;
  while(cin>>n,n){
    Int cnt=n/2,i;
    for(i=1;i*i<n/2;i++) cnt+=(n/2+i-1)/i;
    cnt=cnt*2-i*i;
    cout<<(cnt+n)*8<<endl;
  }
  return 0;
}



Measured memory_bytes: 3012
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long n,i,j,k,l,h,w;
    cin>>h>>w;
    char arr[h+10][w+10];
    for(i=1;i<=h;i++)
    {
        for(j=1;j<=w;j++)
        {
            cin>>arr[i][j];
        }
    }
    for(i=0;i<=h+1;i++)
    {
        for(j=0;j<=w+1;j++)
        {
            if(i>=1&&i<=h)
            {
                if(j>=1&&j<=w)
                {
                    cout<<arr[i][j];
                }
                else
                {
                    cout<<"#";
                }
            }
            else
            {
                cout<<"#";
            }
        }
        cout<<endl;
    }
return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>

using ll = long long int;
using P = std::pair<int, int>;
const int INF = (1<<30);
const ll INFLL = (1ll<<60);
const ll MOD = (ll)(1e9+7);

#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	a = (a<MOD)?a:(a-MOD);
	b = (b<MOD)?b:(b-MOD);
	a += b;
	a = (a<MOD)?a:(a-MOD);
}

int c[555555],e[555555],bitree[555555],ans[555555];
std::vector<int> d[555555];
std::vector<P> f[555555];

int query(int x){
	int v = 0;
	while(x){
		v += bitree[x];
		x -= (x&-x);
	}
	return v;
}

void update(int x, int v = 1){
	while(x<555555){
		bitree[x] += v;
		x += (x&-x);
	}
}

int main(void){
	int n,q,i,j,k,l,r,tt=0;
	std::cin >> n >> q;
	for(i=0; i<n; ++i){
		std::cin >> c[i]; --c[i];
		if(e[c[i]]+1<=i){
			d[e[c[i]]+1].push_back(i);
		}
		e[c[i]] = i+1;
	}
	for(i=0; i<555555; ++i){
		if(e[i]<n){
			d[e[i]+1].push_back(n);
		}
	}
	for(i=0; i<q; ++i){
		std::cin >> l >> r;
		f[l].push_back(P(r-1,i));
	}
	for(i=0; i<555555; ++i){
		for(j=0; j<d[i].l_ength(); ++j){
			update(d[i][j]);
			++tt;
		}
		for(j=0; j<f[i].l_ength(); ++j){
			ans[f[i][j].second] = 555555-(tt-query(f[i][j].first));
		}
	}
	for(i=0; i<q; ++i){
		std::cout << ans[i] << std::endl;
	}
	return 0;
}


Measured memory_bytes: 65384
from bisect import bisect_left
from collections import deque
N,M = map(int,input().split())
PY = []
S =[[] for _ in range(N)]

for i in range(M):
    PY.append(list(map(int,input().split())))
    S[PY[i][0]-1].append(PY[i][1])

for i in range(N):
	S[i].sort()

for i in range(M):
    x = bisect_left(S[PY[i][0]-1],PY[i][1])+1
    print(str(PY[i][0]).zfill(6)+str(x).zfill(6))

Measured memory_bytes: 37008
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp> 
//#include <ext/pb_ds/tree_policy.hpp>
//#include <functional> // for less
//using namespace __gnu_pbds;

#define max_(x, y) (((x) > (y)) ? (x) : (y))
#define min_(x, y) (((x) < (y)) ? (x) : (y))
#define ___ ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
#define Mx 200001
#define inf 1e15
const int MOD = 1e9+7;
const double pi = 2 * acos (0.0);

/*------------------------------Graph Moves----------------------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*---------------------------------------------------------------------*/


typedef long long  L;
//typedef tree<L,null_type,less<L>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

L a1,a2,a3,b1,b2,b3,c,c1,c2,c3,d,d1,d2,d3,d4,d5,e1,e2,e3,f,h,k,l,m,n,m1,m2,n1,n2,o,p,p1,p2,p3,p4,q,q1,q2,q3,q4,r,s,t,
u,v,x,y,z,sum,mx=-inf,mn=inf,flg,flg1,flg2,id1,id2,id3,id4,lim;

//double rat;
L A[Mx+5],B[Mx+5];

char str[Mx];

// vector<L>V,V1;
// set<L>S;
// map<L,L>Mp;
// priority_queue<L>Pq;

//struct node{L nid,nv;node(L nid_,L nv_){nid=nid_;nv=nv_;}};
//vector<node>V;
void solve(){
    c=c/n;c1=c+1;
    d1=0;d2=0;
    for(L i=0;i<n;i++){
        d1+=(abs(A[i]-c)*abs(A[i]-c));
        if(c%n)d2+=(abs(A[i]-c1)*abs(A[i]-c1));
    }
    if(c%n)d1=min(d1,d2);
    printf("%lld\n",d1);
}
int main()
{
    scanf("%lld",&n);
    for(L i=0;i<n;i++){
        scanf("%lld",&d);
        A[i]=d;
        c+=d;
    }
    solve();
    return 0;
}
/// lld I64d push_back() top() pop() insert() upper_bound() lower_bound() memset() max() min() scanf continue 


Measured memory_bytes: 256
str = gets
s1 = []
s2 = []
i = 0
total = 0

str.chars do |c|
  case c
  when '/' then
    if s1[-1]
      j = s1.pop
      s = i - j
      total += s
      while s2[-1] && s2[-1][0] > j
        s += s2.pop[1]
      end
      s2 << [j, s]
    end
  when '_' then
    # nop
  when '\\' then
    s1 << i
  end
  i += 1
end
puts total
if total == 0
  puts s2.length
else
  puts "#{s2.length} #{s2.map{|n| n[1]}*' '}"
end

Measured memory_bytes: 9108
/*
				   _ooOoo_
				  o8888888o
				  88" . "88
				  (| -_- |)
				  O\  =  /O
			   ____/`---'\____
			 .'  \\|     |//  `.
			/  \\|||  :  |||//  \
		   /  _||||| -:- |||||-  \
		   |   | \\\  -  /// |   |
		   | \_|  ''\---/''  |   |
		   \  .-\__  `-`  ___/-. /
		 ___`. .'  /--.--\  `. . __
	  ."" '<  `.___\_<|>_/___.'  >'"".
	 | | :  `- \`.;`\ _ /`;.`/ - ` : | |
	 \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
				   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
		fozubaoyou    pass System Test!
		quoted from "https://codeforces.com/contest/472/submission/7996840"
*/
 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define fin(ans) cout<<(ans)<<endl
#define STI(s) atoi(s.c_str())
#define mp(p,q) make_pair(p,q)
#define pb(n) push_back(n)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define Sort(a) sort(a.begin(),a.end())
#define Rort(a) sort(a.rbegin(),a.rend())
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;}
struct io{io(){ios::sync_with_stdio(false);cin.tie(0);};};
const int MOD = 1000000007;
const int INF = INT_MAX;
const ll LLINF = 1LL<<60;


int main(void){

	string s,t;
	ll k;
	cin>>s>>k;
	ll ans1=0,ans2=0;
	ll n=(int)s.size();
	set<int> se;
	t=s;

	for(int i=0;i<s.size();i++){
		se.insert(s[i]);
	}
	if(se.size()==1){
		cout<<n*k/2<<endl;
		return 0;
	}

	vector<int> v;
	for(int i=0;i<s.size();i++){
		int j=0;
		while(i+j<n&&s[i+j]==s[i]){
			j++;
		}
		v.push_back(j);
		i+=max(j-1,0);
	}
	// for(int i=0;i<v.size();i++){
	// 	cout<<v[i]<<" ";
	// }
	// cout<<endl;
	if(s[0]==s[n-1]){
		for(int i=1;i<v.size()-1;i++){
			ans1+=v[i]/2*k;
		}
		ans1+=v[0]/2+v[v.size()-1]/2+(v[0]+v[v.size()-1])/2*(k-1);
	} else{
		for(int i=0;i<v.size();i++){
			ans1+=v[i]/2*k;
		}
	}
	fin(ans1);
	
}


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

int r;

int main(void){
  // Here your code !
  scanf("%d", &r);
  if (r < 1200) printf("ABC\n");
  else if (1200 <= r && r < 2800) printf("ARC\n");
  else printf("AGC\n");
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int N, X;
    cin >> N >> X;
    
    vector<int> m(N);
    for(int i=0;i<N;i++){
        cin >> m.at(i);
        X -= m.at(i);
    }
    sort(m.begin(),m.end());
    
    int c=0;
    while(X>0){
        X -= m.at(0);
        c++;
    }
    if(X==0)    c++;
    
    cout << c+N-1 << endl;
    
}


Measured memory_bytes: 256