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

using namespace std;

typedef vector<int> vi;
typedef pair<int, int> pi;
typedef long long ll;

#define show(x) cerr << #x << " = " << x << endl;
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()

ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}


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

  int n, k, e;
  cin >> n >> k;
  vector<int> v;

  while(n--){
    cin >> e;
    v.push_back(e);
  }
  sort(all(v));
  int ans = 0;
  for(int i=0; i<k; i++){
    ans += v[i];
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3624
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdlib>
using namespace std;

#define Rep(i,l,r) for (int i = (l); i <= (r); ++ i)
#define RepD(i,r,l) for (int i = (r); i >= (l); -- i)
#define RepG(i,x) for (int i = hd[x]; i; i = e[i].nxt)

const int N = 5e5+5;

char s[N]; int n, a[N], b[N];

int main() {
	scanf ("%d%s", &n, s+1);
	int ans = n;
	Rep(i,1,n) a[i] = a[i-1], a[i] += (s[i]=='W');
	RepD(i,n,1) b[i] = b[i+1], b[i] += (s[i]=='E');
	Rep(i,1,n) ans = min (ans, a[i-1]+b[i+1]);
	printf ("%d\n", ans);
	return 0;
}


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

int a[20000],b[20000];
signed main(){
    int c,d;
    cin>>c>>d;
    fill(b+1,b+c+1,1<<29);
    for(int e=0;e<c;e++)scanf("%d",&a[e]);
    sort(a,a+c,greater<int>());
    for(int f=0;f<d;f++){
	int g,h;
	scanf("%d%d",&g,&h);
	for(int i=c;i>=0;i--){
	    b[i]=min(b[i],b[max(i-g,0)]+h);
	    }
	}
	int MAX=0,sum=0;
    for(int t=0;t<=c;t++){
	MAX=max(MAX,sum-b[t]);
	sum+=a[t];
	}
	cout<<MAX<<endl;
    }

Measured memory_bytes: 3300
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <utility>
#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;

#define INF (1 << 30)
#define INFL (1LL << 62)
#define MOD7 1000000007
#define MOD9 1000000009
#define EPS 1e-10

#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pul pair<ull, ull>
#define all(a) (a).begin(), (a).end()
#define mp make_pair
#define pb push_back
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);--i)
#define REP(i,n) for (int i=0;i<(n);++i)
#define RREP(i,n) for (int i=(n)-1;i>=0;--i)

void YES() { cout << "YES" << endl; }
void NO() { cout << "NO" << endl; }
void Yes() { cout << "Yes" << endl; }
void No() { cout << "No" << endl; }
void yes() { cout << "yes" << endl; }
void no() { cout << "no" << endl; }
void Taka() { cout << "Takahashi" << endl; }
void Aoki() { cout << "Aoki" << endl; }
void digit(int d) { cout << fixed << setprecision(d); }
void IOup() { cin.tie(0); ios::sync_with_stdio(false); }

int main() {
	int a[4];
	for (int i = 0; i < 4; ++i) {
		cin >> a[i];
	}
	sort(a, a + 4);
	if (a[0] == a[1] && a[2] == a[3])
		yes();
	else
		no();

	return 0;
}

Measured memory_bytes: 3140
#include <bits/stdc++.h>
 
using namespace std;
 
int n, m;
char g[55][55];
bool v[55][55];
int dx[] = {0, 1, 0, -1};
int dy[] = {-1, 0, 1, 0};
 
bool dfs(int y, int x, int dir, int num)
{
  if(y < 0 || x < 0 || y >= n || x >= m || g[y][x] == '#') return(false);
  if(v[y][x]++) return(false);
  if(num == 0 && y == 0 && x == m - 1) ++num;
  if(num == 1 && y == n - 1 && x == m - 1) ++num;
  if(num == 2 && y == n - 1 && x == 0) ++num;
  if(num == 3 && y == 1 && x == 0) ++num;
  if(num == 4) return(true);
  (dir += 3) %= 4;
  for(int i = 0; i < 4; i++, (dir += 1) %= 4) {
    if(dfs(y + dy[dir], x + dx[dir], dir, num)) return(true);
  }
  return(false);
}
 
int main()
{
  for(;;) {
    scanf("%d%d", &n, &m);
    if(n + m == 0) break;
    for(int i = 0; i < n; i++) {
      for(int j = 0; j < m; j++) scanf(" %c", g[i] + j);
    }
    memset(v, false, sizeof(v));
    puts(dfs(0, 0, 1, 0) ? "YES" : "NO");
  }
  return 0;
}

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define ALL(a)  (a).begin(),(a).end()
constexpr int MOD = 1000000007;
constexpr int INF = 2147483647;
void yes(bool expr) {
  cout << (expr ? "Yes" : "No") << "\n";
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  string N;
  cin >> N;
  vector<vector<lint>> dp(N.size()+1, vector<lint>(2));
  dp[N.size()][1] = 1e9;
  IREP(i, N.size()) {
    dp[i][0] = dp[i+1][0] + (N[i]-'0');
    if(N[i] != 9) dp[i][0] = min(dp[i][0], dp[i+1][1] + (N[i]-'0') + 1);
    dp[i][1] = dp[i+1][1] + (10 - (N[i]-'0') - 1);
    if(N[i] != 0) dp[i][1] = min(dp[i][1], dp[i+1][0] + (10 - (N[i]-'0')));
  }
  cout << min(dp[0][0], dp[0][1]+1) << endl;
}

Measured memory_bytes: 55964
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+50,inf=1e9;
int n,k,s,a[N];
int main(){
	scanf("%d%d%d",&n,&k,&s);
	if(s==inf)for(int i=1;i<=n;i++)a[i]=i<=k?s:1;
	else for(int i=1;i<=n;i++)a[i]=i<=k?s:inf;
	for(int i=1;i<=n;i++)printf("%d ",a[i]);puts("");
}

