akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <math.h>
int main() {
	int n, t, a, h,ans;
	double min = 1000000000;
	scanf("%d%d%d", &n, &t, &a);
	for (int i = 0; i < n; i++) {
		scanf("%d", &h);
		if (min > fabs(a - (t - h * 0.006))) {
			min = fabs(a - (t - h * 0.006));
			ans = i + 1;
		}
	}
	printf("%d", ans);
	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define MAXN
using namespace std;
char m[15][15];
int main() {
	int h,w,k; scanf("%d%d%d",&h,&w,&k);
	for(int i = 1;i <= h;i ++) {
		string s; cin >> s;
		for(int j = 1;j <= w;j ++) {
			m[i][j] = s[j - 1];
		}
	} 
	int ans = 0;
	for(int i = 0;i < (1 << h);i ++) {
		for(int j = 0;j < (1 << w);j ++) {
			int sum = 0;
			for(int q = 1;q <= h;q ++) {
				for(int p = 1;p <= w;p ++) {
					if(m[q][p] == '#' && (i & (1 << (q - 1))) && (j & (1 << (p - 1)))) sum ++;
				}
			}
			if(sum == k) ans ++;
		}
	}
	printf("%d",ans);
	return 0;
}


Measured memory_bytes: 3788
#!/usr/bin/env python3

from pprint import pprint
from collections import deque, defaultdict
import itertools
import math
import sys

sys.setrecursionlimit(10 ** 6)
INF = float('inf')


x, k, d = map(int, input().split())
x = abs(x)

ans = None
if x > d:
    q, r = divmod(x, d)
    if k <= q:
        ans = x - k * d
    else:
        y = x - q * d
        if (k - q) % 2 == 0:
            ans = y
        else:
            ans = min(abs(y + d), abs(y - d))
else:
    if k % 2 == 0:
        ans = x
    else:
        ans = abs(x - d)

print(ans)


Measured memory_bytes: 68448
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

std::string s;
int n, Q;
std::vector <int> a;


class SegT {
public:
    int n;
    std::vector <int> seg;
    SegT () {}
    SegT (int _n) : n(_n) {
      seg.resize (n*4);
    }
    void push (int rt) {
      seg[rt] = seg[rt<<1] | seg[rt<<1|1];
    }
    void build (int l, int r, int rt) {
      if (l == r) {
        seg[rt] = a[l-1];
        return;
      }
      int mid = l + r >> 1;
      build (l, mid, rt<<1);
      build (mid+1, r, rt<<1|1);
      push (rt);
    }
    int ask (int L, int R, int l, int r, int rt) {
      if (l == L && R == r)
        return seg[rt];
      int mid = l + r >> 1;
      if (R <= mid) return ask (L, R, l, mid, rt<<1);
      else if (L >= mid+1) return ask (L, R, mid+1, r, rt<<1|1);
      else return ask (L, mid, l, mid, rt<<1) | ask (mid+1, R, mid+1, r, rt<<1|1);
    }
    void modify (int pos, int val, int l, int r, int rt) {
      if (l == r) {
        seg[rt] = val;
        return;
      }
      int mid = l + r >> 1;
      if (pos <= mid) modify (pos, val, l, mid, rt<<1);
      else modify (pos, val, mid+1, r, rt<<1|1);
      push (rt);
    }
};

int main () {
  std::cin >> n;
  std::cin >> s;
  a.resize (n);
  for (int i = 0; i < n; ++i)
    a[i] = 1 << (s[i]-'a');
  SegT SegT (n);
  SegT.build (1, n, 1);
  std::cin >> Q;
  while (Q--) {
    int op; std::cin >> op;
    if (op == 1) {
      int x; std::string y;
      std::cin >> x >> y;
      SegT.modify (x, (1<<(y[0]-'a')), 1, n, 1);
    } else {
      int x, y; std::cin >> x >> y;
      int ans = SegT.ask (x, y, 1, n, 1);
      std::cout << __builtin_popcount (ans) << "\n";
    }
  }
  return 0;
}

Measured memory_bytes: 10756
import java.io.*;
import java.util.*;
import java.lang.*;

public class Main {
 	public static void main (String[] args) {
     Scanner sc = new Scanner (System.in);
     int[] a = new int[3];
      a[0] = sc.nextInt();
      a[1] = sc.nextInt();
      a[2] = sc.nextInt();
      
      Arrays.sort(a);
      int num = a[2]*10+a[1]+a[0];
      System.out.println(num);
    }
}

Measured memory_bytes: 35232
using System;
using System.Collections.Generic;
namespace I_am_the_brown_coder{
    class ABC10000000{
        static void Main(){
            string[] n_m = Console.ReadLine().Split();
            int n = int.Parse(n_m[0]);//スイッチがn個
            int m = int.Parse(n_m[1]);//電球がm個
            List<int>[] sw = new List<int>[n];
            for(int i=0;i<n;i++){
                sw[i] = new List<int>();
            }
            for(int i=0;i<m;i++){
                string[] input = Console.ReadLine().Split();
                for(int j=0;j<int.Parse(input[0]);j++){
                    sw[int.Parse(input[j+1])-1].Add(i);
                }
            }
            
            string[] ps = Console.ReadLine().Split();
            int[] p = new int[m];
            for(int i=0;i<m;i++){
                p[i] = int.Parse(ps[i]);
            }

            int ans = 0;
            
            for(int i=0;i<Pow2(n);i++){
                int nowi = i;
                int[] swtodn = new int[m];
                for(int j=0;j<n;j++){
                    if(nowi%2==1){
                        foreach(int k in sw[n-j-1]){
                            swtodn[k] ++;
                        }
                    }
                    nowi /= 2;
                }
                bool allon = true;
                for(int j=0;j<m;j++){
                    if(swtodn[j]%2!=p[j]){
                        allon = false;
                    }
                }
                if(allon){
                    ans ++;
                }
            }

            Console.WriteLine(ans);
        }

        static int Pow2(int n){
            int ans = 1;
            for(int i=0;i<n;i++){
                ans *= 2;
            }
            return ans;
        }
    }
}


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

int main() {
  int n, m, a[100][100], b[100];
  cin >> n >> m;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
      cin >> a[i][j];
  for (int i = 0; i < m; i++)
    cin >> b[i];
  for (int i = 0; i < n; i++) {
    int s = 0;
    for (int j = 0; j < m; j++)
      s += a[i][j] * b[j];
    cout << s << endl;
  }
  return 0;
}

Measured memory_bytes: 1200
def counting_sort(A, k):
    B = [0] * len(A)
    C = [0] * k

    for a in A:
        C[a] += 1

    for i in range(1, k):
        C[i] += C[i - 1]

    for a in reversed(A):
        B[C[a] - 1] = a
        C[a] -= 1

    return B


def main():
    n = int(input())
    A = [int(x) for x in input().split()]
    print(*counting_sort(A, 10001))


main()


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

int main()
{
    long long a,b,c,d,p1,p2,p3,p4,ans,mx1,mx2;
    cin >> a >> b >> c >> d;
    p1=a*c;
    p2=a*d;
    p3=b*c;
    p4=b*d;
    mx1 = max(p1,p2);
    mx2 = max(p3,p4);

    ans = max(mx1,mx2);
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3592
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int now = 0;
        int count = 0;
        while(now <= m && n>0){
            int i = sc.nextInt();
            now += i;
            count++;
            n--;
        }
        sc.close();
        if(now <= m){
            System.out.println(count+1);
        }else{        
            System.out.println(count);
        }
    }
}

