akhauriyash/Code-Regression huggingface dataset:
def myAnswer(N: int, A: list) -> int:
    counter = 0
    for a in A:
        if(a % 2 == 0):
         while a %2 == 0:
            counter+=1
            a //= 2
    return counter



def modelAnswer():
    tmp = 1


def main():
    N = int(input())
    A = list(map(int, input().split()))
    print(myAnswer(N, A[:]))


if __name__ == '__main__':
    main()


Measured memory_bytes: 4148
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc=new Scanner(System.in);

		String str=sc.next();

		String[] strs=str.split("/");

		if(Integer.parseInt(strs[1])>4) System.out.println("TBD");
		else System.out.println("Heisei");

		sc.close();

	}

}


Measured memory_bytes: 21844
#include <iostream>
#include <algorithm>
using namespace std;
int main(void){
    int n;
    std::cin >> n;
    int a[101]={};
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    sort(a,a+n);
    std::cout << a[n-1]-a[0] << std::endl;
    
}


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

using namespace std;

int main(){
	int N;
	cin >> N;
	long a[300000];
	for (int i=0; i<3*N; i++) cin >> a[i];
	long long max = 0;
	sort(a, a+3*N);
	for (int i=0; i<2*N; i++) {
		if (i%2 == 1) {
			max += a[3*N-1-i];
		}
	}
	cout << max << endl;

	return 0;
}


Measured memory_bytes: 2688
n, k = map(int, input().split())


def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)


def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

def com(n, r, mod):
    r = min(r, n - r)
    if r == 0:
        return 1
    res = ilist[n] * iinvlist[n-r] * iinvlist[r] % mod
    return res


mod = 10**9+7

ilist = [0]
iinvlist = [1]
tmp = 1
for i in range(1, n+1):
    tmp *= i
    tmp %= mod
    ilist.append(tmp)
    iinvlist.append(modinv(tmp, mod))

ans = 0
k = min(n-1, k)
for i in range(k+1):
    tmp = com(n, i, mod)
    tmp *= com(n-1, i, mod)
    ans += tmp
    ans %= mod


print(ans)

Measured memory_bytes: 104540
using System;

public class hello
{
    public static void Main()
    {
        while (true)
        {
            string[] line = Console.ReadLine().Trim().Split(' ');
            if (line[0] == "#") break;
            var yy = int.Parse(line[1]);
            var mm = int.Parse(line[2]);
            if (yy >= 32 | (yy == 31 && mm >= 5)) { line[0] = "?"; line[1] = (yy - 30).ToString(); }
            Console.WriteLine(string.Join(" ", line));
        }
    }
}






Measured memory_bytes: 13892
#include <stdio.h>

#define MAX 100000
#define SENTINEL 2000000000

struct Card{
	char suit;
	int value;
};

struct Card L[MAX/2+2],R[MAX/2+2];

void merge(struct Card A[],int n,int left,int mid,int right){
	int i,j,k;
	int n1=mid-left;
	int n2=right-mid;
	for(i=0;i<n1;i++) L[i]=A[left+i];
	for(i=0;i<n2;i++) R[i]=A[mid+i];
	L[n1].value = R[n2].value = SENTINEL;
	i=j=0;
	for(k=left;k<right;k++){
		if(L[i].value<=R[j].value){
			A[k]=L[i++];
		}else{
			A[k]=R[j++];
		}
	}
}

void mergeSort(struct Card A[],int n,int left,int right){
	int mid;
	if(left+1<right){
		mid=(left+right)/2;
		mergeSort(A,n,left,mid);
		mergeSort(A,n,mid,right);
		merge(A,n,left,mid,right);
	}
}

int partition(struct Card A[],int n,int p,int r){
	int i,j;
	struct Card t,x;
	x=A[r];
	i=p-1;
	for(j=p;j<r;j++){
		if(A[j].value<=x.value){
			i++;
			t=A[i];A[i]=A[j];A[j]=t;
		}
	} 
	t=A[i+1];A[i+1]=A[r];A[r]=t;
	return i+1;
}

void quickSort(struct Card A[],int n,int p,int r){
	int q;
	if(p<r){
		q=partition(A,n,p,r);
		quickSort(A,n,p,q-1);
		quickSort(A,n,q+1,r);
	}
}



int main() {
	
	int n,i,v;
	struct Card A[MAX],B[MAX];
	char S[10];
	int stable = 1;
	
	scanf("%d",&n);
	
	for(i=0;i<n;i++){
		scanf("%s %d",S,&v);
		A[i].suit=B[i].suit=S[0];
		A[i].value=B[i].value=v;
	}
	
	mergeSort(A,n,0,n);
	quickSort(B,n,0,n-1);
	
	for(i=0;i<n;i++){
		if(A[i].suit!=B[i].suit) {
			stable = 0;
			break;
		}
	}
	
	if(stable==1) printf("Stable\n");
	else printf("Not stable\n");
	for(i=0;i<n;i++){
		printf("%c %d\n",B[i].suit,B[i].value);
	}
	
	return 0;
}

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

