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

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<ii, int> ri3;
#define mp make_pair
#define pb push_back
#define fi first
#define sc second
#define SZ(x) (int)(x).size()
#define ALL(x) begin(x), end(x) 
#define REP(i, n) for (int i = 0; i < n; ++i) 
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define RFOR(i, a, b) for (int i = a; i >= b; --i)

const int MOD = 1e9+7;

int fac(int x) {
    if (x <= 1) return 1;
    int y = 1;
    FOR(i,2,x) y = (ll) y * i % MOD;
    return y;
}

int expo(int b, int p) {
    if (p == 0) return 1;
    if (p == 1) return b;
    int x = expo(b, p/2);
    x = (ll) x * x % MOD;
    if (p&1) x = (ll) x * b % MOD;
    return x;
}

int inv(int x) { return expo(x,MOD-2); }

int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);

    int X, Y; cin >> X >> Y;

    if ((X+Y)%3 != 0) { cout << 0; return 0; }
    if (X < (X+Y)/3 || Y < (X+Y)/3) { cout << 0; return 0; }

    int n = (X+Y)/3;
    int k = X - n;

    cout << (ll) fac(n) * inv(fac(k)) % MOD * inv(fac(n-k)) % MOD;
}



Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <algorithm>
#include <numeric>
#include <utility>
#include <cmath>

using namespace std;

typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;

const int iinf = 1 << 29;
const long long linf = 1ll << 61;

#define dump(x) cerr << #x << " : " << x << '\n'
#define MOD(x, y) (((y) + (x) % (y)) % (y))

int ar[100];

int main(int argc, char* argv[])
{
	int N;
	scanf("%d", &N);
	int ans = 0;
	for (int i = 0; i < N; i++) {
		int d;
		scanf("%d", &d);
		d--;
		ans += 1 - ar[d];
		ar[d] = 1;
	}
	printf("%d\n", ans);

	return 0;
}


Measured memory_bytes: 256
#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>
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<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 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;}
const int P = 1000000007;
const int INF = INT_MAX;
const long long LLINF = 1LL<<60;
//g++ -std=c++1z main.cpp
//.\a.exe

int main(void){ios::sync_with_stdio(false);cin.tie(0);
///////////////////////////////////////////////////////
 	string s;
 	cin >> s;
	if(s[0]==s[1] && s[1]==s[2] && s[2]==s[3]){
		cout << "No" << endl;
	}
	else if(s[0]==s[1] && s[2]==s[3]){
		cout << "Yes" << endl;
 	}
	else if(s[0]==s[2] && s[1]==s[3]){
		cout << "Yes" << endl;
	} 
	else if(s[0]==s[3] && s[1]==s[2]){
		cout << "Yes" << endl;
	}
    else{
		cout << "No" << endl;
	}

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

Measured memory_bytes: 256
<?php
fscanf(STDIN,"%d %d",$k,$z);

$count = 0;

for($a=0; $a <= $k; $a++){
    for($b=0; $b <= $k; $b++){
        $c = $z - ($a + $b);
        if(0 <= $c && $c <= $k){
            $count++;
        }
    }
}

echo $count;

?>

Measured memory_bytes: 4728
use std::io;
use std::cmp::Ordering;
fn read<T: std::str::FromStr>() -> T{
    let mut n = String::new();
    io::stdin().read_line(&mut n).unwrap();
    n.trim().parse().ok().unwrap()
}
fn read_vec<T: std::str::FromStr>() -> Vec<T>{
    let mut n = String::new();
    io::stdin().read_line(&mut n).unwrap();
    n.trim().split_whitespace()
        .map(|e| e.parse().ok().unwrap()).collect()
}
fn main() {
    let mut n: Vec<i32> = read_vec();
    n.sort();
    println!("{} {} {}",n[0],n[1],n[2]);
}



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

int c[3][3];

int main() {
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            cin >> c[i][j];
        }
    }

    int six_value[6] = {0, 0, 0, 0, 0, 0};
    six_value[0] = c[0][0] + c[1][1] + c[2][2];
    six_value[1] = c[1][0] + c[2][1] + c[0][2];
    six_value[2] = c[2][0] + c[0][1] + c[1][2];
    six_value[3] = c[2][0] + c[1][1] + c[0][2];
    six_value[4] = c[1][0] + c[0][1] + c[2][2];
    six_value[5] = c[0][0] + c[2][1] + c[1][2];

    bool f = true;
    int now = six_value[0];
    for (int i = 1; i < 6; i++) {
        if (now != six_value[i]) {
            f = false;
            break;
        }
    }

    if (f) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int main(){
    int N, K;
    cin >> N >> K;
    string S;
    cin >> S;
    int cnt = 0, cnt2 = 0;
    for(int i = 0; i < N - 1; i++){
        if(S[i] == 'L' && S[i + 1] == 'R') cnt2++;
        else if(S[i] == 'R' && S[i + 1] == 'L') cnt++;
    }
    if(cnt2 + cnt <= 2*K){
        cout << N - 1 << endl;
        return 0;
    }
    for(int i = 0; i < K; i++){
        if(cnt == 0 && cnt2 == 0) break;
        if(cnt == 0 && cnt2 != 0) cnt2--;
        else{
            cnt--;
            cnt2--;
        }
    }
    cout << N - 1 - cnt - cnt2 << endl;
}

Measured memory_bytes: 512
li = []
a, b = map(int,input().split())
for i in range(a):
    li.append(list(input()))

for i in range(a):
    for j in range(b):
        if li[i][j] == '.':
            li[i][j] = 0
            if i!=0 and li[i-1][j]=='#':
                li[i][j]+=1
            if i!=a-1 and li[i+1][j]=='#':
                li[i][j]+=1
            if j!=0 and li[i][j-1]=='#':
                li[i][j]+=1
            if j!=b-1 and li[i][j+1]=='#':
                li[i][j]+=1
            if i!=0 and j!=0 and li[i-1][j-1]=='#':
                li[i][j]+=1
            if i!=a-1 and j!=0 and li[i+1][j-1]=='#':
                li[i][j]+=1
            if i!=0 and j!=b-1 and li[i-1][j+1]=='#':
                li[i][j]+=1
            if i!=a-1 and j!=b-1 and li[i+1][j+1]=='#':
                li[i][j]+=1
        print(li[i][j],end="")
    print()

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

