akhauriyash/Code-Regression huggingface dataset:
import java.util.Scanner;

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

		int[] L = new int[M+1];
		int[] R = new int[M+1];
		int[][] X = new int[N+1][N+1];
		for (int i = 1; i <= M; i++) {
			L[i] =sc.nextInt();
			R[i] = sc.nextInt();
			X[L[i]][R[i]]++; 
		}
		
		int[][] C = new int[N+1][N+1];
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				C[i][j] = C[i][j-1] + X[i][j];
			}
		}
		
		for (int i = 1; i <= Q; i++) {
			int p = sc.nextInt();
			int q = sc.nextInt();
			int sum = 0;
			for (int j = p; j <=q; j++) {
				sum += C[j][q] - C[j][p-1];
			}
			System.out.println(sum);
		}
		sc.close();
	}
}

Measured memory_bytes: 157980
// finding a word

#include<stdio.h>
#include<string.h>

int main()
{
    int i=0 ;
    int lenw=0 ,lent=0 ;
    int flg=0 ;
    char w[11] = {0} ;
    char t[1001] = {0} ;

    scanf("%s",w) ;
    lenw=strlen(w) ;

    for (i=0 ;i<lenw ;i++)
    {
        if (w[i] >= 'A' && w[i] <= 'Z')
        {
            w[i] = w[i] + 32 ;
        }
    }

    while (1)
    {
        scanf("%s",t) ;

        if (strcmp(t ,"END_OF_TEXT") == 0) break ;

        lent=strlen(t) ;
        for (i=0 ;i<lent ;i++)
        {
            if (t[i] >= 'A' && t[i] <= 'Z')
            {
                t[i] = t[i] + 32 ;
            }
        }

        if (strcmp(t ,w) == 0) flg++ ;

    }

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

    return 0 ;
}

Measured memory_bytes: 548
#include<bits/stdc++.h>
using namespace std;
#define int long long



int32_t main(){


   int n;   cin >> n;
   int mx = 0;
   int sum =0;

   for(int x=0;x<n;x++){
       int val; cin >> val;
       sum += val;
       mx = max(mx , val);
   }

   int other = sum - mx;

  // cout << mx << " " << other << endl;

   if(mx < other){
       cout << "Yes" << endl;
   }else{
       cout << "No" << endl;
   }


    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i = 0; i < (n); i++)
#define INF 2 << 29
#define MOD 1000000007
#define Yes(f) puts((f)? "Yes" : "No")
#define YES(f) puts((f)? "YES" : "NO")
int gcd(int a, int b) {
	if (b != 0)return gcd(b, a % b);
	return a;
}
int lcm(int a, int b) {
	return a / gcd(a, b) * b;
}

using Graph = vector<vector<int>>;

int main(){
	string s; cin >> s;
	Yes(s[2] == s[3] && s[4] == s[5]);
}

Measured memory_bytes: 256
import fractions
import math
import itertools
A,B=map(int,input().split())
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def combinations_count(n, r):
   return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
  
def prime_factorize(n):
    a = {}
    while n % 2 == 0:
        a[2]=1
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a[f]=1
            n //= f
        else:
            f += 2
    if n != 1:
        a[n]=1
    return a
  
C=fractions.gcd(A,B)
d_C=prime_factorize(C)
print(len(d_C)+1)



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

move_now = 0
move_max = 0
hi_past = h[0]
for hi in h[1:]:
    if hi_past >= hi:
        move_now += 1
        move_max = max(move_max, move_now)
    else:
        move_now = 0
    hi_past = hi

print(move_max)


Measured memory_bytes: 14252
#include <iostream>
#include <string>
#include <stdio.h>
#include <set>
#include <map>

using namespace std;

#define ll long long
#define rep(i, n) for (ll i = 1; i < (n+1); i++)
#define req(j, n) for (ll j = 1; j < (n+1); j++)
#define rer(k, n) for (ll k = 1; k < (n+1); k++)


int main()
{
    ll N, M;
    cin >> N >> M;
    int arr[M];
    rep(i, M) {
        cin >> arr[i];
        N -= arr[i];
    }
    if (N < 0) {
        cout << "-1" << endl;
    } else {
        cout << N << endl;
    }
}