Measured memory_bytes: 21972
#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;


#define abs(N) ((N>0)?N:-1*N)
#define lt(A,B) ((A>B)?B:A)
#define gt(A,B) ((A<B)?B:A)
#define print(S) (cout << S)
#define println(S) (cout << S << endl)

long long cnt;
int m;
vector<int> G;

void insertionSort(int * A, int n, int g){
	for (int i = g; i < n; ++i) {
		int v = A[i];
		int j = i - g;
		while(j >= 0 && A[j] > v){
			A[j+g] = A[j];
			j = j-g;
			cnt++;
		}
		A[j+g] = v;
	}
}

void shellSort(int * A, int n){
	int i=1;
	m = 0;
	cnt = 0;
	while(i <= n){
		G.insert(G.begin(),i);
		m++;
		i = i * 3 + 1;
	}
	for (vector<int>::iterator itr = G.begin(); itr != G.end(); ++itr) {
		insertionSort(A,n,(*itr));
	}
}

int main(){
	int n;
	cin >> n;
	int A[n];
	for (int i = 0; i < n; ++i) {
		cin >> A[i];
	}

	shellSort(A,n);

	println(m);
	for (vector<int>::iterator itr = G.begin(); itr != G.end(); ++itr) {
		cout << (*itr) << " ";
	}
	cout << endl;
	println(cnt);

	for (int i = 0; i < n; ++i) {
//		if(i > 0) cout << " ";
		cout << A[i] << endl;
	}
//	cout << endl;

	return 0;
}



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

int main(){
    int S;
    cin >> S;
    vector<long long> vec(S, 0);
    vec[0] = 0;
    vec[1] = 0;
    vec[2] = 1;
    /*cout << vec[0] << vec[1] << vec[2] << endl;*/
  	long long mod = 1000000007;
    for (int i = 3; i < S; i++){
        for (int j = 2; j < i - 2; j++){
            vec[i] += vec[j];
            vec[i] %= mod;
        }
    	vec[i] += 1;
      	vec[i] %= mod;
    	/*cout << vec[i] << endl;*/
    }
    cout << vec[S - 1] << endl;
}

Measured memory_bytes: 3616
using System;
using System.Collections.Generic;
using System.Globalization;
using System.Numerics;

class Class3
{
    static void Main(string[] args)
    {
        int N = int.Parse(Console.ReadLine());

        int totalCnt = 0;
        for (int i = 1; i < N; i++)
        {
            int AB = N - i;

            if (AB == 1)
            {
                totalCnt++;
                continue;
            }
            double max = Math.Sqrt(AB);
            int cnt = 0;
            for (int j = 1; j < max; j++)
            {
                if(AB % j == 0)
                {
                    cnt++;
                }
            }

            totalCnt += cnt * 2;

            if (max - Math.Floor(max) == 0)
            {
                totalCnt++;
            }

        }

        Console.WriteLine(totalCnt);


    }
}

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

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

    vector<int> d(n);
    for(int i = 0; i < n; i++) cin >> d[i];

    int64_t ans = 0;
    for(int i = 0; i < n - 1; i++) {
        for(int j = i + 1; j < n; j++) {
            ans += d[i] * d[j];
        }
    }

    cout << ans << endl;

    return 0;
}

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

int main(void){
    int n;
    cin>>n;
    vector<ll> a(n);
    rep(i, n){
        cin>>a[i];
    }
    sort(a.begin(), a.end());
    int flag=0;
    rep(i, n-1){
        if(a[i]==a[i+1]){
            flag++;
            break;
        }
    }
    if(flag==0){
        cout<<"YES"<<endl;
    }
    else {
        cout<<"NO"<<endl;
    }

}

Measured memory_bytes: 1792
#include <limits.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <math.h>

#define P 1000000007

int comp(const void *a, const void *b){return *(int*)a-*(int*)b;}

int main(void){
	int a, b, c, d, e, f;
	int i, j, k, l;
	scanf("%d%d%d%d%d%d", &a, &b, &c, &d, &e, &f);

	int w, s;
	double max=0;
	int answ, anss;
	for(i=0;; i++){
		if(i*a*100>f) break;
		for(j=0;; j++){
			w = (i*a+j*b)*100;
			if(w==0 || w>f) break;
			for(k=0;; k++){
				if(w+k*c>f) break;
				for(l=0;; l++){
					s = k*c+l*d;
					if(w+s>f) break;
					if(s>w/100*e) break;
					double now = ((double)s)/(w/100);
					if(now>=max){
						max=now;
						answ=w;
						anss=s;
					}
				}
			}
		}
	}
	printf("%d %d\n", answ+anss, anss);
}