int main() {

	char porm[4];
	int i,ans=0;

	for (i = 0; i < 4; i++) {
		cin >> porm[i];
		if (porm[i] == '+') {
			ans++;
		}
		else if (porm[i] == '-') {
			ans--;
		}
	}

	cout << ans;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
struct fast_ios { fast_ios(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define REP(i, n) FOR(i,0,n)
template <typename T> bool chmax(T &m, const T q) { if (m < q) {m = q; return true;} else return false; }


int main()
{
    int N, K;
    cin >> N >> K;
    vector<int> P(N), C(N);
    for (auto &x : P) cin >> x, x--;
    for (auto &x : C) cin >> x;

    vector<lint> loopsum(N);
    vector<int> looplen(N);
    REP(i, N) if (!looplen[i])
    {
        int j = i;
        while (true)
        {
            loopsum[i] += C[j];
            looplen[i]++;
            j = P[j];
            if (j == i) break;
        }
        while (true)
        {
            looplen[j] = looplen[i];
            loopsum[j] = loopsum[i];
            j = P[j];
            if (j == i) break;
        }
    }

    lint ret = -2e18;
    REP(i, N)
    {
        if (loopsum[i] > 0)
        {
            lint nbl = max(K / looplen[i] - 1, 0);
            lint tmp = nbl * loopsum[i];
            int now = i;
            if (nbl) chmax(ret, tmp);
            REP(_, K - looplen[i] * nbl)
            {
                now = P[now];
                tmp += C[now];
                chmax(ret, tmp);
            }
        }
        else
        {
            int now = i;
            lint tmp = 0;
            REP(t, K)
            {
                now = P[now];
                tmp += C[now];
                chmax(ret, tmp);
                if (t > looplen[i]) break;
            }
        }
    }
    cout << ret << '\n';
}


Measured memory_bytes: 3728
// inputに入力データ全体が入る
function Main(input) {
	input = input.split("\n");
	const input1 = input[0].split(" ");
	const L = parseInt(input1[0]);
	const R = parseInt(input1[1]);

	if (Math.floor((R - L) / 2019) > 2) {
		console.log(0);
	} else if (Math.floor((R - L) / 2019) > 1) {
		console.log(0);
	} else {
		if (R % 2019 < L % 2019) {
			console.log(0);
		} else {
			var min = 2019;
			for (i = L % 2019; i < R % 2019; i++) {
				for (j = L % 2019 + 1; j <= R % 2019; j++) {
					if (min > (i * j) % 2019) min = (i * j) % 2019;
				}
			}
			console.log(min);
		}
	}

}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 7372
chess = '#.'*150
chess_reverse = '.#'*150

while True:
    h,w = map(int,input().split())
    if h+w == 0:
        break
    else:
        for i in range(h):
            if i % 2 == 0:
                print(chess[:w])
            else:
                print(chess_reverse[:w])
        print('\r')


Measured memory_bytes: 5616
from collections import Counter

N = int(input())
s = []
for i in range(N):
    s.append(input())

c = Counter(s)
tmp = c.most_common()
ans = []

for i in range(len(tmp)):
    if tmp[i][1] != tmp[0][1]:
        break
    else:
        ans.append(tmp[i][0])

ans.sort()
print(*ans, sep="\n")

Measured memory_bytes: 119120
import java.util.*; import java.io.*; import java.math.*;
public class Main{
	//Don't have to see. start------------------------------------------
	static class InputIterator{
		ArrayList<String> inputLine = new ArrayList<String>(1024);
		int index = 0; int max; String read;
		InputIterator(){
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			try{
				while((read = br.readLine()) != null){
					inputLine.add(read);
				}
			}catch(IOException e){}
			max = inputLine.size();
		}
		boolean hasNext(){return (index < max);}
		String next(){
			if(hasNext()){
				return inputLine.get(index++);
			}else{
				throw new IndexOutOfBoundsException("There is no more input");
			}
		}
	}
	static HashMap<Integer, String> CONVSTR = new HashMap<Integer, String>();
	static InputIterator ii = new InputIterator();//This class cannot be used in reactive problem.
	static PrintWriter out = new PrintWriter(System.out);
	static void flush(){out.flush();}
	static void myout(Object t){out.println(t);}
	static void myerr(Object t){System.err.print("debug:");System.err.println(t);}
	static String next(){return ii.next();}
	static boolean hasNext(){return ii.hasNext();}
	static int nextInt(){return Integer.parseInt(next());}
	static long nextLong(){return Long.parseLong(next());}
	static double nextDouble(){return Double.parseDouble(next());}
	static ArrayList<String> nextStrArray(){return myconv(next(), 8);}
	static ArrayList<String> nextCharArray(){return myconv(next(), 0);}
	static ArrayList<Integer> nextIntArray(){
		ArrayList<String> input = nextStrArray(); ArrayList<Integer> ret = new ArrayList<Integer>(input.size());
		for(int i = 0; i < input.size(); i++){
			ret.add(Integer.parseInt(input.get(i)));
		}
		return ret;
	}
	static ArrayList<Long> nextLongArray(){
		ArrayList<String> input = nextStrArray(); ArrayList<Long> ret = new ArrayList<Long>(input.size());
		for(int i = 0; i < input.size(); i++){
			ret.add(Long.parseLong(input.get(i)));
		}
		return ret;
	}
	static String myconv(Object list, int no){//only join
		String joinString = CONVSTR.get(no);
		if(list instanceof String[]){
			return String.join(joinString, (String[])list);
		}else if(list instanceof ArrayList){
			return String.join(joinString, (ArrayList)list);
		}else{
			throw new ClassCastException("Don't join");
		}
	}
	static ArrayList<String> myconv(String str, int no){//only split
		String splitString = CONVSTR.get(no);
		return new ArrayList<String>(Arrays.asList(str.split(splitString)));
	}
	public static void main(String[] args){
		CONVSTR.put(8, " "); CONVSTR.put(9, "\n"); CONVSTR.put(0, "");
		solve();flush();
	}
	//Don't have to see. end------------------------------------------
	static void solve(){//Here is the main function
      int N = nextInt();
      if(N % 2 == 1){
        myout((N / 2) * ((N + 1) / 2));
      }else{
        myout((N / 2) * (N / 2));
      }
	}
	//Method addition frame start



	//Method addition frame end
}


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

#define pb push_back
#define mp make_pair
#define st first
#define nd second
typedef pair < int , int > pp;
const int mod = 1e9 + 7;
const int N   = 1e5 + 5;

int n,i,x,y,z,a,b,c,t;

signed main(){
    cin >> n;
    for(i=1;i<=n;i++){
        cin >> c >> a >> b;
        t = abs(a-x) + abs(b-y);
        if(t > c-z || (t-c+z) & 1){ puts("No"); return 0; }
        x = a;
        y = b;
        z = c;
    }
    
    puts("Yes");
    return 0;
}

Measured memory_bytes: 256
#http://judge.u-aizu.ac.jp/onlinejudge/commentary.jsp?id=ALDS1_4_A
#?????¢??¢?´¢
#???????????§?¨????????????????????????¨?????§??????????????\????????????????????????????????????
def linear_search(list_1, list_2):
    count = 0
    
    for a in list_1:
        i = 0
        list_2.append(a)
        while not a == list_2[i]:
            i += 1
        if not i == len(list_2) - 1:
            count += 1
            
        list_2 = list_2[:-1]
        
    return count

def main():
    n_listA = int(input())
    a = list(set([n for n in input().split()]))
    n_listB = int(input())
    b = list(set([n for n in input().split()]))
    print(linear_search(a,b))

if __name__ == "__main__":
    main()

Measured memory_bytes: 8336
//高知能系Vtuberの高井茅乃です。
//Twitter: https://twitter.com/takaichino
//YouTube: https://www.youtube.com/channel/UCTOxnI3eOI_o1HRgzq-LEZw

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

#define INF 1999999999
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define MODA 1000000007 

int main() {
	int ans = 0;
	int tmp;
	int n, q;
	cin >> n >> q;
	string s;
	cin >> s;
	s = "X" + s;
	int l, r;
	int rw[n+1] = {}, lw[n+1] = {};
	rw[0] = 0; lw[0] = 0;
	REP1(i, n){
		if(s.substr(i, 2) == "AC") rw[i] = rw[i-1] + 1;
		else rw[i] = rw[i-1];
		if(s.substr(i-1, 2) == "AC") lw[i] = lw[i-1] + 1;
		else lw[i] = lw[i-1];
		//cout << rw[i] << " " << lw[i] << endl;
	}
	REP(i, q){
		cin >> l >> r;
		cout << lw[r] - rw[l-1] << endl;
	}
}

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

using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;

#define REP(i, n, m) for(ll i=n; i<(ll)m; ++i)
#define IREP(i, n, m) for(ll i=n-1; i>=m; --i)
#define rep(i, n) REP(i, 0, n)
#define irep(i, n) IREP(i, n, 0)
#define all(v) v.begin(), v.end()

int main(){
    ll N;
    cin >> N;
    vll a(N+1);
    rep(i, N){
        cin >> a[i+1];
    }
    vll b(N+1, -1);
    IREP(i, N+1, 1){
        ll count = 0;
        for(ll j=i+i; j<=N; j+=i){
            count += b[j];
        }
        b[i] = (count+a[i]) % 2;
    }
    ll count = 0;
    rep(i, N){
        count += b[i+1];
    }
    cout << count << endl;
    rep(i, N){
        if(b[i+1]>0) cout << (i+1) << endl;
    }
}


Measured memory_bytes: 3968
n = int(input())
p = list(map(int,(input().split())))

hikaku = list(range(1,n+1))
count = 0
for i in range(n):
    if hikaku[i] != p[i]:
        count += 1
#print(count)
if count >=3:
    print("NO")
else:
    print("YES")


Measured memory_bytes: 2940
A, B, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = min(a) + min(b)
# print(ans)
for i in range(M):
  x, y, c = map(int, input().split())
  discount = a[(x-1)] + b[(y-1)] - c
  if (discount < ans):
    ans = discount
print(ans)


Measured memory_bytes: 18608
MOD = 998244353
N, S = map(int, input().split())
A = tuple(map(int, input().split()))
table = [[0] * (S + 1) for _ in range(N + 1)]
table[0][0] = 1
for n in range(N):
    for s in range(S + 1):
        now = table[n][s]
        table[n + 1][s] = (table[n + 1][s] + now * 2) % MOD
        if s + A[n] <= S:
            table[n + 1][s + A[n]] = (table[n + 1][s + A[n]] + now) % MOD
print(table[N][S])

Measured memory_bytes: 139044
#include <iostream>
using namespace std;
class Card{
public:
  char m;
  int n;
};
int main(void){
  int n,min,f=0;
  Card b[36],s[36];
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>b[i].m>>b[i].n;
    s[i]=b[i];
  }
  for(int i=0;i<n-1;i++){
    for(int j=n-1;j>i;j--){
      if(b[j-1].n>b[j].n)
	swap(b[j-1],b[j]);
    }
  }
  for(int i=0;i<n;i++){
    min=i;
    for(int j=i;j<n;j++){
      if(s[j].n<s[min].n){
	min=j;
      }
    }
    swap(s[i],s[min]);
  }
  for(int i=0;i<n-1;i++)
    cout<<b[i].m<<b[i].n<<" ";
  cout<<b[n-1].m<<b[n-1].n<<endl;
  cout<<"Stable"<<endl;
  for(int i=0;i<n-1;i++){
    if(b[i].m!=s[i].m)
      f=1;
    cout<<s[i].m<<s[i].n<<" ";
  }
  cout<<s[n-1].m<<s[n-1].n<<endl;
  if(f)
    cout<<"Not stable"<<endl;
  else
    cout<<"Stable"<<endl;
  return 0;
}

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

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

const int INF = 1e9;
const int MOD = 1e9 + 7;

// 4近傍、8近傍
int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};

int main() {
  // 入力
  int N, M;
  cin >> N >> M;
  vector<P> v;
  int a, b;
  for (int i = 0; i < M; i++) {
    cin >> a >> b;
    v.push_back(P(b, a));
  }

  sort(v.begin(), v.end());
  int ans = 1;
  int idx = v[0].first;
  for (int i = 1; i < M; i++) {
    if (v[i].second >= idx) {
      ans++;
      idx = v[i].first;
    }
  }

  // 解答
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 1400
n, m = gets.split.map(&:to_i)
a = Array.new(n) { gets.chomp.split(//) }
b = Array.new(m) { gets.chomp.split(//) }

f = catch(:found) do
  throw :found, true if a == b
  moves = a.length - b.length
  moves.times do |x|
    moves.times do |y|
      target = a[x, b.length].map {|l| l[y, b.length]}
      throw :found, true if b.flatten == target.flatten
    end
  end
  puts 'No'
end
puts 'Yes' if f


Measured memory_bytes: 5628
#include<iostream>
#include<stack>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<algorithm>
#include<iomanip>
#include<set>
#include<bitset>
#include<cmath>
#include<numeric>
#include<limits>

#define REP(i, m, n) for(int i = (m); i < (n); i++)
#define rep(i,n) REP(i,0,n)
#define NIL -1
using namespace std;
typedef long long ll;
typedef long long int lli;
static const int MOD = 10000007;
static const int MAX = 100005;

string S;
int N, K;



int main(){
  cin >> N >> K;
  cin >> S;
  int T = 0, ans = 0;
  REP(i, 1, N) {
    if (S[i-1] != S[i]) T++;
    else {
      ans++;
    };
  }
  int a, b;
  a = T/2; b = T % 2;
  if ( K <= a ) {
    ans += 2*K;
  } else if (b == 0) {
    ans += 2 * a;
  } else if (b == 1) {
    ans += 2 * a + b;
  }
  
  cout << ans << endl;
}


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

   typedef long long ll;
   typedef pair<ll, ll> Pii;
   typedef vector<ll> Vi;
   typedef vector<Vi> VVi;

   const double EPS = (1e-7);
   const ll INF =(1e13);
   const double PI = (acos(-1));
   const ll MOD = ll(1e9) + 7;

   #define REP(i, n) for(ll i = 0; i < (ll)(n); i++)
   #define REPR(i, n) for(ll i = n; i > -1; i--)
   #define FOR(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++)
   #define ALL(x) (x).begin(),(x).end()
   #define SORT(x) sort((x).begin(), (x).end())
   #define RSORT(x) sort((x).rbegin(), (x).rend())
   #define REVERSE(x) reverse((x).begin(), (x).end())
   #define SZ(x) ((ll)(x).size())
   #define pb push_back
   #define mp make_pair

   //chmax(a, b): a>bならaをbで更新　更新したときにtrueを返す
   //chmin(a, b): a<bならaをbで更新　更新したときにtrueを返す
   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; }

   #define dump(x) cerr<< #x << "= " << (x) << endl;

   ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
   ll pow(ll a, ll b){if (b == 0) return 1; else if (b % 2 == 0) return pow(a * a, b / 2); else return pow(a * a, b / 2) * a;}
   ll pow(ll a, ll b, ll m){if (b == 0) return 1; else if (a == 0) return 0; else if (b % 2 == 0) return (pow((a * a) % m, b / 2, m) % m); else return (pow((a * a) % m, b / 2, m) * a) % m;}
   ll residue(ll a, ll m){return ((a % m) + m) % m;};

   ll dx[4]={1,0,-1,0};
   ll dy[4]={0,1,0,-1};

const ll MAX_N = 1e5;
ll n, a, b, c;
ll E[100][100] = {};
ll comb[MAX_N + 1] = {};

ll expecation(ll x, ll y){
  if(x >= n || y >= n) return 0;
  if(E[x][y] > 0) return E[x][y];
  E[x][y] = pow(a + b, MOD - 2, MOD) * ((100 + a * expecation(x + 1, y) + b * expecation(x, y + 1)) % MOD) % MOD;
  return E[x][y];
}
void initcomb(){
  comb[0] = 1;
  REP(i, n){
    comb[i + 1] = ((comb[i] * (n + i)) % MOD) * pow(i + 1, MOD - 2, MOD) % MOD;
  }
}
int main(){
  cin >> n >> a >> b >> c;
//  cout << expecation(0, 0) << endl;
  initcomb();
  ll p = a * pow(a + b, MOD - 2, MOD) % MOD;
  ll q = b * pow(a + b, MOD - 2, MOD) % MOD;
  ll temp1 = 0, temp2 = 0, ans = 0;
  REP(i, n){
    temp1 += (i * comb[i] % MOD) * pow(q, i, MOD) % MOD; temp1 %= MOD;
    temp2 += (i * comb[i] % MOD) * pow(p, i, MOD) % MOD; temp2 %= MOD;
  }
  ans = ((n + (pow(p, n, MOD) * temp1 % MOD) + (pow(q, n, MOD) * temp2 % MOD)) * 100 % MOD) * pow(100 - c, MOD - 2, MOD) % MOD;
  cout << ans << endl;
}


Measured memory_bytes: 1024
(function(input) {
    var p = input.split(' ').map(Number);
    var a = p[0];
    var b = p[1];
    var c = p[2];
    c = c / 180 * Math.PI;
    console.log(area(a, b, c));
    console.log(perimeter(a, b, c));
    console.log(height(b, c));
})(require('fs').readFileSync('/dev/stdin', 'utf8'));

function area(a, b, c) {
    return a * b * Math.sin(c) / 2;
}

function perimeter(a, b, c) {
    return a + b + Math.sqrt(a * a + b * b - 2 * a * b * Math.cos(c));
}

function height(b, c) {
    return b * Math.sin(c);
}

Measured memory_bytes: 7644
#include<cstdio>
using namespace std;
int main(void)
{
	int i,x,gou,kin;
	scanf("%d",&gou);
	while(!(gou==0)){
		for(i=0;i<9;i++){
			scanf("%d",&kin);
			gou-=kin;
		}
		printf("%d\n",gou);
		scanf("%d",&gou);
	}
	return 0;
}

Measured memory_bytes: 1028
#include <iostream>
#include <vector>
#include <map>
 
using namespace std;
 
int main(void) {
  int N;
  cin >> N;
  vector<string> W(N);
  map<string, int> S;

  for(int i = 0; i < N; i++){
    cin >> W[i];
  }
  for (int i = 0; i < N - 1; i++) {
    if (W[i][W[i].size() - 1] != W[i + 1][0]) {
      cout << "No" << endl;
      return 0;
    }
  }
  for (int i = 0; i < N; i++) {
    S[W[i]]++;
    if(S[W[i]] == 2){
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;

  return 0;
}

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

int main() {
  int n;
  string s;
  cin >> n >> s;
  int ans = 0;
  rep(i,1000) {
    string t;
    int x = i;
    rep(j,3) {
      t += '0'+x%10;
      x /= 10;
    }

    int ti = 0;
    rep(j,n) {
      if (s[j] == t[ti]) {
        ti++;
        if (ti == 3) break;
      }
    }
    if (ti == 3) ans++;
  }
  cout << ans << endl;
}


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

void solve(ll node,ll vis[],vector<ll> org[],ll dp[])
{

		vis[node]=1;
		for(ll k=0;k<org[node].size();k++)
		{
			if(vis[org[node][k]]==0)
				solve(org[node][k],vis,org,dp);
			
				dp[node]=max(dp[node],1+dp[org[node][k]]);
		}
}


int main()
{
	int node,edge;
	cin>>node>>edge;

	vector<ll> org[node+1];
	ll dp[node+1]={0};
	ll vis[node+1]={0};

	for(ll i=0;i<edge;i++)
	{
		ll u,v;
		cin>>u>>v;

		org[u].push_back(v);
	}

	for(ll j=1;j<=node;j++)
	{
		if(org[j].empty())
			{
				dp[j]=0;
				vis[j]=1;
			}
	}

for(ll t=1;t<=node;t++)
{
	if(vis[t]==0)
	solve(t,vis,org,dp);
}
ll mx=0;

for(ll y=1;y<=node;y++)
{
	mx=max(mx,dp[y]);	
}

cout << mx;
return 0;

}

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

int main()
{
   int n;

   cin>>n;
    map<int , int> b;


    for(int i=-1000;i<=1000;i++)
        {
            long long int temp=i*i*i*i*i;
            b[temp]=i;
        }

    for(int i=0;i<=1000;i++)
    {
        long long int temp=i*i*i*i*i;
        if(b.find(temp-n)!=b.end())
        {
            cout<<i<<" "<<b[temp-n];
            break;
        }
    }
}


Measured memory_bytes: 3696
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<string>
#include<algorithm>
#include<iostream>
#include<bitset>
#include<functional>
#include<numeric>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<cmath>
#include<random>
#include<ctime>
#include<complex>
using namespace std;
typedef long long LL;
mt19937 gene(233);
typedef complex<double> Complex;
#define fi first
#define se second
#define ins insert
#define pb push_back
inline char GET_CHAR(){
	const int maxn = 131072;
	static char buf[maxn],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,maxn,stdin),p1==p2)?EOF:*p1++;
}
inline int getInt() {
	int res(0);
	char c = getchar();
	while(c < '0') c = getchar();
	while(c >= '0') {
		res = res * 10 + (c - '0');
		c = getchar();
	}
	return res;
}

inline LL fastpo(LL x, LL n, LL mod) {
	LL res(1);
	while(n) {
		if(n & 1) {
			res = res * (LL)x % mod;
		}
		x = x * (LL) x % mod;
		n /= 2;
	}
	return res;
}

inline string itoa(int x, int width = 0) {
  string res;
  if(x == 0) res.push_back('0');
  while(x) {
    res.push_back('0' + x % 10);
    x /= 10;
  }
  while((int)res.size() < width) res.push_back('0');
  reverse(res.begin(), res.end());
  return res;
}
const int _B = 131072;
char buf[_B];
int _bl = 0;
inline void flush() {
	fwrite(buf, 1, _bl, stdout);
	_bl = 0;
}
__inline void _putchar(char c) {
	if(_bl == _B) flush();
	buf[_bl++] = c;
}
inline void print(LL x, char c) {
	static char tmp[20];
	int l = 0;
	if(!x) tmp[l++] = '0';
	else {
		while(x) {
			tmp[l++] = x % 10 + '0';
			x /= 10;
		}
	}
	for(int i = l - 1; i >= 0; i--) _putchar(tmp[i]);
	_putchar(c);
}
const int N = 3033;
const int LOG = 20;
const int mod = 998244353;
const int inf = 1e9 + 7;
int n, m;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int dp[N][N][2];
__inline void add(int & a, int b) {
	if((a += b) >= mod) a -= mod;
}
int main() {
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	dp[a][b][0] = 1;
	for(int i = a; i <= c; i++) {
		for(int j = b; j <= d; j++) {
			add(dp[i + 1][j][1], (dp[i][j][1] + dp[i][j][0]) * (LL)j % mod);
			add(dp[i][j + 1][0], dp[i][j][0] * (LL)i % mod);
			add(dp[i][j + 1][0], dp[i][j][1]);
		}
	}
	cout << (dp[c][d][0] + dp[c][d][1]) % mod << endl;
}






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


int main()
{
    int m, f, r;
    
    while(true)
    {
        cin >> m >> f >> r;
        if (m==-1 && f==-1 && r==-1)    break;

        char rank;
        int sum = m+f;
        if (m==-1 || f==-1)
        {
            rank = 'F';
        }
        else
        {
            if (sum>=80)                rank = 'A';
            else if (65<=sum && sum<80) rank = 'B';
            else if (50<=sum && sum<65) rank = 'C';
            else if (30<=sum && sum<50) rank = 'D';
            else                        rank = 'F';
            
            if (rank == 'D' && 50<=r)   rank = 'C';
        }
        cout << rank << endl;
    }
    
    return 0;
}

Measured memory_bytes: 1152
#include <iostream>
#include <iomanip>
#include <cmath>
#include <functional>
#include <algorithm>
#include <numeric>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <boost/range/irange.hpp>
#include <boost/container/static_vector.hpp>
#include <boost/utility/string_ref.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/math/common_factor_rt.hpp>

template <class... Args>
struct tuple_input_impl;
template <std::size_t i, std::size_t... tail>
struct tuple_input_impl<std::index_sequence<i, tail...>>
{
    template <class... Args>
    static void f(std::tuple<Args...>& x)
    {
        std::cin >> std::get<i>(x);
        tuple_input_impl<std::index_sequence<tail...>>::f(x);
    }
};
template <>
struct tuple_input_impl<std::index_sequence<>>
{
    static void f(...) {}
};

template <class... Args>
std::istream& operator>>(std::istream& in, std::tuple<Args...>& x)
{
    tuple_input_impl<std::index_sequence_for<Args...>>::f(x);
    return in;
}

template <class T>
T read()
{
    T res;
    std::cin >> res;
    return res;
}
template <class T>
std::vector<T> read(std::size_t n)
{
    std::vector<T> res(n);
    for (std::size_t i = 0; i < n; ++i) std::cin >> res[i];
    return res;
}

template <class T, class... Args>
void out_impl(T&& v, Args&&... args)
{
    std::cout << std::forward<T>(v) << ' ';
    impl(std::forward<Args>(args)...);
}
template <class T>
void out_impl(T&& v) { std::cout << std::forward<T>(v); }
template <class... Args>
void out(Args&&... args)
{
    out_impl(std::forward<Args>(args)...);
    std::cout << '\n';
}
template <class... Args>
void out_noreturn(Args&&... args) { out_impl(std::forward<Args>(args)...); }

template <class T>
void print(const T& container)
{
    bool first = true;
    for (auto&& x : container) {
        if (!first) std::cout << ' ';
        std::cout << x;
        first = false;
    }
    std::cout << '\n';
}

void prog()
{
    char c;
    std::cin >> c;
    switch (c) {
    case 'A':
        out('T');
        break;
    case 'T':
        out('A');
        break;
    case 'C':
        out('G');
        break;
    case 'G':
        out('C');
        break;
    }
}

int main()
{
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(15);
    prog();
    return 0;
}


Measured memory_bytes: 256
MM = input().split()
N = int(MM[0])
T = int(MM[1])
list1 =[]
for i in range(N):
  NN = input().split()
  c = int(NN[0])
  t = int(NN[1])
  if t <= T:
    list1.append(c)
list1.sort()
if len(list1) == 0:
  print('TLE')
else:
  print(list1[0])

Measured memory_bytes: 9060
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <stack>
#include <deque>
#include <cmath>
#include <map>
using ll = long long;
using namespace std;

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


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define eps LDBL_EPSILON
#define moder 1000000007
#define int long long
#define double long double
#define ll long long
#define INF LLONG_MAX/3
#define P std::pair<int,int>
#define prique priority_queue<int,vector<int>,greater<int>>
using namespace std;
signed main(){
	int a,b;
	cin>>a>>b;
	int ans=0;
	for(int i=a;i<=b;i++){
		string s=to_string(i);
		reverse(s.begin(),s.end());
		if(to_string(i)==s)ans++;
	}
	cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(ll i=0;i<n;i++)
const ll INF=1e18;
const int inf=2e9;
const ll MOD=1000000007;
const ll dy[4]={1,0,-1,0};
const ll dx[4]={0,-1,0,1};
const int MAX = 1100000;
ll 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;
    }
}
int main(){
    COMinit();
    ll N;cin>>N;
    ll info[N];
    rep(i,N)cin>>info[i];
    ll count[1000001];
    rep(i,1000001)count[i]=0;
    rep(i,N){
        map<ll,ll> now;
        ll p=info[i];
        for(ll j=2;j<=sqrt(info[i])+10;j++){
            while(p%j==0){
                p/=j;
                if(now.count(j))now.at(j)++;
                else now.emplace(j,1);
            }
            if(p==1)break;
        }
        if(p!=1)now.emplace(p,1);
        for(auto q:now)count[q.first]=max(q.second,count[q.first]);
    }
    ll LCM=1;
    rep(i,1000001){
        ll p=count[i];
        while(p--)LCM=LCM*i%MOD;
    }
    ll ans=0;
    rep(i,N)ans=(ans+LCM*inv[info[i]]%MOD)%MOD;
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 33920
import java.util.Scanner;
import java.util.stream.Stream;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = Integer.parseInt(sc.nextLine().split(" ")[1]);
        System.out.println(Stream.of(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).filter(h -> k <= h).count());
    }
}

Measured memory_bytes: 37692
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
typedef long long LL;
const LL INF = 0x3f3f3f3f3f3f3f3f;

vector <LL> G[1005];
LL w[1005],z[1005],dp[5005];
LL n,ff;

void dfs(LL u,LL f){
	for(LL i = 0;i < G[u].size();i ++) dfs(G[u][i],u);
	
	for(LL j = 0;j <= w[u];j ++) dp[j] = INF; dp[0] = 0;
	for(LL i = 0;i < G[u].size();i ++){
		LL v = G[u][i];
		for(LL j = w[u];j >= 0;j --){
			LL mi = INF;
			if(j >= w[v]) mi = min(mi,dp[j - w[v]] + z[v]);
			if(j >= z[v]) mi = min(mi,dp[j - z[v]] + w[v]);
			dp[j] = mi;
		}
	}
	for(LL i = w[u];i >= 0;i --) z[u] = min(z[u],dp[i]);
}

int main(){
	memset(z,INF,sizeof(z));
	cin >> n;
	for(LL i = 2;i <= n;i ++){
		cin >> ff;
		G[ff].push_back(i);
	}
	for(LL i = 1;i <= n;i ++) cin >> w[i];
	dfs(1,0);
	cout << (z[1] < INF ? "POSSIBLE" : "IMPOSSIBLE") << endl;
	return 0;
}
//

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define REP(i,x,n) for(int i=x;i<(int)n;i++)
#define rep(i,n) REP(i,0,n)
#define sp(p) cout<<setprecision(16)<<fixed<<p<<endl;
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define SORT(a) sort(all(a))
#define RSORT(a) sort(rall(a))
#define UNIQ(a) unique(all(a))
#define UNIQNUM(a) UNIQ(a)-a.begin()
#define UNIQIT(a) a.erase(UNIQ(a), a.end());
#define VOUT(v,i) rep(i,v.size())cout<<v[i]<<(i==v.size()-1?"\n":" ");
#define vout(v) VOUT(v,z);
#define vdbg(v,i) cout<<#v<<": ";for(int i=0;i<(int)v.size();i++){cout<<v[i]<<" ";}cout<<"\n";
#define vmin(v) *min_element(all(v))
#define vmax(v) *max_element(all(v))
#define vsum(v) accumulate(all(v), 0LL)
#define MOUT(m,r,c) rep(i,r){rep(j,c){cout<<m[i][j]<<" ";}cout<<endl;}
#define mout(m) MOUT(m,m.size(),m[0].size())
#define debg(a) cout<<#a<<": "<<a<<endl;
#define show(a) for(cont &y:a){for(cont &x:y){cout<<x<<" ";}cout<<endl;}
#define digit(a) to_string(a).length();
template<class T>inline int out(const T &t){ print(t); putchar('\n'); return 0; }
template<class T>inline T gcd(T a,T b){if(b==0)return a; return(gcd(b,a%b));}
template<class T>inline T lcm(T a,T b){return a/gcd(a,b)*b;}
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef vector<ll> V;
typedef vector<vector<ll>> VV;
// const long long MOD=1000000007;
const long long INF = 1e18;
#define EPS (1e-7)
#define PI (acos(-1))
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) { a = b; return true; }
    return false;
}
template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) { a = b; return true; }
    return false;
}