Measured memory_bytes: 3204
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (ll i = (ll)(a); i < (ll)(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define ll long long
#define lld long double
#define ALL(x) x.begin(), x.end()
#ifdef DEBUG
#define line() cerr << "[" << __LINE__ << "] ";
#define dump(i) cerr << #i ": " << i << " ";
#define dumpl(i) cerr << #i ": " << i << endl;
#else
#define line(i)
#define dump(i)
#define dumpl(i)
#endif
using namespace std;
int main(int argc, char const *argv[])
{
    int n, m;
    cin >> n >> m;
    int mx = n, mn = 1;
    rep(i, m)
    {
        int l, r;
        cin >> l >> r;
        mx = min(mx, r);
        mn = max(mn, l);
    }
    cout << max(mx - mn + 1, 0) << endl;
    return 0;
}


Measured memory_bytes: 256
//
//  main.cpp
//  ABC124
//
//  Created by hiroaki on 2019/05/07.
//  Copyright © 2019年 hiroaki. All rights reserved.
//

#include <iostream>
#include <vector>
#include <algorithm>


//pair sort firstに揃う

#define int long long
#define pb(n) push_back(n)
#define Rap(n,i) for(int (i)=0;(i)<(n);(i)++)
#define Pr(n) cout<<n<<endl;
#define F first
#define S second
#define vector2 vector<vector<int> >
#define index(v,x) find((v).begin(), (v).end(), (x))-(v).begin()
#define ctoi(c) (int)(c-'0')
#define incin(n) int (n); cin>>(n);
#define all(v) (v).begin() , (v).end()
#define ELM 100001 //問題によっては1000000001に変更


//限定
using namespace std;

signed  main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    incin(x);
    incin(y);
    
    vector<int> a{1,3,5,7,8,10,12},b{4,6,9,11},c{2};
    bool xina = x==1||x==3||x==5||x==8 || x==7 ||x==10||x==12;
    bool xinb = x==4||x==6||x==9||x==11;
    bool xinc = x==2;
    bool yina = y==1||y==3||y==5||y==8 || x==7 ||y==10||y==12;
    bool yinb = y==4||y==6||y==9||y==11;
    bool yinc = y==2;
    
    bool same = (xina&&yina) || (xinb&&yinb) || (xinc&&yinc);
    if (same) {
        Pr("Yes");
    }else{
        Pr("No");
    }
}


Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <map>
#include <iostream>
#include <set>
#include <utility>
#include <vector>

using namespace std;

int main(){
  int N;
  cin >> N;
  vector<int> a(N, 0);

  for (int i = 0; i < N; i++){
    cin >> a[i];
  }
  int min = 200*200*100+1;
  for (int t = -100; t <= 100; t++){
    int temp = 0;
    for (int i = 0; i < N; i++){
      temp += (a[i]-t)*(a[i]-t);
    }
    if (temp < min){
      min = temp;
    }
  }
  cout << min << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int main() {
  int N,M,X,g=0,s=0;
  cin>>N>>M>>X;
  int a[M];
  for(int i=0;i<M;i++){
    cin>>a[i];
    if(a[i]>X) g++;
    else if(a[i]<X) s++;
  }
  cout<<min(g,s)<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep2(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep_inv(i, n, m) for(int i = (int)(n); i > (int)(m); i--)
using namespace std;
using ll = long long;
using vl = vector<ll>;
using vc = vector<char>;
using vvl = vector<vl>;
using vvc = vector<vc>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;

ll N;

int main(){
  cin >> N;

  ll ans = 0;

  rep2(i, 1, N + 1){
    ll cnt = N / i;

    ans += i * cnt * (cnt + 1) / 2;
  }

  cout << ans << "\n";
  
  return 0;
}


Measured memory_bytes: 3668
N = int(input())
D = list(map(int, input().split(' ')))
D.sort()

## 中間のインデックスを取得
half_D = int(N / 2)

"""場合分け
1.中間で区切った小さい方と大きい方の数字が異なる
OK
2.同じ数字
NG
"""

## 2.同じ数字
if D[half_D] == D[half_D-1]:
  print(0)
## 1.中間で区切った小さい方と大きい方の数字が異なる
else:
  print(D[half_D] - D[half_D-1])

Measured memory_bytes: 14396
<?php
$yen500=trim(fgets(STDIN));
$yen100=trim(fgets(STDIN));
$yen50=trim(fgets(STDIN));
$money=trim(fgets(STDIN));
$array=str_split(trim(fgets(STDIN)));

$count = 0;


for($i=0;$i<=$yen500;$i++){
 for($j=0;$j<=$yen100;$j++){
  for($k=0;$k<=$yen50;$k++){
    
    $result=$i*500+$j*100+$k*50;
        if($result==$money){
        $count++;    
        }
    
  }   
 }   
}

echo $count;
?>

Measured memory_bytes: 4604
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <list>
#include <iomanip>
#include <queue>
#include <functional>
#include <cassert>
#include <cmath>
#include <set>
#include <map>

#define REP(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define NL << endl
using namespace std;
using ll = long long;
const int INFINT = 1 << 30;
const ll INFLL = 1LL << 60;
const int MOD = 1000000007;
int gcd(int a, int b) {return b ? gcd(b, a%b) : a;}

int main() {

	int r, g;

	cin >> r >> g;

	cout << 2 * g - r NL;

	return 0;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
using namespace std;
using Graph = vector<vector<int>>;

signed main() {
  int N, M;
  cin >> N >> M;
  Graph G(N+1);
  
  int A, B;
  for( int i = 0; i < M; i++ ){
    cin >> A >> B;
    G.at(A).push_back(B);
  }
  
  for( int i = 0; i < G.at(1).size(); i++ ){
    for( int j = 0; j < G.at(G.at(1).at(i)).size(); j++ ){
      if( G.at(G.at(1).at(i)).at(j) == N ){
        cout << "POSSIBLE" << endl;
        return 0;
      }
    }
  }
  cout << "IMPOSSIBLE" << endl;
}



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

using namespace std;

constexpr int MAX_N = 100000;
vector<int> pre_order(MAX_N, -1);//pre_order[i]:=??±???????????¢?´¢??§???????????????i????????£?????¨??????timer
vector<int> post_order(MAX_N, -1);//post_order[i]:=??±???????????¢?´¢??§???????????????i????????£?????¨??????timer
vector<int> parent(MAX_N, -1);//parent[i]:=??±???????????¢?´¢??§??¨????§????????????¨???????????????i??????
vector<bool> visited(MAX_N, false);//??±???????????¢?´¢???????????§????¨?????????????????????°???????´?????????????

vector<vector<int>> G(MAX_N);

void add_edge(int s, int t) {
	G[s].emplace_back(t);
	G[t].emplace_back(s);
}

void dfs(const vector<vector<int>>& G, int u = 0, int prev_u = -1, int timer = 1) {
	pre_order[u] = timer;
	post_order[u] = timer;
	++timer;

	//u????¨????????????¨????????¢
	visited[u] = true;
	

	for (int i = 0; i < G[u].size(); ++i) {

		int v = G[u][i];

		//u?????£??\??????????????????v == G[u][i] ???????¨?
		if (!visited[v]) {

			//v?????????u??§?¢??????????
			parent[v] = u;

			//v??\????????±???????????¢?´¢????????????
			dfs(G, v, u, timer);

			//u???post_order?????´??°??????
			post_order[u] = min(post_order[u], post_order[v]);
		}

		//u?????£??\??????????????????v?????¢?¨?????????¢?´¢??§??´????????§????????£??????????????¨?????????
		else if (v != prev_u) {
			post_order[u] = min(post_order[u], pre_order[v]);
		}
	}
}

vector<int> articulation_points(const vector<vector<int>>& G, int G_sz, int root = 0) {
	dfs(G,root);
	vector<int> ans;
	vector<bool> used(G_sz, false);
	for (int i = 0; i < G_sz; ++i) {

		//??±???????????¢?´¢??§?§????????????¨??????????????????????????????2?????\????????????????????\????¢????
		if (i == root) {
			int root_child = 0;
			for (int j = 0; j < G_sz; ++j) {
				if (parent[j] == root)++root_child;
				if (root_child == 2) {
					ans.emplace_back(root);
					break;
				}
			}
		}

		else if (parent[i] != root
				&&pre_order[parent[i]] <= post_order[i]
				&& !used[parent[i]]) {

			ans.emplace_back(parent[i]);
			used[parent[i]] = true;
		}
	}
	sort(ans.begin(), ans.end());
	return ans;
}

int main()
{
	int N, E;
	cin >> N >> E;
	int s, t;

	for (int i = 0; i < E; ++i) {
		cin >> s >> t;
		add_edge(s, t);
	}
	vector<int>ans = articulation_points(G, N);
	for (int i = 0; i < ans.size(); ++i) {
		cout << ans[i] << endl;
	}
}

Measured memory_bytes: 6244
num = int(input())
input_line = list(map(int,input().split(' ')))
flower = [0 for i in range(num)]
cnt = 0
while(True):
    flg = 0
    for n in range(num):
        if(flower[n] != input_line[n]):
            flower[n] += 1
            flg = 1
        elif(flg):
            flg = 0
            cnt += 1
        if(flg and (n==(num-1))):
            cnt += 1
    if(sum(flower) == sum(input_line)):
        break
print(cnt)


Measured memory_bytes: 3064
import java.util.*

private fun readStrings() = readLine()!!.split(" ")
private fun readInts() = readStrings().map { it.toInt() }

private inline fun <T, R> List<T>.scanIndexed(initial: R, operation: (Int, R, T) -> R): List<R> {
    val result = ArrayList<R>(size)
    var prevResult = initial
    forEachIndexed { index, element ->
        val elementResult = operation(index, prevResult, element)
        result.add(elementResult)
        prevResult = elementResult
    }
    return result
}

private inline fun <T> Iterable<T>.scanIndexed1(operation: (Int, T, T) -> T): List<T>
        = drop(1).scanIndexed(first(), operation)

private inline fun <T> Iterable<T>.scan1(operation: (T, T) -> T): List<T>
        = scanIndexed1 {i, list, elem -> operation(list, elem)}

private inline fun <T> Iterable<T>.countElements(): Map<T, Int> {
    val result = HashMap<T, Int>()
    forEach { result[it] = (result[it] ?: 0) + 1 }
    return result
}

fun main(args: Array<String>) {
    val N = readInts()[0]
    val a = readInts().map{ it.toLong() }
    println(
            (listOf(0L, 0L) + a)
            .scan1 { a, b -> a + b }
            .countElements().values
            .map { it.toLong() * (it.toLong() - 1L) / 2L }
            .sum()
    )
}

Measured memory_bytes: 99648
#include <bits/stdc++.h>
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)
 
typedef long long ll;
#define INF 1e9
 
int N;


int main(){
  cin >> N;
  vector<vector<int>> A(2, vector<int>(N));
  vector<vector<int>> sum(2,vector<int>(N+1,0));
  REP(i, 2){
    REP(j, N){
      cin >> A[i][j];
      sum[i][j+1] += sum[i][j] + A[i][j];
    }
  }
  int ans = -1;
  REP(i, N){
    ans = max(ans, sum[0][i+1]+sum[1][N]-sum[1][i]);
  }
  cout << ans << endl;



  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define ALL(v) (v).begin(),(v).end()
#define Vi vector<int>
#define pb push_back
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repr(i,a,b) for(int i=a;i>b;i--)
#define leng(n) (int)(log10(n)+1)
#define INF 9000000000000000000
#define MOD 1000000007
using namespace std;

int gcd(int a,int b){return b?gcd(b,a%b):a;}  //  最大公約数gcd
int lcm(int a,int b){return a/gcd(a,b)*b;}  //  最小公倍数lcm

signed main() {
  string s;
  cin >> s;
  bool ok = false;
  rep(i,0,s.size()){
    if(s[i]=='A' && s[i+1]=='C') ok = true;
  }
  if(ok) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
using namespace std;

int main(){
	int a, b;
	cin >> a >> b;
	int SUM[1000];
	SUM[0] = 0;
	for(int i=1;i<=999;i++){
		SUM[i] = SUM[i-1] + i;
	}
	cout << SUM[b-a] - b << endl;
}

Measured memory_bytes: 256
n, k = [int(x) for x in input().split()]

_mod = 10 ** 9 + 7

ans = 0

#init
min0 = sum(range(0,k))
max0 = sum(range(n + 1 - k, n + 1))
cnt = max0 - min0 + 1
ans = cnt

for i in range(k+1 , n + 2):
#    min0 = min0 + i - 1
#    max0 = max0 + (n + 1 - i)
#    cnt  = max0 + (n + 1 - i) - (min0 + i - 1) + 1
    cnt = cnt + (n + 1 - i) - (i - 1)    
    ans += cnt % _mod

print(ans % _mod)

Measured memory_bytes: 9204
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main(){
  int N;
  cin >> N;
string S;
cin >> S;
int K;
cin >> K;
for(int i=0;i<N;i++){
  if(S.substr(K-1,1) != S.substr(i,1)){
    S.replace(i, 1, "*");
  }
}
cout << S << endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <set>
#include <string>

using namespace std;

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

    int N;
    string S;
    cin >> N >> S;

    int answer = 0;
    for (int i = 1; i < N; i++) {
        set<char> first_chars, second_chars;
        auto first = S.substr(0, i);
        auto second = S.substr(i, S.length());
        for(auto c : first){
            first_chars.insert(c);
        }
        for(auto c : second){
            second_chars.insert(c);
        }
        
        int count = 0;
        for(auto c : first_chars){
            if(second_chars.find(c) != second_chars.end()){
                count += 1;
            }
        }
        answer = max(count, answer);
    }

    cout << answer << endl;
}

Measured memory_bytes: 256
# NlogNによる脳死回答
N = int(input())
div_cnt = [0 for i in range(10**7+1)]
for i in range(1, 10**7+1):
    c = i
    while c <= 10**7:
        div_cnt[c] += 1
        c += i
ans = 0
for i in range(1, N+1):
    ans += i*div_cnt[i]
print(ans)

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

#define REP(i,n) for(int i=0;i<(n);++i)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FORD(i,a,b) for(int i=(a);i>=(b);--i)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(c) ((int)((c).size()))
#define st first
#define nd second
#define pb push_back

typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<bool> vb;
typedef long long ll;

void solve(){
    ll n,k;
    cin>>n>>k;
    ll x = n/k;
    ll ans = x*x*x;
    if (k%2 == 0) {
        ll y = (n + k/2) / k;
        ans += y*y*y;
    }
    cout << ans << '\n';
}

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


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

int main() {
  vector<string> day = {"SUN", "MON", "TUE", "WED", "THU", "FRI", "SAT"};
  string s;
  cin >> s;
  int di = -1;
  rep(i, 7) if (day[i] == s) di = i;
  int ans = 7 - di;
  cout << ans << endl;
  return 0;
}

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

int read() {
    int ans=0,flag=1;
    char ch=getchar();
    while( (ch>'9' || ch<'0') && ch!='-' ) ch=getchar();
    if(ch=='-') flag=-1,ch=getchar();
    while(ch>='0' && ch<='9') ans=ans*10+ch-'0',ch=getchar();
    return ans*flag;
}
int main()
{
	int n;
	string ss;
	map<string,int>a;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>ss;
		if(a[ss]!=0){
			cout<<"NO";
			return 0;
		}
		else
			a[ss]+=1;
	}
	cout<<"YES";
 	return 0;
}

Measured memory_bytes: 24832
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	static final int[] weights = { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512 };

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line = "";

		while ((line = br.readLine()) != null) {
			int stuff = Integer.parseInt(line);
			StringBuilder sb = new StringBuilder();

			for (int i = 0; i < 10; i++) {
				if ((stuff & weights[i]) > 0) {
					sb.append(weights[i] + " ");
				}
			}
			sb.deleteCharAt(sb.length() - 1);
			System.out.println(sb.toString());
		}
	}
}

Measured memory_bytes: 17036
#include <bits/stdc++.h>
using namespace std;
#define sc scanf
#define pr printf
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define MAX 500007
#define MOD 1000000007
#define MODL 1000000007LL
#define sz(x) ((int)(x).size())

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;

// Trace dinâmico
template<typename T>
void trace(T a) { cout << a << "\n"; }
template<typename T, typename... Args>
void trace(T a, Args... args) { cout << a << " "; trace(args...); }

// Debugador de recursão
int recNum = 0;
void prTabs() { for (int ii = 0; ii < recNum; ++ii) cout << "    "; }
template<typename... Args>
void recInit(Args... args) { prTabs(); trace("rec(", args..., ")"); recNum++; }
template<typename T>
void recEnd(T a) { prTabs(); trace("->", a); recNum--;}

int MD(int x) {
	if(x < 0) return x+MOD;
	if(x >= MOD) return x-MOD;
	return x;
}

ll MDL(ll x) {
	return (x%MODL+MODL)%MODL;
}

ll modpow(ll a, ll b, ll m) {
	if (!b) return 1LL;
	if (b&1LL) return a*modpow(a, b-1, m)%m;
	ll r = modpow(a, b>>1, m);
	return r*r%m;
}

//m prime
ll invmod(ll a , ll m) {
	return modpow(a, m-2, m);
}

int li[MAX];
int last[MAX];
int bit[MAX];
pair<ii, int> queries[MAX];
int query(int i) {
	i += 2;
	i = MAX-i;
	int s= 0;
	while(i) {
		s += bit[i];
		i -= i&(-i);
	}
	return s;
}
void update(int i, int v) {
	i += 2;
	i = MAX-i;
	while(i < MAX) {
		bit[i] += v;
		i += i&(-i);
	}
}
int r[MAX];

int n, q, k, a, b, c;
int main(){
	sc("%d %d", &n, &q);
	for(int i = 1; i <= n; i++) {
		sc("%d", li+i);
	}
	for(int i = 1; i <= n; i++) {
		update(last[i], 1);
	}
	for(int i = 0; i < q; i++) {
		sc("%d %d", &a, &b);
		queries[i] = mp(mp(b, a), i);
	}
	sort(queries, queries+q);
	int j = 0;
	for(int i = 0; i < q; i++) {
		while(j < queries[i].fi.fi) {
			j++;
			update(last[li[j]], -1);
			last[li[j]] = j;
			update(last[li[j]], 1);
		}
		r[queries[i].se] = query(queries[i].fi.se);
	}
	for(int i = 0; i < q; i++) {
		pr("%d\n", r[i]);
	}
 	return 0;
}


Measured memory_bytes: 17408
#include <stdio.h>
int main()
{
	int a;
	scanf("%d\n",&a);
	int c[60],b,sum,sum1,sum2,i[60],j[60];
	sum=0;
	sum1=0;
	for(b=0;b<a;b++)
	{
		scanf("%d",&i[b]);
	}
	for(b=0;b<a;b++)
	{scanf("%d",&c[b]);
	sum=sum+c[b];	
	}
	for(b=0;b<a-1;b++){
		
		scanf("%d",&j[b]);
	}for(b=0;b<a;b++)
	{
		if(i[b]-i[b-1]==1&&i[b]!=1){
		sum1=sum1+j[i[b]-2];}
	}
	sum2=sum1+sum;
	printf("%d",sum2);
	return 0;
	}


Measured memory_bytes: 128
//#define M_PI 3.14159265358979323846
#define _USE_MATH_DEFINES

//#define _GLIBCXX_DEBUG
//#define all(x) (x).begin(),(x).end()
#pragma comment(linker,"/STACK:256000000")

#include <bits/stdc++.h>

#define TASK ""
#define sqr(x) ((x)*(x))
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
using namespace std;
const ll INFLL = numeric_limits<ll>::max();
const ll INFINT = numeric_limits<int>::max();
const ld EPS = 1e-7;
const ll MOD = 1000000000;
const ll MAXN = 123456;

void run()
{
    ll n;
    cin >> n;
    vector<ll> mas(n);
    for (int i = 0; i < n; ++i)
    {
        cin >> mas[i];
        mas[i]--;
    }
    ll ans = 0;
    for (int i = 0; i < n; ++i)
    {
        if (mas[mas[i]] == i) ans++;
    }
    cout << ans / 2;
}

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

#ifdef LOCAL
//#define STRESS
#ifdef STRESS
    freopen("input.txt", "w", stdout);
    cout << "1000 50\n";
    for (int i = 0; i < 999; i++)
    {
        for (int j = 0; j < 999; j++) cout << ".";
        cout << "X\n";
    }
    for (int j = 0; j < 1000; j++)
        if (j != 1000 / 50)cout << "X";
        else cout << ".";
    return 0;

#endif
    if (strcmp(TASK, "-") != 0)
    {
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    }
#else
    if (strcmp(TASK, "")   != 0)
    {
        freopen(TASK".in", "r", stdin)  ;
        freopen(TASK".out", "w", stdout)  ;
    }
#endif
    run();

    return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<string>
#include<vector>

using namespace std;

int main() {
	int x[3];
	cin >> x[0] >> x[1] >> x[2];
	int s5 = 0, s7 = 0;
	for (int i = 0; i < 3; i++)
	{
		if (x[i] == 5)s5++;
		if (x[i] == 7)s7++;
	}
	if (s5 == 2 && s7 == 1)
		cout << "YES" << endl;
	else
		cout << "NO" << endl;
}

Measured memory_bytes: 256
// {{{ by shik
#include <bits/stdc++.h>
#include <unistd.h>
#define SZ(x) ((int)(x).size())
#define ALL(x) begin(x),end(x)
#define REP(i,n) for ( int i=0; i<int(n); i++ )
#define REP1(i,a,b) for ( int i=(a); i<=int(b); i++ )
#define FOR(it,c) for ( auto it=(c).begin(); it!=(c).end(); it++ )
#define MP make_pair
#define PB push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;

#ifdef SHIK
template<typename T>
void _dump( const char* s, T&& head ) { cerr<<s<<"="<<head<<endl; }

template<typename T, typename... Args>
void _dump( const char* s, T&& head, Args&&... tail ) {
    int c=0;
    while ( *s!=',' || c!=0 ) {
        if ( *s=='(' || *s=='[' || *s=='{' ) c++;
        if ( *s==')' || *s==']' || *s=='}' ) c--;
        cerr<<*s++;
    }
    cerr<<"="<<head<<", ";
    _dump(s+1,tail...);
}

#define dump(...) do { \
    fprintf(stderr, "%s:%d - ", __PRETTY_FUNCTION__, __LINE__); \
    _dump(#__VA_ARGS__, __VA_ARGS__); \
} while (0)

template<typename Iter>
ostream& _out( ostream &s, Iter b, Iter e ) {
    s<<"[";
    for ( auto it=b; it!=e; it++ ) s<<(it==b?"":" ")<<*it;
    s<<"]";
    return s;
}

template<typename A, typename B>
ostream& operator <<( ostream &s, const pair<A,B> &p ) { return s<<"("<<p.first<<","<<p.second<<")"; }
template<typename T>
ostream& operator <<( ostream &s, const vector<T> &c ) { return _out(s,ALL(c)); }
template<typename T, size_t N>
ostream& operator <<( ostream &s, const array<T,N> &c ) { return _out(s,ALL(c)); }
template<typename T>
ostream& operator <<( ostream &s, const set<T> &c ) { return _out(s,ALL(c)); }
template<typename A, typename B>
ostream& operator <<( ostream &s, const map<A,B> &c ) { return _out(s,ALL(c)); }
#else
#define dump(...)
#endif

template<typename T>
void _R( T &x ) { cin>>x; }
void _R( int &x ) { scanf("%d",&x); }
void _R( long long &x ) { scanf("%" PRId64,&x); }
void _R( double &x ) { scanf("%lf",&x); }
void _R( char &x ) { scanf(" %c",&x); }
void _R( char *x ) { scanf("%s",x); }

void R() {}
template<typename T, typename... U>
void R( T& head, U&... tail ) {
    _R(head);
    R(tail...);
}

template<typename T>
void _W( const T &x ) { cout<<x; }
void _W( const int &x ) { printf("%d",x); }
template<typename T>
void _W( const vector<T> &x ) {
    for ( auto i=x.cbegin(); i!=x.cend(); i++ ) {
        if ( i!=x.cbegin() ) putchar(' ');
        _W(*i);
    }
}

void W() {}
template<typename T, typename... U>
void W( const T& head, const U&... tail ) {
    _W(head);
    putchar(sizeof...(tail)?' ':'\n');
    W(tail...);
}

#ifdef SHIK
#define FILEIO(...)
#else
#define FILEIO(name) do {\
    freopen(name ".in","r",stdin); \
    freopen(name ".out","w",stdout); \
} while (0)
#endif

// }}}

const int N=110;
int n,a[N],c[N];

bool solve() {
    REP(i,n) c[a[i]]++;
    int mx=*max_element(a,a+n);
    int mid=(mx+1)/2;
    REP1(i,mid+1,mx) if ( c[i]<2 ) return 0;
    if ( mx%2==0 && c[mid]!=1 ) return 0;
    if ( mx%2==1 && c[mid]!=2 ) return 0;
    REP(i,mid) if ( c[i] ) return 0;
    return 1;
}

int main() {
    R(n);
    REP(i,n) R(a[i]);
    bool ans=solve();
    W(ans?"Possible":"Impossible");
    return 0;
}


Measured memory_bytes: 256
N, K = [int(x) for x in input().split()]
p = [int(x) for x in input().split()]

E_acc = [0]
for i in range(N):
    E_acc.append((p[i] + 1) / 2 + E_acc[i])

ans = 0
for i in range(N - K + 1):
    ans = max(ans, E_acc[i + K] - E_acc[i])

print(ans)

Measured memory_bytes: 25188
#include <stdio.h>

int main(){
	int n;
	int x[40];
	int i,k;
	int Flag = 0;
	
	for(i = 0;i < 40;i++){
		x[i] = 0;
	}
	
	x[39] = 1;
	
	scanf("%d",&n);
	
	for(i = 1;i <= n;i++){
		for(k = 0;k <= 39;k++){
			x[k] *= i;
		}
		
		for(k = 39;k >= 0;k--){
			if(x[k] >= 10){
				x[k-1] += x[k]/10;
				x[k] %= 10;
			}
		}
	}
	
	for(i = 0;i < 40;i++){
		if(x[i] != 0){
			Flag = 1;
		}
		if(Flag == 1){
			printf("%d",x[i]);
		}
	}
	
	printf("\n");
	
	return 0;
}
			

Measured memory_bytes: 1024
n = gets.chomp.to_i
a = gets.chomp.split
height = 0
min = 0
a[0] = a[0].to_i
(n-1).times do |i|
    a[i+1] = a[i+1].to_i
    min = a[i] if a[i] > min
    if a[i+1] - min < 0
        height += (a[i+1] - min).abs
    end
end
puts height


Measured memory_bytes: 28604
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)

//-----------------------------------------------

//------------------------------------------------
int main(){
  int n;
  int d[60];
  int ans;
  ans=0;
  cin>>n;
  rep(i,0,n) cin>>d[i];
  rep(i,0,n) {
    rep(k,i+1,n){
      ans+=d[i]*d[k];
    }
  }

  cout<<ans<<endl;
}


Measured memory_bytes: 256
/* kadai 3_2
   nabe9393 */
 
#include<stdio.h>
 
int main(void){
  int N;
  scanf("%d", &N); //入力
  if (N % 10 == 3){ //１のくらいが３の時はBON
    printf("bon\n");
  }
  else if (N % 10 == 0 || N % 10 == 1 || N % 10 == 6 || N % 10 == 8){ //1のくらいが0,1,6,8の時はPON
    printf("pon\n");
  }
  else{ //それ以外はHON
    printf("hon\n"); 
  }
return 0;
}

Measured memory_bytes: 1664
#include<bits/stdc++.h>
using namespace std;
int main(){
  char S;
  int mix=0;
  int a=0;
  for(int i=0; i<3;i++){
    cin >> S;
    if (S=='R'){
      a++;
      mix=max(a,mix);
    } else {
      a=0;
    }
  }
  cout << mix << endl;
}

Measured memory_bytes: 3608
#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int i=0;i<n;++i)
int main(){
  int n,ans=0,a; cin>>n;
  map<int,int>m;
  rep(i,n)m[(cin>>a,a)]^=1;
  for(auto e:m)ans+=e.second;
  cout<<ans<<endl;
}

Measured memory_bytes: 4992
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<cstring>
#include<iomanip>
#include<math.h>
#include<queue>
#define inf 0x3f3f3f
#define M 1000000
#define ll  long long
using namespace std;
struct note
{
    int x,y;
}a[M];
bool cmp(note x1,note x2)
{
    return x1.y<x2.y;
}
int main()
{
  //  note
  int n,m;
   cin>>n>>m;
   int i;
   for(i=0;i<m;i++)
     cin>>a[i].x>>a[i].y;
     sort(a,a+m,cmp);
     int l=0,sum=0;
     for(i=0;i<m;i++)
     {
         if(a[i].x>=l)
         {
             l=a[i].y;
             sum++;
         }
     }
     cout<<sum<<endl;
     return 0;
}


Measured memory_bytes: 1024
#pragma gcc optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(V) (V).begin(),(V).end()
#define SORT(V) sort(ALL(V)) //小さい方からソート
#define REV(V) reverse(ALL(V)) //リバース
#define RSORT(V) REV(SORT(V)) //大きい方からソート
#define NPN(V) next_permutation(ALL(V)) //順列
#define pb(n) push_back(n)
#define endl '\n'
#define Endl '\n'
#define DUMP(x)  cout << #x << " = " << (x) << endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define RAPID cin.tie(0);ios::sync_with_stdio(false)
#define IN(n) cin >> n
#define IN2(a,b) cin >> a >> b
#define IN3(a,b,c) cin >> a >> b >> c 
#define VIN(V) for(int i = 0; i < (V).size(); i++) {cin >> (V).at(i);}
#define OUT(n) cout << n << endl
#define VOUT(V) for(int i = 0; i < (V).size(); i++) {cout << (V).at(i) << endl;}

// 型マクロ定義
#define int long long
#define P pair<ll,ll>
#define Vi vector<ll>
#define Vd vector<double>
#define Vs vector<string>
#define Vc vector<char>
#define M map<ll,ll>
#define S set<ll>
#define PQ priority_queue<ll>
#define PQG priority_queue<ll,V,greater<ll>
//

const int MOD = 1000000007;
const int INF = 1061109567;
const double EPS = 1e-10;
const double PI  = acos(-1.0);

int gcd(int a,int b){return b?gcd(b,a%b):a;} //最小公倍数

// デフォルト変数定義
int n,m,a,b,c=0,x,y,z;
double d,e,f;
string s,t;
//

signed main() {
  RAPID;
  IN(n);
  FOR(i,1,n+1){
    if(to_string(i).length() % 2 == 1) {
      c++;
    }
  }
  OUT(c);
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
/*#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
*/typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;

#define int ll
#define LOCAL 0
#define dbg(x) cout << #x << " is " << x << "\n"
#define gll(x) scanf("%d",&x)
#define gll2(x,y) scanf("%d%d",&x,&y)
#define gll3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define gllarr(arr,n) f(i,n) gll(arr[i]);
#define sz(x) ((int)x.size())
#define s(x) sort(x.begin(),x.end())
#define all(v) v.begin(),v.end()
#define rs(v) { s(v) ; r(v) ; }
#define r(v) {reverse(all(v));}
#define pb push_back
#define f(i,n) for(int i=0;i<n;i++)
#define fr(i,n) for(int i=n-1;i>=0;i--)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define repr(i,a,b) for(int i=a;i>=b;i--)

const ll mod = (ll)1e9 + 7;
const ll inf = (ll)1e16;
const ld eps = 1e-12;
const ll N = (int)2e5 + 5;
const ll LOGN = 19;
const ld PI = 3.14159265358979323846;
inline ll mul(ll a, ll b, ll m = mod) { return (ll)(a * b) % m;}
inline ll add(ll a, ll b, ll m = mod) { a += b; a += m; return (a % m);}
inline ll power(ll a, ll b, ll m = mod) { if(b == 0) return 1; if(b == 1) return (a % m); ll x = power(a, b / 2, m); x = mul(x, x, m); if(b % 2) x = mul(x, a, m); return x;}

int n, m;

const int MAX_FACT = (int)5e5 + 50;
ll fact[MAX_FACT];
ll inv[MAX_FACT];

/* Calculates factorial and inverse factorial MODULO mod upto MAX_FACT */
void init()
{
    inv[0] = fact[0] = 1 % mod;
    rep(i, 1, MAX_FACT - 1) {
        fact[i] = mul(fact[i - 1], i);
        inv[i] = power(fact[i], mod - 2);
    }
}

ll C(int n, int r){
    /* nCr */
    if(n < r || r < 0) return 0ll;
    return mul(mul(fact[n], inv[r]), inv[n - r]);
}

ll P(int n, int r){
    /* nPr */ 
    if(n < r || r < 0) return 0ll;
    return mul(fact[n], inv[n - r]);
}

ll H(int n, int m){
    /* Solution of equation x1 + x2 + .. + xn = m */
    return C(n + m - 1, m);
}

int findWays(int ff, int ss) {
    int ret = mul(C(ff, ss), fact[ss]);
    return ret;
}

void solve() {
    cin>>n>>m;
    init();
    
    int ans = 0;
    for(int i = 0; i <= n; i++) {
        int cans = mul(C(n, i), findWays(m - i, n - i));
        if(i & 1) ans = add(ans, -cans);
        else ans = add(ans, cans);
    }
    cout<<mul(ans, findWays(m, n));

}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    if (LOCAL) {
        freopen("C:\\Users\\Dishant\\Desktop\\Collection-DEV c++\\input.txt", "r", stdin);
        freopen("C:\\Users\\Dishant\\Desktop\\Collection-DEV c++\\output.txt", "w", stdout);
    }
    int t = 1;
    //cin>>t;
    for(int test = 1; test <= t; test++) {
        //cout<<"Case #"<<test<<": ";
        solve();
    }
    return 0;
}

Measured memory_bytes: 11420
#include <bits/stdc++.h>
#define sz(v)   ((int)(v).size())
#define  all(v)    ((v).begin()),((v).end())
#define  allr(v)    ((v).rbegin()),((v).rend())
#define   pb         push_back
#define   mp         make_pair
#define    clr(v,d)      memset( v, d ,sizeof(v))
#define     PI                       acos(-1)
typedef  long long     ll ;
typedef  unsigned long long ull;
const double eps= (1e-9);
using namespace std;
int dcmp(long double a,long double b){   return fabsl(a-b)<=eps ? 0: (a>b)? 1:-1  ;}
int getBit(ll num, int idx) {return ((num >> idx) & 1ll) == 1;}
int setBit1(int num, int idx) {return num | (1<<idx);}
ll setBit0(ll num, int idx) {return num & ~(1ll<<idx);}
ll flipBit(ll num, int idx) {return num ^ (1ll<<idx);}
void GO(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);}
int countNumBit1(int mask) {int ret=0; while (mask) 	{mask &= (mask-1);++ret;	}return ret;}
const int N=2000+9,mod=1e9+7;
int mem[N][N];
int solve(int id,int rem){
  // cout<<id<<" "<<rem<<endl;
   if(id==0){
    if(rem==0) return 1;
    return 0;
   }

   int &ret=mem[id][rem];
   if(ret!=-1) return ret;

   ll ans=0;
   if(rem>0)
   ans+=solve(id,rem-1);

   if(ans>=mod) ans-=mod;

   ans+=solve(id-1,rem);
   if(ans>=mod) ans-=mod;

   return ret=ans;
}
int main(){
    GO();

    int T;
  //  cin>>T;
    T=1;
    while(T--){
        int s;
        cin>>s;
         clr(mem,-1);
         ll ans=0;
        for(int i=1;i<=s;i++){
            int ts=s;
            if(i*3>ts) continue;
            ts-=3*i;
            ans+=solve(i,ts);
            if(ans>=mod) ans-=mod;
        }
        cout<<ans<<"\n";

    }

}





















































































































































