Measured memory_bytes: 128
import java.util.*;

public class Main{
	public static void main(String[] args){
      
      Scanner sc = new Scanner(System.in);
      
      int A = sc.nextInt();
      int B = sc.nextInt();
   	  int C = sc.nextInt();
      int X = sc.nextInt();
      
      int y = 0;
      int count = 0;
      for(int i=0; i <= A ; i++){
      	for(int j=0; j <= B; j++){
        	y = (X-500*i-100*j)/50;
            if(y >= 0 && y <= C){
            	count = count+1;
            }
               
        }
      }
	System.out.println(count);
    }
}


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

#define ll long long
#define ull unsigned ll

#define vi vector <int>
#define ii pair <int, int>
#define vii vector <ii>
#define vll vector <ll>
#define vull vector <ull>
#define INFL 9e18
#define INF 2e9
#define EPS 1e-9
#define pb push_back
#define emp emplace_back
#define PI acos(-1.0)
#define endl "\n"
#define mp make_pair
#define DEBUG 0

int main ()

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

    int n, r;
    cin >> n >> r;
    vi num(r);
    int sum = 0;
    for (int i=0; i<r; i++)
    {
    	int x;
    	cin >> x;
    	sum += x;
    }
    
    if (sum > n)
    {
    	cout << -1 << endl;
    	return 0;
    }
    
    else cout << n - sum << endl;
    
    return 0;
}

Measured memory_bytes: 3660
#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 <cstdalign>
#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 vector<ll> vl;
typedef long double ld;
typedef vector<ld> vd;
typedef bool bl;
typedef vector<bl> vb;
typedef vector<vl> mt;
typedef unordered_map<ll,unordered_map<ll,ll>> graph;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef vector<string> vs;
typedef vector<vs> table;
typedef vector<vl> v2;
typedef vector<v2> v3;
typedef vector<v3> v4;


const ll e5 = 1 << 20;
const ll mods[] = {998244353, 1000000007, 1000000009};
const ll bases[] = {997, 1009, 1013};
// const ll mod = mods[0];
const ll e3 = 1 << 13;
const ll INF = 1ll << 50;

ll n;
ll ans;

int main(){
  cin >> n;
  for(ll i = 1;i <= n-i;i++){
    if(i != n-i) ans++;
  }
  cout << ans << endl;

}


Measured memory_bytes: 256
#include <stdio.h>

int main(void){

  int a, b;

  scanf("%d", &a);
  scanf("%d", &b);

  if (a < b)
    printf("a < b\n");
  else if (a > b)
    printf("a > b\n");
  else if (a == b)
    printf("a == b\n");

  return 0;
}

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

int main() {
    int n,k;
    cin >> n >> k;
    int s = (n-1) * (n-2) / 2;
    if(k > s){
        cout << -1 << endl;
        return 0;
    }
    int m = n - 1;
    m += s-k;
    cout << m << endl;
    for(int i = 1; i < n; i++){
        cout << i << " " << n << endl;
    }
    int count = 0;
    for(int i = 1; i < n; i++){
        for(int j = i+1; j < n; j++){
            if(count >= s-k){
                return 0;
            }else{
                cout << i << " " << j << endl;
                count++;
            }
        }
    }
}

Measured memory_bytes: 256
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "iomanip"

using namespace std;

const long long int MOD = 1000000007;