signed main(){
    int a[200005] , route[200005] , firstin[200005] = {} , looplen , loopin=0;
    long long n , k;
    bool f = true;
    
    cin >> n >> k;
    for(int i=0 ;i<n ;i++ ){
        cin >> a[i];
        firstin[i+1] = -1;
    }
    
    firstin[1] = 0;
    route[0] = 1;
    for(long long i=1 ;i<=k && f ;i++ ){
        route[i] = a[route[i-1]-1];
        if(i == k){
            cout << route[k] << endl;
        } else if(firstin[route[i]] != -1){
            looplen = i - firstin[route[i]];
            loopin = firstin[route[i]];
            k -= loopin;
            cout << route[loopin + k%looplen] << endl;
            f = false;
        } else {
            firstin[route[i]] = i;
        }
    }
 
    return(0);
}

Measured memory_bytes: 5780
S = gets.chomp.to_i
A = gets.chomp.split().map(&:to_i)
B = gets.chomp.split().map(&:to_i)
res = 0
S.times do |n|
    res += A[n-1]-B[n-1] if A[n-1]>B[n-1]
end
puts res

Measured memory_bytes: 1788
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = new Integer(sc.next());
        int b = new Integer(sc.next());
        int c = sc.nextInt();
        if (a < b && b < c) {
          System.out.println("Yes");
        }else {
          System.out.println("No");
        }
    }
}

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

const int MOD=1000000007;
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3f;
 
int main(){
  //input
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  
  string s ; 
  cin >> s; 
  
  reverse(s.begin(),s.end());
  
  while(s.size()>4){
    if(s.substr(0,5)=="maerd") s=s.substr(5);
    else if(s.substr(0,5)=="esare") s=s.substr(5);
    else if(s.substr(0,6)=="resare") s=s.substr(6);
    else if(s.substr(0,7)=="remaerd") s=s.substr(7);
    else break;
  }
  if(s.size()==0) cout<<"YES"<<endl;
  else cout<<"NO"<<endl;
  
}
  



Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define MOD (int)(1e9+7)
#define ceil(x, y) (x%y==0? (x/y) : (x/y+1))
#define FOR(i, N) for(int i = 0; i < N; ++i)
#define FOR1(i, N) for(int i = 1; i <= N; ++i)
#define vi vector <int>
#define pii pair <int, int>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define mset(a, v) memset(a, v, sizeof(a))
#define all(v) (v).begin(), (v).end()
#define INF 2e9
#define EPS 1e-9
#define MAX 1000009
#define int long long
int freq[MAX], marked[MAX];
/*#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef cc_hash_table<int, int, hash<int>> ht; // while using, comment #define int long long  */

void __print(int x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define dbg(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define dbg(x...)
#endif
using namespace std;
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    #ifndef ONLINE_JUDGE
    	freopen("in.txt", "r", stdin);
    	freopen("out.txt", "w", stdout);
    #endif

	int T=1;
	//cin >> T;
	FOR1(tp, T)
	{
		//cout << "Case #" << tp << ": ";
		//mset(freq, 0); mset(marked, 0);
		int n; cin >> n;
		int a[n+1];
		FOR1(i, n) {
			cin >> a[i];
			freq[a[i]]++;
		}
		int cnt = 0;

		for(int i = 1; i <= MAX; i++){
			if(freq[i] and marked[i] == 0){ // present in array and unamrked
				// all multiples of i from 2*i present in array are to be striked off
				/*The number itself is not marked because of the condition i != j
				But if more than one occurence then number itself also has to be marked*/
				if(freq[i] > 1) marked[i] = true;
				for(int j = 2; j*i < MAX; j++){
					marked[j*i] = 1;
				}

			}
		}
		for(int i = 1; i <= n; i++){
			//cout << marked[a[i]] << " ";
			cnt += !marked[a[i]];
		}
		cout << cnt;
		cout<<'\n';
	}
	return 0;
}


Measured memory_bytes: 20732
import java.util.*

data class Hoge(val p: Int, val s: Boolean, val index: Int)

fun main(args: Array<String>) {
    val (N, M) = readLine()!!.split(" ").map { it.toInt() }
    var success = 0
    var failed = 0
    val ps = Array(M) {
        val list = readLine()!!.split(" ")
        Hoge(list[0].toInt(), list[1] == "AC", it)
    }.groupBy { it.p }.mapValues {
        val tmp = it.value.sortedBy { it.index }
        var suc = 0
        var fail = 0
        for(i in 0 until tmp.size) {
            if (tmp[i].s) {
                suc++
                break
            }
            else {
                fail++
            }
        }
        //println("$suc $fail")
        success += suc
        if (suc > 0)
            failed += fail
    }
    println("$success $failed")
}

Measured memory_bytes: 79540
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <stdio.h>
#include <cstring>
#include <queue>
#include <stack>
#include <functional>
#include <math.h>
using namespace std;
#define Would
#define you

int main() {
	int a, b, c;
	cin >> a >> b >> c;
	string ans;
	if (c + 10 * b + 100 * a == 1 || c + 10 * b + 100 * a == 110) { ans = "Open"; }
	else { ans = "Close"; }
	cout << ans << endl;
}



Measured memory_bytes: 3196
mod = 10**9 + 7

N = int(input())
S = input()

dic = {}
for s in "abcdefghijklmnopqrstuvwxyz":
    dic[s] = 0

for s in S:
    dic[s] += 1

ans = 1
for v in dic.values():
    ans *= v + 1
print((ans - 1) % mod)


Measured memory_bytes: 3188
#include<bits/stdc++.h>
#define maxn 105
using namespace std;
int n,x,a[maxn],dp[maxn],cnt=1;
int main()
{
	cin>>n>>x;
	for(int i=0;i<n;i++)
		cin>>a[i];
	dp[0]=0;
	for(int i=1;i<=n;i++)
	{
		dp[i]=a[i-1]+dp[i-1];
		if(dp[i]<=x)
			++cnt;
	}
	cout<<cnt<<endl; 
	return 0;
}

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

int main(){
  int a,b;
  cin >> a >> b;
  if(a*b==2){
    cout << 3 << endl;
  }else if(a*b==3){
    cout << 2 << endl;
  }else{
    cout << 1 << endl;
  }
  
  return 0;
}

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

using namespace std;

int main(void) {
    int64_t K;
    cin >> K;

    int N = 50;
    vector<int64_t> a(N, N-1 + K/N);
    K %= N;
    for(int i=0; i<K; i++) {
        a[i] += N;
    }
    for(int i=0; i<N; i++) {
        a[i] -= K;
    }
    
    cout << N << endl;
    for(auto e: a) {
        cout << e << ' ';
    }
    return 0;
}


Measured memory_bytes: 256
#include<cmath>
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<set>
#include<vector>
#include<bitset>
#define int unsigned long long
#define hh putchar('\n')
#define kg putchar(' ')
#define lowbit(x) ((x)&(-x))
using namespace std;
const int maxn=1000005,mod=998244353;
int n,isprime[maxn],prime[maxn],num,ans;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
		if(ch=='-')
			f=-1;
		ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
    }
    return x*f;
}
inline void write(int a)
{
    if(a<0)
    {
		putchar('-');
		putchar('1');
    }
    else
    {
		if(a>=10)
			write(a/10);
		putchar(a%10+'0');
    }
}
int calc(int xx,int yy)
{
	return n*(xx-1)+yy-1;
}
int fo()
{
	int kotae=1;
	for(int i=1;i<=18;++i)
		kotae*=10;
	return kotae;
}
void make_prime(int lim)
{
    for(int i=1;i<=lim;++i)
		isprime[i]=1;
    isprime[0]=isprime[1]=0;
    for(int i=2;i<=lim;++i)
    {
        if(isprime[i])
            prime[++num]=i;
        for(int j=1;j<=num&&i*prime[j]<=lim;++j)
        {
            isprime[i*prime[j]]=0;
            if(!(i%prime[j]))
                break;
        }
    }
    return;
}
signed main()
{
	n=read();
	make_prime(1e6);
	for(int i=1;i<=num;++i)
	{
		int tmp,p=prime[i],tot=0,jishuqi=1;
		tmp=p;
		while(n%tmp==0)
		{
			n/=tmp;
			tmp*=p;
			++ans;
		}
		while(n%p==0)
			n/=p;
	}
	if(n>1)
		++ans;
	cout<<ans;
    return 0;
}