Measured memory_bytes: 19352
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; --i)
#define whole(x) (x).begin(),(x).end()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
using P = pair<int, int>;
#define debug(var) cerr << "[" << #var << "] " << var << endl
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
const ll mod = 1000000007;
const int dx[] = {-1,0,1,0};
const int dy[] = {0,-1,0,1};


int main(){
    int n;
    cin >> n;
    vector<int> f(n);
    rep(i, n) {
        rep(j, 10) {
            int x;
            cin >> x;
            f[i] = (f[i]<<1) + x;
        }
    }
    int ans = -mod;
    vector<vector<int>> p(n, vector<int>(11));
    rep(i, n) rep(j, 11) cin >> p[i][j];

    rep(i, 1<<10) {
        if (i==0) continue;
        int res = 0;
        rep(j, n) {
            int num = __builtin_popcount(i&f[j]);
            res += p[j][num];
        }
        chmax(ans, res);
    }
    
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3568
#include<stdio.h>
const int N = 15;
int main()
{
	int n, S[N] = {0}, H[N] = {0}, C[N] = {0}, D[N] = {0};
	scanf("%d",&n);
	for(int i = 0; i < n; i++)
	{
		int p;
		char k;
		scanf(" %c %d",&k,&p);
		if(k == 'S')
		{
			S[p]++;
		}
		else if(k == 'H')
		{
			H[p]++;
		}
		else if(k == 'C')
		{
			C[p]++;
		}
		else if(k == 'D')
		{
			D[p]++;
		}
	}
	for(int i = 1;i <=13;i++)
	{
		if (S[i] == 0)
		{
			printf("S %d\n", i);
		}
	} 
	for(int i = 1;i <=13;i++)
	{
		if (H[i] == 0)
		{
			printf("H %d\n", i);
		}
	} 
	for(int i = 1;i <=13;i++)
	{
		if (C[i] == 0)
		{
			printf("C %d\n", i);
		}
	} 
	for(int i = 1;i <=13;i++)
	{
		if (D[i] == 0)
		{
			printf("D %d\n", i);
		}
	}
	return 0;
}


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

int main (int argc , char** argv)
{
    string s;
    cin>>s;
    string t;
    cin>>t;
    int correct=0;
    for(int i=0 ; i < 3; i++){
        if(s[i] == t[i])
            correct++;
    }

    cout<<correct<<endl;
    return 0;
}

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

int N,M;

struct Node{
	bool operator<(const struct Node &arg) const{
		return weight < arg.weight;
	};
	int from,to,weight;
};

int parent[1001],height[1001];
Node* nodes;

int getParent(int id){
	if(parent[id] == id)return id;
	else{
		return parent[id] = getParent(parent[id]);
	}
}

bool isSame(int a, int b){
	return getParent(a) == getParent(b);
}

void unite(int a,int b){
	int a_parent = getParent(a);
	int b_parent = getParent(b);

	if(a_parent == b_parent)return;

	if(height[a_parent] > height[b_parent]){
		parent[b_parent] = a_parent;
	}else{
		if(height[a_parent] == height[b_parent])height[b_parent]++;
		parent[a_parent] = b_parent;
	}
}

void init(){
	for(int i = 1; i <= N; i++){
		parent[i] = i;
		height[i] = 0;
	}
}

void func(){

	for(int i = 0; i < M; i++){
		scanf("%d %d %d",&nodes[i].from,&nodes[i].to,&nodes[i].weight);
	}

	sort(nodes,nodes+M);

	int count = 0,ans;

	init();

	for(int i = 0; i < M; i++){
		if(!isSame(nodes[i].from,nodes[i].to)){
			unite(nodes[i].from,nodes[i].to);
			if(count == (N-1)/2){
				ans = nodes[i].weight;
				break;
			}
			count++;
		}
	}

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

int main(){

	nodes = (Node*)malloc(sizeof(Node)*10000);

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

		func();
	}
}

Measured memory_bytes: 3392
#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define RREP(i,a,b) for(int i=(a);i>=(b);i--)
typedef long long ll; typedef long double ld;
using namespace std;
const int INF=1e9, MOD=1e9+7;
const int MAX_N=10000;
int n,m,k;
set<int> st;

int main(){
	cin >> n >> m >> k;
	
	REP(i,0,n+1) REP(j,0,m+1) st.insert(i*m+j*n-2*i*j);

	cout << (st.count(k)?"Yes":"No") << endl;
	return 0;
}
	


Measured memory_bytes: 13056
#include "bits/stdc++.h"
using namespace std;
using ll = long long;

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

Measured memory_bytes: 1792
import java.util.Arrays;
import java.util.Scanner;

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

		int n = sc.nextInt();
		int q = sc.nextInt();

		SqrtDecompositionRMQRUQ sq = new SqrtDecompositionRMQRUQ(n);
		sq.update(0, n, Integer.MAX_VALUE);
		for(int i = 0; i < q; i++){
			int type = sc.nextInt();

			if(type == 0){
				int s = sc.nextInt();
				int t = sc.nextInt();
				int x = sc.nextInt();

				sq.update(s, t + 1, x);
			}
			else {
				int s = sc.nextInt();
				int t = sc.nextInt();

				System.out.println(sq.findMin(s, t + 1));
			}

		}
	}

}