long long int N, M, K, H, W, L, R;



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

	cin >> K >> N;
	vector<int>turn(N+2);
	for (int i = 1; i <= N; i++) {
		cin >> turn[i];
	}
	turn[0] = 0;
	turn[N + 1] = INT_MAX;
	cin >> M;
	L = 0;
	R = K;
	int l = 0;
	int r = K;
	int box = 0;
	for (int i = 0; i < M; i++) {
		int t, b;
		cin >> t >> b;
		while (turn[box+1] <= t) {
			box++;
			int bag = turn[box] - turn[box - 1];
			if (box % 2) {
				if (bag <= l) {
					l -= bag;
				}
				else {
					L += bag - l;
					L = min(L, K);
					l = 0;
				}
				if (bag <= r) {
					r -= bag;
				}
				else {
					R += bag - r;
					R = min(R, K);
					r = 0;
				}
			}
			else {
				if (bag + l <= K) {
					l += bag;
				}
				else {
					L -= bag - (K - l);
					L = max((int)L, 0);
					l = K;
				}
				if (bag + r <= K) {
					r += bag;
				}
				else {
					R -= bag - (K - r);
					R = max((int)R, 0);
					r = K;
				}
			}
		}
		int bag = t - turn[box];
		if (box % 2 == 0) {
			if (b <= L) {
				cout << max(0, l - bag) << endl;
			}
			else if (b >= R) {
				cout << max(0, r - bag) << endl;
			}
			else {
				cout << max(0, l - bag + b - (int)L) << endl;
			}
		}
		else {
			if (b <= L) {
				cout << min((int)K, l + bag) << endl;
			}
			else if (b >= R) {
				cout << min((int)K, r + bag) << endl;
			}
			else {
				cout << min(K, l + bag + b - L) << endl;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 1664
#include<cstdio>
#include<iostream>
#include<ctype.h>
#include<string>
using namespace std;
int main(){
	int N, K;
	string S;
	cin >> N >> S >> K;
	for(int i = 0; i < N; i++){
		if(S[i] != S[K - 1]){
			S[i] = '*';
		}
	}
	cout << S << endl;
	return 0;
}

Measured memory_bytes: 256
#include <memory.h>

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>

using namespace std;

#define MOD 1000000007

struct elem
{
    int x;
    int y;
    int d;
    long long int cost;

    bool operator<(const elem &elem) const
    {
        return elem.cost < cost;
    }
};

int main()
{
    int h, w;
    long long int k;
    cin >> h >> w >> k;
    int sx, sy, tx, ty;
    cin >> sx >> sy >> tx >> ty;
    sx--;
    sy--;
    tx--;
    ty--;
    set<pair<int, int>> objects;
    for (int i = 0; i < h; i++)
    {
        for (int j = 0; j < w; j++)
        {
            char c;
            cin >> c;
            if (c == '@')
                objects.insert(make_pair(i, j));
        }
    }
    long long int INIT = pow(MOD, 2);
    vector<vector<vector<long long int>>> res(h, vector<vector<long long int>>(w, vector<long long int>(4, INIT)));
    priority_queue<elem> qu;
    int dx[4] = {1, 0, -1, 0};
    int dy[4] = {0, 1, 0, -1};
    for (int i = 0; i < 4; i++)
    {
        res[sx][sy][i] = 0;
        qu.push(elem{sx, sy, i, 0});
    }
    while (!qu.empty())
    {
        elem e = qu.top();
        qu.pop();
        int x = e.x;
        int y = e.y;
        int d = e.d;
        long long int cost = e.cost;
        if (cost > res[x][y][d])
            continue;
        //cout << x << " " << y << " " << d << " " << cost << endl;
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || nx >= h || ny < 0 || ny >= w || objects.find(make_pair(nx, ny)) != objects.end())
            {
                continue;
            }
            long long int nextcost = cost;
            if (i == d || cost % k == 0)
            {
                nextcost++;
            }
            else
            {
                nextcost -= cost % k;
                nextcost += k;
                nextcost++;
            }
            if (nextcost < res[nx][ny][i])
            {
                res[nx][ny][i] = nextcost;
                qu.push(elem{nx, ny, i, nextcost});
            }
        }
    }
    long long int ans = INIT;
    for (int i = 0; i < 4; i++)
    {
        if (res[tx][ty][i] == INIT)
            continue;
        ans = min(ans, (res[tx][ty][i] + k - 1) / k);
    }
    if (ans == INIT)
        cout << -1 << endl;
    else
        cout << ans << endl;
}

Measured memory_bytes: 144248
#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;
using ll = long long;

const int MOD = 1e9+7;
const ll INF = 1e18;
const double pi = acos(-1);
const int dx4[4] = {1, 0, -1, 0};
const int dy4[4] = {0, 1, 0, -1};
const int dx8[8] = {1,1,0,-1,-1,-1,0,1};
const int dy8[8] = {0,1,1,1,0,-1,-1,-1};

#define int ll
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()


template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }


int n,k;
vector<pair<int,int>> V;


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

    cin.tie(0);
    ios::sync_with_stdio(false);
    
    cin >> n >> k;
    rep(i,n) {
        int a,b; cin >> a >> b;
        V.push_back(make_pair(a,b));
    }
    
    
     
}

 

void solve(){
    
    sort(ALL(V));
    
    int cnt = 0;
    rep(i,n){
        cnt += V[i].second;
        if(cnt >= k) {
            cout << V[i].first << endl;
            break;
        }
        
        
    }
    
    
}





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



Measured memory_bytes: 3444
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long unsigned int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define SZ(x) ((int)(x).size())
#define m0(x) memset(x,0,sizeof(x))
#define fill(x,y) memset(x,y,sizeof(x))
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))



int main() {
  ll N;
  cin >> N;
  long count = 0;
  for (int i = 0; i < 4; i++)
  {
    if (N % 10 == 2) {
      count++;
    }
    N /= 10;
  }
    cout << count << endl;
  return 0;
}


Measured memory_bytes: 256
def solve() :
    n = int(input())
    if n == 0 : return -1 
    score = [] 
    for i in range(n):
        s = input().split()
        key = int(s[0])
        sumTime = 0
        for j in range(1, len(s)) :
            if j % 2 == 0 : sumTime += int(s[j])
            else : sumTime += int(s[j]) * 60
        score.append((sumTime, key))
    score.sort()
    print(score[0][1], score[1][1], score[-2][1], sep='\n')

while True:
    if solve() == -1 : break 


Measured memory_bytes: 6140
//#include<bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <utility>
#include <climits>
#define REP(i, n) for(int i = 0; i < n; ++i)
#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define F first
#define S second
#define OUT(x) cout << x << "\n"
using namespace std;
using point = pair< int,int >;
using ll = long long;

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

    OUT((n - 1) * (m - 1));
    return 0;
}



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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef pair<int, int> P;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

int N, M, R;
int inf = 1000000000;
int d[200][200];