void solve(long long H, long long W){
    if(H==1 || W==1){
        cout << 1 << endl;
        return;
    }
    ll ret=0;
    if(H*W%2){
        ret=(H*W/2)+1;
    }else{
        ret=H*W/2;
    }
    cout << ret << endl;
}

int main(){
    long long H;
    scanf("%lld",&H);
    long long W;
    scanf("%lld",&W);
    solve(H, W);
    return 0;
}


Measured memory_bytes: 256
a,b,k = map(int, input().split())
ans = []
if a > b:
    n = b
else:
    n = a
for i in range(1,n+1):
    if a % i == 0 and b % i == 0:
        ans.append(i)
l = len(ans)
print(ans[l-k])

Measured memory_bytes: 3060
import java.util.Iterator;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);
		String s1 = scan.next();
		String s2 = scan.next();
		
		String ans = "No";
		char[] list = new char[s1.length()];
		for (int i = 0; i < s1.length(); i++) {
			for (int j = 0; j < s1.length(); j++) {
				if (j == 0) {
					list[0] = s1.charAt(s1.length() - 1);
					continue;
				}
				list[j] = s1.charAt(j - 1);
			}
			StringBuilder sb = new StringBuilder();
			for (int j = 0; j < list.length; j++) {
				sb.append(String.valueOf(list[j]));
			}
			s1 = sb.toString();
			if (s1.equals(s2)) {
				ans = "Yes";
				break;
				
			}
		}
		System.out.println(ans);
	}
}