class SqrtDecompositionRMQRUQ {
	int N, K;
	long[] data;
	long[] bucketMin;
	long[] bucketLazyUpdate;
	static final int sqrtN = 512;
	static final int NIL = Integer.MIN_VALUE;

	public SqrtDecompositionRMQRUQ(int n) {
		N = n;
		K = (N + sqrtN - 1) / sqrtN;
		data = new long[K * sqrtN];
		bucketLazyUpdate = new long[K];
		Arrays.fill(bucketLazyUpdate, NIL);
		bucketMin = new long[K];
	}

	// [s, t)
	void update(int s, int t, int x) {
		for (int k = 0; k < K; ++k) {
			int l = k * sqrtN, r = (k + 1) * sqrtN;
			if (r <= s || t <= l)
				continue;
			if (s <= l && r <= t) {
				bucketLazyUpdate[k] = x;
				bucketMin[k] = x;
			} else {
				if(bucketLazyUpdate[k] != NIL){
					for(int i = l; i < r; i++){
						data[i] = bucketLazyUpdate[k];

					}
					bucketLazyUpdate[k] = NIL;
				}
				for (int i = Math.max(s, l); i < Math.min(t, r); ++i) {
					data[i] = x;
				}
				bucketMin[k] = Long.MAX_VALUE;
				for(int i = l; i < r; i++){
					bucketMin[k] = Math.min(bucketMin[k], data[i]);
				}
			}
		}
	}