Measured memory_bytes: 12064
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
using P = pair<ll, ll>;
const ll INF = 5e15;
const ll MOD = 1e9 + 7;
int main(){
    string S;
    cin >> S;
    string rev = S;
    reverse(rev.begin(), rev.end());
    string key = "keyence";
    for(ll i = 0; i < key.size(); i++){
        string s = key.substr(0, i);
        string t = key.substr(i);
        reverse(t.begin(), t.end());
        if(S.substr(0, s.size()) != s) continue;
        if(rev.substr(0, t.size()) == t){
            cout << "YES\n";
            return 0;
        }
    }
    cout << "NO\n";
    return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
    static int[][] graph;
    static int[] check;
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        long b = 1000000000;
        long x, y;
        if(n%b==0){
            y = n/b;
            x = 0;
        }
        else{
            y = n/b + 1;
            x = y*b-n;
        }
        System.out.println("0 0 1000000000 1 " + x + " " + y);
    }
}

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

long long int dfs(int state,vector<vector<long long int >> &t,map<int,long long int> &dp){
  if(dp.count(state)) return dp[state];
  if(state==(1<<n)-1){
    return 0;
  }
  long long int res=1e15;
  for(int i=0;i<n;i++){
    if(!(state & (1<<i))){
      long long int cost=t[i][0];
      for(int j=0;j<n;j++){
	if(state & (1<<j)){
	  cost=min(cost,t[i][j+1]);
	}
      }
      res=min(res,dfs(state+(1<<i),t,dp)+cost);
    }
  }
  return dp[state]=res;
}
int main(){

  while(cin>>n,n){
    vector<vector<long long int>> t(n,vector<long long int>(n+1,0));
    for(int i=0;i<n;i++){
      for(int j=0;j<n+1;j++){
	cin>>t[i][j];
      }
    }
    map<int,long long int> dp;
    cout<<dfs(0,t,dp)<<endl;
  }
  return 0;
}

Measured memory_bytes: 7044
from collections import Counter

N = int(input())
a=[]
for i in range(N):
    s=input()
    S=[]
    for j in range(10):
        S.append(s[j])
    S.sort()
    s="".join(S).split()
    a.append(s[0])
x=Counter(a)
num=x.values()
#print(list(num))
ans=0
for i in (list(num)):
    ans+=i*(i-1)//2
print(ans)


Measured memory_bytes: 71744
#include<cstdio>
#include<cmath>
#include<climits>
#include<algorithm>
#include<sstream>
#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<unordered_set>
#include<unordered_map>
#include<set>
#include<map>
#include<list>

using namespace std;

#define in(s) cin >> s
#define out(s) cout << s << endl
#define rep(i,n) for(int i=0; i<n; i++)
#define rept(i,a,b) for(int i=a; i<b; i++)
#define ll long long
#define MOD 1000000007

#define IMIN INT_MIN;
#define IMAX INT_MAX;


int main(){
    ll A, B, N;
    in(A); in(B); in(N);
    ll i = N;
    ll ans;
    ans = (A * i) / B - A * (i / B);
    i -= i%B;
    i--;
    ans = max(ans, (A * i) / B - A * (i / B));
    out(ans);


	return 0;
}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
using intl = long long;
#define rep(i, n) for(intl i = 0; i < (intl)(n); i++)
#define repd(i, n) for(intl i = (intl)((n) - 1); i >= 0; i--)
#define repi(i, a, b) for(intl i = (intl)(a); i < (intl)(b); i++)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define INF = 1e9;
#define debug(x) cout << #x << ":" << x << endl
using namespace std;
void fp(bool flag){
    if(flag)cout << "Yes" << endl;
    else cout << "No" << endl;
}
int main(){
    intl a;
    cin >> a;
    intl b;
    cin >> b;
    intl c = b;
    rep(i,a - 1){
        c *= (b - 1);
    }
    cout << c << endl;
    return 0;
}

Measured memory_bytes: 256
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author alireza_kaviani
 */

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

template<class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;