void warshall_floyd(){
  rep(k, N)rep(i, N)rep(j, N) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

int main(){
  cin >> N >> M >> R;
  int r[R];
  rep(i, R){
    cin >> r[i];
    r[i] --;
  }
  sort(r, r+R);
  rep(i, N)rep(j, N) d[i][j] = inf;
  rep(i, N) d[i][i] = 0;
  
  rep(i, M){
    int a, b, c;
    cin >> a >> b >> c;
    d[a-1][b-1] = c;
    d[b-1][a-1] = c;
  }
  
  warshall_floyd();
  int ans = inf;
  do{
    int ans_temp = 0;
    rep(i, R-1){
      ans_temp += d[r[i]][r[i+1]];
    }
    ans = min(ans, ans_temp);
  }while(next_permutation(r , r+R));
  cout << ans << endl;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
 
int main() {
 char c ;
 cin >> c;
  if( c == 'a' || c=='i' ||c== 'u' ||c== 'e' ||c== 'o')
    cout << "vowel" <<endl;
else 
 cout <<  "consonant" << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <numeric>
#include <fstream>
#include <iomanip>

typedef long double ld;
typedef long long ll;
const ll INF = (ll)1e18 + 1;
const ll MOD = 1e9 + 7;

// Split
namespace util {

std::vector< std::string > split(std::string s, char delimiter)
{
  std::vector< std::string > vs;
  std::string sub;
  for (auto c : s) {
    if (c == delimiter) vs.push_back(sub), sub.clear();
    else sub += c;
  }
  vs.push_back(sub);
  return vs;
}

} // namespace util

// Minimum, Maximum
template<class T> T minimum(T head, T tail) { return std::min(head, tail); }
template<class H, class... T> H minimum(H head, T... tail) { return std::min(head, minimum(tail...)); }
template<class T> T maximum(T head, T tail) { return std::max(head, tail); }
template<class H, class... T> H maximum(H head, T... tail) { return std::max(head, maximum(tail...)); }

// Output
template<class T, class S> std::ostream& operator << (std::ostream& os, std::pair<T, S> p)
{
  return os << "(" << p.first << " " << p.second << ")";
}

template<class T> std::ostream& operator << (std::ostream& os, std::vector< T > v)
{
  for (ll i = 0; i < (ll)v.size(); i++){ os << " [" << i << "]" << v[i]; if (i % 10 == 9) os << std::endl; }
  //os << v[0]; for (ll i = 1; i < (ll)v.size(); i++){ os << " " << v[i]; }
  return os;
}

template<class T, class S> std::ostream& operator << (std::ostream& os, std::map< T, S > m)
{
  ll i = 0; for (auto p : m){ os << " [" << i << "]" << p.first << "->" << p.second; i++;}
  return os;
}

void print(){ std::cout << std::endl; }
template<typename H> void print(H head) { std::cout << head << std::endl; }
template<typename H, typename... T> void print(H head, T... tail){ std::cout << head << " ", print(tail...); }

// GCD, LCM
ll gcd(ll a, ll b) {
  while (b != 0) { a %= b; std::swap(a, b); }
  return a;
}
ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }

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

  ll N, M;
  std::cin >> N >> M;
  std::vector< ll > va(M, 0LL);
  for (ll i = 0; i < M; i++) {
    std::cin >> va[i];
  }

  ll sum = std::accumulate(va.begin(), va.end(), 0LL);
  ll ans = N - sum < 0 ? -1 : N - sum;

  print(ans);
  
  return 0;
}


Measured memory_bytes: 3684
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <numeric>
#include <iterator>

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int,int> PII;
typedef istringstream ISS;
typedef ostringstream OSS;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )

#define EACH( it, c ) for ( auto it = c.begin(); it != c.end(); ++it )
#define ALL( c ) (c).begin(), (c).end()
#define DRANGE( c, p ) (c).begin(), (c).begin() + p, (c).end()

#define PB( n ) push_back( n )
#define MP( a, b ) make_pair( ( a ), ( b ) )
#define EXIST( c, e ) ( (c).find( e ) != (c).end() )

#define fst first
#define snd second

#define DUMP( x ) cerr << #x << " = " << ( x ) << endl
#define DEBUG( x ) cerr << __FILE__ << ":" << __LINE__ << ": " << #x << " = " << ( x ) << endl

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

// 二部グラフマッチング O( |V||E| )
class BipertiteMatching
{
private:
	const int V;
	vector< vector<int> > G;
	vector<int> match;
	vector<bool> used;

public:
	BipertiteMatching( int v ) : V( v ), G( V ), match( V, -1 ), used( V )
	{
		return;
	}

	void connect( int u, int v )
	{
		G[u].push_back( v );
		G[v].push_back( u );
		return;
	}

	int solve()
	{
		int res = 0;
		fill( match.begin(), match.end(), -1 );

		for ( int v = 0; v < V; ++v )
		{
			if ( match[v] == -1 )
			{
				fill( used.begin(), used.end(), false );
				if ( dfs( v ) )
				{
					res++;
				}
			}
		}

		return res;
	}

private:
	int dfs( int v )
	{
		used[v] = true;

		for ( int i = 0; i < G[v].size(); ++i )
		{
			int u = G[v][i], w = match[u];
			if ( w == -1 || !used[w] && dfs( w ) )
			{
				match[v] = u;
				match[u] = v;
				return true;
			}
		}

		return false;
	}
};
// BipertiteMatching( |V| )
// connect( u, v )
// solve()

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

	while ( true )
	{
		int n, m;
		cin >> n >> m;

		if ( !( n | m ) )
		{
			break;
		}

		VI as( n ), bs( m );
		FOR( a, as )
		{
			cin >> a;
		}
		FOR( b, bs )
		{
			cin >> b;
		}

		BipertiteMatching bm( n + m );
		REP( i, 0, n )
		{
			REP( j, 0, m )
			{
				if ( gcd( as[i], bs[j] ) == 1 )
				{
					continue;
				}

				bm.connect( i, n + j );
			}
		}

		cout << bm.solve() << endl;
	}

	return 0;
}

Measured memory_bytes: 2720
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <string>
#include <deque>
#include <iomanip>
#include <bitset>
#include <complex>
#include <sstream>
#include <algorithm>
#include <limits>
#include <cmath>
#include <utility>
#include <tuple>
using namespace std;

using ll = long long;
using ld = long double;
using P = pair<int, int>;

constexpr int INF = 1e9;
constexpr ll LINF = 1e18;
constexpr int mod = 1e9+7;
constexpr ld eps = 1e-10;
constexpr ld pi = acos(-1.0);

#define DUMP(a) cout << #a << ": " << (a) << endl


int main() {
    int k, t;
    cin >> k >> t;
    vector<int> a(t);
    for(int i=0; i<t; ++i) {
        cin >> a[i];
    }
    while(a.size() > 1) {
        sort(a.rbegin(), a.rend());
        a[0]--; a[1]--;
        a.erase(remove(a.begin(), a.end(), 0), a.end());
    }
    if(a.size() == 0) {
        cout << 0 << endl;
    } else {
        cout << a[0]-1 << endl;
    }
}


Measured memory_bytes: 256
#include<vector>
#include<queue>
#include<iostream>
#include<climits>
#include<cmath>
using namespace std;
typedef long long ll;
typedef pair<int,ll> P;