	long findMin(int s, int t) {
		long result = Long.MAX_VALUE;
		for (int k = 0; k < K; ++k) {
			int l = k * sqrtN, r = (k + 1) * sqrtN;
			if (r <= s || t <= l)
				continue;
			if (s <= l && r <= t) {
				result = Math.min(result, bucketMin[k]);
			}
			else {
				if(bucketLazyUpdate[k] != NIL){
					result = Math.min(result, bucketLazyUpdate[k]);
				}
				else {
					for (int i = Math.max(s, l); i < Math.min(t, r); ++i) {
						result = Math.min(result, data[i]);
					}
				}
			}
		}

		return result;
	}

	long get(int s) {
		int k = s / sqrtN;
		if(bucketLazyUpdate[k] != NIL){
			return bucketLazyUpdate[k];
		}
		else {
			return data[s];
		}
	}
}


Measured memory_bytes: 104052
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SIZE_OF_NAME 11
#define QUEUE_SIZE 100000

typedef struct{
    char name[SIZE_OF_NAME];
    int time;
}Quantum;

typedef struct{
    int front;
    int back;
    int size;
    int max;
}Queue;

void printQuantum(Quantum, int);
void queueInit(Queue*);
void setMax(Queue*, int);
void enqueue(Queue*);
void dequeue(Queue*, Quantum*);
Quantum front(Queue*, Quantum*);
int isFull(Queue*);
int isEmpty(Queue*);