#define all(x)                      (x).begin(),(x).end()
#define Sort(x)                     sort(all((x)))
#define X                           first
#define Y                           second
#define Mp                          make_pair
#define sep                         ' '
#define endl                        '\n'
#define debug(x)                    cerr << #x << " = " << x << endl
#define SZ(x)                       ll(x.size())
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define set_random                  mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

ll poww(ll a, ll b, ll md) {
    return (!b ? 1 : (b & 1 ? a * poww(a * a % md, b / 2, md) % md : poww(a * a % md, b / 2, md) % md));
}

const ll MAXN = 1e6 + 10;
const ll LOG = 22;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; // 998244353; // 1e9 + 9;

ll n, q, L[MAXN], R[MAXN], X[MAXN], D[MAXN];
map<ll, ll> ans;
map<ll, vector<pll>> S, E;
set<pll> st;
vector<ll> vec;

int main() {
    fast_io;

    cin >> n >> q;
    for (ll i = 0; i < n; i++) {
        cin >> L[i] >> R[i] >> X[i];
        S[L[i] - X[i]].push_back({X[i], i});
        E[R[i] - X[i]].push_back({X[i], i});
        vec.push_back(L[i] - X[i]);
        vec.push_back(R[i] - X[i]);
    }
    for (ll i = 0; i < q; i++) {
        cin >> D[i];
        vec.push_back(D[i]);
    }
    Sort(vec);
    vec.resize(unique(all(vec)) - vec.begin());

    for (ll i : vec) {
        for (pll j : S[i]) st.insert(j);
        for (pll j : E[i]) st.erase(j);
        if (st.size() == 0) ans[i] = -1;
        else ans[i] = (*st.begin()).X;
    }
    for (ll i = 0; i < q; i++) cout << ans[D[i]] << endl;

    return 0;
}
/*

*/


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

int main(){
  int n,k;
  cin>>n>>k;
  vector<int> p(n);
  rep(i,n) cin>>p[i];
  sort(p.begin(),p.end());
  int ans=0;
  rep(i,k) ans+=p[i];
  cout<<ans<<endl;
}

Measured memory_bytes: 3628
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#include <list>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
int d;
int c[27];
int s[366][27];
int calc(vector<int> t){
    int last[26]={};
    vector<int> ret(d);
    int ans=0;
    for(int i=0; i<d; i++){
        ans+=s[i][t[i]];
        last[t[i]]=i+1;
        for(int j=0; j<26; j++){
            ans-=c[j]*(i+1-last[j]);
        }
        ret[i]=ans;
    }
    return ans;
}
mt19937 mt(334);

int main()
{
    cin>>d;
    for(int i=0; i<26; i++) cin>>c[i];
    for(int i=0; i<d; i++) for(int j=0; j<26; j++) cin>>s[i][j];
    vector<int> t(d);
    
    int last[26]={};
    for(int i=0; i<d; i++){
        int kmx=0, mx=-1e9;
        for(int k=0; k<26; k++){
            int sum=s[i][k];
            int myon=last[k];
            last[k]=i+1;
            for(int j=0; j<26; j++){
                sum-=c[j]*(i+1-last[j]);
            }
            last[k]=myon;
            if(mx<sum) kmx=k, mx=sum;
        }
        t[i]=kmx;
        last[kmx]=i+1;
    }

    uniform_int_distribution<> rndk(0, d-2);
    clock_t start = clock();
    int ans=calc(t);
    while((double)(clock()-start)/CLOCKS_PER_SEC<1.9){
        int k;
        k=rndk(mt);
        int pr=t[k], q=t[k+1], ansp=ans;
        ans-=s[k][pr];
        ans+=s[k][q];
        int last[2]={};
        for(int i=0; i<d; i++){
            if(t[i]==pr) last[0]=i+1;
            else if(t[i]==q) last[1]=i+1;
            ans+=c[pr]*(i+1-last[0]);
            ans+=c[q]*(i+1-last[1]);
        }
        swap(t[k], t[k+1]);
        last[0]=last[1]=0;
        for(int i=0; i<d; i++){
            if(t[i]==pr) last[0]=i+1;
            else if(t[i]==q) last[1]=i+1;
            ans-=c[pr]*(i+1-last[0]);
            ans-=c[q]*(i+1-last[1]);
        }
        if(ansp>ans){
            swap(t[k], t[k+1]);
            ans=ansp;
        }
    }
    for(int i=0; i<d; i++){
        cout<<t[i]+1<<endl;
    }
	return 0;
}


Measured memory_bytes: 3712
/**
*   Bismillahir Rahmanir Rahim.
*   Imtiaz_rafi
*   PCIU, CHITTAGONG
**/
#include<bits/stdc++.h>
using namespace std;
#define speed ios::sync_with_stdio(0);cin.tie(0);
#define filein freopen ("input.txt", "r", stdin)
#define fileout freopen ("output.txt", "w", stdout)
#define rep(i,a) for(ll i=0;i<a;i++)
#define rep1(i,begin,end) for(ll i=begin;i<=end;i++)
#define all(v)   v.begin(),v.end()
#define pb push_back
#define pf push_front
#define mp make_pair
#define pi acos(-1)
// bitshift (1LL<<(3)) *2^3
typedef long long int ll;
typedef vector<ll>vi;
typedef map<ll,ll>m;
typedef map<char,ll>mc;
typedef set<ll>st;
typedef set<char>sc;

int main()
{
    speed;
    ll t,i,j,a,b,c,d=0,e=0,ans=0;
    for(i=1;i<=5;i++)
    {
        cin>>a;
        if(a==0 && d==0)
            d=i;
    }
    cout<<d<<endl;

}


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

#include <math.h>
#include <stdlib.h>


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



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

    set<string> st;
    st.insert("a");

    for(int i = 1; i < n; i++){
        set<string> stp;
        for(string s : st){
            s.push_back('z');
            int k = -1;
            for(int j = 0; j < i; j++){
                s[i] = s[j];
                k = max(k, int(s[j] - 'a'));
                stp.insert(s);
            }
            s[i] = char('a' + k + 1);
            stp.insert(s);
        }
        st = stp;
    }

    for(string sa : st)cout << sa << endl;
    
    return 0;
}


Measured memory_bytes: 17792
/*
これを入れて実行
g++ code.cpp
./a.out
 */
 
#include <iostream>
#include <stdio.h>
#include <vector>
#include <string>
#include <cstring>
#include <queue>
#include <deque>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <unordered_map>
#include <cmath>
#include <math.h>
#include <tuple>
#include <iomanip>
#include <bitset>
#include <functional>