void dist(int i,vector<vector<P>> V,vector<ll> d){
	d[i]=0;
	priority_queue<P,vector<P>,greater<>> que;
	que.push(P(i,0));
	
	while(!que.empty()){
		P p=que.top();que.pop();
		int u=p.first;
		if(d[u]<p.second) continue;
		for(int k=0;k<V[u].size();k++){
			int v=V[u][k].first;
			ll length=V[u][k].second;
			ll alt=d[u]+length;
			if(d[v]>alt){
				d[v]=alt;
				que.push(P(v,alt));
				//cout<<v<<"="<<alt<<endl;
			}
		}
	}
	return;
}

int main(){
	int N;
	cin>>N;
	vector<vector<P>> to(N);
	for(int i=0;i<N-1;i++){
		int a,b;
		ll c;
		cin>>a>>b>>c;
		a--;b--;
		to[a].push_back(P(b,c));
		to[b].push_back(P(a,c));
	}
	
	int Q,K;
	cin>>Q>>K;K--;
	vector<ll> d(N,LLONG_MAX);
	d[K]=0;
	priority_queue<P,vector<P>,greater<>> que;
	que.push(P(K,0));
	
	while(!que.empty()){
		P p=que.top();que.pop();
		int u=p.first;
		if(d[u]<p.second) continue;
		for(int k=0;k<to[u].size();k++){
			int v=to[u][k].first;
			ll length=to[u][k].second;
			ll alt=d[u]+length;
			if(d[v]>alt){
				d[v]=alt;
				que.push(P(v,alt));
				//cout<<v<<"="<<alt<<endl;
			}
		}
	}
	for(int i=0;i<Q;i++){
		int x,y;
		cin>>x>>y;x--;y--;
		cout<<d[x]+d[y]<<endl;
	}
}

Measured memory_bytes: 11120
#include <bits/stdc++.h>
using namespace std;
int main() {
    long long x, k, d, t;
    cin >> x >> k >> d;
    x = abs(x);
    if (k <= x / d) cout << x - k * d;
    else
    {
        k = k - (x / d);
        x %= d;
        if (k % 2 == 0) cout << x;
        else cout << d - x;
    }
}

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

const long long B = 1e9;

int n;
int f[25][25];

int calc(long long t) {
    int x = 0, y = 0;
    while (t % 2 == 0) { ++ x; t /= 2; }
    while (t % 5 == 0) { ++ y; t /= 5; }

    x = max(0, 18 - x);
    y = max(0, 18 - y);

    //assert(t == 1);

    int ans = 0;
    for (int i = x; i <= 20; ++i)
        for (int j = y; j <= 20; ++j) ans += f[i][j];
    return ans;
}

void inc(long long t) {
    int x = 0, y = 0;
    while (t % 2 == 0) { ++ x; t /= 2; }
    while (t % 5 == 0) { ++ y; t /= 5; }

    x = min(x, 18);
    y = min(y, 18);

    ++ f[x][y];
}

int main() {
#ifdef Wearry
    freopen("in", "r", stdin);
#endif

    long long ans = 0;
    scanf("%d", &n);
    while (n--) {
        double a;
        scanf("%lf", &a);

        long long temp = (long long) round(a * B);
        ans += calc(temp);
        inc(temp);
    }
    printf("%lld\n", ans);

    return 0;
}


Measured memory_bytes: 3848
# include "cstdio"
# include "iostream" 
 
using namespace std;

const int maxm=300000+10; 

int num[maxm],
    tot,
    ans;
     
int main(){
	int n;
	string s; 
	scanf("%d",&n); 
	cin>>s;
	if(s[0]=='W'){ 
		num[0]++; 
	} 
	for(int i=1;i<n;i++) {
		num[i]=num[i-1];
		if (s[i]=='W') {
			num[i]++;
		}
	}
	tot=num[n-1]; 
	int ans=n-tot; 
	if(s[0]=='E'){ 
        ans++; 
    } 
	for (int i=1;i<n;i++) { 
		int left=num[i-1]; 
        int right=n-(i+1)-(tot-num[i]);
		ans=min(ans,left+right);
	}
	printf("%d",ans);
	return 0;
}

Measured memory_bytes: 1796
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, exit


def main(readline=stdin.readline):
    for _ in range(int(readline())):
        first = second = third = out = point = 0

        while out < 3:
            event = readline()[1]

            if event == 'I':
                point += third
                third = second
                second = first
                first = 1
            elif event == 'U':
                out += 1
            else:
                point += first + second + third + 1
                first = second = third = 0

        print(point)
    exit()


if __name__ == '__main__':
    main()

Measured memory_bytes: 4228
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using Pair = pair<int, int>;
using Vec = vector<int>;
using Graph = vector<Vec>;
#define INF 100000000

int		main(void)
{
	int n;
	cin >> n;
	Vec p(n);
	for (int i = 0; i < n; i++)
		cin >> p[i];
	int c = 0;
	int min = INF;
	for (int i = 0; i < n; i++)
	{
		if (p[i] <= min)
		{
			min = p[i];
			c++;
		}
	}
	cout << c << endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
 
int main(){
    ll N;
    cin >> N;
    set<int> S;

    rep(i,N){
        ll x;
        cin >> x;
        S.insert(x);
    }

    if(S.size() != N){
        cout << "NO" << endl;
    }
    else{
        cout << "YES" << endl;
    }
}

Measured memory_bytes: 9600
#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <numeric>
#include <set>

using namespace std;
struct aaa{aaa(){cin.tie(nullptr); ios::sync_with_stdio(false); cout<<fixed<<setprecision(20);};}aaa;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v){o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
#define debug(v) {cerr<<"\033[1;36m[debug]\033[m "<<#v<<" : "<<v<<endl;}

using int64 = long long;

int main() {
    string s,t;
    cin >> t >> s;
    int n = t.size();
    int ans = INT_MAX;
    for (int i=0; i<n; i++) {
        int cnt = 0;
        if (i+s.size() > n) break;
        for (int j=0; j<s.size(); j++) {
            if (t[i+j] != s[j]) cnt++;
        }
        ans = min(ans, cnt);
    }
    cout << ans << endl;
}

Measured memory_bytes: 3160
#include<iostream>
#include<algorithm>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<iomanip>

using namespace std;
using ll = long long;

const int MOD = 1e9 + 7;
const int MAX = 1e9;
const ll LLMAX = 1e18;
const int INF = numeric_limits<int>::max();
const ll LLINF = numeric_limits<ll>::max();
const double PI = acos(-1.0);

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, a, n) for (int i = a; i <= (n); ++i)