int main(int argc, char** argv) {
    int size, interval;
    int timeLapsed = 0;
    Quantum temp;
    scanf("%d %d", &size, &interval);
    Quantum arrayQ[size];
    
    Queue arrayQl;
    queueInit(&arrayQl);
    setMax(&arrayQl, size);
    for(int i = 0; i < size; i++){
        scanf("\n%s %d", arrayQ[i].name, &arrayQ[i].time);
        enqueue(&arrayQl);
    }
    while(!isEmpty(&arrayQl)){
        if(front(&arrayQl,arrayQ).time - interval > 0){
            timeLapsed += interval;
            temp = front(&arrayQl,arrayQ);
            dequeue(&arrayQl,arrayQ);
            strcpy(arrayQ[arrayQl.back].name, temp.name);
            arrayQ[arrayQl.back].time = temp.time - interval;
            enqueue(&arrayQl);
        }
        else{
            timeLapsed += front(&arrayQl,arrayQ).time;
            printQuantum(front(&arrayQl,arrayQ), timeLapsed);
            dequeue(&arrayQl,arrayQ);
        }
    }
    
    return (EXIT_SUCCESS);
}

void printQuantum(Quantum q, int time){
    printf("%s %d\n",q.name, time);
}

void queueInit(Queue *ql){
    ql->size = 0;
    ql->front = 0;
    ql->back = 0;
}