Measured memory_bytes: 24020
//#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include "bits/stdc++.h"

#define rep(i,n) for(ll (i)=0;(i)<(ll)(n);(i)++)
#define all(x) (x).begin(),(x).end()

#define MOD 1000000007LL
#define INF (1LL<<60LL)
#define int long long
#define MAX_N (100001)
typedef long long ll;

using namespace std;




signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	while (1) {
		int x = 0;
		int d; cin >> d;
		int ans = 0;
                if(cin.eof()) break;
		while (x < 600) {
			ans += x * x;
			x += d;
		}
		ans *= d;
		cout << ans << endl;
	}
}



Measured memory_bytes: 3024
#include<bits/stdc++.h>
#define watch(x) cout << (#x) << " is " << (x) << endl
typedef long long ll;
using namespace std;
int static fast = [](){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0); return 0;
}();

int main() {
    int n, h;
    double t, a;
    cin >> n >> t >> a;
    int ans = 0;
    double diff = 1e9;
    for(int i = 0; i < n; i++) {
        cin >> h;
        double t2 = t - h*0.006;
        if (abs(a-t2) < diff) {
            diff = abs(a-t2);
            ans = i+1;
        }
    }
    cout << ans << endl;
    return 0;
}




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

int main(){
  int n,k; cin >>n >>k; int sum=0;
  vector<int>v(n);
  for(int i=0; i<n; i++) cin >>v[i];
  for(int i=0; i<k; i++) sum+=v[i];
  int tem=sum;
  for(int i=k; i<n; i++){
    tem+=v[i]-v[i-k];
    sum=max(sum,tem);
  }
  cout <<fixed<<setprecision(10)<<(sum+k)/2.0;
return 0;}