Measured memory_bytes: 1664
n=int(input())
ar=[list(map(int,input().split())) for i in range(n)]
low=[ar[i][0] for i in range(n)]
high=[ar[i][1] for i in range(n)]
low.sort()
high.sort()
if n%2==1:
    print(high[n//2]-low[n//2]+1)
else:
    l=(low[n//2]+low[n//2-1])/2
    h=(high[n//2]+high[n//2-1])/2
    print(int((h-l)*2)+1)


Measured memory_bytes: 134256
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()

if N == 1 and M == 0:
  	print(0)
  	exit()
  
sc = [LIST() for _ in range(M)]

ans = [-1]*N

for s, c in sc:
  if N >= 2 and s == 1 and c == 0:
      print(-1)
      exit()
  if ans[s-1] != -1 and ans[s-1] != c:
      print(-1)
      exit()
  ans[s-1] = c
    
if ans[0] == -1:
  	ans[0] = 1

for i in range(N):
  if ans[i] == -1:
    ans[i] = 0
        
for n in ans:
  	print(n, end="")
print()

Measured memory_bytes: 5348
#include <stdio.h>
#include <string.h>
int main(void){
    
    int i,j;
    char a[101],b[27]={0};
    
    scanf("%s",a);
    
    for(i=0;i<strlen(a);i++){
        for(j=0;j<26;j++){
            if(a[i]-'a'==j){
                b[j]++;
            }
        }
    }
    
    for(i=0;i<26;i++){
        if(b[i]%2!=0){
            printf("No");
            return 0;
        }
    }
    printf("Yes\n");
}

Measured memory_bytes: 128
use std::vec::Vec;
use std::cmp::*;
use std::collections::HashSet;

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace().map(|e| e.parse().ok().unwrap()).collect()
}

fn main() {
    let s: usize = read();
    let mut hash: HashSet<usize> = HashSet::new();
    let mut now = 0;
    for i in 1..1_000_010 {
      if i == 1 {
        now = s;
      } else {
        now = f(now);
      }

      if hash.contains(&now) {
        println!("{}", i);
        return;
      } else {
        hash.insert(now);
      }
    }
}


fn f(n: usize) -> usize {
  if n % 2 == 0 {
    n / 2
  } else {
    3 * n + 1
  }
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef set<int> si;
typedef pair<int,int> pii;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define per(i,a,b) for(int i=(b)-1; i>=(a); --i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define F first
#define S second
const int INF = 987654321;
const ll MOD = 1000000007;
//const long double PI = (acos(-1));
//const long double EPS = 0.0000000001;
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};

int h, w;
vector<string> brd;
vector<vi> wlen;
vector<vi> hlen;

int main(void) {
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL); 
	cout.tie(NULL);
	//freopen("in.txt", "r", stdin);
	cin >> h >> w;
	brd.resize(h);
	wlen = vector<vi>(h, vi(w));
	hlen = vector<vi>(h, vi(w));
	rep(i,0,h) {
		cin >> brd[i];
	}


	rep(i,0,h) {
		int left = -1;
		rep(j,0,w) {
			if(brd[i][j] == '#') {
				for(int k=left+1; k<j; ++k) {
					wlen[i][k] = j - left - 1;
				}
				left = j;
			}
		}
		for(int k=left+1; k<w; ++k) {
			wlen[i][k] = w - left -1 ;
		}
	}

	rep(j,0,w) {
		int up = -1;

		rep(i,0,h) {
			if(brd[i][j] == '#') {
				for(int k=up+1; k<i; ++k) {
					hlen[k][j] = i - up - 1;
				}
				up = i;
			}
		}

		for(int k=up+1; k<h; ++k) {
			hlen[k][j] = h - up - 1;
		}
	}

	int ret = 0;
	rep(i,0,h) rep(j,0,w) {
		ret = max(ret, wlen[i][j]+hlen[i][j]-1);
	}
	cout << ret << endl;
	return 0;
}

Measured memory_bytes: 35968
#include<cstdio>
int a[10000],b[100];
int main(){
    int h,w,n,p=0;
    scanf("%d%d%d",&h,&w,&n);
    for(int i=0;i<n;i++)scanf("%d",&a[i]);
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            b[j]=p+1;
            a[p]--;
            if(a[p]==0)p++;
        }
        if(i%2==0){
            for(int j=0;j<w;j++)printf("%d ",b[j]);
        }else{
            for(int j=w-1;j>=0;j--)printf("%d ",b[j]);
        }
        printf("\n");
    }
    return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
4 6 1
0 1 1
0 2 4
2 0 1
1 2 2
3 1 1
3 2 5

output:
3
0
2
INF
"""

import sys
import heapq as hp
from math import isinf

WHITE, GRAY, BLACK = 0, 1, 2


def generate_adj_table(v_table):
    for each in v_table:
        source, target, cost = map(int, each)
        init_adj_table[source][target] = cost
    return init_adj_table


def dijkstra_path_heap():
    # path search init
    distance[root] = 0
    path_heap = []
    # heapq: rank by tuple[0], at here it's d[u]
    hp.heappush(path_heap, (0, root))

    while path_heap:
        current = hp.heappop(path_heap)[1]

        color[current] = BLACK

        for adj, cost in adj_table[current].items():
            if color[adj] is not BLACK:
                # alt: d[u] + w[u,v]
                alt_path = distance[current] + cost
                if alt_path < distance[adj]:
                    # update path_list
                    distance[adj] = alt_path
                    # update heap
                    hp.heappush(path_heap, (alt_path, adj))
                    color[adj] = GRAY
                    parents[adj] = current

    return distance


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices, edges, root = map(int, _input[0].split())
    v_info = map(lambda x: x.split(), _input[1:])
    # assert len(init_vertices_table) == vertices_num

    distance = [float('inf')] * vertices
    parents = [-1] * vertices
    color = [WHITE] * vertices
    init_adj_table = tuple(dict() for _ in range(vertices))

    adj_table = generate_adj_table(v_info)
    ans = dijkstra_path_heap()

    print('\n'.join(('INF' if isinf(ele) else str(ele) for ele in ans)))

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

void printline(vector<vector<char>> a, vector<vector<bool>> b, int line_n) {

  bool vacant = true;
  for (char element : a.at(line_n)) {
    if (element == '#') {
      vacant = false;
      break;
    }
  }

  if (!vacant) {
    for (int j = 0; j < a.at(0).size(); j++) {
      if (b.at(line_n).at(j)) {
        cout << a.at(line_n).at(j);
      }
    }
    cout << endl;
  }
}

int main() {
  int h, w;
  cin >> h >> w;

  vector<vector<char>> a(h, vector<char>(w, '.'));

  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      cin >> a.at(i).at(j);
    }
  }

  vector<vector<bool>> b(h, vector<bool>(w, true));

  for (int i = 0; i < h; i++) {
    bool dotline = true;
    for (int j = 0; j < w; j++) {
      if (a.at(i).at(j) == '#') {
        dotline = false;
      }
    }
    if (dotline) {
      for (int j = 0; j < w; j++) {
        b.at(i).at(j) = false;
      }
    }
  }

  for (int j = 0; j < w; j++) {
    bool dotcolumn = true;
    for (int i = 0; i < h; i++) {
      if (a.at(i).at(j) == '#') {
        dotcolumn = false;
      }
    }
    if (dotcolumn) {
      for (int i = 0; i < h; i++) {
        b.at(i).at(j) = false;
      }
    }
  }

  for (int i = 0; i < h; i++) {
    printline(a, b, i);
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef long long ll;
 
typedef vector<int> vi;;
typedef vector<ll> vll;

#define l() length()
#define sz() size()
 
#define b() begin()
#define e() end()
#define all(x) x.begin(), x.end()
 
#define pb(i) push_back(i)
#define PB() pop_back()
 
 
typedef pair<int, int> pii;
typedef pair<ll,ll> pll;
#define mp make_pair
#define Fi first
#define Se second
 
const int maxx=1e6+9;
 
// Happy Coding!


void solve(){
    
    ll n,k;
    cin>>n>>k;
    if(n==1){
        cout<<k<<endl;
        return ;
    }
    ll ans=k;
    for(int i=1;i<n;i++){
        ans*=(k-1);
    }
    cout<<ans;
    // cout<<pow(k-1,n-1)*k;
}





int main() {
    faster;
    int t=1;
    // cin>>t;
    while(t-->0){
        solve();
    }
	return 0;
}

Measured memory_bytes: 3616
n = gets.to_i
a = gets.split.map(&:to_i)
b = gets.split.map(&:to_i)
ans = 0

n.times do |i|
    if a[i] <= b[i]
        ans += a[i]
        b[i] -= a[i]
    else
        ans += b[i]
        b[i] = 0
    end
    
    if a[i+1] <= b[i]
        ans += a[i+1]
        a[i+1] = 0
    else
        ans += b[i]
        a[i+1] -= b[i]
    end
end
    
puts ans

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

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repp(i, l, r) for(int i = (l); i < (r); i++)
#define per(i, n) for(int i = ((n)-1); i >= 0; i--)
#define perr(i, l, r) for(int i = ((r)-1); i >= (l); i--)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007
#define IINF 1000000000
#define LINF 1000000000000000000
#define SP <<" "<<
#define CYES cout<<"Yes"<<endl
#define CNO cout<<"No"<<endl

typedef long long LL;
typedef long double LD;

class UnionFind{
private:
  vector<int> node;

public:
  UnionFind(int n){
    node=vector<int>(n);
    rep(i,n) node[i]=i;
  }
  int root(int x){
    if(node[x]==x) return x;
    else return node[x]=root(node[x]);
  }
  bool uni(int x,int y){
    x=root(x);
    y=root(y);
    if(x==y) return false;
    node[y]=x;
    return true;
  }
};

int main(){
  int n,m;
  cin >> n >> m;
  UnionFind uf(n);
  int x,y,z;
  int ans=n;
  rep(i,m){
    cin >> x >> y >> z;
    if(uf.uni(x-1,y-1)) ans--;
  }
  cout << ans << endl;
  return 0;
}


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

namespace ConsoleApp14
{
    class Class34
    {
        static void Main()
        {
            int N = int.Parse(Console.ReadLine());
            var x = new double[N];
            var y = new double[N];
            for(int i = 0; i < N; i++)
            {
                var read = Console.ReadLine().Split().Select(int.Parse).ToArray();
                x[i] = read[0];
                y[i] = read[1];
            }

            double ans = 0;
            double sum = 0;
            
            for(int i = 0; i < N; i++)
            {
                for(int j = i + 1; j < N; j++)
                {
                    sum += Math.Sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
                    
                }
            }
            ans = sum * 2 / N;
            Console.WriteLine(ans);
        }
        
    }
}


Measured memory_bytes: 13396
#!python
# -*- coding: utf-8 -*-


def main():
    N = int(input())
    A = [int(input()) for i in range(N)]
    X = [0 for i in range(N)]
    A += [0]
    X += [0]

    count = 0

    if A[0] != 0:
        print(-1)
        return

    for i in range(N - 1, -1, -1):
        if A[i - 1] + 1 < A[i]:
            print(-1)
            return

        X[i] = max(0, X[i + 1] - 1)
        if A[i] == X[i]:
            continue

        count += A[i]
        X[i] = A[i]

    print(count)


if __name__ == '__main__':
    main()


Measured memory_bytes: 18864
/**
class cfmaster {
 public:
  struct code {
  	see the details down there !
  };
};
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<vector<int>> g(n);
  vector<int> in_deg(n);
  for (int i = 0; i < m; i++) {
  	int x, y;
  	cin >> x >> y;
  	--x;--y;
  	g[x].push_back(y);
  	++in_deg[y];
	}
	vector<bool> was(n);
	vector<int> tp_sort;
	function<void(int)> Dfs = [&](int v) {
		was[v] = true;
		for (int u : g[v]) {
			if (was[u]) {
				continue;
			}
			Dfs(u);
		}
		tp_sort.push_back(v);
	};
	int ans = 0;
	vector<int> dp(n);
	for (int i = 0; i < n; i++) {
		if (in_deg[i] == 0 && was[i] == false) {
			Dfs(i);
			int k = (int) tp_sort.size();
			for (int j = 0; j < k; j++) {
				int v = tp_sort[j];
				for (int u : g[v]) {
					dp[v] = max(dp[v], dp[u] + 1);
				}
			}
			ans = max(ans, dp[tp_sort[k - 1]]);
			tp_sort.clear();
		}
	}
	cout << ans << '\n';
  return 0;
}



Measured memory_bytes: 11900
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define mp make_pair
#define inf 1000000007
using namespace std;
int main(){
	int n,q;
	cin>>n>>q;
	vector<int> s,t,x;
	vector< pair<int,pair<int,int> > > ev;
	for(int i=0;i<n;i++){
		int ts,tt,tx;
		cin>>ts>>tt>>tx;
		s.pb(ts-tx);t.pb(tt-tx-1);x.pb(tx);
	}
	for(int i=0;i<n;i++){
		ev.pb( mp(s[i],mp(-1,x[i])) );
		ev.pb( mp(t[i],mp(1,x[i])) );
	}
	for(int i=0;i<q;i++){
		int tm;
		cin>>tm;
		ev.pb( mp(tm, mp(0,0)) );
	}
	sort( ev.begin(), ev.end() );
	set<int> fusa;
	for(int i=0;i<ev.size();i++){
		int tim = ev[i].first;
		int tp = ev[i].second.first;
		int pl = ev[i].second.second;
		//cout<<tim<<" "<<tp<<" "<<pl<<endl;
		if(tp == -1){
			fusa.insert(pl);
		}
		if(tp == 0){
			if(fusa.empty()){
				cout<<-1<<endl;
			}
			else{
				cout<<*fusa.lower_bound(-1)<<endl;
			}
		}
		if(tp == 1){
			fusa.erase(pl);
		}
	}
	return 0;
}

Measured memory_bytes: 21328
#include<bits/stdc++.h>
using namespace std;
#define PI 3.14159265
#define seive_len 1000001

typedef long long int lli;

bool seive[seive_len];
lli primeSeive[seive_len];

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

lli lcm(lli a, lli b) {
  lli gcd_ = gcd(a, b);
  lli lcm_ = (a*b)/gcd_;
  return lcm_;
}

lli fastPower(lli a, lli b) {
  lli res=1;
  while(b > 0) {
    if(b&1)
      res *= a;
    a *= a;
    b >>= 1;
  }
  return res;
}

lli fastPowerMODp(lli a, lli b, lli MOD) {
  a %= MOD;
  lli res = 1;
  while(b) {
    if(b%2 == 1)
      res = (res*a)%MOD;
    a = (a*a)%MOD;
    b >>= 1;
  }
  return res%MOD;
}

void multiply(lli a[][2], lli b[][2], lli MOD) {
  lli res[2][2];
  memset(res, 0, sizeof(res));
  for(lli i=0;i<2;i++) {
    for(lli j=0;j<2;j++) {
      for(lli k=0;k<2;k++) {
        res[i][j] += a[i][k]*b[k][j]%MOD;
      }
    }
  }
  for(lli i=0;i<2;i++)
    for(lli j=0;j<2;j++)
      a[i][j] = res[i][j];
}

void matrixExpo(lli a[][2], lli n, lli MOD) {
  if(n == 0 || n == 1)
    return;
  lli b[][2] = {{1,1}, {1,0}};
  matrixExpo(a, n/2, MOD);
  multiply(a, a, MOD);
  if(n%2)
    multiply(a, b, MOD);
}

void makeSeive() {
  for(lli i=2;i*i<=seive_len;i++) {
    if(seive[i]) {
      for(lli j=i*i;j<=seive_len;j+=i)
        seive[j] = false;
    }
  }
}

void makePrimeSeive() {
  for(lli i=1;i<seive_len;i++)
    primeSeive[i] = i;
  for(lli i=4;i<seive_len;i+=2)
    primeSeive[i] = 2;
  for(lli i=3;i*i<seive_len;i++) {
    if(primeSeive[i] == i) {
      for(lli j=i*i;j<seive_len;j+=i) {
        if(primeSeive[j] == j)
          primeSeive[j] = i;
      }
    }
  }
}

bool isPrime(lli n) {
  for(lli i=2;i<=sqrt(n);i++) {
    if(n%i == 0)
      return false;
  }
  return true;
}

lli mod(lli x, lli MOD) {
  x %= MOD;
  if(x<0)
    x += MOD;
  return x%MOD;
}

lli inverse(lli x, lli MOD) {
  x = mod(x, MOD);
  if(x == 1)
    return x;
  return mod((-MOD/x)*inverse(MOD%x, MOD)%MOD, MOD);
}

lli NcR(lli n, lli r, vector<lli> fact, vector<lli> ifact, lli MOD) { 
  lli ret = (ifact[n - r]*ifact[r])%MOD;
  ret = (ret*fact[n])%MOD;
  return ret;
}

void getInput(vector<lli>& a, lli n) {
  lli x;
  for(lli i=0;i<n;i++) {
    cin >> x;
    a.push_back(x);
  }
}

void testCase() {
  lli i, n;
  cin >> n;
  if(n == 0)
    cout << 1;
  else
    cout << 0;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
	lli t=1;
	// cin >> t;
  // makePrimeSeive();
  // FILE* fp;
  // fp = fopen("out.txt", "w");
	for(lli i=1;i<=t;i++) {
    // fprintf(fp, "Case #%d:\n", i);
    // cout << "Case #" << i << ":" << ' ';
		testCase();
    cout << '\n';
	}
	return 0;
}

Measured memory_bytes: 3704
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int min = 1000000;
        for(int i = 0; i+2 < s.length();i++){
            String ss = s.substring(i, i+3);
            min = Math.min(min, Math.abs(Integer.parseInt(ss)-753));
        }
        System.out.println(min);
    } 
}

Measured memory_bytes: 21712
import java.util.Scanner;

import java.lang.StringBuilder;

class Main{

    public void insertionSort(int n,int[] numbers){

        toString(numbers);

        for (int i = 1; i < n; i++) {
            int key = numbers[i];
            /* insert A[i] into the sorted sequence A[0,...,j-1] */
            int j = i - 1;

            while (j >= 0 && numbers[j] > key){
                numbers[j+1] = numbers[j];
                j--;
            }

            numbers[j+1] = key;
            // print the current list
            toString(numbers);

        }
    }
    public void toString(int[] numbers){

        /**
        StringBuilder ans = new StringBuilder().append(numbers[0]);
        for (int x = 1; x < numbers.length; x++)
            ans.append(" ").append(numbers[x]);
        System.out.println(ans.toString());
         */

        String ans = "" +numbers[0];

        for (int i = 1; i < numbers.length; i++)
            ans = ans + " " + numbers[i];

        System.out.println(ans);
    }


    public static void main(String[] args){

        Scanner sc = new Scanner(System.in);
        int length = sc.nextInt();

        int[] numbers = new int[length];

        int i = 0;
        while(sc.hasNextInt() && i < length) {
            numbers[i] = sc.nextInt();
            i++;
        }

        Main is = new Main();

        is.insertionSort(length,numbers);

 
    }
}


Measured memory_bytes: 45216
A, B, K = map(int, input().split())
if B-A+1 >= 2*K:
    res_set = set([i for i in range(A, A+K)]) | set([i for i in range(B-K+1, B+1)])
    for i in sorted(res_set):
        print(i)
else:
    res_list = [i for i in range(A, B+1)]
    for i in res_list:
        print(i)


Measured memory_bytes: 3060
#include <stdio.h>

int main(void) 
{
	int age,price;
	scanf("%d%d",&age,&price);
	if(age >= 13){
		printf("%d\n",price);
	}
	if(age >= 6 && age <= 12){
		price = price / 2;
		printf("%d\n",price);
	}
	if(age <= 5) printf("%d\n",0);
}

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

using namespace std;

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

  int N, M;
  cin >> N >> M;

  auto constexpr NONE = numeric_limits<int>::max();
  auto all_bits = ceil(pow(2, N)) - 1;
  // cout << " all_bits " << all_bits << endl;
  vector<vector<int>> dp(M + 1, vector<int>(all_bits + 1, NONE));

  vector<int> costs(M);
  vector<int> bits(M);

  for (int i = 0; i < M; ++i) {
    int a, b;
    cin >> a >> b;
    costs[i] = a;
    int bit = 0;
    for (int j = 1; j <= b; ++j) {
      int c;
      cin >> c;
      bit |= (1 << (c - 1));
    }
    // cout << " bit for " << i << " : " << bit  << endl;
    bits[i] = bit;
  }

  for (int m = 0; m < M; ++m) {
    auto& cur = dp[m];
    auto& next = dp[m + 1];
    next = cur;
    auto cost = costs[m];
    auto bit = bits[m];
    cur[0] = 0;
    for (size_t i = 0; i < cur.size(); ++i) {
      if (cur[i] != NONE) {
        auto next_cost = cost + cur[i];
        auto next_bit = i | bit;
        next[next_bit] = min(next[next_bit], next_cost);
      }
    }
  }

  auto res = dp[M][all_bits];
  cout << (res == NONE ? -1 : res) << endl;
}


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

typedef long long ll;
typedef long double ld;
typedef vector<ll> vi;
typedef pair<ll, ll> pii;
typedef vector<pii> vii;
typedef vector<vi> vvi;
const int MOD = 1e9 + 7;

#define fastIO \
ios_base::sync_with_stdio(false); cin.tie(nullptr);
#define endl '\n'
#define pb push_back
#define ff first
#define ss second
#define mp make_pair 
const ll INF = ll(1e18) + 42;
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
    cerr << name << " = " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char *names, Arg1 &&arg1, Args&&... args) {
    const char *comma = strchr(names + 1, ',');
    cerr.write(names, comma - names) << " = " << arg1 << " |";
    __f(comma + 1, args...);
}

int n;
vi dp, group_score;
vvi a;

void rec(int idx, int mask, const vector<int>& not_taken, int group) {
    if (idx == int(not_taken.size()))    {
        dp[mask | group] = max(dp[mask | group], dp[mask] + group_score[group]);
        return;
    }
    rec(idx + 1, mask, not_taken, group);
    rec(idx + 1, mask, not_taken, group | (1 << not_taken[idx]));
}

int main() {
    fastIO;
    cin >> n;
    dp.assign((1 << n), -INF);
    group_score.assign((1 << n), -INF);
    
    a.resize(n, vi(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            cin >> a[i][j];
    }
    for (int group = 0; group < (1 << n); group++) {
        group_score[group] = 0;
        for (int i = 0; i < n; i++) {
            if (group & (1 << i)) {
                for (int j = i + 1; j < n; j++) {
                    if (group & (1 << j)) {
                        group_score[group] += a[i][j];
                    }
                }
            }
        }
    }
    // dp[mask] = best score so far with masked rabbits taken in some group and their groups closed
    dp[0] = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        vector<int> not_taken;
        for (int i = 0; i < n; i++) {
            if (!(mask & (1 << i)))
                not_taken.pb(i);
        }
        rec(0, mask, not_taken, 0);
    }
    cout << dp[(1 << n) - 1] << endl;
    return 0;
}


Measured memory_bytes: 1280
#include <bits/stdc++.h>
#define sz(c)      int(c.size())
#define rep(i,a,b) for (int i=a; i<(b); ++i)
#define per(i,a,b) for (int i=(b)-1; i>=(a); --i)
using namespace std;
using ll = long long;



int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	cout<<fixed<<setprecision(10);

	int N,M;
	cin>>N>>M;
	vector<int> a(M);
	rep(i,0,M) {
		int k;
		cin>>k;
		rep(j,0,k) {
			int x;
			cin>>x;
			a[i]|=1<<(x-1);
		}
	}
	vector<int> p(M);
	rep(i,0,M) cin>>p[i];
	
	int res=0;
	rep(mask,0,1<<N) {
		int on=0;
		rep(i,0,M) if (__builtin_popcount(a[i]&mask)%2==p[i]) on++;
		if (on==M) res++;
	}
	cout<<res<<"\n";
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
    string s;
    cin>>s;
    int n=s.size();
    bool found;
    char c='a';

    while( c<='z')
        {
            found=true;
            for(int i=0; i<n; i++)
            {
              if(s[i]==c)
                found=false;
            }
            if(found)
            {
            cout<<c;
            return 0;
            }
            else
                c+=1;

        }

        cout<<"None";


    return 0;
}


Measured memory_bytes: 512
#include <stdio.h>

#define W 0
#define G 1
#define B 2
int n,M[100][100];

int prim(){
  int i,v,u,minv;
  int d[100],p[100],color[100];

  for(i=0;i<n;i++){
    d[i] = 1000000;
    p[i] = -1;
    color[i] = W;
  }

  d[0] =0;

  while(1){
    minv = 1000000;
    u =-1;
    for(i=0;i<n;i++){
      if(minv>d[i] && color[i] != B){
	u = i;
	minv = d[i];
      }
    }
    if(u == -1){
      break;
    }
    color[u] = B;
    for(v=0;v<n;v++){
      if(color[v] != B && M[u][v] != 1000000){
	if(d[v] > M[u][v]){
	  d[v] = M[u][v];
	  p[v] = u;
	  color[v] = G;
	}
      }
    }
  }
  int sum = 0;
  for(i=0;i<n;i++){
    if(p[i] != -1){
      sum += M[i][p[i]];
    }
  }

  return sum;
}

int main(){
  int i,j,temp;

  scanf("%d",&n);
  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      scanf("%d",&temp);
      M[i][j] = (temp == -1) ? 1000000 : temp;
    }
  }

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

  return 0;
}

Measured memory_bytes: 636
#include<stdio.h>
#include<string.h>
#include<math.h>
int main(){
	int k;
	scanf("%d",&k);
	float a,b,x,y;
	scanf("%f %f",&a,&b);
	x=a/k;
	y=b/k;
	int i,t=0;
	for(i=floor(x);i<=floor(y);i++){
		if(i>=x && i<=y) {
			t=1;break;
        }
	}
	if(t==1) printf("OK");
	else printf("NG");
	return 0;
}

Measured memory_bytes: 1740
#include <bits/stdc++.h> 
using namespace std;
using ll = long long;
//>:(
void solve() {
    int N;
    cin >> N;
    vector<ll> a(N),b(N);
    for(int i=0;i<N;i++) cin >> a[i] >> b[i];
    ll cnt=0;
    for(int i=N-1;i>=0;i--) {
        a[i]+=cnt;
        cnt+=(a[i]+b[i]-1)/b[i]*b[i]-a[i];
    }
    cout << cnt << "\n"; 
}

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

    solve();
    return 0;
}

Measured memory_bytes: 2428
n, k = map(int, input().split())
q = list(map(int, input().split()))
v = [-1]*(n+1)
p = []
a = 1
c = 0
while 1:
    if v[a] != -1:
        l = c-v[a]
        if k < c:
            print(p[k])
        else:
            print(p[(k-v[a])%l+v[a]])
        break
    v[a] = c
    c += 1
    p.append(a)
    a = q[a-1]

Measured memory_bytes: 32300
#pragma once
#include <stdio.h>
#include <sstream>
#include <string.h>
#include <vector>
#include <map>
#include <algorithm>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <deque>
#include <limits>
#include <iomanip>
#include <ctype.h>
#define _USE_MATH_DEFINES
#include <iostream>
#include <math.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define bit(x,v) ((ll)x << v)

const ll INF = 1000000007;
const int MAX = 210000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

// 二項係数計算
long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}
int pr[100010];
void uini(int n) {
	for (size_t i = 0; i <= n; i++)
	{
		pr[i] = i;
	}
}

int parent(int x) {
	if (x == pr[x]) return x;
	return pr[x] = parent(pr[x]);
}

bool unit(int x, int y) {
	int px = parent(x);
	int py = parent(y);

	if (px == py) return false;
	if (px < py) {
		pr[py] = px;
	}
	else {
		pr[px] = py;
	}
	return true;
}

ll bit[200010];
int max_n = 200000;
int pm = 0;
void add(int x) {

	while (max_n >= x)
	{
		bit[x]++;
		x += x & -x;
	}
}
void sub(int x) {
	while (max_n >= x)
	{
		bit[x]--;
		x += x & -x;
	}
}
int search(int x) {

	int k = 0;
	int p = 1;
	while (p * 2 <= max_n)
	{
		p *= 2;
	}
	for (int i = p; i > 0; i /= 2)
	{
		if (i + k < max_n && bit[i + k] < x) {
			x -= bit[i + k];
			k += i;
		}
	}
	return k + 1;
}
void solv() {
	int n;

	while (cin >> n)
	{
		if (n == 0) break;
		double s[1010];
		double sum = 0;
		for (size_t i = 0; i < n; i++)
		{
			cin >> s[i];
			sum += s[i];
		}
		double av = sum / (double)n;
		double a2 = 0;
		for (size_t i = 0; i < n; i++)
		{
			a2 += (s[i] - av) * (s[i] - av);
		}

		cout << fixed << setprecision(10) << sqrt(a2 / (double)n) << endl;

	}
}
int main() {
	//	COMinit();
	solv();
	return 0;
}



Measured memory_bytes: 3300
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(true){
            int H = sc.nextInt();
            int W = sc.nextInt();
            if(H==0 && W==0){
                break;
            }
            for(int i=0; i<H; i++){
                for(int j=0; j<W; j++){
                    System.out.print("#");
                }
                System.out.println("");
            }
            System.out.println("");
        }   
    }
}


Measured memory_bytes: 34556
//把n转为b进制下各个位数的和，若与s相同则是答案
#include<bits/stdc++.h>
using namespace std;
#define f1(a,b,c) for(ll c=a;c<=b;c++)
#define f2(a,b,c) for(int c=a;c>=b;c--)
#define f3(a,b,c) for(int c=a;c;c=b)
#define so1(a,n) sort(a+1,a+n+1,mycmp);
#define so2(a,n) sort(a+1,a+n+1);
#define ll long long
#define itn int
#define ubt int 
const int twx=+100;
const ll inf=0x7ffffffffffff;
ll read()
{
    ll sum=0;
    ll flag=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')
        {
            flag=-1;
        }
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        sum=((sum*10)+c-'0');
        c=getchar();
    }
    return sum*flag;
}
ll f(ll b,ll n)
{
    if(n<b)
    {
        return n;
    }
    if(n>=b)
    {
        return f(b,n/b)+n%b;
    }
}
ll n,s;
void init()
{
	n=read();
    s=read();
    if(n<s)
    {
        puts("-1");
        exit(0);
    }
    if(n==s)
    {
        printf("%lld",n+1);
        exit(0);
    }
    ll asd=sqrt(n)+1;
    f1(2,asd,i)
    { 
        if(f(i,n)==s)
        {
            printf("%lld\n",i);
            exit(0);
        }
    }
    n-=s;
    ll res=inf;
    ll qwe=sqrt(n);
    f1(1,qwe,i)
    {
        if(n%i==0)
        {
            ll b=n/i+1;
            ll aa=s-i;
            ll bb=i;
            if(b>=2&&aa>=0&&aa<b&&bb<b)
            {
                res=min(res,b);
            }
        }
    }
    if(res==inf)
    {
        puts("-1");
    }
    else
    {
        printf("%lld",res);
    }
    
}
void work()
{
	
}
void print()
{
	
}
int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
    init();
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cmath>
#include<string>
#include<cctype>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
        int W,H,x,y,r;
        cin>>W>>H>>x>>y>>r;
        if((r<=x && (W-r)>=x)&&(r<=y && (H-r)>=y)){
                cout<<"Yes"<<endl;
        }else{
                cout<<"No"<<endl;
        }
        return 0;
}

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

int main(){
  int val[20],tbl[21][50001];
  int n,m;
  for (int i= 0;i<50001;i++)tbl[0][i] = 50001;
  for (int i=0;i<21;i++)tbl[i][0]=0;

  cin >> n >> m;

  for (int i=0;i<m;i++)
    cin >> val[i];

  for (int i = 1;i <= m;i++){
    for (int j = 1;j<=n;j++){
      if (j-val[i-1]<0) tbl[i][j]=tbl[i-1][j];
      else tbl[i][j]=min(tbl[i-1][j],tbl[i][j-val[i-1]]+1);
      //cout << tbl[i][j];
    }
    //cout << endl;
  }

  cout << tbl[m][n] << endl;
  return 0;
}

Measured memory_bytes: 7188
#include<stdio.h>
#include<stdlib.h>
int main()
{
  int N;
  long long int power=1;
  
  scanf("%d",&N);
  
  for(int i=1;i<=N;i++)
    power=i*power%(1000000000+7);
  printf("%lld",power);
  
  return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<bitset>
#include<cctype>
#include<climits>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<deque>
#include<list>
#include<map>
#include<set>
#include<stack>
#include<string>
#include<sstream>
#include<queue>
#include<vector>
using namespace std;

int main() {
	int a[100][100] = {};
	int i = 0;
	for (string s; getline(cin, s) && s != "$";) {
		bool flag = false; //2??±?????????
		int j = 0;
		for (int c = 0; c < s.size(); c++) {
			if (s[c] == ',') {
				flag = false;
				j++;
			}
			else {
				if (flag) {
					a[i][j] = a[i][j] * 10 + (s[c] - '0');
				}
				else {
					a[i][j] = s[c] - '0';
					flag = true;
				}
			}
		}
		i++;
	}

	int dp[100][100] = {};
	dp[0][0] = a[0][0];
	int k = 1;
	for (; k <= i / 2; k++) {
		dp[k][0] = dp[k - 1][0] + a[k][0];
		for (int l = 1; l <= k; l++) {
			dp[k][l] = max(dp[k - 1][l - 1], dp[k - 1][l]) + a[k][l];
		}
	}
	for (; k <= i; k++) {
		//cout << k << " " << dp[k - 1][j - k + 2] << endl;
		dp[k][i - k + 1] = dp[k - 1][i - k + 2] + a[k][i - k + 1];
		for (int l = 0; l < i - k + 1; l++) {
			dp[k][l] = max(dp[k - 1][l + 1], dp[k - 1][l]) + a[k][l];
		}
	}
	//for (int x = 0; x < 50; x++) {
	//	for (int y = 0; y < 50; y++) {
	//		cout << a[x][y] << " ";
	//	}
	//	cout << endl;
	//}
	//cout << endl;
	//for (int x = 0; x < 50; x++) {
	//	for (int y = 0; y < 50; y++) {
	//		cout << dp[x][y] << " ";
	//	}
	//	cout << endl;
	//}
	cout << dp[i][0] << endl;
	return 0;
}

Measured memory_bytes: 1268
#define _USE_MATH_DEFINES
#include<iostream>
#include<string>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<random>
#include<functional>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<cstring>
#include<bitset>
#include<unordered_map>
#include<climits>
#include<fstream>
#include<time.h>
#include<cassert>

using namespace std;
#define ll long long
#define ld long double
#define int long long
#define all(a) (a).begin(),(a).end()
#define EPS (1e-13)
#define fs first
#define sc second
#define xx first
#define yy second.first
#define zz second.second
#define H pair<int, int>
#define P pair<int, pair<int, int>>
#define Q(i,j,k) mkp(i,mkp(j,k))
#define rep(i,n) for(int (i) = 0 ; (i) < (n) ; (i)++)
#define mkp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define crdcomp(b) sort(all((b)));(b).erase(unique(all((b))),(b).end())
#define ssp(i,n) (i==n-1?"\n":" ")
const int mod = 1e9 + 7;
const int Mod = 998244353;
const ll Inf = 3 * 1e18;
const int inf = 15 * 1e8;
ll read() {
	ll u, k = scanf("%lld", &u);
	return u;
}
ll gcd(ll i, ll j) {
	if (i > j) swap(i, j);
	if (i == 0) return j;
	return gcd(j % i, i);
}
ll mod_pow(ll x, ll n, ll p) {
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = res * x % p;
		x = x * x % p;
		n >>= 1;
	}
	return res;
}
ll bcount(ll x) {
	int sum = 0;
	for (int i = 0; i < 20; i++)
		if ((1ll << i) & x) sum++;
	return sum;
}
const int fn_ = 2000000;
ll fact_[fn_], comp_[fn_];
ll comb(ll x, ll y, ll Mod = mod) {
	if (!fact_[0]) {
		fact_[0] = 1; comp_[0] = 1;
		for (int i = 1; i < fn_; i++) {
			fact_[i] = fact_[i - 1] * i % Mod;
			comp_[i] = mod_pow(fact_[i], Mod - 2, Mod);
		}
	}
	if (x < y) return 0;
	return fact_[x] * comp_[x - y] % Mod * comp_[y] % Mod;
}
//---------------------------------------------------
int n, m;
ld dat[500000];
void update(int i, ld x) {
	i += m - 1;
	dat[i] = x;
	while (i > 0) {
		i = (i - 1) / 2;
		dat[i] = dat[i * 2 + 1] * dat[i * 2 + 2];
	}
}
ld query(int i, int a, int b, int l, int r) {
	if (b <= l || r <= a) return 1;
	if (a <= l && r <= b) return dat[i];
	return query(i * 2 + 1, a, b, l, (l + r) / 2) * query(i * 2 + 2, a, b, (l + r) / 2, r);
}
vector<int>b;
vector<H>a;
signed main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		int u, v;
		cin >> u >> v;
		a.push_back(H{ u, v });
		b.push_back(u);
	}
	for (int i = 0; i < 200000; i++) dat[i] = 1;
	crdcomp(b);
	m = 1;
	while (m < b.size()) m *= 2;
	for (int i = 0; i < n; i++) {
		a[i].fs = lower_bound(all(b), a[i].fs) - b.begin();
		update(a[i].fs, 1 - a[i].sc / 10.);
	}
	int q;
	cin >> q;
	for (int i = 0; i < q; i++) {
		int l, r;
		cin >> l >> r;
		int k = lower_bound(all(b), l) - b.begin();
		int g = upper_bound(all(b), r) - b.begin();
		if (k == b.size()) cout << 1e9 << endl;
		else printf("%.10LF\n", 1000000000.0 * query(0, k, g, 0, m));
	}
}


Measured memory_bytes: 9932
///   ***   ---   |||         In the name of ALLAH        |||   ---   ***   ///



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


typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef double dl;

#define endl '\n'
#define PB push_back
#define F first
#define S second
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define sz(x) (int)x.size()

const double PI = acos(-1);
const double eps = 1e-9;
const int inf = 2000000000;
const ll infLL = 9000000000000000000;
#define MOD 1000000007

#define mem(a,b) memset(a, b, sizeof(a) )
#define sqr(a) ((a) * (a))

#define optimize() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define fraction() cout.unsetf(ios::floatfield); cout.precision(10); cout.setf(ios::fixed,ios::floatfield);
#define file() freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);

#define dbg(args...) do {cerr << #args << " : "; faltu(args); } while(0)
void faltu () {            cerr << endl;}
template < typename T, typename ... hello>void faltu( T arg, const hello &... rest) {cerr << arg << ' ';faltu(rest...);}

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

const int mx = 2e5+123;
ll sumA[mx], sumB[mx];
ll a[mx], b[mx];

int main()
{
    optimize();

    int n, m, k;
    cin >> n >> m >> k;


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

    vl v;
    for ( int i = 1; i <= m; i++ ) {
        cin >> b[i];
        sumB[i] = b[i] + sumB[i-1];
        v.PB ( sumB[i] );
    }

    int ans = 0;
    for ( int i = 0; i <= n; i++ ) {
        if ( k - sumA[i] >= 0 ) {
            int up = upper_bound( all ( v ), k - sumA[i] ) - v.begin();
           // dbg ( up, k-sumA[i] );
            ans = max ( ans, i + up );
        }
    }

    cout << ans << endl;


    return 0;
}


















Measured memory_bytes: 11284
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;
const int MaxN = 1e4;

int vis[3 * MaxN + 5];
int ans[3 * MaxN + 5];

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

int main()
{
	int n,ans1,biu,x;
	while(~scanf("%d",&n))
	{
		memset(vis,0,sizeof(vis));
		n -= 2;
		printf("2 3");
		vis[2] = 1;
		ans[1] = 2;
		ans[2] = 3;
		vis[3] = 1;
		ans1 = 5;
		biu = 2;
		for(int i = 4;i <= 3 * MaxN;i++)
		{
			if(n == 1) break;
			if(i % 2== 0||i % 3 == 0) 
			{
				vis[i] = 1;
				ans[++biu] = i;
				printf(" %d",i);
				ans1 += i;
				n--;
			}
		}
		for(int i = 2;i <= 3 * MaxN;i++)
		{
			if(vis[i] == 0)
			{
				if(gcd(ans1,i) != 1)
				{
					x = 0;
					for(int j = 1;j <= biu;j++)
					{
						if(gcd(ans1 - ans[j] + i,ans[j]) == 1)
						{
							x =  1;
							break;
						}
					}
					if(x != 1)
					{
						printf(" %d",i);
						break;
					}
				}
			}
		}
		printf("\n");
	}
	return 0;
}

Measured memory_bytes: 512
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <bitset>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <string>
#include <chrono>
#include <random>
#include <cmath>
#include <cassert>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <functional>
#include <sstream>

using namespace std;



int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(0);


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

    for (int i = 0; i < n; ++i) {
        A[i] -= i + 1;
    }
    sort(A.begin(), A.end());

    int b = A[(n - 1) / 2];
    long long res = 0;
    for (auto x : A) {
        res += abs(x - b);
    }

    cout << res << '\n';

    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <cstring>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;

typedef pair<int,int> P;

int n, m;
vector<P> t[200];
int dp[200][12][200];

void solve(){
  for(int i = 0; i < 200; i++){
    for(int j = 0; j < 12; j++){
      for(int k = 0; k < 200; k++){
	dp[i][j][k] = INT_MAX;
      }
      if(i == 0) dp[i][j][0] = 0;
    }
  }

  for(int i = 0; i < n; i++){
    for(int j = 0; j < t[i].size(); j++){
      for(int k = 0; k <= m; k++){
	if(dp[i][j][k] == INT_MAX) continue;

	for(int nj = 0; nj < t[i + 1].size(); nj++){
	  int add = (i == 0 ? 0 : (t[i][j].second + t[i + 1][nj].second) * abs(t[i][j].first - t[i + 1][nj].first));
	  dp[i + 1][nj][k] = min(dp[i + 1][nj][k], dp[i][j][k] + add);
	}

	if(k == m) continue;

        for(int nj = 0; nj < t[i + 2].size(); nj++){
          int add = (i == 0 ? 0 : (t[i][j].second + t[i + 2][nj].second) * abs(t[i][j].first - t[i + 2][nj].first));
          dp[i + 2][nj][k + 1] = min(dp[i + 2][nj][k + 1], dp[i][j][k] + add);
        }
      }
    }
  }

  int ans = INT_MAX;

  for(int i = 0; i < t[n].size(); i++){
    for(int j = 0; j <= m; j++){
      ans = min(ans, dp[n][i][j]);
    }
  }

  if(n == 1){
    if(m >= 1) ans = 0;
    cout << ans << endl;
    return;
  }

  for(int i = 0; i < t[n - 1].size(); i++){
    for(int j = 0; j <= m - 1; j++){
      ans = min(ans, dp[n - 1][i][j]);
    }
  }

  cout << ans << endl;
}

int main(){
  while(cin >> n >> m , n || m){
    for(int i = 0; i < 200; i++){
      t[i].clear();
    }
    t[0].push_back(P(0, 0));

    for(int i = 1; i <= n; i++){
      int k;
      cin >> k;

      while(k--){
	int x, d;
	cin >> x >> d;
	x--;
	t[i].push_back(P(x, d));
      }
    }

    solve();
  }
}

Measured memory_bytes: 3104
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define db double
#define pint pair<int,ll>
#define mk make_pair
#define pb push_back
#define eb emplace_back
#define ins insert
#define fi first
#define se second
#define Rep(x,y,z) for(int x=y;x<=z;x++)
#define Red(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
const int MAXM=5e6+5,MAXN=2005,Mod=1e9+7;
char buf[1<<12],*pp1=buf,*pp2=buf,nc;int ny;
inline char gc() {return pp1==pp2&&(pp2=(pp1=buf)+fread(buf,1,1<<12,stdin),pp1==pp2)?EOF:*pp1++;}
//inline char gc(){return getchar();}
inline int read(){
	int x=0;for(ny=1;nc=gc(),(nc<48||nc>57)&&nc!=EOF;)if(nc==45)ny=-1;if(nc<0)return nc;
	for(x=nc-48;nc=gc(),47<nc&&nc<58&&nc!=EOF;x=(x<<3)+(x<<1)+(nc^48));return x*ny;
}
int n,k,Fac[MAXM],iFac[MAXM],F[MAXN][MAXN];
inline int Fp(int x,int k){int ans=1;for(;k;k>>=1,x=1ll*x*x%Mod)if(k&1)ans=1ll*ans*x%Mod;return ans;}
inline void Init(int n){
	Fac[0]=1;Rep(i,1,n)Fac[i]=1ll*Fac[i-1]*i%Mod;
	iFac[n]=Fp(Fac[n],Mod-2);Red(i,n,1)iFac[i-1]=1ll*iFac[i]*i%Mod;
}
inline int C(int n,int m){return n<0||m<0||n<m?0:1ll*Fac[n]*iFac[m]%Mod*iFac[n-m]%Mod;}
int main(){
//	freopen("std.in","r",stdin);
//	freopen("std.out","w",stdout);
	n=read(),k=read();
	if(n==1||k==1)return puts("1"),0;
	Init((n+1)*k);F[0][0]=1;Rep(i,1,n)F[0][i]=1ll*F[0][i-1]*C(i*(k-1)-1,k-2)%Mod;
	Rep(i,1,n)Rep(j,i,n)F[i][j]=(F[i-1][j]+1ll*F[i][j-1]*C(i+j*(k-1)-1,k-2))%Mod;
	cout<<1ll*F[n][n]*Fac[n]%Mod<<'\n';
	return 0;
}




Measured memory_bytes: 48612
#include<bits/stdc++.h>
using namespace std;
int n,k;
int a[100010];
int main(){
	vector<int> v;
	cin>>n>>k;
	for(int i=0;i<n;i++){
		cin>>a[i];
		v.push_back(a[i]);
	}
	sort(v.begin(),v.end());
	int cnt=1e9;
	for(int i=0;i<=v.size()-k;i++){
		cnt=min(cnt,v[i+k-1]-v[i]);
	}
	cout<<cnt<<endl;
	return 0;
}

Measured memory_bytes: 1148