void setMax(Queue *ql, int max){
    ql->max = max;
}

void enqueue(Queue *ql){
    if(!isFull(ql)){
        ql->back++;
        ql->size++;
        ql->back %= ql->max;
    }
    if(ql->size == ql->max)
        ql->back = -1;
}

void dequeue(Queue *ql, Quantum *q){
    strcpy(q[ql->front].name,"");
    q[ql->front++].time = 0;
    ql->size--;
    ql->front %= ql->max;
    if(ql->back == -1){
        if(ql->front == 0)
            ql->back = ql->max - 1;
        else
            ql->back = ql->front - 1;
    }
}

Quantum front(Queue *ql, Quantum *q){
    return q[ql->front];
}

int isFull(Queue *ql){
    if(ql->size < ql->max) return 0;
    return 1;
}

int isEmpty(Queue *ql){
    if(ql->size == 0) return 1;
    return 0;
}



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

#define vi vector<int>
#define pb push_back

typedef long long ll;

bool SO[1000100];

void erast(int n){
    memset(SO,1,sizeof(SO));
    SO[1] = false;
    SO[0] = false;
    REP(i,2,sqrt(n)){
        if(SO[i]){
            REP(j,2,n){
                if(i*j>=1000000) break;
                SO[i*j] = false;
            }
        }
    }
}