#define all(x) (x).begin(),(x).end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
 
using namespace std;
typedef long long ll;
typedef long double ld;
 
int dy4[4] = {-1, 0, +1, 0};
int dx4[4] = {0, +1, 0, -1};
int dy8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dx8[8] = {0, 1, 1, 1, 0, -1, -1, -1};
 
const long long INF = 1LL << 62;
const ll MOD = 1e9 + 7;
 
bool greaterSecond(const pair<int, int>& f, const pair<int, int>& s){
    return f.second > s.second;
}
 
ll gcd(ll a, ll b){
	if (b == 0)return a;
	return gcd(b, a % b);
}
 
ll lcm(ll a, ll b){
    return a / gcd(a, b) * b;
}

ll conbinationMemo[100][100];

ll cmemoInit(){
    rep(i, 100){
        rep(j, 100){
            conbinationMemo[i][j] = -1;
        }
    }
}
 
ll nCr(ll n, ll r){
    if(conbinationMemo[n][r] != -1) return conbinationMemo[n][r];
    if(r == 0 || r == n){
        return 1;
    } else if(r == 1){
        return n;
    }
    return conbinationMemo[n][r] = (nCr(n - 1, r) + nCr(n - 1, r - 1));
}
 
ll nPr(ll n, ll r){
    r = n - r;
    ll ret = 1;
    for (ll i = n; i >= r + 1; i--) ret *= i;
    return ret;
}
 
//-----------------------ここから-----------
int main(void){
    ll m, k;
    cin >> m >> k;

    if((ll)pow(2LL, m) <= k){
        cout << -1 << endl;
        return 0;
    }

    vector<ll> ans;

    if(m == 1){
        if(k == 0){
            vector<ll> a = {0, 1, 1, 0};
            rep(i, a.size()){
                cout << a[i] << " ";
            }
        } else {
            cout << -1;
        }
        cout << endl;
        return 0;
    }

    for(ll i = 0; i < (ll)pow(2LL, m); i++){
        if(i == k) continue;
        ans.push_back(i);
    }
    
    ans.push_back(k);

    for(ll i = (ll)pow(2LL, m) - 1; i >= 0; i--){
        if(i == k) continue;
        ans.push_back(i);
    }

    ans.push_back(k);

    rep(i, ans.size()){
        cout << ans[i] << " ";
    }
    cout << endl;
}

Measured memory_bytes: 3952
N, M = map(int,input().split())
dp = [0]*(N+1)
broke = [0]*(N+1)
dp[0] = 1
dp[1] = 1

for _ in range(M):
    a = int(input())
    broke[a] = -1

for i in range(N-1):
    if broke[i] != -1 and broke[i+1] != -1:
        dp[i+2] = dp[i+1] + dp[i]
    elif broke[i] == -1and broke[i+1] != -1:
        dp[i+2] = dp[i+1]
    elif broke[i+1] == -1and broke[i] != -1:
        dp[i+2] = dp[i]
    else:
        print(0)
        exit()
# print(broke)
# print(dp)
MOD = 10**9+7
print(dp[N]%MOD)




Measured memory_bytes: 460788
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout<< (x) << " "

int main(){
    string a,b;cin>>a>>b;
    if(a==b){co("EQUAL");return 0;}
    if(a.size()>b.size()){co("GREATER");return 0;}
    if(a.size()<b.size()){co("LESS");return 0;}
    rep(i,a.size()){
        if(a[i]>b[i]){co("GREATER");return 0;}
        if(a[i]<b[i]){co("LESS");return 0;}
    }

}

Measured memory_bytes: 256
# coding: utf-8
while True:
    H,W=(int(x) for x in input().split())
    if H==0 & W==0:
        break;
    else:
        for i in range(H):
            for j in range(W):
                if j==0 or j==(W-1) or i==0 or i==(H-1):
                    print("#",end="")
                else :
                    print(".",end="")
            print("")
    print("")


Measured memory_bytes: 7020
N = gets.chomp

HON = %w[2 4 5 7 9]
PON = %w[0 1 6 8]
BON = %w[3]

result = if HON.include?(N[-1])
  "hon"
elsif PON.include?(N[-1])
  "pon"
elsif BON.include?(N[-1])
  "bon"
else
  ""
end
puts result
 

Measured memory_bytes: 14368
#include <bits/stdc++.h>
#define INF 2e9
#define MOD 1000000007
#define MOD9 998244353
#define intMAX 51000;
#define PI 3.14159265359
using namespace std;
typedef long long llong;
// typedef long double ldouble;

using Graph = vector<vector<int>>;

// int ctoi(const char c){
//   if('0' <= c && c <= '9') return (c-'0');
//   return -1;
// }

// int gcd(int a, int b){
//   int ma = max(a,b);
//   int mi = min(a,b);
//   if(mi == 0) return ma;

//   return gcd(mi, ma%mi);
// }

// llong POW(llong a, llong b){
//   if(b == 0) return 1;
//   else{
//     if(b%2 == 0) return POW(a * a % MOD, b / 2) % MOD;
//     else return a * POW(a * a % MOD, b / 2) % MOD;
//   }
// }

int main(){
  int A, B;
  cin >> A >> B;
  if(A*B % 3 == 0 || (A+B) % 3 == 0) cout << "Possible" << endl;
  else cout << "Impossible" << endl;
}

Measured memory_bytes: 256
#pragma GCC optimize ("Ofast")
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i=(a); i<(b); i++)
#define FORD(i, a, b) for (int i=(a); i>(b); i--)
#define PPC(x) __builtin_popcount(x)
#define MSB(x) (31 - __builtin_clz(x))
#define SZ(x) ((int)(x).size())
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define ithBit(m, i) ((m) >> (i) & 1)
#define ft first
#define sd second
#define kw(a) ((a) * (a))
#ifdef DEBUG
#include "debug.h"
#else
#define dbg(...) 0
#endif
using namespace std;

const int maxN = 1 << 19;

long long T[maxN];
const long long INF = 1000000000000000000ll;

void solve()
{
	long long a;
	long double b;
	scanf ("%lld%Lf", &a, &b);
	printf("%lld\n", (long long)floor(a * b));
}