int main() {
    ll a, b, x; cin >> a >> b >> x;

    if (a == 0) cout << b / x + 1 << endl;
    else cout << b / x - (a - 1) / x << endl;    

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
using namespace std;
using ll = long long;
using P = pair<int, int>;


int main(){
    int n, d;
    cin >> n >> d;
    int p[10][10];
    rep(i, n){
        rep(j, d) cin >> p[i][j];
    }

    int cnt = 0;

    rep(i, n){
        rep(j, i){
            if(i == j) continue;
            int sum = 0;
            rep(k, d){
                sum += (p[i][k] - p[j][k]) * (p[i][k] - p[j][k]);
            }
            int flag = false;
            rep(k, 1000){
                if(k*k == sum) flag = true;
            }
            cnt += flag;
        }
    }
    cout << cnt << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define mp make_pair
// #define pb push_back
#define ll long long
#define endl "\n"
using namespace std;



int main() {
	string s1,s2;
	cin>>s1>>s2;
	ll n=s1.length();
	ll m=s2.length();
	ll dp[n+1][m+1];
	for(ll i=0;i<=n;i++){
		for(ll j=0;j<=m;j++){
			if(i==0||j==0){
				dp[i][j]=0;
			}
			else if(s1[i-1]==s2[j-1]){
				dp[i][j]=1+dp[i-1][j-1];
			}
			else{
				dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
			}
		}
	}
	string ans="";
	ll j=m,i=n;
	while(i>=1&&j>=1){
		if(dp[i][j]==dp[i-1][j]){
			i--;
		}
		else if(dp[i][j]==dp[i][j-1]){
			j--;
		}
		else{
			ans+=s1[i-1];
			j=j-1;
		}
	}
	reverse(ans.begin(),ans.end());
	cout<<ans<<endl;
}









Measured memory_bytes: 73928
#include <vector>
#include <iostream>
#include <utility>
#include <algorithm>
#include <string>
#include <deque>
#include <queue>
#include <functional>
#include <cmath>
#include <iomanip>
#include <map>
#include <numeric>
#include <list>
#include <assert.h>
#include <math.h>
#include <valarray>
#include <stdio.h>
#include <algorithm>
#include <set>
#include <complex>
//#include <tuple>
//#include <array>
//#include <random>
//#include <windows.h>
//#pragma comment(lib, "winmm.lib")

using namespace std;
typedef long long int LL;
typedef pair<long long int, long long int> pii;
typedef pair<double, double> pdd;

#define SORT(c) sort((c).begin(),(c).end())
#define BACKSORT(c) sort((c).begin(),(c).end(),std::greater<LL>())
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

int main()
{
	LL N, K;
	cin >> N >> K;
	LL sum = K;
	FOR(i, 0, N - 1) {
		sum *= K - 1;
	}
	cout << sum << endl;
}

Measured memory_bytes: 256
#include <iostream>

using  namespace std;

int main(int argc, char *argv[]) {
	string S1, S2;
	cin >> S1 >> S2;
	if ((S1[0] == 'H') ^ (S2[0] == 'H')) printf("D\n");
	else printf("H\n");
	return 0;
}

Measured memory_bytes: 256
/*
digu_J - Digvijay Janartha
NIT Hamirpur - INDIA
*/

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;

long long pre[N], vis[N];

void test() {
    long long n, x, m;
    cin >> n >> x >> m;
    long long cur = x, ans = 0;
    int fir = -1, last = -1;
    map<int, int> mp;
    for (int i = 1; i <= n; ++i) {
        if (!cur) {
            cout << ans << "\n";
            return;
        }
        ++vis[cur];
        mp[cur] = i;
        pre[i] = pre[i - 1] + cur;
        ans += cur;
        cur *= cur;
        cur %= m;
        if (vis[cur]) {
            fir = mp[cur];
            last = i;
            break;
        }
    }
    if (last != -1) {
        n -= last;
        int len = last - fir + 1;
        long long amt = n / len;
        ans += amt * (pre[last] - pre[fir - 1]);
        n %= len;
        ans += pre[fir + n - 1] - pre[fir - 1];
    }
    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #ifdef HOME
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    int t = 1;
    // cin >> t;
    for (int i = 0; i < t; ++i) {
        test();
    }
    return 0;
}


Measured memory_bytes: 7112
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cmath>

using namespace std;

#define REP(i,n) for(int i = 0; i < (int)(n); i++)
typedef long long ll;
typedef pair<int, int> pint;

/// BIT from 蟻本を参考に
// [1, n]
const int MAX_N = 1<<18;
vector<ll> bit(MAX_N + 1);
ll n;
 
// sum(a[1]..a[n])
ll sum(int i, const int offset) {
  i += offset;
  ll s = 0;
  while(i > 0) {
    s += bit[i];
    i -= i & -i; 
  }
  return s;
}
 
// a[i] += x
void add(int i, const int x, const int offset) {
  i += offset;
  while(i < bit.size()) {
    bit[i] += x;
    //    cout << "A: " << i << " " << bit[i] << endl;
    i += i & -i;
  }
}
 
ll rev_count(const vector<int> &a) {
  fill(bit.begin(), bit.end(), 0LL);
  const int offset = a.size()+1; // -Nまでありうるので，N+1かさあげ
  n = a.size() * 2 + 2;
  //  const int offset = a.size() + 1;
  ll ans = 0;
  int sum_v = 0; 
  add(sum_v, 1, offset); // 自分との比較のために追加
  REP(j,a.size()) {
    sum_v += a[j];
    ans += sum(sum_v, offset); // <= の条件のとき
    //cout << j << ":" << a[j] << ":"<< sum_v << ":" << ans << endl;
    add(sum_v, 1, offset);
  }
  return ans;
}

ll solve(const vector<ll> &data) {
  const int N = data.size();
  ll B = N; B *= (N+1); B/=2LL; B++; B/=2LL;
  //cout << "Border = " << B << endl;
  vector<int> cmp_v(N,0);
#ifdef DEBUG
  for(int i = 0; i <= 5; i++) {
    cout << "Go....." << i << endl;
    REP(j, N) {
      cmp_v[j] = data[j] >= i ? +1 : -1;
      cout << j << data[j] << cmp_v[j] << endl;
    }
    ll ret = rev_count(cmp_v);
    
    cout << i << " " << ret << endl;
  }
  return 0;
#endif
  ll low = 0, high = 1LL<<60;
  while(low + 1 < high) {
    ll mid = (low + high) / 2LL;
    REP(j, N) {
      cmp_v[j] = data[j] >= mid ? +1 : -1;
    }
    ll ret = rev_count(cmp_v);
    //cout << mid << " " << ret << endl;
    if(ret >= B) low = mid;
    else high = mid;
  }
  return low;
}

int main() {
  int N; cin>>N;
  vector<ll> a(N);
  vector<ll> bit(2*N+10, 0);
  REP(i,N) cin>>a[i];
  ll ans = a[0];
  if(N>1) ans = solve(a);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 4992
#include "bits/stdc++.h"
int main()
{
    int t;
    std::cin >> t;
    while (t--)
    {
        int n, d; std::cin >> n >> d;
        int last = d, ret = 0;
        for (int i = 0; i < n - 1; i++)
        {
            ret += 127; last ^= 127;
        }
        std::cout << ret + last << std::endl;
    }
}

Measured memory_bytes: 256
#include<stdio.h>

int main(){
  int as = 0;
  int ae = 0;
  int bs = 0;
  int be = 0;

  scanf("%d %d %d %d", &as, &ae, &bs, &be);
  if(as - bs >=0){
    if(be - as <= 0){
      printf("0\n");
    }else if(be - as > 0 && ae - be > 0){
      printf("%d\n", be - as);
    }else if(be - as > 0 && ae - be <= 0){
      printf("%d\n", ae - as);
    }
  } else{
    if(ae - bs <= 0){
      printf("0\n");
    }else if(ae - bs > 0 && be - ae > 0){
      printf("%d\n", ae - bs);
    }else if(ae - bs > 0 && be - ae <= 0){
      printf("%d\n", be - bs);
    }
  }

  return 0;
}


Measured memory_bytes: 128
/***********************************************************
 *This code By @1353055672(Ligen)                          *
 *[Warning]You're not excepted to understand this code!    *
 *NOIP 2019 RP++                                           *
 ***********************************************************/
//#pragma GCC optimize(3)
#define ADD_STACK int size = 512 << 20;\
	char *pp = (char*)malloc(size) + size;  \
	__asm__("movl %0, %%esp\n" :: "r"(pp))
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<fstream>
#include<queue>
#include<map>
#include<stack>
#include<set>
#include<bitset>
#include<ctime>
#include<vector>
#define ll long long
#define ull unsigned long long
#define mn 200020
#define Max(x,y) (((x)>(y))?(x):(y))
#define Min(x,y) (((x)<(y))?(x):(y))
#define Abs(x) (((x)<(0))?(-(x)):(x))
#define infll (ll)(1e18)
#define infint (1<<30)
#define mod (int)(1e9+7)
#define FOR(a,b,c) for (register int a=b;a<=c;++a)
#define FORD(a,b,c) for (register int a=b;a>=c;--a)
using namespace std;
//char buf[1<<20],*p1=buf,*p2=buf;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
inline ll read(){
	ll x=0,f=1;char c;
	for(c=getchar();c<'0'||c>'9';f=((c=='-')?-1:f),c=getchar());
	for(;c>='0'&&c<='9';x=x*10+c-'0',c=getchar());return x*f;
}
template<typename T>
inline void write(T a){
	if(a==0){putchar('0');return;}if(a<0)putchar('-'),a=-a;char c1[120];int h=0;
	while(a)c1[++h]=a%10+'0',a/=10;FORD(i,h,1)putchar(c1[i]);
}
inline void write_(){return;}
template<typename T,typename... Args>
inline void write_(T a,Args... b){write(a);putchar(' ');write_(b...);}
inline void writeln(){putchar('\n');return;}
template<typename T,typename... Args>
inline void writeln(T a,Args... b){write(a);putchar(' ');writeln(b...);}
//need c++11

//inline void write(ll a){
//    if(a==0){putchar('0');return;}if(a<0)putchar('-'),a=-a;char c1[120];int h=0;
//    while(a)c1[++h]=a%10+'0',a/=10;FORD(i,h,1)putchar(c1[i]);
//}
//inline void write_(ll a){write(a);putchar(' ');}
//inline void writeln(ll a){write(a);putchar('\n');}
inline ll gcd(ll a,ll b){return a==0?b:gcd(b%a,a);}
inline ll lcm(ll a,ll b){return 1ll*a/gcd(a,b)*b;}
inline ll Pow(ll n,ll a){ll b=1;while(a){if(a&1)b=1ll*b*n%mod;n=1ll*n*n%mod;a>>=1;}return b;}
//---------------------Head Files--------------------------//

signed main(){
	#ifdef _WIN32
		// freopen("0.in","r",stdin);
		// freopen("0.out","w",stdout);
		long double be=clock();
	#endif
	int n=read(),a=read(),b=read();
	writeln(Min(n*a,b));
	#ifdef _WIN32
		long double en=clock();
		printf("Time: %.0Lfms\n",en-be);
		fclose(stdin);fclose(stdout);
	#endif
	return 0;
}

Measured memory_bytes: 256