int main(){
//    ifstream in("ain.txt");
//    cin.rdbuf(in.rdbuf());
    erast(1000001);
    int n;
    while(cin >> n,n){
        int cnt =0;

        REP(i,n+1,2*n+1){
            if(SO[i]) cnt++;
        }
        cout << cnt << endl;
    }

    return 0;
}


Measured memory_bytes: 4000
import math
import copy
from copy import deepcopy
import sys
import fractions
# import numpy as np
from functools import reduce
# import statistics
import decimal
import heapq
import collections
import itertools
from operator import mul

sys.setrecursionlimit(100001)


# input = sys.stdin.readline
# sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

x, y, a, b, c = map(int, input().split())
p = getInputListInt()
q = getInputListInt()
r = getInputListInt()

p.sort()
q.sort()
r.sort()

p = p[-x:]
q = q[-y:]

tmp_p_min = min(x, c)
tmp_p = p[:tmp_p_min]
tmp_q_min = min(y, c)
tmp_q = q[:tmp_q_min]

tmp_list = tmp_p+tmp_q+r
tmp_list.sort()
newlist = tmp_list[-tmp_p_min-tmp_q_min:]

ans = sum(p[tmp_p_min:]) + sum(q[tmp_q_min:]) + sum(newlist)
print(ans)


Measured memory_bytes: 25324