int main()
{
	int t = 1;
	//scanf ("%d", &t);
	while (t--)
		solve();
	return 0;
}





Measured memory_bytes: 3796
sx,sy,tx,ty=map(int,input().split())
dx=tx-sx
dy=ty-sy
print('U'*dy+'R'*dx+'D'*dy+'L'*(dx+1)+'U'*(dy+1)+'R'*(dx+1)+'D'+'R'+'D'*(dy+1)+'L'*(dx+1)+'U')

Measured memory_bytes: 3060
def remaining(s1, s2):
    if not('R' in [s1, s2]):
        return 'R'
    elif not('G' in [s1, s2]):
        return 'G'
    else:
        return 'B'

N = int(input())
S = list(input())

# acc[color][i]: i番目からN番目までのcolorの数
acc = {
    'R': [0 for _ in range(N)],
    'G': [0 for _ in range(N)],
    'B': [0 for _ in range(N)]
}
acc[S[-1]][-1] = 1
for i in range(N-2, -1, -1):
    acc[S[i]][i] = acc[S[i]][i+1]+1
    if S[i] == 'R':
        acc['G'][i] = acc['G'][i+1]
        acc['B'][i] = acc['B'][i+1]
    elif S[i] == 'G':
        acc['R'][i] = acc['R'][i+1]
        acc['B'][i] = acc['B'][i+1]
    else:
        acc['G'][i] = acc['G'][i+1]
        acc['R'][i] = acc['R'][i+1]


if __name__ == "__main__":
    ans = 0
    for i in range(N-2):
        for j in range(i+1, N-1):
            if S[i]==S[j]:
                continue
            color = remaining(S[i], S[j])
            ans += acc[color][j+1]
            if j+j-i < N:
                if S[j+(j-i)] != S[i] and S[j+(j-i)] != S[j]:
                    ans -= 1
    print(ans)

Measured memory_bytes: 69184
#include<bits/stdc++.h>
using namespace std;
 
int main(){
  int N, c, n;
  double p;
  cin >> N;
  n = N;
  while(n>0){
    n -=2;
    c++;
  }
  //cout << "N : " << N << endl << "c : " << c << endl << endl;
  p = (double)c/(double)N;
  cout << p << endl;
}

Measured memory_bytes: 256
from itertools import permutations
N, M, *L = map(int, open(0).read().split())
dic = [[] for i in range(N+1)]
for a, b in zip(*[iter(L)]*2):
  dic[a].append(b)
  dic[b].append(a)

ans = 0
for l in permutations(range(2,N+1)):
  l = [1]+list(l)
  for i in range(N-1):
    if l[i+1] not in dic[l[i]]:
      break
  else:
    ans += 1
print(ans)

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

#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, a, b) for (int i = (int)(a); i >= (int)b; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define per(i, r, l) for (int i = (r); i >= (l); i--)
#define ms(x, y) memset(x, y, sizeof(x))
#define SZ(x) ((int)(x).size())

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef double ld;

template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

const i64 mod = (i64)1e9 + 7;
i64 n, a, b;

i64 quickmod(i64 a, i64 b, i64 c) {
    i64 ans = 1;
    while(b) {
        if(b & 1) {
            ans = (ans * a) % c;
        }
        a = (a * a) % c;
        b >>= 1;
    }
    return ans;
}
i64 cc(i64 x, i64 y) {
	i64 tmp = 1;
	for (i64 i = x; i >= x - y + 1; --i) tmp = tmp * i % mod;
	for (i64 i = 1; i <= y; ++i) tmp = tmp * quickmod(i, mod - 2, mod) % mod;
	return tmp;
}


int main() {
	ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.precision(10);
    cout << fixed;
#ifdef LOCAL_DEFIN
    freopen("input.txt", "r", stdin);
#endif

    cin >> n >> a >> b;
    i64 ans = (quickmod(2, n, mod) - 1 + mod) % mod;
    ans = (ans - cc(n, a) + mod) % mod;
    ans = (ans - cc(n, b) + mod) % mod;
    cout << ans << '\n';

#ifdef LOCAL_DEFINE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define Q int tt,qq; cin>>tt ;for(qq=1;qq<=tt;qq++)
#define FAST ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

int main()
{
    int n;
    cin>>n;
    int a,ans=0;
    for(int i=0;i<n;i++){
        cin>>a;
        ans=__gcd(ans,a);
    }
    cout<<ans;
}


Measured memory_bytes: 3616
inputs = open(0).readlines()
n, m = map(int, inputs[0].split())
*H, = map(int, inputs[1].split())
AB = [map(int, ab.split())for ab in inputs[2:]]

C = [[] for _ in range(n)]
for a, b in AB:
    C[a-1].append(H[b-1])
    C[b-1].append(H[a-1])
ans = 0
for c, h in zip(C, H):
    ans += all(h > x for x in c)
print(ans)

Measured memory_bytes: 72700
#include<bits/stdc++.h>
using namespace std;
#define MAX 100005

int n;
set<int> G[MAX];
string C;
int root=-1;

int Flag[MAX];
int base=0;
int sz=0;
int used[MAX];

int Ans=-1e9;

int Solve(int pos,int prev=-1){
  int res=-1;
  if( C[pos]=='B' )
    if( G[pos].size()%2==1 )res=1;
  if( C[pos]=='W' )
    if( G[pos].size()%2==0 )res=1;
  
  Ans=max(Ans, res);
  
  int maxm=0;
  
  vector<int> v;
  for(int to:G[pos]){
    if(to==prev)continue;
    v.push_back( Solve(to,pos) );
    Ans=max( Ans, v.back() + maxm + res );
    maxm=max(maxm, v.back());
  }
  
  return maxm+res+1;
}

void Dfs(int pos,int prev=-1){
  sz++;
  used[pos]=1;
  if( C[pos]=='B' )
    if( G[pos].size()%2==1 )base++;

  if( C[pos]=='W' )
    if( G[pos].size()%2==0 )base++;

  
  for(int to:G[pos]){
    if(to==prev)continue;
    Dfs(to,pos);
  }
}

void dfs(int pos,int prev=-1){
  
  if(C[pos]=='W')Flag[pos]=1;

  set<int> tmp;
  for(int to:G[pos]){
    if(to==prev)continue;
    dfs(to,pos);
    Flag[pos]|=Flag[to];
    if(Flag[to]==0)tmp.insert(to);
  }
  for(int x:tmp)G[pos].erase(x);
}

int solve(){
  dfs(root);
  Dfs(root);

  base+= (sz-1)*2;
  
  Solve(root);

  if(sz==1)return 1;
  return base-Ans-1;
}

int main(){
  cin>>n;
  for(int i=0;i<n-1;i++){
    int x,y;
    cin>>x>>y;
    x--,y--;
    G[x].insert(y);
    G[y].insert(x);
  }
  cin>>C;
  for(int i=0;i<n;i++)
    if(C[i]=='W')root=i;
  if(root==-1){
    cout<<0<<endl;
    return 0;
  }
  cout<<solve()<<endl;
  return 0;
}


Measured memory_bytes: 29312
#include <cstdio>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

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

    vector<pair<int, int> > x(n);
    for(int i=0; i<n; ++i)
        x[i] = make_pair(0, i);

    for(int i=0; i<n*(n-1)/2; ++i){
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        -- a;
        -- b;
        if(c > d)
            x[a].first += 3;
        else if(c < d)
            x[b].first += 3;
        else{
            ++ x[a].first;
            ++ x[b].first;
        }
    }

    sort(x.rbegin(), x.rend());

    vector<int> ret(n);
    for(int i=0; i<n; ++i){
        if(i > 0 && x[i].first == x[i-1].first){
            ret[x[i].second] = ret[x[i-1].second];
        }else{
            ret[x[i].second] = i+1;
        }
    }

    for(int i=0; i<n; ++i)
        cout << ret[i] << endl;
    return 0;
}