Measured memory_bytes: 1024
// C - 100 to 105
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define rp(i,s,e) for(int i=(s);i<(e);++i)

int main(){
	int X; cin>>X;
	vi dp(X+1, false);
	dp[0] = true;
	rp(i, 0, X+1)
		if(dp[i])
			rp(y, 100, 105+1) if(i+y <= X) dp[i+y] = true;
	puts(dp[X]? "1":"0");
}

Measured memory_bytes: 640
#include<stdio.h>
#define N 8
#define FREE 0
#define NOT_FREE 1

int row[N],col[N],leftdia[2*N-1],rightdia[2*N-1],X[N][N];//leftdia左下方向、rightdia右下方向

void initialize(void);
void Queens(int);

int main(){

  int i,j,k,r,c;

  //初期化
  initialize();

  for(i=0;i<N;i++){
    for(j=0;j<N;j++){
      X[i][j]=FREE;
    }
  }

  scanf("%d",&k);
  for(i=0;i<k;i++){
    scanf("%d %d",&r,&c);
    X[r][c]=NOT_FREE;
  }

  Queens(0);

  return 0;
  
}

void initialize(){
  
  int i;
  
  for(i=0;i<N;i++){
    row[i]=FREE;
    col[i]=FREE;
  }
  
  for(i=0;i<2*N-1;i++){
    leftdia[i]=FREE;
    rightdia[i]=FREE;
  }
}