Measured memory_bytes: 0
n=int(input())
g=[[] for _ in range(n)]
for _ in range(n-1):
  u,v,w=map(int,input().split())
  g[u-1]+=[(v-1,w%2)]
  g[v-1]+=[(u-1,w%2)]
l=[-1]*n
q=[(0,0)]
while q:
  a,b=q.pop(); l[a]=b
  for c,d in g[a]:
    if l[c]<0: q+=[(c,b^d)]
print(*l,sep='\n')

Measured memory_bytes: 37228
// Segment tree (Sum)
package main

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

type segmentTree struct {
	data   []int
	offset int
}

func newSegmentTree(n int) segmentTree {
	var result segmentTree
	t := 1
	for t < n {
		t *= 2
	}
	result.offset = t - 1
	result.data = make([]int, 2*t-1)
	return result
}

func (st segmentTree) updateAll(a []int) {
	for i, v := range a {
		st.data[st.offset+i] = v
	}
	for i := st.offset - 1; i > -1; i-- {
		st.data[i] = st.data[i*2+1] + st.data[i*2+2]
	}
}

func (st segmentTree) add(index, value int) {
	i := st.offset + index
	st.data[i] += value
	for i >= 1 {
		i = (i - 1) / 2
		st.data[i] = st.data[i*2+1] + st.data[i*2+2]
	}
}

func (st segmentTree) update(index, value int) {
	i := st.offset + index
	st.data[i] = value
	for i >= 1 {
		i = (i - 1) / 2
		st.data[i] = st.data[i*2+1] + st.data[i*2+2]
	}
}

func (st segmentTree) query(start, stop int) int {
	result := 0
	l := start + st.offset
	r := stop + st.offset
	for l < r {
		if l&1 == 0 {
			result += st.data[l]
		}
		if r&1 == 0 {
			result += st.data[r-1]
		}
		l = l / 2
		r = (r - 1) / 2
	}
	return result
}

func main() {
	defer flush()

	N := readInt()
	Q := readInt()

	c := make([]int, N)
	for i := 0; i < N; i++ {
		c[i] = readInt()
	}

	lr := make([][3]int, Q)
	for i := 0; i < Q; i++ {
		l := readInt() - 1
		r := readInt() - 1
		lr[i] = [3]int{i, l, r}
	}
	sort.Slice(lr, func(i, j int) bool { return lr[i][2] < lr[j][2] })

	result := make([]int, Q)
	st := newSegmentTree(N)
	mr := map[int]int{}
	k := 0
	for i := 0; i < N; i++ {
		if j, ok := mr[c[i]]; ok {
			st.add(j, -1)
		}
		st.add(i, 1)
		mr[c[i]] = i
		for k < Q && lr[k][2] == i {
			result[lr[k][0]] = st.query(lr[k][1], lr[k][2]+1)
			k++
		}
	}

	for i := 0; i < Q; i++ {
		println(result[i])
	}
}

const (
	ioBufferSize = 1 * 1024 * 1024 // 1 MB
)

var stdinScanner = func() *bufio.Scanner {
	result := bufio.NewScanner(os.Stdin)
	result.Buffer(make([]byte, ioBufferSize), ioBufferSize)
	result.Split(bufio.ScanWords)
	return result
}()

func readString() string {
	stdinScanner.Scan()
	return stdinScanner.Text()
}

func readInt() int {
	result, err := strconv.Atoi(readString())
	if err != nil {
		panic(err)
	}
	return result
}

var stdoutWriter = bufio.NewWriter(os.Stdout)

func flush() {
	stdoutWriter.Flush()
}

func println(args ...interface{}) (int, error) {
	return fmt.Fprintln(stdoutWriter, args...)
}


Measured memory_bytes: 76756
import sys

litter = [""]
litter.append(list(" .,!? "))
litter.append(list(" abc"))
litter.append(list(" def"))
litter.append(list(" ghi"))
litter.append(list(" jkl"))
litter.append(list(" mno"))
litter.append(list(" pqrs"))
litter.append(list(" tuv"))
litter.append(list(" wxyz"))

n = input()
for count in range(n):
    ls = map(int, list(raw_input()))
    button, times = None, 0
    for i in ls:
        if i==0 :
            if button != None:
                sys.stdout.write(litter[button][times])
                button, times = None, 0
        else:
            button, times = i, times+1
            if times == len(litter[button]):
                times = 1
    sys.stdout.write('\n')

Measured memory_bytes: 4284
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,b,x;
	cin>>a>>b>>x;
	float ans=0.0;
	if (b*a*a/2.0<=x)
	{
	    ans=atan2((2*a*a*b-2*x),a*a*a);
	}
	else{
	ans = atan2(a*b*b,2*x);}
	cout<<fixed<<setprecision(9)<<ans* 180 / 3.14159265359;
	
}

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