void Queens(int i){

  int j;
  
  if(i==N){//表示して終わる
    
    for(i=0;i<N;i++){
      for(j=0;j<N;j++){
	if(X[i][j]==NOT_FREE){
	  if(row[i]!=j) return;
	}
      }
    }//for

    for(i=0;i<N;i++){
      for(j=0;j<N;j++){
	if(row[i]==j) printf("Q");
	else printf(".");
      }
      printf("\n");
    }
    
    return;
    
  }

  for(j=0;j<N;j++){
    
    if(NOT_FREE==col[j] || NOT_FREE==leftdia[i+j] || NOT_FREE==rightdia[i-j+N-1]){
      continue;
    }
    
    row[i]=j;
    col[j]=NOT_FREE;
    leftdia[i+j]=NOT_FREE;
    rightdia[i-j+N-1]=NOT_FREE;
    
    Queens(i+1);
    
    row[i]=FREE;
    col[j]=FREE;
    leftdia[i+j]=FREE;
    rightdia[i-j+N-1]=FREE;
    
  }
  
}





Measured memory_bytes: 2108
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct node{
  struct node *r;
  struct node *l;
  struct node *p;
  int key;
};
typedef struct node * Node;
#define NIL NULL
Node root;
Node min(Node x);
Node max(Node x);
Node search(Node u, int k);
Node successor(Node x);
void delete(Node z){};
void insert(int k);
void inorder(Node u);
void preorder(Node u);
int main(){
  int n,i,x;
  Node t;
  char com[20];;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%s",com);
    if (com[0]=='f'){
      scanf("%d",&x);
       t= search(root,x);
      if(t!=NIL) printf("yes\n");
      else printf("no\n");
    }
    else if(com[0]=='i'){
      scanf("%d",&x);
      insert(x);
    }
    else if(com[0]=='p'){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
    
    else if(com[0]=='d'){
      scanf("%d",&x);
      delete(search(root,x));
    }
  }
  return 0;
}
Node min(Node x){
  while(x->l!=NIL){
    x= x->l;}
  return x;
}
Node max(Node x){
  while(x->r!=NIL){
    x=x->r;
  }
  return x;
}
Node search(Node u,int k){
  while(u!=NIL &&u->key!=k){
    if (k>u->key){
      u=u->r;
    }
    else u=u->l;
  }
  return u;
}
Node successor(Node x){
  Node y;
  if(x->r!=NIL) return min(x->r);
  y=x->p;
  while(y!=NIL && x==y->r){
    x=y;
    y=y->p;
  }
  return x;
}
void insert (int k){
  Node y= NIL;
  Node x=root;
  Node z;
  
  z=malloc(sizeof(struct node));
  z->key=k;
  z->l=NIL;
  z->r=NIL;
  
  while(x!=NIL){
    y=x;
    if(z->key<x->key){
      x=x->l;
    }  else x=x->r;
  }
  z->p=y;
  if(y==NIL) root=z;
  else if(z->key<y->key){
    y->l=z;
  }
  else y->r=z;
}

void inorder(Node u){
  if(u==NIL )return ;
  inorder(u->l);
  printf(" %d",u->key);
  inorder(u->r);
}

void preorder(Node u){
  if(u==NIL)return ;
  printf(" %d",u->key);
  preorder(u->l);
  preorder(u->r);
}



Measured memory_bytes: 25128
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<map>
#include<string.h>
#include<complex>
#include<math.h>
#include<queue>
#include<time.h>
using namespace std;
typedef long long int llint;
typedef pair<int, int> pint;
typedef pair<llint, llint> pllint;
typedef vector<int> vint;
typedef vector<llint> vllint;
typedef vector<pint> vpint;
typedef vector<pair<llint, llint>> vpllint;
typedef vector<vector<int>> vvint;
typedef vector<vector<llint>> vvllint;
typedef vector<vector<pint>> vvpint;
typedef vector<bool> vbool;
#define rep(i,n) for(int i=0;i<n;i++)
#define drep(i,n) for(int i=n-1;0<=i;i--)
#define yes(ans) if(ans)cout<<"yes"<<endl;else cout<<"no"<<endl;
#define Yes(ans) if(ans)cout<<"Yes"<<endl;else cout<<"No"<<endl;
#define YES(ans) if(ans)cout<<"YES"<<endl;else cout<<"NO"<<endl;
#define POSSIBLE(ans) if(ans)cout<<"POSSIBLE"<<endl;else cout<<"IMPOSSIBLE"<<endl;
#define Pi 3.1415926535897932384626
#define mod llint(998244353)

class UnionFind {
public:
	//親の番号を格納する。親だった場合は-(その集合のサイズ)
	vector<int> Parent;

	//作るときはParentの値を全て-1にする
	//こうすると全てバラバラになる
	UnionFind(int N) {
		Parent = vector<int>(N, -1);
	}

	//Aがどのグループに属しているか調べる
	int root(int A) {
		if (Parent[A] < 0) return A;
		return Parent[A] = root(Parent[A]);
	}

	//自分のいるグループの頂点数を調べる
	int size(int A) {
		return -Parent[root(A)];//親をとってきたい
	}

	//AとBをくっ付ける
	bool connect(int A, int B) {
		//AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
		A = root(A);
		B = root(B);
		if (A == B) {
			//すでにくっついてるからくっ付けない
			return false;
		}

		//大きい方(A)に小さいほう(B)をくっ付けたい
		//大小が逆だったらひっくり返しちゃう。
		if (size(A) < size(B)) swap(A, B);

		//Aのサイズを更新する
		Parent[A] += Parent[B];
		//Bの親をAに変更する
		Parent[B] = A;

		return true;
	}
};

//aとbの最大公約数を求めるよ
long long GCD(long long a, long long b) {
	if (b == 0) return a;
	else return GCD(b, a % b);
}