#define ed cout<<"\n";
#define speed ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long 
#define ffor(i,a,b) for(ll i=(ll)(a);i<(ll)(b);++i)
#define rep(i, n) ffor(i,0,n)
#define All(obj) (obj).begin(),(obj).end()
#define INF ((ll)1e9+7)
#define c(a) cout<<a<<"\n";
using namespace std;
const int N = 100005;



int main() {
	speed;
	string s;
	cin >> s;
	int c0 = 0, c1 = 0;
	rep(i, s.size()) {
		if (s[i] == '0')c0++;
		if (s[i] == '1')c1++;
	}
	c(2*min(c0, c1));
	return 0; 
}



Measured memory_bytes: 512
import math
a, b, x = map(int, input().split())
if a**2*b == x:
    s = 90
elif (a**2)*b/2 < x:
    s = math.degrees(math.atan(a/(2*(b-(x/(a**2))))))
else:
    s = math.degrees(math.atan(2*x/(a*b**2)))
print(90-s)

Measured memory_bytes: 3060
#include<iostream>
#include<vector>
#include<stack>
#include<queue>
#define REP(i,n) for(int i=0;i<(n);++i)
using namespace std;
typedef pair<int,int> pii;
typedef vector<int>   vi;
typedef vector<vi >   vvi;
template<class Type> void line(const Type &a){int cnt=0;for(auto &elem:a){if(cnt++)cout<<' ';cout<<elem;}cout<<endl;}

int h,w,k;				//input.
vector<vector<char>> c;	//
vvi ans;
queue<pii> q;			//イチゴがあるマスの座標.
queue<int> qw;			//イチゴがない行番号.

void f(){//イチゴのある行のグループの決定. 横のマスを埋める.
	while(!q.empty()){
		pii tmp=q.front();
		q.pop();
		
		int y=tmp.first;
		int x=tmp.second;
		int num=ans[y][x];
		
		for(int i=x-1;i>=0;--i){
			if(ans[y][i]!=-1) break;
			ans[y][i]=num;
		}
		for(int i=x+1;i<w;++i){
			if(ans[y][i]!=-1) break;
			ans[y][i]=num;
		}
	}
}

void g(){//イチゴがない行のグループの決定. 上または下の行からコピーする.
	stack<int> st;	//上の行もイチゴないとき,スタックにためる.
	int hoge=-1;	//直近のスタックした行.
	
	while(!qw.empty()){//上の行から.
		int y=qw.front();
		qw.pop();
		if(y-1==hoge){
			st.push(y);
			hoge=y;
		}else{
			REP(i,w) ans[y][i]=ans[y-1][i];
		}
	}
	
	while(!st.empty()){//下の行から.
		int y=st.top();
		st.pop();
		REP(i,w) ans[y][i]=ans[y+1][i];
	}
}

int main(){
	cin>>h>>w>>k;
	
	c.assign(h,vector<char>(w));
	ans.assign(h,vi(w,-1));
	int num=1;//イチゴの番号.
	REP(i,h){
		int cnt=0;
		REP(j,w){
			cin>>c[i][j];
			if(c[i][j]=='#'){
				ans[i][j]=num++;
				q.emplace(i,j);
				cnt++;
			}
		}
		if(cnt==0) qw.push(i);//一行にイチゴがなかったらキューにプッシュ.
	}
	
	f();
	g();
	
	REP(i,h) line(ans[i]);
}


Measured memory_bytes: 1920
//#include <iostream>
#include <cstdio>

int main(){
    int A, B, C;
    //std::cin >> A >> B >> C;
    scanf("%d %d %d", &A, &B, &C);
    if(A + B >= C){
        //std::cout << "Yes" << std::endl;
        printf("Yes");
    }else{
        //std::cout << "No" << std::endl;
        printf("No");
    }

    return 0;
}

Measured memory_bytes: 128
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif
// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<pii,int> ppii;
typedef pair<int,pii> pipi;
typedef pair<ll,ll> pll;
typedef pair<pll,ll> ppll;
typedef pair<ll,pll> plpl;
#define rep(i,n) for(int i=0; i<((int)n); i++)
#define REP(i,n) for(int i=0; i<=((int)n); i++)
#define srep(i,a,n) for(int i=a; i<((int)n); i++)
#define SREP(i,a,n) for(int i=a; i<=((int)n); i++)
#define rrep(i,n) for(int i=n-1; i>=0; i--)
#define RREP(i,n) for(int i=n; i>=0; i--)
#define INF 1000000000
const int mod = INF+7;

//dfsって計算量めっちゃ多くなりそうだけど、実際はO(M)なんだよね。
int dfs(int *dp, int node, map<int, vector<int>> &mp){
  if(mp[node].size()==0){
    return dp[node]=0;
  }
  else if(dp[node]!=-1){
    return dp[node];
  }
  else{
    int mx=0;
    rep(k,mp[node].size()){
      mx=max(mx, dfs(dp, mp[node][k], mp));
    }
    return dp[node]=mx+1;
  }
}


int main(){
  int N, M;
  cin >> N >> M;
  vector<int> x(M);
  vector<int> y(M);
  rep(i,M){
    cin >> x[i] >> y[i];
    x[i]--;
    y[i]--;
  }

  map<int, vector<int>> mp;
  rep(i,M){
    mp[x[i]].push_back(y[i]);
  }

  // rep(i,N){
  //   rep(j,mp[i].size()){
  //     printf("%d ", mp[i][j]);
  //   }
  //   printf("\n");
  // }

  int *dp=(int *)malloc(sizeof(int)*N);
  rep(i,N){
    dp[i]=-1;
  }
  rep(j,N){
    int c=dfs(dp, j, mp);
  }

  int ans=0;
  rep(i,N){
    ans=max(ans, dp[i]);
  }

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

}


Measured memory_bytes: 17152
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
using Graph = vector<vector<int>>;
typedef pair<int, int> P;
const int INF=10000000;
const int MAX_N=50;

int main() {
    int n;
    cin >> n;
    int ans=0, i=n;
    while (true) {
        if(i%2==0 && i%n==0) {
            ans=i;
            break;
        }
        ++i;
    }
    cout << ans << endl;
    
}


Measured memory_bytes: 256