// 返り値: a と b の最大公約数
// ax + by = gcd(a, b) を満たす (x, y) が格納される
long long extGCD(long long a, long long b, long long& x, long long& y) {
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	long long d = extGCD(b, a % b, y, x);
	y -= a / b * x;
	return d;
}

bool check(llint a, llint b) {
	return a > b;
}

// mod. m での a の逆元 a^{-1} を計算する
long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}

//aCbを1000000007で割った余りを求める
llint convination(llint a, llint b) {
	llint ans = 1;
	for (llint i = 0; i < b; i++) {
		ans *= a - i;
		ans %= 1000000007;
	}
	for (llint i = 1; i <= b; i++) {
		ans *= modinv(i, 1000000007);
		ans %= 1000000007;
	}
	return ans;
}

//aのb乗をmodで割った余りを求める
llint power(llint a, llint b) {
	if (b == 1)return a;
	if (b == 0)return 1;
	llint tmp = power(a, (llint)b / 2);
	tmp *= tmp;
	tmp %= mod;
	if (b % 2 == 1) {
		tmp *= a;
		tmp %= mod;
	}
	return tmp;
}

int main() {
	int n;
	cin >> n;
	cout << n * n << endl;
	return 0;
}

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

int main(){
  int N,D,A;
  cin>>N>>D>>A;
  vector<pair<int,int> > xh(N);
  for(int i=0;i<N;i++){
    int x,h;
    cin>>x>>h;
    xh.at(i)=make_pair(x,(h-1)/A+1);
  }

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

  long long ans=0;
  vector<int> sum(N+1,0);
  for(int i=0;i<N;i++){
    if(i!=0){
      sum.at(i)+=sum.at(i-1);
    }
    if(sum.at(i)<xh.at(i).second){
      int tmp=xh.at(i).second-sum.at(i);
      ans+=tmp;
      int k=(int)(upper_bound(xh.begin(),xh.end(),make_pair(xh.at(i).first+2*D,1000000001))-xh.begin());
      sum.at(i)+=tmp;
      sum.at(k)-=tmp;
    }
  }

  cout<<ans<<endl;
}


Measured memory_bytes: 2560
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <limits.h>

#define max 100

//qsort(str, n, sizeof(int), up_comp);
int up_comp(const void *a, const void *b){return *(int*)a - *(int*)b;}
int down_comp(const void *a, const void *b){return *(int*)b - *(int*)a;}
int count_digit(int a){int i=0;while(a!=0){a=a/10;i++;}return i;}
int euclid( int a, int b ){int temp;if(a<b){temp=a;a=b;b=temp;}if(b<1)return -1;if(a%b==0) return b;return euclid(b,a%b);}

int main()
{
    int w, s;
    
    scanf("%d%d", &s, &w);
    
    if (w>=s) {
        printf("unsafe");
    } else {
        printf("safe");
    }
    
    
    return 0;
}



Measured memory_bytes: 1724
import java.util.Scanner;
import java.util.SortedSet;
import java.util.TreeSet;

public class Main {
	public static void main(String[] args) {
		Main main = new Main();
		main.run();
	}

	public void run() {
		Scanner sc = new Scanner(System.in);
		String s=sc.next();
		int k=sc.nextInt();
		SortedSet<String> set = new TreeSet<String>();

		for(int i=0; i<s.length(); i++) {
			for(int j=i; j-i<k && j<s.length(); j++){
				set.add(s.substring(i,j+1));
			}
		}

		int j=1;
		for(String ss : set) {
			if(k==j) {
				System.out.println(ss);
				break;
			}
			j++;
		}
		sc.close();
	}
}


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

int main(){
    int n; cin >> n;
    int m=-1, ans;
    for(int i = 0; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        if(m==-1){
            m = a;
            ans = a+b;
        }
        else if(a>m){
            m = a;
            ans = a+b;
        }
    }
    
    cout << ans << endl;

    
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <set>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <map>
#include <cstring>
#include <cmath>
using namespace std;
#define MAXA 1001
#define MAXB 1001
#define MAXH 1000000001
#define MAXW 405
#define INF 5000
#define MAXN 200001
#define MAXM 200001
#define MAXK 200002
#define MAXP 1000001
#define MOD 1000000007
#define EPS (1e-10)
typedef long long ll;
typedef pair<ll, ll> P;

ll N, K;

int main(){
    cin >> N >> K;
    ll ans = 0;
    for(ll i = K;i <= N + 1;i++){
        ll bl, ul;
        bl = (i * (i - 1) / 2) % MOD;
        ul = (i * (2 * N - i + 1) / 2) % MOD;
        ans = (ans + (ul - bl + 1) % MOD) % MOD;
    }

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


    return 0;
}

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

struct edge{
    int to,weight;
    edge(int to,int weight):to(to),weight(weight){}
};
using Graph = vector<vector<int>> ;
using GraphEdge = vector<vector<int>> ;

long long modinv(long long a, long long m=MOD) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m; 
    if (u < 0) u += m;
    return u;
    /*MODの割り算の際に
    a/＝b;
    を
    a *= modinv(b,MOD);
    とする。
        */
}
int main(){
    int N,M;cin >> N >> M;
    const int MAXM = 100000;
    ll X[MAXM];
    priority_queue<int> PQ;
    int sum = 0;
    ll mi = INT32_MAX;
    ll ma = INT32_MIN;
    rep(i,M){
        cin >> X[i];
        mi = min(mi,X[i]);
        ma = max(ma,X[i]);

    }
    if(N>=M){
        cout << 0 << endl;
        return 0;
    }
    // cout << mi << " " << ma << endl;
    sort(X,X+M);
    
    rep(i,M){
        if(i>0)PQ.push(X[i]-X[i-1]);
    }

    int ans = ma-mi;

    for(int i=0;i<N-1;i++){
        if(!PQ.empty()){
            ans -= PQ.top();
            PQ.pop();
        }
    }

    cout << ans << endl;
    



    return 0;
}

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

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

  int n, d;
  cin >> n >> d;
  int max_val = 2 * d + 1;
  if (n % max_val)
    cout << n / max_val + 1 << endl;
  else
    cout << n / max_val << endl;
}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10000000)
n,m = list(map(int, input().split()))
s = [0 for i in range(n+1)]
t = [-1 for i in range(n+1)]
for i in range(m):
    x = int(input())
    s[x] = 1

def dx(r):
    global t
    if t[r]>=0:
        return t[r]
    x=0
    y=0
    #print(i)
    if s[r+1]==0 and r==n-2:
        return 2
    if s[r+1]==1 and r==n-2:
        return 1
    if r==n-1:
        return 1
    if r==n:
        return 0
    if s[r+1] == 0:
        x=dx(r+1)
    if s[r+2] == 0:
        y=dx(r+2)
    #print([i,x,y])
    t[r]=(x+y)%1000000007
    return (x+y)%1000000007

ans=dx(0)

print(ans)

Measured memory_bytes: 90516